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

Российская академия наук Институт системного программирования

УДК 519 68 Иа правах рукописи

□0344В34и

Белеванцев Андрей Андреевич

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

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва-2008

'2 2т

003446340

Работа выполнена в Институте системного программирования РАН

Научный руководитель академик РАН

Иванников Виктор Петрович

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

Серебряков Владимир Алексеевич

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

Ведущая организация Факультет вычислительной математики и

кибернетики МГУ им М В Ломоносова

Защита диссертации состоится 10 октября 2008 г в 15 часов на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, Москва, ул Б Коммунистическая, д 25,

Институт системного программирования РАН, конференц-зал (комн 110)

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан 9 сентября 2008 г

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

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

Актуальность.

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

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

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

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

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

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

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

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

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

Основные результаты В работе получены следующие основные результаты, обладающие научной новизной

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

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

3 На основе предложенного метода разработан и реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC. Проведена апробация алгоритма на пакете тестов SPEC CPU 2000

Практическая ценность Разработанное спекулятивное планирование команд было одобрено сообществом разработчиков компилятора GCC для включения в основную ветвь разработки Данная оптимизация является частью GCC с марта 2006 года и включена в официальный релиз компилятора версии 4 2 0 Части разработанных механизмов поддержки спекулятивного выполнения используются при реализации нового алгоритма планирования команд для компилятора GCC в рамках проекта, выполняемого Институтом системного программирования РАН для компании Hewlett-Packard

Апробация работы Основные результаты диссертационной работы изложены в статьях [1-7] и представлены в докладах на следующих конференциях и семинарах

1 Научно-исследовательском семинаре по автоматизации программирования под руководством проф М Р Щуры-Буры в ноябре 2006 года,

2 Конференции GCC & GNU Toolchain Developers' Summit в июне 2005, июне 2006 года и июне 2007 года,

3 Тихоновских чтениях на факультете ВМиК МГУ в октябре 2006 года,

4 Втором семинаре Федерации Гелато (2nd Gelato GCC Workshop in Moscow) по улучшению компилятора GCC для платформы Intel Itanium в августе 2006 года,

5 Семинаре GREPS 2007 по исследованию компиляторных технологий с помощью пакета GCC в сентябре 2007 года

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы Объем диссертации составляет 103 страницы Диссертация содержит 6 таблиц и 24 рисунка Список литературы насчитывает 81 наименование

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

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

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

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

В разделе 1 2 описываются механизмы полностью аппаратной поддержки спекулятивного выполнения в традиционных архитектурах с использованием буфера переупорядочивания и отложенных исключений Рассматриваются теоретические модели спекулятивного выполнения команд, контролируемого компилятором, и необходимая для каждой модели поддержка аппаратуры Приводится устройство спекулятивных команд в архитектуре Itanium расширенные команды загрузки (ld.s и Id.а) для устранения зависимостей по управлению и по данным соответственно, команды проверки результата выполнения (Id.с, chk.a, chk.s), а также необходимая аппаратная поддержка этих команд - таблица адресов расширенных загрузок и флаги отложенных исключений (так называемые NaT-биты) для регистров общего назначения Приводится пример ассемблерного кода Itanium с использованием спекулятивных команд

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

цель" и "база+смещение" Рассматривается алгоритм вероятностного анализа зависимостей по данным между массивами

В разделе 1 4 излагаются примеры статических алгоритмов спекулятивных оптимизаций Дается обзор подходов к планированию команд, описывается использование спекулятивных перемещений команд при планировании Излагаются примеры спекулятивных оптимизаций удаления частичной избыточности, а также спекулятивное расширение представления с единственным присваиванием (ЗБА-представления)

В главе 2 приводятся основные результаты диссертации Рассмотрим некоторое множество I наборов входных данных программы Будем называть свойством Т7 программы некоторое утверждение о потоке управления или потоке данных программы Вероятностью выполнения Р свойства ^ программы на множестве / будем называть отношение числа наборов из /, при запуске программы на которых свойство F выполняется, к общему количеству наборов в I

Вероятностным анализом потока управления или потока данных назовем такой анализ, который аннотирует каждое найденное им свойство F программы вероятностью Рр, с которой это свойство выполняется на множестве наборов входных данных /, которое исследует этот анализ Обычный анализ (будем называть его консервативным) аннотирует все найденные свойства вероятностью 1, то есть они заведомо верны для всех наборов входных данных из множества I

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

Спекулятивным преобразованием программы мы будем называть пару <Т[>, Тк>, где Тц - потенциально опасное оптимизирующее преобразование, заведомо некорректное (нарушающее семантику программы) для некоторых наборов входных данных ВсО, а 7К - восстановительное преобразование, добавляющее в программу код восстановления для обеспечения корректности ее выполнения на наборах В Восстановительное преобразование гарантирует корректность программы после применения обоих преобразований из пары Тх, для каждого семантически правильного выполнения программы,

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

Необходимо заметить, что набор входных данных В, на котором преобразование Тв некорректно, не обязательно принадлежит множеству /, на котором определяются вероятности выполнения свойств программы Если множество / использовалось при профилировании программы, то наборы из множества В могут вообще не встретиться в / (то есть ВсО, 1сО, но ВП1=0) В этом случае нулевая вероятность выполнения свойства, найденная на /, не означает, что свойство не может выполниться на наборах из В Например, если при профилировании оказалось, что некоторый указатель р никогда не равен нулю, то оптимизирующее преобразование может исходить из этого предположения, однако восстановительное преобразование все равно должно обеспечить корректность программы в случае, когда р равен нулю

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

• Сохраняют семантическую корректность программы {легальные),

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

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

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

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

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

На фазе трансформации спекулятивная оптимизация сначала определяет множество возможных спекулятивных преобразований Для этого вероятности найденных свойств нужно положить равными 1 или 0 (в зависимости от того, какое значение соответствует семантике свойства в консервативной оптимизации) и выполнить определение множества легальных оптимизирующих преобразований так же, как и в консервативной оптимизации Далее для каждого найденного преобразования Ти, возможно, нарушающего семантику программы, необходимо построить восстановительное преобразование которое позволит сохранить корректность программы при применении 7Ь Построенная пара преобразований 7$ = <Тц, Тк> будет являться легальным преобразованием Восстановительное преобразование обычно состоит из следующих этапов

• Определяется множество В наборов входных данных, для которых преобразование Т0 является некорректным

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

• Генерируется код, который в случае, когда / еВ, возвращает программу в корректное состояние

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

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

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

Консервативная оптимизация Спекулятивная оптимизация

Фаза анализа. Фаза анализа

• Определить необходимые свойства • Определить необходимые свойства

программы программы и их вероятности

о Полностью статическими алгоритмами

о С использованием данных из профиля

программы

о Только с помощью профиля программы

Фаза трансформации Фаза трансформации

• Построить легальные преобразования • Определить множество потенциально

• Выбрать из них опасных преобразований

выгодные преобразования о Положить вероятности свойств равными

• Применить их к программе граничному консервативному значению

• Построить легальные преобразования

о Построить наиболее дешевые парные

восстановительные преобразования

(зависит от оптимизации)

• Построить оценки выгоды для всех

легальных пар спекулятивных

преобразований

о Оценить отдельно влияние опасных и

восстановительных преобразований

(зависит от оптимизации)

• Выбрать наиболее выгодные

Применить их к программе

Рис I Обшая схема постооения спекулятивной оптимизации

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

На фазе трансформации рассматриваются только частично мертвые инструкции, которые мертвы с большой вероятностью Оптимизирующим преобразованием ТГ) будет удаление такой инструкции I Восстановительным преобразованием является вставка копии / на тех путях, на которых 7 жива

Выгодой от преобразования является ускорение программы на тех путях выполнения, на которых / является мертвой Ценой преобразования является цена кода восстановления, которая заключается лишь в увеличении размера программы на количество вставленных копий /, так как время выполнения программы на путях, на которых I является живой, не изменяется - по-прежнему на этих путях будет выполнена одна копия / Решение о проведении преобразования должно приниматься на основании оценки вероятности того, что 1 мертва, и необходимом количестве копий / для кода восстановления

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

• Определить необходимые свойства программы,

• Определить, что понимается под вероятностью выполнения этих свойств,

• Построить алгоритмы нахождения этих вероятностей,

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

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

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

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

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

Пусть теперь при перемещении / нарушаются лишь зависимости по данным Рассмотрим случай зависимости, возникающей из-за операций с памятью В этом случае существует инструкция ./, которая выполняет операцию с памятью по адресу Q, возможно, совпадающему с адресом Р, использующимся в I, при

Рис 2 Определение вероятности зависимостей по данным

этом / зависит от 3. Нарушение зависимости означает, что в преобразованной программе I выполняется раньше У Следовательно, для сохранения корректности программы в точке У необходимо проверить совпадение адресов Р и 2 В случае совпадения, инструкции I и 3 должны быть перевыполнены с верными значениями операндов, которые должны быть сохранены для этого в специальном буфере Для выполнения этих операций также необходима поддержка аппаратуры

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

Определение 2. Вероятностью выпочнения зависимости по данным/по управлению на некотором множестве входных наборов I назовем, как и в общем случае, отношение количества наборов на которых зависимость существует во время выполнения программы, к общему количеству наборов в / Нулевая вероятность означает, что инструкции X и У не зависят друг от друга ни при каких наборах входных данных, если вероятность равна единице, то наоборот, для всех наборов I еО зависимость существует

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

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

Для вычисления вероятностей зависимостей по данным могут использоваться алгоритмы вероятностного анализа указателей и анализа зависимостей по данным между массивами, также рассмотренные в первой главе Тем не менее, такие алгоритмы не дают возможности установить вероятность зависимости по данным в случае, когда вдоль разных путей в графе потока управления указатель может принимать различные значения Например, на рисунке 2 частотное распределение показывает, что при записи по указателю я в 70% случаев он указывал на х, а в 30% - на у, тогда как для загрузки по указателю р данные будут обратными При этом вероятность того, что указатели р и д ссылаются на одну ячейку памяти, равна нулю

Код профилирования для J (асМги) — А;)

о» += 1,

1Е (асйги) == Ак) Г>ка += 1. = аа<Зг(Л ,

Рис 3 Профилирование зависимостей по данным

В работе предлагается использовать непосредственное профилирование найденных зависимостей по данным для вычисления их вероятностей при оптимизации ациклических областей (то есть, например, при планировании команд) Для этого во время компиляции определяются интересующие нас зависимости по памяти - те, для которых статический анализ указателей не может определить, выполняются ли они всегда1 Во время выполнения для каждой инструкции - загрузки или записи в память, участвующей в некоторой зависимости, записываются адреса операндов в глобальный буфер, индексируемый уникальным идентификатором инструкции Кроме того, при выполнении инструкции X, предположительно зависящей от У, адреса операндов X сравниваются с адресами операндов У, и увеличивается один из счетчиков наличия/отсутствия зависимости между Хи V, также находящийся в глобальном буфере, индексируемом по номеру зависимости При этом для ациклических областей достаточно хранить лишь последние значения адресов Более выгодным является хранение адреса для каждой инструкции, а не для каждой зависимости, так как одна и та же инструкция может участвовать в нескольких зависимостях

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

1 Для зависимостей по регистрам всегда известно, что они истинны

11

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

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

• Если перемещение выполняется машинно-независимой оптимизацией, то инструкция / выполняется за одинаковое время в любом месте программы, обозначаемое как Cost(I)

• Если оптимизация машинно-зависима, то компилятором предоставляется модель процессора, по которой можно оценить время выполнения инструкции I в любой точке программы X, обозначающееся как Cost(Ix)

• Время выполнения набора инструкций R обозначается также как Cost(R)

Для каждого спекулятивного перемещения определяются две величины стоимость перемещения и выигрыш от перемещения Стоимостью перемещения будем называть накладные расходы (временные затраты), связанные как с выполнением кода восстановления, так и с новым положением инструкции, и обозначать ее как CosHJВыигрышем от перемещения будем называть ускорение работы программы, достигнутое за счет выполнения опасного перемещения, обозначая его как Benef¡(T¡) Очевидно, перемещение является выгодным, если выигрыш от него превосходит его стоимость, то есть Benefi(Ts) > CosKT^)

Вероятность выполнения пути Р будем обозначать как рР или р(Р) Суммарную вероятность выполнения путей, проходящих через точки Хи У, мы будем обозначать как рху или р(Х, У), а вероятность выполнения путей, не проходящих ни через X, ни через У, как р^ или р{Х,У) Множество всех путей, проходящих через точки Хи У, будем обозначать как Path (X, У) Следовательно, по определению рху = ^р(Р)

РеРтЦХ 11

Утверждение 1 Пусть инструкция I перемещается из точки Y в точку X, нарушая зависимости по управлению Тогда стоимость спекулятивного перемещения по управлению оценивается по следующей формуле Cost(Ti) = pn-xCost(,Jx)+ 2>,„„ Cost(fr) + p, Cost(RE) (1)

'-»-' PePuth(А У) ' '

Са«Ь> ---- to>KE)

Здесь То - опасное преобразование, R - код восстановления, Е - код, обеспечивающий отложенную выдачу исключения (если необходимо) 1х и 1Р обозначают стоимость выполнения инструкции в точке перемещения и ее

копии в восстановительном коде на пути Р соответственно, сумма берется по всем путям, проходящим через X, но не проходящим через Y

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

Cost{Ts) = pxT Costilх) + pXY- Costil „) + ре (2Cost(Br) + Cost(Ir)), (2)

где Cost(Br) - это затраты на выполнение перехода

Утверждение 2 Выигрыш от перемещения, нарушающего зависимости по управлению, можно оценить по формуле

BenefHTs) = рху (Cost(Ir)-Cost(lx)) + GB(Ix), (3)

где Со5!(/,)и Cost{Iх) означают стоимость выполнения инструкции на старом и новом месте соответственно, а СВ(/,) - наведенный выигрыш, получающийся за счет возможности выполнить дальнейшую оптимизацию кода программы в точке X

Результаты утверждений 1 и 2 легко обобщаются на тот случай, когда сразу несколько инструкций из точек Yj, , Y„ перемещается в точку X Такая ситуация может встречаться при планировании и называется унификацией несколько инструкций ниже текущей точки планирования "сливаются" в одну Тогда формулы (1) и (3) будут выглядеть следующим образом

= + ¿ £>(/>) G»í(/,,) +¿Л CostiREiY,))

1=1 1=1 PsPulUX Г,) i-l ^^

Вепф1(Т5) = ^PÍX,Y¡) iCoStiIh)-CostiIx)) + GBiIx) (5)

Для спекулятивного перемещения по данным можно считать, что X и Y находятся в одном и том же базовом блоке, так как если это не так, то стоимость и выгода от нарушения зависимостей по управлению вычисляется отдельно по формулам (1)-(3) Тогда выполняются следующее

Утверждение 3 Стоимость и выигрыш перемещения, нарушающего зависимость по данным, оценивается по следующим формулам

CosliTs) = pF CostiRF), (6)

Benefl(Js ) = Costal у) - Costilx) + GBi¡x) (7)

Здесь pF- это вероятность неудачи перемещения, равная вероятности зависимости по данным, a GBiIx) - наведенный выигрыш

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

должен быть выполнен переход Инструкция проверки, выполняющая переход, должна быть предоставлена аппаратурой

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

Из формул (1-7) следует, что, вообще говоря, чем меньше стоимость кода восстановления, тем больше выгода от спекулятивного перемещения Отсюда естественно вытекает задача о построении для данного спекулятивного перемещения инструкции кода восстановления минимальной стоимости

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

Утверждение 4 Пусть R - множество вершин графа потока управления, формирующее ациклическую область Пусть X и Y- вершины, участвующие в спекулятивном перемещении инструкции I, нарушающем зависимости по управлению, причем инструкция перемещается из вершины Y в вершину X Пусть сеть N построена по следующему алгоритму

• Введен фиктивный исток S, при этом

о Для всех вершин V, в которые ведут дуги из вершин, не

принадлежащих R, добавлена дуга из S в V, о Для всех вершин V, в которые не входит ни одна дуга (например, Entry), добавлена дуга из S в V,

• Стоком Г объявлена вершина Y,

• Удалены все вершины, из которых недостижима Y,

• Удалены все дуги, которые лежат на путях движения инструкции из Y в Л,

о Если при этом образовались новые вершины, из которых недостижима Y, но которые не лежат на путях движения инструкции, то из них в Y также добавлены дуги,

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

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

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

множество дуг, которые выполняются наиболее редко Следовательно, код восстановления, сгенерированный на этих дугах, будет наиболее дешевым

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

Компилятор GCC является единственным компилятором промышленного уровня с открытыми исходными кодами GCC - де-факто стандартный компилятор UNIX и Linux систем GCC портирован на более чем 50 архитектур, от мейнфреймов до встроенных систем Текущая версия компилятора, 4 3 2, обрабатывает программы на языке Си, Си++, Фортран, Ада, Java и некоторых других

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

Поддержка спекулятивного выполнения команд выполнена для двух планировщиков GCC существующего планировщика и селективного планировщика команд, улучшенного и доработанного для компилятора GCC в Институте системного программирования РАН

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

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

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

Инструкции, реализующие легальные спекулятивные перемещения, попадают в список готовых инструкций После этого производится оценка выгоды этих перемещений При оценке выгоды перемещений по управлению из точки У в точку ЛГ всегда рассматривается случай, когда X доминирует над У (то есть если выполняется У, то обязательно выполняется и X), так как только такие перемещения поддерживаются планировщиком При этом создание восстановительной копии не требуется

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

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

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

• Обычная инструкция всегда предпочитается спекулятивной,

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

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

16

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

• Запрос о том, какие типы спекулятивного выполнения (по данным или по управлению) поддерживает архитектура,

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

• Запрос на преобразование инструкции, подготавливаемой к спекулятивному выполнению определенного типа, к виду (во внутреннем представлении), который она примет при этом Для Itanium, например, при передаче инструкции загрузки из памяти в качестве параметра необходимо вернуть инструкцию во внутреннем представлении, соответствующую Id. s или Id. а,

• Запрос на создание инструкции проверки для данного типа спекулятивного выполнения,

• Запрос на то, нужен ли блок восстановления для данной инструкции данного типа спекулятивного выполнения, или же можно обойтись инструкцией проверки

• Запрос на расширение структур данных при создании новых инструкций (нового базового блока)

В результате тестирования реализованного алгоритма на пакете SPEC CPU FP 2000 наилучший результат достигнут с использованием профиля программы - среднее ускорение по тестам из SPEC составило 2 88% при использовании только спекулятивного выполнения по данным, при этом отдельные тесты ускоряются на 12 7% и 17 9% Для хороших результатов спекулятивного выполнения по управлению необходимо профилирование вероятностей выполнения отдельных путей

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

Таблица 1. Результаты тестирования на SPEC FP 2000 (с учетом профилирования).

Тесты Без Отсечка 40% Отсечка 20% Отсечка 0% Отсечка 20%,

спекулятивных только по

команд данным

168 wupwise 535 0,93% 0,93% 1,31% 1,31%

171 swim 710 0,42% 0,14% -0,14% -0,14%

172 mgrid 328 1,22% 1,52% 1,52% 1,22%

173 applu 530 -0,19% -0,19% -0,19% 0,38%

177 mesa 905 3,43% 3,43% 2,76% 5,41%

178 galgel 920 1,74% 3,37% 1,85% 1,96%

179 art 2025 16,44% 17,58% 16,59% 17,93%

183 equake 499 2,81% 3,41% 3,61% 3,21%

187 facerec 391 0,51% 0,51% 0,26% 0,51%

188 ammp 684 12,43% 12,72% 12,72% 12,72%

189 lucas 880 0,00% 0,00% 0Д1% 0,00%

191 fma3d 279 0,72% 1,08% 0,72% 1,08%

200 sixtrack 307 -5,54% -5,54% -5,86% -5,54%

301 apsi 475 2,53% 2,11% 2Д1% 2,32%

SPEC FP GeoMean 583,6251 2,55% 2,79% 2,53% 2,88%

Планирование региона осуществляется с помощью главного цикла

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

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

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

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

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

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

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

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

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

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

Основные результаты диссертационной работы.

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

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

3 На основе предложенного метода разработан и реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC Проведена апробация алгоритма на пакете тестов SPEC CPU 2000.

Результаты диссертации опубликованы в следующих работах:

1 А А Белеванцев, С С Гайсарян, В П Иванников Построение алгоритмов спекулятивных оптимизаций Журнал Программирование, N3 2008, с 122

2 Andrey Belevantsev, Alexander Chernov, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik Improving GCC instruction scheduling for Itanium In Proceedings of GCC Developers' Summit 2005, Ottawa, Canada, June 2005, pp 1-14

3 Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik, Dmitry Zhunkhin An interblock VLIW-targeted instruction scheduler for GCC In Proceedings of GCC Developers' Summit 2006, Ottawa, Canada, June 2006, pp 1-12

4 А Белеванцев, M Кувырков, Д Мельник Использование параллелизма на уровне команд в компиляторе для Intel Itanium Труды ИСП РАН, т 9,

2006, с 9-22

5 Andrey Belevantsev, Maxim Kuvyrkov, Alexander Monakov, Dmitry Melnik, and Dmitry Zhunkhin Implementing an instruction scheduler for GCC progress, caveats, and evaluation In Proceedings of GCC Developers' Summit

2007, Ottawa, Canada, July 2007, pp 7-21

6 Andrey Belevantsev, Dmitry Melnik, and Arutyun Avetisyan Improving a selective scheduling approach for GCC GREPS International Workshop on

GCC for Research in Embedded and Parallel Systems, Brasov, Romania, September 2007 http //sysrun haifa ll lbm com/hrl/greps2007/ 7 Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik GCC instruction scheduler and software pipelining on the Itanium platform 7th Workshop on Explicitly Parallel Instruction Computing Architectures and Compiler Technology (EPIC-7) Boston, MA, USA, April 2008 http //rogue Colorado edu/EPIC7/avetisyan pdf

Заказ № 53/09/08 Подписано в печать 08 09 2008 Тираж 70экз Уел пл 1,5

ООО "Цифровичок", тел (495) 797-75-76, (495) 778-22-20 U, - ;) www cfr ru, e-mail info@cfr ru

Введение

Глава 1. Методы спекулятивного выполнения и оптимизации.

1.1. Используемая терминология.

1.1.1 Анализ потока управления и потока данных.

1.1.2 Зависимости по данным и по управлению.

1.2. Спекулятивное выполнение команд.

1.2.1 Аппаратные механизмы поддержки спекулятивного выполнения.

1.2.2 Спекулятивное выполнение, контролируемое компилятором.

1.2.3 Спекулятивное выполнение в Intel Itanium.

1.3. Алгоритмы вероятностного анализа потока данных и управления.

1.3.1 Анализ потока управления.

1.3.2 Алгоритмы анализа указателей.

1.3.3 Алгоритмы анализа зависимостей по данным между массивами.

1.3.4 Вероятностные алгоритмы анализа потока данных.

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

1.4.1 Существующие подходы к планированию команд.

1.4.2 Использование спекулятивных перемещений при планировании команд.

1.4.3 Спекулятивное удаление частичной избыточности.

1.4.4 Спекулятивное расширение представления с единственным присваиванием (SSA).

Глава 2. Построение алгоритмов спекулятивных оптимизаций.

2.1. Преобразование консервативной оптимизации в спекулятивную.

2.1.1 Понятие спекулятивной оптимизации.

2.1.2 Схема выполнения спекулятивной оптимизации.

2.2. Пример построения спекулятивной оптимизации.

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

2.3.1 Спекулятивные перемещения инструкции программы.

2.3.2 Вероятностные алгоритмы построения зависимостей по данным и по управлению.

2.3.2.1 .Зависимости по управлению.

2.3.2.2.Зависимости по данным.

Использование профилирования.

Эвристики.

2.3.3 Построение легальных и выгодных спекулятивных преобразований.

2.4. Построение кода восстановления.

Глава 3. Реализация спекулятивного перемещения в планировании команд.

3.1. Общее устройство компилятора GCC.

3.1.1 Планировщик команд компилятора GCC.

3.2. Реализация спекулятивного выполнения в планировщике команд компилятора

3.2.1 Расширение и инициализация структур данных.

3.2.2 Помещение спекулятивных инструкций в список планирования .1.

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

3.2.4 Выдача спекулятивных инструкций.

3.2.5 Машинно-зависимая поддержка спекулятивного выполнения.

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

3.3. Селективное планирование команд.

3.3.1 Основные процедуры селективного планирования.

3.3.2 Вычисление множества доступных инструкций.

3.3.3 Перемещение запланированной инструкции.

3.4. Реализация спекулятивного выполнения в селективном планировщике команд.

3.4.1 Анализ зависимостей для спекулятивного выполнения.

3.4.2 Выполнение спекулятивного преобразования.

3.4.3 Описание спекулятивных команд для Intel Itanium.

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

Актуальность.

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

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

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

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

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

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

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

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

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

Основные результаты. В работе получены следующие основные результаты, обладающие научной новизной:

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

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

3. На основе предложенного метода разработан н реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC. Проведена апробация алгоритма па пакете тестов SPEC CPU 2000.

Практическая ценность. Разработанное спекулятивное планирование команд было одобрено сообществом разработчиков компилятора GCC для включения в основную ветвь разработки. Данная оптимизация является частью GCC с марта 2006 года и включена в официальный релиз компилятора, начиная с версии 4.2.0. Части разработанных механизмов поддержки спекулятивного выполнения используются при реализации нового алгоритма планирования команд для компилятора GCC в рамках проекта, выполняемого Институтом системного программирования РАН для компании Hewlett-Packard.

Апробация работы. Основные результаты диссертационной работы изложены в статьях [1-7] и представлены в докладах на следующих конференциях и семинарах:

1. Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Р.Шуры-Буры в ноябре 2006 года;

2. Конференции GCC & GNU Toolchain Developers' Summit в июне 2005, июне 2006 года и шопе 2007 года;

3. Тихоновских чтениях на факультете ВМиК МГУ в октябре 2006 года;

4. Втором семинаре Федерации Гелато (2nd Gelato GCC Workshop in Moscow) no улучшению компилятора GCC для платформы Intel Itanium в августе 2006 года;

5. Семинаре GREPS 2007 по исследованию компиляторных технологий с помощью пакета GCC в сентябре 2007 года.

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации составляет 103 страницы. Диссертация содержит 6 таблиц и 24 рисунка. Список литературы насчитывает 81 наименование.

Заключение

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

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

На основе предложенного метода разработан и реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC. Проведена апробация алгоритма на пакете тестов SPEC CPU 200, при этом среднее ускорение на пакете тестов SPEC INT 2000 составило 1.5%, на пакете SPEC FP 2000 - 2.8%. Кроме того, выполнена реализация поддержки спекулятивного выполнения для селективного планирования и конвейеризации циклов, доработанных и реализованных для компилятора GCC в Институте системного программирования РАН. По результатам тестирования среднее ускорение для спекулятивной конвейеризации циклов на пакете SPEC CPU FP 2000 составило 11.2%, что является трудно достижимым результатом для промышленного компилятора.

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

1. А.А.Белеванцев, С.С.Гайсарян, В.П.Иванников. Построение алгоритмов спекулятивных оптимизаций. Журнал Программирование, N3 2008, с. 1-22.

2. Andrey Belevantsev, Alexander Chernov, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik. Improving GCC instruction scheduling for Itanium. In Proceedings of GCC Developers' Summit 2005, Ottawa, Canada, June 2005, pp. 1-14.

3. Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik, Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler for GCC. In Proceedings of GCC Developers' Summit 2006, Ottawa, Canada, June 2006, pp. 1-12.

4. А. Белеванцев, M. Кувырков, Д. Мельник. Использование параллелизма на уровне команд в компиляторе для Intel Itanium. Труды ИСП РАН, т.9, 2006, с.9-22.

5. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий. Второе издание. Москва, Вильяме, 2008.

6. X. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

7. Alfred Aburto's system benchmarks, ftp://gd.tuwien.ac.at/perf/benchmark/aburto

8. D. F. Bacon, S. L. Graham, and O. J. Sharp. Compiler transformations for high-performance computing. ACM Computer Surveys 26, 4 (Dec. 1994), pp. 345-420.

9. Thomas Ball and James R. Laais. Optimally Profiling and Tracing Programs. ACM Transactions on Programming Languages and Systems, Vol 16, No. 4, July 1994, pp. 13191360.

10. Thomas Ball and James R. Larus. Branch prediction for free. Proceedings of the S1GPLAN '93 Conference on Programming Language Design and Implementation (PLDI), pp. 300-313, June 1993.

11. Thomas Ball and James R. Larus. Efficient path profiling. In Proceedings of the 29th Annual ACM/IEEE international Symposium on Microarchitecture (Paris, France, December 02 04, 1996), pp. 46-57.

12. J. Bharadwaj, K.N. Menezes, and C. McKinsey. Wavefront Scheduling: Path-Based Data Representation and Scheduling of Subgraphs. In Proceedings of the 32nd Annual International Symposium on Microarchitecture (MICR032), (Haifa, Israel), December 1999.

13. Rostislav Bodik. Path-Sensitive, Value-Flow Optimizations of Programs. Ph.F. Thesis, University of Pittsburgh, 1999.

14. R. A. Bringmann. Enhancing instruction level parallelism through compiler controlled optimization. M.S Thesis, University of Illinois, 1992.

15. Peng-Sheng Chen, Yuan-Shin Hwan, Roy Dz-Ching Ju, and Jenq Kuen Lee. Interprocedural Probabilistic Pointer Analysis. IEEE Trans. Parallel Distrib. Syst. 15, 10 (Oct. 2004), pp. 893-907.

16. F. C. Chow, S. Chan, S. Liu, R. Lo and M. Streich. Effective Representation of Aliases and Indirect Memory Operations in SSA Form. In Proceedings of the 6th international

17. Conference on Compiler Construction (April 24 26, 1996), Lecture Notes In Computer Science, vol. 1060. Springer-Verlag, London, pp. 253-267.

18. D. A. Connors. Memory profiling for directing data speculative optimizations and scheduling. Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, 1997.

19. Jeffrey Da Silva. A Probabilistic Pointer Analysis for Speculative Optimizations. Master's Thesis, University of Toronto, 2006.

20. Saumya Debray, Robert Muth, and Matthew Weippert. Alias analysis of executable code. In The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 12-24, Orlando, Florida, Jan. 19-21, 1998.

21. B. Deitrich, B. Cheng, and W. Hwu. Improving Static Branch Prediction in a Compiler. In Proceedings of the 1998 international Conference on Parallel Architectures and Compilation Techniques (October 12 18, 1998). PACT, p. 214.

22. B. Deitrich and W. Hwu. Speculative hedge: regulating compile-time speculation against profile variations. Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture (MICRO-29), p p.70-79, December 02-04, 1996, Paris, France.

23. L. С. V. Dos Santos. A method to control compensation code during global scheduling. Proceedings of the ProRISC CSSP97 Workshop, pp. 457-464.

24. Carole Dulong, Rakesh Krishnaiyer, Dattatraya Kulkami, Daniel Lavery, Wei Li, John Ng, and David Sehr. An overview of the Intel IA-64 compiler. Intel Technology Journal, November 1999.

25. Kemal Ebcioglu. Some design ideas for a VLIW architecture for sequential natured software. In Parallel Processing (Proceedings of IFIP WG 10.3 Working Conference on Parallel Processing), North Holland, Amsterdam, pp. 3-21, 1988.

26. Manuel Fernandez and Roger Espasa. Speculative Alias Analysis for Executable Code. In the 2002 International Conference on Parallel Architectures and Compilation Techniques (PACT'2002), September 2002.

27. Joseph A. Fisher. Global Code Generation for Instruction-Level Parallelism: Trace Scheduling-2. Hewlett-Packard Technical Report #HPL-93-43, http://www.hpl.hp.com/techreports/93/HPL-93-43.html.

28. Manoj Franklin. The Multiscalar Architecture. Ph.D. Thesis, University of Wisconsin-Madison, 1993.

29. Chao-ying Fu, Matthew D. Jennings, Sergei Y. Larin, Thomas M. Conte. Software-Only Value Speculation Scheduling. Technical Report, Dept. of Electrical and Computer Eng., North Carolina State University, June 1998.

30. David M. Gallagher. Memory Disambiguation to Facilitate Instruction-Level Parallelism Compilation. Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1995.

31. GCC, GNU Compiler Collection, http://ecc.gnu.org

32. GCC Compiler Internals, http://gcc.gnu.org/onlinedocs/gccint

33. Rajiv Gupta, David A. Berson, and Jesse Z. Fang. Path profile guided partial redundancy elimination using speculation. IEEE International Conf. Computer Languages, pp.230-239, IEEE Society Press, 1998.

34. R. N. Iiorspool and H. С. Ho. Partial Redundancy Elimination Driven by a Cost-Benefit Analysis. In Proceedings of the 8th Israeli Conference on Computer-Based Systems and Software Engineering (June 18 19, 1997). ICCSSE.

35. A. S. Huang, G. Slavenburg, and J. P. Shen. Speculative disambiguation: a compilation technique for dynamic memory disambiguation. SIGARCH Comput. Archit. News 22, 2 (Apr. 1994), pp. 200-210.

36. S. J. Jackson, J. Ke, and P. Ratanaworabhan. The VPC Trace-Compression Algorithms. IEEE Trans. Comput. 54, 11 (Nov. 2005), pp. 1329-1344.

37. Q. Jacobson, E. Rotenberg and J.E. Smith. Path-based next trace prediction. In Proceedings of the 30th Annual ACM/IEEE international Symposium on Microarchitecture (MICRO-30), pp.14-23.

38. Roy Dz-ching Ju, Jean-Franois Collard, and Karim Oukbir. Probabilistic memory disambiguation and its application to data speculation. SIGARCH Comput. Archit. News 27, 1 (Mar. 1999), pp. 27-30.

39. Roy Dz-ching Ju, Kevin Nomura, Uma Mahadevan, Le-Chun Wu. A Unified Compiler Framework for Control and Data Speculation. PACT'OO, p. 157, 2000.

40. James R. Larus. Whole program paths. SIGPLAN Not. 34, 5 (May. 1999), pp. 259-269.

41. J. Lin, T. Chen, W. Hsu, P. Yew, R. D. Ju, T. Ngai and S. Chan. A compiler framework for speculative analysis and optimizations. SIGPLAN Not. 38, 5 (May. 2003), pp. 289-299.

42. J. Lin, W. Hsu, P. Yew, R.D. Ju, and T. Ngai. Recovery code generation for general speculative optimizations. ACM Trans. Archit. Code Optim. 3, 1 (Mar. 2006), pp. 67-89.

43. Link Time Optimizations for GCC. http://gcc.gnu.org/wiki/LinkTimeOptimization

44. S. A. Mahlke, W.Y. Chen, R.A. Bringmann, R.E.Hank, W.-M.Hwu, B.R.Rau, and M.S.Schlansker. Sentinel scheduling: a model for compiler-controlled speculative executions. ACMTrans. Comput. Syst., 11,4, pp. 276^408, 1993.

45. Vladimir Makarov. The finite state automaton based pipeline hazard recognizer and instruction scheduler in GCC. In Proceedings of GCC Developers' Summit, Ottawa, Canada, June 2003.

46. Eduard Mehofer and Bernhard Scholz. Probabilistic data flow system with two-edge profiling. In Proceedings of the ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization DYNAMO '00. ACM, New York, NY, pp. 65-72.

47. Soo-Mook Moon and Kemal Ebcioglu. Parallelizing Nonnumerical Code with Selective Scheduling and Software Pipelining. ACM TOPLAS, Vol 19, No. 6, pages 853-898, November 1997.

48. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997, 3rd ed.

49. Alexandre Nicolau. Percolation Scheduling: a Parallel Compilation Technique. Technical Report. UMI Order Number: TR85-678, Cornell University, 1985.

50. Diego Novillo. GCC Internals Tutorial, http://www.airs.com/dnovillo/200711 -GCC-Internals

51. The OpenlMPACT Compiler, http://www.gelato.uiuc.edu

52. The Open Research Compiler (ORC). htlp://ipf-orc.sourceforge.net

53. The Open64 Compiler, http://www.open64.net

54. Alessandra Di Pierro, Chris Hankin, Herbert Wiklicky. A Systematic Approach to Probabilistic Pointer Analysis. APLAS 2007, pp. 335-350.

55. G. Ramalingam. Data flow frequency analysis. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation (Philadelphia, Pennsylvania, United States, May 21 -24, 1996). PLDI '96. ACM, New York, NY, pp. 267277.

56. M. Rim and R. Jain. Lower-bound performance estimation for high-level synthesis scheduling problem. IEEE Trans. CAD 13, 451-458. 1994.

57. RTL SSA checkin. http://gcc.gnu.org/viewcvs?view=rev&revision=32465

58. Eric Rotenberg, Quinn Jacobson, Yiannakis Sazeides and Jim Smith. Trace processors. In Proceedings of the 30th Annual International Symposium on Microarchitecture (MICRO-30), pp. 138-148, 1997.

59. P. W. Sathyanathan. Interprocedural Dataflow Analysis: Alias Analysis. Ph.D. Thesis. UMI Order Number AAI3026900. University of Stanford, 2001.

60. Michael S. Schlansker, B. Ramakrishna Rau. EPIC: An Architecture for Instruction-Level Parallel Processors. HP Laboratories Palo Alto Technical ReportHPL-1999-111, Februaiy 2000. http://www.hpl.hp.com/techreports/1999/HPL-1999-1 1 l.pdf

61. B. Scholz and E. Mehofer. Dataflow frequency analysis based on whole program paths. In Proceedings of the IEEE International Conference on Parallel Architectures and Compilation Techniques, PACT-2002.

62. Michael D. Smith. Support for Speculative Execution in High-Performance Processors. Ph.D. Thesis. UMI Order Number: CSL-TR-93-556. Stanford University.

63. Mark Smotherman. IBM Stretch (7030) Aggressive Uniprocessor Parallelism. http://www.cs.clemson.edu/~mark/stretch.html

64. SPEC CPU 2000 benchmarks, http://spcc.org/cpu2000

65. S. Swanson, L. K. McDowell, M. M. Swift, S. J. Eggers and H. M. Levy. An evaluation of speculative instruction execution on simultaneous multithreaded processors. ACM Trans. Comput. Syst. 21,3 (Aug. 2003), pp. 314-340.

66. S. Tallam, R. Gupta, Xiangyu Zhang. Extended whole program paths. In Proceedings of PACT 2005, pp. 17-26.

67. J. Xue and Q. Cai. A lifetime optimal algorithm for speculative PRE. ACM Trans. Archit. Code Optim. 3, 2 (Jun. 2006), pp. 115-155.

68. David W. Wall. Limits of instruction-level parallelism. In Proceedings of the Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , volume IV, pp. 176-188, April 1991.