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