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

Шумаков С.М.

Введение

Процессоры, способные одновременно и независимо выполнять несколько команд, обладают исключительно высоким потенциалом производительности и находят все более широкое применение. О процессорах такого типа говорят, что они поддерживают параллелизм на уровне команд (Instruction Level Parallelism, ILP). Далее для краткости они будут называться ILP-процессорами. Класс ILP-процессоров включает суперскалярные процессоры и процессоры с очень длинным командным словом (Very Large Instruction Word, VLIW), к числу которых относятся, в частности, многие модели цифровых процессоров обработки сигналов (ЦПОС).

Важное преимущество ILP по сравнению с параллелизмом многопроцессорных архитектур заключается в том, что программный параллелизм на уровне команд извлекается (аппаратурой или компилятором) автоматически, без дополнительных усилий со стороны прикладных программистов, в то время как использование параллелизма многопроцессорных архитектур подразумевает переписывание приложений.

Для реального использования высокой производительности ILP-процессоров необходимы компиляторы с языков высокого уровня, способные генерировать эффективный код. Применение одних лишь традиционных методов оптимизации кода оказывается совершенно недостаточным. Например, согласно [3] или [41], типичный компилятор для ЦПОС (поддерживающий только традиционные оптимизации) генерирует код, который по времени выполнения может уступать оптимальному в 5-10 и более раз.

В течение последних лет прилагаются значительные усилия по разработке специальных методов оптимизации программ для ILP-процессоров, направленных на выявление и расширение программного параллелизма на уровне команд. Настоящая работа содержит обзор таких методов.

В разделе 2 дается краткий обзор ILP-процессоров и их основных характеристик. Раздел 3 посвящен критериям оптимизации кода для ILP-процессоров. В разделе 4 представлена примерная схема работы компилятора, характеризуются основные задачи, связанные с оптимизацией кода для ILP-процессоров. В разделе 5 дается обзор способов формирования областей (фрагментов компилируемой программы), в рамках которых возможно эффективное распараллеливание. В разделе 6 описываются методы оптимизации, направленные на усиление внутреннего программного параллелизма в рамках выделенных областей. В разделе 7 рассматриваются методы распараллеливания кода в предварительно выделенных областях. Раздел 8 посвящен специфике оптимизации кода для ЦПОС. В разделе 9 приводится информация о языковых расширениях и их роли в увеличении эффективности процессоров. В заключении (раздел 10) представлены некоторые из актуальных нерешенных до настоящего время проблем оптимизации кода для ILP-процессоров.

ILP-платформы

Общие свойства ILP-процессоров - способность одновременно и независимо выполнять несколько операций и наличие нескольких функциональных устройств различных типов, таких как, например, устройство обмена с памятью, арифметическое устройство и др. В выполнении каждой команды участвует определенный набор функциональных устройств. Процессор может выполнять команды c1, ..., cn одновременно, если:

процессор имеет достаточно функциональных устройств для их совместного выполнения.

ни одна из команд ci не использует в качестве входных операндов результаты других команд c1, ..., cn;

ILP-процессоры могут различаться многими характеристиками, которые существенны с точки зрения применимости и эффективности рассматриваемых далее методов оптимизации. Данный раздел содержит краткий обзор типов ILP-процессоров и их свойств.

Одним из исторически первых видов процессорного параллелизма был конвейерный параллелизм, основанный на том, что выполнение команды разбивалось на этапы, на каждом из которых использовались определенные функциональные устройства (рис. 1). Средства конвейеризации обеспечивали совмещенный режим выполнения команд, когда эти команды оказывались независимыми друг от друга. При этом разработчики стремились добиться того, чтобы среднее количество тактов на выполнение команд в конвейере равнялось 1, т.е. чтобы темп выдачи команд составлял одну команду на такт.

Пусть исполнение команды состоит из 3-х этапов

по 1 процессорному такту на каждый:

1) чтение команды из памяти (Ч);

2) декодирование (Д);

3) исполнение (И).

Последовательное исполнение команд
Этапы	Ч1	Д1	И1	Ч2	Д2	И2	Ч3	Д3	И3
Такты 	1	2	3	4	5	6	7	8	9
Конвейерное исполнение команд
Устройство чтения:	Ч1	Ч2	Ч3	Ч4	Ч5	Ч6	Ч7
Устройство декодирования:		Д1	Д2	Д3	Д4	Д5	Д6	Д7
Устройство исполнения:			И1	И2	И3	И4	И5	И6	И7
Такты 	1	2	3	4	5	6	7	8	9
Конвейерное суперскалярное исполнение команд
Устройство чтения 1:	Ч1	Ч2	Ч3	Ч4	Ч5	Ч6	Ч7
Устройство декодирования 1:		Д1	Д2	Д3	Д4	Д5	Д6	Д7
Устройство исполнения 1:			И1	И2	И3	И4	И5	И6	И7
Устройство чтения 2:	Ч1	Ч2	Ч3	Ч4	Ч5	Ч6	Ч7
Устройство декодирования 2:		Д1	Д2	Д3	Д4	Д5	Д6	Д7
Устройство исполнения 2:			И1	И2	И3	И4	И5	И6	И7
Такты 	1	2	3	4	5	6	7	8	9

Рис. 1. Последовательное и параллельное исполнение команд

Естественным развитием средств конвейерной обработки явились процессоры с множественной выдачей команд на исполнение (multiple issue processors) - суперскалярные и VLIW-процессоры. Суперскалярный процессор исполняет обычный последовательный код, но может выбирать в нем и выдавать на выполнение одновременно несколько команд - не более n, где n - темп выдачи команд данного процессора. Различаются суперскалярные процессоры с упорядоченной и неупорядоченной выдачей команд на исполнение. Процессор первого типа выдает команды на исполнение в точности в том порядке, в котором они закодированы в программе. На каждом такте на исполнение выдается от 1 до n очередных команд с учетом возможности их параллельного исполнения. Процессор второго типа анализирует команды в пределах некоторого "окна" - текущего фрагмента входной программы - выбирая в нем для выдачи на исполнение от 1 до n команд с учетом связей по данным и возможности параллельного исполнения.

При разработке суперскалярных процессоров обычно преследуют цель обеспечить бинарную совместимость с предшествующими поколениями (скалярными или суперскалярными) данного модельного ряда процессоров (см. [51]). Суперскалярный процессор выполняет (без перекомпиляции) программный код для предшествующей модели, обеспечивая более высокую производительность.

VLIW-процессоры отличаются от суперскалярных тем, что код для них организован в виде последовательности очень длинных командных слов, каждое из которых содержит несколько команд (операций). Забота о корректном заполнении командных слов возлагается на компилятор (или программиста, пишущего на ассемблере). VLIW-процессоры в целом производительнее суперскалярных, поскольку не тратят время на динамический анализ зависимостей по данным и функциональным устройствам во время выполнения программы. Однако реальная эффективность выполнения программы целиком зависит от качества кода, сгенерированного компилятором.

Следует отметить, что и для суперскалярных процессоров применение ILP-оптимизаций при компиляции дает существенное повышение производительности (см. [55], [58]). Повышению эффективности исполнения на суперскалярных ЭВМ может способствовать также встраивание избыточной информации о программе, доступной во время компиляции и позволяющей процессору динамически производить дополнительные оптимизации. Пример применения этого подхода можно найти в [50].

VLIW-процессор способен работать с большей эффективностью, чем суперскалярный, поскольку у него нет необходимости заниматься динамическим анализом кода. Суперскалярный процессор, тем не менее, превосходит его в качестве планирования команд, поскольку имеет больше информации. Так, при статическом анализе невозможно предсказать случаи непопадания в кэш при чтении из памяти, из-за чего при выполнении возможны простои, в то время как динамический планировщик в этом случае может запустить другие готовые к исполнению команды. Компилятор не имеет права поменять местами команду чтения из памяти с последующей командой записи в память, поскольку адрес записи, возможно, совпадает с адресом чтения. Динамическому планировщику эти адреса уже известны, следовательно, он обладает большей свободой переупорядочения команд. Еще одно преимущество суперскалярных процессоров заключается в поддержке механизма предсказания ветвлений (branch prediction) и выполнения по прогнозу ветвления (control speculation). Аппаратура выбирает направление ветвления исходя из частоты предыдущих ветвлений в этой точке и с упреждением исполняет команды из более вероятной ветви. Это дает ускорение, если прогноз был верен. При неверном прогнозе аппаратура аннулирует результаты упреждающих вычислений.

Концепция явного параллелизма на уровне команд (EPIC - Explicitly Parallel Instruction Computing) возникла из стремления объединить преимущества двух типов архитектур. Идеология EPIC заключается в том, чтобы, с одной стороны, полностью возложить составление плана выполнения команд на компилятор, с другой стороны, предоставить необходимые аппаратные средства, позволяющие при статическом планировании на стадии компиляции использовать механизмы, подобные тем, которые применяются при динамическом планировании в суперскалярных архитектурах (см. [13]).

В разд. 7.4 и 7.6 рассматриваются некоторые характерные для EPIC-архитектур аппаратные средства

поддержка упреждающего выполнения команд на основе прогноза направления ветвления (control speculation);

поддержка выполнения по прогнозу данных (data speculation);

поддержка условного выполнения (predicated execution)

и их использование при статическом планировании.

С точки зрения применимости различных методов оптимизации существенно различие между VLIW-процессорами с регулярной и нерегулярной организацией командного слова. Последние отличаются тем, что на параллельно исполняемые инструкции налагаются дополнительные ограничения. В частности, для параллельно исполняемой инструкции могут допускаться в качестве операндов не все сочетания регистров или не все способы адресации, которые возможны в такой же инструкции, если параллельно с ней не закодированы другие инструкции. Такие особенности характерны, в частности, для цифровых процессоров обработки сигналов, где, в целях ускорения выборки команд, а также для сокращения общего размера кода и энергопотребления, проектировщики стремятся минимизировать длину командного слова и используют для этого нерегулярные способы кодирования. Нерегулярная организация командного слова (см. например, [52]) и связанные с ней ограничения параллелизма исполнения, называемые ограничениями кодирования, существенно усложняют задачу генерации эффективного кода при компиляции ([41],[59]).

Еще одна разновидность ILP-архитектур - кластерные архитектуры, где функциональные устройства поделены на группы (кластеры), и с каждым кластером связан набор локальных регистров, недоступных для функциональных устройств других кластеров (см. [54]). На рис. 2 изображен пример кластерной архитектуры.

Рис. 2. Кластерная архитектура

Специфическая проблема, возникающая при генерации кода для кластерных архитектур - минимизация обменов данных между регистровыми файлами разных кластеров.

Критерии оптимизации кода

Подходы, используемые при оптимизации кода, могут существенно зависеть от критериев оптимизации. Обычно рассматривают три критерия или их комбинации с некоторыми приоритетами:

минимизация времени выполнения программы;

минимизация размера кода;

минимизация энергопотребления.

Последний критерий существен при компиляции приложений для встроенных автономных систем. Размер кода, как правило, имеет второстепенное значение. Далее в основном будет рассматриваться критерий минимизации времени выполнения с учетом возможных ограничений на размер кода.

Локальные методы оптимизации, применяемые в пределах линейных участков, обычно направлены на сокращение одновременно и времени выполнения, и размера кода. Методы реорганизации кода (такие как развертка циклов, встраивание функций и др. - см. разд., 6.1, 6.3), направлены на ускорение работы компилируемой программы ценой увеличения размера выходного кода.

Возможны и другие, более специальные критерии и ограничения. Например, в работах [39] и [40] рассматривается метод планирования инструкций в условиях, когда для некоторых из них заданы начальные и/или конечные времена Tmini, Tmaxi, так что инструкция i должна сработать не позднее момента Tmaxi и не ранее момента Tmini. Подобные ограничения характерны для систем реального времени, где определенные действия должны совершаться в пределах заданных временных интервалов.

Фактор скорости компиляции, по мнению многих авторов ([41], [45], [58] и др.), для ILP-процессоров следует считать второстепенным. В особенности это справедливо в контексте компиляции для ЦПОС. С одной стороны, генерация оптимального кода для них существенно затрудняется из-за ограничений параллельного исполнения, с другой стороны, эффективность результирующего кода для них имеет гораздо более важное значение, чем скорость компиляции.

Круг проблем, связанных с оптимизацией кода для ILP-процессоров

Прежде чем перейти к рассмотрению основных задач, относящихся к ILP-оптимизации, рассмотрим в общих чертах схему работы компилятора, которая представлена на рис. 3 (см., например, [5],[6]). Компилятор для ILP-процессора объединяет в себе стандартные механизмы компиляции, имеющие смысл для всех целевых платформ, и специализированные методы анализа и оптимизации, направленные на выявление, усиление и использование параллелизма на уровне команд.

Рис. 3. Примерная схема компиляции; постпроцессирование – необязательный этап

На первом этапе проводится лексический, синтаксический и семантический анализ программы на входном языке и строится ее промежуточное представление.

В качестве промежуточного представления может использоваться, например, список, элементы которого соответствуют элементарным инструкциям реальной или гипотетической машины. Элементы промежуточного представления содержат информацию об операндах инструкции, о ее связях с другими инструкциями и т.п. В качестве элементов могут фигурировать также вспомогательные сущности, например, отметки о начале и конце циклов, метки и т.п.

Затем проводятся оптимизации в терминах промежуточного представления. Примеры стандартных оптимизаций, поддерживаемых большинством современных компиляторов, - удаление избыточного кода, свертка константных вычислений, выделение общих подвыражений, вынесение инвариантных вычислений из циклов, понижение мощности операций и др. [61]. В ILP-компиляции особое внимание уделяется методам усиления программного параллелизма в телах циклов, которые подробно рассматриваются в разд. 6.

В контексте ILP наибольший интерес представляет оптимизирующее преобразование, называемое планированием. В ходе планирования последовательность команд, сформированная традиционными методами компиляции, переупорядочивается, и команды группируются таким образом, чтобы обеспечить максимально быстрое параллельное исполнение. При этом учитываются связи между командами по данным и по управлению, а также аппаратные возможности параллельного исполнения команд. В применении к компиляции для VLIW-процессоров данное преобразование кода называют также распараллеливанием (code parallelization) или сжатием (code compaction).

Оптимизированное промежуточное представление преобразуется в ассемблерный код.

Применяются также (см. [47]) оптимизации на уровне ассемблерного кода (постпроцессирование). В ходе постпроцессирования кода, сгенерированного при помощи универсального компилятора, выполняются машинно-зависимые оптимизации. Такой подход позволяет ускорить создание оптимизирующего компилятора для нестандартной целевой платформы.

Существенной характеристикой большинства реализаций, как промышленных, так и экспериментальных, является настраиваемость компонентов компилятора на свойства и систему команд целевого процессора.

Перечислим коротко основные методы анализа, реорганизации и оптимизации кода, применяемые в ILP-компиляторах. Более подробно они рассматриваются в последующих разделах.

1. Выделение областей планирования. Область планирования - это фрагмент или множество фрагментов программы, в пределах которых применяется алгоритм планирования. В простейшем случае в качестве таких областей используются линейные участки в смысле [1] или [4] - последовательности команд, содержащие не более одной метки (в начале) и не более одной команды перехода (в конце). Однако в пределах линейного участка не всегда можно найти достаточно команд, способных исполняться параллельно. Поэтому разработчики компиляторов стремятся выделить более крупные области планирования, объединяющие несколько линейных участков. Различные типы областей планирования рассматриваются в разделе 5.

2. Реорганизации кода, направленные на удлинение линейных участков и расширение областей планирования - преобразования циклов, встраивание функций и др., см. разделы 6.1, 6.2.

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 читает это значение. Будем обозначать это отношение как cicj.

Зависимости этого типа называются истинными, поскольку они отражают объективные связи по данным между операциями, реализующими компилируемую программу: выполнение cj должно планироваться позже, чем выполнение ci. Как правило, избавиться от них нельзя, однако существуют приемы, позволяющие сделать это в некоторых специальных случаях: дублирование переменной суммирования и индуктивных переменных, рассматриваемые далее в этом разделе.

2. Связи типа "запись после записи". Команда cj зависит от ci, если

обе команды записывают значения в некоторый регистр r

j > i

имеется хотя бы одна команда сk, которая читает значение r, записанное командой ci.

Будем обозначать это отношение как cicj. Выполнение команды cj должно быть запланировано позже чем ci, если имеет место cicj.

3. Связи типа "запись после чтения". Команда cj зависит от ci, если существует команда ck, такая что имеет место ckci и ckcj. Будем обозначать это отношение cicj. Смысл этой зависимости в том, что ci читает некоторый регистр r, записанный ранее командой ck, а cj (j > i) записывает в r другое значение. Если имеет место cicj, то 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]).

Планирование команд

Алгоритмы планирования

После того как области планирования выделены и проведены оптимизации снятия зависимостей по данным, выполняется планирование команд. Считается, что на этом этапе для каждой области известны ее входные (вычисленные ранее) и выходные (используемые вне данной области) объекты.

В ILP-компиляции в основном применяются различные варианты приоритетного (эвристического) списочного планирования (list scheduling). Процесс планирования состоит из трех шагов:

1. Вычисление зависимостей по данным и по управлению между командами в пределах области планирования, которые обычно представляют в виде направленного ациклического графа. Зависимости по управлению препятствуют перемещению команд вокруг точек ветвления. Эти зависимости могут быть в дальнейшем частично сняты, т.е. при планировании команды могут перемещаться выше или ниже точек ветвления (см. далее разд.7.3, 7.4).

2. Вычисление приоритетов команд. Приоритеты определяют, в каком порядке будут планироваться готовые к исполнению команды на шаге 3. Способ вычисления приоритетов отражает эвристики планирования, от которых может существенно зависеть результат. Как правило, применяется эвристика планирования по критическому пути, когда приоритет команды определяется высотой соответствующего узла в графе зависимостей. Команды с совпадающими приоритетами упорядочивают либо произвольным образом, либо по некоторому вторичному признаку. В [31] приводятся результаты исследований нескольких эвристик глобального планирования в древовидных областях:

по глубине команды в графе зависимостей;

по числу выходов из области по всем путям в дереве управления, исходящим из данной команды (exit count). Согласно этой эвристике, наибольший приоритет получают команды, находящиеся в корне дерева.

по частоте выполнения на основе данных профилирования (global weight). Приоритет отдается наиболее часто исполняемым командам, а при равенстве частот команды упорядочиваются по глубине.

по взвешенной частоте выходов (weighted count). В качестве первичного критерия используется частота выполнения, а при равенстве частот - счетчик выходов.

Согласно результатам этой работы, наилучшие результаты в среднем дают эвристики 1) и 3); авторы рекомендуют использовать эвристику частоты исполнения, а если данные профилирования отсутствуют, то сортировать команды по глубине в графе зависимостей.

3. На последней фазе рассматриваются (в порядке своих приоритетов) готовые к исполнению команды и выдаются в выходной поток. Если целевой процессор является VLIW-процессором, то выходной поток состоит из длинных командных слов, каждое из которых может содержать несколько команд входного потока. Различаются следующие способы формирования выходного потока [32]:

Сверху вниз / снизу вверх. В первом случае команда рассматривается после того, как все ее предшественники в графе зависимостей выведены в выходной поток. При планировании снизу вверх команда рассматривается после того как выведены все ее потомки. При глобальном планировании более естественным является метод сверху вниз.

Перебор команд / заполнение командных слов. В первом случае планировщик на каждом шаге выбирает готовую к исполнению команду с максимальным приоритетом и подыскивает для нее подходящее командное слово в выходном потоке, так чтобы удовлетворялись связи по данным и ограничения по ресурсам (функциональным устройствам). Во втором случае планировщик последовательно заполняет командные слова. Среди готовых к исполнению команд подбираются команды, которые можно выполнить параллельно, и помещаются в очередное слово. Затем происходит заполнение следующего слова и т.д. Второй подход, по-видимому, предпочтителен для процессоров, где команда может занимать ресурс в течение нескольких тактов, а также для VLIW-процессоров с нерегулярной структурой командного слова.

Иногда применяют дополнительную эвристику, выбирая из множества готовых к исполнению те команды, которые максимально расширят это множество на следующем шаге (см. [9]).

Интересный альтернативный алгоритм планирования, который предложен в работе [11], используется в системе построения компиляторов [5]. Это переборный алгоритм локального планирования, позволяющий находить наилучший по времени план выполнения. Идея его заключается в следующем. Пусть G=(A,V,E) - смешанный граф, где A - множество вершин (операций линейного участка), V - множество дуг, соответствующих зависимостям по данным, E - множество ненаправленных ребер, таких что [a,b]  E, если параллельное исполнение операций a, b невозможно в силу аппаратных ограничений. Из смешанного графа G можно при помощи перебора получить множество ориентированных графов, заменяя каждое из ненаправленных ребер из E на дугу, направленную в ту или другую сторону (если операции a, b невозможно выполнить параллельно, то либо a должна выполниться раньше b, либо наоборот). Каждый ациклический граф, полученный таким образом из G, однозначно определяет план выполнения линейного участка. Среди всех планов выбирается наилучший по времени выполнения.

Время работы алгоритма экспоненциально зависит от длины линейного участка, поэтому автор рекомендует использовать его для оптимизации циклов. Ограничением этого подхода является также предположение о том, что несовместимость команд (невозможность их параллельного исполнения) можно описать в виде бинарного отношения, что не верно, например, если процессор имеет несколько однотипных функциональных устройств. Возможны ситуации, когда, скажем, команды a, b, c несовместимы, хотя любые две из них совместимы.

Координация планирования и распределения регистров

Процедуры планирования и распределения регистров при генерации кода для ILP-процессоров имеют в каком-то смысле конфликтующие цели. Для того чтобы полнее загрузить работой функциональные устройства, планировщик стремится максимально использовать программный параллелизм, а для этого необходимо, чтобы как можно большее число значений находилось на регистрах. Распределитель регистров, напротив, стремится сократить использование регистров, чтобы исключить выталкивание значений в память (а также их сохранение/восстановление при вызовах подпрограмм). Поэтому в компиляторе для ILP-процессора важно обеспечить правильное взаимодействие этих двух механизмов.

Если распределение регистров выполняется до планирования, то это может снизить программный параллелизм из-за введения антизависимостей по данным при переиспользовании регистров. С другой стороны, если планирование выполняется до распределения регистров, то зачастую генерируется код, требующий больше регистров, чем имеется в наличии. В таком случае распределитель регистров вынужден выталкивать часть значений в память и добавлять в программу команды загрузки и выгрузки этих значений, что может привести к деградации выходного кода.

Для решения этой проблемы применяются подходы, включающие повторное планирование, интеграцию обеих процедур или передачу информации между ними.

Повторное планирование. Перед распределением регистров выполняется предварительное планирование. На этом этапе для хранения каждого значения используется уникальный виртуальный регистр, так что отрицательный эффект антизависимостей по данным исключен. Затем проводится распределение регистров и окончательное планирование, во время которого планируется исполнение дополнительных команд, которые могли быть сгенерированы в ходе распределения регистров ([24], [33]).

Распределение регистров с использованием информации, полученной от планировщика. В [57] описывается модификация классического решения задачи распределения регистров методом раскраски графа (см., например, [8]). Задача раскраски формулируется для графа, в котором представлены не только данные об областях жизни значений, но и информация о возможности параллельного исполнения команд (parallel interference graph). Переиспользование регистров по возможности исключается в тех случаях, когда оно влечет ограничение параллелизма. Информация о возможности параллельного исполнения вычисляется планировщиком. Аналогичный подход представлен в [56].

В [21] представлен алгоритм совместного планирования и распределения регистров, где и регистры, и функциональные устройства рассматриваются как ресурсы.

В [25] и [38] предлагаются специальные алгоритмы планирования для развернутых циклов, обеспечивающие контроль числа требуемых регистров, с тем чтобы исключить или минимизировать обмены с памятью.

В компиляторе для архитектуры TriMedia [32] реализован комбинированный подход, где распределение глобальных регистров осуществляется обычным методом раскраски графа, а распределение локальных регистров (для областей жизни, не выходящих за границы линейных участков) осуществляется непосредственно планировщиком, который постоянно отслеживает уровень дефицита регистров (register pressure) и динамически перевычисляет приоритеты команд. Как только уровень дефицита регистров превышает некоторый порог, приоритеты команд пересчитываются таким образом, чтобы преимущество отдавалось командам, выполнение которых приведет к снижению дефицита. При низком уровне дефицита регистров увеличивается приоритет команд, которые открывают новые области жизни, что повышает возможности распараллеливания кода (чем больше значений находится на регистрах, тем больше команд, готовых к исполнению).

При генерации кода для кластерных архитектур возникает проблема минимизации обмена данных между регистровыми файлами разных кластеров. Решение этой проблемы предлагается в [54], где планирование совмещается с назначением кластеров. Аналогичный подход используется в [43].

Глобальное планирование

Преимущество глобального планирования заключается в том, что оно применяется к более крупным фрагментам программы, состоящим из нескольких линейным участкам. В результате появляется возможность более эффективного использования аппаратных средств параллельного исполнения. Для того чтобы это преимущество реально работало, необходимо уметь перемещать команды вокруг точек ветвления. Рассмотрим более подробно соответствующие проблемы и решения.

Перенос команды ниже точки ветвления является частным случаем миграции команд, которая описана выше в разд. 6.2. Более интересен случай переноса команды выше предшествующей точки ветвления. Этот вид переноса может быть полезен по двум причинам:

в предшествующем линейном участке, возможно, имеется свободная позиция в одном из командных слов, куда можно поместить рассматриваемую команду;

если команда имеет задержку (т.е. ее результат можно использовать только по истечению некоторого числа тактов), то выгодно запланировать ее выполнение как можно раньше, в особенности, если она находится на критическом пути.

Перенос команд выше точки ветвления можно назвать упреждающим выполнением (в англоязычной литературе используется термин speculative execution или control speculation), поскольку команда выполняются раньше, чем становится известно, будет ли передано управление в участок, где она изначально находилась.

Рассмотрим ограничения, которые должны соблюдаться при переносе команд выше точки ветвления, на примере (рис. 13).

Рис. 13. Перенос команды C выше точки ветвления B

Перенос команды C выше точки ветвления B (в участок ЛУ1) возможен при соблюдении двух ограничений (см. [30], [35], [48]):

Ограничение 1. Прежнее значение регистра, в который C записывает свой результат, не требуется больше ни одной команде в ЛУ1 или в других участках, куда может быть передано управление из ЛУ1.

Ограничение 2. Команда C не может вызвать прерывание, которое приведет к завершению программы.

Некорректность переноса команды при несоблюдении второго ограничения можно проиллюстрировать на простом примере рис. 14.

Рис. 14. Перенос команды "C=A/B" выше команды ветвления некорректен, так как это приведет к аварийному завершению программы при B=0

Планирование с соблюдением обоих ограничений называют "ограниченной фильтрацией" (restricted percolation). При соблюдении обоих ограничений число команд, перенос которых реально возможен, оказывается невелико, что значительно снижает эффективность глобального планирования. Поэтому важное значение имеют методы, позволяющие снять эти ограничения.

Ограничение 1 можно снять путем переименования регистров - для значения, которое вычисляется в команде C, назначается другой регистр.

Для снятия ограничения 2 необходимы средства аппаратной поддержки, описанные в следующем разделе.

Аппаратная поддержка глобального планирования

Упреждающее выполнение применяется как в динамическом (аппаратном) планировании в суперскалярных процессорах с неупорядоченной выдачей команд, так и в статическом планировании во время компиляции. Здесь будут рассмотрены характерные для EPIC-архитектур аппаратные расширения, которые позволяют планировать упреждающее выполнение команд во время компиляции. Существуют две модели поддержки упреждающего выполнения - модель неограниченной фильтрации (general percolation, см. [35]) и модель защищенного планирования (sentinel scheduling, см. [48]).

Первая модель предполагает наличие в аппаратуре непрерываемых версий всех команд. Если планировщик переносит команду выше точки ветвления, то он использует ее непрерываемую версию. Упреждающее выполнение записей в память не допускается. Исключительные ситуации, если они возникают, игнорируются. Получаемые при этом неправильные результаты могут сказаться на дальнейшем выполнении, например, привести позднее к прерываниям или просто к неверным результатам.

Вторая модель обеспечивает корректность статического планирования с применением упреждающего выполнения и включает следующие аппаратные расширения:

1. В кодировку команд добавляется бит упреждающего выполнения. Если он установлен, то говорят, что команда выполняется в режиме упреждающего выполнения, в котором прерывания не выдаются. Если возникает исключительная ситуация, то в регистре результата устанавливается бит прерывания. То же происходит, если бит прерывания установлен хотя бы в одном из регистров-операндов. При выполнении команд в обычном режиме должны выдаваться прерывания, если хотя бы один из входных регистров имеет установленный бит прерывания (или если исключительная ситуация возникла при выполнении самой команды).

2. К каждому регистру добавляется бит прерывания, который устанавливается при выполнении команд в режиме упреждающего выполнения, если возникает исключительная ситуация, и может быть опрошен при помощи специальной команды check_exception(R). С каждым регистром связывается также поле диагностики, в которое заносится программный адрес возникновения исключительной ситуации. Бит прерывания вместе с полем данных должны сохраняться и восстанавливаться при временном сохранении регистра в памяти.

3. К системе команд добавляется команда для опроса бита прерывания заданного регистра check_exception(R). Если бит установлен, то возникает прерывание.

При наличии перечисленных средств компилятор получает возможность закодировать упреждающее выполнение команды C следующим образом:

в новой позиции команды C (выше точки ветвления) помещается ее вариант с битом упреждающего выполнения;

в прежней позиции команды C помещается команда check_exception, для того чтобы обеспечить прерывание, если оно должно произойти. Если имеется команда, выполняемая в обычном режиме и использующая результат команды C, то команда check_exception не генерируется.

Пример из [48], показанный на рис. 15, демонстрирует применение указанных средств при планировании.

A: if (r2==0) goto L1	*B: r1 = mem(r2)
B: r1 = mem(r2)	*C: r3 = mem(r4)
C: r3 = mem(r4)	*D: r4 = r1+1
D: r4 = r1+1	*E: r5 = r3*9
E: r5 = r3*9	A: if (r2==0) goto L1
F: mem(r2+4) = r4	F: mem(r2+4) = r4
	G: check_exception(r5)
a)	b)

 

Рис. 15. Планирование команд с упреждающим выполнением: a) исходный код; b) код, полученный в результате планирования. Буквы A-G служат для идентификации команд. Символом * отмечены команды с признаком упреждающего выполнения

На рис. 15 показан код до и после планирования (в предположении, что исключительные ситуации возможны только при обращениях к памяти). Команды F и G обеспечивают проверку исключительных ситуаций, которые могли возникнуть при упреждающем выполнении команд B, C.

Для того чтобы разрешить упреждающее выполнение команд записи в память, предусматривается аппаратное расширение, основанное на введении дополнительных полей в элементы буфера записи в память.

Важным преимуществом модели защищенного планирования является поддержка адекватной диагностики исключительных ситуаций с указанием адреса фактического возникновения, даже если команда-источник выполнялась в упреждающем режиме.

По результатам тестов, приведенным в [48], применение защищенного планирования по сравнению с ограниченной фильтрацией на задачах нечисловой обработки дает существенное ускорение результирующих программ. Например, для процессора с темпом выдачи 8 команд на такт коэффициент ускорения при использовании защищенного планирования был от 18 до 135% (в среднем на 57%) выше, чем при планировании с ограниченной фильтрацией.

Для численных приложений, не содержащих большого числа условных переходов во внутренних циклах (таких как операции над матрицами), разница коэффициентов ускорения оказалась незначительной. Коэффициенты ускорения для этих приложений оказались достаточно высокими уже при ограниченной фильтрации. Для двух численных приложений с значительным количеством условных переходов во внутренних циклах улучшение коэффициента ускорения составило 36-38%.

Другое аппаратное расширение, предназначенное для поддержки глобального планирования - средства условного выполнения команд ([15], [58]). Например, процессор TM1000 [32] позволяет задавать в команде предикатный операнд, в качестве которого может выступать любой из 128 регистров. В зависимости от значения младшего бита этого операнда результат операции будет записан или проигнорирован. Аналогичные возможности поддерживаются в процессоре IA-64 ([36], [60]) и др.

Компилятор может слить условно выполняемый линейный участок с объемлющим участком, заменив составляющие его инструкции условно выполняемыми (рис. 16). В результате зависимости по управлению фактически заменяются зависимостями по данным, которые существенно удобнее с точки зрения планировщика.

c:= вычислить(условие) c:= вычислить(условие) [c] goto then_label [c] B_THEN

B_ELSE [!c] B_ELSE

goto join_label

then_label: B_THEN

join_label: ...

a) b)

Рис. 16. Реализация конструкции "if (условие) then B_THEN else B_ELSE" при помощи условных переходов (a) и условным выполнением (b). Обозначение [c] указывает, что команда будет выполнена только если предикат c имеет значение "истина"

В работе [44] рассматривается метод, позволяющий для заданной иерархии вложенных конструкций if-then-else выбрать оптимальные (по средней скорости выполнения результирующей программы) способы реализации.

Поддержка условного выполнения делает особенно эффективным планирование в древовидных областях [32], [31]. Для каждого линейного участка древовидной области вычисляется предикат, который приписывается всем командам этого участка. В результате исключается большая часть условных переходов и появляется возможность планировать параллельное исполнение различных ветвей дерева.

Метод доминантного параллелизма при планировании в древовидных областях

Недостаток метода "дублирования хвостов" заключаются в генерации избыточного кода. При использовании упреждающего исполнения это приводит к нерациональному расходованию вычислительных ресурсов и может замедлить исполнение. В ряде случаев планировщик способен исключить отрицательные последствия при помощи метода доминантного параллелизма (dominator parallelism) [31]. Если команды из некоторого линейного участка BBi и его копии BBi' можно поднять в доминирующий участок BBk (являющийся общим предком BBi и BBi'), то можно оставить только по одному экземпляру команд. Пример ситуации, когда этот прием применим, показан на рис. 17.

Рис. 17. Доминантный параллелизм. Командy r6=0 из линейного участка BB5 и его копии BB5' можно поднять в BB2 (или BB1) и исключить их дублирование

Планирование по прогнозу значений данных

Упреждающее выполнение команд по прогнозу данных (data speculation) широко применяется в динамическом аппаратном планировании в суперскалярных процессорах. Смысл этого приема заключается в том, что значение объекта используется до того, как оно записано, в предположении, что значение останется прежним. Разумеется, если значение все-таки изменяется, процессор обеспечивает перевычисление команд, выполненных с упреждением. EPIC-архитектуры предоставляют аппаратную поддержку для использования аналогичного механизма при статическом планировании в компиляторе по отношении к объектам, хранящимся в памяти, см. [36] или [60].

... ...

MEM(R0) = R1 R2=MEM(R3)' ; упреждающее

... ; чтение

R2=MEM(R3) ...

R4=R2+R2 MEM(R0)=R1

... check(address(R3)),L1

R4=R2+R2

a) b)

Рис. 18. Перестановка операций чтения и записи с использованием аппаратной поддержки упреждающего чтения

При наличии таких аппаратных средств компилятор получает возможность переупорядочивать команды чтения и записи памяти. Это может быть полезно по нескольким причинам:

как можно раньше выполнить команды считывания из памяти, лежащие на критическом пути;

использовать свободную позицию в командном слове,

исключить задержки, связанные с чтением данных из памяти.

На рис. 18a показан пример последовательности вычислений, содержащий команды записи в память (MEM(R0) = R1) и чтения из памяти (R2=MEM(R3)). Компилятор, вообще говоря, не имеет права запланировать чтение раньше записи, если он не имеет точной информации о том, что команда записи не перепишет считываемое значение.

Аппаратная поддержка упреждающего считывания из памяти может состоять из следующих средств (см. [13], [36]):

имеется команда упреждающего считывания, которая считывает значение по указанному адресу и запоминает этот адрес во внутренней таблице процессора;

при записи в память и при обычном считывании содержимое таблицы проверяется, и если в ней присутствует указанный адрес, то соответствующий элемент таблицы помечается как недействительный (или просто исключается)

имеется команда, позволяющая узнать, не было ли записи по заданному адресу с момента упреждающего считывания по этому адресу; если запись была, то выполнить переход по указанному адресу. Подразумевается, что по этому адресу должен находиться компенсирующий код.

На рис. 18b показан пример перестановки чтения и записи памяти с использованием этих средств. Команда чтения (в упреждающем режиме) помещается до команды записи. На месте прежнего положения команды считывания (до использования результата) помещена команда проверки адреса. Если оказалось, что по этому адресу была произведена запись, то управление передается по метке L1, где размещается сгенерированный компилятором компенсирующий код.

Особенности генерации кода для ЦПОС

Особенности генерации эффективного кода для ЦПОС связаны как с нерегулярностью схем кодирования, так и с другими характерными чертами этих процессоров, такими как наличие специализированных команд, нескольких пространств памяти и др. В этом разделе представлены специфические подходы, применяемые в компиляторах для ЦПОС.

Наиболее важной в контексте компиляции для ЦПОС представляется задача планирования (сжатия) кода. Специфика планирования для VLIW-процессоров с нерегулярными схемами кодирования связана с многочисленными ограничениями на параллельное исполнение команд, из-за которых существенно снижаются возможности использования внутреннего параллелизма программы при генерации кода. В ЦПОС также в меньшей степени представлены аппаратные расширения для поддержки параллелизма - условное выполнение, поддержка упреждающего выполнения. При этом именно для данного класса процессоров, в силу специфики областей применения, генерация оптимального кода имеет особенно важное значение.

В силу перечисленных причин в компиляторах для ЦПОС вместо эвристического глобального планирования более разумным представляется применение алгоритмов для поиска точного оптимального решения в пределах линейных участков.

В [45] приводятся следующие аргументы в пользу локального планирования:

Методы глобального планирования так или иначе опираются на локальные методы, которые сами по себе в контексте компиляции для ЦПОС еще недостаточно изучены и разработаны. Поэтому разумно начать с их детального исследования и оценки.

Популярные глобальные методы разрабатывались для регулярных VLIW-процессоров с высоким уровнем аппаратного параллелизма и проявили свою высокую эффективность для этого класса архитектур, в то время как в ЦПОС уровень параллелизма как правило значительно ниже из-за ограничений кодирования.

В глобальном планировании для сохранения корректности программы в нее приходится добавлять компенсирующий код. Это может привести к существенному увеличению размера программы, что неприемлемо, если объем памяти ограничен.

К этому можно добавить, что:

Преимущества глобального планирования экспериментально подтверждены для программ нечисленного характера; для программ численных расчетов выигрыш от глобального планирования, вероятно, не столь значителен.

Применение глобального планирования наиболее эффективно при наличии аппаратных расширений для его поддержки.

В [45] рассматривается подход к задаче локального планирования для определенного класса ЦПОС, основанный на методах целочисленного линейного программирования (см. [10]) и позволяющий находить кратчайший выходной код для процессора с заданными ограничениями на параллельное исполнение команд. Хотя время нахождения решения экспоненциально зависит от длины линейного участка, по мнению авторов, применение подобных подходов в компиляции для ЦПОС оправдано. Важная положительная черта предлагаемого метода заключается в поддержке вариантов команд - если процессор предоставляет несколько различных типов команд для выполнения одной и той же операции, то при поиске оптимального решения обеспечивается перебор вариантов.

В [23] и [29] также представлены реализации локальной оптимизации кода для ЦПОС на основе методов линейного программирования. В этих реализациях совмещается решение задач распределения регистров, распараллеливания и выбора команд (code selection) с учетом наличия в процессоре составных операций типа A=A+B*C.

Другая проблема, обусловленная нерегулярным характером кодирования, - способ представления ограничений на параллельное исполнение команд в планировщике. Если в регулярных ILP-архитектурах эти ограничения достаточно легко описать и представить в виде общего числа функциональных устройств каждого вида и наборов устройств, занимаемых каждой командой, то для процессоров с нерегулярным кодированием их рациональное представление составляет более сложную задачу. В [59] описывается подход, позволяющий свести нерегулярный набор ограничений к регулярному представлению путем определения набора искусственных аппаратных ресурсов и приписывания соответствующего мультимножества ресурсов каждому виду команд процессора. Недостатком предлагаемой реализации является то, что ее применимость ограничена слишком жесткими предположениями о структуре системы команд.

Характерной особенностью многих ЦПОС является малое число регистров, их специализация или кластерная организация. Это также требует особых подходов при распараллеливании и выборе кода ([16], [43]).

Как показано в [23], применение некоторых оптимизаций, считающихся машиннонезависимыми (таких как свертка констант, исключение общих подвыражений), в контексте компиляций для ЦПОС требует особых подходов с учетом специфики организации командного слова и числа доступных регистров в конкретном целевом процессоре.

Поскольку при программировании для ЦПОС обычно налагаются ограничения на размер кода, то при реорганизациях циклов и встраивании функций необходимо учитывать этот фактор. С этой точки зрения интересна работа [42], где рассматривается методика встраивания функций с контролируемым ростом объема кода. Аналогичные методики могут быть полезны и для преобразований циклов.

Важно понимать, что проблема генерации оптимального кода для ЦПОС не сводится только к задаче сжатия кода с учетом возможностей параллельного исполнения. Хороший компилятор для ЦПОС должен уметь эффективно использовать их архитектурные особенности - решать задачу оптимального размещения программных данных в пространствах памяти [41], поддерживать языковые расширения для указания пространства памяти в декларациях переменных [33], решать задачу выбора кода с учетом имеющегося набора команд в процессорах с системами команд для специальных приложений - Application Specific Instruction Set Processors (ASIP), (см. [16],[17]), выделять циклические буферы, оптимизировать способы адресации при обращениях к памяти (см. [29], [41], [46]) и др.

О роли языковых расширений

В различных реализациях компиляторов с языка Си для ILP-архитектур делаются попытка отразить на уровне входного языка специфику этих процессоров и особенности программирования для них ([14], [33]). Операции над комплексными, векторными, матричными данными, явно выраженные в терминах исходного языка, могут быть непосредственно отражены в эффективные связки команд ILP-процессоров.

Комплексный тип данных зафиксирован в последнем стандарте языка Си [37]:

#include <complex.h>

complex float x, y = 1.0 + 3.0 * I;

Для комплексного типа определен набор обычных операций и библиотечных функций.

Векторные и матричные операции, привлекательные с точки зрения возможности напрямую использовать параллелизм на уровне команд, к сожалению, плохо “встраиваются” в синтаксис языка Си, поскольку имена массивов трактуются как описатели. Поэтому, например, в стандарте ANSI Numerical C, разработанном группой NCEG (Numerical C Extension Group) для численных приложений, введены понятия итератора и оператора суммирования, отражающие семантику матричных операций.

Пример описания и использования итератора:

iter I = N;

A[I] = sin (2 * PI * I / N)

Этот фрагмент программы эквивалентен следующему тексту на стандартном Си:

int i;

for (i = 0); i < N; i++)

{

A[i] = sin (2 * PI * i / N);

}

Пример вычисления произведения матриц с использованием итераторов и операторов суммирования:

iter I=N, J=N, K=N;

A[I][J] = sum (B[I][K] * C[K][J]);

Суммирование здесь производится по итератору K. В общем случае суммирование проводится по всем свободным итераторам, т.е. итераторам, которые не встречаются в том же итераторе вне оператора суммирования.

В работе [33] также предлагаются некоторые другие расширения, отражающие специфику ЦПОС – пространства памяти, циклические буферы.

Положительные стороны такого рода расширений — краткость и естественность исходных текстов, возможность эффективно отобразить высокоуровневые операции в оптимальный для заданной целевой платформы код.

Заключение

Круг вопросов, связанных с генерацией эффективного кода для ILP-архитектур, охватывает проблемы формирования областей планирования, снятия зависимостей по данным и по управлению, алгоритмы планирования (распараллеливания) кода, соотношение между планированием и распределением регистров.

Несмотря на обилие уже разработанных и опробованных подходов, создание эффективного компилятора для ILP-процессора в каждом конкретном случае остается непростой задачей. Сложность проблемы связана отчасти с тем, что эффективность практически всех методик существенно зависит как от аппаратных особенностей процессора (степень параллелизма, количество регистров, поддержка условного и упреждающего исполнения), так и от характера компилируемых программ (планирование в расширенных областях наиболее эффективно для программ управляющего характера; в программах вычислительного характера эффект от их применения менее значителен).

Наиболее сложной, по-видимому, остается проблема генерации эффективного кода для ЦПОС. Для VLIW-процессоров с регулярной организацией командного слова основным препятствием к распараллеливанию команд является недостаточность программного параллелизма, поэтому усилия разработчиков компиляторов для них направлены, в основном, на его повышение (за счет расширения областей планирования и снятия зависимостей по данным и по управлению). При успешном решении этой задачи быстрые алгоритмы эвристического списочного планирования могут давать приемлемые результаты. В ЦПОС, в силу нерегулярности кодирования, распараллеливание команд затрудняется, в первую очередь, многочисленными сложными ограничениями кодирования. Поэтому для них необходимы более сложные и трудоемкие переборные методы, такие как [45] или [29]. В связи с этим особый интерес представляет разработка практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков.

Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы.

Преобразования циклов, направленные на усиление программного параллелизма – развертка циклов, слияние и разбивка циклов, конвейеризация циклов.

Преобразования, направленные на ослабление зависимостей по данным – перемещение кода, переименование регистров, дублирование переменных суммирования в циклах и др.

Применение методов глобального планирования потока команд на основе алгоритма списочного планирования.

Использования аппаратных средств поддержки упреждающего выполнения и упреждающего чтения данных.

Совмещение планирования команд и распределения регистров.

Применение локального планирования на основе целочисленного линейного программирования;

Реализация языковых расширений.

При выборе конкретных методов и их параметров необходимо учитывать уровень аппаратного параллелизма и другие особенности целевого процессора, а также характер типичных приложений.

Благодарности

Автор выражает благодарность Виктору Зиновьевичу Шнитману и Андрею Геннадьевичу Шадскому за полезные консультации.

Литература

Ахо А., Сети Р., Ульман Д., Компиляторы: принципы, технологии и инструменты. – М., Издательский дом "Вильямс", 2001.

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, том 2. - М., Мир, 1978.

Балашов В.В., Капитонова А.П., Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Метод и средства оценки времени выполнения оптимизированных программ. - Программирование #5, 2000, c. 52 61.

Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Описание VLIW-архитектуры в оптимизирующем постпроцессоре. М.: НИИСИ РАН, 2001.

Дорошенко А.Ю., Куйвашев Д.В. Архитектура модульного кросс компилятора для микропроцессоров с очень длинным командным словом. - Проблемы программирования, 2000 г., N 3-4, с. 122-134 (на укр. языке).

Дорошенко А.Ю., Куйвашев Д.В. Интеллектуализация векторизующих компиляторов для микропроцессоров с длинным командным словом. - Проблемы программирования, 2001 г., N 1-2, с. 138-151 (на укр. языке).

Евстигнеев В.А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом (обзор). - Программирование, 1991, N 2, стр. 69-80.

Ершов А.П. Введение в теоретическое программирование. - М., Наука, 1977.

Калашников Д.В., Машечкин И.В., Петровский М.И. Планирование потока инструкций для конвейерных архитектур. - Москва, МГУ, Вестник Московского университета, серия 15 (вычислительная математика и кибернетика), N4, 1999, с. 39-44.

Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. - М., Мир, 1985.

Скворцов С.В. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов. - Программирование 1996, N 2, стр. 41-52.

Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации. - Программировние, 1992, N 3, стр. 16-37.

Шланскер М.С., Рау Б.Р. Явный параллелизм на уровне команд. Открытые Системы, #11-12, 1999.

ADSP-21000 Family. C Tools Manual. - Analog Devices, Inc. http://www.analog.com/publications/documentation/CTools_manual/books.htm

Allen J.R., Kennedy K., Porterfield C., Warren J.D. Conversion of Control Dependence to Data Dependence. Proceedings of the 10th ACM Symposium on Principles of Programming Languages. Jan. 1983, pp. 177-189.

Araujo G., Malik S. Optimal Code Generation for Embedded Memory Non-Homogeneous Register Architectures. - 8th Int. Symp. on System Synthesis (ISSS), 1995, pp. 36-41.

Araujo G., Malik S., Lee M. Using Register-Transfer Paths in Code Generation for Heterogeneous Memory-Register Architectures. - In ACM IEEE Design Automation Conference (DAC), number 33, pp. 591-596, June 1996.

Banerjia S., Havanki W.A., Conte T.M. Treegion Scheduling for Highly Parallel Processors. - Proceedings of the 3rd International Euro-Par Conference (Euro-Par'97, Passau, Germany), pp. 1074-1078, Aug. 1997.

Benitez M. E., Davidson J. W. Target-specific Global Code Improvement: Principles and Applications. - Technical Report CS-94-42, Department of Computer Science, University of Virginia, VA 22903.

Bernstein D., Rodey M. Global Instruction Scheduling for Superscalar Machines. - Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pp.241-255, June 1991.

Berson D. A., Gupta R., Soffa M. L. Integrated Instruction Scheduling and Register Allocation Techniques. - In Proc. of the Eleventh International Workshop on Languages and Compilers for Parallel Computing, LNCS, Springer Verlag, Chapel Hill, NC, Aug. 1998.

Bharadwaj J., Menezes K. McKinsey C. Wavefront Scheduling: Path Based Data Representation and Scheduling of Subgraphs. The Journal of Instruction-Level Parallelism, May 2000.

Bruggen T., Ropers A. Optimized Code Generation for Digital Signal Processors. - Institute for Integrated Signal Processing, http://www.ert.rwth-aahen.de/coal .

Chang P. P., Mahlke S. A., Chen W. Y., Warter N. J., Hwu W. W. IMPACT: An architectural framework for multipleinstruction-issue processors," in Proceedings of the 18th International Symposium on Computer Architecture, pp. 266-275, May 1991.

Eichenberger A. E., Davidson E. S., Abraham S. G. Minimizing Register Requirements of a Modulo Schedule via Optimum Stage Scheduling. - International Journal of Parallel Programming, February, 1996.

Eichenberger A. E., Lobo S. M. Efficient Edge Profiling for ILP-Processors. - Proceedings of PACT 98, 12-18 October 1998 in Paris, France..

Fisher J. A. Global code generation for instruction-level parallelism: Trace Scheduling-2. - Tech. Rep. HPL-93-43, Hewlett-Packard Laboratories, June 1993

Fisher J.A. Trace scheduling: A Technique for Global Microcode Compaction. - IEEE Transaction on Computers, vol. 7, pp. 478-490, July 1981.

Gebotys C. H., Gebotys R. J. Complexities In DSP Software Compilation: Performance, Code Size, Power, Retargetability. 1060-3425/98, IEEE, 1998.

Grossman J.P. Compiler and Architectural Techniques for Improving the Effectiveness of VLIW Compilation. – submitted to ICCD 2000.

Havanki W. A., Banerjia S., Conte T. M. Treegion Scheduling for Wide Issue Processors. - Proc. 4th Intl. Symp. on HighPerformance Computer Architecture, Feb. 1998, pp. 266-276.

Hoogerbrugge J., Augusteijn L. Instruction Scheduling for TriMedia. - The Journal of Instruction-Level Parallelism, February 1999

Horst E., Kloosterhius W., Heyden J. A C Compiler for the Embedded R.E.A.L DSP Architecture. - Материал получен с телеконференции comp.dsp.

Hsu P.Y.T., Davidson E.S. Highly Concurrent Scalar Processing. - Proceedings of the 13th Annual International Symposium on Computer Architecture, pp. 386-395. June 1986.

Hwu W.W., Mahlke S.A., Chen W.Y., Chang P.P., Warter N.J., Bringmann R.A., Quelette R.G., Hank R.E., Kiyohara T., Haab G.E., Holm J.G., Lavery D.M. The Superblock: An Effective Technique for VLIW and Superscalar Compilation. - The Journal of Supercomputing, vol. 7, pp. 229-249, May 1993.

IA-64 Application Developer's Architecture Guide. - Intel, May 1999.

ISO/IEC 9899:1999(E). Programming Languages - C. - ISO/IEC, 1999.

Kiyohara T., Gyllenhaal J. C. Code Scheduling for VLIW/ Superscalar Processors with Limited Register Files. Proceedings of the 25th International Symposium on Microarchitecture, Dec. 1992, pp. 197-201.

Leung A., Palem K.V. A fast algorithm for scheduling timeconstrained instructions on processors with ILP. - In The 1998 International Conference on Parallel Architectures and Compilation Techniques (PACT 98), Paris, October, 1998.

Leung A., Palem K.V. Scheduling Time-Constrained Instructions on Pipelined Processors. - Submitted for publication to ACM TOPLAS, 1999.

Leupers R. Code Generation for Embedded Processors. - ISSS 2000, Madrid/Spain, Sept. 2000.

Leupers R. Function Inlining under Code Size Constraints for Embedded Processors. – ICCAD’99, San Jose (USA), Nov 1999.

Leupers R. Instruction Scheduling for Clustered VLIW DSPs. -Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT'00).

Leupers R. Novel Code Optimization Techniques for DSPs.- 2nd European DSP Education and Research Conference, Paris/France, Sep 1998.

Leupers R., Marwedel P. Time-Constrained Code Compaction for DSPs. - 8th Int. System Synthesis Symposium(ISSS), 1995. Trans. on VLSI Systems, Vol. 5, no. 1, March 1997.

Liao S., Devadas S., Keutzer K., Tjiang S., Wang A. Storage Assignment to decrease code size. – ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 186-195, 1995.

Lin W.-Y., Lee C.G., Chow P. An Optimizing Compiler for the TMS320C25 DSP Chip. - Proceedings of the 5th International Conference on Signal Processing Applications and Technology, pp. I-689I-694, October 1994.

Mahlke S. A., Chen W. Y., Hwu W. W., Rau B. R., Schlansker M. S. Sentinel Scheduling for VLIW and Superscalar Processors. - ASPLOS-V Conference Proceedings, October 1992.

Mahlke S.A., Lin D.C., Chen W.Y., Hank R.E., Bringmann R.A. Effective Compiler Support for Predicated Execution Using the Hyperblock. - Proceedings of the 25th Annual International Workshop on Microprogramming (Portland, Oregon), pp. 45-54, Dec. 1992.

Martin M. M., Roth A., Fischer C. N. Exploiting Dead Value Information. - 30th International Symposium on Microarchitecture, pages 125--135, December 1997.

Moreno J.H. Dynamic Translation of tree-instructions into VLIW. IBM Research Report, 1996.

Motorola DSP96000 User's Manual. - Motorola, Inc., 1990.

Motorola DSP96KCC User's Manual. - Motorola, Inc., 1990.

Ozer E., Banerjia S. Unified Assign and Schedule: A New Approach to Scheduling for Clustered Register File Microarchitectures. - Proceedings of the MICRO-31 - The 31th Annual International Symposiumon Microarchitecture, 1998.

Pai V. S., Adve S. Code Transformation to Improve Memory Parallelism. - The Journal of Instruction-Level Parallelism, May 2000.

Pendry A., Fenwick J. B., Norris J. C. Using SUIF as a Front-end Translator for Register Allocation and Instruction Scheduling Research. - In Second SUIF Compiler Workshop, Stanford, CA, August 1997.

Pinter S. Register Allocation with Instruction Scheduling: a New Approach. - Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 248-257, 1993.

Pozzi L. Compilation Techniques for Exploiting Instruction Level Parallelism, a Survey. - Milano, Italy, 1998.

Rajagopalan S., Vachharajani M,. Malik S. Handling Irregular ILP Within Conventional VLIW Schedulers Using Artificial Resource Constraints. - CASES'00, November 17-19, 2000, San Jose, California.

Rao S. IA-64 Code Generation. – Electrical and Computer Engineering, June 2000.

Stallman R. Using and Porting GNU CC. - FSF, Boston, USA.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.citforum.ru/