Оптимизация кода для платформы Эльбрус на простых примерах

в 7:17, , рубрики: c++, ELBRUS, sparc, Алгоритмы, Блог компании Smart Engines Ltd., МЦСТ, обработка изображений, оптимизация кода, Программирование, распознавание, распознавание изображений, распознавание паспорта, Эльбрус

"Обычно хакер пишет программы не ради выгоды,
а ради собственного удовольствия. Такая программа
может оказаться полезной, а может остаться
всего лишь игрой интеллекта."
Генри С. Уоррен. Алгоритмические трюки для программистов [1]

Сегодня мы продолжим наши заметки об Эльбрусе. Первую статью, посвященную запуску и оптимизации системы распознавания паспорта, можно прочитать тут.

image

Однажды мы с коллегами заинтересовались, как самые простые методы оптимизации работают на Эльбрусе.

Процессор Эльбрус имеет VLIW (Very Long Instruction Word) архитектуру — то есть оперирует “широкими” командными словами. Это означает, что компилятор lcc анализирует исходный код программы при компиляции, определяет зависимости между командами и формирует широкие командные слова. В одном таком слове можно уместить до 23 действий, которые будут исполняться одновременно. Если использовать SIMD (Single Instruction Multiple Data), то это число может возрасти до 33 и более операций. Команды в широком слове исполняются параллельно, обеспечивая загрузку всех 6 арифметико-логических устройств на каждом процессоре. Распараллеливание и загрузка всех вычислителей целиком ложится на плечи оптимизирующего компилятора, что позволяет значительно упростить аппаратуру для анализа и исполнения команд и снизить энергопотребление до 45 Вт для Эльбрус-4С [2, 3].

Мы в Smart Engines задались вопросом, как будут работать все привычные оптимизации, такие как, например, развертывание циклов, на столь непривычной платформе с “умным” компилятором.

Мы рассмотрели простые примеры на С++ и сравнили результаты работы на Эльбрус-4С и Intel Core i7-6700K. На Эльбрусе использовался компилятор lcc версии 1.20.17, для Core i7 — Microsoft Visual Studio Community 2015. Для lcc мы использовали флаги компиляции -O3 и -ffast-math.

Для начала, приведем характеристики Эльбрус-4С и Intel Core i7-6700K:

Эльбрус-4С Intel Core i7-6700K
Архитектура Эльбрус Skylake-S
Частота, GHz 0.8 4
Число ядер 4 4 (8 c Hyper-Threading)
Технологический процесс 65 nm 14 nm
Cache L1 size, data 64 Kb 32 Kb
Cache L1 size, instructions 128 Kb 32 Kb
Cache L2 size 8 Mb 1 Mb
Cache L3 size - 8 Mb
Тип оперативной памяти DDR3-1600 DDR4-2133
Потребляемая мощность, Вт 45 91

Тактовая частота этих процессоров значительно отличается: 800 МГц у Эльбрус-4С и 4 ГГц у Intel Core i7. Также заметим, что Эльбрус имеет другую структуру кэш-памяти: отсутствует L3 кэш, однако размер L2 кэша составляет 8 Mb (по 2 Mb на ядро), в то время как у рассмотренного Core­ i7 1 Mb (по 0.25 Mb на ядро). L1 кэш на Эльбрусе также больше, особенно кэш инструкций (128 Kb против 32 Kb).

Пример 1. Развертывание циклов

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

Теперь рассмотрим пример:

#define N 64000
unsigned int x = 0;
unsigned int a[N];
for (int i = 0; i < N; ++i)
  a[i] = i;
//Оптимизируемый цикл
for (int k = 0; k < N;)
{
  x += a[k];
  a[k++] = k;
}

Последний цикл мы и попробовали развернуть. Результаты замеров времени приведены в таблице 1. Стоит отметить, что на Эльбрусе использовался 32-битный режим адресации (флаг компилятора -mptr32). Мы также рассчитали время работы на 1 ГГц путем умножения измеренного времени на тактовую частоту процессора в ГГц. Полученная таким образом безразмерная величина позволяет сравнить производительность Эльбрус и Core i7 с учетом различия в тактовой частоте.

Таблица 1. Время работы в зависимости от N — числа развернутых итераций.

Эльбрус-4С Эльбрус-4С Intel Core i7 Intel Core i7
N Время, мс Время в пересчете на 1 ГГц Время, мс Время в пересчете на 1 ГГц
1 400 320 255 1020
2 200 160 116 464
4 100 80 54 216
8 50 40 25 100
16 26 21 20 80
32 15 12 7 28
64 8 6 5 20

Можно видеть, что развертывание циклов работает как на современном Core i7, так и на Эльбрус-4С. В случае совсем простого цикла, который мы рассмотрели, Эльбрус-4С работает значительно эффективнее Core i7 с учетом отношения частот.

Пример 2. Обработка данных различной длины

В этом примере мы обрабатываем массив по 1, 4 или 8 байтам. Исходный массив а был выровнен на 8 байт.

#define MASK1  0xF1
#define MASK4 0xF1F2F3F4
#define MASK8 0xF1F2F3F4F5F6F7F8

for (k = 0; k < n; ++k)
{
  а[k] &= MASK1;
}

Результаты замеров времени приведены в таблице 2.

Таблица 2. Время работы в зависимости от N — числа обрабатываемых байт.

Эльбрус-4С Эльбрус-4С Intel Core i7 Intel Core i7
N Время, мс Время в пересчете на 1 ГГц Время, мс Время в пересчете на 1 ГГц
1 2400 1920 811 3244
4 600 480 201 804
8 300 240 102 408

Можно видеть, что обработка по 4 и 8 байт работает быстрее как на современном Core i7, так и на Эльбрус-4С, причем времена уменьшаются кратно числу обрабатываемых байт. Кроме того, Эльбрус работает эффективнее Core i7 с учетом отношения частот.

Пример 3. Использование SIMD

В этом примере мы решили протестировать интринсики и рассмотрели вычисление скалярного произведения чисел типа float при n = 12800.
Неоптимизированный цикл:

float result = 0.0;
for (int i = 0; i < n; ++i)
{
  result += x[i] * y[i];
}

С использованием SSE:

float *pX = x;
float *pY = y;
__m128 Sum = _mm_setzero_ps();
int num = n / 4;
for (int i = 0; i < num; ++i, pX += 4, pY += 4)
{
  Sum = _mm_add_ps(Sum, _mm_mul_ps(_mm_load_ps(pX), _mm_load_ps(pY)));
}
float result = _mm_extract_ps(Sum, 0) + _mm_extract_ps(Sum, 1) + _mm_extract_ps(Sum, 2) + _mm_extract_ps(Sum, 3);

С использованием EML [4] (оптимизированная библиотека под Эльбрус):

double result;
eml_Vector_DotProd_32F(x, y, n, &result);

Результаты замеров времени приведены в таблице 3. Размер SIMD-регистра на Эльбрус-4С составляет 64 бита (instruction set версии 3), что в общем-то соответствует наблюдаемому ускорению в 2 раза между версией без оптимизаций и версией с SIMD. На Core i7 все тоже довольно правдоподобно, мы оперировали 128-битными регистрами, в которые помещается 4 числа типа float. Кроме того, заметно, что Эльбрус без интринсиков работает эффективнее Core i7 с учетом частоты, а вот с интринсиками времена работы практически совпадают.

Таблица 3. Время работы подсчета скалярного произведения.

Эльбрус-4С Эльбрус-4С Intel Core i7 Intel Core i7
Время, мс Время в пересчете на 1 ГГц Время, мс Время в пересчете на 1 ГГц
Без оптимизации 263 210 99 396
С SIMD 110 88 24 96

Пример 4. Подсчет расстояния Хэмминга между двумя массивами

Здесь мы вычисляли расстояние Хэмминга между двоичным представлением двух массивов, т.е. взяли расстояния Хэмминга между двоичными представлениями соответствующих чисел в массивах и нашли их сумму. Для массивов с 8-битными данными мы использовали побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ и предподсчитанную таблицу расстояний:

int result = 0;
for (int i = 0; i < n; ++i)
{
  result += popcnt_table[x[i] ^ y[i]];
}

Для 32- и 64-битных данных мы использовали побитовое логическое ИСКЛЮЧАЮЩЕЕ ИЛИ и интринсики _mm_popcnt_u32, _mm_popcnt_u64 на Intel и интринсики __builtin_e2k_popcnts, __builtin_e2k_popcntd на Эльбрусе. Общая длина массивов x и y в байтах оставалась неизменной и равной n = 512. Результаты замеров времени приведены в таблице 4.

Таблица 4. Время подсчета расстояния Хэмминга в зависимости от числа обрабатываемых байт N.

Эльбрус-4С Эльбрус-4С Intel Core i7 Intel Core i7
N Время, мс Время в пересчете на 1 ГГц Время, мс Время в пересчете на 1 ГГц
1 630 504 155 620
4 110 88 47 188
8 76 61 15 60

В этом примере мы видим, что интринсики для подсчета числа единиц в 64-битном и 32-битном регистрах и на Эльбрусе, и на Core i7 дают значительное ускорение относительно версии с предподсчитанной таблицей. Кроме того, 32-битная команда popcnt на Эльбрусе работает быстрее, чем на Core i7 с учетом отношения частот. А вот в 64-битной случае времена работы на Core i7 и Эльбрусе сравнялись.

Пример 5. Устранение зависимости по данным

Данный пример позаимствован из книги Криса Касперски “Техника оптимизации программ. Эффективное использование памяти” [5]. Он демонстрирует, как устранение зависимости по данным помогает повысить производительность. Массив a заполнен нулями, n = 2097152.
Пример с зависимостью по данным:

int x = 0;
for (size_t a = 0; a < BLOCK_SIZE; a += 8 * sizeof(int))
{
        x = *(int *)((char *)p1 + a + 0 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 1 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 2 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 3 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 4 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 5 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 6 * sizeof(int));
        a += x;
        x = *(int *)((char *)p1 + a + 7 * sizeof(int));
        a += x;
}

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

int x = 0;
for (size_t a = 0; a < BLOCK_SIZE; a += 8 * sizeof(int))
{
        x += *(int *)((char *)p2 + a + 0 * sizeof(int));
        x += *(int *)((char *)p2 + a + 1 * sizeof(int));
        x += *(int *)((char *)p2 + a + 2 * sizeof(int));
        x += *(int *)((char *)p2 + a + 3 * sizeof(int));
        x += *(int *)((char *)p2 + a + 4 * sizeof(int));
        x += *(int *)((char *)p2 + a + 5 * sizeof(int));
        x += *(int *)((char *)p2 + a + 6 * sizeof(int));
        x += *(int *)((char *)p2 + a + 7 * sizeof(int));
}

Результаты замеров времени приведены в таблице 5. Устранение зависимости по данным работает как на Эльбрусе, так и на Core i7, причем на Core i7 время работы различается примерно в 11 раз, а на Эльбрусе — практически в 20! Код с зависимостью по данным отработал на Эльбрусе медленнее, чем на Core i7 в пересчете на 1 ГГц, а вот без зависимости Эльбрус всего в 4 раза медленнее Core i7 (при различии частот в 5 раз). Такие результаты на Эльбрусе можно объяснить наличием механизма асинхронной подкачки массивов (array prefetch buffer), которая работает эффективно, если подкачиваемые элементы располагаются последовательно.

Таблица 5. Время чтения зависимых и независимых данных.

Эльбрус-4С Эльбрус-4С Intel Core i7 Intel Core i7
Время, мс Время в пересчете на 1 ГГц Время, мс Время в пересчете на 1 ГГц
Зависимые данные 605 484 87 348
Независимые данные 32 26 8 32

Пример 6. Многопоточные вычисления

Разумеется, мы не могли не рассмотреть такой метод оптимизации, как распараллеливание. Для чистоты эксперимента мы взяли полностью независимые задачи (вычисление скалярного произведения двух массивов типа double). В таблице 6 приведено время последовательной работы N задач (Tпосл), время работы N задач в N потоков (Tпар) и ускорение E:

Таблица 6. Время последовательного и параллельного вычисления скалярного произведения в зависимости от числа задач и потоков N.

Эльбрус-4С Эльбрус-4С Эльбрус-4С Intel Core i7 Intel Core i7 Intel Core i7
N Tпосл, мс Tпар, мс E=Tпосл/Tпар Tпосл, мс Tпар, мс E=Tпосл/Tпар
2 2628 1316 2.00 1033 500 2.07
4 5259 1318 3.99 1994 500 3.99
8 10513 2634 3.99 3987 503 7.93
16 21045 5268 4.00 7980 1009 7.91
20 26321 6583 4.00 9967 1263 7.89
32 42053 10535 3.99 15948 2014 7.92
40 52566 13170 3.99 19936 2528 7.89

Видно, что на Core i7 ускорение практически в 8 раз достигается на 8 потоках и дальше варьируется незначительно. На Эльбрусе ускорение в 4 раза достигается на 4 потоках и также с увеличением числа потоков не меняется. Соотношение по скорости между Эльбрус и Core i7 оказалось равным примерно 2.6, в то время как отношение частот равно 5.

Выводы

Привычные методы ускорения вычислений вполне работают на Эльбрусе и в этом плане программирование для него не требует специфических знаний и умений. В рассмотренных элементарных примерах для оптимизации кода Эльбрус показал себя просто замечательно с учетом тактовой частоты в 800 МГц и в два раза меньшей потребляемой мощности по сравнению с Core i7.

P.S. А еще мы запустили нашу систему распознавания паспорта на SPARC! Это означает, что теперь мы сможем писать статьи о распознавании на еще одной вычислительной архитектуре.

Использованные источники

[1] Генри С. Уоррен, мл. Алгоритмические трюки для программистов. М.: Издательский дом "Вильямс", 2014. ISBN 978-5-8459-1838-3 – 512 С.
[2] http://www.elbrus.ru/arhitektura_elbrus.
[3] http://www.mcst.ru/mikroprocessor-elbrus4s.
[4] http://www.mcst.ru/vysokoproizvoditelnye_biblioteki.
[5] Крис Касперски. “Технологии оптимизации программ. Эффективное использование памяти”. Спб.: БХВ-Петербург, 2003. ISBN 5-94157-232-8 – 464 С.

Автор: Smart Engines Ltd.

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js