автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Развитие методов глобального планирования программ для архитектур с явно выраженной параллельностью

УДК 004.4'416

На правах рукописи

Новиков Сергей Викторович

РАЗВИТИЕ МЕТОДОВ ГЛОБАЛЬНОГО ПЛАНИРОВАНИЯ ПРОГРАММ ДЛЯ АРХИТЕКТУР С ЯВНО ВЫРАЖЕННОЙ ПАРАЛЛЕЛЬНОСТЬЮ

05.13.11 - Математическое и профаммное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена в ЗАО «МЦСТ»

Научный руководитель

кандидат технических наук Дроздов А. Ю.

Официальные оппоненты: доктор технических

Семенихин С.В.

наук

Ведущая организация

кандидат физико-математических наук

Тарасенко Л.Г.

Институт проблем информатики РАН

Защита состоится «1.6 » декабря 2005 г. в Ц мин, на заседании диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 117218, ГСП-7, г. Москва, Нахимовский проспект, д. 36, корп. 1.

С диссертацией можно ознакомиться в библиотеке Института микропроцессорных вычислительных систем РАН.

Автореферат разослан « 2. » ноября 2005 г.

Ученый секретарь диссертационного совета д.ф.-м.н., профессор II /

Михайлкж М. В.

Общая характеристика работы

Актуальность работы

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

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

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

усложнением логики проверок в аппаратуре при планировании команд, тем самым, обеспечивая совместимость программного обеспечения на ряде поколений микропроцессоров. К недостатку динамического подхода можно отнести необходимость ограничивать сложность алгоритмов планирования, так как повышение сложности ведет к увеличению времени, затрачиваемого на динамическое распараллеливание. Этот недостаток удается преодолеть при статическом подходе, когда распараллеливание инструкций происходит на этапе компиляции программы. Для обозначения процессоров, устройство которых использует принципы динамического подхода, применяется термин суперскалярная архитектура. Для обозначения процессоров, устройс1во которых использует принципы статического подхода, применяется термин EPIC (Explicitly Parallel Instruction Computing) или архитектура с явно выраженной параллельностью на уровне команд.

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

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

Цель диссертационной работы

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

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

• разработка эффективного алгоритма планирования ациклических регионов программы;

• разработка эффективного алгоритма планирования произвольного участка программы;

• разработка методов оценки эффективности планирования;

• разработка механизмов интеграции оптимизирующих преобразований в алгоритмы планирования;

• разработка оптимизирующих преобразований для интеграции в алгоритмы планирования;

• разработка механизма использования аппаратной поддержки спекулятивных вычислений в алгоритмах планирования;

• разработка алгоритмов построения и коррекции зависимостей для произвольного участка программы;

• разработка методов сохранения информации о зависимостях по управлению на эшпе планирования;

• разработка алгоритма построения предикатного выражения для произвольного пути программы;

• разработка алгоритмов коррекции глобального графа потока данных на этапе планирования;

• разработка методов коррекции информации о времени жизни объектов на этапе планирования;

• разработка методов коррекции аналитической информации о циклах на этапе планирования;

• реализация указанных алгоритмов в составе оптимизирующего компилятора для архитектуры Эльбрус-ЗМ.

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

• методы статического планирования программ с точки зрения их эффективности и возможности применения в контексте промышленных оптимизирующих компиляторов;

• оценка влияния методов статического планирования программ на конечную производительность и эффективность результирующего кода.

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

Научная новизна

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

• разработка эффективного алгоритма планирования ациклических областей программы;

• разработка эффективного алюритма планирования произвольного региона программы;

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

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

• разработка алгоритма построения графа зависимостей и методов их коррекции на этапе планирования;

• разработка методов сохранения информации о зависимостях по управлению после преобразования потока управления в поток данных на этапе планирования;

• разработка алгоритма построения предика шого выражения для произвольного пути в программе;

• разработка методов коррекции глобального графа потока данных на этапе планирования;

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

• разработка методов коррекции аналитической информации о зависимостях в циклах на этапе планирования.

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

промышленного оптимизирующего компилятора для архитектуры Эльбрус-ЗМ.

В процессе выполнения диссертационной работы получены следующие практические результаты:

1) Все разработанные алгоритмы реализованы в составе оптимизирующего компилятора для архитектуры Эльбрус-ЗМ.

2) Выявились дальнейшие направления исследований в области развития методов статического планирования программ.

Апробация

Результаты работы докладывались на Международной молодежной научной конференции "XXX Гагаринские чтения" (Москва, 2005 г.), на IX Санкт-Петербургской Международной конференции "Региональная информатика - 2004" (РИ-2004) в 2004 г., XXI научно-технической конференции войсковой части 03425 (Москва, 2003 г.), а также докладывались и обсуждались на семинарах и научно-шхнических совещаниях ЗАО "МЦСТ" и Института микропроцессорных вычислительных сис1ем РАН.

Публикации

По теме диссертации опубликованы 10 печатных работ.

Структура и объем работы

Диссертация состоит из введения, трех пшв и заключения. Диссертация содержит 107 страниц, 32 рисунка, 7 таблиц. Список литературы насчитывает 65 наименования.

Краткое содержание работы

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

Отмечена научная новизна исследования и дана краткая

характеристика

содержания работы и ее результатов.

1

; Анализ и оптимизации на представлении без ;

предикатного кода j

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

Анализ и оптимизации на представлении с j предикатным кодом !

I

I Локальное планирование в рамках |

расширенных скалярных участков !

гггши::

■ Распределение регистров и генерация кода

1..............................................1..........................................'

Рис. 1. Схема оптимизирующей части компилятора

Глава 1 содержит краткий обзор существующих методов статического планирования программ, анализируются их основные недостатки и ограничения, определяются направления для исследования, производится постановка задачи, решению которой посвящена данная диссертационная работа. Кроме jiojo проводится анализ существующих архитектур с явно выраженной параллельностью на уровне команд на примере архитектуры Эльбрус-ЗМ и архитектуры Itanium. Определяются основные аппаратные черты, которые должны быть учтены при

реализации алгоритмов статического планирования. Помимо архитектурных аспектов, в данной главе описаны элементы программного контекста алгоритмов планирования. Рассмотрены вопросы технологии оптимизирующей трансляции и определяется место алгоритмов планирования в схеме оптимизирующего компилятора (рис. 1).

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

В п. 2.1 дано общее описание алгоритма набора гиперблоков. В архитектурах, использующих параллельность на уровне операций, существует целый ряд исполнительных устройств. Методы статического планирования должны использовать доступные вычислительные ресурсы максимально эффективно. Очень часто, в исходных программах бывает недостаточное количество параллельных вычислений в пределах одного линейного участка. Из-за этого вычислительные ресурсы не удается использовать с максимальной загрузкой. Для повышения уровня параллельных вычислений используются техники глобального планирования. Эти техники включают в рассмотрение регионы, состоящие из многих линейных участков. Одним из подходов, который позволяет одновременно планировать операции с разных линейных участков, называется техникой набора гиперблоков. Используя поддержку предикатных вычислений можно преобразовать ациклический регион программы, состоящий из нескольких линейных участков, в один линейный участок. При этом действии будут удалены все внутренние переходы ациклического региона. Процесс перевода безусловного кода в предикатный традиционно называется if-conversion. По сути, if-conversion преобразует зависимости по управлению с операциями переходов в

зависимости по данным с условиями операций. Исходный регион для преобразования if-conversion обладает следующими свойствами:

• регион является ациклическим

• имеется единственный вход

• управление внутри региона задано только условными предложениями

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

Такой регион принято называть гиперблоком. Основная трудность применения преобразования if-conversion состоит в определении участков, для которых перевод в предикатную форму приводит к ускорению их выполнения. Если гиперблок набран неверно, то после преобразования if-conversion время его исполнения может увеличиться. В данной работе предложен метод, позволяющий определять регионы, для которых перевод в предикатную форму эффективен. Это достигается за счет нескольких факторов. Во-первых, одним из новшеств по сравнению с уже разработанными подходами набора гиперблоков, является использование алгоритма планирования для повышения точности оценки эффективности набора. Алгоритм планирования работает по модели архитектуры, и именно результаты планирования определяют принятие решений на каждом шаге алгоритма набора. Во-вторых, важной особенностью предлагаемого подхода можно назвать возможность учета эффекта от оптимизирующих преобразований на предикатном коде в момент набора регионов. После .преобразования потока управления в поток данных появляются возможности для применения целого класса скалярных оптимизаций, которые могут существенно изменить состояние промежуточного представления на момент планирования. Интеграция оптимизирующих преобразований в схему планирования решает проблему

учета этих изменений в момент принятия решений о формировании гиперблоков.

Применение планирования и интеграция оптимизирующих преобразований для оценки эффективности набора гиперблоков стали <

возможны вследствие реализации схемы восстановления представления на каждом шаге алгоритма (рис. 2). *

Ациклический Применение Оценка

участок оптимизаций эффективности

Node :

Z\

Node 2

Node 3

Сохранение

состояния

Node 4

Восстановление

исходного

состояния

Рис. 2. Схема набора гипербчоков с откатами

Реализуется данный подход путем создания копии промежуточного представления со всеми необходимыми структурами данных и поддержание её в согласованном состоянии с исходным преде гавлением на каждом шаге алгоритма. При принятии положительного решения на некотором этапе копия должна быть согласована с оригиналом. При принятии отрицательного решения оригинал восстанавливается по копии. Основная задача в реализации механизма сохранения-восстановления промежуточного представления состоит в минимизации накладных расходов на это действие. Для этой цели в данной работе было обеспечено свойство локальности коррекций в момент принятия решений. Сохранение

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

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

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

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

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

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

В п. 2.2 рассматривается важный для планирования вопрос о построении и поддержании в корректном состоянии графа зависимостей. Планированием операций является назначение порядка их исполнения. Статическим планированием называется планирование операций на этапе трансляции программы. Задача эффективного использования всего многообразия аппаратных механизмов и ресурсов EPIC архитектур решается статическим планированием. В любой программе изначально задан порядок выполнения операций, который может быть сохранен или корректно изменен в процессе компиляции программы. Изменение исходного порядка операций может быть осуществлено в результате анализа операций на возможность их переупорядочивания. Если две операции упорядочены, то есть одна из них не может быть выполнена раньше другой, то говорят, что между операциями есть зависимость. Граф зависимостей представляет собой аналитическую структуру данных, на базе которой работают алгоритмы планирования. Наиболее актуальным вопросом при работе с этой структурой данных является вопрос скорости построения графа зависимостей. Сложность данного алгоритма 0(N*N), где N - число операций исходной цепочки. Такая сложность алгоритма не позволяет его использовать для процедур с большим числом операций, так как существенно замедляет процесс оптимизирующей компиляции. В данной работе предлагается подход, который позволяет в большинстве случаев значительно ускорить построение графа зависимостей. Несмотря на ю, чю в общем случае сложность предлагаемого алгоритма остается 0(N*N), в большинстве пользовательских программ сложность будет определяться как 0(N*K), где К « N.

В п. 2.3 описаны подходы к построению предикатов при преобразовании if-conversion, применяемые для архитектур Эльбрус-ЗМ и Itanium. Разные подходы обусловлены отличиями в системах команд этих архитектур, связанных с поддержкой предикатных вычислений. В архитектуре Эльбрус-ЗМ существуют логические операции над предикатами. Для реализации предикатного выражения используется операция предикатной конкатенации с подавлением дефектноеги: land pi р2 рЗ. Механизм построения предикатных выражений с использованием операции land основан на использовании gated single assignment (GSA) форме представления протраммы, в котором для каждого узла существует описатель пути от непосредственного доминатора в терминах предикатных операций И, а также в терминах инверсии предиката. В архитектуре IA-64 нет логических операций над предикатами. Вместо этою у операций сравнения существует два предикатных результата и введены специальные режимы исполнения операций сравнения, что позволяет использовать алгоритм определения CD-эквивалености узлов управляющего графа для построения предикатных выражений.

П. 2.4 посвящен вопросам использования поддержки спекулятивных вычислений в алгоритме планирования. В £'Р/С-архитектурах существует поддержка спекулятивных вычислений, как по управлению, так и по данным. Спекулятивность по управлению позволяет выполнять без постановки под условие операцию раньше перехода, а спекулятивность по данным позволяет выполнять операцию чтения из памяти раньше, чем выполниться потенциально конфликтующая с операцией чтения операцию записи Оба этих механизма были реализованы на этапе планирования общей техникой спекулятивного переноса с построением компенсирующего кода.

Вопросы коррекции аналитических структур данных на этапе планирования рассмотрены в п. 2.5. К ним относятся

• граф управления

• глобальный граф потока данных

• информация о зависимостях по управлению

На каждом шаге алгоритма планирования происходит преобразование потока управления в поток данных. Исходный ациклический участок преобразуется в один узел. Это преобразование поддерживается как на уровне управляющего графа, так и на уровне отдельно взятой операции. После такого преобразования изменяются свойства глобального графа потока данных, который содержит в себе информацию о доминировании определений над использованиями. Операции из параллельных веток программы оказываются в одном узле, и информация о параллельности вычислений сохраняется в специальной таблице пересечений операций. По этой таблице для двух предикатных операций можно получить информацию о возможности их одновременного исполнения. Три структуры данных тесно взаимосвязаны друг с другом и находятся в согласованном состоянии. Их корректность необходима для последующих фаз оптимизирующей трансляции. Сохранение глобального графа потока данных, а также информации о зависимостях по управлению является важной задачей для возможности применения эффективного алгоритма распределения регистров, который является критическим для производительности вычислительных систем, построенных на базе £Р/С-архитектур.

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

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

• глобальный (на всю процедуру) граф зависимостей

• схема глобального построения предикатных выражений

• сохранение и коррекция при преобразованиях информации о времени жизни объектов

• сохранение информации о зависимостях по управлению при преобразовании потока управления в поток данных

• сохранение в корректном состоянии глобального графа потока данных

• точная коррекция результатов анализа циклов

• все базовые преобразования, позволяющие осуществлять произвольный перенос операций

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

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

• механизм работы с фронтом и перенос операций с построением компенсирующего кода

• использование 1ехники I ist Scheduling при планировании расширенных скалярных участков и планировании операций во фронт

• эвристики по оценке эффективности переноса операций

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

В п. 3.2 описано развитие алгоритмов построения и коррекции графа зависимостей при расширении планируемого региона с ациклического участка до размеров всей процедуры. Проведен эксперимент, аналогичный эксперименту при планировании ациклических регионов. Результаты показывают, что при увеличении количества операций, для которых строится граф зависимостей, увеличивается понижающий коэффициент оценки сложности алгоритма, определяемый формулой 0(N*K), где К = ^результаты эксперимента). Эксперимент показывает, что если процедура содержит порядка сотни операций, то алгоритм построения графа зависимостей будет линейным для нее на реальных задачах. Кроме алгоритма построения графа зависимостей рассматриваются методы коррекции зависимостей при переносе операций.

Важной информацией, используемой в процессе глобального планирования, является знание о времени жизни объектов. Данная проблема рассмотрена в п. 3.3. На основе этой информации может приниматься решение о снятии условия с операции при ее переносе. Эти знания позволяют оценить рост давления на регистры и вовремя ограничить перенос операций, чтобы не допустить возникновения дополнительного кода, который достраивается распределителем регистров в случае нехватки аппаратных ресурсов. Для ускорения коррекции этой информации в данной реализации был задействован метод сохранения информации о времени жизни, который в своей работе предложили Alexandria Nicolau и Steven Novack (Alexandra Nicolau and Steven Novack, Trailblazing: A Hierarchical Approach to Percolation Scheduling. Department of Information and Computer Science University of California, Proceedings of the 1993 International Conference on Parallel processing). Информация о времени жизни сохраняется с привязкой к участкам с одним входом и

одним выходом, которые выделяются в процессе построения дерева структуры программы. Эта структура данных представляет собой дерево, каждый узел которого является участком управляющего графа с одним входом и одним выходом (SESE - single entry single exit). Сохранение таким образом информации о времени жизни объектов позволяет осуществлять перенос операций через SESE регионы без дополнительной коррекции этой информации внутри региона.

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

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

обратных зависимостей, которые препятствуют параллельному ' исполнению операций с разных итераций цикла. Удаляя зависимости

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

пересылками в /ГР/С-архитектурах существует механизм базированных ресурсов. Распределив регистры на них можно удалить операции пересылки.

П. 3.6 посвящен коррекции аналитических структур данных при планировании произвольного региона программы. Значительно усложняются корректоры, как для графа управления, так и для глобального графа потока данных, а так же для информации о зависимостях по управлению. На этапе планирования произвольного региона программы достаточно активно применяются различные преобразования управляющего графа. Среди них можно выделить следующие преобразования:

• удаление узла или дуги

• создание узла или дуги

• копирование узла с перенаправлением на него некоторых входных дуг

• копирование подграфа управляющего графа

Все эти базовые преобразования в той или иной степени используются для таких задач как:

• удаление критических дуг путем вставления на них пустых узлов

• удаление пустых узлов после планирования региона

• дублирование узлов для снятия ограничений на перенос операций (tail duplication)

• удаление узла после объединения его операций с операциями предшествующего узла (merge)

• создание новых узлов при переносе операции перехода из цикла (peeling)

• копирование итерации цикла в момент его раскрутки (unroll)

• удаление базовой итерации цикла после раскрутки

Для коррекции июбального графа потока данных были разработаны алгоритмы для таких преобразований как:

• перенос и планирование одной копии исходной операции

• перенос и планирование нескольких копий исходных операций

• коррекция ОеТ-Ше графа для предикатного аргумента

• дублирование узла

• вынос операции перехода из цикла

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

Еще одним видом аналитической информации, которая корректируется на этапе глобального планирования, является информация от анализа циклов. Эта информация привязана и к операциям, и к циклам (рис. 3).

ГогО = 0; ¡<N¡¡+=2) {

{

А[2*ЩЗ*Л = ...

}

}

а) исходный текст б) индекс операции записи в память

Рис. 3. Представкпие индекса операции обращения в пимять

Index:

const 1 * i + const2 * j

diml:

2 * i

dim 2:

3*j

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

раскрутка циклов.

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

В Заключении приводятся основные результаты диссертационной работы.

Выводы по результатам диссертации

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

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

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

1) Предложен новый метод статического планирования программы в рамках ациклических регионов, позволивший в среднем на 30% улучшить показатели производительности для целочисленных задач пакета 5рес95.

2) Предложен новый метод статического планирования произвольного региона программы, позволивший дополнительно на 7% в среднем улучшить показатели производительности для целочисленных задач пакета 8рес95.

3) Предложены эффективные методы сохранения аналитической информации о программе на этапе статического планирования, которые включают в себя:

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

• новый метод сохранения информации о зависимостях по управлению при преобразовании потока управления в поток данных;

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

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

4) Предложен новый метод построения предикатного выражения для произвольного пути программы, позволивший снять ограничения

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

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

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

Список работ, опубликованных по теме диссертации

1. Дроздов А.Ю., Новиков C.B. Исследование методов преобразования программы в предикатную форму для архитектур с явно выраженной параллельностью // Компьютеры в учебном процессе. № 5. 2005. С. 91-99.

2. Дроздов А.Ю., Новиков C.B., Шилов В.В. Эффекшвный ал гори im преобразования потока управления в поток данных // Информационные технологии. № 2. 2005. Приложение. С. 24-31.

3. Дроздов А.Ю., Новиков C.B. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии. № 3. 2005. С. 45-51.

4. Боханко A.C., Новиков C.B., Шлыков СЛ. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе. № 8. 2005. С. 73-80.

5. Новиков C.B. Развитие методов глобального планирования программ, используемых в современных оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом на уровне команд // Тезисы докладов Международной молодежной научной конференции «XXXI Гагаринские чтения», т. 4. М.: МАТИ, 2005.

6. Дроздов А.Ю., Новиков C.B. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция "Региональная Информатика-2004". Тезисы докладов. СПб.: СПИИ РАН, 2004.

7. Дроздов А.Ю., Новиков C.B. Методы совместного планирования путей программы, предлагаемые для использования в современных оптимизирующих компиляторах // Сборник тезисов докладов XXI научно-технической конференции войсковой части 03425. М.: в/ч 03425,2003.

8. Боханко А. С., Дроздов А. Ю., Новиков С. В., Шлыков С. Л.

Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС PAII, Выпуск N8, 2005, С. 71-77.

9. Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005, С. 78-87.

Ю.Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б. DefUse граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. № 12. 2005. С. 3-14.

Принято к исполнению 01/10/2005 Исполнено 02/11/2005

Заказ № 1175 Тираж- 75 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (095) 975-78-56 (095) 747-64-70 www.autoreferat ru.

»20903

РНБ Русский фонд

2006-4 18487

Введение.

1. Лналш методов планирования для архитектур с явной параллельностью.

1.1. Лналш архитектур с явной параллельностью.

1.2. Статическое планирование операций.

1.2.1. Зависимости по управлению и по данным

1.2.2. Контекст алгоритмов статического планирования

1.2.3. Место статического планирования в схеме оптимизирующей трансляции

1.3. Методы статического планирования.

1.3.1. Планирование по списку

1.3.2. Планирование трассы

1.3.3. Суперблок и Гиперблок

1.3.4. Планирование по дереву доминирования

1.3.5. Конвейеризация циклов

1.3.6. Планирование с учетом задержек между линейными участками

1.3.7. Планирование техникой просачивания

1.3.8. Планирование волнового фронта

1.4. Проблемы и недостатки существующих .методов.

1.5. Постановка задачи.

1.6. Выводы.!.

2. Глобальное планирование в рамках ациклического региона.

2.1. Общее описание алгоритма набора гнперблоков.

2.1.1. Описание схемы огкага

2.1.2. Оценка эффективности одного шага алгоритма

2.1.3. Алгоритм набора гиперблоков

2.1.4. Стратегии набора

2.1.5. Экспериментальные результаты

2.2. Граф зависимостей.

2.2.1. Алгоритм построения зависимостей

2.2.2. Коррекция зависимостей на каждом шаге алгоритма

2.2.3. Минимизация графа зависимостей

2.2.4. Результаты тестирования

2.3. Переход к предикатному представлению - if-conversion.

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

2.3.2. Построение предикатов для архитектуры Itanium

2.4. Использование спекулятивного режима.

2.4.1. Спекулятивность по управлению без построения компенсирующего кода

2.4.2. Спекулятивность по управлению и по данным с построением компенсирующем о кода 2.4.3. Использование спекулятивного режима на )гане планирования

2.5. Оптимизации, включенные в схему планирования.

2.6. Коррекция аналитических структур данных.

2.6.1. Коррекция графа управления

2.6.2. Коррекция глобального графа потока данных

2.6.3. Коррекция информации о зависимостях по управлению

2.7. Экспериментальные результаты.

2.8. Выводы.

3. Глобальное планирование за пределами ациклических регионов.

3.1. Общее описание алгоритма глобального планирования.

3.2. Граф зависимостей.

3.2.1. Алгоритм построения зависимостей

3.2.2. Коррекция зависимостей при переносе операций

3.2.3. Результаты тестирования

3.3. Информация о времени жизни объектов.

3.4. Построение предиката операции.

3.5. Оптимизации, включенные в схему планировании.

3.6. Коррекция аналитических структур данных.

3.6.1. Коррекция графа управления

3.6.2. Коррекция глобального графа потока данных

3.6.3. Коррекция информации о зависимостях по управлению

3.6.4. Коррекция результатов индексного анализа

3.7. Алгоритм глобального планировании.

3.8. Экспериментальные результаты.

3.9. Выводы.".

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

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

В настоящее время в современных микропроцессорах широко используются оба подхода к распараллеливанию вычислений на уровне инструкций. Динамический подход позволяет, не меняя исходные коды программного обеспечения, повышать параллельность за счет усложнением логики проверок в аппаратуре при планировании команд, тем самым, обеспечивая совместимость программного обеспечения на ряде поколений микропроцессоров. К недостатку динамического подхода можно отнести необходимость ограничивать сложность алгоритмов планирования, так как повышение сложности ведет к увеличению времени, затрачиваемого на динамическое распараллеливание. Этот недостаток удается преодолеть при статическом подходе, когда распараллеливание инструкций происходит на этапе компиляции программы. Для обозначения процессоров, устройство которых использует принципы динамического подхода, применяется термин суперскалярная архитектура. Для обозначения процессоров, устройство которых использует принципы статического подхода, применяется термин EPIC (Explicitly Parallel Instruction Computing) или архитектура с явно выраженной параллельностью на уровне команд.

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

Цель диссертационной раоогм

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

• исследование современного уровня развития методов статического планирования программ и возможностей их использования в промышленных о птим из и ру ю тих ко м пил ято pax;

• разработка эффективного алгоритма планирования ациклических регионов программы;

• разработка эффективного алгоритма планирования произвольного участка программы;

• разработка методов оценки эффективности планирования;

• разработка механизмов интеграции оптимизирующих преобразований в алгоритмы планирования;

• разработка механизма использования аппаратной поддержки спекулятивных вычислений в алгоритмах планирования;

• разработка оптимизирующих преобразований для интеграции в алгоритмы планирования;

• разработка алгоритмов построения и коррекции зависимостей для произвольного участка программы;

• разработка методов сохранения информации о зависимостях по управлению на этапе планирования;

• разработка алгоритма построения предикатного выражения для произвольного пути программы;

• разработка алгоритмов коррекции глобального графа потока данных на этапе планирования;

• разработка методов коррекции информации о времени жизни объектов на этапе планирования;

• разработка методов коррекции аналитической информации о циклах на этапе планирования;

• реализация указанных алгоритмов в составе оптимизирующего компилятора для архитектуры Эльбрус-ЗМ.

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

• методы статического планирования программ с точки зрения их эффективности и возможности применения в контексте промышленных оптимизирующих компиляторов;

• оценка влияния методов статического планирования программ на конечную производительность и эффективность результирующего кода.

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов, теории диофантовых уравнений и неравенств, математической логики. Путем измерений ключевых параметров, оценивалась эффективность предложенных методов. Для проведения замеров использовался инструментальный комплекс в составе оптимизирующего компилятора и нотактной мололи архитектуры ')льбруе-ЗМ. камеры производились на пакете задач Ярес')5.

Научная шжиша

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

• разработка эффективного алгоритма планирования ациклических областей программы;

• разработка ■эффективного алгоритма планирования произвольного региона программы;

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

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

• разработка алгоритма построения графа зависимостей и методов их коррекций на этапе планирования;

• разработка методов сохранения информации о зависимостях по управлению после преобразования потока управления в поток данных на этапе планирования;

• разработка алгоритма построения предикатного выражения для произвольного пути в программе;

• разработка методов коррекции глобального графа потока данных на этапе планирования;

• разработка метода использования аппаратной поддержки спекулятивных вычислений в атгоритмах планирования;

• разработка методов коррекции анатитической информации о зависимостях в циклам на этапе планирования.

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

В процессе выполнения диссертационной работы получены следующие практические результаты:

1) Все разработанные алгоритмы реатизованы в составе оптимизирующего компилятора для архитектуры Эльбрусом.

2) Выявились датьнейшие направления исследований в области развития методов статического планирования программ.

Апробация

Результаты работы докладывались на Международной молодежной научи 011 конференции "XXX Гагарине кие чтения" (Москва, 2005 г.), на ГХ Санкт-Петербургской! Международной конференции "Регионатьная информатика - 2004" (141-2004) в 2004 Г--XXI научно-технической конференции войсковой части 03425 (Москва, 2003 г.), также докладыватнсь и обсуждатись на семинарах и научно-технических совещаниях ЗАО "МЦСТ" и Института микропроцессорных вычислительных систем РАН.

Публикации

По геме диссертации опубликованы 10 печатных работ:

• Дротов А.Ю., Новиков C.B. Исследование методов преобразования программы в предикатную форму для архитектур с явно выраженной параллельностью // Компьютеры в учебном процессе. № 5. 2005. С. 91-99.

• Дроздов АЛО., Новиков C.B., Шилов В.В. Эффективный алгоритм преобразования потока управления в поток данных // Информационные технологии. № 2. 2005. Приложение. С. 24-31.

• Дроздов А.Ю., Новиков C.B. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии. № 3. 2005. С. 45-51.

• Боханко A.C., Новиков C.B., Шлыков СЛ. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе. № 8. 2005, С. 73-80.

• Новиков C.B. Развитие методов глобального планирования программ, используемых в современных оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом на уровне команд // Тезисы докладов Международной молодежной научной конференции «XXXI Гагаринские чтения», т. 4. М.: МАТИ, 2005.

• Дроздов А.Ю., Новиков C.B. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция "Региональная Информагика-2004". Тезисы докладов. - СПб.: СПИИ РАИ, 2004.

• Дроздов АЛО., Новиков C.B. Методы совместного планирования путей программы, предлагаемые для использования в современных оптимизирующих компиляторах // Сборник тезисов докладов XXI научно-технической конференции войсковой части 03425. М.: в/ч 03425, 2003.

• Боханко А. С., Дроздов А. Ю., Новиков С. В., Шлыков С. JI. Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005, С. 71-77.

• Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазии А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005, С. 78-87.

• Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазнн А. Б. Def-Use граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. № 12. 2005. С. 3-14.

Структура и обьеч работы

Диссертация состоит из введения, трех глав и заключения. Диссертация

3.9 Выводы

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

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

2) Предложен способ интеграции результатов ациклического планирования в алгоритм глобального планирования.

3) Предложен быстрый алгоритм построения графа зависимостей на произвольный регион программы и собрана статистика, подтверждающая возможность его применения. Рассмотрены вопросы коррекции графа зависимостей на этапе планирования программы.

4) Предложен метод построения предикатного выражения для произвольного пути программы.

5) Предложен метод сохранения информации о зависимостях но управлению при преобразовании поIока управления в иоюк данных.

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

7) Рассмотрен вопрос использовании информации о времени жизни объектов в процессе планирования. Рассмотрен механизм ускорения коррекции згой информации при переносе операций.

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

Заключение

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

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

1) Предложен новый метод статического планирования программы в рамках ациклических регионов, позволивший в среднем на 30% улучшить показатели производительности для целочисленных задач пакета Брес95.

2) Предложен новый метод статического планирования произвольного региона программы, позволивший дополнительно на 7% в среднем улучшить показатели производительности для целочисленных задач пакета Брес95.

3) Предложены эффективные методы сохранения аналитической информации о программе на этапе статического планирования, которые включают в себя:

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

• новый метод сохранения информации о зависимостях по управлению при преобразовании потока управления в поток данных;

• алгоритмы коррекции глобального графа потока данных на этапе глобального планирования, сохраняющие важну ю для оптимизиру ющих фаз структуру данных, на базе которой удается существенно повысить качество одного из ключевых алгоритмов оптимизирующей трансляции программ для ЕРЮ архитектур - алгоритма распределения регистров;

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

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

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

Реализация и отладка всего программного комплекса, описанного в данной работе, велась на протяжении 4 лег. Объем работы составил более 200 тысяч строк.

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

1. Boris Babayan. E2K Technology and Implementation. // in Proceedings of the Euro-Par 2000 Parallel Processing: 6th International. - Volume 1900 / 2000. -January, 2000.-P. 18-21.

2. M. Кузьминский. Отечественные микропроцессоры: Elbrus E2K. // Открытые системы, № 05-06, 1999. С. 8-13.

3. К. Dieffendorf. The Russians Are Coming. Supercomputer Maker Elbrus Seeks to Join X86/IA-64 Melee // Microprocessor Report, V.13, №.2. February 15, 1999. -P. 1-7.7. http://open.spechench.oru/cpu95

4. Intel Itanium 2 Processor Reference Manual for Software Development and Optimization, Document Number: 251110-001, June 2002. 179 p.

5. Y. N. Srikant, P. Shankar, "The compiler design handbook: optimizations and machine code generation", CRC PRESS, Boca Raton, 2003.

6. В. Ю. Волконский, "Оптимизирующие компиляторы для архитектуры с явным параллелизмом команд и аппаратной поддержкой двоичной совместимости". Информационные технологии и вычислительные системы, №3, 2004.

7. Joseph A. Fisher and John J. O'Donnel. VLIW Machines: Multiprocessors We Can Actually Program // CompCon 84'Proceedings, IEEE. February ,1984. - P. 299-305.

8. John R. Ellis. Bulldog: A Compiler for VLIW Architectures. Cambridge: MIT Press, 1986. -320 p.

9. В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение // Санкт-Петербург: «БХВ-Пегербург», 2003.

10. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools// Addison-Wesley, Reading, 1986.

11. Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs and Koen G. Langendoen. Modern Compiler Design // by John Wiley & Sons,Ltd, 2000.

12. Randy Allen, Ken Kennedy. Optimizing Compilers for Modern Architectures // by Academic Press, 2002

13. Steven S. Muchnick. Advanced Compiler Design and Implementation // Morgan Kauftman, San Francisco, 1997.

14. Johnson, Richard Craig. Efficient Program Analysis Using Dependence Flow Graphs Ph.D. dissertation // Cornell University. August, 1994.

15. Miling Girkar, Constantine D.Polychronopoulos. Extracting Task-Level Parallelism // ACM, July 1995.

16. Alexandru Nicolau and Steven Novack. Trailblazing: A Hierarchical Approach to Percolation Scheduling// Department of Information and Computer Science University of California, Proceedings of the 1993 International Conference on Parallel processing.

17. Vugranam C. Sreedhar, Yong-fong Lee, Guang R.Gao. DJ-Graphs and Their Applications to Flovvgraph Analyses // AC APS Tchnical Memo 70, May 11, 1994.

18. Johnson, Richard Craig. Efficient Program Analysis Using Dependence Flow-Graphs Ph.D. dissertation// Cornell University, August, 1994.

19. Pend Tu, David Padua. Efficient Building and Placing of Gating Functions Center for Supercomputing Research and Development // University of Illinois at Urbana-Champaingn, 1995.

20. Joseph A. Fisher. Trace Scheduling: A technique for global microcode compaction // Transactions on Computers, IEEE. -V. C-30. July, 1981. - P. 478-490.

21. S. A. Mahlke, D. C. Lin, YV. Y. Chen, R. E. Hank, and R. A. Bringmann. Effective Compiler Support for Predicated Execution Using the Hyperblock. // in Proceedings of the 25th International Symposium on Microarchitecture. December, 1992. - P. 45-54.

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

23. VV. A. Havanki, S. Banerjia, and Т. M. Conte. Treegion scheduling for wide-issue processors // Proceedings of the 4th International Symposium on High-Performance Computer Architecture (HPCA-4), February 1998.

24. A. Nicolau. Uniform parallelism exploitation in ordinary programs // In ICPP, 1985.

25. Santosh G. Abraham, Vinod Kathail, Brian L. Deitrich. Meld Scheduling: Relaxing Scheduling Condtraints across Region Boundaries // Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, pp. 308-321, 1996

26. B. R. Rau. Iterative modulo scheduling: An algorithm for software pipelining loops // In Proceedings of the 27th International Symposium on Microarchitecture, pp. 63-74, December 1994.

27. B. R. Rau and J. A. Fisher. Instruction-level parallel processing: History, overview, and perspective // The Journal of Supercomputing, 7(l):9-50, January 1993.

28. Дроздов А.Ю., Стеианенков A.M. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10, 2004 г.

29. Jay Bharadwaj, Kishore Menezes, Chris McKinsey. Wavefront scheduling: path based data representation and scheduling of subgraphs // Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, pp. 262-271, 1999

30. Joseph С. H. Park; Mike Schlansker. On Predicated Execution // Software and System Laboratory HPL-91-58, May, 1991.

31. Pend Tu, David Padua. Efficient Building and Placing of Gating Functions // Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaingn, 1995.

32. Дроздов А. Ю., Новиков С. В., Шилов В. В. Эффективный алгоритм преобразования потока управления в поток данных // Информационные технологии. № 2. 2005. Приложение. С. 24-31.

33. Дроздов А. Ю., Новиков С. В. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии. № 3. 2005.

34. Richard Johnson and Michael Schlansker. Analysis Techniques for Predicated Code// In Proc. Of the 29th Annual Int'l Symp. On Microarchitecture, December 1996.

35. Fohn VV. Sias, Wcn-mei YV. IIwu, David I. August. Accurate and Efficient Predicate Analysis with Binary Decision Diagrams // Proceedings of the 22rd Annual ACM/IEEE Internationsl Symposium on Microarchitecture, December 2000.

36. John Wollenburg. Condition awareness support for predicate analysis optimization // University of Illinois, 1997.

37. R.E. Bryant. Symbolic Boolean manipulation with ordered binary decision diagrams // Technical Report CMU-CS-92-160, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, October 1992.

38. Волконский В. IO., Окуиев С. К. Оптимизации критического пути на предикатном представлении программы // Информационные технологии. № 9. 2003. С. 2-13.

39. Babaian, S. К. Okunev, V. Y. Volkonsky. Critical path optimization unzipping: United States Patent 6,564,372 // B. A. AppL No.: 504630; Filed: February 15, 2000; Pub.: May 13, 2003. 4 p.

40. В. A. Bahaian, S. К. Okunev, V. Y. Volkonsky. Method for removing dependent store-load pair from critical path: United States Patent 6,516,463 // Appl. No.: 771482; Filed: January 25, 2001; Pub.: February 4, 2003. 6 p.

41. B. A. Bahaian, S. K. Okunev, V. Y. Volkonsky. Critical path optimization -optimizing branch operation insertion: United States Patent 6,526,573 // Appl. No.: 505653; Filed: February 17, 2000; Pub.: February 25, 2003. 9 p.

42. Боханко Л.С., Дроздов А.Ю., Корпев P.M. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004.

43. Боханко А.С., Дроздов А.Ю. Оптимизация "Расширенное удаление излишних операций чтения из памяти" // В трудах Международной молодежной научной конференции «XXX Гагаринские чтения», Москва, 2004.

44. P. P. Chang, S. A. Mahlke and YV. VV. Hwu. Using profile information to assist classic compiler code optimizations // Software Practice and Experience, V. 21, №12. 1991. P. 1301-1321.

45. Thomas Ball and James R. Larus. Branch Prediction For Free// SIGPLAN Notices, V. 28 № 6. June 1993. P. 300-313.

46. Youfeng VVu and James R. Larus. Static Branch Frequency and Program Profile Analysis // International Symposium on Microarchitecture (MICRO-27). 1994. P. 1-11.

47. Волконский В. IO., Масленников Д. M., Pobiiiickiiu Е. В. Развитие метода статического предсказания профильной информации // Высокопроизводительные вычислительные системы и микропроцессоры. Выпуск 2. Сб. научных трудов ИМВС РАН. Москва, 2001. С. 37-51.

48. Thomas Lengauer, Robert Tarjan. A Fast Algorithm for Finding Dominators in a Flowgraph // ACM TOP LAS, Vol. 1, No. 1, July 1979, pp. 121-141.

49. Bilardi G., Pingali K. The Static Single Assignment Form and its Computation // Cornell University Technical Report, July, 1999.

50. А. С. Боханко, С. В. Новиков, С. J1. Шлыков. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе. № 8. 2005, С. 73-80.

51. Дроздов А. ГО., Новиков С. В., Боханко А. С., Галазнн А. Б. Def-U.se граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. № 12. 2005. С. 3-14.

52. С п и со к и л л ioc r pa ц и ii

53. Рис. 1. Структура широкой команды ')льбрус-ЗМ Стр. К)

54. Рис. 2. Структура свя жи IA-64 Стр. 10

55. Рис. 3. Способы реализации зависимостей Сгр. 15

56. Рис. 4. Схема оптимизирующей части компилятора Стр.18

57. Рис. 5. Планирование операций в трассе с боковым входом Стр. 20

58. Рис. 6. Формирование суперблока Стр.21

59. Рис. 7. Формирование деревьев на управляющем графе С гр. 23

60. Рис. 8. Пример конвейеризованного цикла архитекту ры IA-64 Стр. 24

61. Рис. 9. Базовые преобразования Percolation Scheduling Сгр. 26

62. Рис. 10. Продвижение фронта сверху вниз Стр. 28

63. Рис. И. Пример гиперблока и РСУ Стр. 32

64. Рис. 12. Схема набора гиперблоков с откатами Стр. 33

65. Рис. 13. Результаты профилирования и планирования Стр. 34

66. Рис. 14. Ресурсные классы Стр.41

67. Рис. 15. М и нимизация зав и с имоетей Стр. 43

68. Рис. 16. Построение предикатов двумя методами Стр. 46

69. Рис. 17. Спекулятивность с построением компенсирующего кода Сгр. 48

70. Рис. 18. Пример перевода программы в SSA-форму Стр. 51

71. Рис. 19. Def-Use граф Сгр. 52

72. Рис. 20. Битовый вектор Стр. 54

73. Рис.21. Таблица пересечений по предикатам Стр. 55

74. Рис. 22. Применение преобразования if-con version Сгр. 57

75. Рис. 23. Свойство достижимости для операций из разных циклов Стр. 61

76. Рис. 24. Перенос операции Сгр. 62

77. Рис. 25. Перепое операции с коррекцией минимизированного графа Сгр. 63зависимостей

78. Рис. 26. Управляющий граф с SESE регионами Стр. 65

79. Рис. 27. Дерево структуры программы С тр. 66

80. Рис. 28. Перепое операции через SESH участок Стр. 67

81. Рис. 29. Перенос операции Стр. 80

82. Рис. 30. Перепое операции по обратной дуге Стр. 82

83. Рис. 31. Дублирование узла Сгр. 85

84. Рис. 32. Представление индекса операции обращения в намять Сгр. 86