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

• Новиков, Сергей Викторович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Новиков, Сергей Викторович

Введение.

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 для архитектуры Эльбрусом и играют важную роль для получения высокоэффективного кода для этой вычислительной системы.

Список литературы диссертационного исследования кандидат технических наук Новиков, Сергей Викторович, 2005 год

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