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

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

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

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

кандидата технических наук: Окунев, Сергей Константинович
город: Москва
год: 2003
специальность ВАК РФ: 05.13.11

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

Автореферат диссертации по теме "Базовые методы оптимизации на предикатном представлении программы для архитектур с явно выраженной параллельностью"

Институт Микропроцессорных Вычислительных Систем РАН

УДК 004.4'416

' Окунев Сергей Константинович

БАЗОВЫЕ МЕТОДЫ ОПТИМИЗАЦИИ НА ПРЕДИКАТНОМ ПРЕДСТАВЛЕНИИ ПРОГРАММЫ ДЛЯ АРХИТЕКТУР С ЯВНО ВЫРАЖЕННОЙ ПАРАЛЛЕЛЬНОСТЬЮ

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

Автореферат

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

Москва - 2003

Работа выполнена в Институте Микропроцессорных Вычислительных Систем РАН и ЗАО "МЦСТ"

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

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

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

с.н.с. Галатенко Владимир

Антонович

кандидат физико-математических наук Эйсымонт Леонид

Константинович

Ведущая организация: Институт Проблем Информатики

РАН

Защита состоится «2/{у> декабря 2003 г. в 15:00 на заседании диссертационного совета Д 002.043.01 при Институте Микропроцессорных Вычислительных Систем РАН по адресу: 119435, г. Москва, Б. Саввинский пер., д. 14.

С диссертацией можно ознакомиться в библиотеке Института Микропроцессорных Вычислительных Систем РАН.

Автореферат разослан «20» ноября 2003 г.

Ученый секретарь диссертационного совета:

д.ф.-м.н., профессор Михайлюк М.В.

£оо 5-А I f^fo

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

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

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

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

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

--3-772!

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

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

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

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

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

{if-conversion)-,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация

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

Публикации

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

США.

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

Диссертация состоит из введения, трех глав, заключения и приложения. Диссертация содержит 136 страниц, 32 рисунка, 8 таблиц, приложение на 14 страницах с 2 рисунками. Список литературы насчитывает 62 наименования.

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

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

Глава 1 рассматривает параллельность на уровне операций как основу получения эффективного кода с точки зрения архитектуры процессора и с точки зрения оптимизирующей компиляции. В разделе 1.1 показано развитие идеи архитектуры со статическим планированием и широким командным словом. Современное название такого рода архитектур определяется термином - EPIC (Explicitly Parallel Instruction Computing) или архитектура с явно выраженной параллельностью на уровне команд. Отмечаются важнейшие свойства таких архитектур: предикатный и спекулятивный режимы исполнения операций, и наличие значительных аппаратных ресурсов, направленных на поддержку

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

Табл. 1

Сравнительные характеристики ЕР1С-архитектур

Архитектура (процессор) Период разработки. Реализация (такт, частота) Размер широкой команды (бит) Регистры (целые, вещ., предик.) Число операций за такт (каналы АЛУ1, память, целые, вещ., переходы) Каналы доступа в память (Ы+ЛМ/цпкл.)

Эльбрус-3 1985-1992 сделан опытный образец 288(504)' 64+5123 10 7/2/7/5/3" 2/2/8

ЫАгсЬ 1992-1998 не реализован 512 256" 16 4/2/4/4/3 2/2/4

Е-2к 1996-... подготовка опьггиого образца 512 256* 32 6/4/8/9/17 4/2/7

1А-64 (Катит) середина 2001 800 МЬ 256 (2x128) 128 128 64 6/2/2/2/3 2/2/-

1А-64 (Иагаит-2) середина 2002 1000 МЬ-1500 МЪ 256 (2x128) 128 128 64 8/4/6/2/3" 4/2/-

1 Арифметико-логические устройства

г Команда в буфере команд находится в упакованном виде - от 1 до 4 72-разрядных слова и при дешифрации распаковывается в 504-разрядное слово

3 В процессоре два регистровых файла (буферные памяти)- общий и конвейерный для поддержки цикловых вычислений при совмещении итераций цикла

4 Каналы доступа в память совмещены по входу с двумя АЛУ

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

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

7 Максимальный выход 8 (9 для вещественных) операций в такт происходит за счет 2 комбинированных трехаргументных операций для целых и 4 комбинированных операций типа «умножить-и-сложить» для вещественных (плюс операция деления). Устройств передачи управления в Е2К 3, но за один такт можно запустить только один переход (это сделано для увеличения тактовой частоты процессора).

8 Число арифметических каналов и каналов памяти - 8 (4 память и/или целые, 2 целые и/или мультимедийные, 2 вещественные).

В главе представлен сравнительный анализ наиболее актуальных архитектурных платформ типа EPIC - Эльбрус-ЗМ и IA-64 (Itanium Processor Family) по возможностям поддержки параллелизма на уровне команд. Важнейшие характеристики этих архитектурных платформ с явно выраженной параллельностью сведены в табл. 1. Первые 3 строки в таблице представляют линию Эльбрус-3 и Эльбрус-ЗМ: экспериментальный проект NArch - SPARC-совместимая разновидность архитектуры Эльбруса-3, и архитектура Е2К с х86-расширением системы команд и защищенным режимом программирования, наследующим контекстно защищенную архитектуру Эльбрусов. Перечислим важнейшие свойства, унаследованные этими новыми архитектурами от Эльбруса-3:

• принцип организации широкого командного слова переменной длины

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

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

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

• аппаратная поддержка оптимизации цикла методом совмещения итераций

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

В новых проектах дальнейшее развитие получила поддержка предикатных вычислений. Все операции могут быть поставлены в предикатный режим. К предикатным результатам, полученным операциями сравнения, применимы логические функции с подавлением дефектности второго операнда. При этом до 3 таких операций могут стоять в одной команде помимо основных арифметико-логических операций, что позволяет получать до 6 новых предикатов за такт. Более сбалансированными выглядят возможности задания различных арифметических операций в одном такте, что позволяет лучше планировать широкие команды для разных приложений с различными вариантами вычислений. В Е2К (см. табл. 1), по сравнению с 4-х канальной архитектурой NArch, увеличилась параллельность на уровне операций - 6 каналов АЛУ, стал большим парк исполнительных устройств, увеличился файл предикатных регистров, добавилась возможность задавать в одной широкой команде дополнительно 2 комбинированные трехаргументные операции для целых чисел и 4 комбинированные операции типа «умножить-и-сложить» для вещественных. И пиковые возможности такой архитектуры составляют выдачу за один такт 14 элементарных операций на скалярных целочисленных вычислениях, 16

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

Процессоры семейства Itanium на базе архитектуры IA-64 - это совместная разработка ведущих компьютерных фирм Intel и Hewlett-Packard, начатая в середине 90-х годов. При разработке архитектуры IA-64 достаточно много внимания было уделено аппаратной совместимости с кодами х86. Широкая команда в этой архитектуре представляется как две 128-разрядные связки (bundle) по 3 операции каждая. При этом в связку могут попадать зависимые по данным операции для получения более компактного кода, что отличает такие команды от классического VLIW варианта. Несмотря на наличие 3 отдельных устройств для выполнения переходов или 8 каналов АЛУ в процессоре Itanium-2 с очень большим парком исполнительных устройств, в одном такте может быть запущено на исполнение только 6 элементарных операций, в отличие от 10 до 15-17 операций за такт только у 4-х канальной NArch архитектуры. Другие главные отличия архитектур касаются спекулятивного режима исполнения операций, механизма подкачки кода при переходах и степенью поддержки оптимизации циклов совмещением итераций.

Таким образом, можно заключить, что Эльбрус-ЗМ и Itanium-2 имеют наиболее мощную архитектурную поддержку параллельности на уровне операций среди современных и разрабатываемых процессоров, что как раз и является важнейшим принципом архитектур типа EPIC.

Далее для прототипа и основного варианта архитектуры Эльбрус-ЗМ приведены структурные схемы, основные характеристики, а также возможности запуска различных групп операций за один такт, размещение их в каналах АЛУ и длительность исполнения. Отмечается, что для скалярного участка кода возможен пиковый выпуск 10 элементарных операций в такт в случае NArch, если к арифметическим добавить 3 операции управления и 3 операции над предикатами, и 12/14 операций в случае Е2К, если к арифметическим добавить 1 операцию управления и 3 операции над предикатами. При оптимизации цикла совмещением итераций есть дополнительные аппаратные возможности задания операций вычисления адресов элементов массивов, операций подкачки элементов массивов и операции продвижения счетчика цикла, что определяет для этого случая пиковый выход за один такт 15-17 операций NArch и больше 20 операций Е2К.

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

Главным итогом анализа, проведенного в разделе 1.1, является вывод

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

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

^ управляющие;

^ информационные;

по конфликтам доступа в память (по памяти);

предикатные.

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

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

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

та о. о н ш о 5

о л

I-

о (в X

к го

О Ф У 5

и се

Межпроцеду! оптим ный анализ и хзация

> >

Анализ и О] потока уг - тгимизации фавлсния -

Потоковый анализ и оптимизации

Первая фаза анализа и цикловых оптимизаций

-------------- - -------------------------- ^—- Промежуточное представление по линеиным участкам

" Перезод к преднкатнЬму*. * ' представлению (¡^сопмегпоп).'

ПреОикатное промежуточное предапаелете

Вторая фаза цикловых оптимизаций Оптимизация внутренних циклов методом совмещения итераций

' У/.,оптимизирующие'. _ • >, > 'преобразования по сокращению

. '^"лредакатн0ГО'у'"1ЦСГ1;а * • промежуточногопредставленю! '.У-. ' -•• у* .

I-

с О

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

Локальные оптимизации

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

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

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

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

Глава 2 посвящена переходу от промежуточного представления с линейными участками кода и условными переходами между ними к предикатному промежуточному представлению в виде совокупности расширенных .скалярных участков. Предикатное преобразование {if-conversion), осуществляющее этот переход, т. е. преобразование зависимостей по управлению в зависимости по предикатным данным, определяется как базовое оптимизирующее преобразование для архитектур типа EPIC, которые обеспечивают соответствующую

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

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

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

if (а > (b+c)) а = Ь-с;

а = а*а-с;

На рис. 2а представлено промежуточное представление фрагмента программы, разбитое на линейные участки Bl, В2, ВЗ, В4. Для операций на этих участках построен граф зависимостей по данным (см. пояснение для дуг и узлов, представленное на этом рисунке). В зависимости от условия (операция >) и соответствующего ему условного перехода на этом участке реализуется один из двух путей - В1—>В2—>В4 или В1->ВЗ—>В4. При длительности операций в тактах, равной следующим значениям: +, - и > -1 такт; * - 3 такта, статически спланированная длина путей получается 8 и 7 тактов соответственно. После применения преобразования if-conversion с необходимыми оптимизирующими преобразованиями контекста на границах линейных участков получаем один предикатный участок (рис. 26), который в оптимизирующем компиляторе был назван Расширенный Скалярный Участок - РСУ (Extended Scalar Block - ESB). При этом управляющая зависимость от условного перехода была преобразована в предикатную зависимость (по данным) операции vmergev («смеситель») от условия, которая пропускает на выход либо значение операции загрузки - "rd а4, либо значение операции вычитания в зависимости от значения предикатной операции больше (ЛОЖЬ или ИСТИНА, соответственно), что отражает формирование значения переменной а в точке схождения альтернатив на участок В4. При этом арифметическая операция ('-' на луче В2), которая была в альтернативе условного оператора, находится в спекулятивном режиме в РСУ и выполняется параллельно с вычислением условия (операции + и >), и ее неявная зависимость от этого условия разрешается тем, что результат этой спекулятивной операции проходит через операцию «смеситель». Длина полученного расширенного скалярного участка равна 7 тактам (или 5 при дальнейшем применении оптимизаций по сокращению критического пути - это будет показано в дальнейшем), что меньше или равно каждому из путей в первоначальном представлении данного фрагмента.

гН я гяъ:' гЛг.

■МТ:

■ гг1 с

гН г

•«та

а) Промежуточное представление по линейным участкам

гЛ я

б) Предикатное промежуточное представление — расширенный скалярный участок

V зависимость по данным

зависимость по управлению >- предикатная зависимость узел операция ор (ряв - на критическом пути)

фиктивный узел начала или конца участка

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

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

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

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

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

В конце главы приводятся экспериментальные данные по замерам производительности на целочисленных задачах из тестовых пакетов 5РЕСШ92 и БРЕСШ95. Дана методика проведения замеров на потактной модели архитектуры Эльбрус-ЗМ. Приведенные результаты показывают эффективность перевода программы в предикатное представление и использование его для оптимизирующих преобразований. Применение

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

Основным результатом, представляемым в этой главе, следует 1 считать то, что в инструментальном оптимизирующем компиляторе

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

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

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

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

предикатных зависимостей:

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

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

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

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

Оптимизация предикатной зависимости - исключение условия с критического пути (будем также называть этот метод «молния») применяется, если операция, задающая условие для выполнения необходимых предикатных операций, находится на критическом пути. Задача оптимизации - исключить такую операцию с критического пути и уменьшить его время. Искомая операция - условия определяется по операции «смеситель», которая в зависимости от значения условия (булевские ИСТИНА или ЛОЖЬ) пропускает на выход одно из двух входных значений. Операция «смеситель» может быть или представлена, или смоделирована в архитектуре с поддержкой предикатного режима исполнения операций. Она отображает в предикатном промежуточном представлении первоначальную точку схождения управления и позволяет в оптимизирующих преобразованиях рассматривать одновременно информационные и предикатные зависимости. Во время преобразования выполняются следующие действия. Операция, которая является преемником операции «смеситель», т. е. использует значение, выработанное ей, дублируется, так что вместо этого значения используется непосредственно одно из входных значений операции «смеситель». Полученные операции копии делаются входными для операции «смеситель». Использование последующими операциями значения, выработанного операцией преемником, заменяется использованием значения, полученного преобразованной операцией «смеситель».

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

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

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

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

Применение описанного оптимизирующего преобразования предикатной зависимости для примера, рассмотренного ранее (см. рис. 2), представлено на рис.3. На этом рисунке для каждой операции обозначены: верхней цифрой - время раннего запуска операции и нижней цифрой -время позднего запуска. Узлы графа с затемнением обозначают критический путь участка (равенство времен раннего и позднего), и длина участка до преобразования получается 7 тактов (от 0 до 6). При этом вычисление условия (операции + и > на рис. За) находится на критическом пути участка. В результате применения оптимизации условие (операции + и > на рис. 36) исключается с критического пути и длина пути сокращается до 6 тактов (от 0 до 5), что и было заявлено целью оптимизации.

Следующий метод оптимизации зависимости по доступу в память используется для сокращения критического пути, который определяется возможной (неразрешенной статическими методами) зависимостью, направленной от операции записи в память к операции считывания из памяти. Удаление такой зависимости и перестановка операций считывания и записи и, соответственно, уменьшение критического пути, основывается на возможности предикатного и спекулятивного режима исполнения операций. Для этого в рассматриваемый участок промежуточного представления вставляются операции, реализующие сравнение адресов рассматриваемых операций доступа в память при исполнении программы, и результат сравнения (результирующий предикат) используется для выбора значения, необходимого преемникам операции считывания. Т. е., по результату сравнения, указывающему совпадение адресов доступа в память, выбирается значение, записываемое операцией записи в память, а по предикату, задающему непересеченйЬ адресов, необходимое значение определяется операцией считывания, которая уже не зависит от порядка выполнения операции записи и может выполниться раньше неё. Такой выбор необходимого значения по предикату может быть реализован через операции пересылки в предикатном режиме или через операцию «смеситель», как это было реализовано в инструментальном оптимизирующем компиляторе. Таким образом, удаление зависимости, определяемой доступом в память и находящейся на критическом пути участка, а также возможность параллельного исполнения добавляемых операций, необходимых для сравнения адресов доступа, позволяет сократить критический путь участка.

Вставление оптимизирующего (кзакорачивающего») перехода

применяется для выравнивания времени исполнения взаимоисключающих множеств операций, зависящих от результата условия, при их совместном исполнении на расширенном скалярном участке. Альтернативные множества операций, каждое из которых зависит от результирующего значения операции условия (булевские ИСТИНА или ЛОЖЬ), могут иметь разное время завершения. Вставляемый оптимизирующий переход выполняется для одной из альтернатив, когда результат условия готов, так, чтобы в случае, когда альтернатива, имеющая меньшее время завершения, выбирается по условию, не было необходимости ожидать завершения оставшейся, более продолжительной части другой альтернативы. Т. е., оптимизация должна обеспечить выполнение каждой альтернативы за «свое» критическое время, сохранив при этом преимущества совместного исполнения части этих альтернатив параллельно с вычислением разрешающего условия. Если каждое из множеств операций завершается раньше условия, т. е. операция, вычисляющая условие, находится на критическом пути, то, применив сначала оптимизирующее преобразование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

Сдано в печать 18.11.03г. Формат 60x90/16 Объем 1,5 печ.л. Тираж 80 экз. Зак № 21

Отпечатано в ООО "Эдель-М" 105005, г.Москва, ул.Бауманская д.43/1

8ЕЧ 9299

J1J

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

Введение.

Глава 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. Вывод.

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

Актуальность работы. Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая всё более широкий круг проблем. И если в 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) Созданы функциональные компоненты инструментального оптимизирующего компилятора платформы прототипа Эльбрус-ЗМ, в составе которых реализованы следующие фазы платформо-ориентированных оптимизирующих преобразований:

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

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

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

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

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

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

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

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

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

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

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

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

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

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Ф

Похожие работы

Информатика, вычислительная техника и управление
05.13.00