Исследование разреженной модели базовых блоков для оптимизации потока команд вычислительного конвейера тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Довгалюк, Павел Михайлович

• Довгалюк, Павел Михайлович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Довгалюк, Павел Михайлович

Введение

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).

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Довгалюк, Павел Михайлович, 2007 год

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.