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

УДК 004.4'416 На правах рукописи

7 ¿>

и/7/Т- '¿¡> А, У/.

Филиппов Александр Николаевич

МЕТОДЫ УДАЛЕНИЯ ИЗБЫТОЧНОСТЕЙ НА ЭТАПЕ КОМПИЛЯЦИИ ПРОГРАММ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 6 НОЯ 2009

Москва-2009

003484919

Работа выполнена в ЗАО «МЦСТ» и ОАО «ИНЭУМим. И.С.Брука»

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

старший научный сотрудник Волконский Владимир Юрьевич

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

Петренко Александр Константинович кандидат технических наук Серебряный Константин Сергеевич

Ведущая организация: ОАО «Институт точной механики и

вычислительной техники им. С.А. Лебедева»

Защита состоится « 3 » ^в/сй^Ъ я 2009г. в /5" часов на заседании диссертационного совета Д.409.009.01 при ОАО «Институт электронных управляющих машин им. И.С.Брука», расположенном по адресу : 119334, Москва, ул. Вавилова, д.24

С диссертацией можно ознакомиться в библиотеке ОАО «ИНЭУМ им. И.С. Брука»

Автореферат разослан « £) » //¿)9&>Я 2009 г.

Ученый секретарь диссертационного совета, кандидат технических наук, профессор

Красовский В.Е.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация.

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

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

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

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

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

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

• на семинарах секции программного обеспечения ЗАО «МЦСТ» и ОАО «ИНЭУМ».

Публикации.

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

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

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

Содержание работы.

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

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

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

Piic. 1. Классификация избыточностей Подробное исследование трех известных методов нумерации значений - пессимистического (Hash Based Value Numbering), оптимистического (Value Partitioning) и универсального (SCC Based Value Numbering) - в части устранения внутрипроцедурных избыточностей приводит к выводу, что, несмотря на многообразие возможностей, они имеют ряд недостатков.

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

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

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

8

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

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

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

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

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

Эффективность предложенного метода нумерации значений для операций обращения в память экспериментально проверена на задачах пакета SPEC CPU2000. В ходе экспериментов для каждого теста подсчитывалась процентная доля «потенциально избыточных»1 операций чтения из памяти. Она в среднем составила 33% от общего количества чтений, а на некоторых тестах достигала 58%.

Следующим результатом в части сокращения ограничений, свойственных методам устранения внутрипроцедурных избыточностей, является алгоритм выявления эквивалентностей между арифметическими операциями, имеющими разные имена. Он базируется на использовании техники PS-форм (форма сумм произведений, Product Sums Form). PS-форма представляет собой полином вида с0 + С1хцх12... х^ +... + с^х^... х& , где са..., сп -некоторые константы, a х,у - переменные (в нашем случае, классы кошру-энтности). В качестве дополнительного признака эквивалентности операций предложенный алгоритм использует совпадение соответствующих им PS-форм. Причиной выбора PS-форм в качестве символьных выражений для анализа является обилие арифметических операций, используемых, главным образом, для вычисления индексов многомерных массивов, встречающееся в кодах реальных программ.

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

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

10

в заданном диапазоне. В работе предложен интегрированный с Value Numbering способ описания константных свойств выражений, при котором значение выражения рассматривается не как число, а как вектор битов. Для этого каждому классу конгруэнтности сопоставляется два битовых вектора: вектор известных битов {known bits) и вектор значений известных битов (hits yal). Равенство единице бита с номером п вектора knownbits означает, что значение этого бита (в результатах всех операций данного класса конгруэнтности) известно. Величина этого известного значения отражена в бите с номером п вектора bitsval.

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

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

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

• глобальный сбор общих подвыражений (GCSE, Global Common Subexpressions Elimination),

• глобальное распространение копий (GCP, Global Copy Propagation)

• удаление частичных избыточностей (PRE, Partial Redundancies Elimination или VDCM, Value Driven Code Motion)

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

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

Усиленный метод нумерации значений, включающий в себя нумерацию значений для операций обращения в память, использование техники PS-форм, а также применение битового подхода к описанию константных свойств операций, был реализован в составе оптимизирующего компилятора для архитектуры «Эльбрус». В составе компилятора были также реализованы оптимизации GCP, GCSE, VDCM и bitopt.

С практической точки зрения, использование результатов усиленного метода нумерации значений позволило повысить эффективность оптимизаций GCP, GCSE и VDCM и достичь дополнительного прироста производительности, по сравнению с базовым методом. Для пакета SPEC CPU2000 среднее ускорение составило 8,5%; на отдельных тестах ускорение достигло 28,8%. Что касается пакета SPEC CPU95, то для него среднее ускорение составило 3,15%, а на отдельных тестах достигло 6%.

Исследовалось применение оптимизации bitopt, использующей исключительно результаты усиленной нумерации значений, после проведения классических оптимизаций. Для тестов пакета SPEC CINT2000 оно дало дополнительное ускорение, которое в среднем составило 1,3%, а на отдельных тестах достигло 2,7%. На тестах пакета SPEC CPU95 среднее ускорение составило 3%, а максимальное - 6,9%.

Методы, предложенные в данной главе, не зависят от конкретной архитектуры и могут применяться в оптимизирующих компиляторах для различных микропроцессоров. В частности, усиленный метод нумерации значений и использующие его преобразования были реализованы в составе компилятора для суперскалярных микропроцессоров Sparc. На тестах пакета SPEC CPU95 использование усиленного метода нумерации значений позволило достичь ускорения до 4,8%, а использование оптимизации bitopt

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

В Главе 3 рассматривается задача удаления избыточностей, специфичных для архитектур класса ЕРЮ.

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

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

Решение этой проблемы потребовало разработки специализированных методов упрощения предикатных выражений и удаления избыточных предикатов. Метод упрощения сложных предикатных выражений основывается на построении совершенных дизъюнктивно нормальных форм (СДНФ) для предикатов и последующем их упрощении с помощью правил булевой и укороченной (short circuit) логики, а также на основе анализа потока данных программы. Кроме того, совпадение СДНФ является критерием для установления эквивалентности предикатов и последующего удаления избыточных (дублирующих) предикатных операций. Использование

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

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

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

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

Время исполнения аппаратно-конвейеризованного цикла монотонно зависит от величины max(nr, па), где пг - длина максимальной рекуррентности, а па - минимальное число инструкций, необходимое для упаковки опе-

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

В качестве способа минимизации пг в диссертационной работе предложен метод специализированной балансировки, предполагающий вынос «лишних» операций из рекуррентных цепочек. В рамках оптимизирующего компилятора для архитектуры «Эльбрус» классическая и специализированная балансировка реализованы в виде единой многоцелевой балансировки. Она включает в себя различные эвристические условия, исходя из которых принимается решение о применении классического или специализированного алгоритма преобразования. Использование многоцелевой балансировки в компиляторе позволило достичь ускорения до 15,5% и 19,5% на тестах пакетов SPEC CPU2000 и SPEC CPU95 соответственно.

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

На задачах пакета SPEC CPU95 комбинирование операций в контексте аппаратно-конвейеризованных циклов привело к ускорению до 6%. Кроме того, данная оптимизация позволила достичь очень хорошего эффекта -ускорение до 98% - на функциях, входящих в состав высокопроизводительной библиотеки векторных вычислений для архитектуры "Эльбрус".

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

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

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

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

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

res_size = beforejsizel + before_size2 — common opersjmm где res size - итоговый размер вызывающей процедуры после подстановки, before size 1 и before_size2 - размеры вызывающий и вызываемой процедур до подстановки, a common opers пит - число эквивалентных операций в вызывающей и вызываемой процедурах.

Справедливости ради, нужно сказать, что в реальных программах контекст для такой специализированной подстановки встречается довольно редко. Реализованная в составе оптимизирующего компилятора, инлайн-подстановка на основе результатов межпроцедурной нумерации значений применилась лишь на двух тестах из пакета SPEC CPU2000 и одном тесте из пакета SPEC CPU95. Максимальное ускорение составило 3%. При этом размер исполняемой программы увеличился незначительно.

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

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

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

На основании полученной статистической информации, в работе предложен метод условной итайн-подстановки. Он сочетает в себе последовательную специализацию кода и, собственно, подстановку тела функции в точку вызова. Суть первой состоит в том, что если вероятность вызова в данной точке программы конкретной процедуры f une превосходит некоторый порог, то непосредственно перед этой точкой строится ветвление управления. Условием ветвления полагается совпадение адреса вызова и адреса процедуры func. В случае если эти адреса совпадают, управление передается на участок кода, содержащий явный вызов func. В противном случае, управление передается на исходный участок кода, содержащий косвенный вызов. Теперь, после того, как в программе появился явный вызов, компилятор в состоянии выполнить подстановку тела процедуры func в точку вызова.

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

вызовы. В пакете SPEC CPU2000 содержится 5 таких программ, па которых удалось достичь ускорения до 14,5%.

Заключение

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

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

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

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

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. Использование этих методов и алгоритмов вносит ощутимый вклад в задачу повышения производительности упомянутых вычислительных систем. Кроме того, результаты исследования могут быть адаптированы для использования в других вычислительных системах, ориентированных на высокопроизводительные вычисления.

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

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

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

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

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

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

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

Подписано в печать 30 октября 2009 г. Объем 1,2 п.л. Тираж 100 экз. Заказ № 1028 Отпечатано в Центре оперативной полиграфии ООО «Ол Би Принт» Москва, Ленинский пр-т, д.37

Введение.

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. Использование этих методов и алгоритмов вносит ощутимый вклад в задачу повышения производительности упомянутых вычислительных систем. Кроме того, результаты исследования могут быть адаптированы для использования в других вычислительных системах, ориентированных на высокопроизводительные вычисления.

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.