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

УДК 004.4416

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

Иванов Дмитрий Сергеевич

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 2 ЯНВ 2012 005008527

Москва - 2011

005008527

Работа выполнена на кафедре «Информатика и вычислительная техника» Московского физико-технического института (государственного университета)

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

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

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

доктор технических наук, Дроздов Александр Юльевич кандидат технических наук Остановим Александр Юрьевич

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

Институт системного программирования РАН

Защита состоится 2012 г. в час. (УО мин. на заседа-

нии диссертационного совета Д 409.009.01 при ОАО «Институт электронных управляющих машин им. И.С.Брука» , расположенном по адресу: 119334, г.Москва, ул.Вавилова д.24

С диссертацией можно ознакомиться в библиотеке ОАО «ИНЭУМ им. И.С.Брука» .

Автореферат разослан «2-?>» 201 ]_ г.

Ученый секретарь

диссертационного совета,

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

Красовский В.Е.

Общая характеристика работы

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

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

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

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

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

Особенностью данного исследования стало его проведение применительно к различным микропроцессорным архитектурам. С одной стороны, это архитектуры ШЭС-класса, представленные в данной работе БРАПС-совмсстимыми микропроцессорами «МЦСТ-Я» разработки ЗАО «МЦСТ» , на базе которых выпускаются и создаются вычислительные комплексы для широкого класса перебазируемых и встраиваемых систем. В этом варианте планирование инструкций в процессе компиляции (статическое планирование) применяется в силу относительной простоты аппаратуры, исключающей возможность динамического планирования. С другой стороны, это архитектуры класса УЫ\У, использующие концепцию широкого командного слова, согласно которой компилятор в фазе планирования инструкций осуществляет наполнение командного слова набором инструкций, допускающих их одновременное выполнение рядом исполнительных устройств процессора. Типовым представителем, использовавшимся при проведении данного исследования, является микропроцессорная архитектура «Эльбрус» , рассчи-таная па создание высокопроизводительных стационарных информационно-вычислительных комплексов стратегического применения.

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

Цель исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность результатов работы состоит в реализации методов, объектов и алгоритмов комплексной технологии распределения регистров и планирования инструкций в составе оптимизирующего компилятора с языков высокого уровня Си и Си++ для вычислительных комплексов на базе микропроцессоров с архитекурой «Эльбрус» и архитектурой SPARC. Их эффективность подтверждена при исполнении пакетов SPEC CPU2000 и SPEC CPU95.

Апробация

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

• на 49-й научной конференции МФТИ (2006 г.)

• на 50-й научной конференции МФТИ (2007 г.)

• на XXXVII Международной молодежной научной конференции "Гага-ринские чтения "(Москва, МАТИ, 2011 г.)

• на научно-технической конференции "Перспективные направления развития средств вычислительной техники "в ОАО "НИЦЭВТ"(2011 г.)

• па семинаре Института системного программирования РАН (2011 г.)

• на семинарах секции программного обеспечения ЗАО «МЦСТ» и ОАО «ИНЭУМ» (2006 - 2011 гг.)

Публикации

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

Структура и объем работы

Диссертация состоит из введения, трех глав и заключения. Список литературы составляет 41 наименование. Объем диссертации составляет 117 страниц текста. Диссертация содержит 15 рисунков.

Содержание работы

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

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

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

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

1. Распределение регистров на основе раскраски графа несовместимости. В основе метода лежат работы русского математика А.ГТ. Ершова по распределению памяти. Использовать раскраску графа несовместимости для распределения регистров предложил американский математик Г. Четин. Большое количество работ посвящено различным усовершенствованиям базового алгоритма раскраски графа, предложенного Четиным. В большинстве этих публикаций связь распределения регистров и планирования инструкций вообще не рассматривается, хотя некоторые авторы предлагают учитывать отдельные аспекты влияния этих фаз друг па друга.

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

иолняется только их назначение.

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

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

Перечисленные алгоритмы имеют ряд недостатков.

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

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

Алгоритмы, основанные на методах линейного программирования, мед-

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

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

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

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

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

Рис. 1. Этапы распределения регистров: сбор информации, глобальное распределение, выполняемое до планирования, откачка в память и локальное распределение при планировании.

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

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

Этап сбора информации о сетях

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

Этап глобального распределения регистров

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

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

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

Архитектурные регистры, в свою очередь, представляются как Аг-битовые векторы, где N - количество гиперблоков в процедуре. Таким образом, регистровое окно процедуры выглядит как битовая матрицу размером N х К, где Я - количество доступных для распределения архитектурных регистров. В дальнейшем она обозначается как «регистровая матрица» ЯМ. Условие В.М1 — 0 означает, что регистр г свободен для распределения в г-ом гиперблоке. Если ЯМ? = 1, то в гиперблоке г на регистр г уже распределена какая-то сеть. Соответственно, если конъюнкция вектора жизни сети и вектора регистра есть нулевой вектор, сеть может быть распределена на этот регистр. В противном случае необходим дополнительный анализ в гиперблоках, соответствующих ненулевым битам вектора, полученного в результате конъюнкции.

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

следующим образом:

cost = ^2(store_cost ■ def_count) + load_cost ■ use_count) (1)

def use

В дайной формуле store_cost и load__cost - стоимость выполнения одной инструкции записи в память и чтения из памяти. Аргументы def_count и use_count - это, соответственно, счетчики выполнения определений и использований сети. С разной степенью точности они могут быть получены с помощью динамической профильной информации, статического предсказателя переходов или на основе уровней вложенности циклов или ветвлений, в которых находятся данные использования и определения.

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

Этап откачки глобальных сетей в память

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

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

Этап планирования инструкций и локального распределения регистров

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

14

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

Время жизни локальной сети начинается при планировании первого определения ТРИ и заканчивается при планировании последнего использования ТШ сети. Необходимое количество регистров можно с большой точностью оценить как

^(ТЩ-ТЩ) ^

Н ' ^

где ТЬЩ соответствует среднему времени планирования последнего использования, Г^Д: - среднему времени планирования первого определения, а Н - времени планирования последней инструкции гиперблока (считаем, что время планирования первой инструкции всегда равно нулю). Среднее время планирования зависит от соотношения количества параллельных ветвей в графе зависимостей гиперблока к доступной параллельности архитектуры. Если количество параллельных ветвей в графе зависимости гиперблока ниже либо равно доступной параллельности архитектуры (количеству инструкций, которых можно одновременно запустить на исполнение), то среднее время планирования инструкций будет соответствовать раннему времени планирования. Если количество параллельных ветвей в графе зависимости превосходит доступную архитектурную параллельность, то по мере увеличения параллельности среднее время планирования будет увеличиваться и может значительно превосходить время позднего планирования. Среднее время планирования можно с большой точностью определить по формуле

Щ = + (3)

где Те - время раннего планирования инструкции, 7] - время позднего планирования инструкции, А % - соотношение количества параллельных вет-

вей графа зависимостей к доступной архитектурной параллельности. Среднее время планирования первого определения ТЕД определяется аналогично.

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

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

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

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

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

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

Дополнительные оптимизации, применяемые на разных этапах технологии

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

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

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

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

1. Пересылки регистра самого в себя

2. Инструкции, не имеющие потребителей и побочных эффектов

3. Инструкции, модифицирующие флаги процессора

4. Инструкции, подлежащие удалению в силу особенностей регистрового файла архитектуры

5. Инструкции, ставшие ненужными в результате пересчета значений (ре-материализации)

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

будет востребован на распределении регистров и планировании инструкций, так как в результате него могут появляться лишние инструкции типов 1, 3, 4 и 5. Поэтому оптимальным решением является выполнение удаления лишних инструкций указанных типов при распределении регистров и планировании инструкций.

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

Оценка алгоритмической сложности

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

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

Прямое внедрение представленной на Рис 1 поэтапной схемы в компилятор для архитектуры SPARC позволила увеличить производительность в среднем на 4% на задачах SPEC CINT95 и уменьшить суммарное время работы фаз на 40% по сравнению с алгоритмом раскраски графа несовместимости. Предложенные методы удаления лишних инструкций позволили удалить до 10% инструкций пересылок от общего числа инструкций пересылок па задачах пакета SPEC CINT95.

Применение разработанной технологии к архитектуре «Эльбрус» имеет следующие особенности. В целом, распределение регистров для архитектур класса УЫ\У выполняется так же, как и для простых ИБС-архитектур, однако, благодаря планированию кода по широким командам, преимущества предлагаемой технологии над другими методами становятся еще более заметными. Откачка сетей в память выполняется во время планирования кода, и инструкции откачки планируются на общих основаниях, что позволяет эффективно использовать ресурсы широкой команды и избежать разреза кода и вставки новых широких команд. Более того, при дефиците регистров выполняется задержка планирования некритичных инструкций и излишне параллельный код естественным образом становится последовательным. Широкая команда выдвигает и более жесткие требования к удалению инструкций. Во УЫ\¥-архитектурах набор инструкций широкой команды фиксируется в фазе планирования, поэтому лишние инструкции должны детектироваться и удаляться не позднее момента их планирования. Также, при этом должна обнуляться задержка инструкции, чтобы се преемники могли попасть в открытую широкую команду. Таким образом, распределение регистров при планировании инструкций позволяет эффективно использовать место в широкой команде, которое при распределении регистров после планирования инструкций было бы занято бесполезными инструкциями. В то же время, потребовались некоторые дополнения.

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

откачки предикатных сетей в память.

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

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

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

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

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

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

Реализация объединенной схемы планирования инструкций и распределения регистров в компиляторе для архитектуры «Эльбрус» позволила увеличить производительность в среднем на 10% па задачах SPEC CFP2000 с искусственным ограничением на количество регистров, а также уменьшить суммарное время работы фаз в 3 раза по сравнению с раскраской графа несовместимости после планирования инструкций.

Заключение

В диссертационной работе рассматривается проблема объединения двух фаз завершающего этапа компиляции - распределения регистров и планирования инструкций. Анализ описанных в литературе методов распределения регистров показал их недостаточное взаимодействие с планированием инструкций, приводящее к неэффективному использованию ресурсов аппаратуры. На основании теоретического и экспериментального исследования проблемы и методов се решения предложена оригинальная технология распределения регистров при планировании инструкций, эффективность которой подтверждена при внедрении в оптимизирующий компилятор вычислительных комплексов разработки ЗАО «МЦСТ» , построенных на базе мик-

ропроцессоров различной архитектуры.

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

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

2. Предложена комплексная технология распределения регистров и планирования инструкций, которая позволила повысить эффективность программ пакета SPEC CINT95 для архитектуры SPARC па 4% и программ пакета SPEC CFP2000 для архитектуры «Эльбрус» на 10%.

3. Разработан алгоритм распределения регистров с использованием битовых векторов, обладающий линейной алгоритмической сложностью. Его реализация в компиляторе позволила сократить суммарное время работы фаз планирования и распределения на 40% для архитектуры SPARC и в 3 раза для архитектуры «Эльбрус» .

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

5. Предложены методы учета влияния особенностей архитектур класса VLIW на распределение регистров при планировании инструкций.

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

вычислительных комплексах ВК «Эльбрус-ЗМ1» и ВК «Эльбрус-90микро» . Представленные в работе методы и алгоритмы могут быть адаптированы и использоваться для различных микропроцессорных архитектур.

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

1. Иванов Д. С. Распределение регистров и планирование инструкций в оптимизирующих компиляторах вычислительных средств ЗАО «МЦСТ» // Сборник тезисов докладов научно-технической конференции «Перспективные направления развития средств вычислительной техники» , Москва 2011, С.54-55

2. Иванов Д.С. Удаление лишних инструкций при планировании инструкций и распределении регистров // Научные труды XXXVII Международной молодежной научной конференции «Гагаринские чтения» , т.4.М.:МАТИ, 2011, С.66-67

3. Иванов Д.С. Распределение регистров при планировании инструкций для архитектуры «Эльбрус-ЭОмикро» // Вопросы радиоэлектроники, Серия Электронная Вычислительная техника, Выпуск 3, 2011, С.70-82

4. Иванов Д.С. Распределение регистров при планировании инструкций для УЫ\¥-архитектур /'/ Программирование, № 6, 2010,С.74-80

5. Иванов Д.С. Особенности распределения регистров при планировании команд для архитектур с широким командным словом // Труды 50-й научной конференции МФТИ, 2007,С.55-56

6. Иванов Д.С. Распределение регистров при планировании операций для архитектуры «Эльбрус-ЭОмикро» // Труды 49-й научной конференции МФТИ, 2006, С.46

Подписано в печать 26 ноября 2011 г. Объем 1,2 пл. Тираж 100 экз. Заказ № 587 Отпечатано в Центре оперативной полиграфии ООО «Ол Би Принт» Москва, Ленинский пр-т, д.37

Введение

Глава 1. Методы распределения регистров

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

1.2. Особенности организации регистровых файлов для ШБС-архитектур.

1.3. Существующие методы распределения регистров

1.4. Недостатки существующих методов распределения регистров

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

1.6. Выводы.

Глава 2. Технология распределения регистров при планировании инструкций.

2.1. Глобальное и локальное распределение регистров

2.2. Сбор информации о сетях

2.3. Глобальное распределение регистров перед планированием инструкций

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

2.5. Планирование инструкций и локальное распределение регистров

2.6. Откачка сетей в память.

2.7. Удаление лишних инструкций

2.8. Оценка сложности алгоритма

2.9. Результаты применения алгоритма

2.10. Выводы.

Глава 3. Особенности технологии для архитектур класса УЬПУ

3.1. Планирование инструкций с использованием широкого командного слова.

3.2. Распределение регистров

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

3.4. Взаимодействие с другими фазами компилятора

3.5. Архитектуры VLIW и ЕРЮ

3.6. Результаты применения алгоритма

3.7. Выводы.

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

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

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

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

Особенностью данного исследования стало его проведение применительно к различным микропроцессорным архитектурам. С одной стороны, это архитектуры RISC-класса, представленные в данной работе SPARC-совместимыми микропроцессорами «МЦСТ-R» разработки ЗАО «МЦСТ» , на базе которых выпускаются и создаются вычислительные комплексы для широкого класса перебазируемых и встраиваемых систем. В этом варианте планирование инструкций в процессе компиляции (статическое планирование) применяется в силу относительной простоты аппаратуры, исключающей возможность динамического планирования. С другой стороны, это архитектуры класса VLIW, использующие концепцию широкого командного слова, согласно которой компилятор в фазе планирования инструкций осуществляет наполнение командного слова набором инструкций, допускающих их одновременное выполнение рядом исполнительных устройств процессора. Типовым представителем, использовавшимся при проведении данного исследования, является микропроцессорная архитектура «Эльбрус» , рассчитаная на создание высокопроизводительных стационарных информационно-вычислительных комплексов стратегического применения.

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

Цель исследования. Основная цель исследования состояла в повышении производительности вычислительного комплекса при исполнении откомпилированной программы за счет объединения фаз распределения регистров и планирования инструкций при ее компиляции. Наряду с этим, ставилось требование увеличить скорость компиляции программ. Соответственно, решались следующие задачи:

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

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

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

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

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

Предмет исследования составляют:

• особенности организации регистровых файлов для RISC-архитектур вообще и для VLIW-архитектур [1] в частности

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

• конечная эффективность и производительность результирующего кода

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов и теории алгоритмов. Оценка эффективности представленных решений выполнялась путем замера времени исполнения программ на вычислительных комплексах с микропроцессорами «Эльбруо и МЦСТ-R. Замеры производились на пакетах задач SPEC CPU95 и SPEC CPU2000 [2]

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

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

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

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

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

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

Практическая ценность результатов работы состоит в реализации методов, объектов и алгоритмов комплексной технологии распределения регистров и планирования инструкций в составе оптимизирующего компилятора с языков высокого уровня Си и Си++ для вычислительных комплексов на базе микропроцессоров с архитекурой «Эльбрус» и архитектурой SPARC. Их эффективность подтверждена при исполнении пакетов SPEC CPU2000 и SPEC CPU95.

Апробация

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

• на 49-й научной конференции МФТИ (2006 г.)

• на 50-й научной конференции МФТИ (2007 г.)

• на XXXVII Международной молодежной научной конференции "Гагарин-ские чтения "(Москва, МАТИ, 2011 г.)

• на научно-технической конференции "Перспективные направления развития средств вычислительной техники"в ОАО "НИЦЭВТ"(2011 г.)

• на семинаре Института системного программирования РАН (2011 г.)

• на семинарах секции программного обеспечения ЗАО «МЦСТ» и ОАО «ИНЭУМ» (2006 - 2011 гг.)

Публикации

По теме диссертации опубликовано шесть печатных работ: в Иванов Д.С. Распределение регистров и планирование инструкций в оптимизирующих компиляторах вычислительных средств ЗАО "МЦСТ"// Сборник тезисов докладов научно-технической конференции "Перспективные направления развития средств вычислительной техники Москва 2011, С.54-55

• Иванов Д.С. Удаление лишних инструкций при планировании инструкций и распределении регистров // Научные труды XXXVII Международной молодежной научной конференции "Гагаринские чтения т.4.М.:МАТИ, 2011, С.66-67

• Иванов Д.С. Распределение регистров при планировании инструкций для архитектуры Эльбрус-ЭОмикро // Вопросы радиоэлектроники, Серия Электронная Вычислительная техника, Выпуск 3, 2011, С.70-82

• Иванов Д.С. Распределение регистров при планировании инструкций для УЫ\¥-архитектур // Программирование, № 6, 2010, С.74-80

• Иванов Д.С. Особенности распределения регистров при планировании команд для архитектур с широким командным словом //' Труды 50-й научной конференции МФТИ, 2007,С.55-56

• Иванов Д.С. Распределение регистров при планировании операций для архитектуры Эльбрус-ЭОмикро // Труды 49-й научной конференции МФТИ, 2006, С.46

Структура и объем работы

Диссертация состоит из введения, трех глав и заключения. Список литературы составляет 41 наименование. Объем диссертации составляет 117 страниц текста. Диссертация содержит 15 рисунков.

3.7. Выводы

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

2. Распределение регистров на спланированном коде и планирование кода

4>

В н

J3

2 О

Я > чЭ

U g В о О и СЙ 1 * ТЗ ей •с ад В г» оо г

ЧО

Benchmark

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

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

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

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

Заключение

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

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

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

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

2) Предложен метод объединения фаз планирования инструкций и распределения регистров на основе разделения задачи распределения регистров на две подзадачи: распределение регистров для глобальных сетей перед планированием и распределение регистров для локальных сетей при планировании инструкций

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

4) Предложена классификация групп лишних инструкций и рассмотрены методы их удаления при планировании инструкций и распределении регистров

5) Исследованы особенности реализации предложенных методов для различных архитектур и показана применимость предложенных методов для архитектур RISC и VLIW

6) Исследовано взаимодействие объединенной фазы планирования инструкций и распределения регистров с другими фазами компилятора и предложены варианты взаимного расположения этих фаз

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

1. Ахо, А., Лам, М., Сети, Р., Ульман, Д. Компиляторы. Принципы, технологии, инструментарий. Вильяме, Москва, 2011

2. Standard Performance Evaluation Corporation. The SPEC Benchmark Suites. CPU-intensive benchmark suite. Electronic resource]. — 1995-2000. http: / / www.spec.org/cpu

3. SPARC International, Inc., Englewood Cliffs, NJ, USA. SPARC architecture manual. Version 8. — 1992

4. ARM Limited. The ARM-THUMB Procedure Call Standard. 1998

5. Галазин, А. Методы оптимизации доступа к подсистеме памяти на этапе компиляции для микропроцессорных систем с архитектурой широкого командного слова, phdthesis, Москва. — 2008. Научный руководитель -Нейман-заде, М.И.

6. Hennessy, J.L., Patterson, D.A. Computer Organization and Design: the Hardware/Software interface. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2009

7. Ершов, А.П. Сведение задачи распределения памяти при составлении программ к задаче раскраски вершин графа, techreport, АН СССР. — 1961

8. Chaitin, G.J. Register allocation & spilling via graph coloring. SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction, pp 98-105. ACM, New York, NY, USA, 1982

9. Briggs, P., Cooper, K.D., Kennedy, K., Torczon, L. Coloring heuristics for register allocation. PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, pp 275-284. ACM, New York, NY, USA, 1989

10. Callahan, D., Koblenz, B. Register allocation via hierarchical graph coloring. SIGPLAN Not., volume 26, № 6:pp 192-203. 1991

11. Goodman, J.R., Hsu, W.C. Code scheduling and register allocation in large basic blocks. ICS '88: Proceedings of the 2nd international conference on Supercomputing, pp 442-452. ACM, New York, NY, USA, 1988

12. Pinter, S.S. Register allocation with instruction scheduling. PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, pp 248-257. ACM, New York, NY, USA, 1993

13. Berson, D.A., Gupta, R., Sofïa, M.L. Ursa: A unifed resource allocator for registers and functional units in vliw architectures, techreport, Pittsburgh, PA. 1992

14. Muchnick, S.S. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA, USA, 1997

15. Norris, C., Pollock, L.L. Register allocation over the program dependence graph. PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, pp 266-277. ACM, New York, NY, USA, 1994

16. Berson, D.A., Gupta, R., Soffa, M.L. Gurrr: a global unified resource requirements representation. IR '95: Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, pp 23-34. ACM, New York, NY, USA, 1995

17. Proebsting, T.A., Fischer, C.N. Demand-driven register allocation. ACM Trans. Program. Lang. Syst., volume 18, № 6:pp 683-710. 1996

18. Goodwin, D.W., Wilken, K.D. Optimal and near-optimal global register allocations using 0-1 integer programming. Softw. Pract. Exper., volume 26, № 8:pp 929-965. 1996

19. Lueh, G.Y., Gross, T. Call-cost directed register allocation. PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, pp 296-307. ACM, New York, NY, USA, 1997

20. Park, J., Moon, S.M. Optimistic register coalescing. PACT '98: Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p 196. IEEE Computer Society, Washington, DC, USA, 1998

21. Chen, G., Smith, M.D. Reorganizing global schedules for register allocation. ICS '99: Proceedings of the 13th international conference on Supercomputing, pp 408-416. ACM, New York, NY, USA, 1999

22. Pu, C., Wilken, K. A faster optimal register allocator. MICRO 35: Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, pp 245-256. IEEE Computer Society Press, Los Alamitos, CA, USA, 2002

23. Koes, D., Goldstein, S.C. A progressive register allocator for irregular architectures. CGO '05: Proceedings of the international symposium on Code generation and optimization, pp 269-280. IEEE Computer Society, Washington, DC, USA, 2005

24. Matz, M. Design and implementation of a graph coloring register allocator for gcc. techreport. — 2003

25. Smith, M.D., Ramsey, N., Holloway, G. A generalized algorithm for graph-coloring register allocation. PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pp 277-288. ACM, New York, NY, USA, 2004

26. Боханко, А. Распределение регистров методом раскраски графа несовместимости для современных вычислительных систем, phdthesis, Москва. — 2005. Научный руководитель Волконский, В.Ю.

27. Xu, W., Tessier, R. Tetris: a new register pressure control technique for vliw processors. LCTES '07: Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pp 113122. ACM, New York, NY, USA, 2007

28. Quintao Pereira, F.M., Palsberg, J. Register allocation by puzzle solving. PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pp 216-226. ACM, New York, NY, USA, 2008

29. Baev, I.D. Techniques for region-based register allocation. CGO '09: Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization, pp 147-156. IEEE Computer Society, Washington, DC, USA, 2009

30. Touati, S.A.A., Barthou, D. On the decidability of phase ordering problem in optimizing compilation. Proceedings of the 3rd conference on Computing frontiers, CF '06, pp 147-156. ACM, New York, NY, USA, 2006

31. Morgan, R. Building an optimizing compiler. Digital Press, Newton, MA, USA, 1998

32. Allen, R., Kennedy, K. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann, San Francisco, CA, USA, 2001

33. Останевич, А. Планирование операций при генерации кода для архитектур с явно выраженным паралелизмом. phdthesis, Москва. — 1999. Научный руководитель Волконский, В.Ю.

34. Briggs, P., Cooper, K.D., Torczon, L. Rematerialization. PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, pp 311-321. ACM, New York, NY, USA, 1992

35. Triebel, W. Itanium Architecture for Software Developers. Intel Press, USA, 2000

36. SPARC International, Inc., Englewood Cliffs, NJ, USA. SPARC architecture manual. Version 9. — 1994

37. P754, I.T. ANSI IEEE 754-1985, Standard for Binary Floating-Point Arithmetic. IEEE, New York. 1985

38. Распределение регистров путем раскраски графа методом Четина 18

39. Квадратный граф, раскрашиваемый двумя цветами. 19

40. Оптимистическая раскраска графа методом Бриггса. 19

41. Четыре этапа технологии распределения регистров при планировании инструкций: сбор информации о сетях, глобальное распределение регистров, откачка глобальных сетей и в память и локальное распределение регистров при планировании инструкций. 37

42. Планирование по приоритетам с разметкой графа зависимостей . 67

43. Изменение производительности компилируемых программ в результате изменения схемы распределения регистров с раскраски графа несовместимости на распределение регистров при планировании инструкций в компиляторе для архитектуры SPARC. . . 81

44. Чтения значения сети в случае нескольких условных использований 95

45. Относительная производительность комбинированной схемы и схемы с раздельными планированием инструкций и распределением регистров.106

46. Отношение суммарного времени работы фаз планирования и распределения регистров для комбинированной и раздельно схем . . 107