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

На правах рукописи

Рыбаков Алексей Анатольевич

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

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

21 „]ДШ

005539034

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

Москва 2013

005539034

Работа выполнена в ЗАО «МЦСТ».

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

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

начальник отделения ОАО «ИНЭУМ им. И. С. Брука», старший научный сотрудник.

Официальные оппоненты:

Амербаев Вильжан Мавлютинович,

доктор технических наук, академик HAH PK, профессор,

главный научный сотрудник ИППМ РАН;

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

кандидат физико-математических наук,

старший научный сотрудник ИСП РАН.

Ведущая организация:

Научно-исследовательский вычислительный центр МГУ

Защита диссертации состоится «7?» -YZ 2013 года час. J^mhh. на заседании диссертационного совета Д212.134.02 в Национальном исследовательском университете «МИЭТ» по адресу: 124498, Москва, Зеленоград, проезд 4806, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ.

Автореферат разослан / 2013 года.

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

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

Одним из важных и востребованных применений динамической компиляции является динамическая двоичная трансляция, при которой коды одной реально существующей аппаратной шйтформы исполняются с помощью двоичного транслятора на другой аппаратной платформе. Примерами систем динамической двоичной трансляции являются IA-32 Execution Layer фирмы Intel, Transmeta Code Morphing Software или Lintel компании ЗАО «МЦСТ».

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

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

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

В ЗАО «МЦСТ» разрабатываются микропроцессоры архитектуры «Эльбрус». Технология динамической двоичной трансляции обеспечивает полную совместимость архитектуры «Эльбрус» с архитектурой Intel х86. Для вычислительного комплекса «Эльбрус» разработана аппаратно поддерживаемая система динамической двоичной трансляции Lintel, позволяющая исполнять приложения х86 на микропроцессорах

«Эльбрус» путем перевода исполняемого кода х86 в исполняемый код «Эльбрус». В состав Lintel входит оптимизирующий компилятор базового уровня, выполняющий умеренную оптимизацию, создавая высокопроизводительный код за приемлемое время трансляции. Базовый оптимизирующий компилятор использует промежуточное представление программы, основой которого является граф потока управления (control flow graph, CFG), отражающий структуру передачи управления в программе. Из-за большой плотности команд перехода в исходном коде, а также особенностей реализации переходов в архитектуре «Эльбрус» оптимизации переходов являются важной составляющей частью базового компилятора, что определяет актуальность их исследования и разработки.

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

В диссертационной работе решаются следующие задачи:

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

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

3. Исследование и разработка алгоритма распределения специальных регистров переходов архитектуры «Эльбрус» с учетом совпадения адресов переходов.

4. Исследование и разработка алгоритма переноса специальных операций подготовки переходов внутри CFG.

5. Проведение теоретической оценки эффективности разработанных алгоритмов.

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

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

трансляции, математического моделирования, исследования операций, теории графов, теории вероятностей. Для проверки работоспособности и априорной оценки эффективности линеаризации использовалась модель для создания случайных CFG. Практическая оценка эффективности алгоритмов получена на основе замеров времени исполнения приложений CINT2000 из пакета SPEC CPU2000 на архитектуре «Эльбрус» под управлением Lintel.

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

Введены два критерия оптимальности распределения регистров переходов архитектуры «Эльбрус» для переходов по неповторяющимся адресам. Найдено оптимальное по обоим критериям распределение регистров переходов в узле CFG и доказана его оптимальность. Разработан новый алгоритм повторного использования регистров переходов при совпадении адресов переходов.

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

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

Основные научные и практические результаты, выносимые на защиту. В

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

• локальные атомарные преобразования CFG и формулы корректировки статистики исполнения (профиля исполнения);

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

2. Решение задачи линеаризации:

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

• быстрый алгоритм для нахождения приближенного решения;

• оценка эффективности разработанного быстрого алгоритма;

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

3. Решение задачи распределения регистров переходов архитектуры «Эльбрус»:

• критерии оптимальности распределения регистров переходов;

• нахождение оптимального по данным критериям распределения регистров переходов для переходов по разным адресам, доказательство оптимальности данного распределения;

• алгоритм повторного использования регистров переходов при совпадении адресов переходов.

4. Эвристический алгоритм переноса операций подготовок переходов внутри CFG для уменьшения критического пути исполнения программы:

• алгоритм переноса подготовок переходов с разрешением конфликтов по регистрам переходов;

• подбор эвристик для повышения эффективности работы алгоритма.

Апробация работы. Результаты диссертационной работы представлены на

конференции Parallel and Distributed Computing Systems 2013 (PDCS'13), в г. Харьков, в 2013 г.; на конференции High Performance Computing 2012 (HPC-UA'12), в г. Киев, в 2012 г.; на V Международной научно-практической конференции «Современные информационные технологии и ИТ-образование», в г. Москва, в 2010 г.

Публикации. По материалам диссертации опубликовано 6 печатных работ, в том числе 3 в журналах, входящих в перечень ВАК.

Структура и объем диссертационной работы. Диссертационная работа

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

-6,

указателя и библиографического списка, содержащего 91 наименование. Диссертационная работа изложена на 152 страницах машинописного текста и содержит 31 рисунок, одну таблицу и 17 графиков.

Основное содержание диссертационной работы.

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

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

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

количество и вероятность переходов по дугам CFG (счетчики и вероятности дуг, си(е),т(е)).

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

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

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

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

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

Во второй главе приведено расширенное определение и описание свойств CFG со статическим профилем исполнения. Для проверки работоспособности и априорной оценки эффективности линеаризации предлагается механизм построения случайных CFG с корректным профилем исполнения. Построение CFG представляет собой применение последовательности атомарных преобразований CFG к начальному

элементарному CFG, состоящему из глобального входа и глобального выхода, соединенных ребром (рис. 1 а).

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

V

в

га

е

га

е,

га

га

е,

га

е,

Ф

е.

га б)

Рис. 1. Элементарные преобразования CFG.

Всего предложен набор из пяти атомарных преобразований. Первое из них -помещение узла на ребро - позволяет создать новый узел CFG на выбранном ребре е (рис. 1. б). Профиль исполнения при этом корректируются следующим образом: Тп: w(v) = ы(е), ш^) = со(е2) = ш(е),т(ег) = г(е),т(е2) = 1.

Добавление кратного pie6pa (рис. 1. в) позволяет дублировать выбранное ребро е, перераспределяя поток управления между ним и созданной копией в пропорции а:

а ш(е) а т(е)

Ге: шСеО = —— ш(е),ш(е2) = —_,т(е1) = ——т(е),т(е2) = ——.

1 + а 1 + а l + ct 1 + а

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

Tt: ш(е) = --ш(у),т(е) = t,co(v') = --,т(е2) = 1 - т.

1 — т 1 — т

Растягивание узла в ребро (рис. 1. д) вместо одного узла v создает два, один из которых наследует все входящие ребра исходного узла, а другой - выходящие:

Tx: wOj) = co(v2) = co(v), cu(e) = ü)(v),t(e) = 1.

Растягивание узла в ребро со случайным перераспределением инцидентных ребер (рис. 1. е) также дублирует узел v, но обладает способностью случайно перераспределять любое инцидентное ребро исходного узла на один из новых узлов (ребра е3, е4 в общем случае являются множествами ребер, ш(ег) > ¿о(е3)): Tr: wivj = w(ei),£o(v2) = <u(e4),w(e) = aifo) - со(е3),

co^e-J cofo)

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

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

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

Будем говорить, что два узла CFG соединены провалом (или fall through переходом), если после исполнения последней команды первого узла управление должно передаться на второй узел не вследствие выполнения команды перехода. Если два узла, соединенные провалом, записаны в память не последовательно, то вместо провала придется построить команду перехода. Это, естественно, негативно отразится на производительности результирующего кода. Поэтому для уменьшения количества операций переходов между узлами CFG требуется, чтобы как можно больше пар узлов, связанных провалами, располагались в памяти последовательно (при этом будем говорить, что провал удалось использовать).

Очевидно, что два провала, ведущих на один и тот же узел не могут быть использованы одновременно (конфликтующие провалы). Также не могут быть одновременно использованы все провалы, образующие ориентированный цикл. Формулируется и доказывается теорема 3.1, утверждающая следующее: если множество провалов D таково, что в нем нет конфликтов и циклов, то все провалы данного множества можно использовать одновременно. Данная теорема позволяет поставить задачу отыскания оптимального подмножества используемых провалов в терминах линейного программирования. Рассматривается граф, полученный из CFG удалением всех ребер, не являющихся провалами, и всех узлов, не инцидентных ни одному провалу. Такой граф назовем графом провалов (fall through graph, FTG).

Для определения оптимального подмножества провалов, которые можно использовать, ставится задача линейного программирования максимизации суммы счетчиков провалов, которые удалось использовать. Задача максимизации представлена в виде:

где п — количество провалов, N — множество номеров провалов (Ы = [1,п]), = со(ег) - счетчик соответствующего провала, - битовая переменная, принимающая значение 1 или 0 в зависимости от того, используется ли данный провал или нет, М]- - множества провалов с общим входным узлом (ш не превышает порядок КТО), К] - множества провалов, образующих циклы (к - количество циклов в

Данная задача решается с помощью целочисленного симплекс-метода.

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

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

teMjcN

ViEKjCN

FTG).

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

После описания быстрого алгоритма линеаризации проводится теоретическая оценка его решения по сравнению с оптимальным решением. Сформулирована и доказана теорема 3.3, утверждающая, что для ациклической компоненты связности FTG быстрый алгоритм находит оптимальное решение. Сформулирована и доказана теорема 3.4, утверждающая, что для каждой содержащей цикл компоненты связности FTG справедлива оценка Mopt - Mgreedy < <d(emin), где Mopt - сумма счетчиков использованных провалов при оптимальном решении, Мдгеейу - сумма счетчиков использованных провалов при применении быстрого алгоритма, emin - провал из цикла с минимальным счетчиком.

Долей использованных провалов назовем отношение количества использованных провалов к общему количеству провалов в FTG. Для случайных CFG формулируется и доказывается следующая теорема 3.5. Средняя доля использованных провалов для случайных CFG порядка п при условии оптимальной работы быстрого алгоритма подчиняется соотношению

1

lim Fn = 1--

n-too е

Из доказательства данной теоремы также вытекает значение математического ожидания и дисперсии средней доли использованных провалов для случайных CFG порядка п, где п достаточно велико:

JL

Во второй части главы рассматривается задача распределения регистров переходов архитектуры «Эльбрус» в узле CFG. Всего существует три регистра перехода (CI, С2, СЗ). Для осуществления перехода (BRANCH) для него должен быть

-12-

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

Рис. 2. Распределение регистров переходов для двух последовательных переходов.

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

Таким образом, использование одного и того же регистра для двух последовательных переходов на разные адреса негативно влияет на планирование переходов. Для определения эффективности распределения регистров в рамках одного узла CFG будем пользоваться следующим критерием: между переходами по одному и тому же регистру должно быть как можно больше переходов по другим регистрам. Пусть в узле CFG находится п переходов (с номерами от 1 до n), q -регистр i-го перехода, т; - его вероятность, a р; - количество предшествующих переходов по регистрам, отличным от с(. Тогда оптимальным распределением регистров переходов с точки зрения перемешивания регистров переходов назовем распределение, при котором максимума достигает функция

i=i

n

Пусть также 7} - наименьший номер широкой команды «Эльбрус» от начала узла, в которой может быть спланирован ¿-ый переход, если учитывать зависимости только от подготовки перехода и других операций перехода. Тогда оптимальным распределением регистров переходов с точки зрения планирования результирующего кода назовем распределение, при котором минимума достигает функция, соответствующая средней длине исполнения узла:

Сформулированы и доказана две теоремы (3.6 и 3.7), утверждающие, что для переходов по различным адресам с ненулевыми вероятностями, оптимальным распределением регистров переходов является циклическое назначение регистрам переходов последовательных номеров (например, [1, 2, 3, 1, 2, 3,...]).

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

п

L(n,T) = У Т1Ь

¡=1

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

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

Рис. 3. Перенос подготовок переходов между узлами CFG.

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

-15 -

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

Данный алгоритм переноса подготовок переходов между узлами CFG имеет сложность O(vlogv + Z(v + £)), где v - порядок CFG, е - его размер, I - среднее количество операций в узле CFG. Результат работы данного алгоритма существенным образом зависит от планирования результирующего кода, и точных критериев целесообразности его применения нет. Вместо этого используется целый набор эвристических правил, соответствие которым приводит к повышению производительности результирующего кода.

В четвертой главе приведены экспериментальные результаты применения разработанных алгоритмов. Данные алгоритмы реализованы на языке Си в оптимизирующем компиляторе базового уровня системы Lintel, Они прошли тестирование на различных пакетах задач, среди которых SPEC CPU2000, SPEC CPU95, исполняемые файлы Windows 2000, Linux, DOS, специальные тестовые пакеты для анализа производительности, а также тесты генератора исполняемых файлов х8б.

Априорная оценка эффективности линеаризации получена путем применения быстрого алгоритма на случайных CFG, сгенерированных с помощью методов, описанных в главе 2. Анализировались случайные выборки CFG с количеством вершин, равным 100 (рис. 4), 500 и 1000 (рис. 5). Размер каждой выборки равен 1000 штук. Эффективность оптимизации оценивалась по следующим характеристикам:

1*1' " ле.Ео>аеу

где Е - множество всех провалов, Е' - множество использованных провалов. Таким образом, характеристика F представляет собой долю использованных провалов, aFM-долю использованных провалов с учетом профиля исполнения (F%, F^ -соответствующие доли использованных провалов, выраженные в процентах).

100% 90% 80% 70% 60% 50% 40% 30% 20%

процент использованных провалов с учетом профиля исполнения — процент использованных провалов

Рис. 4. Процент использованных провалов при линеаризация для случайных CFG порядка 100 (представлены данные 1000 последовательных экспериментов)

100% -Т

А/[**] » 04.8Я-. П[Р%] « 2. М2 ЩР*) « 86. зя. « 10. ГА2

30%

процент использованных провалов с учетом профиля исполнения —процент использованных провалов

Рис. 5. Процент использованных провалов при линеаризация для случайных CFG порядка 1000 (представлены данные 1000 последовательных экспериментов)

Для величин F% и Fj° по данным, представленным на рис. 4 и рис. 5 вычислены значения математического ожидания и дисперсии. Значения математического ожидания и дисперсии для величины F% хорошо соотносятся с аналитически полученными значениями математического ожидания и дисперсии доли использованных провалов, полученных из теоремы 3.5 (таблица 1). Кроме того, данные о процентных долях использованных провалов, полученные на задачах пакета SPEC CINT2000 также свидетельствуют об адекватности модели, разработанной для создания случайных CFG (рис. 6).

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

M[F%], экспер. M[F%], аналит. D[F%], экспер. D[F%], аналит.

п= 100 65 % 63,2 % 20,5 %2 23,3

п = 500 64,9 % 63,2 % 4,4 %2 4,6 %2

п= 1000 64,8 % 63,2 % 2,4 %2 2,3

(F%)„ » 64. [УХ. (F%}4 ss G4.8% {F*)a » S3.9%. (F« 83. S'K юои ------

■ процент использованныхпровалов

ш процент использованных провалов суметом профиля исполнения

Рис. 6. Процент использованных провалов при линеаризации на задачах пакета SPEC

CINT2000

(j>erf)a* 3.9%

[ Приближенный алгоритм es Симплекс-метод

Рис. 7. Прирост производительности на задачах SPEC CINT2000 вследствие выполнения линеаризации с помощью разработанного быстрого алгоритма и с помощью симплекс-метода.

Рис. 8. Суммарный прирост производительности на задачах пакета SPEC CINT2000, полученный вследствие применения разработанных оптимизаций переходов.

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

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

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

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

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

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

3. Исследованы и разработаны новые алгоритмы оптимизации переходов.

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

• Введены два критерия эффективности распределения регистров переходов архитектуры «Эльбрус». Найдено распределение регистров переходов в узле CFG, являющееся оптимальным по обоим критериям, и доказана его оптимальность. Разработан новый алгоритм повторного использования регистров переходов при совпадения адресов переходов.

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

• Определена алгоритмическая сложность разработанных алгоритмов.

4. Выполнена практическая реализация и оценка эффективности разработанных алгоритмов.

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

• Применение разработанных алгоритмов оптимизаций переходов привело к повышению производительности результирующего кода. Средний прирост производительности, полученный вследствие применения разработанных алгоритмов, на задачах пакета SPEC CINT2000 составил около 5% (от 2% до 8% в зависимости от задачи). Применение разработанных алгоритмов оптимизации переходов в большинстве случаев приводит к уменьшению времени компиляции.

• На всех задачах пакета SPEC CINT2000 решение разработанного быстрого алгоритма линеаризации оказалось оптимальным.

-21-

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

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

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

[1] Рыбаков А. А., Алгоритм создания случайных графов потока управления для анализа глобальных оптимизаций в компиляторе. II Parallel and distributed computing systems PDCS 2013, Collection of scientific papers, Kharkiv, Ukraine, 2013, p. 269-275.

[2] Рыбаков А. А., Анализ алгоритмов оптимизации расположения в памяти линейных участков программы. II Известия вузов. Электроника, 2013, номер 1, с. 47-53.

[3] Рыбаков А. А., Оптимизация переходов в двоичном трансляторе для архитектуры «Эльбрус». II Программные продукты и системы, 2012, номер 4, с. 49-53.

[4] Рыбаков А. А., Оптимизация переходов в системе двоичной трансляции для архитектуры «Эльбрус». II High performance computing HPC-UA'2012, Conference proceedings, Kiev, Ukraine, 2012, p. 292-299.

[5] Воронов H. В., Гимпельсон В. Д., Маслов М. В., Рыбаков А. А., Сюсюкалов Н. С., Система динамической двоичной трансляции х8б —» «Эльбрус». II Вопросы радиоэлектроники, серия ЭВТ, Москва, 2012, выпуск 3, с. 89-108.

[6] Рыбаков А. А., Маслов М. В., Быстрый регионный компилятор системы двоичной трансляции для архитектуры «Эльбрус». II V Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Сборник избранных трудов, Москва, 2010, с. 436-443.

Подписано в печать:

Формат 60x84 1/16. Уч.-изд.л.

Тираж и<7экз. Заказ №

Отпечатано в типографии ИПК МИЭТ.

124498, г. Москва, г. Зеленоград, проезд 4806, д. 5, МИЭТ

ЗАО «МЦСТ»

На правах рукописи

04201451654

Рыбаков Алексей Анатольевич

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

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

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

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

Москва - 2013

Оглавление

Введение 5

Глава 1. Системы двоичной трансляции 14

1.1 Основные определения........................14

1.2 Особенности архитектуры «Эльбрус»...............18

1.3 Система динамической двоичной трансляции Lintel.......22

1.4 Базовый оптимизирующий компилятор..............25

1.5 Обзор систем двоичной трансляции................31

1.6 Оптимизации переходов.......................35

1.6.1 Использование задержек переходов ............35

1.6.2 Оптимизация последовательностей переходов.......36

1.6.3 Предсказание переходов...................37

1.6.4 Удаление лишних переходов путем слияния или расположения узлов........................39

1.6.5 Перемешивание подготовок переходов...........40

1.7 Выводы из главы 1..........................42

Глава 2. Моделирование промежуточного представления оптимизирующего компилятора 43

2.1 Граф потока управления и статический профиль исполнения . . 43

2.2 Создание случайного графа потока управления со статическим профилем исполнения........................47

2.3 Моделирование графа потока управления с помощью языка программирования Erlang......................57

2.4 Выводы из главы 2..........................66

Глава 3. Алгоритмы оптимизации переходов 67

3.1 Оптимизация линеаризации исполнения программы.......67

3.1.1 Постановка задачи......................70

3.1.2 Определение структуры графа провалов .........75

3.1.3 Приближенный алгоритм линеаризации исполнения программы ............................78

3.1.4 Оценка эффективности работы приближенного алгоритма 82

3.2 Локальное распределение подготовок переходов.........88

3.2.1 Оптимальное решение для переходов по неповторяющимся адресам...........................90

3.2.2 Использование истории переходов для распределения регистров переходов ......................95

3.3 Перенос операций подготовок переходов между узлами.....100

3.3.1 Общее описание оптимизации переноса операций между узлами.............................100

3.3.2 Алгоритм оптимизации переноса подготовок переходов между узлами.........................103

3.3.3 Определение сложности алгоритма.............108

3.4 Выводы из главы 3..........................109

Глава 4. Применение оптимизаций переходов в базовом компиляторе 111

4.1 Методика проведения измерений..................112

4.2 Тестовый пакет SPEC CPU2000 ................... 113

4.3 Общие характеристики задач пакета SPEC CPU2000 ...... 115

4.4 Алгоритм линеаризации исполнения программы.........121

4.5 Использование истории переходов.................128

4.6 Перенос подготовок переходов между узлами...........131

4.7 Суммарный эффект оптимизаций переходов...........133

4.8 Выводы из главы 4..........................134

Заключение

135

Список сокращений 138

Предметный указатель 139

Список литературы 143

Введение

Актуальность темы. Динамическая компиляция [1, 2, 3, 4, 5] — это технология, позволяющая исполнять программу, представленную в кодах одной платформы {исходной платформы), на другой платформе {целевой платформе), причем преобразование кода исходной платформы в код целевой платформы происходит по мере исполнения.

В качестве примеров динамической компиляции можно привести реализации таких языков программирования, как Java [6], Haskell [7], Erlang [8], Lua [9], Python (PyPy) [10] и других. В данных языках программирования исходный код сначала компилируется во внутреннее промеоюуточное представление (intermediate representation, IR) - байт-код, который впоследствии может быть исполнен на целевой платформе с помощью виртуальной машины.

Другим примером применения динамической компиляции является динамическая двоичная трансляция [11], при которой коды одной реально существующей аппаратной платформы исполняются с помощью двоичного транслятора на другой аппаратной платформе. Примерами систем динамической двоичной трансляции являются такие системы, как IA-32 Execution Layer фирмы Intel [12], Transmeta Code Morphing Software (CMS) [13], открытая система Valgrind[14] или Lintel компании ЗАО «МЦСТ» [15].

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

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

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

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

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

Эффективность оптимизации переходов существенным образом зависит от особенностей целевой архитектуры. Оптимизации переходов направлены на уменьшение разветвленности передачи управления, а значит, увеличивают линейность исполнения кода. Архитектуры с явно выраженным параллелизмом исполнения на уровне отдельных команд (explicitly parallel instruction computing, EPIC) быстрее исполняют код, содержащий меньшее количество команд передачи управления, так как длинные линейные участки исполняемого кода открывают более широкие возможности для параллельного исполнения. Разработка оптимизаций переходов для таких архитектур имеет важное значение.

В ЗАО «МСЦТ» разрабатываются микропроцессоры архитектуры «Эльбрус» [19, 20, 21, 22, 23]. Технология динамической двоичной трансляции обеспечивает полную совместимость архитектуры «Эльбрус» с архитектурой Intel х86 [24, 25]. Для вычислительного комплекса «Эльбрус» разработана аппа-ратно поддерживаемая система двоичной трансляции Lintel, которая эмулирует поведение машины х86 путем декодирования инструкций х86 и перевода их в коды архитектуры «Эльбрус». В состав системы двоичной трансляции

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

В процессе работы системы двоичной трансляции Lintel участки кода х86 переводятся в соответствующий код «Эльбрус» с помощью одного из уровней двоичного транслятора. Оттранслированный код может быть сохранен и исполнен многократно. Чем выше используемый уровень транслятора, тем выше качество результирующего кода, то есть скорость его исполнения, но тем больше и время, затрачиваемое на трансляцию. Для уменьшения общего времени работы кода х86 под управлением системы двоичной трансляции Lintel целесообразно выполнять трансляцию наиболее часто исполняемого кода с помощью более высокого уровня транслятора, а редко исполняемого кода - с помощью более низкого уровня. Пороги счетчиков исполнения кода, на которых происходит динамическое переключение между уровнями транслятора, выбираются эмпирически [26].

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

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

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

важной составляющей частью базового компилятора.

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

В диссертационной работе решаются следующие задачи:

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

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

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

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

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

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

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

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

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

Введены два критерия оптимальности распределения регистров переходов архитектуры «Эльбрус» для переходов по неповторяющимся адресам. Найдено оптимальное по обоим критериям распределение регистров переходов в узле промежуточного представления и доказана его оптимальность. Разработан новый алгоритм повторного использования регистров переходов при совпадении адресов переходов.

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

Разработанные алгоритмы реализованы в базовом оптимизирующем ком-

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

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

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

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

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

2. Решение задачи линеаризации исполнения программы:

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

• быстрый алгоритм для нахождения приближенного решения;

• оценка эффективности разработанного быстрого алгоритма;

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

3. Решение задачи распределения регистров переходов архитектуры «Эльбрус» :

• критерии оптимальности распределения регистров переходов;

• нахождение оптимального по данным критериям распределения регистров переходов для переходов по разным адресам, доказательство оптимальности данного распределения;

• алгоритм повторного использования регистров переходов при совпадении адресов переходов.

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

• алгоритм переноса подготовок переходов с разрешением конфликтов по регистрам переходов;

• подбор эвристик для повышения эффективности работы алгоритма.

Апробация работы. Результаты диссертационной работы представлены на конференции Parallel and Distributed Computing Systems 2013 (PDCS'13), в г. Харьков, в 2013 г.; на конференции High Performance Computing 2012 (НРС-UA'12), в г. Киев, в 2012 г.; на V Международной научно-практической конференции «Современные информационные технологии и ИТ-образование», в г. Москва, в 2010 г.

Содержание. Диссертационная работа состоит из четырех глав.

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

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

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

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