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

084615601

Дроздов Александр Юльевич

Компонентный подход к построению оптимизирующих компиляторов

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

Автореферат

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

Москва-2010

004615601

Работа выполнена в Институте Точной Механики и Вычислительной техники им. С.А. Лебедева

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

чл.-корр. РАН

Воеводин Владимир Валентинович

доктор физико-математических наук Галатенко Владимир Антонович

доктор физико-математических наук Крюков Виктор Алексеевич

Ведущая организация Учреждение Российской академии наук

Вычислительный центр им. А. А. Дородницына РАН

Защита состоится « 16 » декабря 2010 г. в 15 ч. 00 мин. на заседании диссертационного совета Д 002.087.01 при Учреждении Российской академии наук Институте системного программирования РАН по адресу:

109004, Москва, ул. Александра Солженицына, д.25, Учреждение Российской академии наук

Институт системного программирования РАН, конференц-зал (комн. 110). С диссертацией можно ознакомиться в библиотеке ИСП РАН.

Автореферат разослан «¡03»» 2010 г.

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

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

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

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

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

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

этих решений. В качестве примеров можно привести оптимизирующие компиляторы компаний Intel, Sun Microsystems, Transmeta, Microsoft, IBM, HP, Elbrus, и др. Все эти компании создали свои собственные, не совместимые друг с другом коммерческие продукты с высоким уровнем внутренней сложности. Этот процесс продолжает нарастать, так как нужно соответствовать современной тенденции увеличения разнообразия аппаратных решений (Multi core, Many core, EPIC и т.д.).

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

Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая всё более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, её значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.

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

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

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

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

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

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

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

Исходя из вышеизложенного, для достижения поставленной цели в работе выполняются:

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

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

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

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

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

Предмет исследования

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

• Алгоритмические основы функционирования блоков

оптимизирующих компиляторов:

методы статического анализа программ;

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

^ методы многопоточного распараллеливания программ на основе технологии ОрепМР;

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

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

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

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

• Методология портирования блоков оптимизирующей компиляции в контексте существующих инфраструктур оптимизирующей компиляции (GCC, phoenix, АСЕ, open64, pathscale,...);

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

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

распараллеливатель, работающий в составе компиляторной технологии GCC (www.gnu.org). Замеры производились на пакетах задач Spec92, Spec95 и Spec2006.

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

Научной новизной в диссертации обладают:

1) разработка новых и улучшение существующих алгоритмов и

структур данных, которые используются для создания

оптимизирующих компиляторов:

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

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

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

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

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

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

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

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

2) разработка новых методов построения компонент оптимизирующей

компиляции:

■ разработка методологии реализации блоков оптимизирующей компиляции, позволяющей распараллеливать работу компилятора;

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

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

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

Апробация

Результаты работы докладывались на Всероссийской научно-практической конференции «Перспективы развития

высокопроизводительных вычислительных архитектур: история,

современность и будущее отечественного компьютеростроения», приуроченной к 60-летию ИТМиВТ им. С.А. Лебедева РАН в 2008 году.

Практические результаты работы докладывались на международном форуме «Салон инноваций и инвестиций — 2008», который проходил в Москве, ВВЦ, в 2008 году. Проект «Разработчик оптимизирующих компиляторов» был удостоен золотой медали VIII Московского международного салона инноваций и инвестиций.

Результаты работы докладывались на IX Санкт-Петербургской Международной конференции «Региональная информатика-2004 (РИ-2004)» в 2004 г., на Международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, 2004 г.), XXI Научно-технической конференции войсковой части 03425 (Москва, в/ч 03425, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО "МЦСТ" (2003-2005 гг.), Института микропроцессорных вычислительных систем РАН (2004-2005 гг.), Института точной механики и вычислительной техники им. С.А. Лебедева РАН (2007-2008 гг.), Института системного программирования РАН (2008), ОАО «Научно-исследовательский центр электронной вычислительной техники» (НИЦЭВТ) (2008) и НИВЦ МГУ им. Ломоносова (2009,2010).

Публикации

По теме диссертации опубликованы 36 печатных работ. Из них 14 в изданиях, рекомендованных ВАК.

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

Диссертация состоит из пяти глав и заключения. Диссертация содержит 307 страниц, 124 рисунка, 23 таблицы. Список литературы насчитывает 160 наименований.

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

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

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

Структурные аспекты

В качестве языка реализации был выбран язык С++, как проверенный инструмент отображения абстракций объектно-ориентированного проектирования.

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

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

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

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

- использование единого стиля программирования;

- использование методов и практик объектно-ориентированного проектирования и программирования;

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

- использование средств внутренней верификации и отладки;

- использование средств визуализации внутренних структур данных;

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

- глубокое тестирование программ.

На настоящий момент времени блоки оптимизирующей компиляции, реализованные на основе технологии, предложенной в данной работе, оттестированы в технологической цепочке компиляторов GCC. Компиляция с языков С, С++, FORTRAN оттестирована в контексте архитектуры х86. Сейчас есть возможность производить тестирование в контексте любой целевой архитектуры, поддержанной в технологической цепочке GCC - х86, Itanium, SPARC, MIPS, Power PC, Power Cell.

Параметризация окружения

Рис. 1 иллюстрирует основной подход к переносимости технологии в произвольные технологические цепочки.

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

методов анализа и/или трансформации программы: анализ потока управления, анализ потока данных, скалярный оптимизатор и т.д.

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

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

Иерархия оптимизирующих блоков

|Оптими*ации и планирование

............ ........~¥

[ Анализ (1РА, РР, 00....)

Аналитические структуры

[ Инструменты (Граф, хеш...)

База данных программы

Машинная модель

Информация высокого уровня: ¡таблица символов. ра>меры....

1_

Семантика программы: операции, операнды передана управления....

Рис.1 Иерархия блоков и база данных программы

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

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

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

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

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

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

Для того чтобы произвести абстрагирование, программу необходимо представить в понятиях настолько общих, что внутренняя структура реализации этого представления не будет никак сказываться на реализации блоков. Наиболее общий подход к хранению и манипуляции данных, позволяющий практически полностью абстрагировать конкретный способ хранения этих данных, представлен в использовании базы данных Oracle. Доступ к базе данных (заполнение, изменение, удаление) осуществляется при помощи интерфейса запросов (SQL) или при помощи функционального интерфейса (PL SQL), что и позволяет полностью скрыть реализацию базы от пользователя. Подобный подход применим и в случае с информацией о программе (информация о высокоуровневом языке, информация о семантике операций и информация о целевой архитектуре (machine model)). Задание всех входных параметров компиляции через такую базу данных позволяет полностью скрыть от пользователя детали используемого промежуточного представления

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

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

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

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

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

Распараллеливание работы компилятора

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

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

Регион-,

(модуль, процедура, цикл)

Thread-,

if?

Ьптимизации[.

; j Анализы

Модели

' / '

Инструменты

Регионп

(модуль, процедура, цикл)

Thread,,

-V

Оптимизации

:liiii|l

Анализы

Модели

0Ш

Инструменты

/ :

Рис. 2. Распараллеливание

В главе 3 разработана технология портирования блоков оптимизирующей компиляции в любую существующую технологическую цепочку. Современный оптимизирующий компилятор представляет из себя программный инструмент, с помощью которого можно откомпилировать программу, написанную на некотором входном языке программирования (С, С++, Fortran и. т. д.) или представленную в машинных кодах (х86, spare и т.д.), в требуемый выходной язык или машинный код. В процессе компиляции программа последовательно трансформируется в промежуточные представления, используемые компиляторами для сохранения семантики программы в процессе компиляции. На интерфейсах промежуточных представлений реализуются алгоритмы анализа и оптимизаций.

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

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

Методы портирования

■■

-:-

Анализы и Оптимизации

Способы портирования

, ; -.............■ ■ -- ■■ | Щ -—

Аналитические модели (CFG, DFG, DAG,...) -В_I_i_i_i_t_i____j_

\налитичёское промежуточное представление_

mm

промежуточное оставление

Профаммная база данных

---___L._ I IM,

Рис. 3 Способы портирования

Существует три сценария взаимодействия блоков оптимизирующей компиляции с системой трансляции пользователя (рис. 3,4).

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

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

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

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

XML файл БДП /память

сохранить в восстановить

i

пп,

"Г

Надстройка над ПП*

I

ппп

<

Код на выходе

*) ПП - Промежуточное представление

Рис. 4 Методика портирования

Семантическое представление

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

фрагменты программ внутри модулей. Структуры данных программ представляются объектами с фиксированными или динамически задаваемыми размерами и описанием их внутренней структуры с помощью типов. Наиболее общим способом сохранения алгоритмической составляющей программы в компиляторах является операционное представление (рис 5).

Операционное представление является списком операций. У операции может существовать входной контекст и выходной контекст. Входной и выходной контексты задаются списками аргументов и результатов. Аргументы могут быть литералами, объектами или ссылками на другие операции. Отображение связи между результатом одной операции и аргументом другой через объекты является более общей, чем представление этой связи в виде ссылки на операцию. Сама операция представляет собой набор атрибутов, определяющих семантическое действие над входным контекстом для получения выходного контекста. К такому операционному представлению может быть сведено практически любое известное промежуточное представление, начиная с синтаксических деревьев фронтендов ^сс, е<1§), заканчивая представлениями, наиболее приближенными к ассемблерам целевой архитектуры.

Рис. 5 Представление операции

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

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

Для представления фрагментации программы на уровне аналитического представления вводится понятие области видимости. Области видимости имеют иерархическую организацию. Каждый объект программы принадлежит одной из областей видимости. Понятия модуля и процедуры семантического представления программы представляются областями видимости в аналитическом представлении программы.

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

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

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

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

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

Рис.6

Семантическая модель

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

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

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

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

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

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

Рис. 7. 3-х аргументная операция сложения и ее семантическая модель

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

Совместимость с GCC

Технология, представленная в работе, может применяться на платформах Windows, Linux или как кросс-платформенная. Исходный код транслируется с языков С, С++, Fortran компилятором GCC. С промежуточного представления высокого уровня 'GIMPLE', используемого в gcc, семантика экспортируется в файл в формате базы данных программы, из которого она далее разворачивается в промежуточное представление оптимизирующих блоков. На этом промежуточном представлении применяются оптимизации, после чего модифицированная семантика экспортируется обратно в файл, из которого она далее возвращается обратно в компилятор GCC, разворачивается в нем

в его промежуточное представление и далее транслируется в код целевой машины, например х86, SPARC, PowerPC (рис.8).

Платформа „ £ {£\Unux , ufjWndows }

Рис. 8. Совместимость с GCC

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

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

зависящего от семантики программы), модели программы (граф потока управления, граф потока данных).

ОМР Распар аллеливатель Оптимизатор потока данных Трансформации управления

От

о

Менеджер памяти

Рис. 9. Иерархия блоков оптимизирующей компиляции

В п.4.3 рассмотрены алгоритмические основы построения анализатора программ.

Форма статического единственного присваивания (Static Single Assignment, SSA) является одной из самых распространенных форм представления потока данных программы и активно используется в большинстве современных оптимизирующих компиляторов. Для множества переменных сложность алгоритма имеет порядок 0(Е)*В, где В - количество переменных, для которых строится SSA-форма, Е -количество дуг графа потока управления. Таким образом, количество переменных существенно влияет на скорость преобразования программы в SSA-форму. В работе предлагается метод, позволяющий уменьшать алгоритмическую сложность алгоритмов построения (р-функций, которые

¡Продукты

4

ft Л

представляют собой вспомогательные элементы промежуточного представления и построение которых составляет основную алгоритмическую сложность перевода программы в статическую форму единственного присваивания. В новой оценке величина В заменяется на величину B/size(word), где size(word) - размер минимального элемента реализации пакета битовых векторов (в нашей реализации size(word)=32).

Предложена новая структура данных (дерево значений), позволяющая объединить в единое целое информацию о потоке данных и доминировании. Приведен алгоритм построения дерева значений. Алгоритм обладает алгоритмической сложностью 0(Mi+M2*N), где М! -число операций и ф-узлов SSA-формы, - число операций

промежуточного представления программы, N - число линейных участков в управляющем графе. Результаты тестирования показали, что дерево значений имеет хорошие характеристики по объему занимаемой памяти и подходит для использования в промышленных компиляторах. Далее показывается, как использование дерева значений позволяет эффективно проводить ряд оптимизирующих преобразований программы, таких как глобальное распространение копий (Global Copy Propagation, далее GCP), удаление излишних чтений (Redundant Loads Elimination, далее RLE), удаление мертвого кода (Dead Code Elimination, далее DCE) и удаление излишних записей (Redundant Stores Elimination, далее RSE). Для этих оптимизаций использование дерева значений позволяет упростить их реализацию, увеличив при этом эффект от применения и регион применения как минимум некоторых из них.

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

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

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

Метод, расширяющий применимость этого вида анализа на случай произвольного региона, позволяет включить в рассмотрение поток данных, входящих в регион через ср-узлы. На рис. 10 представлен пример, в котором на основе анализа предикатов удаётся определить, что операция условной записи в переменную a (store a, v [рО]) доминирует над операцией use г0 [р4], которая использует результат операции чтения из переменной a (load а г0), следовательно, оптимизация удаления избыточных чтений применима.

Рис.10. Пример предикатного кода.

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

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

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

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

Ключевыми параметрами в постановке задачи межпроцедурного анализа являются:

— множество объектов программы, для которых проводится анализ;

- степень детализации результатов анализа.

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

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

За основу решения данной проблемы в работе был взят известный подход, основанный на использовании частичных трансферных функций (ЧТФ) (Robert P.Wilson, Monika S.Lam. Efficient context-sensitive pointer analysis for С programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language and Implementation, pages 1-12, June 1995.).

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

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

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

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

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

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

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

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

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

Эти методы позволили повысить на десятки (а в случае планирования циклов методом наложения итераций на сотни) процентов эффективность использования аппаратных ресурсов архитектуры «Эльбрус-ЗМ» с явно выраженной параллельностью на уровне команд по сравнению с кодом, полученным без использования данных методов.

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

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

технологической цепочки GCC и компонентной технологии оптимизирующей трансляции (КТОТ). Коллекция компиляторов GCC позволяет транслировать приложения со всех популярных языков программирования, таких как С, С++, Fortran, в код наиболее известных целевых платформ, таких как х86, Power Cell, Sparc и т.п. Компонентная технология оптимизирующей трансляции содержит в себе методы статического анализа программ, оптимизирующие преобразования и алгоритмы распараллеливания. Технология портирования, на базе которой реализована библиотека компонент, позволяет использовать все компоненты совместно с любой технологической компиляторной цепочкой, в том числе и с GCC.

Таким образом, используя технологию GCC для трансляции программ с языков высокого уровня в языки целевых архитектур, и технологию КТОТ для статического анализа программ, выявления параллельности и оптимизаций программ, был реализован АР.

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

> анализ потока данных методом нумераций значений

> анализ потока управления

> анализ переменных в цикле (распознавание инвариантов, индуктивностей, рекурентностей)

> анализ цикловых зависимостей

> анализ зависимостей на ациклических участках

> межпроцедурный анализ потока данных -чувствительный/нечувствительный к потоку управления/вызывающему контексту

> межпроцедурный распространитель (констант, выравниваний, диапазонов, указателей)

> межпроцедурный анализ методом нумерации значений

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

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

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

В работе приведены результаты сравнения производительности базовых компиляторов для платформ х8б, IA64 и PowerPC компаний Intel и IBM с производительностью для этих платформ, полученной с помощью АР. Замеры проводились для подмножества задач из пакетов Spec2006 и NAS Parallel Benchmarks

Ощутимый прирост производительности от применения АР зафиксирован как на задачах пакета Spec2006, так и на задачах NPB. В среднем, автоматический распараллеливатель (utlcc) дает больший прирост производительности по отношению к исходному уровню gcc, чем функциональность автоматического распараллеливания базовых компиляторов компаний Intel и IBM (reference) по отношению к их исходному уровню (без распараллеливания).

Ниже (рис. 11 и 12) приведены сравнительные характеристики АР (utlcc) и автоматического распараллеливания от базовых компиляторов компаний Intel и IBM (reference). Для получения сравниваемых значений время исполнения задачи, скомпилированной без распараллеливания, делится на время исполнения распараллеленной версии. Затем эти отношений усреднялись по каждому из пакетов (по 6 задачам из каждого). Результат выражается в процентах. В скобках указано количество ядер на аппаратных системах, для которых производилось сравнение (<архитектура> (х<количество ядер>)).

Spec2006

500% -

400% -

300% -

200%

100%

0%

-1Ж1-

X

х86 (х8)

IA64 (х4)

IA64 (х64) PowerPC (х2)

■ reference ■ utlcc

Рис. 11. Интегральные результаты по производительности (Spec2006)

NAS Parallel Benchmarks

1100% 900% 700% 500% 300% 100% -100%

□ reference □ utlcc Рис. 12. Интегральные результаты по производительности (NAS)

Как видно из приведенных на рис.11 и рис.12 диаграмм, авто-распараллеливатель, созданный на основе компонентного подхода, распараллеливает более эффективно, чем авто-распараллеливатели базовых компиляторов компаний Intel и IBM.

Компилятор общего назначения для архитектуры «Эльбрус-ЗМ» позволил вычислительному комплексу, построенному на базе этой архитектуры, реализовать заложенный в него потенциал и достичь требований производительности, которые поставил перед разработчиками заказчик и которые были подтверждены государственными испытаниями вычислительного комплекса «Эльбрус-ЗМ» в 2007 году.

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

х86(х8) 1А64 (х4) IA64 (х64) PowerPC (х2)

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

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

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

1. Разработаны или существенно улучшены алгоритмические основы компонент оптимизирующих компиляторов: 1.1. Статический анализ программ

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

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

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

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

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

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

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

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

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

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

■ Предложен алгоритм решения задачи межпроцедурной нумерации значений.

1.2. Глобальное планирование программ

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

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

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

1.2. Разработаны методы группирования оптимизаций,

позволяющие повысить эффективность применения оптимизаций

при одновременном уменьшении времени компиляции.

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

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

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

5. На примере автоматического распараллеливателя программ показана эффективность применения разработанных технологических и алгоритмических основ построения оптимизирующих компиляторов.

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

созданы анализатор программ и автоматический распараллеливатель программ для архитектур х86 (Intel, AMD), Itanium (Intel), Power PC, Power Cell. Автоматические распараллеливатели были построены на основе совместного использования компонентной технологии построения оптимизирующих компиляторов и технологии GCC.

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

1. Дроздов А.Ю. Компонентный подход к построению оптимизирующих компиляторов. // Программирование. 2009. № 5, с. 7080

2. Дроздов А.Ю., Особенности и перспективы Универсальной технологии оптимизирующей компиляции. // Сборник научных трудов ИТМиВТ им. С. А. Лебедева РАН, Выпуск №1, Материалы Всероссийской конференции «Перспективы развития высокопроизводительных архитектур. История, современность и будущее отечественного компьютеростроения», 2008, С. 62-74.

3. А.Ю. Дроздов, C.B. Новиков. Авто-распараллеливатель программ, реализованный на основе компонентной технологии построения оптимизирующих компиляторов. // Программирование. 2009. № 6, с. 124.

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

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

6. Дроздов А.Ю, Владиславлев В.Е. Межпроцедурный анализ указателей // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 2-13.

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

8. Дроздов А. Ю., Тютюник О. М., Шилов В.В. Эффективная реализация графа потока зависимостей // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 19-23.

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

10. Дроздов А.Ю, Боханко A.C. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании // Информационные технологии, № 12, 2004 г.

11. Дроздов А. Ю., Корнев P.M., Боханко A.C. Индексный анализ зависимостей по данным // Информационные технологии и вычислительные системы, № 3,2004г., с. 27-37.

12. Дроздов А. Ю., Степаненков А. М. Управляемые пакеты оптимизаций // Информационные технологии и вычислительные системы, № 3,2004г., с. 93-101.

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

14. Волконский В.Ю., Дроздов А.Ю., Ровинский Е.В. Метод использования мелкоформатных векторных операций в

оптимизирующем компиляторе // Информационные технологии и вычислительные системы, № 3, 2004г.. с. 63-77.

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

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

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

18. Дроздов А.Ю., Перекатов В.И., Шлыков СЛ. Задача планирования операций по кластерам для архитектур с разделением исполнительных устройств на кластеры // Компьютеры в учебном процессе, № 3, 2005 г.

19. Дроздов А.Ю., Кирнасов А.Е., Перекатов В.И. Использование результатов анализа предикатных выражений для эффективного применения оптимизирующих преобразований программ // Компьютеры в учебном процессе, № 3,2005 г.

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

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

22. Дроздов А.Ю., Ровинский Е.В. Технология использования векторных операций для получения оптимального кода // Компьютеры в учебном процессе, № 9, 2004 г.

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

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

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

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

27. Дроздов А.Ю., Владиславлев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

28. Боханко А.С., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

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

молодежной научной конференции «XXX Гагаринские чтения», Москва, 2004.

30. Б. А. Бабаян А. К. Ким, Ю. X. Сахин, А. Ю. Дроздов и др. ИМВС РАН Научно-технический отчет по НИР «Поисковые исследования и разработка архитектурных и логических принципов построения универсальных вычислительных систем «Эльбрус-4» с производительностью пентафлопового диапазона». Разработка принципов построения однокристального мультипроцессора. Глава 3: Исследование зависимостей по данным и управлению в алгоритмах задач. Москва 2003г.

31. Б. А. Бабаян, А. К. Ким, Ю. X. Сахин, А. Ю. Дроздов и др. Российская академия наук. Институт микропроцессорных вычислительных систем (ИМВС). Отчет о научно-исследовательской работе. Программа фундаментальных научных исследований ОИТВС РАН "Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий". Направление № 2 "Высокопараллельная, масштабируемая кластерная архитектура, приспосабливаемая под конкретные приложения". Раздел 9: Особенности генерации кода для архитектур с разделением исполнительных устройств на кластеры. Москва 2003.

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

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

технической конфренции войсковой части 03425" Москва, в/ч 03425, 2003г.

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

35. A. Drozdov, I. Moukhin, A. Kasinsky, S. Okunev, A. Ostanevich, Y. Rumyantsev, A. Sushentsov, V. Tikhonov, V. Volkonski, K. Yaremenko. The optimizing compiler for the Elbrus-3 supercomputer // In Proceedings of the "International Congress on Computer Systems and Applied Mathematics ( CSAM'93)", Abstracts. - St. Petersburg, July 19-23,1993. - P. 127-128.

36. В. Ю. Волконский, А. Ю. Дроздов, А. И. Касинский, И. А. Мухин, С. К. Окунев, А. Ю. Остаиевич, A. JI. Сушенцов и др. Оптимизирующая транслирующая система для МВК "Эльбрус-3" // В трудах международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях", Тезисы. - Алма-Ата, сентябрь 1991 г. - С. 70.

Формат 60x90/16. Заказ 948. Тираж 100 экз. Подписано в печать 19.10.2010 г.

Печать офсетная. Бумага для множительных аппаратов.

Отпечатано в ООО "ФЭД+", Москва, ул. Кедрова, д. 15, тел. 774-26-96

5.4 Выводы

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

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

Основными результатами данной главы является авто-распараллеливатель программ, созданный на основе компонентного подхода к построению оптимизирующих компиляторов и полномасштабный оптимизирующий компилятор для архитектуры «Эльбрус-ЗМ» ([4-6]). Компонентная технология позволила встроить авто-распараллеливатель в состав технологии gcc, а также позволяет встраиваться в любую технологическую цепочку компиляции.

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

Несмотря на ограничения в использовании автоматического распараллеливания, существует целый ряд реальных приложений, на которых удается добиться заметного улучшения производительности. Наиболее благоприятные условия для автоматического распараллеливания существуют в фортрановских задачах (410.bwaves, 436.cactusADM, 437.1eslie3d, 459.GemsFDTD, задачи пакета NPB), в силу специфики алгоритмов, реализуемых на этом языке. В тоже время две задачи (462.1ibquantum, 470.1bm), написанные на языке С, так же удалось распараллелить.

Следует отметить важность использования межпроцедурного анализа, позволившего распараллелить две задачи (470.1bm и 462.1ibquantum) из шести.

В среднем АР, встроенный в GCC, показ ал, лучшие результаты распараллеливания как на задачах пакета Spec2006, так и на задачах пакета NPB на архитектурах фирм Intel (х86, IA64) и IBM (PowerPC)

Автоматический распараллеливатель, встроенный в GCC показал свое превосходство над одним из лучших на сегодняший день автоматических распараллеливаетелей — компилятором компании Intel - icc.

Компилятор общего назначения для архитектуры «Эльбрус-ЗМ» ([4-6]) позволил вычислительному комплексу, построенному на базе этой архитектуры реализовать заложенный в него потенциал и достичь требований производительности, которые поставил перед разработчиками заказчик.

6 Заключение

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

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

1. Разработаны или существенно улучшены алгоритмические основы компонент оптимизирующих компиляторов: 1.1. Статический анализ программ

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

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

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

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

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

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

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

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

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

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

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

Предложен алгоритм решения задачи межпроцедурной нумерации значений.

2. Глобальное планирование программе

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

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

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

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

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

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

4. Разработана методология»портирования блоков* оптимизирующей компиляции в состав любой существующей технологической цепочки. Это позволяет, использую блочную технологию, достраивать и улучшать любой оптимизирующий компилятор без необходимости его полного редизайна. Технология была успешно использована в процессе портирования автоматического распараллеливания в контекст GCC.

5. На примере автоматического распараллеливателя программ показана эффективность применения разработанных технологических и алгоритмических основ построения оптимизирующих компиляторов.

Все представленные в диссертационной работе алгоритмы, и методы, реализованы^ в составе оптимизирующего компилятора с языков высокого уровня С, С++, F77 для архитектуры «Эльбрус-ЗМ» и? составляют основу оптимизирующей части этого компилятора. На основе предложенной блочной технологии построения оптимизирующих компиляторов были созданы анализатор программ и автоматический распараллеливатель программ для архитектур х86 (Intel, AMD), Itanium (Intel), Power PC, Power Cell. Автоматические распараллеливатели были построены на основе совместного использования компонентной технологии построения оптимизирующих компиляторов и технологии GCC.

1. 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. 80 p.

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

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

4. К. 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.specbench.org/cpu928. http://open.specbench org/cpu95

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

6. В.В. Воеводин, Вл. В. Воеводин, Параллельные вычисления. Санкт-Петербург «БХВ-Петербург», 2002.

7. Alfreds V. Aho, Ravi» Sethi, Jeffrey D. UHman, "Compilers. Principles, Techniques, and Tools", Addison-Wesley, Reading, 1986.

8. John R. Ellis. Bulldog: A compiler for VLIW Architectures. MIT Press, 1985

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

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

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

12. Utpal Banerjee, Loop Transformations for Restructuring Compilers. Kluwer academic Publishers, 1993.

13. Utpal Banerjee. Dependence Analysis. Kluwer Acadmic Publishers. 1997

14. Miling Girkar, Constantine D.PolychronopouIos. "Extracting Task-Level Parallelism" ACM, July 1995.

15. Stephen Alstrup, Dov Harel, Peter W.Lauridsen, Mikkel Thorup, Dominators in Linear Time. Department of Computer Science, University of Copenhagen, 1985.

16. G. Ramalingam, On Loops, Dominators, and Dominance Frontier. PLDI 2000, Vancouver, Canada.

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

18. Vugranam C. S. Sreedhar, Guang R.Gao. Computing phi-nodes in Linear Time Using DJ-graphs. ACAPS Tchnical Memo 75, January 18, 1994.

19. Keshav Pingali, Gianfranco Bilardi, Optimal Control Dependence Computation and the Roman Chariots Problem. ACM, 1997.

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

21. Fohn W. Sias, Wen-mei W. Hwu; 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.

22. Nancy Ji.Warter,.Scott A. Mahlke, Wcn-meiW.Hwu, B. Ramakrishna Rau. Reverse If- Conversion. ACM-SIGPLAN-LDI-6/93/Albuquerque, N.M.

23. Maryam Emami- "A practical interprocedural alias analysis for optimizing/parallelizing C compiler". Master's thesis, School of Computer Science, McGill University, August 1993.

24. P.' Cousot, R. Gousot, "Abstract interpretation framework". Journal of logic and Computation, 2(4) 511-547, August 1992.

25. Eric James • Stoltz, Intermediate Compiler Analysis via. reference Chaining. Portland State University, Thesis, January 1995.

26. William-Bluine, Rudolf Eigenmann: Symbolic Range Propagation. University of Illinois at Urbana-Champaign, September 20,1994.

27. Williams Blume, Rudolf Eigenmann. Demand-driven, Symbolic Range . Propagation. University of Illinois at Urbana-Champaign.

28. Loren5 Taylor. Simson, Value-Driven Redundancy Elimination, Thesis, Rice University, Houston, Texas, April, 1996.

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

30. Kwangkeun Yi andWilliams Ludwell Harrison III, Interprocedural Data Flow Analysis for Compile-time Memory Management. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

31. Evelyn* Duestenvald, Rajiv Gupta, Mary Lou Soffa; Demand-driven Computation of Interprocedural Data Flow. Department of Computer Science, University of Pittsburg, POPL'95 1/95 San Francisco, CA USA.

32. Evelyn Duesterwald, Rajiv Gupta, and Mary Lou Soffa, A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis. University of Pittsburg, ASM SISPLAN-SIGACT Symposium on Principles of Programming Languages, 1995.

33. Susan Horwitz, Thomas Reps, and Mooly Sagiv, Demand Interprocedural Dataflow Analysis. University of Wisconsin, Proceedings of the Third ASM SIGSOFT Symposium on Foundations of Software Engineering, Washington DC, October 10-13, 1995.

34. David.R.Chase, Mark Wegman, F.Kenneth Zadeck, Analysis of Pointers and Structures. ASM SIGPLAN'90 PLDI, June 20-22,1990.

35. Yuan-Shin Hwang, Joel Saltz, Compile-Time Analysis on Programs with Dynamic Pointer-Linked Data Structures. Depatment of Computer Science, University of Maryland, Nobember 8, 1996.

36. Xinan Tang, Rakesh Ghiya, Laurie J: Hendren, Guang R.Gao, Heap Analysis and Optimizations for Threaded Programs. School of Computing Science, McGill University, 1997.

37. Rakesh Ghiya, Practical Techniques for Interprocedural Heap Analysis. School of Computing Science, McGill University, Montreal, January 1996.

38. Keith* D.Cooper, Ken Kennedy, Fast Interprocedural Alias Analysis. Rice University, 1989.

39. Bjarne Steensgaard, Points-to Analysis in Almost Linear Time, Microsoft Research, 1996.

40. Keith3 D.Cooper, Ken Kennedy, Interprocedural Side-Effect Analysis in Linear Time. Rice University, 1988.

41. Robert P.Wilson, Monika S.Lam. Efficient context-sensitive pointer analysis for С programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language and Implementation, pages 1-12, June 1995.

42. Kleanthis Psarris and Konstantinos Kyriakopoulos, Data Dependence Testing in Practice. Division of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249.

43. Paul M.Petersen and David A.Padua, Experimental Evaluation of Some Data Dependence Tests (Extended Abstract), Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

44. Paul M.Petersen, David A.Padua, Static and Dynamic Evaluation of Data Dependence Analysis. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

45. Keshav Pingali, Micah Beck, Richard« Johnson, Mayan Moudgill, Paul Stodghill, Dependence Flow Graph: An Algebraic Approach to Program Dependencies. Department of Computer Science, Cornell University, Ithaca, NY 14853.

46. Jay Hoeflinger, Run-Time Dependence Testing by Integer Sequence Analysis. Center for Supercomputing Research & Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

47. Paul M.Petersen, David A.Padua, Dynamic Dependence Analysis: A Novel Method for Data Dependence Evaluation. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801-2932.

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

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

50. Bilardi G., Pingali К. The Static Single Assignment Form and its Computation -Cornell University Technical Report, July, 1999.

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

52. Ronaldf Cytron, Jean Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth^Zadeck, "Efficiently Computing Static Single Assignment Form and the Program Dependence Graph", ACM TOPLAS, Vol. 13, No. 4, Oct. 1991, pp. 451490.

53. Thomas Lengauer, Robert Tarjan, "A Fast Algorithm for Finding Dominators in a Flowgraph", ACM TOPLAS, Vol. 1, No. 1, July 1979, pp. 121-141.

54. Боханко A.C., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

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

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

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

58. L. Garter, B. Simon, B. Calder, L. Carter, and J. Ferrante, "Predicated single static assignment ", in Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, October 1999.

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

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

61. S. A. Mahlke, D. C. Lin, W. 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.

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

63. Sebastian Winkel, "Optimal versus Heuristic Global Code Scheduling," micro, pp.43-55, 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2007), 2007

64. John? Wollenburg, "Condition awareness support for predicate analysis optimization", University of Illinois, 1997.

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

66. J. Ferrante, K. J. Ottenstein, and J.D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.

67. Le-ChumWu, Wen-mei W. Hwu. A New Data-Location Tracking Scheme for the Recovery of Expected Variables Values. Technical Report IMPACT-98-07.

68. Le-Ghun Wu, Rajiv Mirani, HarishPatil, Bruce Olsen, Wen-mei W. Hwu: A New Framework for Debugging Globally Optimized Code. ACM SIGPLAN Conference on Programming Language Design and Implementation, Atlanta, Georgia, May 1-4, 1999.

69. R: Gupta, "Debugging code reorganized by a trace scheduling compiler", Structred Programming, vol. 11, pp. 141-150, July 1990.

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

71. Vadim Maslov, "Delinearisation: an Efficient Way to Break Multiloop Dependence Equations", Proceedings of PLDI'92, ACM, 1992.

72. Г. П. Кюнци, В. Крелле, "Нелинейное программирование", Москва, Советское Радио, 1965.

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

74. М. Wolfe, С. W. Tseng, "The Power test for data dependence", IEEE Transaction on Parallel and Distributed Systems, Vol. 3, No. 5, pp. 591-601, September 1992.

75. W. Pugh, "A practical algorithm for exact array dependence analysis", Communication of the ACM, 35(8):102-114, August 1992.

76. K. Psarris, K. Kyriakopoulos, "Data Dependence Testing in Practice", IEEE International Conference on Parallel Architectures and Compiler Techniques, October 12-16, 1999, California.

77. Brian R. Murphy, Monica S. Lam "Program Analysis with Partial Transfer Function", Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, January, 1999

78. Marc Shapiro, Susan Horwitz "Fast and Flow-Insensitive Points-To Analysis". Proceedings of 24th ACM SIGPLAN-SIGACT symposium of programming language, pp.1-14, Paris, France, January (1997).

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

80. Дроздов А.Ю., Владислав л ев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская

81. Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

82. R'. Wilson. "Efficient, context-sensitive pointer analysis for С programs". Phd thesis, Stanford University, 1997.

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

84. 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-Verlag, 1998.

85. Babayan B. A*. E2k Technology and Implementation. // Proceedings of the Euro-Par 2000 Parallel Processing: 6th International. - V. 1900/2000. - January, 2000. -P. 18-21.

86. Timothy G. Mattson,.Beverly A. Sanders, Berna L. Massingill. Patterns for Parallel Programming. Addison-Wesley, 2005.

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

88. Simpson, Loren Taylor. Value-Driven Redundancy Elimination. Ph.D. Thesis, Rice University, Houston, Texas, 1996.

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

90. J R. Ellis, "Bulldog: A Compiler for VLIW "Architectures", Doctoral Dissertation, , MIT Press Cambridge MA 1985.

91. D.F. Bacon, S. L. Graham, O.J. Sharp, "Compiler Transformations for HighPerformance Computing", ACM Computing Surveys, Vol. 26, No 4, December 1994.

92. Clifford^ N. Click, "Combining Analyses, Combining Optimizations", A thesis submitted in partial fulfillment of the requiiements for the degree Doctor of Philosophy. Houston, Texas, February 1995.

93. Intel1 Itaniunb2 Processor Reference Manual for Software Development and Optimization, Document Number: 25 111 0-001, June 2002. 179 p.

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

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

96. R. P. Colwell, R. P. Nix, J. J. O'Donnel, D. В. Papworth, P. K.,Rodman. A

97. VLIW Architecture for a Trace Scheduling Compiler // in Proceedings of the second International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS II). SIGPLAN Notices, V. 22, №10. -October, 1987,- P. 180-192.

98. Joseph A. Fisher. Very Long Instruction Word Architectures and the ELI-512 // in Proceedings of 10th International Symposium on Computer Architectures, IEEE. -June, 1983.-P. 140-150.

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

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

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

102. W. A. Havanki, S. Banerjia, and T. MJ Conte. Treegion scheduling for wide-issue processors // Proceedings of the 4th International Symposium on HighPerformance Computer Architecture (HPCA-4), February 1998.

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

104. 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. 308321, 1996

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

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

107. 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. 262271, 1999

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

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

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

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

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

113. Bi A. Babaian, S. K. 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.

114. В. A'. Babaian, S. К. 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.

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

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

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

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

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

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

121. Р:Миллер, Л.Боксер. Последовательные и параллельные алгоритмы: общий подход. БИНОМ, Лаборатория знаний, Москва, 2006

122. Alexander Aiken, Alexandru Nicolau, Steven Novack. Resource-Constrained Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, December 1995, pp. 1248-1270

123. Walter Triebel. Itanium Architecture for Software Developers. Intel Press, 2000.

124. A.E. Eichenberger, E. S. Davidson, "Stage Scheduling: A Technique to Reduce the Register Requirements of a Modulo Schedule", Proceedings of the 28-th Annual IEEE/ACM International Syposium in Microarchitecture, pp 338-349, November 1995.

125. J.R. Allen, K. Kennedy, C. Porterfleld, and J: Warren. Conversion of control dependence to data dependence // In Proceedings of the Tenth Annual ACM Symposium on the Principles of Programming Languages, January 1983, P. 177189

126. Utpal Banerjee, Loop Transformations for Restructuring Compilers. Kluwer academic Publishers, 1993.

127. A. W. Lim and M. S. Lam, Maximizing Parallelism and Minimizing Synchronization with Affine Partitions Parallel Computing, Vol. 24, Issue 3-4, May 1998, Pages 445-475.

128. A. W. Lim, G. I. Cheong and M. S. Lam, An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication In Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing, June, 1999, pp. 228-237.

129. Воеводин B.B., Воеводин Вл.В. Параллельные вычисления. // Санкт-Петербург, "БХВ-Петербург" 2002. -608 с.