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

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

Шумаков Сергей Михайлович

Оптимизация объектного кода для процессорных архитектур с поддержкой параллелизма

на уровне команд

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2002

Работа выполнена в Научно-исследовательском институте системных исследований Российской Академии наук.

Научные руководители: член-корреспондент РАН,

профессор Бетелин В.Б., доктор физико-математических наук Галатенко В. А.

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

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

Защита диссертации состоится "_"_2002 г. в_часов на заседании

диссертационного совета Д 002.087.01 при институте системного программирования РАН (109004, г. Москва, ул. Большая Коммунистическая, д. 25).

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

Автореферат разослан "_"_2002 г.

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

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

Актуальность темы.

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

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

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

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

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

Основными целями диссертационной работы являются:

- исследование методов оптимизации объектного кода для микропроцессорных архитектур с параллелизмом на уровне команд;

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

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

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

Предложен алгоритм планирования потока команд для процессоров с

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

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

Практическая ценность.

Реализован оптимизирующий компилятор для отечественного микропроцессора 1В577. Этот компилятор используется в НИИСИ РАН, КБ "Корунд".

Апробация.

Основные положения диссертационной работы докладывались на международной конференции «Параллельные вычисления и задачи управления», Москва, ИПУ РАН 2001 и на семинаре «Современные сетевые технологии», МГУ, 2001.

Публикации.

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

Объем и структура работы.

Диссертация состоит из 4 глав, заключения и списка литературы. Диссертация содержит 162 страницы машинописного текста, включая 27 рисунков и 3 таблицы.

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

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

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

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

Процессоры, способные одновременно и независимо выполнять несколько команд, обладают исключительно высоким потенциалом производительности и находят все более широкое применение. О процессорах такого типа говорят, что они поддерживают параллелизм на уровне команд (Instruction Level Parallelism, ILP). Класс ILP-процессоров включает суперскалярные процессоры и процессоры с очень длинным командным словом (Very Large Instruction Word, VLIW), к числу которых относятся, в частности, многие модели цифровых процессоров обработки сигналов.

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

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

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

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

Ниже перечислены основные методы анализа, реорганизации и оптимизации кода, применяемые в ILP-компиляторах.

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

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

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

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

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

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

Также усложняет генерацию кода традиционно малое число регистров в таких процессорах.

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

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

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

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

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

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

1. Планирование потока команд: объединение команд, из которых состоит сгенерированный базовым компилятором код, в длинные командные слова.

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

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

3. Модификация команд. Примером модификации может служить замена способа адресации при обращении к памяти.

4. Удаление лишних команд (результат которых не используется).

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

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

Для организации перебора строится граф состояний, где каждой вершине £ соответствует подмножество команд, выведенных в выходной поток из множества всех команд участка Св. Будем называть вершины этого графа также наборами или состояниями перебора. Начальное состояние соответствует пустому набору команд, конечное - набору Св. За один шаг алгоритма строится одно командное слово, называемое также УЫШ-строкой. УЫШ-строка составляется из готовых к исполнению команд1.

Дуга из £ в 8' соответствует построению УЬГ^строки из множества команд (£' - £). Оптимальный план выполнения вычисляется как путь с минимальной стоимостью из начального состояния в конечное. Стоимость пути £0, . ., -Я определяется суммой стоимостей УЫ^строк 2:

к-1

ЕС081( £+1- £)

1=00

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

1. Условие готовности. Все команды, от которых с1, ..., сп зависят по данным, выведены ранее.

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

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

1. стоимость набора Сов1;(£г) - длина кратчайшего (из построенных до сих пор)

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

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

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

пути из начального (пустого) набора £ьеёт в £■; 2. набор £=Ргеё(£г), такой что дуга £) принадлежит кратчайшему пути из

£Ъе§щ в £.

Построив таким образом все пути из 5ьеёт в конечный набор £епа, можно затем восстановить (в обратном направлении) оптимальный путь: £епа, Ргеё(£епа), Ргеё(Ргеё(£епа)), ... . Соответствующую ему последовательность УЬГ^строк также можно восстановить из наборов, через которые проходит кратчайший путь.

Перебор в порядке неубывания мощности наборов является важным условием. Он гарантирует, что к моменту, когда начинается построение дуги из набора Я, уже пройдены все возможные пути из 5ьеёш в £ (по определению все пути в графе направлены от наборов меньшей мощности к наборам большей мощности); следовательно, стоимость £ уже определена как длина кратчайшего пути из £ьеёт в £.

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

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

Ограничение числа наборов одинаковой мощности. Если в исходном линейном участке есть длинная последовательность команд, не зависящих друг от друга, то количество наборов одинаковой мощности ограничено константой 2М, где N - число независимых команд. Чтобы избежать рассмотрения слишком большого числа наборов, постпроцессор ограничивает количество наборов одной мощности, оставляя не более N с наименьшими стоимостями и не более Ы2 с наименьшим относительным смещением команд (наиболее похожих на исходный). Первые нужны, чтобы сохранить оптимальные пути, имеющие наименьшее время выполнения, последние - для того, чтобы гарантировать нахождение хотя бы одного пути. Если оставлять только наиболее удачные

4

пути, то существует риск, что все они заведут в тупики.

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

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

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

Областью жизни Ь(т) )=(а, Readers(a,r)) регистра г называется множество, состоящее из команды а, пишущей значение в г, и команд Readers(a,r), читающих это значение. Областей жизни регистра на линейном участке может быть несколько. Область жизни открыта, если выведена пишущая команда, но не все читающие. С точки зрения сохранения зависимостей по данным при построении частичных планов не может быть открыто более одной области жизни одного и того же регистра, что позволяет исключить из рассмотрения значительное количество наборов.

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

• Команды а, Ь несовместимы, а И Ь, если их параллельное выполнение невозможно.

• Команда а строго предшествует Ь, (а □ Ь), если в любом допустимом плане исполнения а выполняется раньше, чем Ь.

• Команда а нестрого предшествует Ь, (а □ Ь), если в любом допустимом плане исполнения а выполняется не позже, чем Ь.

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

1. Уменьшение числа областей жизни, отслеживаемых при переборе. Пусть имеется область жизни Ь(г)=(а, Readers(a,r)) и все другие команды, пишущие в регистр г, либо строго предшествуют а, либо строго следуют за всеми командами из Reаders(a,r). Тогда область Ь(г) можно исключить из рассмотрения при переборе.

2. Уменьшение размеров областей ^жизни. Если сформулированное выше условие выполняется не для всех команд из Reаders(a,r), то в Readers(a,r) можно выделить подмножество команд, для которых оно не выполняется, и отслеживать только их.

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

4. Дополнительный контроль УЫШ-строк. При построении множества

всех допустимых "УЫ^строк в данном состоянии перебора £ будем следить, чтобы команды а, Ь, такие что а □ Ь и Ь □ а, всегда помещались в одну "УЪГ^строку (исполнялись одновременно).

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

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

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

Описание целевой платформы для постпроцессора состоит из следующих элементов:

- описание регистров, классов регистров, соглашений о связях;

- описание ресурсов (функциональных устройств процессора и др.);

- описания свойств команд и модификаторов5 а также набор предикатов, описывающих различные виды операндов;

- описание множеств взаимозаменяемых вариантов команд;

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

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

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

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

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

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

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

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

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

Измерение эффективности генерируемого кода показало, что проигрыш оптимальному коду (написанному на языке ассемблера квалифицированным программистом) составляет от 1.2 до 2.2 раз. Примеры вычислительных задач, характерных для процессора 1В577, и коэффициенты эффективности сгенерированного кода приведены в таблице.

Коэффициент эффективности

Тестовая задача Вещественные данные Комплексные данные

1. Сложение векторов 1.2 1.4

2. Умножение вектора на скаляр 1.7 1.5

3. Скалярное произведение векторов 1.7 1.5

4. Внешнее произведение векторов 1.7 1.5

5. Поэлементное произведение векторов 1.2 1.5

6. Умножение квадратных матриц 1.7 1.7

7. Транспонирование матрицы 1.4 1.5

8. Сравнение элементов массива с заданной константой 1.2 1.4

9. Вычисление многочлена по схеме Горнера 1.3 1.3

10. Вычисление 4 нецентральных моментов 1.6 -

11. Преобразование Фурье - 2.1

12. Корреляция (FIR фильтр) - 1.5

13. FIR фильтр со сдвигом - 2.0

14. Степенной ряд N-го порядка 1.7 -

15. Сглаживание картинки фильтром 3х3 2.2 -

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

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

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

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

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

4. Разработаны и реализованы средства настройки оптимизирующего постпроцессора на различные целевые архитектуры. Выполнена настройка на отечественный микропроцессор 1В 577.

5. Разработан оптимизирующий кросс-компилятор с языка Си для отечественных целевых ЭВМ на основе микропроцессора 1В 577. Компилятор позволяет сочетать преимущества программирования на языке высокого уровня с качеством объектного кода, близким к ручному, что подтверждено полученными экспериментальными оценками.

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

Личный вклад.

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

Автор выражает глубокую благодарность научным руководителям В.Б. Бетелину и В. А. Галатенко за постоянное внимание и неоценимую помощь.

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

Автор признателен А.И. Немытову и Ю.С. Осипову за внимание к работе, за консультации по тонкостям микропроцессора 1В577, а также за конструктивную, доброжелательную критику.

По теме диссертации опубликованы следующие работы:

1. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Алгоритм планирования потока команд для УЫ^процессоров. - М.: НИИСИ РАН, 2002.

2. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Генерация эффективного кода для процессорных архитектур с явным параллелизмом. -М.: НИИСИ РАН, 2001.

3. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. О проблеме оптимизации кода для процессорных архитектур с явным параллелизмом. -Труды международной конференции "Параллельные вычисления и задачи управления". - М.: ИПУ РАН, 2001.

4. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Описание УЬГ^архитектуры в оптимизирующем постпроцессоре. - М.: НИИСИ РАН, 2001.

5. Шумаков. С.М. Обзор методов оптимизации кода для процессоров поддержкой параллелизма на уровне команд. - М.: НИИСИ РАН, 2002.

Оглавление.

1. Введение.

2. Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд.

2.1. ILP-платформы.

2.2. Критерии оптимизации кода.

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

2.4. Области планирования.

2.5. Усиление параллелизма в пределах областей планирования

2.5.1. Преобразования циклов.

2.5.2. Встраивание функций.

2.5.3. Снятие зависимостей по данным.

2.5.4. Соотношение программного и аппаратного параллелизма.

2.6. Планирование команд.

2.6.1. Алгоритмы планирования.

I 2.6.2. Координация планирования и распределения регистров.

2.6.3. Глобальное планирование.

2.6.4. Аппаратная поддержка глобального планирования.

2.6.5. Метод доминантного параллелизма при планировании в древовидных областях.

2.6.6. Планирование по прогнозу значений данных.

2.7. Особенности генерации кода для ЦПОС.

2.8. О роли языковых расширений.

2.9. Сводка методов оптимизации для процессоров с поддержкой параллелизма на уровне команд.

3. Компилятор с оптимизирующим постпроцессором - детальное описание.

3.1. Характеристика процессора 1В577.

3.2. Общие сведения о компиляторе для 1В577.

3.3. Роль базового компилятора.

3.4. Постпроцессирование.

3.4.1. Примеры оптимизаций, выполняемых постпроцессором.

3.4.2. Основные понятия.

3.4.3. Последовательность обработки входного ассемблерного файла.

3.4.4. Аппаратная совместимость.

3.4.5. Модель линейного участка и постановка задачи планирования.

3.4.6. Алгоритм планирования.

3.4.7. Учет аппаратных задержек.

3.4.8. Сокращение перебора.

3.4.9. Подбор вариантов команд.

3.4.10. Модификация команд.

3.5. Настройка постпроцессора на архитектуру 1В577.

3.5.1. Регистры.

3.5.2. Классы регистров.

3.5.3. Соглашения о связях.

3.5.4. Ресурсы.

3.5.5. Свойства команд.

3.5.6. Варианты.

3.5.7. Псевдокоманды (модификаторы).

3.5.8. Динамические ресурсы.

3.5.9. Реализация аппаратных ограничений при помощи псевдорегистров.

4. Оценки эффективности.

4.1. Сравнение с другими методами планирования.

4.1.1. Списочное планирование.

4.1.2. Методы планирования на основе ЦЛП.

4.1.3. Метод планирования с использованием дизъюнктивных графов.

4.2. Измерение эффективности кода для процессора 1В577.

4.2.1. Цели и методика измерений.

4.2.2. Результаты измерений.

4.2.3. Конвейеризация и развертка циклов.

4.2.4. Замена адресации со смещением на адресацию с постинкрементацией адресного регистра.

4.2.5. Перестановки обращений к памяти.

4.2.6. Оценка эффективности оптимизаций.

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

Актуальность темы.

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

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

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

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

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

Основными целями диссертационной работы являются:

- исследование методов оптимизации объектного кода для микропроцессорных архитектур с параллелизмом на уровне команд;

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

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

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

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

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

Практическая ценность.

Реализован оптимизирующий компилятор для отечественного микропроцессора 1В577. Этот компилятор используется в НИИСИ РАН, КБ "Корунд".

Апробация.

Основные положения диссертационной работы докладывались на международной конференции «Параллельные вычисления и задачи управления», Москва, ИПУ РАН 2001 и на семинаре «Современные сетевые технологии», МГУ, 2001.

Публикации.

По теме диссертации опубликовано 5 печатных работ - [4], [5], [6], [7],

19].

Объем и структура работы.

Диссертация состоит из 4 глав, заключения и списка литературы.

Первая глава является введением.

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

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

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

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

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

5. Заключение

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

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

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

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

4. Разработаны и реализованы средства настройки оптимизирующего постпроцессора на различные целевые архитектуры. Выполнена настройка на отечественный микропроцессор 1В577.

5. Разработан оптимизирующий кросс-компилятор с языка Си для отечественных целевых ЭВМ на основе микропроцессора 1В577. Компилятор позволяет сочетать преимущества программирования на языке высокого уровня с качеством объектного кода, близким к ручному, что подтверждено полученными экспериментальными оценками.

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

1. Ахо А., Сети Р., Ульман Д., Компиляторы: принципы, технологии и инструменты. - М., Издательский дом "Вильяме", 2001.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, том 2. М., Мир, 1978.

3. Балашов В.В., Капитонова А.П., Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Метод и средства оценки времени выполнения оптимизированных программ. Программирование #5, 2000, с. 52- 61.

4. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Алгоритм планирования потока команд для VLIW-процессоров. М.: НИИСИ РАН, 2002.

5. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Генерация эффективного кода для процессорных архитектур с явным параллелизмом. М.: НИИСИ РАН, 2001.

6. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. О проблеме оптимизации кода для процессорных архитектур с явным параллелизмом. Труды международной конференции "Параллельные вычисления и задачи управления". - М.: ИПУ РАН, 2001.

7. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Описание VLIW-архитектуры в оптимизирующем постпроцессоре. М.: НИИСИ РАН, 2001.

8. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М., Мир, 1975.

9. Дорошенко А.Ю., Куйвашев Д.В. Архитектура модульного кросскомпилятора для микропроцессоров с очень длинным командным словом. Проблемы программирования, 2000 г., N 3-4, с. 122-134 (наукр. языке).

10. Ю.Дорошенко А.Ю., Куйвашев Д.В. Интеллектуализация векторизующих компиляторов для микропроцессоров с длинным командным словом. -Проблемы программирования, 2001 г., N 1-2, с. 138-151 (на укр. языке).

11. П.Евстигнеев В.А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом (обзор). Программирование, 1991, N 2, стр. 69-80.

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

13. З.Калашников Д.В., Машечкин И.В., Петровский М.И. Планирование потока инструкций для конвейерных архитектур. Москва, МГУ, Вестник Московского университета, серия 15 (вычислительная математика и кибернетика), N4, 1999, с. 39-44.

14. Н.Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988 г.

15. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М., Мир, 1985.

16. Скворцов С.В. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов. Программирование 1996, N 2, стр. 41-52.

17. Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации. Программировние, 1992, N 3, стр. 16-37.

18. Шланскер М.С., Pay Б.Р. Явный параллелизм на уровне команд. Открытые Системы, #11-12, 1999.

19. Шумаков. С.М. Обзор методов оптимизации кода для процессоров поддержкой параллелизма на уровне команд. М.: НИИСИ РАН, 2002.

20. ADSP-21000 Family. С Tools Manual. Analog Devices, Inc. http://www.analog.com/publications/documentation/C-Toolsmanual/books. htm

21. Aho A.V., Sethi R, Ullman J.D.: Compilers Principles, Techniques, and Tools, Addison-Wesley, 1986

22. Allen J.R., Kennedy K., Porterfield C., Warren J.D. Conversion of Control Dependence to Data Dependence. Proceedings of the 1 Oth ACM Symposium on Principles of Programming Languages. Jan. 1983, pp. 177-189.

23. Araujo G., Malik S. Optimal Code Generation for Embedded Memory Non-Homogeneous Register Architectures. 8th Int. Symp.on System Synthesis (ISSS), 1995, pp. 36-41.

24. Araujo G., Malik S., Lee M. Using Register-Transfer Paths in Code Generation for Heterogeneous Memory-Register Architectures. In ACM IEEE Design Automation Conference (DAC), number 33, pp. 591-596, June 1996.

25. Baneijia S., Havanki W.A., Conte T.M. Treegion Scheduling for Highly Parallel Processors. Proceedings of the 3rd International Euro-Par Conference (Euro-Par'97, Passau, Germany), pp. 1074-1078, Aug. 1997.

26. Benitez M. E., Davidson J. W. Target-specific Global Code Improvement: Principles and Applications. Technical Report CS-94-42, Department of Computer Science, University of Virginia, VA 22903.

27. Bernstein D., Rodey M. Global Instruction Scheduling for Superscalar Machines. Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pp.241-255, June 1991.

28. Bharadwaj J., Menezes K. McKinsey C. Wavefront Scheduling: Path Based Data Representation and Scheduling of Subgraphs. The Journal of Instruction-Level Parallelism, May 2000.

29. Cooper K.D., Schielke P.J., Subramanian D. An Experimantal Evaluationof List Scheduling. Department of Computer Science, Rice University, Houston, TX, USA: Technical Report, http://cs-tr.cs.rice.edu/Dienst/UI/2.0/Describe/ncstrl.rice-cs/TR98-326

30. Eichenberger A. E., Davidson E. S., Abraham S. G. Minimizing Register Requirements of a Modulo Schedule via Optimum Stage Scheduling. -International Journal of Parallel Programming, February, 1996.

31. Eichenberger A. E., Lobo S. M. Efficient Edge Profiling for ILP-Processors. Proceedings of PACT 98, 12-18 October 1998 in Paris, France.

32. Fisher J. A. Global code generation for instruction-level parallelism: Trace Scheduling-2. Tech. Rep. HPL-93-43, Hewlett-Packard Laboratories, June 1993

33. Fisher J.A. Trace scheduling: A Technique for Global Microcode Compaction. IEEE Transaction on Computers, vol. 7, pp. 478-490, July 1981.

34. Gebotys С. H., Gebotys R. J. Complexities In DSP Software Compilation: Performance, Code Size, Power, Retargetability. 1060-3425/98, IEEE, 1998.

35. Grossman J.P. Compiler and Architectural Techniques for Improving the

36. Effectiveness of VLIW Compilation. submitted to ICCD 2000.

37. Havanki W. A., Banerjia S., Conte Т. M. Treegion Scheduling for Wide Issue Processors. Proc. 4th Intl. Symp. on HighPerformance Computer Architecture, Feb. 1998, pp. 266-276.

38. Hoogerbrugge J., Augusteijn L. Instruction Scheduling for TriMedia. The Journal of Instruction-Level Parallelism, February 1999

39. Horst E., Kloosterhius W., Heyden J. А С Compiler for the Embedded R.E.A.L DSP Architecture. Материал получен с телеконференции comp.dsp.

40. Hsu P.Y.T., Davidson E.S. Highly Concurrent Scalar Processing. -Proceedings of the 13th Annual International Symposium on Computer Architecture, pp. 386-395. June 1986.

41. IA-64 Application Developer's Architecture Guide. Intel, May 1999.

42. ISO/IEC 9899:1999(E). Programming Languages C. - ISO/IEC, 1999.

43. Kiyohara Т., Gyllenhaal J. C. Code Scheduling for VLIW/ Superscalar Processors with Limited Register Files. Proceedings of the 25th International Symposium on Microarchitecture, Dec. 1992, pp. 197-201.

44. Leung A., Palem K.V. A fast algorithm for scheduling timeconstrainedinstructions on processors with ILP. In The 1998 International Conference on Parallel Architectures and Compilation Techniques (PACT 98), Paris, October, 1998.

45. Leung A., Palem K.V. Scheduling Time-Constrained Instructions on Pipelined Processors. Submitted for publication to ACM TOPLAS, 1999.

46. Leupers R. Code Generation for Embedded Processors. ISSS 2000, Madrid/Spain, Sept 2000.51 .Leupers R. Function Inlining under Code Size Constraints for Embedded Processors. ICCAD'99, San Jose (USA), Nov 1999.

47. Leupers R. Instruction Scheduling for Clustered VLIW DSPs. -Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT'00).

48. Leupers R. Novel Code Optimization Techniques for DSPs.- 2nd European DSP Education and Research Conference, Paris/France, Sep 1998.

49. Leupers R., Marwedel P. Time-Constrained Code Compaction for DSPs. -8th Int. System Synthesis Symposium(ISSS), 1995. Trans.on VLSI Systems, Vol. 5, no. 1, March 1997.

50. Liao S., Devadas S., Keutzer K., Tjiang S., Wang A. Storage Assignmentto decrease code size. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 186-195, 1995.

51. Lin W:-Y., Lee C.G., Chow P. An Optimizing Compiler for the TMS320C25 DSP Chip. Proceedings of the 5th International Conference on Signal Processing Applications and Technology, pp. I-689-I-694, October 1994.

52. Mahlke S. A., Chen W. Y., Hwu W. W., Rau B. R., Schlansker M. S. Sentinel Scheduling for VLIW and Superscalar Processors. ASPLOS-V Conference Proceedings, October 1992.

53. Mahlke S.A., Lin D.C., Chen W.Y., Hank R.E., Bringmann R.A. Effective

54. Compiler Support for Predicated Execution Using the Hyperblock. -Proceedings of the 25th Annual International Workshop on Microprogramming (Portland, Oregon), pp. 45-54, Dec. 1992.

55. Martin M. M., Roth A., Fischer C. N. Exploiting Dead Value Information. -30th International Symposium on Microarchitecture, pages 125—135, December 1997.

56. Moreno J.H. Dynamic Translation of tree-instructions into VLIW. IBM Research Report, 1996.

57. Motorola DSP96000 User's Manual. Motorola, Inc., 1990.

58. Pai V. S., Adve S. Code Transformation to Improve Memory Parallelism. -The Journal of Instruction-Level Parallelism, May 2000.

59. Pendry A., Fenwick J. В., Norris J. C. Using SUIFas a Front-end Translator for Register Allocation and Instruction Scheduling Research. In Second SUIF Compiler Workshop, Stanford, CA, August 1997.

60. Pinter S. Register Allocation with Instruction Scheduling: a New Approach. -Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 248-257, 1993.

61. Pozzi L. Compilation Techniques for Exploiting Instruction Level Parallelism, a Survey. Milano, Italy, 1998.

62. Rajagopalan S., Vachharajani M,. Malik S. Handling Irregular ILP Within Conventional VLIW Schedulers Using Artificial Resource Constraints. -CASES'00, November 17-19, 2000, San Jose, California.

63. Rao S. IA-64 Code Generation. Electrical and Computer Engineering, June 2000.

64. Stallman R. Using and Porting GNU CC. FSF, Boston, USA.