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

Информацию о векторизации как идиоме программирования см. в разделе «Программирование массивов» . Сведения об автоматическом преобразовании растровой графики в векторную см. в разделе Автоматическая трассировка изображений .

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

${\begin{aligned}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{aligned}}$

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

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

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

Предыстория

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

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

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

Гарантии

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

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

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

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

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

данных

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

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

Теория

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

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

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

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

Предположим, что размер вектора равен 4 целым числам:

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];

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

Общая структура

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

• Прелюдия : где независимые от цикла переменные подготовлены к использованию внутри цикла. Обычно это предполагает перемещение их в векторные регистры с определенными шаблонами, которые будут использоваться в векторных инструкциях. Здесь также можно вставить проверку зависимости во время выполнения. Если проверка решит, что векторизация невозможна, перейдите к Cleanup .
• Циклы : все векторизованные (или нет) циклы, разделенные кластерами 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-параллелизм на уровне цикла. Он состоит из следующих двух основных этапов.

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

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

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

• После вскрытия

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 внутри базовых блоков, а не циклов. Два основных шага заключаются в следующем.

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

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

• После развертывания цикла (по длине вектора, в данном случае принятой равной 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. который использует оба.

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

Наличие операторов 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++ можно использовать встроенные функции для векторизации вручную за счет усилий программиста и удобства сопровождения.

См. также

• Цепочка (векторная обработка)
• Векторный процессор