Автоматическая векторизация в параллельных вычислениях — это особый случай автоматической распараллеливания , когда компьютерная программа преобразуется из скалярной реализации, которая обрабатывает одну пару операндов за раз, в векторную реализацию, которая обрабатывает одну операцию над несколькими парами операндов одновременно. Например, современные обычные компьютеры, включая специализированные суперкомпьютеры , обычно имеют векторные операции , которые одновременно выполняют такие операции, как следующие четыре сложения (через оборудование SIMD или SPMD ):
Однако в большинстве языков программирования обычно пишутся циклы, которые последовательно выполняют сложение многих чисел. Вот пример такого цикла, написанного на языке C :
для ( i = 0 ; i < n ; i ++ ) c [ i ] = a [ i ] + b [ i ]; Векторизующий компилятор преобразует такие циклы в последовательности векторных операций. Эти векторные операции выполняют сложения блоков элементов из массивов a, bи c. Автоматическая векторизация является важной темой исследований в области компьютерных наук. [ необходима цитата ]
Ранние компьютеры обычно имели одно логическое устройство, которое выполняло одну инструкцию на одной паре операндов за раз. Поэтому компьютерные языки и программы были разработаны для последовательного выполнения. Современные компьютеры, однако, могут делать много вещей одновременно. Поэтому многие оптимизирующие компиляторы выполняют автоматическую векторизацию, где части последовательных программ преобразуются в параллельные операции.
Векторизация циклов преобразует процедурные циклы, назначая процессорный блок каждой паре операндов. Программы проводят большую часть своего времени в таких циклах. Поэтому векторизация может значительно ускорить их, особенно при больших наборах данных. Векторизация циклов реализована в MMX , SSE и AVX от Intel , в AltiVec от Power ISA , в NEON , SVE и SVE2 от ARM и в наборах инструкций Vector Extension от RISC-V .
Многие ограничения мешают векторизации или затрудняют ее. Иногда векторизация может замедлить выполнение, например, из-за синхронизации конвейера или синхронизации перемещения данных. Анализ зависимости циклов выявляет циклы, которые можно векторизовать, опираясь на зависимость данных инструкций внутри циклов.
Автоматическая векторизация, как и любая оптимизация цикла или другая оптимизация времени компиляции, должна в точности сохранять поведение программы.
Во время выполнения необходимо учитывать все зависимости, чтобы предотвратить получение неверных результатов.
В общем случае, циклически инвариантные зависимости и лексически прямые зависимости можно легко векторизовать, а лексически обратные зависимости можно преобразовать в лексически прямые зависимости. Однако эти преобразования должны выполняться безопасно, чтобы гарантировать, что зависимость между всеми утверждениями останется верной оригиналу.
Циклические зависимости должны обрабатываться независимо от векторизованных инструкций.
Целочисленная точность (размер бита) должна быть сохранена во время выполнения векторной инструкции. Правильная векторная инструкция должна быть выбрана на основе размера и поведения внутренних целых чисел. Кроме того, в случае смешанных целочисленных типов необходимо проявлять особую осторожность, чтобы правильно повышать/понижать их без потери точности. Особое внимание следует уделять расширению знака (поскольку несколько целых чисел упакованы в один и тот же регистр) и во время операций сдвига или операций с битами переноса , которые в противном случае были бы приняты во внимание.
Точность с плавающей точкой также должна быть сохранена, если только не отключено соответствие IEEE-754 , в этом случае операции будут быстрее, но результаты могут немного отличаться. Большие изменения, даже игнорируя IEEE-754, обычно указывают на ошибку программиста.
Чтобы векторизовать программу, оптимизатор компилятора должен сначала понять зависимости между операторами и перестроить их, если необходимо. После того, как зависимости отображены, оптимизатор должен правильно организовать инструкции по реализации, изменив соответствующих кандидатов на векторные инструкции, которые работают с несколькими элементами данных.
Первый шаг — построить граф зависимостей , определяющий, какие операторы зависят от каких других операторов. Это включает в себя проверку каждого оператора и идентификацию каждого элемента данных, к которому оператор обращается, сопоставление модификаторов доступа массива с функциями и проверку каждой зависимости доступа от всех остальных во всех операторах. Анализ псевдонимов может использоваться для подтверждения того, что различные переменные обращаются к одной и той же области памяти (или пересекают ее).
Граф зависимостей содержит все локальные зависимости с расстоянием не больше размера вектора. Таким образом, если векторный регистр имеет размер 128 бит, а тип массива — 32 бита, размер вектора составляет 128/32 = 4. Все остальные нециклические зависимости не должны делать векторизацию недействительной, поскольку не будет никакого параллельного доступа в одной и той же векторной инструкции.
Предположим, что размер вектора равен 4 целым числам:
for ( i = 0 ; i < 128 ; i ++ ) { a [ i ] = a [ i -16 ]; // 16 > 4, можно смело игнорировать a [ i ] = a [ i -1 ]; // 1 < 4, остается на графике зависимостей } Используя граф, оптимизатор может затем кластеризовать сильно связанные компоненты (SCC) и отделить векторизуемые операторы от остальных.
Например, рассмотрим фрагмент программы, содержащий три группы операторов внутри цикла: (SCC1+SCC2), SCC3 и SCC4, в том порядке, в котором только вторая группа (SCC3) может быть векторизована. Окончательная программа будет тогда содержать три цикла, по одному для каждой группы, и только средний из них будет векторизован. Оптимизатор не может объединить первый с последним, не нарушив порядок выполнения операторов, что сделает недействительными необходимые гарантии.
Некоторые неочевидные зависимости можно дополнительно оптимизировать на основе определенных идиом.
Например, следующие зависимости от внутренних данных могут быть векторизованы, поскольку значения правых значений ( RHS ) извлекаются и затем сохраняются в левом значении, поэтому данные не могут измениться в ходе назначения.
а [ я ] = а [ я ] + а [ я + 1 ]; Самостоятельность скаляров может быть векторизована путем исключения переменных .
Общая структура векторизации циклов делится на четыре этапа:
Некоторые векторизации не могут быть полностью проверены во время компиляции. Например, библиотечные функции могут победить оптимизацию, если данные, которые они обрабатывают, предоставлены вызывающей стороной. Даже в этих случаях оптимизация во время выполнения может векторизовать циклы на лету.
Эта проверка во время выполнения выполняется на этапе прелюдии и направляет поток к векторизованным инструкциям, если это возможно, в противном случае возвращается к стандартной обработке, в зависимости от переменных, которые передаются в регистрах или скалярных переменных.
Следующий код можно легко векторизовать во время компиляции, так как он не зависит от внешних параметров. Кроме того, язык гарантирует, что ни одна из них не будет занимать ту же область памяти, что и любая другая переменная, так как они являются локальными переменными и существуют только в стеке выполнения .
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) достаточно, чтобы определить, перекрываются ли массивы или нет, тем самым выявляя любые зависимости. (Обратите внимание, что начиная с C99 указание параметров с помощью ключевого слова restrict — здесь: ) — сообщает компилятору, что диапазоны памяти, на которые указывают a и b, не перекрываются, что приводит к тому же результату, что и в примере выше.)int *restrict a, int *restrict b
Существуют некоторые инструменты для динамического анализа существующих приложений с целью оценки скрытого потенциала параллелизма SIMD, который можно использовать посредством дальнейших усовершенствований компилятора и/или посредством ручного изменения кода. [1]
Примером может служить программа для умножения двух векторов числовых данных. Скалярный подход будет выглядеть примерно так:
для ( i = 0 ; i < 1024 ; i ++ ) c [ i ] = a [ i ] * b [ i ]; Это можно векторизовать так, чтобы выглядело примерно так:
для ( 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 на уровне цикла. Она состоит из двух основных шагов, как указано ниже.
На первом этапе компилятор ищет препятствия, которые могут помешать векторизации. Главным препятствием для векторизации является истинная зависимость данных, которая короче длины вектора. Другие препятствия включают вызовы функций и короткие счетчики итераций.
После того, как цикл определен как векторизуемый, цикл очищается по длине вектора, и каждая скалярная инструкция в теле цикла заменяется соответствующей векторной инструкцией. Ниже показаны преобразования компонентов для этого шага с использованием приведенного выше примера.
для ( i = 0 ; i < 1024 ; i += 4 ) для ( j = 0 ; j < 4 ; j ++ ) c [ i + j ] = a [ i + j ] * b [ i + j ]; для ( i = 0 ; i < 1024 ; i += 4 ) { для ( j = 0 ; j < 4 ; j ++ ) tA [ j ] = A [ i + j ]; для ( j = 0 ; j < 4 ; j ++ ) tB [ j ] = B [ i + j ]; для ( j = 0 ; j < 4 ; j ++ ) tC [ j ] = tA [ j ] * tB [ j ]; для ( j = 0 ; j < 4 ; j ++ ) C [ i + j ] = tC [ j ]; } для ( 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 с короткими длинами векторов. [2] Хотя циклы могут быть развернуты для увеличения количества параллелизма SIMD в базовых блоках, этот метод использует параллелизм SIMD в базовых блоках, а не в циклах. Два основных шага следующие.
Чтобы продемонстрировать пошаговые преобразования при этом подходе, снова используется тот же пример.
для ( 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 ]); } для ( 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 ]); } для ( 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 [3] [ устаревший источник ] , который использует оба подхода.
Наличие операторов if в теле цикла требует выполнения инструкций во всех путях управления для объединения нескольких значений переменной. Один из общих подходов заключается в прохождении последовательности преобразований кода: предикация → векторизация (с использованием одного из вышеперечисленных методов) → удаление векторных предикатов → удаление скалярных предикатов. [4] Если следующий код используется в качестве примера для демонстрации этих преобразований;
для ( i = 0 ; i < 1024 ; i ++ ) если ( 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 ); 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 ) } для ( 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 ) } для ( 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 ]; } Необходимость выполнения инструкций во всех путях управления в векторном коде была одним из основных факторов, замедляющих векторный код по отношению к скалярной базовой линии. Чем сложнее становится поток управления и чем больше инструкций обходят в скалярном коде, тем больше становятся накладные расходы векторизации. Чтобы уменьшить эти накладные расходы векторизации, векторные ветви могут быть вставлены для обхода векторных инструкций аналогично тому, как скалярные ветви обходят скалярные инструкции. [5] Ниже предикаты AltiVec используются для демонстрации того, как этого можно достичь.
для ( i = 0 ; i < 1024 ; i ++ ) { если ( A [ i ] > 0 ) { C [ i ] = B [ i ]; если ( B [ i ] < 0 ) D [ i ] = E [ i ]; } } для ( 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 ); } для ( i = 0 ; i < 1024 ; i += 4 ) { если ( 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 ); если ( 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++ можно использовать встроенные функции для ручной векторизации, но это снижает усилия программиста и упрощает поддержку.