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

Довгалюк Павел Михайлович

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

05 13 18 — Математическое моделирование, численные методы и комплексы

программ

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

ииЗиб58б8

003065868

Довгалюк Павел Михайлович

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

05 13 18 — Математическое моделирование, численные методы и комплексы

программ

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

Работа выполнена в Новгородском государственном университете имени Ярослава Мудрого

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

Макаров В А

Официальные оппоненты доктор физико-математических наук,

профессор Колногоров А В

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

Новиков Ф А

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

Институт системного программирования (ИСП) Российской академии наук (РАН)

Защита состоится "25" октября 2007 в 14 ч 00 мин на заседании Диссертационного совета Д 212 168 04 при Новгородском государственном университете имени Ярослава Мудрого по адресу 173003, Россия, Великий Новгород, ул Б Санкт-Петербургская, 41

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

Автореферат разослан "_С

/Ученый секретарь Диссертационного совета Д 212 168 04

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

профессор

Эминов С И

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Практически все производимые в настоящее время процессоры имеют конвейерную архитектуру (в том числе и процессоры от Intel, AMD, Atmel, Samsung), а оптимизация потока команд компилятором имеет большое значение Это значение будет все более возрастать в будущем при увеличении количества функциональных блоков в процессорах

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

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

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

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

1 Изучены известные математические модели базовых блоков

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

3 Исследованы свойства модели, позволяющие осуществить конвейерную оптимизацию

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

5 Разработана методика конвейерной оптимизации для более эффективного применения алгоритмов

6 Разработанная модель и алгоритмы проверены на практике

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

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

• Математическая модель представления базовых блоков для оптимизации расписаний — разреженная модель базовых блоков

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

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

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

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

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

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

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

2 Свойства модели, упрощающие применение алгоритмов для поиска расписаний операций базового блока

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

4 Алгоритм поиска оптимального расписания для последовательности команд в базовом блоке

5 Методика применения предложенного алгоритма, позволяющая затрачивать на оптимизацию меньшее количество времени при практически неизменном результате

Апробация работы Научные результаты исследования были опубликованы в "Вестнике НовГУ" (Новгород, 2005), в сборнике трудов Института системного программирования РАН (Москва, 2004, 2006), выносились на обсуждение на конференции "Математические методы в технике и технологиях" (Казань, 2005), в докладах на научных конференциях в рамках Дней Науки в НовГУ (Новгород, 2004, 2006)

Публикации По теме диссертации опубликованы 7 научных работ, из них — 4 статьи, 3 работы - в материалах конференций

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследуемой проблемы, сформулирована цель и задачи диссертационной работы, перечислены полученные в диссертации новые результаты, их практическая ценность, представлены положения, выносимые на защиту и описана структура диссертации

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

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

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

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

Зависимости между командами делятся на два класса по данным и по управлению Существуют четыре вида зависимостей по данным между двумя инструкциями ох и 02 (с>2 выполняется позже чем о%)

1 Потоковая зависимость Операция о2 зависит от операции оь если результат операции 01 является операндом операции 02 Это случай также имеет название истинной зависимости

2 Анти-зависимость Операция 02 имеет анти-зависимость по отношению к операции о\, если о2 осуществляет запись в ячейку памяти (например, в регистр), которую 01 должна прочитать перед тем, как она будет переписана 02

3 Зависимость по выходам Операция 02 зависит по выходу от операции 0\, если они обе должны записать что-либо в одну и ту же ячейку памяти

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

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

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

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

Для того чтобы задать протяженность задержки между командами в наиболее популярной модели используются числовые пометки ребер графа, соответствующие продолжительностям задержек — D((v,гí))

шоу а, Ь

ас!<1 с, 1

ши1 а, с

шоу (3, с

ти1 а, с1

Рис 1 Пример содержимого базового блока

тоу а, Ь

асЫ с, 1

ти1 а, с

тоу с1, с

иш! а, (1

Рис 2 Традиционное представление базового блока в виде графа

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

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

1 Отсутствие сброса конвейера при выполнении перехода

2 Наличие команд, занимающих несколько тактов конвейера

3 Наличие ограниченных сверху по времени зависимостей между командами

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

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

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

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

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

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

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

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

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

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

Данную модель базовых блоков можно математически описать с помощью следующего ациклического графа <3= (У.Я.я.е), где

• V — множество узлов, соответствующих конвейерным операциям, формирующим базовый блок

• Е С V х V — множество связей, определяющих порядок поступления узлов-операций (команд и задержек) на конвейер процессора

• з € V — стартовый (корневой) узел

• е € V — последний узел в любом корректном расписании, построенном на основе данного графа

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

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

Обозначим подмножество жестких связей как Н

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

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

шоу а, Ь

ти1 а, с

ас1с1 с, 1

шоу (1, с

ти1 а, (1

Рис 3 Представление базового блока с помощью разреженной модели

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

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

Некоторые зависимости также могут быть избыточными Гибкие зависимости в графе задают лишь относительный порядок вершин Такой порядок

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

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

Исходный граф С можно разбить на 2 графа (?! и С?2 в точке сочленения V так, что этот узел станет финишным подграфа С\ и стартовым для Сг При этом, в силу независимости подграфов Сп и Сг, множество корректных расписаний для исходного графа будет состоять из тех же элементов, что и декартово произведение множеств расписаний отделенных подграфов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть С = {сг} — вершины-команды, а Б = {с^} — вершины-задержки, которые допустимо поместить в расписание, учитывая входящие в них связи (те все предшественники таких вершин должны уже быть размещены в расписании) Назовем все эти вершины свободными Опишем основные шаги алгоритма построения расписания подзадачи В, состоящей в поиске расписания для некоторого подграфа, оставшегося после помещения некоторого количества вершин исходного графа в результирующее расписание

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

2 Если в С несколько вершин-команд имеют входящие жесткие связи, то

решения не существует

3 Рассмотрим решения всех подзадач для В Ец = В\Е (если ни в одну из с, не входят жесткие связи) и Ег = В\П\сг для кажой вершины сг Все задержки из множества И допустимо помещать в расписание одновременно, так как они не используют каких-либо ресурсов процессора При этом, если хотя бы одна из вершин в множестве £>и 0% имеет исходящую жесткую связь в некоторую вершину е, и эта вершина не входит в число свободных вершин подзадачи Еи то данная подзадача не имеет решения

4 Выберем кратчайшее решение подзадачи В = либо В = {й, Ео}, где Ек = г(Ег) Если не существует ни одного Е,, то и решения для всей подзадачи В не существует

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

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

1 Оптимальность для подзадач Данное свойство означает, что оптимальное решение всей задачи должно содержать оптимальные решения для ее подзадач

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

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

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

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

Несмотря на то, что предложенный алгоритм также перебирает все возможные варианты расписаний, время его работы ограничено величиной 0(п 2п), которая растет медленнее, чем О(тг') Однако, данная оценка является оценкой наихудшего предельного случая Реальное же количество выполняемых алгоритмом операций будет зависеть от структуры графа В частности, для слаборазветвленных графов, количество выполняемых алгоритмом операций будет расти как полиномиальная величина с ростом числа вершин графа

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

В разделе 3 4 была предложена следующая методика для оптимизации потоков команд в пределах функций

1 Построит ь граф зависимостей по управлению между базовыми блоками (так называемый граф потока функции)

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

3 Удалить из графа потока базовые блоки, для которых расписание уже

найдено

4 Если граф потока функции не пуст, перейти к п 2

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

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

Оптимальному алгоритму должно отдаваться предпочтение в следующих случаях

• Слаборазветвленный граф

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

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

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

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

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

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

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

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

В разделе 4 3 описано моделирование применения предлагаемой модели и алгоритма поиска оптимального расписания к архитектурам с жесткими связями между командами (например, 186О) Алгоритм ДП здесь сравнивался с традиционными списочным алгоритмом и алгоритмом с предвидением

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

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

Также было проведено исследование применения предлагаемого алгоритма как к графам, смоделированным случайным образом (7000 базовых блоков), так и к графам, полученным из реальных программ, скомпилированных для двух различных ИБС-архитектур (набор тестов 5РЕС2000, всего 101726 базовых блоков) Если применять алгоритм ДП ко всем базовым блокам программы, то полученный выигрыш по быстродействию будет намного меньше, чем затраты времени на оптимизацию

Однако, использовав предложенную в данной главе методику оптимизации, можно применять данный алгоритм лишь к 2 5% графов Таким образом будет получен тот же самый выигрыш по быстродействию (около 0 08%) Тем не менее, для подобных архитектур, алгоритм ДП выгоднее всего применять к наиболее часто выполняемым базовым блокам При этом полученный выигрыш по быстродействию будет сравним с увеличением затрат времени на оптимизацию программы

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2 Исследованы свойства модели, позволяющие применять ее для поиска расписаний узлов графа

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Довгалюк, П M Улучшенный алгоритм оптимизации порядка выполне-ия команд Вестник Новгородского государственного университета Сер Технические науки, № 30, 2005 — с 117-118 (всего 2 стр )

2 Довгалюк, П M Разреженная модель базовых блоков для оптимизации потоков команд Труды Института системного программирования Том 9 /Под ред В П Иванникова/ — M ИСП РАН, 2006 — с 23 (всего 6 стр )

3 Довгалюк, П M Улучшение алгоритма оптимизации порядка выполнения инструкций в базовых блоках Математические методы в технике и технологиях - MМТТ-18 Сб трудов XVIII Международ Науч Конф В 10 т 1 8 Секции 10,12 Под общ Ред В С Балакирева - Казань изд-во Казанского гос Технол Ун-та, 2005 — с 167-168 (всего 2 стр )

4 Довгалюк, П М Усовершенствованный алгоритм распространения констант с использованием СБА-представления Труды Института системного программирования Том 8 часть 2 /Под ред В П Иванникова/ — М ИСП РАН, 2004 - с 7 (всего 8 стр )

5 Довгалюк, П М Анализ и оптимизация циклов с помощью производящих функций Труды Института системного программирования Том 8 часть 2 /Под ред В П Иванникова/ — М ИСП РАН, 2004 — с 15 (всего 5 стр )

6 Довгалюк, П М Разреженная модель базовых блоков для оптимизации потоков команд Тезисы докладов аспирантов, соискателей, студентов XIII научной конференции преподавателей, аспирантов и студентов НовГУ Великий Новгород, 3-8 апреля 2006 г / Отв Ред В В Ша-дурский, НовГУ им Ярослава Мудрого — Великий Новгород, 2006 — (всего 1 стр )

7 Довгалюк, П М Анализ и оптимизация циклов с помощью производящих функций Тезисы докладов аспирантов, соискателей, студентов XI научной конференции преподавателей, аспирантов и студентов НовГУ Великий Новгород, 5-10 апреля 2004 г / Отв Ред В В Шадурский, НовГУ им Ярослава Мудрого — Великий Новгород, 2004 — (всего 1 стр)

Подписано к печати 14 08 07 Формат 60x84/16

Шрифт Anal Суг Тираж 100 экз Отпечатано в ЗАО "Новгородский Технопарк" 173003, Великий Новгород, ул Б С-Петербургская, 41 Тел (816 2) 73 76 76

Введение

1 Потоки команд в вычислительных процессах как объект исследования

1.1 Математические модели для оптимизации потока команд

1.2 Алгоритмы для оптимизации потока команд.

1.2.1 Списочный алгоритм оптимизации потока команд

1.2.2 Эвристики используемые списочным алгоритмом

1.2.3 Существующие расширения списочного алгоритма

1.2.4 Стохастические алгоритмы.

1.2.5 Оптимизация с помощью целочисленного линейного программирования.

1.3 Проблемы локальной оптимизации потока команд.

1.4 Выводы.

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

2.1 Задачи оптимизации потока команд.

2.2 Основные особенности целевой архитектуры.

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

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

2.5 Расписания команд для разреженной модели базовых блоков

2.6 Свойства разреженной модели базовых блоков.

2.6.1 Избыточные вершины-задержки.

2.6.2 Избыточные зависимости между вершинахми.

2.6.3 Делимость графа на несколько независимых подграфов

2.6.4 Делимость графа на несколько зависимых подграфов

2.7 Выводы.

3 Применение разреженной модели базовых блоков

3.1 Моделирование распространенных архитектур с помощью разреженной модели базовых блоков.

3.1.1 Моделирование зависимостей по данным между командами

3.1.2 Моделирование команд, занимающих несколько тактов конвейера.

3.1.3 Моделирование команд с ограниченным временем жизни результата выполнения

3.1.4 Моделирование неустранимых задержек в командах перехода.

3.1.5 Моделирование зависимостей по данным между базовыми блоками.

3.2 Преобразования графа, упрощающие его структуру.

3.2.1 Объединение узлов.

3.2.2 Объединение ребер.

3.2.3 Линеаризация подграфов-регионов с единственным входом и выходом

3.2.4 Линеаризация подграфов-регионов с побочными входами и выходами.

3.3 Алгоритмы оптимизации потока команд.

3.3.1 Списочный алгоритм оптимизации потока команд

3.3.2 Оптимизационные эвристики.бб

3.3.3 Подходы, применяемые для получения оптимального расписания.

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

3.4 Методика оптимизации

3.5 Выводы.

Исследование разреженной модели базовых блоков

4.1 Описание предлагаемого алгоритма построения расписания

4.2 Программный комплекс для моделирования работы алгоритмов поиска расписания на разреженной модели базовых блоков

4.3 Исследование разреженной модели для архитектур с жесткими связями между командами.

4.3.1 Способ создания случайных графов.

4.3.2 Метод измерения параметров графов

4.3.3 Результаты сравнения алгоритмов поиска расписаний

4.3.4 Исследование вычислительной сложности предлагаемого алгоритма.

4.3.5 Выводы.

4.4 Исследование разреженной модели для архитектур без жестких связей между командами.

4.4.1 Исследование разреженной модели с использованием графов, сгенерированных случайным образом

4.4.2 Способ создания случайных графов.

4.4.3 Метод измерения параметров графов

4.4.4 Результат сравнения списочного алгоритма с предлагаемым алгоритмом поиска расписания.

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

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

4.4.7 Выводы.

4.5 Рекомендации по применению алгоритма ДП в компиляторе

4.6 Особенности реализации предлагаемого алгоритма построения расписания.

4.7 Выводы.

Практически все производимые в настоящее время процессоры имеют конвейерную архитектуру (в том числе и процессоры от Intel, AMD, Atmel, Samsung). Следовательно, оптимизация потока команд компилятором имеет большое значение в настоящие дни [27]. Значение данной технологии будет все более возрастать в будущем при увеличении количества функциональных блоков в процессорах.

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

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

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

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

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

1. Отсутствие сброса конвейера при выполнении перехода

2. Наличие команд, занимающих несколько тактов конвейера

3. Наличие жестких связей по времени между командами

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

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

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

2. Исследование свойств модели, позволяющих осуществить оптимизацию.

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

4. Разработка методики оптимизации для более эффективного применения алгоритмов.

5. Проверка разработанной модели и алгоритмов на практике.

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

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

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

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

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

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

4.7 Выводы

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

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

Для моделирования работы алгоритмов оптимизации на разреженной модели был разработан программный комплекс. Достоверность результатов моделирования была проверена сравнением результатов с известными из работ [33], [42], [83]. Объем исходного кода разработанного комплекса составил около 4000 строк в 8 модулях.

В разделе 4.3 смоделировано применение предлагаемой модели и алгоритма поиска оптимального расписания к архитектурам с жесткими связями между командами (например, 1860). Алгоритм ДП здесь сравнивался с традиционными списочным алгоритмом и алгоритмом с предвидением.

В результате моделирования было получено, что в среднем для 25% графов традиционные алгоритмы либо не находят расписания вообще, либо делают это неоптимально. Эти данные соответствуют полученным в результате других исследований (например, в работе [33]), следовательно, алгоритм ДП найдет лучшее расписание в 25% случаев, чем традиционные. В результате этого достигается достаточно большой средний выигрыш по быстродействию результирующей программы в 3%. Кроме того, благодаря применению предложенной в данной главе методике оптимизации, увеличение времени, затрачиваемого на оптимизацию, будет сравнимым с полученным выигрышем по быстродействию результирующей программы. Следовательно, применение предложенной методики и алгоритма на практике является оправданным.

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

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

Заключение

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

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

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

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

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

Также в работе были получены следующие практические результаты:

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

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

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

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

Научные результаты исследования были опубликованы в сборнике трудов Института системного программирования РАН (Москва, 2006), выносились на обсуждение на конференции "Математические методы в технике и технологиях" (Казань, 2005), в докладах на научных конференциях в рамках Дней Науки в НовГУ (Новгород, 2004, 2006).

Все научные и практические результаты получены автором самостоятельно.

Дальнейшее развитие исследований может идти в следующих направлениях:

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

Разработка методов эффективного применения разреженной модели к оптимизации циклов.

Исследование вопросов применения модели к архитектурам с очень длинным программным словом (УЫ\У), а также к многоядерным и многопроцессорным архитектурам.

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

2. Барский, А. Б. О построении диспетчеров для вычислительных систем. Изв. АН СССР. Техническая кибернетика, 1971, № 1, с. 113-118.

3. Барский, А. Б., Бахарев, В. М., Безденежных, Н. П. и др. Некоторые вопросы диспетчеризации вычислительных систем. — Вопросы радиоэлектроники. Сер. Электронная вычислительная техника, 1974, вып. 8, с. 27-42.

4. Барский, А. Б. Планирование параллельных вычислительных процессов. — М.: Машиностроение, 1980. — 192 с.

5. Головкин, Б. А. Параллельные вычислительные системы. — М.:Наука, Главная редакция физ.-мат. литературы, 1980. — 520 с.

6. Головкин, Б. А. Классификия методов диспетчеризации работы многопроцессорных и многомашинных вычислительных систем. — Управляющие системы и машины, 1982, № 3, с. 150-162.

7. Головкин, Б. А. Расчет характеристик и планирование параллельных вычислительных процессов. — М.: Радио и связь, 1983. — 272 с.

8. Довгалюк, П. М. Усовершенствованный алгоритм распространения констант с использованием GSA-представления. Труды Института системного программирования: Том 8 часть 2. /Под ред. В.П. Иваннико-ва/ М.: ИСП РАН, 2004. - с. 7 (всего 8 стр.)

9. Довгалюк, П. М. Анализ и оптимизация циклов с помощью производящих функций. Труды Института системного программирования: Том 8 часть 2. /Под ред. В.П. Иванникова/ М.: ИСП РАН, 2004. - с. 15 (всего 5 стр.)

10. Довгалюк, П. М. Улучшенный алгоритм оптимизации порядка выпол-неия команд. Вестник Новгородского государственного университета. Сер. Технические науки, № 30, 2005. — с. 117-118 (всего 2 стр.)

11. Довгалюк, П. М. Разреженная модель базовых блоков для оптимизации потоков команд. Труды Института системного программирования: Том 9. /Под ред. В.П. Иванникова/ М.: ИСП РАН, 2006. - с. 23 (всего 6 стр.)

12. Карцев, М. А., Брик, В. А. Вычислительные системы и синхронная арифметика. — М.:Радио и связь, 1981. — 360 с.

13. Касьянов, В. Н., Евстигнеев, В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — 1104 с.

14. Кнут, Д. Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с англ. — М.: Издательский дом "Вильяме", 2005. — 720 с.

15. Конвей, Р. В., Максвелл, В. Л., Миллер, Л. В. Теория расписаний: Пер. с англ. / Под ред. Г. П. Башарина. — М.: Наука, Главная редакция физ.-мат. литературы, 1975. — 360 с.

16. Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 с.

17. Методы параллельного микропрограммирования / П. А. Анишев, С. М. Ачасова, О. JI. Бандман и др.; Под ред. О. JI. Бандман. — Новосибирск: Наука, Сибирское отделение, 1981. — 180 с.

18. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф. Г. Энслоу: Пер. с англ. М.: Мир, 1976. — 384 с.

19. Подчасова, Т. П., Португал, В. М., Татаров, В. А. и др. Эвристические методы календарного планирования. — Киев: Технжа, 1980. — 138 с.

20. Поспелов, Д. А. Введение в теорию вычислительных систем. — М,:Сов. радио, 1972. 280 с.

21. Танаев, В. С., Шкурба, В. В. Введение в теорию расписаний. — М.: Наука, Главная редакция физ.-мат. литературы, 1975. — 256 с.

22. Трахтенгерц, Э. А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. — М.: Наука, 1981. — 254 с.

23. Adam, Т. L., Chandy, К. М, Dickson, J. R. A comparison of list schedules for parallel processing systems. — Commun. ACM, 1974, v. 17, № 12, p. 685-690.

24. Appelbe, В., Das, R., and Harmon, R. Instructions scheduling for highly super-scalar processors. Tech. Rep. GIT-CC-97-34, College of Computing, Georgia Institute Of Technology, 1997.

25. Arya, S. An Optimal Instruction-Scheduling Model for a Class of Vector Processors. IEEE Transactions on Computers, C-34(ll):981-995, November 1985.

26. Baer, J. L. A survey of some theoretical aspects of multiprocessing. — Computing Surveys, 1973, v. 5, № 1, p. 31-80.

27. Baker, K. R. Introduction to sequencing and scheduling. — New York: J. Wiley and Sons, 1974. 305 p.

28. Beaty, S. Lookahead scheduling. Proceedings of the 25th annual international symposium on Microarchitecture. Portland, Oregon, United States, pp. 256-259, 1992.

29. Beaty, S. Genetic algorithms versus tabu search for instruction scheduling. In International Conference on Neural Networks and Genetic Algorithms (Innsbruck, Austria, April 1993).

30. Beaty, S. List scheduling: Alone, with foresight, and with lookahead. In Conference on Massively Parallel Computing Systems: the Challenges of General-Purpose and Special-Purpose Computing (Ischia, Italy, May 1994).

31. Beaty, S., Colcord, S., and Sweany, P. Using genetic algorithms for fine-tune instruction-scheduling heuristics. In Proceedings of the Second International Conference on Massively Parallel Computing Systems (Italy, 1996).

32. Bernstein, D., and Gertner, I. Scheduling expressions on a pipelined processor with a maximal delay of one cycle. ACM Transactions on Programming Languages and Systems, ll(l):57-66, January 1989.

33. Bernstein, D., Rodeh, M., Gertner, I. On the complexity of scheduling problems for parallel/pipelined machines. IEEE Transactions on Computers, 38(9):1308-1313, September 1989.

34. Bruno, J., Jones, J., and So, K. Deterministic scheduling with pipelined processors. IEEE Transactions of Computers C-29, 1980, pp. 308-316.

35. C-M Chang, C-M Chen, and C-T King. Using Integer Linear Programming for Instruction Scheduling and Register Allocation in Multi-Issue Processors. Computers and Mathematics with Applications, 34(9): 1-14, November 1997

36. Hong-Chich Chou, Chung-Ping Chung. An Optimal Instruction Scheduler for Superscalar Processor, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.303-313, March 1995.

37. Coffman, E. G., Jr., Denning, P. J. Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973.

38. Computer and job-shop scheduling theory / Ed. E. G. Goffman. — New York: J. Wiley and Sons, 1976. 299 p.

39. Cooper, K. D., Schielke, P. J., Subramanian, D. An experimental evaluation of list scheduling. Technical report, Dept. of Computer Science, Rice University, Sep. 1998.

40. Dujmovic, J. J. and Dujmovic, I. Evolution and evaluation of SPEC benchmarks. SIGMETRICS Perform. Eval. Rev. 26, 3 (Dec. 1998), 2-9.

41. Ertl, A. and Krall, A. Optimal Instruction Scheduling Using Constraint Logic Programming, In Programming Language Implementation and Logic Programming (PLILP). Springer-Verlag, 1991.

42. Frederickson, G. N. Scheduling unit-time tasks with integer release times and deadlines. Tech. Rep. CS-81-27, Dept. of Computer Science, Penn. State University, 1982.

43. Garey, M. R., Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman k Co., New York, NY, 1979.

44. Gibbons, P. B. and Muchnick, S. S. Efficient instruction scheduling for a pipelined architecture. In Proceedings ACM SIGPLAN'86 Conference on Programming Language Design and Implementation, pages 11-16, 1986.

45. Gonzalez, M. J. Deterministic processor scheduling. — Computing Surveys, 1977, v. 9, № 3, p. 173-204.

46. Graham, R. L. Bounds for certain multiprocessing anomalies. — Bell System Techn. J., 1966, v. 45, № 9, p. 1563-1581.

47. Hennessy, J., Jouppi, N., Gill, J., Baskett, F., Strong, A., Gross, T., Rowen, C., and Leonard, J. The MIPS machine. Proceedings IEEE Compcon, 1982, 2-7.

48. Hennessy, J. L. and Gross, T. Postpass Code Optimization of Pipeline Constraints. ACM Trans. Program. Lang. Syst. 5, 3. Jul. 1983. pp. 422448.

49. Intel, i860 64-bit microprocessor programmer's reference manual, 1990.

50. Katevenis, M. G. Reduced Instruction Set Computer Architectures for VLSI. Massachusetts Institute of Technology, 1985.

51. Keßler, C. W., Rauber, T. Generating optimal contiguous evaluations for expression DAGs. Computer Languages 21(2) pp. 113-27, 1995.

52. Keßler, C. Scheduling Expression DAGs for Minimal Register Need. Computer Languages, 24(l):33-53, April 1998.

53. Kogge, P. M. The Architecture of Pipelined Computers. McGraw-Hill Book Company, New York, 1981.

54. Kohler, W. H. A preliminary evaluation of the critical path method for scheduling tasks on multiprocessor systems, — IEEE Trans. Comput., 1975, v. C-24, № 12, p. 1235-1238.

55. Krishnamurthy, S. M. A brief survey of papers on scheduling for pipelined processors. SIGPLAN Notices, 25(7):97-106, July 1990.

56. Landskov, D. et al. Local microcode compaction techniques, ACM Comp. Surveys, vol. 12, no. 3, pp. 261-294, Sept. 1980.

57. Lenstra, J. K., Kan, A. H. G. R., and Brucker, P. Complexity of machine scheduling problems. Annals of Discrete Mathematics 1,1977, pp. 343-362.

58. Leung, A., Palem, K. V., and Pnueli, A. Scheduling time-constrained instructions on pipelined processors. ACM Trans. Program. Lang. Syst. 23, 1 (Jan. 2001), pp. 73-103.

59. Leupers, R., Marwedel, P. Time-constrained code compaction for DSP's, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v. 5 n.l, p.112-122, March 1997.

60. Lin, S. and Kernighan, B. W. An effective heuristic for the traveling salesman problem. Oper. Res., 21(2):498-516, 1973.

61. Linn, J. SRDAG compaction — a generalization of trace scheduling to increase the use of global context information. In Proceedings of the 16th Annual Microprogramming Workshop (December 1983), vol. 14 of ACM Sigmicro Newsletter, pp. 11-22.

62. Manacher, G. K. Production and stabilization of real-time task schedules. J. ACM, 1967, v. 14, № 3, p. 439-465.

63. Margulis, N. i860 microprocessor architecture, Osborne/McGraw-Hill, Berkeley, CA, 1990.

64. Muchnick, S. Advanced compiler design and implementation, 1997.

65. Ochsner, B. P. Controlling a multiprocessor system. — Bell Lab. Rec., 1966, v. 44, № 2, p. 59-62.

66. Palem, K. S. On the Complexity of Precedence Constrained Scheduling. Technical Report. UMI Order Number: CS-TR-86-11., University of Texas at Austin, 1986.

67. Palem, K. V. and Simons, B. B. Scheduling time-critical instructions on RISC machines. ACM Trans. Program. Lang. Syst. 15, 4. Sep. 1993. pp. 632-658.

68. Patel, J. H. and Davidson E. S., Improving the throughput of a pipeline by insertion of delays. In Proc. of the 3rd Ann. Symp. on Computer Architecture, pages 159-164, Clearwater, Flor., Jan. 19-21, 1976. IEEE Comp. So. and ACM SIGARCH.

69. Radin, G. The 801 minicomputer. IBM Journal of Research and Development 27, 3, 1983, pp. 237-246.

70. Ramamoorthy, C. V., Chandy, K. M., and Gonzalez, M. J. Jr. Optimal scheduling strategies in a multi-processor system. IEEETrans. Comp. C-21, 2 (Feb. 1972), 137-146.

71. Rau, B. R., Fisher, J. A., Instruction-level parallel processing: History, overview, and perspective. Journal of Supercomputing — Special Issue, 7:9-50, July 1993.

72. Rinnooy Kan, A. H. G. Machine scheduling problems: Classification, complexity, and computations. — The Hague: Martinus Nijhoff, 1976. — 180 p.

73. Schielke, P. Issues in Instruction Scheduling. Rice University, Department of Computer Science. Ph. D. Thesis Proposal

74. Bjorn De Sutter. General-Purpose Architecture Instruction Scheduling Techniques. ELIS Technical Report DG 98-09, November 1998

75. Vegdahl, S. R. Local code generation and compaction in optimizing microcode compilers, 1982.

76. Warren, H. S. Instruction scheduling for the IBM RISC System/6000 processor. IBM J. Res. Dev. 34, 1, Jan. 1990, pp. 85-92.

77. Wilken K., Liu J., Heffernan M. Optimal instruction scheduling using integer programming. Proceedings of the ACM SIGPLAN'OO conference on Programming language design and implementation, p. 121-133, June 18-21, 2000, Vancouver, British Columbia, Canada

78. Zweben, M., Davis, E., Daun, D., Drascher, E., Deale, M., and Eskey, M. Learning to improve constraint-based scheduling. Artificial Intelligence 58(1—3):271—296, 1992.

79. Zweben, M., Daun, B., and Deale, M. Scheduling and rescheduling with iterative repair. In Intelligent Scheduling, pp. 241-255. Morgan Kaufman, San Mateo, CA, 1994.