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

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

Шувиков Сергей Владимировну 0 ^ д

Г" (1 г»

и

МЕТОДЫ И АЛГОРИТМЫ РАСПАРАЛЛЕЛИВАНИЯ ОБЪЕКТНОГО КОДА ДЛЯ ПРОЦЕССОРОВ С ПРОГРАММНЫМ УПРАВЛЕНИЕМ ФУНКЦИОНАЛЬНЫМИ УСТРОЙСТВАМИ

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

АВТОРЕФЕРАТ

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

Рязань-2000

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

академии.

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

доктор технических наук, доцент C.B. Скворцов

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

доктор технических наук, профессор Е.А. Саксонов кандидат технических наук, доцент A.A. Логинов

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

Московский технический университет связи и информатики

Защита состоится 22 декабря 2000 г. в 12 часов на заседанш диссертационного совета Д 063.92.03 в Рязанской государственно! радиотехнической академии по адресу: 391000, г. Рязань, ГСП, ул Гагарина, 59/1.

С диссертацией можно ознакомится в библиотеке Рязанско! государственной радиотехнической академии.

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

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

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

канд. техн. наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Параллельные вычисления являются од-ш из основных средств повышения производительности современ-(ых процессоров. Для увеличения эффективности использования по-генциалъного параллелизма, присутствующего в программах, в победнее время широкое распространение получили процессоры, ис-тользующие статический или программный параллелизм. Примерами эешений, использующих такой подход, могут служить суперкомпью-геры Intel Paragon, созданные на базе процессоров i860, или расшире-шя систем команд процессоров для современных персональных ком-тьютеров и рабочих станций (ММХ, 3Dnow, VIS). При такой органи-тции работы распределение инструкций по функциональным устройствам (ФУ) процессора производится на этапе трансляции программы, ITO с одной стороны, позволяет более полно использовать ресурсы, тредоставляемые процессором, а с другой - накладывает повышенные гребования на эффективность алгоритмов трансляции и оптимизации трограмм.

Процессоры со статическим управлением параллелизмом на уфовне ФУ имеют следующие характерные особенности: » фиксированное время исполнения большинства команд; » сокращенный набор команд (RISC); » наличие большого числа ФУ; • увеличение числа доступных регистров; » простая внутренняя структура.

Следует также отметить, такие черты, присущие этим процессорам, как «плавающий» формат командного слова (КС) и мультипорто-вый регистровый файл. Наличие командного слова «плавающего» формата означает, что командное слово имеет несколько вариантов разбиения на поля (форматов). Каждый из форматов обеспечивает цоступ к определенной части ресурсов процессора. При этом время смены форматов, как правило, отлично от нуля.

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

Таким образом, процессоры с программным управлением параллелизмом на уровне ФУ являются перспективным направлением в

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

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

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

Учитывая, что управление ФУ и формирование КС происходит на уровне объектного кода программы, основные задачи формулируются следующим образом:

1. Выполнить анализ существующих программных систем и методов, применяемых при трансляции и оптимизации программ и оценить возможности их использования для систем с программным управлением ФУ процессора.

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

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

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

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

1. Разработана модель процессора, учитывающая такие особенности процессоров с программным управлением на уровне ФУ, как «плавающий» формат КС с ненулевым временем смены формата и мультипортовый регистровый файл.

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные модели и методы организации параллельных вы числений на микро- и макроуровнях параллелизма, предложенные ] диссертационной работе, реализованы в программных комплексах официально зарегистрированных в Российском агентстве по правовое охране программ для ЭВМ, баз данных и топологий интегральны; микросхем (РОСАПО) и Российском агентстве по патентам и товар ным знакам (РОСПАТЕНТ).

Реализация и внедрение. Теоретические и практические ре зультаты, полученные автором диссертации, использованы при проек тировании и создании ряда программных комплексов организаци! вычислительных процессов для процессоров с программным управле нием параллелизмом на уровне функциональных устройств, а так/Ю при разработке и оптимизации программного обеспечения, предна значенного для систем обработки данных на базе процессоров с воз можностью управления ФУ.

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

• Федеральное агентство правительственной связи и информации при Президенте российской федерации, НТЦ "АТЛАС" (реализа ция криптографического алгоритма САБТ-128 в рамках проект создания системы передачи данных по открытым каналам связи);

• ГУП ОКБ «Спектр» при Рязанской государственной радиотехни ческой академии (выбор технических решений программны: средств обработки высокоинформативных потоков телеметриче ской информации для системы РОКС). I

Апробация работы. Основные положения и результаты диссертационной работы представлены и обсуждены на следующих конференциях и семинарах: Всероссийская конференция "Новые информационные технологии в радиоэлектронике" (Рязань, 1997); 2-я Всероссийская конференция "Современные информационные системы в образовании" (Рязань, 1998); Всероссийская конференция "Новые информационные технологии в радиоэлектронике" (Рязань, 1998); XXIX научно-методическая конференция Военного автомобильного института (Рязань, 1999); 4-я Всероссийская конференция "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999); Международный научно-технический семинар "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций" (Рязань, 1999); 3-я Московская Международная телекоммуникационная конференция "Молодежь и наука" в научной сессии МИФИ (Москва, 2000); 9-я Международная конференция "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций" (Рязань 2000); конференции профессорско-преподавательского состава Рязанской государственной радиотехнической академии (1998 -2000 г.г.)

Публикации. По результатам исследований автором опубликовано 18 работ, среди которых 1 статья в центральной печати, 2 свидетельства об официальной регистрации программ для ЭВМ в РОСАПО и РОСПАТЕНТ.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения и списка литературы, изложенных на 114 стр., а также приложений на 51 стр. Список литературы содержит 94 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

В результате проведенного анализа программных систем генерации кода, ориентированных на процессоры с программным управлением параллелизмом на уровне ФУ, были сделаны следующие выводы:

1. Разработка эффективного программного обеспечения для процессоров со статическим управлением ФУ невозможна без использования автоматизированных средств генерации и оптимизации объектного кода.

2. Этапы, предшествующие формированию КС, в значительной степени определяют эффективность последующей оптимизации.

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

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

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

1. Дерево, получаемое в результате разбора выражения, не содержит минималъное число ярусов.

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

3. Для большинства методов входное выражение должно быть представлено в префиксной или постфиксной записи. Эффективность работы во многом определяется вариантом записи выражения.

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

Известно, что ограниченная длина линейных блоков (ЛБ) программы не позволяет эффективно использовать потенциальные воз-

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

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

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

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

1. Матрица доступных ресурсов М =

М

1Д

м

\,т

М

м

/не-

которая со-

держит число и тип доступных ресурсов для каждого формата КС.

2. Матрица времен перехода между форматами Т =

I'1 • •• V

т8,\ •

где

\Г

О, если

1Р-

если г*

Каждый элемент матрицы определяет

время перехода от г" -го формата КС с к ] -му формату.

>. Матрица с элементами, определяющими времена загруз-

Л/ ^

'М 1,2

ки/сохранения данных в регистры /„ = • I

/ ..V

. Вектор времен исполнения КС £ = (&] -•■ %).

При этом Я -число форматов КС, поддерживаемых процессо-юм, т -число типов ресурсов процессора, г-число типов регистров гроцессора, р -количество портов регистрового файла, /'//* -время

;тения/записи в память, -время перехода между форматами КС.

Оптимизируемый участок кода задается графом зависимости по [анным (ГЗД) вида С = (/Л\ О), где /5-множество инструкций (вершин рафа), О -множество связей по данным между инструкциями (дуг рафа).

Текущее состояние процессора описывается содержимым реги-трового файла и форматом КС.

В терминах разработанной модели дано условие корректности юрмируемого КС и формула подсчета времени его исполнения.

Разработан метод совместного планирования загрузки ФУ и ре-истров, использующий предложенную модель и учитывающий архи-ектурные особенности процессоров с программным управлением ¡>У. Метод основан на использовании списочных расписаний. Для ;остижения большей эффективности планирования в разработанном 1етоде было предложено использовать интегральные приоритеты, от-юсительные веса которых могут быть найдены, например, с исполь-ованием генетического алгоритма. Возможность совместного плани-ования загрузки регистров и ФУ достигнута за счет добавления в )ормулу расчета приоритетов составляющей, учитывающей необхо-;имость и время загрузки/сохранения значений регистров процессора соответствии с очередным формируемым КС и текущим состоянием >егистрового файла.

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

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

Пусть имеется выражение Е = ейиОРи{"(",")"},с

операндами Б = {Г\,Ог, ...ДО, операциями ОР-{+-,*,/}, приоритетами операций рг(+) = рг{-) = 1, рг(*) = рг(Г) -2 и числом приоритетов Л(£) =| РЯ где РЯ = {/>/■(•*,): л'/ е ОР). Приведение такого выражения к бесскобочному виду состоит в изменении приоритетов операций в выражении для .V, еОР:рг^+ (№?[/']-№[/])*Л(£), где №[/], Л/с[/] - количество открывающих "(" и закрывающих ")" скобок слева от д-,. На втором этапе производится выделение пар операндов и выбор знака операции. За каждый просмотр выражения формируется один ярус дерева. Таким образом, количество просмотров выражения равно количеству ярусов в максимальной ярусно-параллельной форме (ЯПФ) представления ГЗД исходного выражения.

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

• операции вызовов внешних для оптимизируемой программы функций, которые не подлежат оптимизации;

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

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

• операции синхронизации по времени, так как они привязывают темп исполнения программы к фиксированным временным интервалам (оптимизация по времени теряет смысл);

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

• операции с памятью с вычисляемым адресом (невозможно проследить зависимости по данным на стадии трансляции).

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

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

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

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

Участок программы М описывается множеством ЛБ М = {ВЬВ2,...,В„},В1 =(/£/(0,л(0,/1(0,£)(0), где /</'}- идентификатор (номер) ЛБ; г^ - уровень вложенности циклов ЛБ; А^ = {аья2,...,а^} -

множество инструкций входящих в ЛБ; = - множест-

во идентификаторов ЛБ, к которым могут быть осуществлены переходы данного ЛБ.

К особенностям предлагаемой модели можно отнести:

• возможность представления как участков кода на ЯВУ, так и объектного кода;

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

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

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

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

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

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

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

Разработан и официально зарегистрирован в РОСПАТЕНТ учебно-исследовательский кросс-транслятор, ориентированный на генерацию параллельного объектного кода, который демонстрирует корректность и работоспособность предлагаемых моделей, методов и алгоритмов анализа и синтеза объектного кода. Кросс-транслятор обеспечивает компиляцию исходных программ с языка высокого уровня и генерацию необходимых моделей как макро- так и микроуровня. Подсистема генерации моделей, отражающих как глобальную структуру оптимизируемой программы, так и потенциальные возможности параллелизма на микроуровне, зарегистрирована в РосАПО.

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

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

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

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

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

3. Разработан метод разбора арифметических выражений, ориентированный на процессоры с программным управлением ФУ.

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

5. Разработаны методы, позволяющие повысить эффективность применения существующих алгоритмов оптимизации объектного кода по критерию времени для процессоров с программным управлением ФУ.

6. Разработаны и зарегистрированы в РосАПО и РОСПАТЕНТ инструментальные программные средства генерации и оптимизации параллельного объектного кода.

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

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

1. Скворцов C.B., Шувиков C.B. Синтез графовых моделей прикладных программ доя задач оптимизации объектного кода // Новые информационные технологии в научных исследованиях радиоэлектроники: Тез. докл. Всероссийской научно-технической конференции. Рязань, май 1997. Рязань: РГРТА, 1997,- С. 5-6.

2. Скворцов C.B., Шувиков C.B. Учебно-исследовательский компилятор, ориентированный на генерацию параллельного кода // Современные информационные системы в образовании: Тез. докл. 2-й Всероссийской конференции. Рязань, май 1998. Рязань: Ряз. обл. ин-т развития образования, 1998. С.114-116.

3. Скворцов C.B., Шувиков C.B. Разбор выражений для VLIW процессоров // Новые информационные технологии в радиоэлектронике: Тез. докл. Всероссийской конференции. Рязань, май 1998. Рязань: РГРТА, 1998. С.54-57.

4. Скворцов C.B., Шувиков C.B. Синтаксический разбор выражений для параллельного вычисления // Новые информационные технологии: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1998. С.69-74.

5. Свидетельство об официальной регистрации программы для ЭВМ N980385 (Россия). Программа генерации графовых моделей (ГенГраф) / Авторы Скворцов C.B., Шувиков C.B. Заявка N980253. Зарегистрировано в РосАПО 23.06.98.

6. Горюнов М.Е., Скворцов C.B., Шувиков C.B. Программные средства генерации графовых моделей прикладных программ // Новые информационные технологии в научных исследованиях и в образовании: Тез. докл. 4 Всероссийской конференции. Рязань, май 1999. Рязань: РГРТА, 1999. С.97-98.

7. Скворцов C.B., Шувиков C.B. Распараллеливание линейных участков программ для вычислительных систем с программным управлением на уровне функциональных устройств // Новые информационные технологии в научных исследованиях и в образовании: Тез. докл. 4 Всероссийской конференции. Рязань, май 1999. Рязань: РГРТА, 1999. С.87-89.

8. Корячко В.П., Скворцов C.B., Шувиков C.B. Генерация машинно - независимого кода для параллельного вычисления ариф-

метических выражений // Информационные технологии. 1999. № 3. С. 2-7.

9. Горюнов М.Е., Скворцов C.B., Шувиков C.B. Графовые модели генерации параллельного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Международный научно-технический семинар. Рязань, сентябрь 1999. Рязань: РГРТА, 1999. С.27-28.

10. Скворцов C.B., Шувиков C.B. Статическое предсказание переходов для компиляторов параллельного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Международный научно-технический семинар. Рязань, сентябрь 1999. Рязань: РГРТА, 1999. С.32-34.

11.Шувиков C.B. Исследование алгоритмов разбора выражений ориентированных на параллельное вычисление // Вычислительные машины комплексы и сети. Межвузовский сборник научных трудов. Рязань: РГРТА, 1999. С.59-61.

12. Шувиков C.B. Рациональная организация вычислительных систем коллективного пользования // Тез. докл. XXIX научно-методической конференции ВАИ. Рязань 1999. Рязань: ВАИ,

1999. С.87-89.

13. Свидетельство об официальной регистрации программы для ЭВМ N990663 (Россия). Учебно-исследовательский кросс-транслятор, ориентированный на генерацию параллельного объектного кода / Авторы Горюнов М.Е., Скворцов C.B., Шувиков C.B. Заявка N990545. Зарегистрировано в РОСПАТЕНТ 13.06.99.

14. Скворцов C.B., Шувиков C.B. Критерии корректности параллельных программ при оптимизации объектного кода // Новые информационные технологии. Межвузовский сборник научных трудов. Рязань: РГРТА, 2000. С.53-58.

15. Скворцов C.B., Шувиков C.B. Методы организации параллельных вычислений для процессоров с суперскалярной архитектурой // Тез. докл. XXX научно-методической конференции ВАИ. Рязань

2000. Рязань: ВАИ, 2000. С 8.

16. Шувиков C.B., Скворцов C.B. Генерация машинно-независимого кода для параллельного вычисления арифметических выражений // Научная сессия МИФИ-2000: Сборник научных трудов. В 13 томах. Т. 2. Информатика и процессы управления. Информационные технологии. Сетевые технологии и параллельные вычисления. М.: МИФИ, 2000. С.201-202.

17. Скворцов C.B., Шувиков C.B. Диаграма циклов и ветвлений // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Тез. доклада 9-й Международной конференции. Рязань, октябрь 2000. Рязань: РГРТА. С.20-23.

18. Шувиков C.B. Преобразование графа зависимостей по данным к виду леса бинарных деревьев // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Тез. доклада 9-й Международной конференции. Рязань, октябрь 2000. Рязань: РГРТА. С.27-28.

Шувиков Сергей Владимирович

МЕТОДЫ И АЛГОРИТМЫ РАСПАРАЛЛЕЛИВАНИЯ ОБЪЕКТНОГО КОДА ДЛЯ ПРОЦЕССОРОВ С ПРОГРАММНЫМ УПРАВЛЕНИЕМ ФУНКЦИОНАЛЬНЫМИ УСТРОЙСТВАМИ

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

Подписано в печать 30.10.00. Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1.0. Уч.-изд. л. 1.0 Тираж 70 экз. Заказ Бесплатно.

Рязанская государственная радиотехническая академия. 391000, г.Рязань, ул.Гагарина, 59/1. Отдел оперативной полиграфии Рязанского областного комитета статистики. 390013, г.Рязань, ул.Типанова, 4.

Введение

1 Анализ состояния проблемы оптимизации кода для процессоров с программным управлением параллелизмом

1.1 Системы генерации объектного кода.

1.2 Формальные методы, применяемые при распараллеливании программ.

1.2.1 Трансляция арифметических выражений.

1.2.2 Предсказание ветвлений.

1.2.3 Методы распараллеливания циклов.

1.2.4 Модели представления объектного кода.

1.2.5 Методы локальной оптимизации.

Выводы.\.

2 Оптимизация объектного кода по критерию времени

2.1 Модель вычислительной среды.

2.2 Планирование загрузки регистров и функциональных устройств.

2.2Л Загрузка функциональных устройств.

2.2.2 Загрузка регистров.

2.2.3 Комбинированный алгоритм

2.3 Разбор выражений.

2.4 Выбор доминирующей ветви.

Выводы

3 Средства повышения эффективности методов оптимизации объектного кода

3.1 Диаграмма циклов и ветвлений.

3.2 Модификация графа зависимости по данным.

Выводы.

4 Практическое использование и экспериментальное исследование результатов работы

4.1 Разбор арифметических выражений. Вычислительный эксперимент

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

4.3 Учебно-исследовательский транслятор.

4.3.1 Компилятор

4.3.2 Формирование моделей макроуровня.

4.3.3 Формирование моделей микроуровня

Выводы

За последние годы резко возросло число задач, требующих высокой скорости вычислений. Такие задачи возникают при обработке изображений, создании систем реального времени, разработке моделирующих систем. В решении подобных задач ключевую роль играет производительность микропроцессора целевой системы обработки данных (СОД) [17].

В настоящее время в области разработки архитектуры компьютерных систем существуют два основных пути повышения производительности микропроцессоров. Первым является повышение тактовой частоты, позволяющее исполнять больше операций за фиксированный промежуток времени. Вторым - использование параллелизма уровня инструкций (Instruction-Level Parallelism, ILP), представляющий собой набор аппаратных и программных технологий, позволяющих одновременно исполнять несколько машинных инструкций (процессоры с суперскалярной архитектурой) и таким образом получать каждый такт несколько результатов [88, 64]. Повышение тактовой частоты влечет за собой повышение тепловыделения, требует использования более совершенной технологии производства кристаллов и, как следствие, повышает процент брака.

Все разработки, использующие ILP, можно разделить на три группы по подходу к управлению параллелизмом [9, 10].

1. Аппаратный (динамический) параллелизм (DEC Alpha 21164, Power-PC 620, MIPS R10000, HP PA 8000). При этом подходе все действия по распараллеливанию программы выполняются в процессе ее выполнения с помощью микропрограмм, встроенных в процессор. Такой подход позволяет легко адаптировать имеющееся программное обеспечение к новому процессору. Но в связи с тем, что процессор включает в себя набор программ для распараллеливания, его структура усложняется, что щгечет за собой повышение стоимости разработки, снижение тактовой частоты. Динамический параллелизм допускает очень ограниченный предпросмотр и спекулятивное исполнение в пределах длины конвейера предвыборки инструкций. Это ведет к снижению уровня реально получаемого выигрыша в скорости выполнения. Так при возможности выполнения до четырех команд за такт синхронизации среднее число одновременно выполняемых команд не превышает двух [16, 18].

2. Программный (статический) параллелизм, т.е. управление по принципу VLIW (1860, iWarp, TïiMedia DSP, HP РА 9000, Эльбрус 3) допускает планирование выполнения программы на уровне отдельных функциональных устройств процессора и подразумевает, что распараллеливание происходит на этапе компиляции. Отличительными чертами процессоров, допускающих статический параллелизм, являются [9, 15, 78, 18]:

• фиксированное время исполнения команд;

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

• наличие большого количества функциональных устройств;

• увеличенный объем регистрового файла;

• высокая степень потенциального параллелизма.

3. Аппаратно-программный параллелизм (Ultra-SPARC, Pentium II, Pentium III,AMD K6-2, AMD K7), т.е. параллелизм на основе расширения системы команд VIS, ММХ, 3DNow!, ММХ2. Базовая система команд таких процессоров как правило представляет собой типичный суперскалярный процессор, принадлежащий к первой группе, но содержат дополнительные команды, реализующие выполнение параллельных операций над данными уменьшенной разрядности в режиме SIMD (Single Instruction Multiple Data) [16, 9, 2, 14, 33].

Актуальность темы. Основной проблемой при использовании языков высокого уровня (ЯВУ) для процессоров, допускающих программное управление параллелизмом (вторая и третья группы), является создание компиляторов, наиболее полно использующих потенциальные возможности процессоров. Например, применение технологий ММХ и 3DNow! в настоящее время возможно только при программировании на языке ассемблера [2]. В компании Sun ведется несколько исследовательских проектов, направленных на разработку компилятора, который бы автоматически включал VIS-команды в объектные программы, однако Sun этого пока не добилась [22].

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

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

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

1. Выполнить анализ существующих программных систем и методов, применяемых при трансляции и оптимизации программ, и оценить возможности их использования для систем с программным управлением ФУ процессора.

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

3. Разработать методы дополнительной оптимизации кода с целью максимального использования аппаратных ресурсов СОД на базе процессоров с управлением параллелизмом на уровне ФУ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные модели и методы организации параллельных вычислений на микро- и макроуровнях параллелизма, предложенные в диссертационной работе, реализованы в программных комплексах, официально зарегистрированных в Российском агенстве по правовой охране программ для ЭВМ, баз данных и топологий интегральных микросхем (РОСАПО) и Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ).

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

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

• Федеральное агенство правительственной связи и информации при Президенте Российской федерации, НТЦ "АТЛАС" (реализация криптографического алгоритма СА8Т-128 в рамках проекта создания системы передачи данных по открытым каналам связи);

• ГУП ОКБ "Спектр" при Рязанской государственной радиотехнической академии ( выбор технических решений програмных средств обработки высокоинформативных потоков телеметрической информации для системы РОКС).

Объем и структура диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения и списка литературы, изложенных на 114 стр., а также приложений на 51 стр.

Результаты работы использованы использованы в процессе проведения научно-исследовательской работы по теме "Рабочая станция разработчика мобильного программного обеспечения для параллельных вычислительных систем на основе современной элементной базы" (г.р. N 01200001955).

Основные положения диссертации опубликованы в работах автора [5, 6, И, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 34, 35, 36, 37].

Заключение

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

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

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

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

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

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

1. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П.Ершова. // М.: Наука, 1982. 336 с.2} Бердышев Е. Технология ММХ // М.: Диалог-МИФИ, 1998. 233 с.

2. Воеводин В.В. Математические модели и методы в параллельных процессах // М.: Наука, 1986. 296 с.

3. Головкин Б.А. Вычислительные системы с большим числом процессоров // М.: Радио и связь, 1995. 320 с.

4. Горюнов М.Е., Скворцов C.B., Шувиков C.B. Графовые модели генерации параллельного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Международный научно-технический семинар. Рязань: РГРТА, 1999. С.27-28.

5. Григорьев B.JI. Микропроцессор i486. Архитектура и программирование // М.: ГРАНАЛ, 1993. 346 с.

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

7. Корнеев В.В., Киселев A.B. Современные микропроцессоры //М.: Но-лидж, 1998. 240 с.

8. Корячко В.П,, Скворцов C.B., Телков И,А. Архитектуры многопроцессорных систем и параллельные вычисления: Учебное пособие // М.: Высшая школа, 1999. 235 с.

9. Корячко В.П., Скворцов С.В., Шувиков С.В. Генерация машинно -независимого кода для параллельного вычисления арифметических выражений // Информационные технологии. 1999. 3. С.2-7.

10. Миренков Н.Н. Структурное параллельное программирование // М.: Программирование. 1975. 3. С.3-14.

11. Многопроцессорные ЭВМ и методы их проектирования / Б.А.Вабаян, А.В.Бочаров, В.С.Волин и др. // М.: Высшая школа, 1990. 143 с.

12. Набор команд процессоров Alpha пополняется новыми мультимедиа инструкциями // Computer Week-Moscow. 1996. 30.

13. Назаров JI. Н. Многопроцессорные вычислительные комплексы "Эльбрус" // Проблемы информатизации. 1997. 1,2. С.33-37.

14. Петрова Ю. RISC-процессоры третьего поколения. // Computer Week-Moscow. 1995. 22, 23.

15. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. // М.: Энергатомиздат, 1983. 312 с.

16. Процессоры TriMedia с архитектурой VLIW. // Computer Week-Moscow. 1996. 25.

17. Распараллеливание алгоритмов обработки информации. Том 1 / под ред. А.Н. Свенсона. // Киев: Наук. Думка, 1985. 280 с.

18. Свидетельство об официальной регистрации программы для ЭВМ N 980385 (Россия). Программа генерации графовых моделей (ГенГраф) / Авторы Скворцов С.В., Шувиков С.В. Заявка N980253. Зарегистрировано в РосАПО 23.06.98.

19. Свидетельство об официальной регистрации программы для ЭВМ N990663 (Россия). Учебно-исследовательский кросс-транслятор, ориентированный на генерацию объектного кода / Авторы Горюнов М.Е.,

20. Скворцов С.В., Шувиков С.В. Заявка N990545. Зарегистрировано в РОСПАТЕНТ 13.06.99.

21. Системы команд процессоров пополняются мультимедиа инструкциями // Computer Week-Moscow. 1996. 32.

22. Скворцов С.В., Шувиков С.В. Разбор выражений для VLIW процессоров // Новые информационные технологии в радиоэлектронике: Тез. докл. Всероссийской конференции. Рязань, май 1998. Рязань: РГРТА,1998. С.54-57 .

23. Скворцов С.В., Шувиков С.В. Синтаксический разбор выражений для параллельного вычисления // Новые информационные технологии: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1998. С.69-74.

24. Скворцов С.В., Шувиков С.В. Статическое предсказание переходов для компиляторов параллельного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Международный научно-технический семинар. Рязань: РГРТА, 1999. С.32-34.

25. Скворцов С.В., Шувиков С.В. Критерии корректности объектных программ при оптимизации объектного кода / / Новые информационные технологии: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 2000. С.53-58.

26. Скворцов С.В., Шувиков С.В. Методы организации параллельных вычислений для процессоров с суперскалярной архитектурой // Тез. докл. XXX научно-методической конференции ВАИ. Рязань, 2000. Рязань: ВАИ, 2000. С.8.

27. Скворцов С.В., Шувиков С.В. Диаграма циклов и ветвлений // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Тез. докл. 9-й Международной конференции. Рязань, октябрь 2000. Рязань: РГРТА, 2000. С.20-23.

28. Ферранте Дж., Оттенштейн К., Уоррен Дж. Граф програмных зависимостей и его применение в оптимизации // Векторизация программ: теория, методы, реализация. М.: Мир, 1991. С.141-182.

29. Шнитман В. Архитектура процессоров UltraSPARC // Открытые системы. 1996. 2. С.5-13.

30. Шувиков С.В. Исследование алгоритмов разбора выражений ориентированных на параллельное вычисление // Вычислительные машины комплексы и сети: Межвуз. сб. / Рязан. гос. радиотехн. акад. Рязань, 1999. С.59-61.

31. Шувиков С.В. Рациональная организация вычислительных систем коллективного пользования // Тез. докл. XXIX научно-методической конференции ВАИ. Рязань, 1999. Рязань: ВАИ, 1999. С.87-89.

32. Aditya S., Kathail V., Ramakrishna Ran В. Elcor's Machine Description System: Version 3.0 // Hewlett-Packard Laboratory. Oct. 1998. 77 p.

33. Aho A., Sethi R., Ulman J. Compilers: Principles, Techniques, and Tools // Addison-Wesley, Reading, MA. 1986.

34. Aiken A., Nicolau A. Perfect Pipelining: A new Loop Parallelization Technique // Proc. of the 1988 European Symp. on Programing, Mar. 1988.

35. Aiken A., Nicolau A. Optimal loop parallelization // Proc. of the ACM SIGPLAN Conference on Progaming Language Design and Implementation, 1988. P.308-317.

36. Baer J.L., Bovet D.P. Compilation of arithmetic expressions for parallel computations // Proc. IFIP Congr., 1968. Amsterdam: North-Holland Publ. Co., 1968. P.340-346.

37. Baer J.L. A survey of some theoretical aspects of multiprocessing // Computing Surveys, 1973. 1. P.31-80.

38. Ball Т., Larus J.R. Branch prediction for free // Proc. of the ACM SIGPLAN Conference on Progaming Language Design and Implementation, June 1993. P.300-313.

39. Beaty S.J., Colcord S., Sweany P.H. Using Genetic Algorithms to Fine-Tune Instruction-Sheduling Heuristics. // Tech. Report, Univ. of Michigan, 1998. 14 p.

40. Bodik R., Gupta R. Array Data Flow Analysis in Load-Store Optimizations in Superscalar Architectures//Dept. of Computer Science, University of Pittsburgh, 1995. 17 p.

41. Bodin F., Charot F. Loop optimization for Horizontal Microcoded Machines // Proc. Int. Conf. of Supercomputing, Jun. 1990. P.164-176.

42. Briggs P., Cooper K.D., Kennedy K.? Torczon L. Coloring Heuristics for Register Allocation // Conf. of Prog. Lang. Design and Implementation, Portland, Oregon, June 1989. P.275-284.

43. Carr S., Lehoucq R.B. Compiler Blockability of Dense Matrix Factorizations //Dept. of Computer Science, Michigan Technological University, Oct. 1996. 21 p.

44. Chaitin G.J., Auslander M.A., Coke J., Hopkins M.E., Markstein P.W. Register allocation via coloring // Computer Lang., 1981. 6.

45. Chaitin G.J. Register allocating and spilling via graph coloring // Proc. of the ACM SIGPLAN 82, Symposium on Compiler Construction, June 1982. P.201-207.

46. Chang P.P., Hwu W-M.W. Control Flow Optimization for Supercomputer Scalar Processing // Center for Reliable and High Performance Computing, University of Illinois, 1989. 8 p.

47. Chao L-F., LaPaugh A. Scheduling Cyclic Data-Flow Graphs by Retimingwith Resource Constraints // Sixth Int. Workshop on HLS., Nov. 1992. P.111-134.

48. Compiler/Architecture Interaction in a Tree-Based VLIW processor / Moudgill M., Moreno J.H., Ebcioglu K., Altman E., Chen S.K., Polyak A. // IBM Research Division, Apr. 1996. 11 p.

49. Crowford J.H. The i486 CPU: Executing instructions per one clock cycle // IEEE Micro., Feb. 1990. P. 27-36.

50. Cytron R. Compiler-Time Scheduling and Optimization for Asyncronous Machines // Ph.D. thesis University of Illinois, 1984. 240 p.

51. Danelutto M. A Massively Parallel Architecture Using VLIW for Fine Grain Parallelism Exploitation // Ph.Thesis, University of Pizza, Mar. 1990. 226 p.

52. Danelutto M., Orlando S., Pelagatti S., Vanesschi M. Parallel programming models based on the restricted computation structure approach // Dept. of Informatica, University of Pizza, 1991. 54 p.

53. Dasgupta S., Tartar J. The identification of maximal parallelism in straight-line microprograms // IEEE Trans. Comp., 1976. V.C-25. N10. P.986-991.

54. DeWitt D. A Machine-Independent approach to the prodaction of Optimal Horizontal Microcode // Ph.D. Thesis, Univ. of Michigan, Ann Abor, MI, 1976, 254 p.

55. Edmonson J.H., Rubinfeld P., Preston R., Rajagopalan V. Superscalar instruction execution in the 21164 Alpha microprocessor // IEEE Micro., April 1995. P.33-43.

56. Effective Compiler Support for Predicated Execution Using the Hyperblock / Mahike S.A., Lin D.C., Chen W.Y., Hank R.E., Bringmann R.A. // Center for Reliable and High Performance Computing, University of Illinois, 1992. 10 p.

57. Ertl M.A., Krall A. Optimal Instruction Scheduling using Constraint Logic Programming // Programming Language Implementation and Logic Programming, 1991. 12 p.

58. Fernandes M.M., Llosa J., Topham N. Extending a VLIW Architecture Model. // CSG Report Series. Department of Computer Science University of Edinburgh., Dec. 1997. 22 p.

59. Fischer C.N., LeBlanc jr R.J. Crafting A Compiler With C // The Benjamin/Cummings Publishing Company, 1991. 812 p.

60. Fisher J.A. Trace Scheduling: A Technique for Global Microcode Compaction // IEEE Trans, on Comp., C-30. N7. Jul. 1981.

61. Forsyth M., Mangelsdorf S., DeLano E., Gleason C., Yetter J. CMOS PA-RISC processor for a new family of workstations // Proceedings of IEEE COMPCON, Feb. 1991. P.202-207.

62. Garey M.R., Johnson D.S. Computers and Intractability: The Guide of the Theory of NP-Completeness // W.H.Freeman and Co. San Francisco, CA, 1979.

63. Girczyc E.F. Loop Winding A data flow approach to Functional Pipelining // Proc. of IEEE ISCAS, May 1987. P.382-385.

64. Goosens G., Wandewalle J., DeMan H. Loop Optimization in Register Transfer Scheduling for DSP systems // IEEE Design Aut. Conf., 1989. P.826-831.

65. Hank R.E., Mahlke S.A., etc. Superblock formation using static program analisys / / Center for Relable and High Performance Computing, University of Illinois, 1993. 9 p.

66. Hellerman H. Parallel proccesing of Algebraic Expressions // IEEE Trans, on Comp. EC-15. N 1. Jun. 1966. P.82-91.

67. Hwang C.-T., Hsu Y.-C., Lin Y.-L. Scheduling for Functional Pipelining and Loop Winding // 20th ACM/IEEE Design Automation Conference, Jun. 1991. P.764-769.

68. Hwu W.-M.W., Hank R.E., etc. Compiler Technology for Future Microprocessors / / Center for Reliable and High Performance Computing, University of Illinois, 1995. 52 p.

69. Lam M. Software Pipelining: An Effective scheduling technique for VLIW machines // Proc. of SIGPLAN, Jun. 1988. P.318-328.

70. Lee J.K.F., Smith A.J. Branch prediction strategies and branch target buffer disign // IEEE Computer, Jun. 1984.

71. Local Microcode Compaction Techniques / Landskov D., Davidson S., Shriver B., Mallet P.V. // ACM Comput. 1980. V.12. 3. P.261-294.

72. Margulis N. The Intel 80860 // Byte. Dec. 1989. P.333-339.

73. Moreno J.H., Moudgill M. Scalable instruction-level parallelism through tree-instructions // IBM Research Division, Dec. 1996. 14 p.

74. Nicolau A. Uniform Parallelism Exploitation in Ordinary Programs // Proc. of ICPP, Aug. 1985.

75. Padua D.A., Kuck D.J., Lawrie D.H. High-speed multiprocessors and compilation technicues // IEEE Tran. Comput., Sept. 1980. C-29. P.763-776.

76. Park N., Parker A.C. Sehwa: A software package for synthesis of pipelines from behavioral specifications // IEEE Trans, on Computer-Aided design, Mar. 1988. P.356-370.

77. Paulin P.G., Knight J.P. Force-Directed Scheduling for the behavioral synthesis of ASIC's // IEEE Trans, on Computer-Aided design, Jun. 1989. P.661-679.

78. Percolation based synthesis / Potasman R., Lis J., Nicolau A., Gajski D. // 27th ACM/IEEE Design Automation Conference, 1990. P.444-449.

79. Pieper K.L. Parallelizing Compilers: Implementation and Effectiveness // AT&T GRPW, 1993. 167 p.

80. Rau R., Fisher J. Instruction-level parallel processing: History, overview and perspective. //The Journal of Supercomputing, May 1993. P.9-50.

81. Sanchez F., Cortadella J. A Novel Approach for Resource-Constrained Loop Pipelining // Universität Politecnica de Catalunya, Barselona, Spain, May 1993. 46 p.

82. Smith J.S. A study of branch prediction strategies // Proceedings of International Symposium on Computer Architecture, May 1981. P.135-148.

83. Squir I. S. A translation algorithm for a multiple Processor Computer // Proc. 18th ACM Nat. Conf. Colorado: Denver, 1963. P.174^191.

84. Stone. One-pass compilation of arithmetic expressions for a parallel processor // Communic. ACM, 1967. 10. N4. P.215-223.

85. Wayner P. SPARC strikes back // Byte. 19. Nov. 1994. P.105-112.