Содержание к диссертации
Введение
1. Анализ методов планировании для архитектур с явной параллельностью 1.1. Анализ прмпскіур с явной параллельностью 8 1.2. Статическое планирование операции 13 1.2.1. Зависимости по управлению и по данным 1.2.2. Контекст алгоритмов статического планирования 1.2.3. Место статического планирования в схеме оптимизирующей трансляции 1.3. Мегоды статического планировании 18 1.3.1. Планирование по списку 1.3.2. Планирование трассы 1.3.3. Суперблок и Гнперблок 1.3.4. Планирование по дереву доминирования 1.3.5. Конвейеризация циклов 1.3.6. Планирование с учетом задержек между линейными участками 1.3.7. Планирование техникой просачивания 1.3.8. Планирование волнового фронта 1.4. Проблемы н недостатки существующих методов 28 1.5. Постановка задачи 29 1.6. Выводы '. 30 2. Глобальное планирование в рамках ациклического региона 31 2.1. Общее описание алгоритма набора пшерблоков 31 2.1.1. Описание схемы отказа 2.1.2. Оценка эффективности одного шага алгоритма 2.1.3. Алгоритм набора гиперблоков 2.1.4. Стратегии набора 2.1.5. Экспериментальные результаты 2.2. Граф зависимостей ЗУ 2.2.1. Алгоритм построения зависимостей 2.2.2. Коррекция зависимостей на каждом шаге алгоритма 2.2.3. Минимизация графа зависимостей 2.2.4. Результаты тестирования 2.3. Переход к предикатному представлению - if-conversion 44 2.3.1. Построение предикатов для архитектуры 'Хтьбруе-ЗМ 2.3.2. Построение предикатов для архитектуры Itanium 2.4. Использование спекулятивного режима 47 2.4.1. Спекулятивность по управлению без построения компенсирующего кода 2.4.2. Спекудяїиішоеть по управлению и по данным с построением компенсирующею кода 2.4.3. Иепользоилние спекулятивного режима на 'кане планирования 2.5. Оптимизации, шелючешнле в схему планировании 50 2.6. Коррекция анализичеекпх структур данных 50 2.6.1. Коррекция і рафа управления 2.6.2. Коррекция глобального графа потока данных 2.6.3. Коррекция информации о зависимостях по управлении) 2.7. Экспериментальные результаты 58 2.S. Выводы 5 3. Глобальное планирование за пределами ациклических регионов 60 3.1. Общее описание алгоритма глобального планировании 60 3.2. Граф зависимостей 60 3.2.1. Алгоритм построения зависимостей 3.2.2. Коррекция зависимостей при переносе операций 3.2.3. Результаты тестирования 3.3. Информация о времени жіпни объектов 64 3.4. Построение предиката операции 68 3.5. Оптимизации, включенные в схему планировании 73 3.6. Коррекции аналитических структур данных 74 3.6.1. Коррекция графа управления 3.6.2. Коррекция глобального графа потока данных 3.6.3. Коррекция информации о зависимостях по управленню 3.6.4. Коррекция результати индексного анализа 3.7. Алгоритм глобального планировании 85 3.8. Экспериментальные результаты 98 3.9. Выводы * 99 Заключение 100 Список литературы Введение к работе Лкіул.іьішеїь работы. Вычисли іельная техника н настоящее время непользуется практически ко всех областях человеческой деятельности. Многие передовые страны мира рассматривают задачу создания вычислительных технологии как одно из приоритетных направлений своего развития. Если проследить историю развития вычислительной техники, то можно увидеть, что за несколько десятилетий область ее применения достигла оіромньгх масштабов. Житнь современного человека немыслима бет использования вычислительной техники. Важным фактором, определяющим уровень развития вычислительных систем, является их производительность, то есть скорость вычислений. Одним из способов повышения производительности является тактовая частота, с которой работает вычислительная система. Другим способом является логическая организация вычислительного процесса. На протяжении последних десятилетий очень большое внимание уделяется проблемам распараллеливания вычислений. Вычислительные задачи могут быть распараллелены как на уровне процессов, то есть когда исполняются одновременно несколько подзадач, так и на уровне элементарных инструкций (операций) вычислительной системы. Распараллеливание операций реализуется двумя способами - динамически или статически. Динамическое распараллеливание происходит в момент исполнения программы аппаратными средствами. Статическое распараллеливание осуществляется на этапе компиляции программы. В настоящее время в современных микропроцессорах широко используются оба подхода к распараллеливанию вычислений на уровне инструкций. Динамический подход позволяет, не меняя исходные коды пропэаммного обеспечения, повышать параллельность за счет усложнением логики проверок в аппаратуре при планировании команд, тем самым, обеспечивая совместимость программного обеспечения па ряде поколений микропроцессоров. К недостатку динамического подхода можно отнести необходимость ограничивать сложность алгоритмов планирования, так как повышение сложности ведет к увеличению времени, затрачиваемого на динамическое распараллеливание. Этот недостаток удается преодолеть при статическом по;іходе. когда распараллеливание инструкций происходит на этапе компиляции программы. Для обозначения процессоров, устройство которых использует принципы динамического подхода, применяется термин суперскалярная архитектура. Для обозначения процессоров, устройство которых использует принципы статического подхода, применяется термин EPIC (Explicitly Parallel Instruction Computing) или архитектура с явно выраженной параллельноетью на уровне команд. В архитектурах с явно выраженной параллельностью эффективное использование машинных ресурсов в большей степени определяется процессом кочшгляции исходной программы. Другими словами, нахождение максимального параллелизма программы на уровне операций, выражение его в промежуточном представлении и отображение в статически спланированный код - это главные задачи оптимизирующего компилятора, позволяющие иолучаїь эффективный результирующий код и обеспечивающие оптимальную загрузку процессора и архитектурах типа EPIC Развитие методов статического планирования программ является одним из глаьных резервов, позволяющих эффективно использовать ресурсы процессора для одновременного исполнении независимых вычислений в программе. Особое внимание в данной работе уделено таким методам статического планирования программ, как планирование в рамках ациклических регионов программы, а также планирование за пределами ациклических. Использование этих методов позволяет добиваться полноценного использования таких архитектурных особенностей ЕРІС- архитектур как широкая команда, предикатным и спекулятивный режимы исполнения инструкций, Цель диссертационном работы Целью диссертационной работы является исследопание проблем и подходов к практическому решению задачи статического планирования операций ятя архитектур с явным параллелизмом. Для достижения поставленной цели в работе выполняются следующие этапы; исследование современного уровня развития методов статического планирования программ и возможностей их использования в промышленных оптимизирующих компиляторах; разработка эффективного алгоритма планирования ациклических реї ионов програм мы; разработка эффективного алгоритма планирования произвольного участка программы; разработка методов оценки эффективности планирования; t разработка механизмов интеграции оптимизирующих преобразований в алгоритмы планирования; разработка механизма использования аппаратной поддержки спекулятивных вычислений в алгоритмах планирования; разработка оптимизирующих преобразований для интеграции в алгоритмы планирования; разработка алгоритмов построения и коррекции зависимостей для произвольного участка пропэаммы; разработка методов сохранения информации о зависимостях по управлению на этапе планирования; разработка алгоритма построения предикатного выражения для произвольного пути программы; разработка алгоритмов коррекции глобального графа потока данных па этапе планирования; разработка методов коррекции информации о времени жизни объектов на зіапе планирования; разработка методов коррекции аналитической информации о циклах на этапе планирования; реализация указанных алгоритмов в составе оптимизирующего компилятора ятя архитектуры Ольбруе-ЗМ. Предмет исследовании составляют алгоритмические аспекты разработки оптимизирующих компиляторов для высокопроизводительных вычислительных систем; методы статического планирования программ с точки зрения их эффективности и возможности применения в кошексте промышленных оптимизирующих компиляторов; оценка влияния методов статического планирования программ на конечную производительность и эффективность результирующего кода. Методы исследовании заимствованы из областей системного программирования, технологии компиляции, теории графов, теории диофантоиых уравнений и неравенств, математической логики. Путем измерении ключевых параметров, оценивалась эффективность предложенных методов. Для проведения замеров использовался инструментальный комплекс в составе оптимизирующего компилятора и поіакгной модели архитектуры ')льбруе-ЗМ. Замеры производились на пакете задач Spee.45. Научная новизна Решение поставленных в диссертационной' рабо іє задач определяет научную новизну исследования, которую, по преимуществу, составляют: разработка эффективного алгоритма планирования ациклических областей программы; разработка эффективного алгоритма планирования произвольного региона программы; разработка техники отката на этапе планирования, позволяющей точно определять эффективность планирования, а также интегрировать в алгоритма планирования оптимизирующие преобразования, повышая тем самым эффективность планирования; разработка двухуровневой схемы планирования, состоящей в последовательном использовании алгоритмов планирования ациклических областей программы И алгоритма планирования произвольного региона программы; разработка алгоритма построения графа зависимостей и методов их коррекции на этапе планирования; разработка методов сохранения информации о зависимостях но управление после преобразования потока управления в поток данных на :угапе планирования; разработка алгоритма построения предикатного выражения для произвольного пути в программе; разработка методов коррекции глобального графа потока данных на :ггалс планирования; разработка метода использования аппаратной поддержки спекулятивны* вычислений в алгоритмах планирования; разработка методов коррекции анхштическон информации о зависимостях f* циклах на этане планирования. Практическая ценность результатов работы состоит в том, что на основе предложенных в работе методов были разработаны критичные с точки зрения производительности вычислительного комплекса алгоритмы промышленного оптимизирующего компилятора для архитектуры Эльбрус-ЗМ. В процессе выполнения диссертационной работы получены следующие практические результаты: Все разработанные алгоритмы реализованы в составе оптимизирующем41 компилятора для архитектуры Ольбрус-ЗМ. Выявились дальнейшие направления исследований в области развития методов статического планирования программ. Апробации Результаты работы докладывались па Международной молодежной научиоП конференции "XXX Гагаринекие чтения" (Москва, 2005 г.), на IX Санкт-ПегербургскоГ' Международной конференции "Региональная информатика - 2004" (PH-2U04) в 2004 г--XXI научно-технической конференции войсковой части 03425 (Москва. 2003 г.). *-1 также докладывались и обсуждались на семинарах и научно-технических совещаниям ЗЛО "МЦСТ" и Института микропроцессорных вычислительных систем РАН. Публикации По теме диссертации опубликованы 10 печати их работ: Дроздов АЛО,, Нови кон СВ. Исследование методов преобразования программы и предикатную форму для архитектур с явно выраженной параллельностью // Компьютеры в учебном процессе. № 5. 2005. С. 91-99. Дроздив Л. К)., Новиков СВ., Шилов В.В. Эффективный алгоритм преобразования потока управления в поток данных // Информационные технологии. № 2. 2005. Приложение. С. 24-31. Дроздов Л.Ю., ІГовнков СВ. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии. № 3. 2005. С. 45-51. Боханко Л.С, Новиков СВ., Шлыков С.Л. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе. № 8. 2005, С. 73-80. Новиков СВ. Развитие методов глобального планирования программ, используемых в современных оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом па уровне команд // Тезисы докладов Международной молодежной научной конференции «XXXI Гагаринекие чтения», т. 4. М.; МАТИ, 2005. Дроздов ЛЛО., [Тоников СВ. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция "Региональная Имформатика-2004". Тезисы докладов. - СПб.; СПИИ РАН, 2004. Дроздов ЛЛО., [Тоников СВ. Методы совместного планирования путей программы, предлагаемые для использования и современных оптимизирующих компиляторах // Сборник тезисов докладов XXI научно-технической конференции войсковой части 03425. М.: в/ч 03425, 2003, Коханко А. С, Дроздов А. [О., Новиков С В., Шлыков С. Л. Распределение регистров методом раскраски графа несовместимости для VLIVV-архитсктур // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8. 2005. С. 71-77. Дроздов А. Ю., Новиков С В., Боханко А. С, Галазнн А. I». Глобальный граф потоки данных и его роль в проведении оптимизирующих преобразований программ // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005. С. 78-87. Дроздов А. Ю., Новиков С В., Кочлпко А. С, Гііліінш А. Ь. Def-Use граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. Нч 12. 2005. С. 3-14. Структура и odi.cM раоом.і Диссертация состоит из введения, трех глав и заключения. Диссертация содержит 107 страниц. 32 рисунка. 7 таблиц. Список литературы насчитывает 66 наименований. Краткие содержание работы Схема построения оптимизирующего компилятора для ЕРЮ архитектур представлена на рис. 4. В ходе трансляции выполняются аналитические и оптимизирующие фазы компилятора. Операции промежуточного представления в ходе преобразований приобретать новые свойства. Например, операция может быть поставлена под условие или в спекулятивный режим. Некоторые алгоритмы компилятора способны применяться на любом состоянии промежуточною представления, а некоторые требуют наличия определенных свойств. Одним из важных свойств операций, влияющих на работу алгоритмов, является предикатное исполнение. Точное построение глобального графа потока данных осуществляется на представлении без предикатных вычислений, а при переводе потока управления в поток данных и на предикатном представлении глобальный граф позока данных корректируется. Глобальное планирование максимально использует все архитектурные черты и именно па этой фазе происходит преобразование некоторых вычислений в предикатную форму. Как будет показано в данной работе, на глобальном планировании выполняются некоторые оптимизирующие преобразования для повышения эффективности планирования. Тем не менее, некоторые преобразования полезно применять после глобального планирования. Перед финальными фазами распределения регистров и генерацией кода выполняется локальное планирование операций, которое необходимо из-за преобразований на предикатном коде. В :m ii главе будет дан обзор существующих методов статического планирования, Ез зависимости от области применения алгоритмов статического планирования их можно называть локальными, глобальными или цикловыми. Локальными являются алгоритмы, осуществляющие планирование в пределах линейных участков. Глобальные методы осуществляют планирование между линейными участками. Цикловые методы осуществляют планирование самых вложенных циклов. Техника планирования по списку (List Schedutmy) [9. 14, 22] является самым распространенным метолом статического планирования и современных компиляторах. Так или иначе. зга техника используется в контексте всех, рассматриваемых далее алгоритмов планирования, В общем виде задача поиска оптимального размещения операций но устройствам является Л Р-нолной, то есть найти самое оптимальное решение можно голыш полным перебором всех случаен. Такой метод не используется It компиляторах ич-ча ограничений на время их работы. Сбалансированным подходом к решению задачи планирования как рач и является алгоритм List Scheduling. Н рамках этот подхода удается найти эффективное решение за разумное время. ОсновоІі этого алгоритма является список готовых к планированию операций. Готовой считается операция, у которой спланированы псе предшественники по зависимостям н к текущему моменту ожидается ГОТОВНОСТЕ, всех аргументов данной операции. Псе элементы списка готовых операций упорядочены по приоритетам планирования. Эвристики, устанавливающие при ори геты, являются ключевой составляющей, влияющей на эффективность работы алгоритма. В момент планирования происходит обход списка сотовых операций с проверками на возможность размещения их в текущей команде. Пели для операции есть исполняющее устройство, то она планируется в эту команду. По мере планирования операций обновляется список готовых к планированию. Сложность данного алгоритма можно определить как (9(NxN). где N - количество операций. Это означает, что п худшем случае для того, что бы спланировать одну операцию, нужно обойти псе не спланированные операции. Реально сложность сильно зависит от степени параллельности вычислений. Именно она определяет возможную длину списка готовых операций. В архитектурах, использующих параллельность на уровне операций, существует целый ряд исполнительных устройств. Методы статического планирования должны использовать доступные вычислительные ресурсы максимально эффективно. Очень часто, в исходных программах бывает недостаточное количество параллельных вычислений в пределах одного линейного участка. Из-за этого вычислительные ресурсы не удается использовать с максимальной загрузкой. Для повышения уровня параллельных вычислений используются техники глобхіьного планирования. Эти техники включают в рассмотрение регионы, состоящие из многих линейных участков. Одним из таких подходов является Trace Scheduling [У, 14, 2, 30, 33], который использовался в компиляторах для F7, W-архитектур. Идея этого метода основывается на предположении о том, что условные переходы с большой вероятностью происходят по одному и тому же направлению при различных входных данных и, если рассматривать переход по этому направлению как безусловный, то появляются дополнительные возможности совмещения операций па больших участках программы. Оценки направления переходов или их вероятности можно получать, используя профилирование программы или статическое предсказание переходов. Используя эти оценки, компилятор выбирает путь или трассу по линейным участкам через все переходы с направлением наибольшей вероятности, и рассматривает эту трассу как единый участок, который планирует оптимальным образом. При этом возможно перемещение операций выше и ниже условных переходов, что требует от компилятора для корректное!и исполнения программы вставлять компенсирующий код на ветви входа в трассу и выхода из нее (рис. 5). Затем процесс повторяется для следующей наиболее вероятной трассы, которая может включать первоначальный код и компенсирующий код от предыдущей иіерации. Таким образом, компилятор преодолевает границы линейных участков и находит параллелизм па более длинных потоках команд. За счет компенсирующею кода возможно увеличение кода всей программы. Но так как дополнительный код приходится на трассы с меньшей вероятностью исполнения и благодаря высокой параллельности ГЛШ-архнтектуры должно досчитаться ускорение программы. В рассмотренном выше подходе планирования трассы при переносе операции череч боковые входы іребуетея построение компенсирующего кода. " гого можно и (бежать, если убрать бокчжые входы тп трассы. Суперблоком [ ), 311 называется трасса бет боковых входов. Управление может передаваться только на вход сунерилока. Выход и І суперблока может осуществляться в нескольких местах. Формирование суперблоков происходит в два :гтаиа (рис. 6). На первом mine выделяется путь е использованием профильной информации. Затем выполняется преобразование tail duplication, которое техникой дублирования удаляет боковые входы в трассу. Процесс дублирования кола может негативно отражаться на времени исполнения приложения. Основой техники просачивания (Percolation Scheduling) [О, 35, ЗА] являются базовые преобразования над операциями, которые позволяют осуществлять их корректный перенос: перенос операции перенос операции ветвления дублирование учла дублирование операции. На рис. 9 приведены примеры этих преобразований. Следует отметить, что все зги базовые преобразования в той или иной степени используются в алгоритмах планирования. Например, при планировании трассы используется как перенос операции, так и ее дублирование при переносе через боковой вход. Преобразование tail duplication выполняет последовательно дублирование узлов целого подграфа. Алгоритм планирования Percolation Scheduling осуществляет перенос операций из исходных узлов вверх по некоторому "лучшему" (в соответствии с некоторой оценочной функцией) пути в конечные узлы. Этот алгоритм получил развитие в работе [25], где он получил название Trai lb lazing Percolation Scheduling. Изменения были связаны с тем, что перенос операций осуществлялся на структуре иерархического графа задании {Hierarchical Task Graph), где факторизуютея участки управляющего графа с одним входом и одним выходом. Эти участки являются мостами (bridge) для переноса операций, то есть через них этот перенос возможен. Так как эти участки могут включать в себя циклы, то это существенно увеличило регионы планирования. Сам алгоритм планирования, представленный в работе [25]. состоит из трех шагов. Во-первых, эвристически проставляются ранги всех операций программы. Во-вторых, для каждого узла определялось множество операций, которые могут быть в него перенесены. Изначально, это множество включает в себя все операции узлов, которые исходный узел доминирует. В процессе планирования операции становятся непереносимыми и удаляются из множеств. Например, операция становится для узла непереносимой, если ее спланировали выше или в самом узле. Третий шаг состоит в планировании каждою узла в порядке сверху вниз. При планировании узла осуществляются попытки переноса в него в порядке приоритетов операций. ;шя которых потенциально возможен перенос. Переносу операций моїуг мешать такие факторы как зависимости, стратегии спекулятивного переноса, ограничения на рост кода. В процессе планирования перенос возможен и ;тля операций ветвления. Как и любая техника планирования, ;шя управления ростом кода и временем трансляции при данном подходе используются эвристики, управляющие и тем и другим. Техника планирования полію ко го фроніа (Wavefront Scheduling) [41] была реализована в кошекеге оптимизирующего компилятора ятя архитектуры Itanium. Казовым понятием данного подхода является понятие фронта планирования. Фронт определяет утлы, в которые в настоящий момент идет планирование. Узлы фронга разбивают ациклический участок натри части: узлы выше фронта утлы фронта утлы ниже фронта. Операции могут планироваться ко фронт либо сверху вниз, либо снизу «верх. Планирование работает в пределах ациклической области. В -эту область могут быть включены никлы, которые должны быть уже спланированы и которые трактуются как один учел ациклического участка. Планирование во вложенные циклы и из них не осуществляется. Утлы фронга выбираются так, что любой путь, соединяющий узлы из разных областей относительно фронта, содержал только одни учел фронта. Учлы фронта не достижимы друг от друга. На рис. 10 приведен пример продвижения фронта но ациклическому участку. Для корректного продвижения фронта на участке не должно быть критических дуг, то есть дут. выходящих из узлов с более чем одним выходом и входящих в учел, па который есть более одного перехода. Для достижения этого на критические дуги оставляются пустые узлы. Во время планирования управление не изменяется. Для улучшения показателей планирования операция может быть спланирована в узлы разных фронтов. Например, при планировании операции из утла F во фронт W1 (рис. 10) может быть спланирована копия операции только в учел В. а в момент планирования во фронт W3 другая копия может быть спланирована в Для преодоления зависимостей на этапе планирования используется несколько техник. Во-первых, в случае, если переносу операции во фронт мешает выходная или обратная зависимость, то осуществляется переименование результата переносимой операции с построением дополнительной операции пересылки, что позволяет преодолевать эти виды зависимостей. Во-вторых, если существует зависимость но некоторому маловероятному пути, то для преодоления ее возможно построение компенсирующею кода. Например, если переносу операции узла F во фронт W0 (рис. 7) мешает зависимость с операцией из маловероятного участка Е, то в участке Е может быть построена операция компенсирующего кода. В-третьих, если в некоторый узел нельзя перенести операцию из-за того, что этот узел находиться между некоторым определением тгого ресурса и его использованием, то сделать возможным лот перенос можно так же, как и в первом случае, путем переименования. В момент планирования используются возможности спекулятивного н предикатного переноса операций, Если при планировании операции она переносится через переход и операция, вырабатывающая условие для этого перехода уже спланирована, то переносимая операция будет поставлена под условие перехода. Используется возможность частичной спекулятивности, то есть через некоторые переходы перенос операции происходит спекулятивно, а через некоторые иод условием. Напомним, чіо методы I.S и MS могуг якляїьея "ілсмешами печальных подходов, поэтому отдельно их ограничения рассматривать нет необходимости. Во-первых, с гочки зрения областей применении многие рассмотренные методы имеют ограничения. Техники TS. SS и HS раооїаюг в рачках ациклических областей программы. SW P применяется только к самым вложенным циклам, а техника WS хоть и может применяться ни произвольный регион, но не может переносить операции из вложенных циклов а охватывающие циклы. Во-вторых, планирование с учеюм характеристик архитектуры пс всегда используется л.тя принятия решения при переносе операций. Например, при напоре гнперблоков н HS вместо планирования используются эвристики. Негшннный эффект от построения компенсирующею кола для случаен TS и PS также не проверяется планированием. В-третьих, излишнее дупднронание кода может негативно скачаться тіа эффективности планирования. Такое дублирование возникает в подходах TS, SS. PS и WS. В-четвертых, FiTt в одном представленном подходе не говорится об интеграции скалярных оптимизации в схемы планирования. Петь интеграция только техники переименования и техники использования спекулятивности, направленные на удаление зависимостей, препятствующих переносу. Известно, что перенос операций или помещение их в один гиперблок создают возможности для применения скалярных оптимизаций (сбор общих подвыражений, распространение копий, и т.п.). Если проводить зги оптимизации на этапе планирования, то это создаст возможности для более точного планирования. В-пятых, ни в одном представленном подходе не говорится об интеграции цикловых оптимизаций в схемы планирования. Известно, что кроме SWP подхода к одновременному исполнению операций с разных итераций цикла возможно применение оптимизации раскрутки цикла (unroll) [9]. Ключевым фактором, влияющим на -эффективность данной оптимизации, является принятие решения о количестве раскрученных итераций цикла. Планирование является наиболее точным механизмом для принятия этого решения, так как именно на планировании видна возможность для одновременного исполнения операций с разных итераций цикла. В-шестых, пи в одном подходе нет интеграции в схему планирования сразу двух возможностей преобразовании операций перехода: дублирования (tail duplication) и переноса. Операция дублирования встречается в і відходе SS как дополнительная фаза при формировании суперблоков. Операция переноса переходов существует в подходе PS как одна из базовых техник планирования. Наличие возможности для произвольного преобразования на этапе планирования дает большую свободу в принятии решения, что в свою очередь улучшает характеристики алгоритма. Наличие перечисленных ограничений существующих методов планирования определяет пути их развития. Развитие методов статического планирования должно снимать существующие ограничения, добиваясь большей свободы при принятии решений о плакировании операций. Перед финальными фазами компиляции, такими как распределение регистров и генерация кода, операция СННСК должна быть раскрыта и представлена как реальная операция архитектуры. Спекулятивность по управлению не всегда требует построения компенсирующего кода. Если известно, что операция для корректных аргументов всегда выполнит корректно вычисления, то построения компенсирующего кола не гребуетея. Операции чтения и спекулятивном по упраплепию режиме не гарантируют корректного чтения для корректною адреса. )то связано с оптимизацией доступа в память. Спекулятивное чтение по определению обычно исполняется чаїне, чем исходная операция чтении. Коли данные, соответствующие спекулятивному чтению окажутся в mine, то есть доступ к ним будет относительно не долгим, то чіение состоится корректно. Если же чтение данных потребует прерывания для подкачки данных из памяти, то это ка порядок замедлит работу операции чтения, результат которой может оказаться не востребованным, и поэтому п спекулятивном режиме такое чтение отменяется, а решение о чтении принимается в компенсирующем коде операции CHECK. Гак как операция CHECK всегда выполняется под своим точным предикатом, то обращение в память будет происходить, только если оно точно должно было состояться. Таким образом, можно сказать, что операции без побочных эффектов могут спекулятивно планироваться бет построения компенсирующего кода. Побочным эффектом в данном случае можно считать выдачу ігекорректиого результата исполнения для корректных аргументов. Следует отметить, что в архитектуре Эльбрус-ЗМ, в отличие от архитектуры ІА-64. реализован полуспекулятивный режим операций чтения. В этом режиме операция чтения всегда будет осуществлять чтение корректно для корректного адреса и потешу в этом случае не требуется построения компенсирующего кода. Есть только ограничения на использование этого режима. Если компилятор используется для трансляции операционной системи, то не всегда можно снимать условие с операций чтения с постановкой ее в полуепекудятиный режим, так как незапланированное прерывание, то есть вызов процедуры самой операционной системы, может нарушить ее работу. Использование спекулятивного режима может являться не только оптимизацией, но и приводить к деградации транслируемого кода. Основной побочный эффект от использования спекулятивности по управлению является увеличение частоты исполнения вычислений. Если вычисления исполняются под точными предикатами, го количество их выполнений определено семантикой программы. Точный предикат отменит исполнение операций, если его не должно было быть. Снятие условия приводит к исполнению вычислений, даже если в данный момент их исполнение не требуется. Спекулятивность и по данным и по управлению с построением компенсирующего кода удваивает количество вычислений для случая ухода на компенсирующий код. так как в компенсирующем коде происходит перевычисление спекулятивных операций. Таким образом, для того, чтобы использование спекулятивного режима являлось оптимизацией и не приводило к деградациям транслируемого кода, нужно выработать стратегию применения спекулятивности на этапе планирования. Основная задача при принятии решения об использовании спекулятивного режима состоит в оценке положительного эффекта от этого действия. Для спекулятивности и по управлению и по данным оцениваются два фактора: уменьшение критического пути в результате применения ошимизацни и вероятность наличия реальной зависимости, которая удаляется в процессе оптимизации. Реальная зависимость для спекулятивности по данным означает наличие конфликта между операцией записи и операцией чіення. Реальная зависимость ;іля спекулятивности по управлению означает, что вероятность исполнения операции мала. Большую роль в определении реальноіі зависимости по данным играет статический анализ, который в основном эвристически іірої но пірует конфликт. Реальная зависимость но управлению н основном определяется на основании нрофи:и ноіі информации. В данной работе в алгоритм набора гиперблоков был интегрирован ряд локальных оптимизаций для повышения точности принятия решения па каждом шаге алгоритма. Локальность откачает, что область применения оптимизаций составляет один і и перилок. Все оптимизации можно разбить на два класса: оптимизации, наце;гскные на повышение параллельности вычислений ча счет удаления зависимостей скалярные оптимизации, минимизирующие количество вычислений ча счет удаления избыточных и упрощения вычислений с точки зрения особенностей конкретной архитектуры. К первому классу оптимизаций можно отнести удаление зависимостей с использованием аппаратной поддержки спекулятивных вычислений. Кроме этого, зависимости типа чтение-запись (обратная) и запись-запись (выходная) между двумя операциями могут быть удалены путем построения операции пересылки результата операции, являющейся преемником зависимости, в новый ресурс. При этом действии зависимость перенаправляется на операцию пересылки, и исходный преемник зависимости может быть спланирован выше предшественника. К скалярным оптимизациям относится удаление избыточных вычислений, результат которых нигде не используется, сбор общих подвыражений на предикатном коде, а так же специфичные для архитектуры упрощения на уровне операций, называемые преобразованием peephole. Коррекция управляющего графа на каждом шаге алгоритма набора гиперблоков достаточна тривиальна. Каждый расширенный скалярный участок представляется в графе управления одним узлом, аналогично линейному участку. В момент объединения нескольких расширенных скалярных участков в один все дуги, соответствующие внешним для гиперблока переходам перенаправляются на итоговый учел. Внутренние для гиперблока душ удаляются. Удаляются так же узлы управляющего графа, операции которых объединяются в один расширенный скалярный участок. Форма статического единственного присваивания (Static Single Assignment, SSA) является одной из самых распространенных форм представления потока данных нршраммы и активно используется в большинстве современных оптимизирующих компиляторов [I ]. Важной информацией, используемой в процессе глобального планирования, является знание о времени жизни объектов [19, 22J. Па основе этой информации может приниматься решение о снятии условия с операции при ее переносе. Эти знания позволяют оценить рост давления па регистры и вовремя ограничить перенос операций, чтобы не допустить возникновения дополнительного кода, коюрый достраивается распределителем регистров в случае нехватки аппаратных ресурсов. Время жизни объекта представляет собой произвольный участок управляющего графа, ограЕнгченпый использованиями и определениями объекта. Вычисление времени жизни является итерационной задачей поюкового анализа. В общем случае алгоритм ее вычисления имеег квадратичную сложность (" (N N). где N количество узлов управляющею графа [22], Обычно решается задача проходом вверх по управляющему графу. Использования объекта начинаю время жизни, определения объекта заканчгшаюг время жизни. Уравнения потокового анализа, решающие эту задачу, выглядят так: Информация о времени жични хранится в таблице (ішоньїх векторов. Нее объекты, для которых вычисляется время жиши. перенумеровываются. Их НОМер является индексом и оптовый векюр, в котором сохраняется при інак того, жив или пег объект в данной точке нрої раммы. Актовые вектора выделяются для дут управляющего графа. Каждой дуге соответствует бишныи вектор. Нее вектора входных дуг одного и того же учли должны быть жвивалентны с точки фения информации, получаемой по ним. В процессе глобального планирования информация о кремени жити должна иып. скорректирована. В общем случае, при переносе операции во фронт глобальною планирования, для ее аргументов и резулыатон должен осуществляться корректирующий обход гой области, мерсі коюрую переносилась операция. При переносе использования обьекта информация время жіпші можег уменьшаться, если для некоторых участков оно было единственным. Г [ре переносе определения обьекта. время жизни его не может уменьшиться, а может только увеличиваться, гак как в момент переноса определение удаляется от использований. Для ускорения коррекции пои информации в данной реализации был задействован метод сохранения информации о времени жизни, предложенный в работе [25]. Информация о времени жизни сохраняется с привязкой к участкам с одним входом и одним выходом, которые выделяются в процессе построения дерева структуры программы. Понятие дерева структуры программы (PST - program structure tree) вводится в работе 23]. Ота структура данных представляет собой дерево, каждый узел которого является участком управляющего графа с одним входом и одним выходом (SESB — single entry single exit). Алгоритм построения дерева структуры программы работает за линейное время 0(E), где F - чисто дуг в управляющем графе. В каждом узле дерева содержится информация о входящей дуге и выходящей дуге участка SF-SE. ЕЇ дугах содержится информация о том, ннляется ли она входящей и/нди выходящей дутой некоторою SF-SE участка. Узлы дерева PST с одного уровня не могут включаїь в себя одни и re же узлы управляющего графа. Общие узлы могут быть юлько у достижимых в дереве PST регионов SESE. Дерево PST было использовано в контексте алгоритма глобального планирования. Во-первых, с использованием г той структуры данных была ускорена коррекция информации о времени жизни объектов. Во-вторых, на основе чинний об участках с одним входом и одним выходом было оптимизировано построение предикатов для переносимых операций па глобальном планировании. В процессе макро преобразований регионы SESE могут разрушаться. При удалении или дублировании входов и выходов узла SESE вызывается корректор, который удаляет в дереве затронутые узлы. В момент раскрутки итераций цикла подграф дерева PST, соответствующий итерации цикла, копируется вместе с итерацией цикла. Гї рачках рассматриваемого подхода реали чує гея возможность переноса операций через SESE участки ост дополнительной коррекции в них информации о времени жизни. Основная идея этого подходи состоит втом, чтобы для SESE регионов, где нет определений некоторого объекта, сохранять только локальную ;ідя данного региона информацию о времени житии данного объекта. При этом измениіьея алгоритм проверки свойства живых/неживых для объекта в некоторой точке программы. Теперь, если по битовому вектору дуги управляющего графа для объекта получаем» что он не жив в данной точке программы и эта дуга принадлежит SESE региону, в котором нет определения данною объекта, то дополнительно проверяем информацию о времени житии на выходе ближайшего охватывающего SESE региона, в котором определение объекта существует. Если на выходе данного SESE региона объект окатывается жив, то итоговый отпет будет состоять в том, что он жив и в исходной точке программы. Па рис 28 приведен пример переноса операции через SESE участок. Па рис 28.а аргумент операции а имеет время жизни, включающее в себя регион Л. В предлагаемом подходе информация о времени жизни в дугах 2,3,4,5,6 цикла будет нулевой, т.е. объект локально не живой. Но при вопросе о том, жив ли объект в любой из этих дуг при проверке в охватывающем SESE участке В. где есть определение этого объекта, в дуге 7 будет установлена информация о том, что объект жив. Итоговый ответ будет отображать реальную ситуацию, а именно что в дугах 2,3,4,5,6 объект жив. В момент переноса операции из узла в узел корректируется только информация в дугах t и 7. а в регионе А корректор запускаться не будет. После переноса на тот же вопрос тем же алгоритмом для дуг 2,3,4,5,6 мы получим новую корректную информацию о том, что объект в этих дугах не жив. При любых преобразованиях глобального планирования необходимо сохранять дисциплину локальной и полной информации о времени жизни объектов. Если в некоторый SESE регион переносится определение объекта, то локальная информация для данного региона должна быть достроена до полной. Для этого всегда можні) распространить информацию о времени жизни, которая глобальна на выходе из этого SESE региона, внутри него. Если из SESE региона выносится последнее определение объекта, то внутри региона нужно удалить глобальную информацию, оставив только локальную. Для этого информацию о времени жизни внутри региона можно пересчитать ;ідя оставшихся там использований.Зависимости по управлению и по данным
Планирование по дереву доминирования
Оценка эффективности одного шага алгоритма
Информация о времени жіпни объектов
Похожие диссертации на Развитие методов глобального планирования программ для архитектур с явно выраженной параллельностью
