Автоматическая векторизация - Automatic vectorization

Автоматическая векторизация при параллельных вычислениях является частным случаем автоматического распараллеливания , когда компьютерная программа преобразуется из скалярной реализации, обрабатывающей одну пару операндов за раз, в векторную реализацию, которая обрабатывает одну операцию над несколькими парами операндов. операнды сразу. Например, современные обычные компьютеры, включая специализированные суперкомпьютеры , обычно имеют векторные операции, которые одновременно выполняют такие операции, как следующие четыре добавления (через оборудование SIMD или SPMD ):

{\ displaystyle {\ begin {align} c_ {1} & = a_ {1} + b_ {1} \\ c_ {2} & = a_ {2} + b_ {2} \\ c_ {3} & = a_ {3} + b_ {3} \\ c_ {4} & = a_ {4} + b_ {4} \ end {align}}}

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

for (i = 0; i < n; i++)
    c[i] = a[i] + b[i];

Компилятор векторизации преобразует такие циклы в последовательности векторных операций. Эти векторные операции выполняют сложение блоков элементов из массивов a, bи c. Автоматическая векторизация - одна из основных тем исследований в области компьютерных наук.

Фон

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

Векторизация цикла преобразует процедурные циклы, назначая блок обработки каждой паре операндов. Программы проводят большую часть своего времени в таких циклах. Следовательно, векторизация может значительно ускорить их, особенно для больших наборов данных. Петля векторизации реализован в Intel 's MMX , SSE и AVX , в мощности ISA ' s AltiVec , и в ARM «s NEON , SVE наборы инструкций и SVE2.

Многие ограничения предотвращают или затрудняют векторизацию. Иногда векторизация может замедлить выполнение, например, из-за конвейерной синхронизации или времени перемещения данных. Анализ зависимости от цикла определяет циклы, которые можно векторизовать, полагаясь на зависимость инструкций внутри циклов от данных.

Гарантии

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

Зависимости данных

Во время выполнения необходимо соблюдать все зависимости, чтобы предотвратить получение неверных результатов.

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

Циклические зависимости должны обрабатываться независимо от векторизованных инструкций.

Точность данных

Целочисленная точность (битовый размер) должна сохраняться во время выполнения векторной инструкции. Правильная векторная инструкция должна быть выбрана на основе размера и поведения внутренних целых чисел. Кроме того, при использовании смешанных целочисленных типов необходимо проявлять особую осторожность, чтобы правильно повысить / понизить их уровень без потери точности. Особое внимание следует уделять расширению знака (поскольку несколько целых чисел упакованы внутри одного регистра) и во время операций сдвига или операций с битами переноса , которые в противном случае были бы приняты во внимание.

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

Теория

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

Построение графа зависимостей

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

Граф зависимостей содержит все локальные зависимости с расстоянием не больше размера вектора. Итак, если векторный регистр имеет размер 128 бит, а тип массива - 32 бита, размер вектора составляет 128/32 = 4. Все другие нециклические зависимости не должны аннулировать векторизацию, поскольку не будет никакого параллельного доступа в та же векторная инструкция.

Предположим, что размер вектора такой же, как 4 int:

for (i = 0; i < 128; i++) {
    a[i] = a[i-16]; // 16 > 4, safe to ignore
    a[i] = a[i-1]; // 1 < 4, stays on dependency graph
}

Кластеризация

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

Например, рассмотрим фрагмент программы, содержащий три группы операторов внутри цикла: (SCC1 + SCC2), SCC3 и SCC4 в том порядке, в котором может быть векторизована только вторая группа (SCC3). Окончательная программа будет содержать три цикла, по одному для каждой группы, с векторизацией только средней. Оптимизатор не может соединить первое с последним без нарушения порядка выполнения операторов, что приведет к аннулированию необходимых гарантий.

Обнаружение идиом

Некоторые неочевидные зависимости могут быть дополнительно оптимизированы на основе определенных идиом.

Например, следующие собственные зависимости данных могут быть векторизованы, потому что значение правых значений ( RHS ) выбирается и затем сохраняется в левом значении, поэтому данные не могут измениться в рамках назначения.

a[i] = a[i] + a[i+1];

Самозависимость от скаляров может быть векторизована путем исключения переменных .

Общие рамки

Общая схема векторизации циклов делится на четыре этапа:

Прелюдия : где независимые от цикла переменные подготовлены для использования внутри цикла. Обычно это включает перемещение их в векторные регистры с определенными шаблонами, которые будут использоваться в векторных инструкциях. Это также место для вставки проверки зависимости во время выполнения. Если проверка решает, что векторизация невозможна, перейдите к Очистке .
Цикл (ы) : все векторизованные (или нет) циклы, разделенные кластерами SCC в порядке появления в исходном коде.
Постлюдия : вернуть все независимые от цикла переменные, индукции и редукции.
Очистка : Реализуйте простые (не векторизованные) циклы для итераций в конце цикла, которые не кратны размеру вектора, или когда проверки во время выполнения запрещают обработку векторов.

Время выполнения и время компиляции

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

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

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

int a[128];
int b[128];
// initialize b

for (i = 0; i<128; i++)
    a[i] = b[i] + 5;

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

void compute(int *a, int *b)
{
    int i;
    for (i = 0; i < 128; i++, a++, b++)
        *a = *b + 5;
}

Быстрая проверка во время выполнения адреса как a, так и b , а также пространства итераций цикла (128) достаточно, чтобы определить, перекрываются ли массивы или нет, тем самым выявляя любые зависимости.

Существуют некоторые инструменты для динамического анализа существующих приложений для оценки скрытого потенциала SIMD-параллелизма, которые можно использовать при дальнейших усовершенствованиях компилятора и / или посредством ручного изменения кода.

Методы

Примером может служить программа для умножения двух векторов числовых данных. Скалярный подход будет примерно таким:

for (i = 0; i < 1024; i++)
    c[i] = a[i] * b[i];

Его можно векторизовать, чтобы он выглядел примерно так:

for (i = 0; i < 1024; i += 4)
    c[i:i+3] = a[i:i+3] * b[i:i+3];

Здесь c [i: i + 3] представляет четыре элемента массива от c [i] до c [i + 3], и векторный процессор может выполнять четыре операции для одной векторной инструкции. Поскольку четыре векторные операции выполняются примерно за то же время, что и одна скалярная инструкция, векторный подход может работать до четырех раз быстрее, чем исходный код.

Существует два различных подхода к компиляции: один основан на традиционной технике векторизации, а другой - на развертывании цикла .

Автоматическая векторизация на уровне петель

Этот метод, используемый для обычных векторных машин, пытается найти и использовать параллелизм SIMD на уровне цикла. Он состоит из двух следующих основных этапов.

Найдите самый внутренний цикл, который можно векторизовать
Преобразуйте цикл и сгенерируйте векторные коды

На первом этапе компилятор ищет препятствия, которые могут помешать векторизации. Основное препятствие для векторизации - истинная зависимость данных короче длины вектора. К другим препятствиям относятся вызовы функций и короткое количество итераций.

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

После стрипмайнинга

for (i = 0; i < 1024; i += 4)
    for (j = 0; j < 4; j++)
        c[i+j] = a[i+j] * b[i+j];

Распределение после цикла с использованием временных массивов

for (i = 0; i < 1024; i += 4)
{
    for (j = 0; j < 4; j++) tA[j] = A[i+j];
    for (j = 0; j < 4; j++) tB[j] = B[i+j];
    for (j = 0; j < 4; j++) tC[j] = tA[j] * tB[j];
    for (j = 0; j < 4; j++) C[i+j] = tC[j];
}

После замены на векторные коды

for (i = 0; i < 1024; i += 4)
{
    vA = vec_ld(&A[i]);
    vB = vec_ld(&B[i]);
    vC = vec_mul(vA, vB);
    vec_st(vC, &C[i]);
}

Автоматическая векторизация на уровне базового блока

Этот относительно новый метод специально предназначен для современных архитектур SIMD с короткими длинами векторов. Хотя циклы могут быть развернуты для увеличения степени параллелизма SIMD в базовых блоках, этот метод использует параллелизм SIMD в базовых блоках, а не в циклах. Два основных шага заключаются в следующем.

Самый внутренний цикл разворачивается с коэффициентом длины вектора, чтобы сформировать большое тело цикла.
Изоморфные скалярные инструкции (которые выполняют одну и ту же операцию) упаковываются в векторную инструкцию, если зависимости не препятствуют этому.

Чтобы показать пошаговые преобразования для этого подхода, мы снова используем тот же пример.

После разворачивания цикла (по длине вектора, в данном случае принимается равной 4)

for (i = 0; i < 1024; i += 4)
{
    sA0 = ld(&A[i+0]);
    sB0 = ld(&B[i+0]);
    sC0 = sA0 * sB0;
    st(sC0, &C[i+0]);
          ...
    sA3 = ld(&A[i+3]);
    sB3 = ld(&B[i+3]);
    sC3 = sA3 * sB3;
    st(sC3, &C[i+3]);
}

После упаковки

for (i = 0; i < 1024; i += 4)
{
    (sA0, sA1, sA2, sA3) = ld(&A[i+0:i+3]);
    (sB0, sB1, sB2, sB3) = ld(&B[i+0:i+3]);
    (sC0, sC1, sC2, sC3) = (sA0, sA1, sA2, sA3) * (sB0, sB1, sB2, sB3);
    st((sC0, sC1, sC2, sC3), &C[i+0:i+3]);
}

После генерации кода

for (i = 0; i < 1024; i += 4)
{
    vA = vec_ld(&A[i]);
    vB = vec_ld(&B[i]);
    vC = vec_mul(vA, vB);
    vec_st(vC, &C[i]);
}

Здесь sA1, sB1, ... представляют скалярные переменные, а vA, vB и vC представляют векторные переменные.

Большинство коммерческих компиляторов с автоматической векторизацией используют традиционный подход на уровне цикла, за исключением IBM XL Compiler, который использует оба.

При наличии потока управления

Наличие операторов if в теле цикла требует выполнения инструкций на всех путях управления для объединения нескольких значений переменной. Один из общих подходов - выполнить последовательность преобразований кода: предикация → векторизация (с использованием одного из вышеперечисленных методов) → удаление векторных предикатов → удаление скалярных предикатов. Если следующий код используется в качестве примера для демонстрации этих преобразований;

for (i = 0; i < 1024; i++)
    if (A[i] > 0)
        C[i] = B[i];
    else
        D[i] = D[i-1];

После предиката

for (i = 0; i < 1024; i++)
{
    P = A[i] > 0;
    NP = !P;
    C[i] = B[i];     (P)
    D[i] = D[i-1];   (NP)
}

где (P) обозначает предикат, охраняющий утверждение.

После векторизации

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = B[i:i+3];     (vP)
    (NP1, NP2, NP3, NP4) = vNP;
    D[i+3] = D[i+2];         (NP4)
    D[i+2] = D[i+1];         (NP3)
    D[i+1] = D[i];           (NP2)
    D[i]   = D[i-1];         (NP1)
}

После удаления векторных предикатов

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);
    (NP1, NP2, NP3, NP4) = vNP;
    D[i+3] = D[i+2];         (NP4)
    D[i+2] = D[i+1];         (NP3)
    D[i+1] = D[i];           (NP2)
    D[i]   = D[i-1];         (NP1)
}

После удаления скалярных предикатов

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);
    (NP1, NP2, NP3, NP4) = vNP;
    if (NP4) D[i+3] = D[i+2];
    if (NP3) D[i+2] = D[i+1];
    if (NP2) D[i+1] = D[i];
    if (NP1) D[i]   = D[i-1];
}

Снижение накладных расходов на векторизацию при наличии потока управления

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

Скалярная базовая линия (исходный код)

for (i = 0; i < 1024; i++)
{
    if (A[i] > 0)
    {
        C[i] = B[i];
        if (B[i] < 0)
            D[i] = E[i];
    }
}

После векторизации при наличии потока управления

for (i = 0; i < 1024; i += 4)
{
    vPA = A[i:i+3] > (0, 0, 0, 0);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);
    vT = B[i:i+3] < (0,0,0,0);
    vPB = vec_sel((0, 0, 0, 0), vT, vPA);
    D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);
}

После вставки векторных ветвей

for (i = 0; i < 1024; i += 4)
{
    if (vec_any_gt(A[i:i+3], (0, 0, 0, 0)))
    {
        vPA = A[i:i+3] > (0,0,0,0);
        C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);
        vT = B[i:i+3] < (0, 0, 0, 0);
        vPB = vec_sel((0, 0, 0, 0), vT, vPA);
        if (vec_any_ne(vPB, (0, 0, 0, 0)))
            D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);
    }
}

В окончательном коде с векторными ветвями следует отметить две вещи; Во-первых, инструкция определения предиката для vPA также включается в тело ветви внешнего вектора с помощью vec_any_gt. Во-вторых, прибыльность внутренней векторной ветви для vPB зависит от условной вероятности того, что vPB будет иметь ложные значения во всех полях, если vPA имеет ложные значения во всех полях.

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

Ручная векторизация

В большинстве компиляторов C и C ++ можно использовать встроенные функции для векторизации вручную за счет усилий программиста и удобства обслуживания.

Languages

In other projects