WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

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

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

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

МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ПЕРЕХОДОВ

В КОМПИЛЯТОРЕ БАЗОВОГО УРОВНЯ СИСТЕМЫ

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

Специальность 05.13.11.

Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени

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

Москва 2013

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

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

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

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

Амербаев Вильжан Мавлютинович, доктор технических наук, академик НАН РК, профессор, главный научный сотрудник ИППМ РАН;

Белеванцев Андрей Андреевич, кандидат физико-математических наук, старший научный сотрудник ИСП РАН.

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

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

Защита диссертации состоится 17 декабря 2013 года в 14 час. 30 мин. на заседании диссертационного совета Д212.134.02 в Национальном исследовательском университете «МИЭТ» по адресу: 124498, Москва, Зеленоград, проезд 4806, МИЭТ.



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

Автореферат разослан «__» ________ 2013 года.

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

доктор технических наук, доцент Гуреев А. В.

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

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

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

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

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

В ЗАО «МЦСТ» разрабатываются микропроцессоры архитектуры «Эльбрус».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Методика создания случайных CFG:

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





-5доказательство того, что с помощью предложенной методики может быть получен произвольный корректный 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указателя и библиографического списка, содержащего наименование.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

–  –  –

-9Растягивание узла в ребро со случайным перераспределением инцидентных ребер (рис. 1. е) также дублирует узел, но обладает способностью случайно перераспределять любое инцидентное ребро исходного узла на один из новых узлов (ребра 3, 4 в общем случае являются множествами ребер, (1 ) (3 )):

: 1 = 1, 2 = 4, = 1 3, (3 ) (3 ) = 1, 3 =, 4 = 1.

(1 ) (1 ) Преобразования, являются частными случаями преобразования.

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

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

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

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

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

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

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

Задача максимизации представлена в виде:

1, [1, ] 1, [1, ] где – количество провалов, – множество номеров провалов ( = [1, ]), = ( ) – счетчик соответствующего провала, – битовая переменная, принимающая значение 1 или 0 в зависимости от того, используется ли данный провал или нет, – множества провалов с общим входным узлом ( не превышает порядок FTG), – множества провалов, образующих циклы ( - количество циклов в FTG).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эффективность оптимизации оценивалась по следующим характеристикам:

() =, =, ()

–  –  –

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

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

–  –  –

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47-53.

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

49-53.

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

[5] Воронов Н. В., Гимпельсон В. Д., Маслов М. В., Рыбаков А. А., Сюсюкалов Н.

С., Система динамической двоичной трансляции x86 «Эльбрус». // Вопросы радиоэлектроники, серия ЭВТ, Москва, 2012, выпуск 3, с. 89-108.

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



Похожие работы:

«ВЕСТНИК Научно-технический журнал Издается с 2003 г. САРАТОВСКОГО Выходит один раз в квартал ГОСУДАРСТВЕННОГО Май 2007 г. ТЕХНИЧЕСКОГО Журнал включен в перечень ведущих УНИВЕРСИТЕТА рецензируемых журналов и научных изданий, утвержденный президиумом ВАК 2007 Министерства образов...»

«Труды Одесского политехнического университета, 2008, вып. 2(30) С.В. Бельтюкова, д-р. хим. наук, проф., УДК 615.074;543.426 А.А. Бычкова, магистр, Одес. нац. акад. пищевых технологий СОРБЦИОННО-ЛЮМИНЕСЦЕНТНОЕ ОПРЕДЕЛЕНИЕ КВЕРЦЕТИНА В ЛЕКАРСТВЕННЫХ РАСТЕНИЯХ С.В. Бельтюкова, Г.О. Бичкова. Сорбційн...»

«ISSN 2305-8420 Российский гуманитарный журнал. 2015. Том 4. №5 339 DOI: 10.15643/libartrus-2015.5.2 Статус и структура методологии науки © И. В. Назаров Уральский Государственный Лесотехнич...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ (МИИТ) Кафедра теоретической механики А.Н.Тедых, А.И. Бондаренко Кинематика плоских рычажных механизмов Рекомендовано редакционно-издательским советом университет...»

«УДК 159.9:316.35 СОЦИАЛЬНО-ПСИХОЛОГИЧЕСКИЕ ФАКТОРЫ ФОРМИРОВАНИЯ ЛИЧНОСТНЫХ АСПЕКТОВ УСПЕШНОСТИ УЧЕБЫ ИНОСТРАННЫХ СТУДЕНТОВ В РОССИЙСКИХ ВУЗАХ1 © 2015 А. С. Чернышев1, А. А. Форопонова2 зав. кафедрой психологии, докт психол наук, профессор, e-mail kursk-psychol@ya...»

«ЕТНОПОЛІТИКА УДК 323.15(477.75)+325.454(477.75) Ю.А. Билецкая, аспирант Севастопольский национальный технический университет ул. Университетская, 33, г. Севастополь, Украина, 99053 E-mai...»

«Р.Г. Мумладзе, А.А. Гайдаенко, О.В. Гайдаенко ОСНОВЫ ЛОГИСТИКИ В АПК Учебник Рекомендовано УМО вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, об...»

«А.В. Карпенко В НАТО тоже есть наши корабли В ноябре 2004 года состоялась передача ВМС Греции очередного десантного корабля на воздушной подушке проекта 12322 «Зубр». Это уже третий однотипный корабль построенный фирмой «Алмаз» для инозаказчик...»

«ГОУ ВПО «ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» УТВЕРЖДАЮ Ректор ДГТУ, академик, v j.'9 ^ 'Т.А. И смаилов ОС Н О В НАМ ОБ РАЮ В АТ ЕЛ Ь Н АЯ П РОI РА ММ А С п е ц и а л ь н о с т ь 030301 — Психология шифр и наименование специальности 11сихолог Квалификация Преподаватель психологии Ср...»

«УДК 621.372 СОВРЕМЕННЫЕ МОДИФИКАЦИИ И ОБОБЩЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Скобцов Ю.А. Донецкий национальный технический университет, ул.Артема 58, Донецк, Украина, 83000 e-mail: skobtsov@kita.dgtu.donetsk.ua Скобцов В.Ю....»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.