В современных компиляторах задача векторизации циклов является очень важной и нужной. В большинстве своем, при успешной векторизации производительность приложения может быть существенно увеличена. Способов добиться этого достаточно много, а тонкостей, связанных именно с получением ожидаемого «ускорения» нашего приложения – ещё больше.

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

Когда мы оперируем с элементами массивов (и не только с ними), то на самом деле постоянно работаем с кэш-линиями размером по 64 байта. SSE и AVX векторы всегда попадают в одну кэш линию, если они выравнены по 16 и 32 байта, соответственно. А вот если наши данные не выравнены, то, очень вероятно, нам придётся подгружать ещё одну «дополнительную» кэш-линию. Процесс этот достаточно сильно сказывается на производительности, а если мы при этом и к элементам массива, а значит, и к памяти, обращаемся непоследовательно, то всё может быть ещё хуже.
Кроме этого, ещё и сами инструкции могут быть с выравненным или невыравненным доступом к данным. Если в инструкции мы видим буковку u (unaligned), то скорее всего это инструкция невыравненного чтения и записи, например vmovupd. Стоит отметить, что начиная с архитектуры Nehalem скорость работы этих инструкций стала сопоставима с выравненными, при условии выравненности данных. На более старых версиях то не так.

Компилятор может нам активно помогать в борьбе за производительность. Например, он может попытаться разбить 128 битный невыравненный load на два 64 битных, что будет лучше, но всё же медленно. Ещё одно хорошее решение, которое компилятор умеет реализовывать – это генерировать разные версии для выравненного и невыравненного случаев. В рантайме происходит определение, какие же у нас данные имеются, и выполнение идёт по нужной версии. Проблема только в одном – накладные расходы на подобные проверки могут быть слишком велики, и компилятор откажется от этой идеи. Ещё лучше если компилятор сможет сам выравнять для нас данные. Кстати, если при векторизации данные не выравнены или компилятор ничего не знает о выравненности, исходный цикл разбивается на три части:

• некоторое количество итераций (всегда меньше длины вектора) до основного «ядра» (peel loop), которые компилятор может использовать для выравнивания начального адреса. Отключить peeling можно с помощью опции mP2OPT_vec_alignment=6.
• основное тело — «ядро» — цикла (kernel loop), для которого генерируются выравненные векторные инструкции
• «хвост» (remainder loop), который остаётся из-за того, что количество итераций не делится на длину вектора; он может быть тоже векторизован, но не так эффективно как основной цикл. Если мы хотим отключить векторизацию remainder цикла, то используем директиву #pragma vector novecremainder в С/С++ или !DIR$ vector noremainder в Фортране.

Таким образом, может быть достигнута выравненность начального адреса, за счет потери в скорости — нам придётся «перетаптываться» до основного ядра цикла, выполняя какое-то количество итераций. Но этого можно избегать, выравнивая данные и говоря компилятору об этом.

Разработчикам нужно взять за правило выравнивать данные «как надо»: 16 байт для SSE, 32 для AVX и 64 для MIC & AVX-512. Как это можно делать?

Для выделения выравненной памяти на С/С++ в куче используется функция:

void* _mm_malloc(int size, int base)

В Linux есть функция:

int posix_memaligned(void **p, size_t base, size_t size)

Для переменных на стэке используется атрибут __declspec:

__declspec(align(base)) <var>

Или специфичная для Linux:

<var> __attribute__((aligned(base)))

Проблема в том, что __declspec неведом для gcc, так что возможна проблема с портируемостью, поэтому стоит использовать препроцессор:

#ifdef __GNUC__
#define _ALIGN(N)  __attribute__((aligned(N)))
#else
#define _ALIGN(N)  __declspec(align(N))
#endif

_ALIGN(16) int foo[4];  

Интересно, что в компиляторе Фортрана от Intel (версии 13.0 и выше) имеется специальная опция -align, с помощью который можно сделать данные выравненными (при объявлении). Например, через -align array32byte мы скажем компилятору, чтобы все массивы были выравнены по 32 байта. Есть и директива:

 !DIR$ ATTRIBUTES ALIGN: base :: variable

Теперь про сами инструкции. При работе с невыравненными данными инструкции невыравненного чтения и записи очень медленные, за исключением векторных SSE операций на SandyBridge и новее. Там они по скорости могут не уступать инструкциям с выравненным доступом при соблюдении ряда условий. Невыравненные векторные инструкции AVX для работы с невыравненными данными медленнее аналогичных для работы с выравненными, даже на последних поколениях процессоров.

При этом компилятор предпочитает генерировать невыравненные инструкции для AVX, потому что в случае выравненных данных они будут работать так же быстро, а если данные окажутся не выравнены – то будет более медленное выполнение, но оно будет. Если же сгенерируются выравненные инструкции, а данные окажутся не выравнены – то всё упадёт.

Подсказывать компилятору какой набор инструкций использовать можно через директиву pragma vector unaligned/aligned.

Например, рассмотрим этот код:

void mult(double* a, double* b, double* c)
{
  int i;
#pragma vector unaligned
  for (i = 0; i < N; i++)
    c[i] = a[i] * b[i];
}

Для него при использовании AVX инструкций мы получи следующий ассемблерный код:

..B2.2:
  vmovupd   (%rdi,%rax,8), %xmm0
  vmovupd   (%rsi,%rax,8), %xmm1
  vinsertf128 $1, 16(%rsi,%rax,8), %ymm1, %ymm3
  vinsertf128 $1, 16(%rdi,%rax,8), %ymm0, %ymm2
  vmulpd    %ymm3, %ymm2, %ymm4
  vmovupd   %xmm4, (%rdx,%rax,8)
  vextractf128 $1, %ymm4, 16(%rdx,%rax,8)
  addq      $4, %rax
  cmpq      $1000000, %rax
  jb        ..B2.2

Стоит отметить, что в этом случае не будет того самого peel loop'а, потому что мы использовали директиву.
Если мы заменим unaligned на aligned, дав тем самым гарантии компилятору, что данные выравнены и безопасно генерировать соответствующие выравненные инструкции, мы получим следующее:

..B2.2:
  vmovupd   (%rdi,%rax,8), %ymm0
  vmulpd    (%rsi,%rax,8), %ymm0, %ymm1
  vmovntpd  %ymm1, (%rdx,%rax,8)
  addq      $4, %rax
  cmpq      $1000000, %rax
  jb        ..B2.2

Последний случай будет работать быстрее при условии выравненных a, b и с. Если же нет – всё будет плохо. В первом случае мы получаем чуть более медленную реализацию при условии выравненных данных за счет того, что у компилятора не было возможности использовать vmovntpd, и появилась дополнительная инструкция vextractf128.

Ещё один важный момент – это понятие выравненности начального адреса и относительного выравнивания. Рассмотрим следующий пример:

void matvec(double a[][COLWIDTH], double b[], double c[])
{
  int i, j;
  for(i = 0; i < size1; i++) {
    b[i] = 0;
#pragma vector aligned
    for(j = 0; j < size2; j++)
      b[i] += a[i][j] * c[j];
  }
}

Вопрос здесь только один – заработает ли данный код при условии, что a, b и с выравнены по 16 байт, и мы собираем наш код c использованием SSE? Ответ зависит от значения COLWIDTH. В случае нечетной длины (длина регистров SSE / размер double = 2, значит COLWIDTH должно делиться на 2), наше приложение закончит своё выполнение намного раньше ожидаемого (после прохода по первой строке массива). Причина в том, что первый элемент данных во второй строчке оказывается невыравненным. Для таких случаев необходимо добавлять фиктивные элементы («дырки») в конец каждой строки, чтобы новая строка оказалась выравненной, делая так называемый padding. В данном случае мы можем это сделать с помощью COLWIDTH, в зависимости от набора векторных инструкций и типа данных, которые мы будем использовать. Как уже говорилось, для SSE это должно быть четное число, а для AVX — делиться на 4.
Если мы знаем, что только начальный адрес выравнен, можно дать эту информацию компилятору через атрибут:

__assume_aligned(<array>, base)

Аналог для Фортрана:

!DIR$ ASSUME_ALIGNED address1:base [, address2:base] ...

Я немного поигрался с простым примером перемножения матриц на Haswell, чтобы сравнить скорость работы приложения с AVX инструкциями на Windows в зависимости от директив в коде:

  for (j = 0;j < size2; j++) {
    b[i] += a[i][j] * x[j];

Выравнивал данные по 32 байта:

_declspec(align(32)) FTYPE a[ROW][COLWIDTH];
_declspec(align(32)) FTYPE b[ROW];
_declspec(align(32)) FTYPE x[COLWIDTH];

Примерчик идёт вместе с сэмплами к компилятору от Intel, весь код можно посмотреть там. Так вот, если мы используем директиву pragma vetor aligned перед циклом, то время выполнения цикла составляло 2.531 секунды. При её отсутствии, оно увеличилось до 3.466 и появился peel цикл. Вероятно, про выравненные данные компилятор не узнал. Отключив его генерацию с помощью mP2OPT_vec_alignment=6, цикл выполнялся почти 4 секунды. Интересно, что «обмануть» компилятор оказалось весьма не просто в таком примере, потому что он упорно генерировал рантайм проверку данных и делал несколько вариантов цикла, в результате чего скорость работы с невыравненными данными была незначительно хуже.

В сухом остатке нужно сказать, что выравнивая данные вы почти всегда избавитесь от потенциальных проблем, в частности, с производительностью. Но выравнять данные само по себе не достаточно — необходимо информировать компилятор о том, что известно вам, и тогда можно получить на выходе наиболее эффективное приложение. Главное — не забывать о маленьких хитростях!