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

• Окунев, Сергей Константинович
• кандидат технических наук
• 2003

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

Введение.

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

1.1. Архитектурная поддержка параллельности на уровне операций.

1.1.1. Широкое командное слово, статическое планирование операций.

1.1.2. Предикатный и спекулятивный режим исполнения операций.

1.1.3. Аппаратные ресурсы архитектур с явно выраженной параллельностью.

1.1.4. Краткое описание архитектуры Эльбрус-ЗМ.

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

1.2.1. Промежуточное представление программы и отображение параллельности.

1.2.2. Разбиение программы на участки и граф управления.

1.2.3. Методы анализа и оптимизирующие преобразования программы.

1.2.4. Генерация кода из промежуточного представления.

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

1.4. Выводы.

Глава 2. Предикатное промежуточное представление как совокупность расширенных скалярных участков.

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

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

2.1.2. Базовый регион предикатного промежуточного представления -расширенный скалярный участок (РСУ).

2.2. Алгоритм построения РСУ.

2.2.1. Построение полных условий относительно точки входа в РСУ.

2.2.2. Применение базовых преобразований контекстных операций на границах линейных участков.

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

Ж эффектом в предикатную форму.

2.2.4. Сложность алгоритма.

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

2.3.1. Использование профиля программы, взаимодействие с построением гиперблоков.

2.3.2. Усложнение предикатного преобразования.

2.4. Результаты, полученные на тестовых пакетах SPECint92 и

SPECint95.

2.4.1. Наборы тестовых программ.

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

2.5. Выводы.

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

3.1. Разметка операций временем раннего и позднего запуска и ^ критический путь участка.

3.2. Оптимизирующие преобразования для предикатного представления программы, направленные на сокращение критического пути участка.

3.2.1. Исключение условия с критического пути.

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

3.2.3. Балансировка критических путей РСУ, зависящих от условия.

3.3. Результаты, полученные на тестовых пакетах SPECint92 и

SPECint95.

3.4. Вывод.

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

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

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

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

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

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

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

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

• разработка алгоритма преобразования промежуточного представления по линейным участкам в предикатное промежуточное представление (if-conversion);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) оптимизация потенциально возможной зависимости по конфликтам доступа в память от операции записи к операции считывания-удаление с критических путей потенциально зависимых последовательностей "запись в память - считывание из памяти" путем вставления динамического сравнения адресов; ■

3) балансировка критических путей в РСУ, зависящих от условия -вставление переходов для оптимизации критических путей, зависящих от предиката.

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

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

1) Все разработанные алгоритмы реализованы автором в составе инструментального оптимизирующего компилятора с языков высокого уровня "С", "Фортран-77" для прототипа Эльбрус-ЗМ, позволяющего получать оптимизированный код данной платформы с предикатными и спекулятивными свойствами операций.

2) Инструментальный компилятор как конечный продукт вошел в состав Инструментального программного комплекса и программных средств обеспечения совместимости МВК " Эльбрус-ЗМ " с МВК " Эльбрус-2 ", " Эльбрус-1".

3) Результаты работы нашли применение при проектировании промышленного компилятора.

Апробация

Результаты работы докладывались на VIII Санкт-Петербургской международной конференции «Региональная информатика - 2002 (РИ - 2002)» в 2002 г., на международной молодежной научной конференции «XXIX Гагаринские чтения» (Москва, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО "МЦСТ" и Института микропроцессорных вычислительных систем РАН.

Публикации

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

• Волконский В. Ю., Окунев С. К. Предикатное представление как основа оптимизации программы на уровне отдельных операций // Материалы VIII Санкт-Петербургской международной конференции "Региональная информатика - 2002 (РИ - 2002)", часть 1. - Санкт-Петербург, ноябрь 2002 г. -С. 27-28;

• Окунев С. К. Базовые методы оптимизации скалярных частей программы для архитектур с явно выраженной параллельностью // Международная молодежная научная конференция «XXIX Гагаринские чтения», Тезисы докладов, том 5. -Москва, апрель, 2003 г. - С. 18-19;

• Окунев. С. К. Базовые участки (регионы) оптимизации программ для архитектур с явно выраженной параллельностью // Компьютеры в учебном процессе, № 10. -2002 г.-С. 79-95;

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

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

По теме диссертации получены 5 патентов США:

• Cache miss saving for speculative load operations: United States Patent 6,516,462 / S. K. Okunev; V. Y. Volkonsky. Appl. No.: 506429; Filed: February 17, 2000; Pub.: February 4, 2003. 12 p.

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

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

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

• Critical path optimization - unload hard extended scalar block: United States Patent 6,584,611 / B. A. Babaian, S. K. Okunev, V. Y. Volkonsky. Appl. No.: 771481; Filed: January 25, 2001; Pub.: June 24,2003. lip.

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

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

3.4. Выводы

В соответствии со стратегией оптимизации скалярных частей программы в инструментальном оптимизирующем компиляторе платформы Эльбрус-ЗМ автором была разработана и реализована фаза компиляции для применения оптимизирующих преобразований на предикатном представлении программы, направленных на сокращение критических путей расширенных скалярных участков (блок 4 на рис.13, гл. 2). Критический путь РСУ определяется по разметке графа зависимостей рассматриваемого участка временами самого раннего и самого позднего начала запуска операции.

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

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

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

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

• балансировка критических путей в РСУ, зависящих от условия - вставление переходов для оптимизации критических путей, зависящих от предиката.

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

4) Проведено сравнение рассматриваемых методов с аналогичными методами, описанными в зарубежных статьях. Стоит отметить, что практически все направления оптимизации предикатного промежуточного представления параллельно развивались и в наших проектах Эльбрус-3 и Эльбрус-ЗМ, и в линии разработок, приведших к реализации семейства процессоров Itanium Processor Family (IPF) совместного проекта ведущих компьютерных фирм США Hewlett-Pakcard и Intel. Оптимизирующие методы, рассмотренные в 3 главе диссертационной работы, были запатентованы [60-62]. Также были запатентованы: оптимизирующий метод по переносу операций на предикатном промежуточном представлении - разгрузка вычислительно значимого расширенного скалярного участка [49] и оптимизация по уменьшению промахов в кэш данных для спекулятивной операции считывания из памяти путем добавления предикатных зависимостей [59]. Эти методы, разработанные и реализованные автором в инструментальном оптимизирующем компиляторе, входят в состав фазы оптимизации критических путей.

5) Экспериментальные результаты, полученные на целочисленных задачах из тестовых пакетов SPECint92 и SPECint95, показывают, что только одна фаза оптимизации критических путей, включающая приведенные здесь методы и некоторые другие, дает улучшение эффективности результирующего кода по времени исполнения около 3% по отношению к базовому уровню оптимизации. Оптимизация программы с использованием оптимизирующих методов этой фазы и комплекса цикловых оптимизирующих преобразований дает 6-7% улучшения времени исполнения по отношению к базовому уровню оптимизации. т

Заключение

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

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

1) Созданы функциональные компоненты инструментального оптимизирующего компилятора платформы прототипа Эльбрус-ЗМ, в составе которых реализованы следующие фазы платформо-ориентированных оптимизирующих преобразований:

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

• фаза оптимизаций критического пути на предикатном представлении программы',

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

• построение полных условий относительно точки входа в РСУ;

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

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

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

• перевод операций с побочным эффектом в предикатную форму;

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

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

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

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

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

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

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

• балансировка критических путей в РСУ, зависящих от условия - вставление переходов для оптимизации критических путей, зависящих от предиката.

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

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

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

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

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

Все представленные в диссертационной работе алгоритмы, кроме алгоритма набора гиперблока и разметки участка промежуточного представления временами, разработаны и реализованы автором. Первый вариант предикатного преобразования и рассмотренных оптимизаций критического пути на предикатном представлении программы был реализован автором на языке "Эль-76" в составе оптимизирующего транслятора с этого же языка для МВК 'Эльбрус-3" в конце 80-х - начале 90-х годов. Дальнейшее развитие и настройка этих оптимизирующих методов были продолжены в работе над оптимизирующим компилятором с языков "С" и "Фортран-77" для проекта NArch, SPARC-совместимой разновидности архитектуры Эльбрус-3 (прототипа Эльбрус-ЗМ) в 90-х годах. Представленные в диссертационной работе результаты получены автором в ходе разработки и реализации оптимизирующего компилятора в составе инструментального комплекса данной архитектуры.

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

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

Список литературы диссертационного исследования кандидат технических наук Окунев, Сергей Константинович, 2003 год

1. John L. Hennessy & David A. Patterson. Computer Architecture. A Quantative Approach. Third Edition. - San Francisco: Morgan Kaufmann Publishers, Elsevier Science, 2003. - 883 p., A-1.App.

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

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

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

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

6. G. M. Amdahl. Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities // AFIPS Conference Proceedings of the SJCC. V. 30. -April, 1967.-P. 483-485.

7. Roy. F. Touzeau. A Fortran compiler for the FPS-164 Scientific Computer // in Proceedings of the ACM SIGPLAN'84 Symposium on Compiler Construction. -SIGPLAN Notices, V. 19, №6. June, 1984. - P. 48-57.

8. B. R. Rau, D. W. L. Yen, W. Yen and R. A. Towle. The Cydra 5 departmental supercomputer: design philosophies, decisions and trade-offs // Computer 22, № 1. -January, 1989.-P. 12-35.

9. James C. Dehnert and Ross A. Towle. Compiling for the Cydra 5 // IEEE Computer, 7(1/2).- 1993.-P. 181-227.

10. Система команд многопроцессорного вычислительного комплекса "Эльбрус-3". Редакция 6 (15.04.92).

11. NArch Architecture Specification. Draft D 1.2.1. Moscow Center of SPARC-technology, 1996.

12. Система программирования Эль-96. Эскизно-технический проект. Пояснительная записка. Книга 2. «Архитектура Эльбрус-ЗМ основа для защищенного языка программирования». - Московский центр СПАРК-технологии, 1996.

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

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

15. К. 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.

16. V. Kathail, M. S. Schlansker, and B. R. Rau. HPL Play-Doh architecture specification: Version 1.0.: Technical Report HPL-93-80 / Hewlett-Packard Laboratories, Palo Alto, February 1994.-58 p.

17. M. S. Schlansker, В. 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.

18. Intel Itanium Processor Reference Manual for Software Optimization, Document Number: 2455473-003, November 2001. 30 p.

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

20. Johan De Gelas. Itanium: Titan or Titanic? Ace's Hardware, July 22,2001.

21. Бабаян Б. А., Сахин Ю. X. Система Эльбрус // Программирование, № 6.- Москва, 1980.-С. 72-86.

22. Особенности архитектуры центрального процессора МВК Эльбрус / Бабаян Б. А., Горштейн В. Я., Ким Г. С., Назаров JI. Н., Сахин Ю. X. Препринт/ИТМиВТ АН СССР. - Москва, 1985. - № 15. - 46 с.28. http://open.specbench.org/osg/cpu200Q/results/

23. А. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. -Addison-Wesley, Reading, MA, 1986. 796 p.

24. Steven S. Muchnick. Advanced Compiler Design Implementation. San Francisco, California: Morgan Kaufmann Publishers, 1997, 856 p.

25. Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures. A dependence-Based Approach. San Francisco: Morgan Kaufmann, Academic Press, 2002.-790 p.

26. Касьянов В. H. Оптимизирующие преобразования программ. М.: Наука, 1988. -336 с.

27. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985.-352 с.

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

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

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

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

32. Окунев С. К. Базовые методы оптимизации скалярных частей программы для архитектур с явно выраженной параллельностью // В трудах международной молодежной научной конференции «XXIX Гагаринские чтения», том 5, Тезисы. -Москва, апрель 2003 г. С. 18-19.

33. Окунев. С. К. Базовые участки (регионы) оптимизации программ для архитектур с явно выраженной параллельностью // Компьютеры в учебном процессе, №10. -Москва, октябрь 2002 г. С. 79 - 95.

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

35. Ершов А. П. Введение в теоретическое программирование (беседа о методе). -М.: Наука, 1977. 288 с.

36. J. R. Allen, К. Kennedy, С. Porterfield, and J. Warren. Conversion of control dependence to data dependence // In Conference Record of the Tenth Annual ACM

37. Symposium on the Principles of Programming Languages. January 1983. - P. 177189.

38. J. C. Park, and M. S. Schlansker. On Predicated Execution : Technical Report HPL-91-58 / Hewlett-Packard Software and Systems Laboratory, May 1991.

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

40. Critical path optimization unload hard extended scalar block: United States Patent 6,584,611 / B. A. Babaian, S. K. Okunev, V. Y. Volkonsky. Appl. No.: 771481; Filed: January 25, 2001; Pub.: June24, 2003. lip.

41. Способ получения объектного кода: патент на изобретение № 2206119 РФ / Волконский В. Ю., Останевич А. Ю., Сушенцов А. Л. № 2000124183/09. Заявл. 22.09.2000; Опубл. 10.06.2003. Бюл. № 16. И с.

42. Michael Schlansker and Vinod Kathail. Critical Path Reduction for Scalar Programs // ■ in Proceedings of the 28th International Symposium on Microarchitecture.1. November, 1995 P. 57-69.

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

44. A. Nicolau. Run-time disambiguation: coping with statically unpredictable dependencies // IEEE Transactions on Computers. May, 1989. - V. 38. - P. 663 -678.

45. A. Huang, G. Slavenburg, and J. P. Shen. Speculative disambiguation: a compilation technique for dynamic memory disambiguation // in 21st International Symposium on Computer Architecture, Chicago. 1994. - P. 200-210.

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

47. Cache miss saving for speculative load operations: United States Patent 6,516,462 / S. K. Okunev; V. Y. Volkonsky. Appl. No.: 506429; Filed: February 17, 2000; Pub.: February 4, 2003. 12 p.

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

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

50. Critical path optimization optimizing branch operation insertion: United States Patent 6,526,573 / B. A. Babaian, S. K. Okunev, V. Y. Volkonsky. Appl. No.: 505653; Filed: February 17, 2000; Pub.: February 25,2003. 9 p.иллюстраций

51. Рис. 1 Рис. 2 Рис. 3 Рис.4 Рис. 51. Рис. 6 Рис.71. Рис. 8 Рис. 91. Рис. 10 Рис. 111. Рис. 12 Рис. 131. Рис. 141. Рис. 151. Рис. 16 Рис. 17 Рис. 181. Рис. 19 Рис. 20 Рис. 211. Рис. 221. Рис. 231. Рис. 241. Рис. 25

52. Структура широкой команды Эльбрус-ЗМ.

53. Структурная схема 4-х канального процессора Narch.

54. Структурная схема процессора Е2к.

55. Общая схема оптимизирующего компилятора

56. Контекстный объект как абстракция области памяти,' порожденной переменной1. Пример графа зависимостей

57. Пример потокового промежуточного представления с графом зависимостей1. Пояснения к рисункам

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

59. Обобщенная схема анализирующих и оптимизирующих фаз компилятора

60. Пример предикатного преобразования

61. Схема получения и работы с предикатным представлением программы

62. Расширенный скалярный участок

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

64. Достраивание записи по предикату

65. Операция записи в точке ветвления условного предложения

66. Операция записи в точке схождения альтернатив условного предложения

67. Пример РСУ из задачи compress пакета тестов SPECint92

68. Результирующий код важнейшего РСУ из задачи compress

69. Пример РСУ с разметкой времени раннего и времени позднего запуска операции

70. Печать в символьном виде важнейшего РСУ с разметкой из задачи compress

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

72. Преобразование операции «смеситель» перед фазой кодогенерации

73. Исключение условия с критического пути ("молния")

74. Рис. 26 Пример применения оптимизирующего преобразования по Стр. 102 исключению условия с критического пути

75. Рис. 27 Удаление с критического пути потенциально зависимойпоследовательности запись в память считывание из памятипутем вставления динамического сравнения адресов Стр. 104

76. Рис. 28 Пример применения преобразования по удалениюзависимостей запись-считывание с критического пути Стр. 106

77. Рис. 29 Вставление условного перехода для оптимизациикритических путей, зависящих от условия Стр. 110

78. Рис. 30 Временн'ые характеристики метода балансировки критическихпутей вставлением перехода Стр.114

79. Рис. 31 Пример вставления оптимизирующего («закорачивающего») перехода для балансировки критических путей в РСУ, зависящих от условия Стр. 116

80. Рис. 32 Результирующий код примера вставления оптимизирующего перехода для балансировки критических путей в РСУ, зависящих от условия Стр. 118

81. Рис. 33 Шаблонное преобразование зависимых операций «смеситель» содинаковым предикатным операндом (в приложении) Стр. 138

82. Рис. 34 Шаблонное преобразование параллельных операцийсмеситель» с одинаковым предикатным операндом и однимтем же преемником (в приложении) Стр. 139Ф