Методы и алгоритмы распараллеливания объектного кода для процессоров с программным управлением функциональными устройствами тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Шувиков, Сергей Владимирович

• Шувиков, Сергей Владимирович
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Шувиков, Сергей Владимирович

Введение

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. Разработан метод преобразования графа зависимости по данным к виду дерева минимизирующий число дополнительно используемых регистров.

Список литературы диссертационного исследования кандидат технических наук Шувиков, Сергей Владимирович, 2000 год

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.