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

• Филиппов, Александр Николаевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Филиппов, Александр Николаевич

Введение.

1. Методы нумерации значений как основа для удаления избыточных вычислений.

1.1. Основные понятия и определения.

1.1.1 Структура оптимизирующего компилятора и промежуточное представление.

1.1.2 Граф управления.

1.1.3 Форма со статически единственным присваиванием.

1.1.4 Глобальный граф определений и использований.

1.2. Пессимистический подход к нумерации значений (Hash Based Value Numbering).

1.2.1 Нумерация значений в пределах линейного участка.

1.2.2 Нумерация значений на произвольном ациклическом участке.

1.2.3 Способы усиления нумерации значений при пессимистическом подходе.

1.3. Оптимистический подход к нумерации значений (Value Partitioning).

1.4. Универсальный алгоритм нумерации значений (SCC Based Value Numbering).

1.4.1 Алгоритм Тарьяна поиска сильно связанных компонент.

1.4.2 Нумерация значений на сильно связанной компоненте.

1.4.3 Универсальный алгоритм нумерации значений для всей процедуры.;.

1.5. Недостатки существующих методов.

1.6. Выводы.

2. Развитие методов нумерации значений и использование результатов анализа в платформо-независимых оптимизациях.

2.1. Развитие методов нумерации значений.

2.1.1. Нумерация значений для операций обращения к памяти.

2.1.1.1 Нумерация значений для операций с объектами типа «скаляр».

2.1.1.2 Нумерация значений для операций с другими типами объектов.

2.1.1.3 Нумерация значений для операций, объект которых установить не удалось.

2.1.1.4 Алгоритмы построения доминирующего фронта конфликтующих записей.

2.1.1.5 Результаты экспериментов.

2.1.2. Применения техники ре-форм при нумерации значений.

2.1.3. Битовый подход к описанию константных свойств операций.

2.1.3.1 Использование векторов известных битов в нумерации значений.

2.1.3.2 Вычисление векторов известных битов для различных операций.

2.2. Использование результатов нумерации значений в платформо-независимых оптимизациях.

2.2.1. Глобальное распространение копий.

2.2.2 Глобальный сбор общих подвыражений.

2.2.3. Удаление частичных избыточностей.

2.2.4. Оптимизация на основе вычисления векторов значащих битов(Ькор^.

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

2.4. Выводы.

3. Удаление избыточностей для архитектур с явно выраженной параллельностью.

3.1. Использование предикатности для преобразования потока управления в поток данныхОГ-сопуешоп).

3.2. Удаление избыточностей на предикатном коде.

3.2.1 Упрощение предикатных выражений.

3.2.2 Удаление избыточных операций на предикатном коде.

3.3. Балансировка ассоциативных деревьев.

3.3.1. Граф зависимостей, время раннего запуска и критический путь.

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

3.4. Повышение эффективности аппаратной конвейеризации циклов.

3.4.1 Сокращение длин рекуррентностей при помощи балансировки.

3.4.2 Уменьшение ресурсного размера цикла с помощью комбинирования операций.

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

3.6. Выводы.

4. Удаление межпроцедурных избыточностей.

4.1. Межпроцедурные избыточности. Подстановка тела функции в точку вызова (inline) как метод их устранения.

4.2. Межпроцедурная нумерация значений и использование ее результатов в инлайн-подстановках.

4.2.1 Промежуточное представление EIR.

4.2.2. Метод внутрипроцедурной нумерации значений на промежуточном представлении EIR.

4.2.3. Межпроцедурный обход. Передача параметров и возврат значений. Частичная трансферная функция.

4.2.4. Использование результатов межпроцедурной нумерации значений при подстановке тела функции в место вызова.

4.3. Использование профиля значений в инлайн-подстановках.

4.3.1. Профилирование значений и специализация кода.

4.3.2. Профилирование адресов операций вызова по косвенности.

4.3.3. Специализированная подстановка тела функции в место вызова на основе профиля значений.

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

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Методы удаления избыточностей на этапе компиляции программ»

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

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

Проблема наличия избыточностей приобретает особенную актуальность применительно к архитектурам, рассчитанным на достижение высших показателей производительности. Их аппаратные особенности приводят к появлению специфических видов избыточностей, которые не могут быть удалены общими методами. В этом ряду следует выделить архитектуры, использующие статический подход к распараллеливанию на уровне инструкций (EPIC - Explicitly Parallel Instruction Computing), к которым относится архитектура отечественных микропроцессоров серии «Эльбрус» [9], предназначенных для разработки крупномасштабных иформационно-вычислительных систем стратегического значения. Ключевой задачей компилятора в данном случае является нахождение максимального параллелизма программы на уровне операций, поэтому основным видом избыточностей по праву считаются вычисления, препятствующие эффективному статическому распараллеливанию. Существенно также, что в этих архитектурах используется аппаратная поддержка предикатных вычислений и конвейеризации циклов, которая вызывает появление дополнительных избыточностей. Эти факторы не позволяют полноценно использовать преимущества ЕР1С-архитектуры, поэтому развитие методов их устранения представляется актуальным.

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

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

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

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

• реализовать предложенные алгоритмы и методы в составе оптимизирующего компилятора для архитектуры «Эльбрус».

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

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

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

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

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов, теории алгоритмов и математической логики. Эффективность предложенных в работе алгоритмов и методов оценивалась путем замера времени исполнения программ на вычислительном комплексе с микропроцессором «Эльбрус». Замеры производились на реальных задачах из пакетов SPEC CPU2000 и SPEC CPU95 [26], а таюке на функциях, входящих в состав высокопроизводительной библиотеки векторных вычислений для архитектуры «Эльбрус».

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

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

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

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

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

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

Практическая ценность работы состоит в создании новых и усовершенствовании известных методов оптимизации программ, а также в существенном повышении информативности аналитических компонентов компилятора. Все представленные в диссертационной работе методы реализованы в составе оптимизирующего компилятора с языков высокого уровня Си, Си++, Фортран для микропроцессора «Эльбрус». Кроме того, часть из них, не зависящая от целевой платформы, была реализована в составе оптимизирующего компилятора для микропроцессора Sparc. Эффективность предложенных методов подтверждена замерами производительности на пакетах задач SPEC CPU95 и SPEC CPU2000 и на функциях, входящих в состав высокопроизводительной библиотеки векторных вычислений для архитектуры «Эльбрус».

Апробация.

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

• на XXXII Международной молодежной научной конференции «Гагаринские чтения» (Москва, МАТИ, 2006 г.);

• на XXIII научно-технической конференции «Направления развития и применения перспективных вычислительных средств и новых информационных технологий в ВВТ РКО» (Москва, в/ч 03425, 2007г.);

• на XXXIII Международной молодежной научной конференции «Гагаринские чтения» (Москва, МАТИ, 2007 г.);

• на 51-й научной конференции МФТИ (2008г.);

• на XXXV Международной молодежной научной конференции «Гагаринские чтения» (Москва, МАТИ, 2009 г.);

• на семинарах ЗАО «МЦСТ» и ОАО «ИНЭУМ».

Публикации.

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

• Филиппов А.Н., Шлыков CJL Удаление частичных избыточностей // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск №9, 2006, С. 49-57

• Филиппов А.Н. Метод нумерации значений и использование его результатов в оптимизациях программ// Информационные технологии, №4 2009, С. 43-49

• Филиппов А.Н. Вычисление диапазонов бит для арифметических и логических выражений" // Научные труды XXXII Международной молодежной научной конференции « Гагаринские чтения», т. 6. М. : МАТИ, 2006, С. 185 -186

• Филиппов А.Н. Метод нумерации значений и его использование в оптимизациях программ // Научные труды XXXIII Международной молодежной научной конференции « Гагаринские чтения», т. 6. М. : МАТИ, 2007, С. 262-263

• Филиппов А.Н. Метод нумерации значений для операций обращения к памяти // Труды 51-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» Часть I. Радиотехника и кибернетика. — М.: МФТИ, 2008. С. 58-60

• Филиппов А.Н. Условная подстановка тела процедуры в место вызова на основе профильной информации // Научные труды XXXV Международной молодежной научной конференции « Гагаринские чтения», т. 4. М. : МАТИ, 2009, С. 166-167

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

Диссертация состоит из введения, четырех глав и заключения. Список литературы составляет 67 наименований. Объем диссертации составляет 161 страницу текста. Диссертация содержит 57 рисунков и 3 таблицы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Филиппов, Александр Николаевич

Основные результаты данной главы приведены ниже

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

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

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

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

Заключение

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

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

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

2. Разработан усиленный метод нумерации значений, включающий в себя анализ обращений к памяти, использование PS-форм и сбор информации о константных свойствах операций; за счет этого был получен прирост производительности до 28,5% и 6% на тестах пакетов SPEC CPU2000 и SPEC CPU95, исполненных на микропроцессоре с архитектурой «Эльбрус»; кроме того, установлена применимость метода к другим архитектурам - при исполнении тестов пакета SPEC CPU95 микропроцессором архитектуры Sparc достигнуто ускорение до 6%.

3. Предложен метод оптимизации программ на основе вычисления векторов значащих битов, который позволил достичь ускорения до 2,7% на задачах пакета SPEC CINT2000 и до 6,9% на задачах пакета SPEC CPU95 (архитектура «Эльбрус»); метод также продемонстрировал эффективность для микропроцессора Sparc (ускорение до 2,5% на пакете SPEC CPU95).

Перечисленные далее методы разработаны применительно к EPIC-архитектурам. Их эффективность экспериментально установлена в процессе замеров производительности для микропроцессора «Эльбрус».

4. Предложен метод удаления избыточностей и упрощения предикатных выражений на предикатной форме промежуточного представления, который позволил получить прирост производительности до 7% на тестах пакета SPEC CPU2000 и до 7,3% на тестах пакета SPEC CPU95.

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

6. Предложен метод построения комбинированных операций в контексте аппарат-но-конвейеризованных циклов, который позволил достичь ускорения до 6% на тестах пакета SPEC CPU95 и до 98% на функциях, входящих в состав высокопроизводительной библиотеки векторных вычислений для архитектуры «Эльбрус».

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

8. Предложен метод специализированной подстановки тела функции в точку вызова на основе профиля значений, который позволил получить прирост производительности до 14,5% на задачах, содержащих неявные вызовы.

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

Список литературы диссертационного исследования кандидат технических наук Филиппов, Александр Николаевич, 2009 год

1. Ахо, Альфред В., Лам, Моника С., Сети, Рави, Ульман, Джеффри Д. Компиляторы: принципы, технологии, инструмнтарий, 2-е изд. : Пер. с англ. М. : ООО "И.Д. Вильяме", 2008. - 1184 с.

2. В.Ю. Волконский, В.Г. Тихонов, Е.Г. Мареев. Семантические конверторы в составе компиляторов.// Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N2,2001, С. 21-37.

3. ЗАО МЦСТ. Официальный сайт http://mcst.ru

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

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

6. К. 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. Huck J., Morriss D., Ross J., Knies A., Mulder H., Zahir R. Introducing The IA-64 Architecture // IEEE MICRO, №5, 2000, pp. 12-22

8. Triebel W. Itanium architecture for software developers // Intel Press, 2000

9. В.Ю. Волконский, А.К.Ким. Развитие идей параллелизма в архитектуре вычислительных комплексов серии «Эльбрус»// Четвертая Международная конференция «Параллельные вычисления и задачи управления» РАСО 2008, Институт проблем управления РАН

10. Steven S. Muchnick, "Advanced Compiler Design and Implementation", Morgan Kauffman, San Francisco, 1997

11. Bilardi G, Pingali K. The Static Single Assignment Form and its Computation Cornell University Technical Report

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

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

14. Particia C.Goldberg. A comparison of certain optimization techniques. In Rustin, editor, Design and Optimization of Compilers, 31-50, Prentice-Hall, 1972.

15. John Cocke, Jacob T. Schwartz. Programming languages and their compilers: Preliminary notes. Teclmical report, Courant Institute of Mathematical Sciences, New York University, 1970

16. Loren Taylor Simpson, "Value-Driven Redundancy Elimination", Ph.D. Thesis, Rise University, Houston, Texas, 1996

17. Bowen Alpern, Mark N.Wegman and F.Kenneth Zadeck. Detecting equality of variables in programs. In Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pages 1-11, San Diego,California, January 1988

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

19. Robert E.Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing 1(2): 146-160, June 1972.

20. Rastislav Bodik, Rajiv Gupta, Mary Lou Soffa, "Complete Removal of Redundant Expressions", Dept. of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260, 1998.

21. John Cocke. Global common subexpression elimination. SIGPLAN Notices, 5(7):20-24, July 197. Proceedings of a Symposium on Compiler Optimization.

22. Robert Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu and Fred Chow, "Partial Redundancy Elimination in SSA Form ", ACM Transactions on Programming Languages and Systems, Vol. 21, No. 3, May 1999.

23. Preston Briggs, Keith D. Cooper, "Effective Partial Redundancy Elimination", Department of Computer Science, Rice University, Houston, Texas. 1994

24. Филиппов A.H., Шлыков С.JI. Удаление частичных избыточностей.// Высокопроизводительные вычислительные системы и микропроцессоры, №9 2006

25. Standart Perfomance Evaluation Corporation. The Spec Benchmark Suites. CPUintensive benchmark suite. Electronic resource. 1995-2000. http://www.spec.org/cpu

26. The SPARC Architecture Manual. Version 8/Version9. Electronic resource. http://www.sparc.org

27. R. B. Garner. "SPARC: The Scalable Processor Architecture", SunTechnology, vol. 1, no. 3, Summer, 1988, and M. Hall and J. Barry (eds.), TheSun Technology Papers, Springer-Verlag, 1990, pp. 75-99

28. Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23 Annual ACM Symposium on Principles of Programming Languages, 1996

29. Ramalingam G. Identifying loops in almost linear time // ACM Transactions on Programming Languages and Systems, Volume 21, № 2,1999, pp. 175-188

30. Касинский А.И. "Вычисление диапазонов бит для арифметических и логических выражений", Высокопроизводительные вычислительные системы и микропроцессоры, №2 2001

31. А.Ю. Дроздов, А.В. Кан. Анализ межпроцедурная нумерация значений. // Компьютеры в учебном процессе, № 6, 2005

32. Sreedhar, Vugranam С. and Gao, Guang R. A linear time alorithm for placing (p-nodes // Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, California, January 1995. Pp. 62-73

33. Sreedhar, Vugranam C., Lee, Yong-fong, Gao, Guang R. DJ-Graphs and Their Applications to Flowgraph Analysis ACAPS Technical Memo 70, May 11, 1994

34. Wilson, Robert Paul. Efficient, Context-Sensitive Pointer Analysis For С Programs. Ph.D. Thesis, Stanford University, 1997

35. Brian R. Murphy and Monica S. Lam. "Program Analysis with Partial Transfer Functions". Computer Systems Laboratory, Stanford University, 2000.

36. Laure J. Hendren, Marian Emami, Rakesh Chiya, Clark Verbrugge. "A Practical Context-Sensitizes Inter-procedural Analysis Framework For С Compilers". ACAPS Technical Memo 72, 24 July 1993.

37. M. Hind and A. Pioli. "Assessing the effects of flow-sensitivity on pointer alias analyses". Lecture Notes in Computer Science, 1503, pages 57-81. Springer-Yerlag, 1998.

38. Mooly Sagiv, Thomas Preps, Susan Horwotz "Precise Dataflow Analysis with Applications Constant Propagation". TAPSOFT 1995. pages 651-665.

39. Дроздов А. Ю., Сыркин А. Г. Методы контекстного межпроцедурного распространения свойств значений переменных программы // Информационные технологии, Приложение № 2, Февраль 2005 г.

40. Сыркин А.Г. Развитие методов межпроцедурных оптимизаций, применяемых в современных оптимизирующих компиляторах // Компьютеры в учебном процессе, №7, июль 2005

41. M. S. Schlansker, B. R. Rau. EPIC: An Architecture for Instruction-Level Parallel Processors: Technical Report HPL-1999-111. Compiler and Architecture Research Hewlett-Packard Laboratories, Palo Alto, February 2000.

42. NArch Architecture Specification. Draft D 1.2.1. Moscow Center of SPARCtechnol-ogy, 1996.

43. Волконский В.Ю., Окунев C.K. Предикатное представление как основа оптимизации программ для архитектур с явно выраженной параллельностью // Информационные технологии, № 4,2003. С. 36-44.

44. August D.I., Wen-mei W. Hwu, and Mahlke S.A. A Framework for Balancing Control Flow and Predication // Proceedings of the 30th annual IEEE/ACM International Symposium on Microarchitecture. December, 1997. P. 92-103.

45. Park J.C.H.; Schlansker M. On Predicated Execution. Software and System Laboratory HPL-91-58, May, 1991.

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

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

48. J.R. Allen, K. Kennedy, C. Porterfield, J. Warren. Conversion of control dependences to data dependences, Conf. Record of POPL-IO, 1983.

49. Новиков C.B. Развитие методов глобального планирования для архитектур с явно выраженной параллельностью. Дис. канд. тех. наук: 05.13.11, ЗАО «МЦСТ», М.-2005

50. 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.

51. В.Ю.Волконский, В.Д.Гимпельсон, Д.М.Масленников "Быстрый алгоритм минимизации высоты графа зависимостей", Информационные технологии и вычислительные системы, №3, 2004.

52. Chaitin G., Auslander М., Chandra A., Cocke J., Hopkins M., Markstein P. Register allocation via coloring // Computer Languages, №1, 1981, pp. 47-57

53. Chaitin G. Register allocation and spilling via graph coloring // Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction, SIGPLAN Notices, №6, 1982, pp. 98-105

54. А.Ю.Дроздов, А.М.Степаненков "Технология оптимизации циклов для архитектур с аппаратной поддержкой конвейеризации", Информационные технологии и вычислительные системы, №3,2004.

55. Дроздов А. Ю., Кирнасов A.E. Анализ предикатных выражений и его использование в оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом // Информационные технологии, № 7,2005 г.

56. T.Ball, J. R. Larus. Efficient path profiling // In International Symposium on Microarchitecture, pp. 46-57,1996.

57. В. Calder, P. Feller, A. Eustace. Value profiling // In International Symposium on Microarchitecture, pp. 259-269, 1997,

58. B. Calder, P. Feller, A. Eustace. Value profiling and optimization // Journal of Instruction Level Parallelism, 1999.

59. S. Watterson, S. Debray. Goal-directed value profiling // Lecture Notes in Computer Science, 2001.

60. Серебряный K.C. Методы высокоуровневой оптимизации циклов. Дис. канд. тех. наук: 05.13.11, ЗАО «МЦСТ», М.-2004

61. Галазин А.Б. Оптимизация участков кода с малым количеством исполнений. // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН 2006. - Вып.9 - С. 28-63

62. R. Muth, S. A.Watterson, S. К. Debray. Code specialization based on value profiles // In Static Analysis Symposium, pp. 340-359,2000.