"Обычно хакер пишет программы не ради выгоды,
а ради собственного удовольствия. Такая программа
может оказаться полезной, а может остаться
всего лишь игрой интеллекта."
Генри С. Уоррен. Алгоритмические трюки для программистов [1]
Сегодня мы продолжим наши заметки об Эльбрусе. Первую статью, посвященную запуску и оптимизации системы распознавания паспорта, можно прочитать тут.
Однажды мы с коллегами заинтересовались, как самые простые методы оптимизации работают на Эльбрусе.
Процессор Эльбрус имеет 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.
