Введение к работе
Актуальность.
Современные процессорные архитектуры обладают большим количеством паралелльно работающих конвейерных функциональных устройств. Для достижения высокой производительности на этих архитектурах требуется обеспечить непрерывную загрузку этих функциональных устройств, максимально используя параллелизм на уровне команд, имеющийся в программе. Компиляторной трансформацией, переупорядочивающей команды программы с целью получения максимальной загрузки ресурсов процессора, является планирование команд (и конвейеризация циклов, как специальный вид планирования). Следовательно, актуальной является задача о построении алгоритмов планирования команд, максимально использующих новые возможности современных архитектур.
Важным подходом к увеличению параллелизма на уровне команд является спекулятивное выполнение - опережающее выполнение команд прежде, чем становится известно, что их выполнение необходимо, либо что их операнды вычислены. Аппаратно спекулятивное выполнение применяется вместе с предсказанием переходов при конвейерном выполнении команд, однако для этого в процессоре должна быть реализована достаточно сложная функциональность, так как выполняемые команды не должны необратимо изменять состояние процессора, пока не станет известно, правильно ли предсказан переход. В архитектуре с явно выраженным параллелизмом команд (EPIC), реализованной в процессорах семейства Itanium, спекулятивной выдачей команд на выполнение управляет компилятор, что позволяет упростить логику процессора, а также просматривать больший объем исходного кода программы при выборе команд-кандидатов на спекулятивное выполнение. Однако, для этого компилятор должен уметь решать много новых задач - искать подходящие команды для спекулятивного выполнения, выбирать момент для их выдачи, генерировать необходимый код восстановления на случай их неудачного выполнении. Это обеспечивает актуальность задачи о поддержке спекулятивного выполнения команд, ориентированной на архитектуры с явно выраженным параллелизмом команд.
Кроме того, идея спекулятивного выполнения может использоваться компилятором не только при машинно-зависимых, но и при машинно-независимых оптимизациях. Обычно при статической оптимизации программ рассматриваются только такие преобразования, которые сохраняют семантику программы на всех возможных входных данных. Это серьезно ограничивает круг возможных преобразований, так как в процессе компиляции невозможно получить точную информацию о потоке данных программы. В частности, нельзя извлечь выгоду из ситуации, когда в результате проведения преобразования семантика программы может нарушиться лишь на некоторых, редко встречающихся, наборах входных данных.
Существует другой возможный подход: провести потенциально небезопасное преобразование, дополнительно обеспечив проверку его
корректности во время выполнения программы. Если для некоторых входных данных проведенное преобразование оказалось некорректным, то вставленная проверка восстановит первоначальную семантику программы, выполнив так называемое восстановительное преобразование. При этом, если выигрыш во времени выполнения программы от небезопасного преобразования на множестве входных данных, при которых оно является корректным, превышает накладные расходы на выполнение восстановительного преобразования в противном случае, то в целом построенное преобразование ускорит выполнение программы.
Алгоритмы оптимизации, допускающие такие небезопасные преобразования, по аналогии со спекулятивным выполнением команд процессором также называют спекулятивными. При выполнении этих оптимизаций компилятор должен выполнять большее количество действий по сравнению с выполнением обычных оптимизаций. Так, нужно определить множество выполнимых небезопасных преобразований, оценить эффективность каждого из них, выбрать множество "выгодных" (то есть ускоряющих выполнение программы) преобразований, построить для этих преобразований соответствующие восстановительные преобразования. В настоящее время все эти задачи решаются в компиляторах без использования каких-либо специализированных алгоритмов.
Следовательно, актуальной является задача о построении спекулятивных оптимизаций, как машинно-зависимых, ориентированных на архитектуры с явно выраженным параллелизмом, так и машинно-независимых.
В диссертационной работе предлагается следующая схема построения спекулятивной оптимизации. В отличие от обычного анализа потока данных, с необходимостью устанавливающего лишь достоверные свойства программы, выполнить вероятностный анализ, который аннотирует каждое найденное им свойство вероятностью его выполнения на некотором наборе входных данных. Далее с помощью найденных вероятностей установить те преобразования программы, которые, не являясь полностью корректными для некоторых входных данных (то есть использующие свойства программы, вероятность которых меньше единицы), тем не менее, могут ускорить выполнение программы. Наконец, построить для каждого выбранного преобразования соответствующее восстановительное преобразование.
Целью диссертационной работы является разработка подхода к спекулятивному планированию команд для современных архитектур, а также разработка методики построения статических спекулятивных оптимизаций на основе преобразования обычной оптимизации в её спекулятивный аналог. Кроме того, необходимо реализовать разработанный алгоритм спекулятивного планирования для архитектур с явно выраженным параллелизмом команд с помощью предложенной методики.
Основные результаты. В работе получены следующие основные результаты, обладающие научной новизной:
Предложена общая схема построения спекулятивных оптимизаций, основанная на понятии вероятностного анализа потока данных и оценке успеха спекулятивного преобразования программы.
Разработан и обоснован метод построения спекулятивных оптимизаций, преобразующих программу с помощью спекулятивных перемещений команд. Метод включает алгоритмы нахождения вероятностей зависимостей по данным и по управлению, построения множества возможных спекулятивных перемещений команд, оценки выгоды спекулятивного перемещения и построения кода восстановления.
На основе предложенного метода разработан и реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC. Проведена апробация алгоритма на пакете тестов SPEC CPU 2000.
Практическая ценность. Разработанное спекулятивное планирование команд было одобрено сообществом разработчиков компилятора GCC для включения в основную ветвь разработки. Данная оптимизация является частью GCC с марта 2006 года и включена в официальный релиз компилятора версии 4.2.0. Части разработанных механизмов поддержки спекулятивного выполнения используются при реализации нового алгоритма планирования команд для компилятора GCC в рамках проекта, выполняемого Институтом системного программирования РАН для компании Hewlett-Packard.
Апробация работы. Основные результаты диссертационной работы изложены в статьях [1-7] и представлены в докладах на следующих конференциях и семинарах:
Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Р.Шуры-Буры в ноябре 2006 года;
Конференции GCC & GNU Toolchain Developers' Summit в июне 2005, июне 2006 года и июне 2007 года;
Тихоновских чтениях на факультете ВМиК МГУ в октябре 2006 года;
Втором семинаре Федерации Гелато (2nd Gelato GCC Workshop in Moscow) по улучшению компилятора GCC для платформы Intel Itanium в августе 2006 года;
Семинаре GREPS 2007 по исследованию компиляторных технологий с помощью пакета GCC в сентябре 2007 года.
Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации составляет 103 страницы. Диссертация содержит 6 таблиц и 24 рисунка. Список литературы насчитывает 81 наименование.
