Введение к работе
Актуальность темы. Динамическая компиляция - это технология, позволяющая исполнять программу, представленную в кодах одной платформы (исходной), на другой платформе (целевой), причем преобразование кода исходной платформы в код целевой платформы происходит по мере исполнения.
Одним из важных и востребованных применений динамической компиляции является динамическая двоичная трансляция, при которой коды одной реально существующей аппаратной платформы исполняются с помощью двоичного транслятора на другой аппаратной платформе. Примерами систем динамической двоичной трансляции являются IA-32 Execution Layer фирмы Intel, Transmeta Code Morphing Software или Lintel компании ЗАО «МЦСТ».
Во время компиляции исходной программы в код целевой платформы происходит динамическая оптимизация программного кода - применение набора эквивалентных преобразований (отдельных оптимизаций), выполняемых с целью сокращения времени исполнения программы, уменьшения размера кода, экономии памяти, а также для достижения других критериев оптимизации. Так как время, затрачиваемое на оптимизацию, включается в общее время исполнения, то для систем, использующих динамическую компиляцию, важно применение быстрых алгоритмов оптимизации программы.
Умеренная оптимизация, применяемая в динамических компиляторах, является набором отдельных оптимизаций, применение которых приводит к компромиссу между качеством результирующего кода и временем, затрачиваемым на его получение. Использование умеренной оптимизации приводит к уменьшению времени работы всей системы в целом.
Доля количества команд передачи управления от общего количества команд в современных приложениях достигает 20% и более, поэтому оптимизации переходов являются важной составляющей любого оптимизирующего компилятора, то есть компилятора, выполняющего оптимизацию программного кода.
В ЗАО «МЦСТ» разрабатываются микропроцессоры архитектуры «Эльбрус». Технология динамической двоичной трансляции обеспечивает полную совместимость архитектуры «Эльбрус» с архитектурой Intel х86. Для вычислительного комплекса «Эльбрус» разработана аппаратно поддерживаемая система динамической двоичной трансляции Lintel, позволяющая исполнять приложения х86 на микропроцессорах
«Эльбрус» путем перевода исполняемого кода х86 в исполняемый код «Эльбрус». В состав Lintel входит оптимизирующий компилятор базового уровня, выполняющий умеренную оптимизацию, создавая высокопроизводительный код за приемлемое время трансляции. Базовый оптимизирующий компилятор использует промежуточное представление программы, основой которого является граф потока управления (control flow graph, CFG), отражающий структуру передачи управления в программе. Из-за большой плотности команд перехода в исходном коде, а также особенностей реализации переходов в архитектуре «Эльбрус» оптимизации переходов являются важной составляющей частью базового компилятора, что определяет актуальность их исследования и разработки.
Цель работы. Цель работы состоит в исследовании возможностей оптимизации переходов в базовом компиляторе для уменьшения времени исполнения программы, разработке алгоритмов, позволяющих повысить производительность результирующего кода в условии дефицита времени компиляции, анализе эффективности и реализации данных алгоритмов.
В диссертационной работе решаются следующие задачи:
-
Исследование оптимизаций переходов, направленных на уменьшение времени исполнения программы.
-
Исследование и разработка алгоритма уменьшения количества переходов путем определения порядка расположения линейных участков результирующего кода в памяти (далее просто линеаризация).
-
Исследование и разработка алгоритма распределения специальных регистров переходов архитектуры «Эльбрус» с учетом совпадения адресов переходов.
-
Исследование и разработка алгоритма переноса специальных операций подготовки переходов внутри CFG.
-
Проведение теоретической оценки эффективности разработанных алгоритмов.
-
Реализация разработанных алгоритмов и получение экспериментальных результатов, подтверждающих их эффективность.
Методы исследования. В работе используются теоретические положения из областей системного программирования, технологии компиляции и двоичной
трансляции, математического моделирования, исследования операций, теории графов, теории вероятностей. Для проверки работоспособности и априорной оценки эффективности линеаризации использовалась модель для создания случайных 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 в журналах, входящих в перечень ВАК.
Структура и объем диссертационной работы. Диссертационная работа
