Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд (стр. 4 из 9)
На рис. 9 показан пример конвейеризации цикла. Команды, относящиеся к одной итерации исходного цикла, не могут выполняться параллельно в силу зависимостей по данным. Тело результирующего цикла составлено из команд, относящихся к трем смежным итерациям (i, i+1, i+2) и не зависящих друг от друга, так что их выполнение может быть спланировано параллельно. Число итераций, участвующих в конвейерном выполнении цикла, называется глубиной конвейеризацией (по аналогии с аппаратной конвейеризацией). Число итераций конвейеризованного цикла сокращается на n-1, где n - глубина конвейеризации, а в пролог и эпилог выносятся команды, относящиеся к начальным и завершающим итерациям исходного цикла.
a[0]=b[0]+2;
a[1]=b[1]+2;
d[0]=a[0]/n;
for (i=0;i<100;i++){ for (i=0;i<98;i++){
a[i]=b[i]+2; f[i]=d[i]+a[i];
d[i]=a[i]/n; ==> d[i+1]=a[i+1]/n;
f[i]=d[i]+a[i];} a[a+2]=b[i+2]+2;}
d[99]=a[99]/n;
f[98]=d[98]+a[98];
f[99]=d[99]+a[99]];
Рис. 9. Конвейеризация цикла
Конвейеризация, как и развертывание цикла, создает возможности для параллельного выполнения команд из разных итераций, но обладает тем преимуществом, что не увеличивает размер тела цикла.
Обзор методов конвейеризации циклов можно найти в работах [7], [12].
Разбивка циклов (loop distribution). В некоторых случаях может иметь смысл преобразование, обратное слиянию и называемое разбивкой циклов. Это целесообразно, например, если тело цикла слишком длинное, и имеющееся число регистров недостаточно для размещения всех используемых в теле цикла переменных. В этом случае часть промежуточных значений приходится временно выгружать в память, а перед использованием в вычислениях загружать на регистры (в англоязычной литературе этот процесс обозначают термином register spilling). Благодаря разбивке цикла можно избежать дефицита регистров и выталкивания значений в память.
В примере, показанном на рис. 10, вторая команда не может быть выполнена параллельно с первой в силу зависимости по данным. В результате разбивки создаются циклы с более короткими телами и меньшим числом зависимостей по данным.
for (i=0;i<100;i++){ for (i=0;i<100;i++)
b[i]=b[i-1]+c; ==> b[i]=b[i-1]+c;
a[i]=b[i]+2;} for (i=0;i<100;i++)
a[i]=b[i]+2;
Рис. 10. Разбивка циклов
Встраивание функций
Встраивание функций широко применяется как метод оптимизации и в традиционных технологиях компиляции, поскольку при этом экономится время, затрачиваемое на передачу параметров, выполнение пролога и эпилога. В контексте ILP-компиляции этот подход имеет дополнительное преимущество, поскольку он позволяет спрямлять пути исполнения, создавая более длинные линейные участки и дополнительные возможности для распараллеливания кода.
Снятие зависимостей по данным
Алгоритмы планирования команд, используемые практически во всех компиляторах (см. разделы 7.1 и 8), работают с тремя видами зависимостей (или связей) по данным между командами (см., например, [58] или [45]). Здесь будут рассмотрены только зависимости по обращениям к регистрам; о зависимостях по обращениям к памяти см. разд. 7.6.
Пусть имеется некоторая последовательность команд c1, ..., cn, подлежащих планированию. Планировщик может изменять порядок выполнения команд, не нарушая их частичной упорядоченности, которая определяется перечисленными далее зависимостями по данным. (При глобальном планировании планировщик также должен учитывать связи по управлению, препятствующие перемещению команд через точки ветвления; подробнее об этом см. разделы 7.3, 7.4).
1. Связи типа "чтение после записи". Команда cj зависит от ci, если ci записывает значение в некоторый регистр r, а cj читает это значение. Будем обозначать это отношение как ci
cj.Зависимости этого типа называются истинными, поскольку они отражают объективные связи по данным между операциями, реализующими компилируемую программу: выполнение cj должно планироваться позже, чем выполнение ci. Как правило, избавиться от них нельзя, однако существуют приемы, позволяющие сделать это в некоторых специальных случаях: дублирование переменной суммирования и индуктивных переменных, рассматриваемые далее в этом разделе.
2. Связи типа "запись после записи". Команда cj зависит от ci, если
обе команды записывают значения в некоторый регистр r
j > i
имеется хотя бы одна команда сk, которая читает значение r, записанное командой ci.
Будем обозначать это отношение как ci
cj. Выполнение команды cj должно быть запланировано позже чем ci, если имеет место ci cj.3. Связи типа "запись после чтения". Команда cj зависит от ci, если существует команда ck, такая что имеет место ck
ci и ck cj. Будем обозначать это отношение ci 
cj. Смысл этой зависимости в том, что ci читает некоторый регистр r, записанный ранее командой ck, а cj (j > i) записывает в r другое значение. Если имеет место ci cj, то cj может быть выполнена не раньше ci (т.е. одновременно или позднее ci).Последние два типа связей называют антизависимостями или ложными зависимостями, поскольку они возникают в результате того, что компилятор использует одни и те же регистры для хранения разных значений (или программист использует одни и те же рабочие переменные для хранения различных промежуточных значений).
Рис. 11. Зависимости по данным (a) до распределения регистров, (b) после распределения регистров. После распределения регистров появляются антизависимости WAR (R3=R1+R2,R1=R4-R5) по R1 и WAW(R3=R1+R2,R3=R0-R7) по R3
На рис. 11 представлены примеры зависимостей всех типов и показано, как образуются антизависимости.
Зависимости по данным препятствуют параллельному исполнению команд и их переупорядочению при планировании. В случае, показанном на рис. 11а), возможно параллельное выполнение команд (1,2,4) или (3,4). После распределения регистров (рис. 11б), антизависимости жестко определят порядок выполнения команд – 1), 2), 3), 4). Поэтому важно по возможности избавляться от них. Большинство из перечисленных далее преобразований направлено на снятие антизависимостей по данным внутри областей планирования.
Миграция команд. Если результат команды не используется в данной области, то ее можно переместить в области, которые выполняются реже. Для суперблоков этот метод применяется следующим образом [35]. Если результат операции не используется в суперблоке S, то она может быть удалена из S, при этом ее копии создаются во всех суперблоках, на которые управление может быть передано из S. При этом исключаются суперблоки, в которых результат заведомо не используется. Решение принимается с учетом оценок частот выполнения суперблоков. В результате в S исключаются все зависимости по данным, связанные с этой операцией.
Переименование регистров. Суть этого приема заключается в том, чтобы размещать разные значения в разных регистрах. Разумеется, его практическое применение ограничено числом доступных регистров.
Дублирование индуктивной переменной. Индуктивные переменные это переменные, представляющие собой выражения, линейно зависящие от переменной цикла, например, адресные выражения для доступа к элементам массива. В развернутом цикле при вычислении индуктивных переменных возникают зависимости по данным. В результате оказывается невозможным распараллеливание вычисления индуктивных переменных и доступа к памяти по ним. Положение можно исправить, если завести несколько экземпляров индуктивной переменной (в соответствии с коэффициентом развертки цикла).
Дублирование переменной суммирования. Если в цикле производится суммирование или перемножение выражений, то при развертке цикла можно создать несколько экземпляров переменной суммирования для накопления частичных сумм или произведений [35]. В эпилоге цикла частичные суммы или произведения, соответственно, складываются или перемножаются. Этот прием применим к любой операции, обладающей свойствами коммутативности и ассоциативности.
На рис. 12 показано применение развертки цикла в сочетании с оптимизациями снятия зависимостей - переименованием регистров, дублированием переменной суммирования и индуктивной переменной. Код, полученный непосредственно после развертки, слабо поддается распараллеливанию из-за большого числа зависимостей по данным. В результате снятия зависимостей получается тело цикла, выполнение которого на идеальном процессоре (с неограниченными возможностями параллельного исполнения, без задержек) занимает 2 такта.
Исходный цикл:
s=0;
for (i=0;i<100;i++)
{s=s+a[i];}
Ассемблерный код
r1 = A
r3 = 0
L1: r2 = MEM(r1)
r3 = r3 + r2
r1 = r1 + 4
blt (r1 A+4N) L1
Результат развертки с коэффициентом 3:
r1 = A
r3 = 0
L1: r2 = MEM(r1)
r3 = r2 + r3
r1 = r1 + 4
r2 = MEM(r1)
r3 = r2 + r3
r1 = r1 + 4
r2 = MEM(r1)
r3 = r2 + r3
r1 = r1 + 4
blt (r1 A+4N) L1
Результат снятия зависимостей по данным:
r11 = A ;; Размножение индуктивной
r21 = A + 4 ;; переменной
r31 = A + 8
r3 = 0 ;; Размножение переменной
r23 = 0 ;; суммирования
r33 = 0
L1: r2 = MEM(r11)
r3 = r2 + r3
r11 = r11 + 12
r22 = MEM(r21) ;; Переименование r2 -> r22
r23 = r22 + r23
r21 = r21 + 12
r32 = MEM(r31) ;; Переименование r2 -> r22
r33 = r32 + r33
r31 = r31 + 12
blt (r1 A+4N) L1
r3 = r3 + r23 ;; Сложение частичных сумм
r3 = r3 + r33
Рис. 12. Развертка цикла и снятие зависимостей по данным
Соотношение программного и аппаратного параллелизма
Рассмотренные выше методы оптимизации направлены на усиление программного параллелизма на уровне команд, с тем чтобы максимально использовать имеющиеся в процессоре средства параллельного исполнения. Важный момент, который необходимо учитывать при их практической реализации, - соотношение между фактическим уровнем аппаратного параллелизма целевого процессора и уровнем программного параллелизма. Набор оптимизаций и их параметры (такие как коэффициент развертки) следует соразмерять с аппаратными характеристиками, в первую очередь, с реальными возможностями параллельного исполнения команд и количеством доступных регистров. Например, дублирование переменной суммирования может не иметь смысла, если процессор не способен выполнять одновременно несколько сложений. Развертка цикла может привести к деградации производительности, если регистров недостаточно для размещения всех переменных увеличившегося тела цикла. В этом случае компилятор вынужден размещать переменные в памяти, и использовать дополнительные команды для загрузки их на регистры перед выполнением операций и выгрузки в память при изменении значений, что может свести на нет эффект усиления параллелизма (см. [19], [38]).