Компилятор векторизации преобразует такие циклы в последовательности векторных операций. Эти векторные операции выполняют сложение по длине - четыре (в нашем примере) блока элементов из массивов a, bи c. Автоматическая векторизация - важная тема исследований в области информатики.
Содержание
- 1 Предпосылки
- 2 Гарантии
- 2.1 Зависимости данных
- 2.2 Точность данных
- 3 Теория
- 3.1 Построение графа зависимостей
- 3.2 Кластеризация
- 3.3 Определение идиом
- 4 Общая структура
- 5 Время выполнения vs. время компиляции
- 6 Методы
- 6.1 Автоматическая векторизация на уровне цикла
- 6.2 Автоматическая векторизация на уровне базового блока
- 6.3 При наличии потока управления
- 6.4 Сокращение накладных расходов на векторизацию при наличии потока управления
- 7 Ручная векторизация
- 8 См. Также
- 9 Ссылки
Предпосылки
Ранние компьютеры обычно имели один логический блок, который выполнял одну инструкцию на одной паре операнды за раз. Компьютерные языки и программы поэтому были разработаны для последовательного выполнения. Однако современные компьютеры могут делать много вещей одновременно. Таким образом, многие оптимизирующие компиляторы выполняют автоматическую векторизацию, когда части последовательных программ преобразуются в параллельные операции.
Векторизация цикла преобразует процедурные циклы путем назначения блока обработки каждой паре операндов. Программы проводят большую часть своего времени в таких циклах. Поэтому векторизация может значительно ускорить их, особенно для больших наборов данных. Циклическая векторизация реализована в Intel MMX, SSE и AVX в Power ISA. AltiVec и в наборах инструкций ARM NEON.
Многие ограничения предотвращают или затрудняют векторизацию. Иногда векторизация может замедлить выполнение, например, из-за синхронизации конвейера или синхронизации перемещения данных. Анализ зависимости от цикла определяет циклы, которые могут быть векторизованы, основываясь на зависимости данных инструкций внутри циклов.
Гарантирует
Автоматическая векторизация, как и любая оптимизация цикла или другая оптимизация времени компиляции, должна точно сохранять поведение программы.
Зависимости данных
Во избежание получения неверных результатов во время выполнения должны соблюдаться все зависимости.
В общем случае инвариантные зависимости цикла и лексически прямые зависимости можно легко векторизовать, а лексически обратные зависимости можно преобразовать в лексически прямые зависимости. Однако эти преобразования должны выполняться безопасно, чтобы гарантировать, что зависимость между всеми операторами останется верной исходной.
Циклические зависимости должны обрабатываться независимо от векторизованных инструкций.
Точность данных
Целое точность (размер в битах) должна сохраняться во время выполнения векторной инструкции. Правильная векторная инструкция должна быть выбрана на основе размера и поведения внутренних целых чисел. Кроме того, при использовании смешанных целочисленных типов необходимо проявлять особую осторожность, чтобы правильно повысить / понизить их уровень без потери точности. Особое внимание следует уделять расширению знака (поскольку несколько целых чисел упакованы в одном регистре) и во время операций сдвига или операций с переносом битов, которые в противном случае были бы приняты во внимание.
Точность с плавающей запятой также должна быть сохранена, если не отключено соответствие IEEE-754. В этом случае операции будут выполняться быстрее, но результаты могут незначительно отличаться. Большие вариации, даже игнорирование IEEE-754, обычно означают ошибку программиста.
Теория
Чтобы векторизовать программу, оптимизатор компилятора должен сначала понять зависимости между операторами и при необходимости заново выровнять их. После отображения зависимостей оптимизатор должен должным образом упорядочить инструкции реализации, заменив подходящих кандидатов на векторные инструкции, которые работают с несколькими элементами данных.
Построение графа зависимостей
Первым шагом является построение графа зависимостей, определение того, какие операторы зависят от других операторов. Это включает в себя изучение каждого оператора и идентификацию каждого элемента данных, к которому он обращается, отображение модификаторов доступа к массиву с функциями и проверку зависимости каждого доступа от всех остальных во всех операторах. Анализ псевдонимов может использоваться для подтверждения того, что разные переменные обращаются (или пересекаются) к одной и той же области памяти.
Граф зависимостей содержит все локальные зависимости с расстоянием, не превышающим размер вектора. Итак, если векторный регистр имеет размер 128 бит, а тип массива - 32 бита, размер вектора составляет 128/32 = 4. Все другие нециклические зависимости не должны аннулировать векторизацию, поскольку не будет никакого одновременного доступа в та же векторная инструкция.
Предположим, что размер вектора такой же, как 4 int:
for (i = 0; i < 128; i++) { a[i] = a[i-16]; // 16>4, можно игнорировать a [i] = a [i-1]; // 1 < 4, stays on dependency graph }Кластеризация
Используя график, оптимизатор затем может сгруппировать сильно связанные компоненты (SCC) и отделить векторизуемые операторы от остальных.
Например, рассмотрим фрагмент программы, содержащий три группы операторов внутри цикла: (SCC1 + SCC2), SCC3 и SCC4, в том порядке, в котором может быть векторизована только вторая группа (SCC3). Окончательная программа будет тогда содержать три цикла, по одному для каждого группа, с векторизацией только средней. Оптимизатор не может соединить первую с последней без нарушения порядка выполнения оператора, что приведет к аннулированию необходимых гарантий.
Обнаружение идиом
Некоторые неочевидные зависимости могут быть дополнительно оптимизированы на основе определенных идиом.
Например, следующие зависимости собственных данных могут быть векторизованы, поскольку значения правых значений (RHS ) равны f выгравированы, а затем сохранены в левом значении, поэтому данные не могут измениться в назначении.
a [i] = a [i] + a [i + 1];
Самозависимость с помощью скаляров может быть векторизована с помощью исключения переменных.
Общая структура
Общая структура векторизации цикла разделена на четыре этапа:
- Прелюдия : где Независимые от цикла переменные готовы к использованию внутри цикла. Обычно это включает перемещение их в векторные регистры с определенными шаблонами, которые будут использоваться в векторных инструкциях. Это также место для вставки проверки зависимости во время выполнения. Если проверка решает, что векторизация невозможна, перейдите к Очистка .
- Цикл (ы) : все векторизованные (или нет) циклы, разделенные кластерами SCC в порядке появления в исходном коде.
- Postlude : вернуть все независимые от цикла переменные, индукции и сокращения.
- Cleanup : реализовать простые (не векторизованные) циклы для итераций в конце цикла, которые не кратны размеру вектора или для случаев, когда проверки во время выполнения запрещают обработку векторов.
Сравнение времени выполнения и времени компиляции
Некоторые векторизации не могут быть полностью проверены во время компиляции. Например, библиотечные функции могут обойти оптимизацию, если обрабатываемые ими данные предоставляются вызывающей стороной. Даже в этих случаях оптимизация времени выполнения позволяет векторизовать циклы на лету.
Эта проверка во время выполнения выполняется на этапе prelude и направляет поток на векторизованные инструкции, если это возможно, в противном случае возвращается к стандартной обработке, в зависимости от переменных, которые передаются в регистры или скалярные переменные.
Следующий код можно легко векторизовать во время компиляции, поскольку он не зависит от внешних параметров. Кроме того, язык гарантирует, что ни одна из них не будет занимать ту же область памяти, что и любая другая переменная, поскольку они являются локальными переменными и живут только в стеке выполнения stack.
int a [128]; int b [128]; // инициализируем b для (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, которые можно использовать в дальнейшем компилятор продвигается вперед и / или посредством ручного изменения кода.
Методы
Примером может быть программа для умножения двух векторов числовых данных. Скалярный подход будет выглядеть примерно так:
для ( 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] и векторный процессор может выполнять fo ur операции для одной векторной инструкции. Поскольку четыре векторные операции выполняются примерно за то же время, что и одна скалярная инструкция, векторный подход может работать до четырех раз быстрее, чем исходный код.
Существует два различных подхода к компиляции: один основан на традиционной методике векторизации, а другой основан на развертывании цикла.
Автоматическая векторизация на уровне цикла
Этот метод, используемый для обычных векторных машин, пытается найти и использовать параллелизм SIMD на уровне цикла. Он состоит из двух следующих основных этапов.
- Найдите самый внутренний цикл, который можно векторизовать.
- Преобразуйте цикл и сгенерируйте векторные коды
На первом этапе компилятор ищет препятствия, которые могут предотвратить векторизацию. Основным препятствием для векторизации является истинная зависимость данных короче длины вектора. Другие препятствия включают вызовы функций и короткие итерации.
Как только цикл определен как векторизуемый, цикл разделяется длиной вектора, и каждая скалярная инструкция в теле цикла заменяется соответствующей векторной инструкцией. Ниже на примере выше показаны преобразования компонентов для этого шага.
for (i = 0; i < 1024; i+=4) for (ii = 0; ii < 4; ii++) C[i+ii] = A[i+ii]*B[i+ii];
- После распределения цикла с использованием временных массивов
for (i = 0; i < 1024; i+=4) { for (ii = 0; ii < 4; ii++) tA[ii] = A[i+ii]; for (ii = 0; ii < 4; ii++) tB[ii] = B[i+ii]; for (ii = 0; ii < 4; ii++) tC[ii] = tA[ii]*tB[ii]; for (ii = 0; ii < 4; ii++) C[i+ii] = tC[ii]; }- После замены кодами векторов
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 параллелизм внутри базовых блоков, а не циклов. Два основных шага заключаются в следующем.
- Самый внутренний цикл разворачивается с коэффициентом длины вектора для формирования большого тела цикла.
- Изоморфные скалярные инструкции (которые выполняют та же операция) упаковываются в векторную инструкцию, если зависимости не препятствуют этому.
Чтобы показать пошаговые преобразования для этого подхода, снова используется тот же пример.
- После развертывания цикла (по вектору length, в данном случае предполагается равным 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 в теле цикла требует выполнение инструкций во всех путях управления для объединения нескольких значений переменной.Один общий подход состоит в том, чтобы пройти последовательность преобразований кода: предикация → векторизация (с использованием одного из вышеуказанных методов) → удаление векторных предикатов → удаление скалярных предикатов. Если следующий код используется в качестве примера для демонстрации этих преобразований:
для (i = 0; i < 1024; i++) if (A[i]>0) C [i] = B [i]; иначе D [i] = D [i-1 ];
для (i = 0; i < 1024; i++) { P = A[i]>0; NP =! P; C [i] = B [i]; (P) D [i] = D [i-1 ]; (NP)}где (P) обозначает предикат, охраняющий оператор.
для (i = 0; i < 1024; i+=4) { vP = A[i:i+3]>(0,0,0,0); vNP = vec_not (vP); С [я: я + 3] = В [я: я + 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)}- После удаления векторных предикатов
для (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; если (NP4) D [i + 3] = D [i + 2]; если (NP3) D [i + 2] = D [i + 1]; если (NP2) D [i + 1] = D [i]; если (NP1) D [i] = D [i-1];}Снижение накладных расходов на векторизацию при наличии потока управления
Необходимость выполнять инструкции на всех путях управления в векторном коде была одним из основных факторов, замедляющих векторный код по отношению к скалярной базовой линии. Чем сложнее становится поток управления и чем больше инструкций пропускается в скалярном коде, тем больше становятся накладные расходы на векторизацию. Чтобы уменьшить эти накладные расходы на векторизацию, можно вставлять ветви вектора для обхода вектора инструкции, подобные тому, как скалярные ветви обходят скалярные инструкции. Ниже предикаты AltiVec используются, чтобы показать, как этого можно достичь.
- Скалярная базовая линия (исходный код)
для (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 имеет ложные значения во всех полях.
Рассмотрим пример, где всегда берется внешняя ветвь в скалярной базовой линии, минуя большинство инструкции в теле цикла. Промежуточный случай выше, без векторных ветвей, выполняет все векторные инструкции. Конечный код с векторными ветвями выполняет как сравнение, так и ветвление в векторном режиме, pote Значительное повышение производительности по сравнению со скалярной базовой линией.
Ручная векторизация
В большинстве компиляторов C и C ++ можно использовать встроенные функции для векторизации вручную, за счет усилий программиста и ремонтопригодности.
См. Также
Ссылки
