Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд
3. Усиление параллелизма в пределах выделенных областей. Поскольку параллельное исполнение инструкций возможно только при условии их независимости по данным, то в пределах областей проводятся реорганизации кода, направленные на частичное снятие зависимостей по данным между инструкциями - переименование регистров, исключение индуктивных переменных в циклах и др. Наиболее эффективны эти реорганизации в применении к телам развернутых циклов. Эти вопросы рассматриваются в разделе 6.3.
4. Планирование команд в пределах выделенных областей. Различают методы локального планирования (в пределах линейных участков) и глобальное планирование (в пределах расширенных областей), где применяется перемещение команд между линейными участками с использованием аппаратных и программных средств для сохранения корректности программы. Планированию команд посвящен раздел 7.
Области планирования
В традиционных компиляторах планирование, как правило, осуществляется в пределах линейных участков [2]. Однако для ILP-процессоров такой подход может приводить к потерям производительности. Характерная частота переходов в программах нечисленных приложений, например, составляет примерно 20%, т.е. средняя длина линейного участка - 5 команд. С учетом связей по данным, которые вероятнее всего присутствуют между этими командами, степень естественного программного параллелизма оказывается невысокой. Для того чтобы привести степень программного параллелизма в соответствие с уровнем имеющегося аппаратного параллелизма, в компиляторах для ILP-процессоров реализуют планирование в рамках более широких областей кода, объединяющих несколько линейных участков, так что инструкции могут в результате перемещаться из одного участка в другие. При этом обычно стремятся максимально ускорить выполнение вдоль наиболее часто исполняемых ветвей программы. Надо заметить, что подавляющая часть из доступных экспериментальных результатов, подтверждающих преимущества глобального планирования по сравнению с локальным, относятся к приложениям нечисленного характера. Эффективность глобального планирования в компиляции численных приложений требует дополнительных исследований.
Для того чтобы перемещения инструкций между линейными участками были корректны, применяются определенные приемы, ограничения и аппаратные средства, которые рассматриваются в разд. 7.3, 7.4. В этом разделе будут рассмотрены типы областей, для которых выработаны эффективные методы планирования, а также способы построения областей.
Введем два понятия, которые используются в определениях областей: точка слияния - команда, на которую управление может прийти более чем из одного места; точка ветвления - команда условной передачи управления.
Область планирования состоит из одного или более линейных участков, которые в исходной программе могут быть расположены последовательно или произвольно. Области различаются по структуре своего потока управления и по способу формирования. Наиболее известные типы областей - суперблоки, трассы, гиперблоки, древовидные области и регионы - имеют два общих признака: ациклический граф управления и один головной участок, из которого достижимы все остальные.
Ниже перечислены типы областей и их основные характеристики:
Суперблок [30], [35]
может содержать только одну точку слияния - точку входа в начале головного линейного участка;
имеет прямолинейный граф управления. Команды ветвления могут передавать управление в другие суперблоки, но не на команды того же суперблока.
Трасса [27], [28], [30] отличается от суперблока тем, что может содержать более одной точки слияния.
Гиперблок [49] - суперблок, который может включать условно исполняемые участки. Метод гиперблоков эффективен для процессоров, поддерживающих условное выполнение.
Древовидная область (treegion) [18], [31], [32], [34], имеет древовидный граф управления и включает не более одной точки слияния (в начале головного участка). Древовидные области могут формироваться путем реорганизации входной программы; при этом также могут использоваться данные профилирования.
Регион [20], [22] - область с произвольным ациклическим графом управления. Отличительная черта метода регионов - поддержка вложенных регионов (например, внутренних циклов). Метод регионов применяется, в частности, в компиляторе для IA-64 [22], где его реализация существенно опирается на аппаратные средства поддержки параллелизма.
Одна из идей, на которой основываются методы глобального планирования, заключается в том, что код можно реорганизовать таким образом, чтобы сократить время выполнения вдоль одних путей за счет замедления вдоль других. Если решения принимаются в пользу ускорения наиболее частых путей, то за счет этого можно достичь сокращения времени выполнения программы в целом. Такой подход может быть неприемлем в приложениях реального времени, где возможны ограничения на время выполнения вдоль любого, даже самого редкого пути исполнения [58].
При формировании областей используются данные профилирования по частоте выполнения переходов, что делает актуальной задачу эффективного получения данных профилирования. В работе [26] предлагается экономный метод профилирования передач управления для ILP-процессоров. Метод не требует аппаратной поддержки и основан на добавлении минимального необходимого числа дополнительных линейных участков, содержащих зондирующий код для регистрации передач управления. Зондирующий код организуется таким образом, чтобы при выполнении обеспечивалось его максимальное распараллеливание.
Рассмотрим более подробно способы формирования двух типов областей - суперблоков и древовидных областей.
Суперблоки
Понятие суперблока соответствует определению расширенного линейного участка. Расширенный линейный участок есть последовательность линейных участков B1 ... Bk, такая что для 1 i < k Bi - единственный предшественник Bi+1. Отличительная черта суперблоков заключается в способах их формирования. С учетом данных профилирования, точки слияния в исходной программе удаляются путем создания копий соответствующих участков. При этом стремятся выделить суперблоки, расположенные вдоль трасс - наиболее часто исполняемых путей на графе управления. Пример формирования суперблока из [35] приведен на рис. 4.
Рис. 4. Формирование суперблоков на основе данных профилирования
На рис. 4а показан граф управления для программного фрагмента, составляющего тело цикла, с указанием частот выполнения участков и переходов между ними. Из этой схемы видно, что наиболее часто выполнение следует вдоль пути A B E F. Поэтому принимается решение сформировать три суперблока: {A,B,E,F}, {C}, {D}. Для этого необходимо исключить точку слияния в F. На рис. 4б показано, как это достигается путем добавления копии F (F'). Этот прием называют "дублированием хвостов" (tail duplication). В конечном счете, из исходного программного фрагмента создается 4 суперблока: {A,B,E,F}, {C}, {D}, {F'}.
Древовидные области
Формирование древовидных областей проводится в два этапа. Сначала на основе статического анализа в графе управления выделяются имеющиеся древовидные участки. Далее, если доступны данные профилирования, выделенные участки искусственно наращивают методом "дублирования хвостов". При этом стремятся объединить участки вдоль наиболее часто исполняемых путей.
Рис. 5. Древовидная область
На рис. 5 приведен пример из [32], где показано наращивание первоначально выделенной области. Исходный программный фрагмент состоит из двух древовидных областей (а). Если исполнение преимущественно следует вдоль A B D E, то желательно реорганизовать код, чтобы путь A B D E попал в общую область, и планировщик мог максимально использовать параллелизм на этом отрезке. На рис. 5b и рис. 5c показаны два этапа такого преобразования. Сначала создается копия D' участка D и формируется область, включающая путь A B D. Затем создается копия E' участка E и формируется область, включающая пути A B D E и A C D' E', а также область, состоящая из одного участка F.
Данные профилирования могут использоваться также на этапе планирования в древовидных областях, для того чтобы обеспечить максимально быстрое выполнение (и исключить задержки) преимущественно вдоль часто исполняемых путей.
Для того чтобы ограничить объем результирующей программы, при принятии решений о "дублировании хвостов", помимо данных профилирования, применяются и другие эвристики (см. [31]):
допустимый общий коэффициент расширения не должен превышать некоторой заранее заданной величины;
число путей исполнения в каждой древовидной области не должно превышать заданной величины;
если число предшественников участка в графе управления больше заданной величины, то дублирование участка не производится.
Аналогичные эвристики используются и при формировании областей других типов.
В [7] можно найти описание метода проникающего планирования (percolation scheduling), предполагающего глобальное переупорядочение кода для выявления параллелизма на уровне тела функции.
Усиление параллелизма в пределах областей планирования
Большинство из рассматриваемых в этом разделе методов применимы в той или иной степени ко всем типам ILP-процессоров и видам областей планирования.
Преобразования циклов
Преобразования циклов, применяемые в ILP-компиляции, подробно рассмотрены в [35] и [58]. К ним относятся: развертка циклов, слияние и разбивка циклов, подгонка циклов, конвейеризация циклов. Все они имеют смысл независимо от наличия параллелизма в целевом процессоре, поскольку позволяют уменьшить общее число проверок завершения цикла и операций перехода. В компиляции для ILPпроцессоров они приобретают дополнительную значимость, поскольку позволяют усилить программный параллелизм в теле цикла.
В примерах, иллюстрирующих смысл преобразований, использован язык Си, реально же они применяются на уровне промежуточного представления.
Развертка цикла (loop unrolling). Суть этого преобразования заключается в том, что тело цикла дублируется n раз, а число повторений соответственно сокращается во столько же раз (рис. 6). Число n называется коэффициентом развертки цикла.
for (i=0;i<100;i++) for (i=0;i<100;i=i+4) {
{a[i]=a[i]+c;} a[i]=a[i]+c;
==> a[i+1]=a[i+1]+c;
a[i+2]=a[i+2]+c;
a[i+3]=a[i+3]+c;}
Рис. 6. Развертка циклов
В контексте ILP-компиляции он приобретает большее значение, поскольку позволяет использовать параллелизм команд, относящихся к разным итерациям цикла. Наиболее эффективно его применение в сочетании с другими преобразованиями, направленными на усиление параллелизма (см. рис. 12).
Слияние циклов (loop fusion). Два расположенных последовательно цикла можно слить, если они имеют одинаковое число итераций и отсутствуют зависимости по данным, препятствующие объединению. Если тела сливаемых циклов не зависят друг от друга (рис. 7), появляется возможность спланировать параллельное выполнение команд, относящихся к разным циклам.
for (i=0;i<100;i++) for (i=0;i<100;i++) {
b[i]=b[i]+c; ==> b[i]=b[i]+c;
for (j=0;j<100;j++) a[i]=a[i]*2;
a[j]=a[j]*2; }
Рис. 7. Слияние циклов
Если граничные значения переменных двух циклов различаются, но ненамного, то применяют слияние с предварительной подгонкой одного из циклов.
Подгонка цикла (loop peeling). Подгонка цикла заключается в изменении граничных значений переменной цикла. Обычно подгонка применяется для того чтобы можно было выполнить слияние (рис. 8) или развертку цикла (если число итераций не кратно коэффициенту развертки).
for (i=0;i<100;i++) for (i=0;i<100;i++) {
b[i]=b[i+2]+c; ==> b[i]=b[i+2]+c;
for (j=0;j<102;j++) a[i]=a[i]*2;}
a[j]=a[j]*2; a[100]=a[100]*2;
a[101]=a[101]*2;
Рис. 8. Слияние циклов с подгонкой одного из них
Программная конвейеризация цикла (software pipelining). Идея конвейеризации цикла заключается в том, что выполнение команд, относящихся к последующим итерациям, начинается раньше, чем завершается выполнение предшествующих итераций. Конвейеризация применима в тех случаях, когда тело цикла можно разбить на группы команд, не зависящих друг от друга на разных итерациях.
На рис. 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 представлены примеры зависимостей всех типов и показано, как образуются антизависимости.
Зависимости по данным препятствуют параллельному исполнению