Оптимизация приложений под Android x86: проверенные способы

Любое приложение для Android, даже написанное только на скриптовых языках (таких как Java или HTML5), в конечном счёте использует базисные компоненты среды исполнения, которые должны быть оптимизированы. Хорошими примерами для иллюстрации оптимизационных подходов и потребностей являются приложения, использующие технологии мультимедиа и дополненной реальности, описанные ниже. Для платформы Android (смартфоны и планшеты) Intel использует различные виды процессоров Atom, имеющих SSSE3 уровень векторизации и обычно 2 ядра с гипертредингом – считайте это намеком :) Для тех, кто намек понял, под катом – история оптимизации и распараллеливания одного конкретного приложения израильской компании iOnRoad ^[1] — iOnRoad.

Постановка задачи

iOnRoad представляет из себя приложение дополненной реальности для смартфонов, помогающее безопасному вождению автомобиля. Используя GPS, сенсоры и видеокамеру смартфона, а также современные алгоритмы компьютерного зрения, приложение предупреждает водителя об уходе с полосы, а также возможном столкновении с другими машинами и препятствиями. Приложение крайне популярно (более миллиона загрузок!), отмечено всевозможными наградами, и имело всего два недостатка:
1. Не предупреждает о пьяных водителях соседних машин и красивых девушках, голосующих на дороге по ходу следования вашего авто.
2. Требует оптимизации, в том числе и по энергопотреблению, так как исходная версия не могла использоваться без подключения смартфона к питанию более 30 минут, за это время батарея полностью садилась.

На данный момент недостаток остался только один. Первый.

Итак, работая в реальном времени, приложение конвертирует каждый исходный фрейм формата YUV420/NV21 с камеры смартфона в формат RGB перед дальнейшей его обработкой.
Изначально функция, реализующая данную трансформацию, использовала до 40% ресурсов процессора, тем самым ограничивая возможности дальнейшей обработки изображений. Таким образом, потребность в оптимизации выглядела настоятельной.
Единственная существующая оптимизированная функция, которую мы нашли, это функция YUV420ToRGB из пакета IPP (Intel Integrated Performance Primitives library ^[2]), но она не имеет необходимого для iOnRoad сочетания поддерживаемых входных и выходных форматов. Кроме того, она не многопоточная.
Поэтому было принято решение написать новый оптимизированный код, реализующий необходимую трансформацию.

Трансформация из YUV420/NV21 в RGB

Формат YUV420/NV21 содержит три 8-битные компоненты – яркости Y (чёрно-белую) и две компоненты цветности U и V.

Для получения четвёрки пикселей в стандартном формате RGB (с его тремя цветными компонентами для каждого пикселя), каждой четверке компонент Y требуется только одна пара соответствующих компонент U и V.
На картинке выше соответствующие четверки Y и обслуживающие их пары U и V помечены одним цветом. Данный формат (обычно называемый YUV) обеспечивает двукратную компрессию по сравнению с RGB.

Трансформация YUV в RGB — целочисленный подход с использованием таблиц (look-up table, LUT)

Трансформация YUV в RGB производится по простой линейной формуле. Чтобы избежать преобразования в числа с плавающей точкой, в iOnRoad воспользовались следующей хорошо известной целочисленной аппроксимацией:

Промежуточные результаты вычислений по этой формуле больше, чем 2¹⁶ – это важный момент для дальнейших обсуждения векторизации.
Для скалярных вычислений в iOnRoad использовали так называемые таблицы преобразований (look-up table, LUT): поскольку все компоненты Y, U и V — 8-битные, то умножения в приведённых выше формулах могут быть вычислены заранее и 32-битные результаты сохранены в пяти таблицах с 256-ю входами.

Трансформация YUV в RGB – общая идея использования вычислений с фиксированной точкой на базе SSE

SSE не имеет векторных инструкций «сборки» (gather) для работы с LUT; использование векторного умножения 16-битных упакованных чисел представляется более быстрым, чем комбинация из скалярных LUT операций и последующего упаковывания. Однако простое 16-битное SSE умножение (PMULLW) не может быть использовано, так как ожидаемые промежуточные результаты могут быть больше, чем 2¹⁶. В SSE есть инструкция PMULHRSW, которая комбинирует полное 16-битное умножение и сдвиг вправо 32-битного промежуточного результата до требуемых 16-ти битов с округлением. Для использования этой инструкции, операнды должны быть предварительно сдвинуты влево, обеспечивая максимальное количество значимых битов в конечном результате (в нашем конкретном случае мы можем получить 13-битный конечный результат).

Встроенные функции (intrinsics) как средство написания ручного SSE кода

Чтобы помочь избежать написания ручного SSE кода с использованием ассемблера, все известные компиляторы C/C++ (MS, GNU, Intel) имеют набор специальных API, называемых встроенными функциями (intrinsic functions).
С точки зрения программиста, встроенная функция выглядит и ведет себя как обычная функция C/C++. На самом деле она представляет из себя обертку одной ассемблерной инструкции SSE и в большинстве случаев компилируется только как эта инструкция. Использование встроенных функций заменяет написание ассемблерного кода со всеми его сложностями при тех же самых показателях производительности.
Например, чтобы вызвать PMULHRSW инструкцию, о которой говорилось выше, в С коде мы использовали встроенную функцию _mm_mulhrs_epi16().
Каждая SSE инструкция имеет соответствующую встроенную функцию, так что необходимый SSE код может быть полностью написан с использованием встроенных функций.

Трансформация YUV в RGB – реализация вычислений с фиксированной точкой на базе SSE

Процесс начинается с загрузки 2-х порций из 16-ти 8-битных Y и 8-ми 8-битных пар (U,V).
В результате эти данные будут сконвертированы в 16 32-битных RGB пикселей (в форме FRGB, когда старший байт имеет значение 0xff).
Число 16 вычитается из 16-ти 8-битных Y с использованием операции 8-битного вычитания с насыщением, таким образом отпадает необходимость в проверке результата на отрицательность.
8 пар (U,V) «обслуживают» 2 строки с 16-ю значениями Y.
Для распаковки входных данных используется операция перестановки (shuffle), при этом получается 2 порции из:

• 2-x наборов из 8-ми 16-битных Y;
• 1-го набора из 4-х 16-битных удвоенных U;
• 1-го набора из 4-х 16-битных удвоенных V.

Ниже показана детальная схема изготовления одной порции.

Перед использованием U и V, из них вычитается 128 с помощью 16-битной инструкции _mm_sub_epi16().
После вычитания, все 8 16-битных значений Y, U и V сдвигаются влево, чтобы оптимально подходить для _mm_mulhrs_epi16(); эта инструкция используется с соответствующим образом упакованными коэффициентами.

Замечание: Эти подготовительные шаги (вычитания и сдвиги), упомянутые выше, используются вместо LUT операций в скалярном алгоритме.

Результаты умножения суммируются для получения окончательных 16-битных значений, ограниченных на отрезке между 0 и 213-1 (8192) с использованием _mm_min_epi16() и _mm_max_epi16().
После завершения всех вычислений, мы получаем результат в виде упакованных раздельно 16-битных значений R, G и B.
Переупаковка их в формат FRGB (где F – альфа-канал, заполненный единицами согласно требованиям iOnRoad) производится за два шага.
На первом шаге мы переупаковываем 16-битные раздельные значения R, G и B в 16-битные FR и GB с использованием дополнительного регистра, заполненного 16-битным <0xff00>. Эта фаза переупаковки производится с помощью логических сдвигов влево и вправо и логических операций ИЛИ/И, как показано на рисунке:

На втором шаге промежуточные результаты FR и GB окончательно пакуются в FRGB с использованием инструкций распаковки _mm_unpacklo_epi16() и _mm_unpackhi_epi16():

Код, описанный выше, реализующий конверсию YUV в RGB с использованием встроенных векторных функций SSE, даёт 4-х кратное ускорение в сравнении с исходным скалярным кодом, использующим предварительно вычисленные таблицы (LUT).

Использование CILK+ для параллелизации: тривиально

Все версии процессоров Atom, используемые в смартфонах и планшетах, имеют два ядра с гипертредингом, а в будущем будут иметь еще больше, поэтому параллелизация алгоритмов для них очень важна.
Простейший подход к параллелизации реализован в расширении CILK+ компилятора Intel ^[3] для языков C и C++ (знаменитый TBB работает только для C++!). Самый простой оператор параллелизации cilk_for (используемый для внешнего цикла конвертации YUV в RGB вместо стандартного for языка C/C++) обеспечивает двукратный прирост производительности на двухядерном процессоре Clover Trail+.
Использование внутренних функций SSE для векторизации совместно с параллелизацией CILK+ дает 8-кратное общее ускорение.

Использование CILK+ для векторизации: Array Notation, function mapping и редукция

CILK+ содержит очень важное расширение, называемое Array Notation, позволяющее существенно повысить эффективность векторизации и в то же время улучшить читаемость кода.
Array Notation обеспечивает масштабируемость платформ: один и тот же код может быть оптимально векторизован и под 128-битный Atom, и под 256-битный Haswell, и под 512-битный MIC/Skylake – в отличие от кода, основанного на внутренних функциях SSE/AVX: его приходится переписывать вручную под каждую конкретную платформу. Array Notation позволяет использовать так называемые секции массива в качестве аргументов функции (function mapping), а также для редукции (суммирование, поиск максимума/минимума и т.д.).

Пример использования CILK+ Array Notation

Посмотрите на два фрагмента кода.
Исходный код со сложными определениями и разверткой (взято из реального приложения):

И однострочную комбинацию с элементами CILK+, состоящую из секции Array Notation, function mapping и редукции:

Эти два варианта полностью идентичны с функциональной точки зрения, но CILK+ версия работает в 6 раз быстрее!

Выводы и призыв к разработчикам

Внутренние функции SSE (уровень SSSE3) значительно улучшают производительность приложений на устройствах Atom/Intel.
Использование CILK+ Array Notation (встроенного в компилятор Интеля) обеспечивает большие возможности для автоматической векторизации.
CILK+ — отличное средство для параллелизации приложений на устройствах Atom/Intel.
Наша рекомендация для Atom/Android разработчиков в новом «андроидном» мире: не стесняйтесь оптимизировать свои мультимедийные приложения и игры с помощью SSE и CILK+ — эти проверенные средства обеспечат вам огромный скачок в производительности!

Автор текста — Григорий Данович, Старший Инженер по Прикладным Решениям, Intel Израиль.

Автор: saul

Источник ^[4]