Статья: Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

может содержать только одну точку слияния - точку входа в начале головного линейного участка;

имеет прямолинейный граф управления. Команды ветвления могут передавать управление в другие суперблоки, но не на команды того же суперблока.

Трасса [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;