Содержание к диссертации
Введение
Глава 1. Использование параллельности на уровне операций для получения эффективного кода 13
1.1. Архитектурная поддержка параллельности на уровне операции 14
1.1.1. Широкое командное слово, статическое планирование операций 14
1.1.2. Предикатный и спекулятивный режим исполнения операций 16
1.1.3. Аппаратные ресурсы архитектур с явно выраженной параллельностью 18
1.1.4.Краткое описание архитеюуры Эльбрус-ЗМ 25
1.2. Задачи оптимизирующего компилятора для архитеюуры с явно выраженной параллельностью 30
1.2.1. Промежуточное представление программы и отображение параллельности 32
1.2.2. Разбиение программы на участки и граф управления 39
1.2.3. Методы анализа и оптимизирующие преобразования программы 44
1.2.4. Генерация кода из промежуточного представления 52
1.3. Постановка задачи 53
1.4. Выводы 54
Глава 2. Предикатное промежуточное представление как совокупность расширенных скалярных участков 56
2.1. Переход к предикатному представлению 'if' conversion 56
2.1.1. Преобразование зависимостей по управлению к предикатным зависимостям, использование свойства спекулятивности для оптимизации предикатных зависимостей 57
2.1.2. Базовый регион предикатного промежуточного представления - расширенный скалярный участок (РСУ) 61
2.2. Алгоритм построения РСУ 66
2.2.1. Построение полных условий относительно точки входа в РСУ 69
2.2.2. Применение базовых преобразований контекстных операций на границах линейных участков , 72
2.2.3. Установление необходимых зависимостей по памяти, управляющих зависимостей и перевод операций с побочным эффектом в предикатную форму 76
2.2.4. Сложность алгоритма 81
2.3. Оптимальное использование совместного спекулятивного исполнения операций из нескольких альтернатив условных предложений 81
2.3.1. Использование профиля программы, взаимодействие с построением гиперблоков 82
2.3.2. Усложнение предикатного преобразования 85
2.4. Результаты, полученные на тестовых пакетах SPECint92 и SPECint95 86
2.4.1. Наборы тестовых программ 87
2.4.2. Экспериментальные результаты 87
2.5. Выводы 89
Глава 3. Использование стратегии критического пути в оптимизациях на основе предикатного представления программы 92
3.1. Разметка операций временем раннего и позднего запуска и критический путь участка
3.2. Оптимизирующие преобразования для предикатного представления программы, направленные на сокращение критического пути участка. 98
3.2.1. Исключение условия с критического пути 98
3.2.2. Удаление с критических путей потенциально зависимых последовательностей запись в память - считывание из памяти путем вставления динамического сравнения адресов 103
3.2.3. Балансировка критических путей РСУ, зависящих от условия 109
3.3. Результаты, полученные на тестовых пакетах SPECint92 и SPECint95 119
3.4. Вывод 122
Заключение 124
Литература 128
- Аппаратные ресурсы архитектур с явно выраженной параллельностью
- Методы анализа и оптимизирующие преобразования программы
- Базовый регион предикатного промежуточного представления - расширенный скалярный участок (РСУ)
- Удаление с критических путей потенциально зависимых последовательностей запись в память - считывание из памяти путем вставления динамического сравнения адресов
Введение к работе
Актуальность работы. Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая всё более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, её значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.
Ядром развития вычислительной техники с самого начала ее появления остается создание высокопроизводительных вычислительных систем. На протяжении последних десятилетий очень большое внимание уделяется проблемам распараллеливания вычислений. В этой области сосуществуют и активно развиваются два подхода к нахождению и использованию параллелизма вычислительных задач: распараллеливание на уровне процессов (многопроцессорные и массово-параллельные системы) и использование параллельности на уровне отдельных операций внутри одного процессора. В свою очередь распараллеливание на уровне операций может быть реализовано как аппаратными средствами во время исполнения программы (динамический подход), так и транслятором на этапе компиляции программы (статический подход).
Динамическое распараллеливание вычислении наиболее распространено в современных микропроцессорах и продолжает обеспечивать достаточную производительность исполнения вычислительных задач и совместимость программного обеспечения на ряде архитектур. Но дальнейшее увеличение параллельности на уровне операций в архитектурах процессоров может быть ограничено квадратичным усложнением логики проверок в аппаратуре при динамическом подходе к планированию команд. Поэтому статический подход к реализации пооперационной параллельности в процессе компиляции сейчас активно развивается как альтернатива суперскалярным (с динамическим планированием вычислений) процессорам. Для обозначения такого рода архитектур во второй половине 90-х годов появился термин -EPIC (Explicitly Parallel Instruction Computing) или архитектура с явно выраженной параллельностью на уровне команд.
В архитеюурах с явно выраженной параллельностью эффективное использование машинных ресурсов в большей степени определяется процессом компиляции исходной программы. Другими словами, нахождение максимального параллелизма программы на уровне операций, выражение его в промежуточном представлении и отображение в статически спланированный код - это главные задачи оптимизирующего компилятора, позволяющие получать эффективный результирующий код и обеспечивающие оптимальную загрузку процессора в архитектурах типа EPIC. Усложнение техники оптимизирующей компиляции, направленное на преобразование зависимостей между операциями и преодоление барьеров, мешающих параллельному исполнению операций, представляет один из главных резервов получения высокоэффективного кода, и увеличения производительности вычислений для архитектур с явно выраженной параллельностью. Особое внимание в данной работе уделено таким архитектурным свойствам как предикатность и спекулятивность, задающим условные режимы исполнения операций. Совместное использование этих архитектурных особенностей позволяет применять преобразования программы, переводящие динамически неоднозначные зависимости по управлению (от условных переходов) и по памяти (от операций обращения в память) в статически учитываемые зависимости по данным, преодолевая барьеры условных переходов и получая участки промежуточного представления программы со значительной параллельностью на уровне операций»
Цель диссертационной работы
Целью диссертационной работы является исследование проблем и подходов к
практическому решению задачи использования предикатных и спекулятивных свойств операций на фазе платформо-ориентированных оптимизирующих преобразований и ко до генерации. Это необходимо осуществить путем проектирования и реализации компонента, осуществляющего переход от промежуточного представления по линейным участкам к предикатному промежуточному представлению в оптимизирующем компиляторе для высокопроизводительной архитектуры Эльбрусом А также в рамках стратегии оптимизации ациклических (скалярных) участков программы необходимо разработать и реализовать в оптимизирующем компиляторе специфические оптимизирующие преобразования для предикатного представления программы, направленные на сокращение критического пути участка. Для достижения поставленной цели в работе выполняются следующие этапы:
исследование возможностей применения преобразования групповых управляющих зависимостей от условных переходов программы в предикатные зависимости одних операций от операций, вычисляющих условие, для архитектур с явно выраженной параллельностью;
разработка алгоритма преобразования промежуточного представления по линейным участкам в предикатное промежуточное представление {if-convershn)\
разработка алгоритмов специфических оптимизирующих преобразований для предикатного представления программы, направленных на сокращение критического пути участка при наличии и с использованием предикатных зависимостей;
реализация указанных алгоритмов в составе фаз платформо-ориентированных оптимизирующих преобразований инструментального оптимизирующего компилятора для архитектуры Эльбрус-ЗМ.
Предмет исследования составляют архитектурные и алгоритмические аспекты разработки оптимизирующего компилятора для высокопроизводительной вычислительной системы:
конкретные архитектурные решения, принятые разработчиками, и их влияние на применение оптимизирующих преобразований программы
общие и специализированные методы трансляции и их адаптация для конкретного вида промежуточного представления программы
алгоритмы оптимизирующих преобразовании программы для получения и работы на предикатном промежуточном представлении программы, их эффективность и сложность
конечная производительность и эффективность результирующего кода.
Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов. Архитектурные платформы исследовались методом сравнительного анализа. Эффективность объектного кода и конечная производительность оценивались путем замера времени исполнения б тактах пакета тестовых задач на потактной модели архитектуры в составе инструментального комплекса прототипа Эльбрус-ЗМ. Полученные данные для разных вариантов оптимизации транслируемой программы сравнивались между собой.
Научная новизна
Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, по преимуществу, составляют:
полномасштабное использование предикатных и спекулятивных свойств операций, а также других архитектурных возможностей, поддерживающих параллельность на уровне операций, в процессе оптимизирующей компиляции и получении кода архитектур с явно выраженной параллельностью;
разработанный алгоритм преобразования промежуточного представления по линейным участкам в предикатное промежуточное представление в форме совокупности расширенных скалярных участков;
разработанные оптимизирующие методы преобразования конкретных типов зависимостей, определяющих критический путь участка предикатного промежуточного представления программы
оптимизация предикатной зависимости - исключение условия с критического пути;
оптимизация потенциально возможной зависимости по конфликтам доступа в память от операции записи к операции считывания -удаление с критических путей потенциально зависимых последовательностей "запись в память - считывание из памяти'1 путем вставления динамического сравнения адресов;'
балансировка критических путей в РСУ, зависящих от условия -вставление переходов для оптимизации критических путей, зависящих от предиката.
Практическая ценность результатов работы состоит в том, что на основе замеров производительности была произведена оценка применения базовых оптимизирующих преобразований и использования важнейших аппаратных свойств данной архитектуры с явно выраженной параллельностью на уровне операций (Эльбрус-ЗМ). Эти оценки, с одной стороны, подтверждают правильность выбранных архитектурных решений, ооеспечивающих высокую эффективность результирующего кода проектируемой архитектуры. С другой стороны, подтверждение получили выбранные стратегии оптимизации программы. Кроме того, были выявлены возможные неоптимальности перехода к предикатному преобразованию программы, недостатки во взаимодействии и реализации различных анализирующих и оптимизирующих фаз
процесса компиляции, и, соответственно, определены подходы и методы решения обнаруженных проблем. Опыт эксплуатации инструментального компилятора позволил оптимизировать многие архитектурные параметры будущего микропроцессора. Полученный опыт реализации и тестирования фазы платформо-ориентированных оптимизирующих преобразований в составе инструментального оптимизирующего компилятора учтен и использован при проектировании промышленного оптимизирующего компилятора.
В процессе выполнения диссертационной работы получены следующие практические результаты:
Все разработанные алгоритмы реализованы автором в составе инструментального оптимизирующего компилятора с языков высокого уровня "С", "Фортран-77" для прототипа Эльбрус-ЗМ, позволяющего получать оптимизированный код данной платформы с предикатными и спекулятивными свойствами операций.
Инструментальный компилятор как конечный продукт вошел в состав Инструментального программного комплекса и программных средств обеспечения совместимости МВК " Эльбрус-ЗМ " с МВК " Эльбрус-2 ", " Элъбрус-Г.
Результаты работы нашли применение при проектировании промышленного компилятора.
Апробация
Результаты работы докладывались на 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.: February4, 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,3721B. 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 Stales 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.
Краткое содержание работы.
Аппаратные ресурсы архитектур с явно выраженной параллельностью
Пионерской работой в области статического распараллеливания скалярных вычислений, имевшей некоторый коммерческий успех, была машина FPS-164 [8]- В этом проекте был сделан существенный шаг - кроме параллельных арифметических устройств и устройств памяти, также произошло распараллеливание потайного управления командного потока, т.е. введение широкого командного слова (64 бита), управляющего всеми независимыми функциональными устройствами. Поскольку при задании объектного кода для такой архитектуры необходимо учитывать временные соотношения операций в программе и детальную структуру машины, то уровень трансляции программы должен быть не доступен программисту. Для решения этой задачи в FPS пришлось сузить область применения процессора только научно-техническими вычислениями и ориентироваться на создание оптимизирующего транслятора с Фортрана. Поэтому был слабо поддержан процедурный механизм, труднореализуемы прерывания, неэффективно реализованы условные предложения и, следовательно, практически использовался параллелизм только внутри линейного участка [8],
При работе над архитектурой TRACE фирмы Multiflow [6], для увеличения использования параллельности на уровне операций за границами линейных участков был разработан компиляторный метод Trace Scheduling [2, 5-6]. Идея этого метода основывается на предположении о том, что условные переходы с большой вероятностью происходят по одному и тому же направлению при различных входных данных и, если рассматривать переход по этому направлению как безусловный, то появляются дополнительные возможности совмещения операций на больших участках программы. Оценки направления переходов или их вероятности можно получать, используя профилирование программы или статическое предсказание переходов. Используя эти оценки, компилятор выбирает путь или трассу по линейным участкам через все переходы с направлением наибольшей вероятности, и рассматривает эту трассу как единый участок, который компакгирует (планирует) оптимальным образом в длинные командные слова. При этом возможно перемещение операций выше и ниже условных переходов, что требует от компилятора вставлять компенсирующий код на ветви входа в трассу и выхода из нее для корректности исполнения программы. Затем процесс повторяется для следующей наиболее вероятной трассы, которая может включать первоначальный код и компенсирующий код от предыдущей итерации. Таким образом, компилятор преодолевает границы линейных участков и находит параллелизм на более длинных потоках команд. За счет компенсирующего _кода возможно увеличение кода всей программы. Но так как дополнительный код приходится на трассы с меньшей вероятностью исполнения и благодаря высокой параллельности VI/lV-архитектуры должно достигаться ускорение программы.
Trace Scheduling предоставляет достаточно ясные и простые критерии для глобального перемещения операций при трансляции прикладных программ с точными профильными данными и интенсивными цикловыми вычислениями. Это характерно для научно-технических счетных задач, В программах с более сложным поведением управления и более скалярными характеристиками такой метод будет гораздо менее эффективным и/или более сложным в реализации. Также необходима отметить, что основной подход к оптимизации циклов для данной разработки базировался на раскрутке циклов, что не давало возможности оптимально транслировать многие случаи встречающихся в программах цикловых регионов.
Таким образом, первоначальные разработки УЇЛ -архитектур фирм Multiflow [6] и Cydrome [9-10] были направлены на использование в области численных научных вычислений и имели серьезные недостатки при исполнении программ универсального применения. Поэтому эти проекты не получили дальнейшего развития и, соответственно, внедрения. С конца 80-х - начала 90-х годов идея архитектуры со статическим планированием вычислений продолжала развиваться в нескольких коллективах - проекты Элъбрус-3 [11-13], Эльбрус-ЗМ (NArch9 Е-2к) [14-18], HPL -PlayDoh [19],, IMPACT [20-21], HP/Intel - Itanium Processor Family (IPF) [22-25]. При этом ставилась задача разработки архитектуры универсального применения, дающей возможность получения высокоэффективного кода для широкого класса задач. Значительным шагом для поддержки параллелизма на уровне операций стали новые архитектурные черты - спекулятивный и предикатный режим исполнения операций1 (speculative and predicated execution), которые стали проникать и в архитектуры с динамическим планированием операций (суперскалярные). Кроме тогот использование некоторых архитектурных особенностей суперскаляров, испытанных на практике, могло бы позволить улучшить динамические характеристики новых архитеюур. Поэтому, во второй половине 90-х годов появился новый термин, определяющий архитектуры такого рода - EPIC (Explicitly Parallel Instruction Computing) или архитектура с явно выраженной параллельностью на уровне команд [20-22].
Определим архитектурные свойства спекулятивности и предикатности. Спекулятивность - условное исполнение с отложенным прерыванием, которое в случае его возникновения фиксируется в операции как дефектное или недопустимое значение результата. Это дефектное значение далее распространяется по спекулятивным операциям, использующим это значение, и останавливается на некоторых предикатных операциях, которые не пропускают это значение, обеспечивая «гладкое», без прерываний выполнение операций для нормального случая. Отложенное прерывание может произойти на операции, стоящей не в спекулятивном режиме, в случае, если это требуется программой, или в случае ошибки исполняемой программы или ошибки самого компилятора. Это распространенная схема реализации механизма спекулятивности операций. Возможны и другие схемы взаимодействия спекулятивной и не спекулятивной операций и реакции на возникновение прерывания на операции в спекулятивном режиме [1].
Спекулятивный режим исполнения устанавливается для всех операций в альтернативе условного предложения при совместном исполнении альтернатив, атакже для операций, использующих результат такой операции, которая может вызвать прерывание и она поднимается выше некоторого условного перехода (т. е. может исполниться раньше, чем выполнится переход), контролирующего возникновение этого прерывания. По существу спекулятивность означает исполнение операций «на всякий случай» по нескольким возможным путям управления программы, до того как станет известно условие, выбирающее какой путь должен исполниться. Поэтому блокировка прерываний необходима, чтобы не помешать выполнению полезных вычислений со стороны той части спекулятивных операций» которые в итоге окажутся невостребованными.
Свойство предикаптости - это условное выполнение операции в зависимости от значения предиката - результата операции, вычисляющей условие. Другими словами, операция в предикатном режиме либо выполняется, либо аннулируется, не сохраняя результата, в зависимости от условия. Это свойство используется для реализации слияния информационных потоков в точке соединения условного предложения, а также для преобразования зависимости по управлению между операциями с побочным эффектом и условным переходом в предикатную зависимость этих операций.
Методы анализа и оптимизирующие преобразования программы
Промежуточное представление фиксирует состоянне(я) программы в процессе компиляции от исходной записи на входном языке до выходного состояния — целевого исходного кода программы исполняемой на заданной платформе. Основные функции промежуточного представления: отображение и сохранение инвариантной семантики исходной программы базис для проведения анализа и оптимизирующих преобразований программы интерфейс взаимодействия со всеми фазами компиляции, позволяющий фиксировать и передавать изменения программы. Конечно, одна из главных причин введения и широкого использования различных видов промежуточного представления программы и вспомогательных надстроечных структур над ним - это необходимость при оптимизирующей компиляции иметь форму представления, позволяющую эффективно применять мощный набор алгоритмов анализа и оптимизирующих преобразований программы.
По отношению к исходному состоянию программы на языке высокого уровня (ЯВУ) можно выделить три уровня промежуточного представления программы. Это высокий (hir), средний (mir) и низкий (Ііг) уровни промежуточного представления [30, гл. 4], А, соответственно, с точки зрения целевого объектного кода можно характеризовать промежуточное представление как машинно-независимое (платформо-независимое) и машинно-зависимое (гшатформо-зависимое). Легче всего охарактеризовать крайние фазы процесса компиляции. Фронтальная фаза синтаксического разбора исходной программы использует синтаксическое дерево как выходное промежуточное представление. Оно является достаточно близким к языковому уровню и потому оно - промежуточное представление высокого уровня. А, с другой стороны, в нем еще не конкретизированы особенности целевой платформы и потому оно характеризуется как платформо-независимое. Очень часто эта часть компилятора выступает как независимый программный продукт. Противоположный пример - это фазы генерации кода, конечного распределения регистров (ресурсов), а также ассемблерный компонент компилятора. Естественно, что промежуточное представление, необходимое в данном случае, похоже на язык ассемблера, является представлением низкого уровня и платформо-зависимым.
Особенности и свойства промежуточного представления программы на других фазах компиляции определяются задачами, решаемыми этими фазами. Поэтому проектирование одного или нескольких видов промежуточного представления, удовлетворяющего требованиям разнообразных аналитических и оптимизирующих фаз компилятора, очень сложная и не формализуемая (близкая к искусству?) задача. Например, в компиляторе ncomp межпроцедурный анализ (іра) и оптимизации (inline и cloning) выполнялись на синтаксическом дереве программы, полученном фронтальной фазой. Действительно, для іра валено компактность представ л ения, наиболее полное отображение информации о функциях, типах, переменных, ссылках и пойнтерах, и несущественна машинная конкретизация. Однако, проектируемая модернизация межпроцедурного анализа, усложнение его алгоритмов свойствами потокового анализа, возможный учет управляющих свойств программы, показали, что свойства синтаксического дерева не удовлетворяют новым требованиям этой фазы- Поэтому при переходе к ecomp, вызвавшему редизайн компилятора, было спроектировано новое промежуточное представление еїг (Elbrus intermediate representation). Оно удовлетворяло спецификациям іра и работе с программой как с целым, т. е. возможностью иметь одновременный доступ к любым объектам программы» что означает необходимость иметь отображение промежуточного представления на файле и, соответственно, функции сброса и восстановления на файл. Его можно охарактеризовать как платформо-независимое представление среднего уровня. После введения такого промежуточного представления, следующим шагом стало проектирование и создание платформо-зависимого представления низкого уровня для поддержки фаз машинно-зависимых оптимизирующих преобразований и кодогенерации. И вообще, расположение и взаимодействие различных оптимизации, а также аналитических фаз, очень трудная задача, проработанная лишь в общих чертах. Такое взаимодействие для многих компиляторов выстраивается случайным образом.
Основными элементами промежуточного представления для отображения семантики программы являются операции и контекст, в том числе константы. С помощью понятая контекста отображается множество объектов, порождённое исходной программой, а операции отображают действия над элементами контекста и последовательность их выполнения- Выполнение программы определяется пространством значений и последовательностью команд, выполняемых над ним. Во время работы кода программы на целевой машине пространство значений суть физическая память машины, В ЯВУ оно определяется конструкциями. описания переменных и функций, т.е. описания определяют количество физической памяти, необходимой для хранения информации, время выделения памяти и возможные операции обработки этой информации. При написании программы на ЯВУ программист оперирует не понятием физической памяти, а понятиями переменная -место хранения информации, и процедура - последовательность операций над переменными. Множество переменных и процедур, описанных в программе, можно назвать контекстом программы уровня языка программирования.
Моделирование выполнения программы в процессе компиляции, необходимое для реализации алгоритмов анализа и оптимизаций, базируется на понятиях контекстного объекта, класса и функционального объекта.
Понятие контекстного объекта, далее объекта, есть абстракция локализации (области памяти), необходимой для хранения информации, порождаемой вычислениями, для ее последующего использования в программе. Изменение уровня абстракции объекта в процессе трансляции программы от исходного текста программы, через промежуточное представление для анализа и оптимшации и до результирующего кода программы представлено на рис. 5. Хранимая информация называется значением объекта. Другим важным атрибутом контекстного объекта является tvo идентификация или путь доступа к занимаемой области памяти . Класс (объектов), есть абстрактное представление типизации в языках программирования. Это понятие позволяет группировать объекты, обладающие общими свойствами. Класс и принадлежащий ему объект соотносятся следующим образом: каждому классу соответствует множество операций, применимых ко всем объектам данного класса; каждый объект класса обладает собственным состоянием; любой объект принадлежит некоторому классу (при создании объекта определяется его начальное состояние, после чего все операции, допустимые в данном классе, могут быть к нему применены). В основном понятие класса вводится для представления внутренней структуры составных объектов. Фупщиопаїьшй объект (ompaimn или операторный элемент) есть абстракция преобразователя информации. Операторный элемент - это набор операций, обладающий некоторыми заданными свойствам!!. Функциональную модель операции можно представить следующим образом,
Базовый регион предикатного промежуточного представления - расширенный скалярный участок (РСУ)
Архитектуры с явно выраженной параллельностью добавляют в пространство, в котором выполняются вычисления, новую координату - предикатную. Это заключается, во-первых, в том, что каждая операция получает возможность иметь дополнительный предикатный операнд, который отображает зависимость от операции-условия, вырабатывающей этот предикат. Во-вторых, в процессоре появляется соответствующая предикатная область памяти - предикатный регистровый файл, служащий для хранения значений предикатов. Такое расширение архитектурного пространства вычислений направлено на поддержку параллельности на уровне операций, и задача оптимизирующего компилятора (см» рис. Ив главе 1) состоит в том, чтобы максимально эффективно для транслируемой программы использовать это пространство. Как уже отмечалось в предыдущей главе, базовым оптимизирующим преобразованием, которое обеспечивает значительное увеличение параллельности на уровне операций, является преобразование промежуточного представления с линейными участками кода и условными переходами между ними к предикатному представлению программы, в котором большая часть переходов удалена, а управляющие зависимости, выражавшиеся ими, переведены в предикатные зависимости одних операций от операций, вычисляющих условие. Такое преобразование зависимостей по управлению в зависимости по данным рассматривалось еще до появления архитектурной поддержки предикатного исполнения операции и было названо - if-conversion [46]. Это преобразование обеспечивает добавление предикатных свойств в промежуточное представление, и для архитектур типа EPIC которые обеспечивают соответствующую архитектурную поддержку /LP-параллелизму, применение if-conversion и переход к предикатному представлению программы становится, по-настоящему, эффективным. Важнейшими архитектурными свойствами, используемыми данным оптимизирующим преобразованием для этого, являются предикатный и спекулятивный режим исполнения операций, которые были определены в подразделе 1.1.2,
Преобразование зависимостей по управлению к предикатным зависимостям, использование свойства спекулятивности для оптимизации предикатных зависимостей
Разбиение промежуточного представления по линейным участкам (лучам), представленное в подразделе 1.2.2, выполняется по управляющим операциям, которые завершают линейные участки, и отражает групповым образом управляющие зависимости от этих операций к операциям на последующих линейных участках. Для примера на рис. 9 от условного перехода на луче В1 зависят операции с участков В2 и ВЗТ а точка схождения управления, луч В4, отображает зависимость от предыдущих линейных участков. В конечном итоге, исполнение или не исполнение операций на участке В2, зависит от условия ( ), которое является операндом условного перехода. Поэтому, используя предикатные свойства операций, косвенное влияние условия на исполнение операций, реализуемое через условный переход, можно заменить явными предикатными зависимостями каждой операции от условия и удалить условный переход. Свойство спекулятивности, определенное в подразделе 1.1.2 как условное исполнение с отложенным прерыванием, позволяет оптимизировать предикатную зависимость, то есть делать ее неявной и удалять из графа зависимостей. Тогда использование значения спекулятивной операции должно приводить по каждому пути исполнения к предикатной операции, где эта неявная зависимость будет разрешена предикатным операндом - управляющим условием для сохранения корректности исполняемой программы. Такая модель предикатного промежуточного представления позволяет не иметь в архитектуре специальных операций (типа check), где бы проверялись значения спекулятивных операций, и нужно было делать откат. Таким образом, предикатный режим исполнения операций позволяет сформировать внешний контекст преобразуемого региона в зависимости от условий ветвления внутри региона, то есть эквивалентным образом как до предикатного преобразования. Для этого контекстные операции и операции передачи управления, которые формируют внешний контекст региона, должны иметь предикатную зависимость от соответствующего условия, которое вычисляется по отношению к входу в рассматриваемый регион. В то же время всем арифметическим операциям, которые находятся в альтернативах условных предложений внутри региона, достаточно установить спекулятивный режим исполнения, так как они формируют только промежуточные результаты вычислений на линейных участках в выбранной в компиляторе потоковой форме промежуточного представления. Для отображения точек схождения альтернатив условного предложения в предикатное промежуточное представление вводится специальная операция смеситель (по аналогии с соответствующей операцией в потоковых машинах), которая пропускает на выход либо значение своего первого операнда, либо значение второго операнда в зависимости от значения предикатного операнда. В архитектуре с предикатной поддержкой такая операция может бьпь задана явно в системе команд (ЭльбруоЗ, Е2К), или реализована с помощью операций пересылки в предикатном режиме (NArch). Специально проведенные исследования показали, что интегрированное использование и предикатного, и спекулятивного режима исполнения операций в предикатном промежуточном представлении дают более эффективный код, чем в случае использования этих свойств операций по отдельности [21].
Частичный порядок операций в потоковом промежуточном представлении задается графом зависимостей. Поэтому при выполнении if-conversion необходимо достроить граф зависимостей для получаемого предикатного участка промежуточного представления. Для этого на границах линейных участков проводятся преобразования контекстных операций и перенос необходимых зависимостей (по памяти и управляющих), которые будут рассмотрены в параграфе 2,2.3.
Удаление с критических путей потенциально зависимых последовательностей запись в память - считывание из памяти путем вставления динамического сравнения адресов
Сложность алгоритма, главным образом, определяется перестроением графа зависимостей - базовыми преобразованиями контекстных операций на границах линейных участков, т, е. работой процедуры обработать_коіітскст_на_грапице_луча_1 в цикле обхода региона. Внутри этой процедуры выполняется цикл по всем операциям записи, которые доступны Б рассматриваемой точке обхода, И для каждого объекта, соответствующего операции записи, просматриваются все операции доступа в память на следующем участке, чтобы определить операции доступа к одному и тому же объекту и затем применить описанные выше преобразования, а также найти конфликтующие операции и установить необходимые зависимости» Поэтому сложность алгоритма можно оценить как 0(N N_ST__OP N_BB_MEMOP)t где N - число линейных участков в преобразуемом регионе, N_ST_OP - число операций записи в регионе, NJ$B__MEMQP-максимальное число операций доступа в память на одном луче, С учетом граничных условий предикатного преобразования, а, именно, некоторого предела для числа операций на одном луче (считаем множитель NJBBJdEMOP константным), упрощенная оценка сложности будет - 0(N N_MEMOP), где N_MEMOP - число операций доступа в память в регионе.
Необходимо отметить, что значительное увеличение параллельности на уровне операций на расширенных скалярных участках происходит во многом за счет совместного спекулятивного исполнения операций с нескольких альтернатив условных предложений; Это, так называемый, гш-тралледизм, который означает, что если несколько путей по управлению из начального региона полностью включены в построенный расширенный скалярный участок и имеют общий выход из него, то у них получается одинаковое время исполнения, равное длине спланированного кода от начала участка до рассматриваемого выхода, тогда как до преобразования длины путей могут сильно отличаться. Другими словами, после предикатного преобразования мы получаем некоторый обобщенный критический путь, который соответствует нескольким путям по управлению в промежуточном представлении по линейным участкам. В общем случае, при наличии нескольких выходов из РСУ, число таких критических путей равно числу выходов. Для простого примера, рассмотренного в подразделе 2ЛЛ, обобщенный критический путь полученного участка после предикатного преобразования меньше, чем длина каждого из первоначальных путей по управлению. В произвольном случае длина какого-то из путей до преобразования может оказаться меньшей, чем длина обобщенного критического пути в предикатном представлении. Это может быть связано либо с наличием зависимостей, имеющих большую задержку, либо с большим количеством операций на альтернативных путях по управлению, что приводит к удлинению обобщенного критического пути. Такого рода неоптимальности предикатного преобразования можно назвать избыточным или-параллелизлюм іти избыточной спекулятивностью. Здесь мы перечислим некоторые методы, позволяющие уменьшать эту избыточную спекулятивность и улучшать эффективность перехода к предикатному представлению.
Один из них - это определение границ региона, к которому применяется if-conversiont т. к. структура графа управления задает пути в регионе и количество выходов из него. На основе предварительного профилирования программы, выбираются ациклические регионы с часто исполняемыми путями по управлению, включающими точки схождения. И они могут быть использованы как входные регионы для предикатного преобразования программы. В литературе такого рода регионы были названы гиперблоками [48]. При наборе пшерблоков, т. е. выделении соответствующих регионов . программы, кроме частотных эвристик, полученных на основании профильной информации или вычисленных статически, можно использовать также количественные оценки включаемых линейных участков по числу операций и длине критического пути участка, чтобы сбалансировать пути по управлению и уменьшить избыточную спекулятивность. Этот метод можно считать существенным приближением по уменьшению избыточной спекулятивности после применения if-conversion к выделенному алгоритмом региону. Он характеризуется также невысокой алгоритмической сложностью, но в то же время недостаточной точностью по сбалансированности различных путей, зависящих от предикатов, т. к. оценки, участвующие в эвристиках алгоритма, могут быть получены лишь по линейным участкам, т. е. как предварительные по отношению к построенному расширенному скалярному участку , Неточность этого метода может проявиться и в случае, когда недоступен профиль программы, и эвристики основываются на статических предсказаниях переходов [36-38]. В целом, можно считать, что это неточности второго порядка, не сильно влияющие на эффективность перехода к предикатному промежуточному представлению. Расширенный скалярный участок из задачи compress, приведенный в качестве примера в параграфе 2.2.3, основывался на начальном выделении регионов алгоритмом набора гиперблоков.
Дадим краткую характеристику этого алгоритма, реализованного в компиляторе ncomp разработчиком фазы высокоуровневых преобразований управления, В результате работы алгоритма определяется совокупность ациклических регионов -гиперблоков, которые являются входными регионами для предикатного преобразования программы и удовлетворяют требованиям, описанным в параграфе 2.2. L Данный алгоритм основывается на результатах, полученных в ходе анализа управления и структурного анализа, а именно на информации о границах циклов, об обратных дугах, о глобальных метках, о точках схождения, соответствующих точкам разветвлений. Эвристики алгоритма набора пшерблока базируются на достаточно большом количестве граничных параметров, которые получаются из профильных данных (счетчики выполнения узлов и дуг графа управления), числа операций каздого луча и информации о наличии на линейном участке вызова и записей по неизвестным указателям. Главный принцип (или простейшая эвристика) включения узла графа в гиперблок выглядит так: включаем узел N в гиперблок, если counter(N) /counter(HB_HD) = 0Jr где HB__HD - головной узел гиперблока (если узел N содержит вызов» то к нему можно применить более жесткое условие: counteriN) / counter(HB_HD) = 0.2). Алгоритм набора начинается с выбора головного узла гиперблока, который должен удовлетворять следующим условиям:
