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

УДК 004.4'416

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

Боханко Андрей Сергеевич

РАСПРЕДЕЛЕНИЕ РЕГИСТРОВ МЕТОДОМ РАСКРАСКИ ГРАФА НЕСОВМЕСТИМОСТИ ДЛЯ СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

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

Автореферат

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

Москва - 2005

Работа выполнена в Институте микропроцессорных вычислительных систем РАН и ЗАО "МЦСТ"

Научный руководитель кандидат технических наук, старший

научный сотрудник Волконский В. Ю.

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

доктор физико-математических наук, профессор Серебряков В. А.

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

кандидат технических наук Добров А.

Д.

Институт точной механики и вычислительной техники им. С. А. Лебедева

Защита состоится «-£» декабря 2005 г. в ч. ¿С мин. на заседании диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 117218, ГСП-7, Москва, Нахимовский проспект, д. 36, корп. 1.

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

Автореферат разослан « 2.»НоэерЯ 2005 г.

Ученый секретарь диссертационного совета д.ф.-м.н., профессор ///л.

Михайлюк М.В.

2202. ш

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

Актуальность работы

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

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

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

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

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

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

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

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

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

У-

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

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

Цель диссертационной работы

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

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

Для достижения поставленной цели в работе выполняются следующие этапы:

• Исследование влияния аппаратных механизмов вычислительных систем и других компонент оптимизирующего компилятора на задачу распределения регистров;

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

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

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

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

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

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

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

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

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

Научная новизна

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

• Исследование влияния новых аппаратных механизмов (широкого командного слова, предикатное™, отдельных регистровых файлов для данных разных типов) на распределение регистров

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

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

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

• Разработанный алгоритм анализа предикатных определений переменных с точки зрения прекращения времени жизни этих переменных

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

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

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

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

1.) Все разработанные алгоритмы были реализованы в составе распределителя регистров оптимизирующего компилятора с языков высокого уровня С, С++ и Фортран-77, позволяющего получить высокоэффективный оптимизированный код для микропроцессора с архитектурой Эльбрус-ЗМ.

2.) Оптимизирующий компилятор как конечный продукт вошел в состав программного комплекса вычислительной системы Эльбрус-ЗМ.

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

Апробация

Результаты работы докладывались на международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, в 2004 и 2005 гг.; тезисы докладов опубликованы) и международной конференции "Региональная информатика 2004" (С-Петербург, 2004 г.; тезисы докладов опубликованы); кроме того, были сделаны доклады и проведено обсуждение на семинарах и научно-технических совещаниях ЗАО "МЦСТ" и Института микропроцессорных вычислительных систем РАН.

Публикации

По теме диссертации опубликовано шесть печатных работ.

б

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

Диссертация состоит из введения, трех глав и заключения. Диссертация содержит 101 страницу, 19 рисунков, 1 таблицу. Список литературы насчитывает 56 наименований.

Краткое содержание работы

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

В первом разделе проводится анализ развития архитектурных механизмов, с особенным вниманием к различным способам организации параллельных вычислений. Рассмотрены возможности крупнозернистого и мелкозернистого параллелизма, и важность роли компилятора в поддержке распараллеливания. Подробно, насколько позволяют рамки раздела, проанализированы архитектуры с широким командным словом, как исторические (ELI, Cydra-5, PlayDoh), так и современные (Intel Itanium, Эльбрус-ЗМ). Проведен обзор и прослежены истоки оптимизирующей компиляции.

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

Аналитические структуры данных можно условно разделить два типа: структуры анализа потока управления и структуры анализа потока данных. Из описанных структур данных к первому типу относятся управляющий граф, дерево доминаторов / постдоминаторов и дерево циклов. Ко второму типу относятся форма со статически единственным присваиванием (SSA-форма) и граф потока данных.

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

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

На Рисунке 1 приведен пример перевода программы в SSA-форму (слева исходная программа, справа - программа, представленная в SSA-форме).

if (...) { fool = А;

} else {

foo2 = В;

}

foo3 = ((»(fool, foo2); bar = foo3;

Рис. 1. Пример перевода программы в SSA-форму

Один из самых простых и удобных способов представления информации, собранной анализом потока данных - граф потока данных. Граф такого рода связывает дугами все операции, работающие с определенным объектом. В силу причин технического характера часто граф потока данных разделяют на два графа — Data-Flow Graph (сокращенно DFG) и Def-Use Graph (сокращенно DUG). DFG строится только внутри линейных участков; DUG строится на всю процедуру и является дополнением DFG.

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

if (...) { foo = А;

} else {

foo = В;

}

bar = foo;

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

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

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

Одним из важнейших механизмов обеспечения параллелизма на уровне отдельных инструкций является широкое командное слово. Различают У1Л\¥-архитектуры, в которых ширина слова фиксирована, и ЕР1С-архитектуры, позволяющие кодировать широкое слово произвольного размера (хотя, разумеется, не гарантируется, что все инструкции, входящие в это слово, будут исполнены параллельно и за один такт).

Широкое командное слово позволяет одновременно выполнять несколько операций; разумеется, выполняемые операции должны использовать разные ресурсы. Таким образом, нагрузка на регистры возрастает. Этот факт является одной из причин того, что для VI архитектур характерен большой размер регистрового файла. Например, архитектура Е2К позволяет одновременно использовать до 192 регистров общего назначения и 32 предикатных регистра, каждый из которых может использоваться как в прямом, так и в инвертированном виде; в Капшт'е доступно 96 целочисленных, 64 плавающих и 64 предикатных регистра.

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

предложены необходимые модификации, причем как для УЬШ-, так и для ЕР1С-архитектур. Эти модификации не изменяют алгоритмическую сложность алгоритмов пропагации.

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

Были проведены исследования того, какой порядок работы планировщика и распределителя регистров наиболее эффективен. Для замеров использовался общепринятый в индустрии и исследовательском сообществе пакет тестов 8РЕС2000, в котором собраны наиболее типичные пользовательские программы. В него включены как целочисленные, так и вещественные задачи. Результаты замеров, представленные в разделе 2.1.2 диссертационной работы, позволили сделать вывод о предпочтительности предварительного запуска планирования и распределения регистров на уже спланированном коде.

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

регистров. Если операция стоит под некоторым предикатным регистром рп, то она будет выполнена только в том случае, если значением этого регистра рп является "истина" (TRUE). Разумеется, в ходе работы программы значение предикатного регистра может меняться динамически.

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

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

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

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

и

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

Алгоритмическая сложность предложенного алгоритма равняется .

о (o*n + dn*de), где о - число операндов процедуры, п - число узлов в графе несовместимости (то есть суммарное число всех физических регистров и сетей), dn - число узлов, a de - число дуг в Def-Use графе. В диссертационной работе доказана корректность и алгоритмическая сложность предложенного алгоритма.

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

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

Дня определения безсвязности предлагается использовать Граф разделения предикатов (Predicate Partition Graph). В основе PPG лежит понятие домена (domain) предиката. В домен предиката р входят '

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

последойательности. Разделение (partition) предиката - это разбитие домена на несколько непересекающихся подмножеств, объединение которых образует полный домен. Используя введенные понятия, можно дать следующее определение: графом разделения предикатов называется ориентированный граф G=(V, Е), каждый узел которого представляет предикат, а дуга (р, q) обозначает существования разделения р, такого, что р является подмножеством q.

Бессвязность с помощью PPG можно определить следующим образом: два домена независимы, если от них достижим общий предшественник по разньм дугам одного и того же разбиения домена. Например, на рисунке 2 предикаты pi и р5 независимы; про предикаты рЗ и р2 этого сказать нельзя.

Умея вычислять бессвязность предикатов, можно дать следующее определение "ложной несовместимости" между сетями: если между сетями wl и w2 есть дуга е в графе несовместимости, и при этом все операции -определения wl являются бессвязными (disjoint) со всеми операциями -определениями w2, значит дуга е является "ложной", и ее можно удалить.

Ро

d

Pi

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

На основе этого определения в разделе 2.2.2.2 был предложен алгоритм удаления всех "ложных несовместимостей".

Алгоритмическая сложность предложенного алгоритма удаления "ложных несовместимостей" равна 0(г*г), где г - число операндов -результатов процедуры. При этом подразумевается, что ответ о свзяности / бессвязности двух операций выполняется за константное время. Как правило, это так, потому что граф разделения предикатов обычно хранится в виде таблицы; индекс к соответствующей строке таблицы хранится в каждой операции.

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

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

• 96 целочисленных 64-х битных регистра

• 32 глобальных целочисленных 64-х битных регистра

• 64 вещественных 80-ти битных регистра

• 64 предикатных однобитных регистра

• 4 регистра перехода

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

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

Факт наличия регистров разных типов и форматов сгавит еще два вопроса: порядок распределения регистров и точное отслеживание форматов.

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

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

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

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

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

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

Например, оптимизация Глобальное распространение копий (Global Copy Propagation, GCP), может увеличить время жизни переменных от небольшого участка программы, состоящего из нескольких операций, до всей процедуры. Еще один пример классической оптимизации,

увеличивающей время жизни - Вынос инвариантов из тела цикла (loop invariant removal).

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

Оценка положительного эффекта для каждой оптимизации уникальна. Приводится алгоритмы такой оценки для двух упомянутых оптимизаций в разделе 3.1.

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

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

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

Далее, в разделе 3.2, рассматривается вопрос взаимодействия общецелевого и циклового распределителей регистров.

Во многих современных микропроцессорах (таких, например, как Intel Itanium и Эльбрус-ЗМ) огромное значение имеет поддержка циклов с наложением итераций. В циклах с наложением итераций (носящих также название конвейеризованных циклов) несколько итераций MOiyT выполняться одновременно, чем достигается значительное ускорение работы циклов. При этом важную роль играет поддержка в аппаратуре вращающихся регистров - регистров, номера которых в разные моменты времени могут указывать на разные фактические регистры, так что, например, RR0 может указывать в один момент времени на R0, а после выполнения операции, сдвигающей базу вращающихся регистров на одно деление, уже на R1. Использование вращающихся регистров позволяет передавать значения, выработанные операциями, через итерации цикла без использования операций пересылки (MOV). При этом также не создаются антизависимости, которые были бы неизбежны в случае использования явных пересылок.

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

В некоторых архитектурах, например в архитектуре Itanium, пространства вращающихся и общецелевых регистров пересекаются; в других, таких как Эльбрус-ЗМ, эти пространства разделены, однако ничто не мешает использовать вращающиеся регистры вне циклов с совмещением итераций, для распределения на них обычных виртуальных регистров. Таким образом, ресурсы, используемые двумя упомянутыми распределителями регистров, пересекаются. Необходимо некоторое взаимодействие, призванное обеспечить корректное разделение ресурсов.

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

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

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

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

В разделе 3.3 предложен новый подход к организации набора таких параметров. Кроме того, перечислены свойства, позволяющие эффективным образом настраивать распределитель регистров на широкий класс современных вычислительных систем. По сравнению с уже известными подходами, предложенный метод отличается полнотой и универсальностью - с его помощью успешно удалось портировагь распределитель регистров на такие разные архитектуры, как Эльбрус-ЗМ, Itanium и SPARC V8. Стоит отметить, что три эти архитектуры достаточно разнятся по своим характеристикам: первая является VLIW-архитектурой, вторая - EPIC архитектурой, а третья вообще не поддерживает

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

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

Выводы по результатам диссертации

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

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

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

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

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

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

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

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

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

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

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

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

1. Дроздов А. Ю., Корнсв Р. М., Боханко А. С. Индексный анализ зависимостей по данным // Информационные технологии и вычислительные системы, № 3,2004. С. 27-37.

2. Боханко А. С., Дроздов А. Ю., Корнев Р. М. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8,2004. С. 57-68.

3. Дроздов А. Ю., Боханко А. С. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании // Информационные технологии, № 12,2004. С. 32-37.

4. Боханко А. С., Новиков С. В., Шлыков С. Л. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе, № 8,2005. С. 73-80.

5. Боханко А. С., Дроздов А. Ю., Новиков С. В., Шлыков С. Л. Распределение регистров методом раскраски графа несовместимости для У1Л\У-архитсктур / Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Вып. 8. М., 2005. С. 71-77.

6. Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ / Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Вып. 8. М., 2005. С. 78-87.

Принято к исполнению 01/10/2005 Исполнено 02/11/2005

Заказ № 1176 Тираж: 75 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (095) 975-78-56 (095) 747-64-70 .www.autoreferat.rg

42077ft

РНБ Русский фонд

2006-4 20620

Актуальность работы.2

Цель диссертационной работы.3

Научная новизна.4

Апробация.5

Публикации.5

Краткое содержание работы.6

3.4 Выводы

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

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

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

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

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

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

Проведен анализ вопросов, связанных с распределением регистров, не зависящим от целевой платформы. Проведен анализ подходов к написанию платформонезависимого оптимизирующего компилятора. Представлены методы, позволяющие реализовать распределение регистров для практически всех современных архитектур на базе единого исходного кода. Предложен список параметров целевой архитектуры, достаточный для настройки платформонезависимого распределителя регистров. Такой не зависящий от целевой платформы распределитель регистров был реализован в рамках оптимизирующего компилятора для микропроцессора Эльбрус-ЗМ; его тестирование проведено на трех платформах: Эльбрус-ЗМ, Intel Itanium и SUN SPARC V8.

Заключение

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

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

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

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

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

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

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

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

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

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

1. Арнольд 1997. Арнольд К., Гослинг Д. Язык программирования Java// Питер, Санкт-Петербург, 1997

2. Евстигнеев 1994. Евстигнеев В. А., Касьянов В. Н. Теория графов: алгоритмы обработки деревьев // ВО "Наука", Новосибирск, 1994

3. Ершов 1977. Ершов А. П. Введение в теоретическое программирование (беседа о методе) // Наука, Москва, 1977

4. Керниган 2001. Керниган Б., Ритчи Д. Язык программирования С, 3-е издание // С-Петербург, Невский Диалект, 2001

5. Рейли 1999. Рейли М. Как рождается микропроцессор Alpha" // Открытые Системы, №4, 1999, С. 14-21

6. Шланскер 1999. Шланскер М. С., Pay Б. Р. Явный параллелизм на уровне команд // Открытые Системы, № 11-12 (43^14), 1999, С. 8-16

7. Шривер 1999. Шривер Б., Капек П. Из чистого любопытства. Интервью с Джоном Коком // Открытые Системы, № 9-10 (41-42), 1999, С. 89-96

8. Aho 1986. Aho А. V., Sethi R., Ullman J. D. Compilers: principles, techniques, and tools // Addison-Wesley, Reading, Massachusetts, 1986

9. Beck 1993. Beck G. R., Yen D. W. L., Anderson T. L. The Cydra 5 minisupercomputer: architecture and implementation // The Journal of Supercomputing, №7, 1993, pp. 143-180

10. Bharadwaj 2000a. Bharadwaj J., McKinsey C. Wavefront scheduling: path based data representation and scheduling of subgraphs // Journal of instruction-level parallelism, Vol. 1, № 6, pp. 1-6, 2000

11. Bharadwaj 2000b. Bharadwaj J., Chen W. Y., Chuang W., Hoflehner G., Menezes K., Muthukumar K., Pierce J. The Intel IA-64 compiler code generator // IEEE MICRO, № 11, 2000, pp. 44-52

12. Briggs 1989. Briggs P., Cooper K. D., Kennedy K., Torczon L. Coloring heuristics for register allocation // Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, 1989, pp. 275-284

13. Briggs 1994. Briggs P., Cooper K. D., Torczon L. Improvements to graph coloring register allocation // ACM Transactions on Programming Languages and Systems, Vol. 16, № 3, 1994, pp. 428-455

14. Callahan 1991. Callahan D., Koblenz B. Register allocation via hierarchical graph coloring // Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, 1991, pp. 192-203

15. Chaitin 1981. Chaitin G., Auslander M„ Chandra A., Cocke J., Hopkins M„ Markstein P. Register allocation via coloring // Computer Languages, №1, 1981, pp. 47-57

16. Chaitin 1982. Chaitin G. Register allocation and spilling via graph coloring// Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction, SIGPLAN Notices, №6, 1982, pp. 98-105

17. Chow 1990. Chow F. C., Hennessy J. L. The priority-based coloring approach to register allocation // ACM Transactions on Programming Languages and Systems, Vol. 12, №4, pp. 501-536

18. Cocke 1988. Cocke J. Turing award lecture: the search for performance in scientific processors // Communications of the ACM, №3, 1998, pp. 250-253

19. Diefendorf 1999. Diefendorf K. The russians are coming: supercomputer maker Elbrus seeks to join x86/IA-64 melee // Microprocessor Report, Vol. 11, № 2, 1999

20. Drozdov 1993. Drozdov A., Moukhin, Kasinsky A., Okunev S., Ostanevich A., Rumyantsev Y., Sushentsov, Tikhonov V., Volkonski V., Yaremenko K. The optimizing compiler for the Elbrus-3 supercomputer // CSAM'93 Proceedings, pp. 127-128.

21. Dulong 1999. Dulong C., Krishnaiyer R„ Kulkarni D., Lavery D., Li W., Ng J., Sehr D. An overview of the Intel IA-64 compiler // Intel Technology Journal, Quarter 4, 1999

22. Eichenberger 1994. Eichenberger A. E., Davidson E. S. Minimum register requirements for a modulo schedule // Proceedings of the 27-th Annual International Symposium on Microarchitecture, San Jose, California, 1994, pp. 75-84

23. Eichenberger 1995. Eichenberger A. E. Register allocation for predicated code // Proceedings of the 28th annual international symposium on Microarchitecture, 1995, pp. 180-191

24. Ellis 1985. Ellis J. R. Bulldog: a compiler for VLIW architectures // MIT Press, Cambridge, Massachusetts, 1985

25. Fisher 1981. Fisher J. A. Trace scheduling: a technique for global microcode compaction // IEEE Transactions on Computers, Vol. C-30, pp. 478-490

26. Garner 1988. Garner R., Agrawal A., Brown W., Hough D., Joy W., Kleiman S., Muchnick S., Patterson D., Pendleton J., Tuck R. The scalable processor architecture SPARC, Proceedings of 1988 COMPCON Conference, 1988

27. GCC 2005. GCC internals manual // Free Software Foundation, URL: http://gcc.gnu.org/onlinedocs/ (August 2005)

28. Gillies 1996. Gillies D. M., Ju D. R„ Johnson R., Schlansker M. Global predicate analysis and its application to register allocation // Proceedings of the 29th annual ACM/IEEE International Symposium on Microarchitecture, 1996, pp. 114-125

29. Gordon 2001. Gordon A. D., Syme D. Toward a multi-language intermediate code // POPL'Ol Proceedings, pp. 248-260

30. Grune 2000. Grune D., Bal H. E., Jacobs C. J. H., Langendoen K. G. Modern compiler construction // John Wiley & Sons, New York, 2000

31. Gupta 1994. Gupta R., Soffa M. L., Ombres D. Efficient register allocation via coloring using clique separators // ACM Transactions on Programming Languages and Systems, Vol. 16, № 3, pp. 370-386

32. Hank 1993. Hank R. E. Machine independent register allocation for the IMPACT-C Compiler//MS Thesis, University of Illinois, Urbana, USA, 1993

33. Huck 2000. Huck J., Morriss D., Ross J., Knies A., Mulder H., Zahir R. Introducing The IA-64 Architecture // IEEE MICRO, №5, 2000, pp. 12-22

34. Hwu 1995. Hwu W. W„ Hank R. E., Gallagher D. M., Mahlke S. A., Lavery D. M., Haab G. E., Gyllenhaal J. C., August D. I. Compiler Technology for Future Microprocessors // Proceedings of the IEEE, Vol. 83, № 12, pp. 1625-1640

35. Johnson 1996. Johnson R., Schlansker M. Analysis techniques for predicated code // Proceedings of the 29th Annual International Symposium on Microarchitecture, 1996

36. Kathail 1993. Kathail V., Schlansker M., Rau B. HPL PlayDoh architecture specification: version 1.0 // Hewlett-Packard Laboratories Technical Report, HPL-93-80,1993

37. Makowski 1995. Makowski C., Pollock L. L. Achieving efficient register allocation via parallelism // Proceedings of the 1995 ACM symposium on Applied computing, 1995,pp. 123-129

38. Moore 1965. Moore G. Cramming more components onto integrated circuits // Electronic, Volume 38, № 8, 1965

39. Muchnick 1997. Muchnick S. S. Advanced compiler design and implementation // Morgan Kauffman, San Francisco, 1997

40. Nicolau 1993. Nicolau A., Novack S. Trailblazing: a hierarchical approach to percolation scheduling// Proceedings of the 1993 International Conference on Parallel Processing, 1993, pp. 120-124

41. Ning 1993. Ning Q., Gao G. R. A novel framework of register allocation for software pipelining // 20-th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1993, pp. 29-42

42. Norris 1993. Norris C., Pollock L. L. A schedular-sensitive global register allocator // Proceedings of the 1993 ACM/IEEE conference on Supercomputing, 1993, pp. 804813

43. Norris 1995. Norris C., Pollock L. L. An experimental study of several cooperative register allocation and instruction scheduling strategies // Proceedings of the 28th annual international symposium on Microarchitecture, 1995, pp. 169-179

44. Park 1991. Park J. С. H., Schlansker M. S. On predicated execution // Technical Report HPL-91-58, HP Laboratories, Palo Alto, California, 1991

45. Pinter 1993. Pinter S. S. Register allocation with instruction scheduling // Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, 1993, pp. 248-257

46. Ramalingam 1999. Ramalingam G. Identifying loops in almost linear time // ACM Transactions on Programming Languages and Systems, Volume 21, № 2, 1999, pp. 175-188

47. Rau 1989. Rau B. R., Yen D., Yen W., Towle R. The Cydra 5 departmental supercomputer: design philosophies, decisions, and trade-offs // IEEE Computer, Vol. 22, № l,pp. 12-35

48. Rau 1992. Rau B. R., Lee M., Tirumalai P. P., Schlansker M. S. Register allocation for software pipelined loops // Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation, 1992, pp. 283-299

49. Ritchie 1978. Ritchie D. M., Thompson K. The UNIX time-sharing system // The Bell System Technical Journal, № 4, 1978

50. Ryder 1986. Ryder B. G., Paull M. C. Elimination algorithms for data flow analysis // ACM Computing Surveys, N9, 1986, pp. 277-316

51. Smith 2004. Smith M. D., Ramsey N., Holloway G. A generalized algorithm for graph-coloring register allocation // Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, 2004, pp. 277-288

52. SPEC 2005. SPEC CPU2000 run and reporting rules // SPEC Open Systems Group, URL: http://www.spec.org/cpu2000/docs/runrules.html (August 2005)

53. Triebel 2000. Triebel W. Itanium architecture for software developers // Intel Press, 2000