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

• Рыбаков, Алексей Анатольевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Рыбаков, Алексей Анатольевич

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

135

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

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

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

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы оптимизации переходов в компиляторе базового уровня системы двоичной трансляции для архитектуры "Эльбрус"»

Введение

Актуальность темы. Динамическая компиляция [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.

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

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

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

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

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

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

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

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

Определение 1.1. Компилятор (или транслятор) - это программа, которая переводит другую программу или ее часть, написанную на одном языке - исходном, в эквивалентную программу на другом языке - целевом [27].

В классическом понимании компилятора в роли исходного языка выступает какой-либо язык программирования [28], а в роли целевого языка - двоичный код, который может быть выполнен на машине [29]. В этом случае будем говорить о языковом компиляторе. Если компилятор в качестве исходного языка принимает некоторый двоичный код, то будем называть его двоичный компилятор.

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

Зачастую компиляторы для своей работы используют одно или несколько различных промежуточных представлений [27, 29, 16]. Промежуточное представление является внутренним описанием программы, предназначен-

ным для нужд компилятора.

Компиляторы, выполняющие преобразования промежуточного представления с целью получить более качественный целевой результирующий код, называются оптимизирующими компиляторами [27, 16, 30]. Как правило, основным критерием качества кода является скорость его выполнения, однако, могут учитываться и другие факторы, такие как размер результирующего кода или эффективность использования ресурсов.

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

Определение 1.2. Базовым блоком, (или линейным участком) будем называть последовательность инструкций с одним входом и одним выходом.

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

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

Базовые блоки бывают трех видов:

1. Базовый блок, не содержащий команд перехода (рис. 1.1, а). После ис-

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

2. Базовый блок, заканчивающийся командой безусловного перехода (рис. 1.1,6). После исполнения всех команд данного базового блока безусловный переход также выполняется, и управление передается на адрес назначения перехода.

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

BRANCH-

BRANCH [с]--;

а)

б)

в)

Рис. 1.1. Виды базовых блоков

Определение 1.3. Квазилинейным участком будем называть последовательность инструкций с одним входом.

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

Определение 1.4. Провал - передача управления, осуществляемая не вследствие выполнения команды перехода.

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

Определение 1.5. Суперблок - последовательность базовых блоков, подчиняющаяся двум требованиям [32]:

1. Из любого базового блока последовательности управление передается по провалу на следующий базовый блок этой последовательности.

2. Ни из какого базового блока последовательности управление не передается с помощью перехода на другой базовой блок этой последовательности.

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

а) б)

Рис. 1.2. Примеры суперблока и региона

Определение 1.6. Регион - это произвольный набор линейных или квазилинейных участков, связанных меоюду собой передачей управления (то есть переходами и провалами).

Заметим, что регион может иметь как несколько входов, так и несколько выходов (рис. 1.2, б), а также может содержать циклы.

Теперь можно дать определение графу потока управления.

Определение 1.7. Граф потока управления (управляющий граф, control flow graph, CFG) региона - ориентированный псевдограф, узлами которого являются линейные или квазилинейные участки региона, а с помощью ребер указана передача управления между ними (как с помощью команд перехода, так и по провалу).

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

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

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

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

Основной причиной высокой производительности архитектуры «Эльбрус» является параллелизм исполнения кода на уровне отдельных команд. Это обусловлено тем, что «Эльбрус» является VLIW-архитектурой (very long instruction word) [33, 34, 17], или архитектурой с широким командным словом, что позволяет кодировать в одной VLIW-комапде несколько отдельных

операций и выполнять их параллельно. Время выполнения каждой отдельной операции детерминировано, а также известны все задеро/ски, которые должны быть выдержаны между операциями. Используя эту информацию на этапе компиляции, можно эффективно планировать широкие команды, максимально используя вычислительные ресурсы процессора [35].

В микропроцессоре «Эльбрус» максимальная длина одной широкой команды составляет 64 байта, что позволяет включить в нее несколько операций [23, 36]. В микропроцессоре «Эльбрус» присутствует 6 арифметико-логических устройств (arithmetic logic unit, ALU), четыре из которых могут использоваться для вычислений с плавающей арифметикой. Кроме того, некоторые арифметические операции могут объединяться в так называемые комбинированные („двухэтажные") операции, что позволяет загружать вычислительные ресурсы микропроцессора более эффективно. Наибольшую эффективность микропроцессоры архитектуры «Эльбрус» демонстрируют при запуске задач, использующих параллельные алгоритмы обработки данных (например такие, как описанные в [37, 38]), так как на подобных задачах ALU могут использоваться максимально плотно.

Другой особенностью является большой размер регистрового файла [39], организованного в виде процедурных окон. Размер регистрового файла составляет 256 регистров, 32 из которых предназначены для глобальных данных. При переполнении регистрового файла автоматически выполняется его откачка, при исчерпании - подкачка.

Наличие предикатного (условного) режима исполнения операций позволяет в некоторых случаях избежать создания ненужных операций передачи управления путем планирования в одном линейном участке команд под разными предикатами [40, 41].

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

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

Предикатный файл состоит из 32 двухразрядных регистров. Любая процедура может использовать все 32 предиката. Аналогично регистровому файлу, при переполнении предикатного файла выполняется его автоматическая откачка, при исчерпании - подкачка [19].

Список литературы диссертационного исследования кандидат наук Рыбаков, Алексей Анатольевич, 2013 год

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

[1] Kulkarni P., Arnold M., Hind M. Dynamic compilation: the benefits of early investing. // VEE'07 Proceedings of the 3rd international conference on Virtual execution environments, 2007, P. 94-104.

[2] Wakeling D. The dynamic compilation of lazy functional programs. // Journal of Functional Programming, Volume 8 Issue 1, January 1998, P. 61-81.

[3] Whaley J. Partial method compilation using dynamic profile information. // OOPSLA'Ol Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2001, P. 166-179.

[4] Aycock J. A brief history of just-in-time. // ACM Computing Surveys (CSUR), Volume 35 Issue 2, June 2003, P. 97-113.

[5] Chambers C. Staged compilation. // PEPM'02 Preceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, P. 1-8.

[6] Debbabi M., Gherbi A., Ketari L., Talhi C., Yahyaoui H., Zhioua

S. A synergy between efficient interpretation and fast selective dynamic compilation for the acceleration of embedded Java virtual machines. // PPPJ'04 Proceedings of the 3rd international symposium on Principles and practice of programming in Java, P. 107-113.

[7] Schilling T. Challenges for a trace-based just-in-time compiler hor haskell. // IFL'll Proceedings of the 23rd international conference on Implementation and Application of Functional Languages, P. 51-68.

[8] Johansson E., Pettersson M., Sagonas K. A high performance Erlang

system. // PPDP'OO Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, P. 32-43.

[9] Mascarenhas F., Ierusalimschy R. Efficient compilation of Lua for the CLR. // SAC'08 Proceedings of the 2008 ACM symposium on Applied computing, P. 217-221.

[10] Rigo A., Pedroni S. PyPy's approach to virtual machine construction. // OOPSLA'06 Companion to the 21st ACM SIGPLAN symposium on Object-oriented programming systems, languages, and applications, P. 944-953.

[11] Altman E., Kaeli D., Sheffer Y. Welcome to the Opportunities of Binary Translation. // Computer, Vol. 33, No. 3, March 2000, P. 40-45.

[12] Baraz L., Devor Т., Etzion O., Goldenberg S., Skaletsky A., Wang Y. and Zemach Y. IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium-based systems. // Microarchitecture, MICRO-36, Proceedings, 36th Annual IEEE/ACM International Symposium, 2003, P. 191-201.

[13] Dehnert J., Grant В., Banning J., Johnson R., Kistler Т., Klaiber A., Mattson J. The transmeta code morphing software: using speculation, recovery, and adaptive retranslation to address real-life challenges, //in the Proceedings of the International Symposium on Code Generation and Optimization, 2003.

[14] Nethercote N., Seward J. Valgrind: a framework for heavyweight dynamic binary instrumentation. // Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, P. 89-100.

[15] Воронов H. В., Гимпельсон В. Д., Маслов М. В., Рыбаков А. А., Сюсюкалов Н. С. Система динамической двоичной трансляции

х86 «Эльбрус». // Вопросы радиоэлектроники. Сер. ЭВТ., 2012, Вып. 3, С. 89-108.

[16] Muchnick S. Advanced Compiler Design and Implementation. // Morgan Kaufmann Publishers, 1997.

[17] Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. // БХВ-Петербург, 2002.

[18] Орлов С. А., Цилькер Б. Я. Организация ЭВМ и систем. Фундаментальный курс по архитектуре и структуре современных комптютерных средств. // Издательство «Питер», 2011.

[19] Ким А. К., Перекатов В. И., Ермаков С. Г. Микропроцессоры и вычислительные комплексы семейства «Эльбрус». // Питер, 2013.

[20] Babayan В. Main principles of Е2К architecture. // Free Software Magazine, Vol. 1, No. 2, Feb. 2002.

[21] Babayan В. E2K Technology and Implementation. // Parallel Processing: 6th International, Vol. 1900/2000, Jan. 2000, P. 18-21.

[22] Волконский В., Ким А., Назаров JI., Перекатов В., Фельдман

В. Микропроцессоры и вычислительные комплексы российской компании МЦСТ. // Электроника, 8/2008, С. 62-69.

[23] Волконский В. Оптимизирующие компиляторы для архитектуры с явным параллелизмом команд и аппаратной поддержкой двоичной совместимости. // Информационные технологии и вычислительные системы, 3/2004.

[24] Diefendorf К. The Russians Are Coming: Supercomputer Maker Elbrus Seeks to Join x86/IA-64 Melee. // Microprocessor report, vol. 11, num. 2, Feb. 15, 1999.

[25] Intel Corporation. Intel IA-32 Architecture Software Developer's Manual. // Vol. 1-3, 2003.

[26] Волконский В. Ю., Гимпельсон В. Д. Методы определения порогов активизации динамического оптимизирующего транслятора. // Информационные технологии, номер 4, 2007.

[27] Aho A., Lam М., Sethi R., Ulman J. Compilers: Principles, Techniques, and Tools. // Prentice Hall, 2nd edition, Sep. 2006.

[28] Sebesta R. Concepts of Programming Languages. // Addison Wesley, 9th edition, Apr. 2009.

[29] Bauer F., DeRemer F., Ershov A., Gries D. Compiler Construction: An Advanced Course. // Springer, 2nd edition, Dec. 1984.

[30] Allen R., Kennedy K. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. // Morgan Kaufmann, Oct. 2001.

[31] Евстигнеев В. А. Применение теории графов в программировании. // Москва, «Наука», 1985.

[32] Hwu W. The superblock: an effective technique for VLIW and superscalar compilation. // The Journal of Supercomputing 7, 1/2 (1993), P. 229-248.

[33] Oklobdzija V. The computer engeneering handbook. // CRC Press LLC, 2002, section II, chapter 5.2.

[34] Joseph A. Fisher. Very Long Instruction Word Architectures and the ELI-512. //in Proceedings of 10th International Symposium on Computer Architectures, IEEE. Jun. 1983, P. 140-150.

[35] Ellis J. Bulldog: A Compiler for VLIW Architectures. Doctor Dissertation. // MIT, Press Cambridge, MA, 1985.

[36] Волконский В. Ю., Брегер А. В., Грабежной А. В., Ермолиц-кий А. В., Муханов JL Е., Нейман-заде М. Н. Методы распараллеливания программ в оптимизирующем компиляторе для ВК семейства «Эльбрус». //VI Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», сборник избранных трудов, 2011, С. 46 - 59.

[37] Амербаев В. М., Пак И. Т. Параллельные вычисления в комплексной плоскости. // Алма-Ата, «Наука», 1970.

[38] Голуб Дж., Ван Лоун Ч. Матричные вычисления. // Москва, «Мир», 1999.

[39] Farkas К., Jouppi N., Chow P. Register File Design Considerations in Dynamically Scheduled Processors. // WRL Research Report 95/10, Nov. 1995.

[40] Волконский В. Ю., Окунев С. К. Предикатное представление как основа оптимизации программы для архитектур с явно выраженной параллельностью. // Информационные технологии, е4, апрель 2003, С. 36 -45.

[41] Волконский В. Ю., Окунев С. К. Оптимизация критического пути на предикатном представлении программы. // Информационные технологии, е9, сентябрь 2003.

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

[43] Дроздов А. Ю., Степаненков А. М. Технология оптимизации цикловых участков процедур в компиляторах для архитектур с аппаратной

поддержкой конвейеризации циклов. // Информационные технологии и вычислительные системы, 3/2004.

[44] Гимпельсон В. Д. Конвейеризация циклов в двоичном динамическом трансляторе. // Вопросы радиоэлектроники, выпуск 3, 2009.

[45] Галазин А. Б., Грабежной А. В. Эффективное взаимодействие микропроцессора и подсистемы памяти с использованием асинхронной предварительной подкачки данных. // Информационные технологии, номер 5, 2007.

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

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

[48] Mahlke S., Lin D., Chen W., Hank R., Bringmann R. Effective Compiler Support for Predicated Execution Using the Hyperblock. //in Proceedings of the 25th International Symposium on Microarchitecture, Dec. 1992, P. 45-54.

[49] Zhou H., Jennings M., Conte T. Tree Traversal Scheduling: A Global Scheduling Technique for VLIW/EPIC Processors. // The 14th Annual Workshop on Languages and Compilers for Parallel Computing (LCP'01), LNCS 2624, Springer Verlag, Aug. 2001, P. 223-238.

[50] Intel Corporation. Intel Itanium 2 Processor. Hardware Developer's Manual. // Jul. 2002.

[51] Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual. // Vol. 1-3, Dec. 2011.

[52] Chernoff A., Herdeg M., Hookway R., Reeve C., Rubin N., Tye T., Yadavall B. and Yates J. FX!32: A Profile-Directed Binary Translator. // IEEE Micro(18), Marh/April 1998.

[53] Drongowski P., Hunter D., Fayyazi M., Kaeli D. Studying the Perfomance of the FX!32 Binary Translation System, //in the Proceedings of the 1st Workshop on Binary Translation, Newport Beach, CA, Oct. 1999.

[54] Richter J. Advanced Windows NT. // Redmond, Wash., Microsoft Press, 1994.

[55] Kessler R. The Alpha 21264 Microprocessor. // IEEE Micro, March/April 1999, P. 24-36.

[56] Transmeta Corporation. Crusoe Processor. Model TM5800. // 2001.

[57] Transmeta Corporation. Introducing the Transmeta Efficeon TM8000 Microprocessor Family. // Oct. 2003.

[58] Hewlett-Packard Development Company. HP Aries. Technical overview, references and success stories. // Version 2.4, April 2008.

[59] Zheng C., Thompson C. PA-RISC to IA-64: Transparent Execution, No Recompilation. // IEEE Computer 33(3), 2000, P. 47-52.

[60] Hewlett-Packard Development Company. PA-RISC 1.1 Architecture amd Instruction Set Reference Manual. // Feb. 1994.

[61] Cooper C., Moore C. HP-UX Hi Internals. // Prentice Hall, Feb. 2004.

[62] Bellard F. QEMU, a Fast and Portable Dynamic Translator. // USENIX 2005 Annual Technical Conference, FREENIX Track, P. 41-46.

[63] Motorola Inc. PowerPC Microprocessors Family: The Programmer's Reference Guide. // 1995.

[64] Sloss A., Symes D., Wright C. ARM System Developer's Guide. Designing and Optimizing System Software. // Morgan Kaufmann, 2004.

[65] SPARC International Inc. The SPARC Architecture Manual. //Version 8, 1994.

[66] Kane G., Heinrich J. MIPS RISC Architecture. // Prentice Hall, 2 edition, Sep. 1991.

[67] Singh A. Mac OS X Internals: A System Approach. // Addison-Wesley Professional, Jun. 2006.

[68] Golumbic M., Rainish V. Instruction Scheduling Beyond Basic Blocks. // IBM Journal of Research and Development, Vol. 34, No. 1, Jan. 1990, P. 93-97.

[69] Ball Т., Larus J. Branch Prediction for Free, //in Proceedings of the Conference on Programming Language Design and Implementation, ACM SIGPLAN Notices, Vol. 28, 1993, P. 300-313.

[70] Yeh T.-Y., Patt Y. Two-level Adaptive Training Branch Prediction. // Proc. 24th Annual International Symposium on Microarchitecture, Nov. 1991, P. 51-61.

[71] Касьянов В. H., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. // «БХВ-Петербург», Санкт-Петербург, 2003.

[72] Armstrong J. Programming Erlang. Software for a Concurrent World. // Pragmatic Bookshelf. 2007.

[73] Armstrong J., Virding R., Wilkstrom C. Concurrent Programming in Erlang. // Prentice Hall. 1996.

[74] Cesarini F., Thompson S.. Erlang Programming. // O'REILLY, June 2009.

[75] Venkatachalam S., Sairam N., Srinivasan B. Code Optimization Using Graph Mining. // Research Journal of Applied Sciences, Engineering and Technology, Vol. 4, Issue 19, 2012.

[76] Harju T. Lecture Notes on Graph Theory. // Department of Mathematics University of Turku, 1994-2011, http://users.utu.fi/harju/graphtheory/graphtheory.pdf, дата обращения 01.10.2013.

[77] Харари Ф. Теория графов. // Книжный дом «ЛИБРОКОМ», Москва, 2009.

[78] Оре О. Теория графов. // Книжный дом «ЛИБРОКОМ», Москва, 2008.

[79] Вентцель Е. С. Исследование операций. // Советское радио, Москва, 1972.

[80] Chinneck J. Practical Optimization: A Gentle Introduction. / / Carleton University, Systems and Computer Engineering, http://www.sce.carleton.ca/faculty/chinneck/po.html, дата обращения 01.10.2013.

[81] Волков И. К., Загоруйко Е. А. Исследование операций. // Издательство МГТУ имени Н. Э. Баумана, Москва, 2000.

[82] Ашманов С. А. Линейное программирование. // «Наука», Москва, 1981.

[83] Taha Н. Operations Research: An Introduction. // Prentice Hall, 2006.

[84] Maros I. Computational Techniques of the Simplex Method (International Series in Operations Research and Management Science). // Springer, Dec. 2002.

[85] Горелик В. А., Ушаков И. А. Исследование операций. // Москва, «Машиностроение», 1986.

[86] Gomory R. Outline of an algorithm for integer solutions to linear programs. // Bulletin of the American Mathematical Society, Vol. 64, 1958, P. 275-278.

[87] Klee V., Minty G. How Good is the Simplex Algorithm? // In O.Shisha, editor, Inequalities, III, Academic Press, New York, 1972, P. 159-175.

[88] Greenberg H. Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. // University of Colorado at Denver, http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf, дата обращения 01.10.2013.

[89] Бондаренко А. В., Гудков А. С. О среднем числе разных комбинаций с учетом частоты подмножеств. // Электронный журнал „Исследовано в России", 213, 2006, С. 2023-2030, http://zhurnal.ape.relarn.ru/articles/2006/213.pdf, дата обращения 01.10.2013.

[90] Standard Performance Evaluation Corporation, www.spec.org

[91] Huang J., Leng T. Generalized Loop-Unrolling: a Method for Program Speed-Up. // Department of Computer Science, the University of Houston, 1997.