Компонентный подход к построению оптимизирующих компиляторов тема диссертации и автореферата по ВАК РФ 05.13.11, доктор технических наук Дроздов, Александр Юльевич

• Дроздов, Александр Юльевич
• доктор технических наук
• 2010

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Дроздов, Александр Юльевич

5.4 Выводы

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

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

Основными результатами данной главы является авто-распараллеливатель программ, созданный на основе компонентного подхода к построению оптимизирующих компиляторов и полномасштабный оптимизирующий компилятор для архитектуры «Эльбрус-ЗМ» ([4-6]). Компонентная технология позволила встроить авто-распараллеливатель в состав технологии gcc, а также позволяет встраиваться в любую технологическую цепочку компиляции.

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

Несмотря на ограничения в использовании автоматического распараллеливания, существует целый ряд реальных приложений, на которых удается добиться заметного улучшения производительности. Наиболее благоприятные условия для автоматического распараллеливания существуют в фортрановских задачах (410.bwaves, 436.cactusADM, 437.1eslie3d, 459.GemsFDTD, задачи пакета NPB), в силу специфики алгоритмов, реализуемых на этом языке. В тоже время две задачи (462.1ibquantum, 470.1bm), написанные на языке С, так же удалось распараллелить.

Следует отметить важность использования межпроцедурного анализа, позволившего распараллелить две задачи (470.1bm и 462.1ibquantum) из шести.

В среднем АР, встроенный в GCC, показ ал, лучшие результаты распараллеливания как на задачах пакета Spec2006, так и на задачах пакета NPB на архитектурах фирм Intel (х86, IA64) и IBM (PowerPC)

Автоматический распараллеливатель, встроенный в GCC показал свое превосходство над одним из лучших на сегодняший день автоматических распараллеливаетелей — компилятором компании Intel - icc.

Компилятор общего назначения для архитектуры «Эльбрус-ЗМ» ([4-6]) позволил вычислительному комплексу, построенному на базе этой архитектуры реализовать заложенный в него потенциал и достичь требований производительности, которые поставил перед разработчиками заказчик.

6 Заключение

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

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

1. Разработаны или существенно улучшены алгоритмические основы компонент оптимизирующих компиляторов: 1.1. Статический анализ программ

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

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

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

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

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

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

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

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

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

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

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

Предложен алгоритм решения задачи межпроцедурной нумерации значений.

2. Глобальное планирование программе

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

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

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

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

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

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

4. Разработана методология»портирования блоков* оптимизирующей компиляции в состав любой существующей технологической цепочки. Это позволяет, использую блочную технологию, достраивать и улучшать любой оптимизирующий компилятор без необходимости его полного редизайна. Технология была успешно использована в процессе портирования автоматического распараллеливания в контекст GCC.

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

Все представленные в диссертационной работе алгоритмы, и методы, реализованы^ в составе оптимизирующего компилятора с языков высокого уровня С, С++, F77 для архитектуры «Эльбрус-ЗМ» и? составляют основу оптимизирующей части этого компилятора. На основе предложенной блочной технологии построения оптимизирующих компиляторов были созданы анализатор программ и автоматический распараллеливатель программ для архитектур х86 (Intel, AMD), Itanium (Intel), Power PC, Power Cell. Автоматические распараллеливатели были построены на основе совместного использования компонентной технологии построения оптимизирующих компиляторов и технологии GCC.

Список литературы диссертационного исследования доктор технических наук Дроздов, Александр Юльевич, 2010 год

1. M. S. Schlansker, B. R. Rau. EPIC: An Architecture for Instruction-Level Parallel Processors: Technical Report HPL-1999-111 / Compiler and Architecture Research Hewlett-Packard Laboratories, Palo Alto, February 2000. 80 p.

2. Boris Babayan. E2K Technology and Implementation. // in Proceedings of the Euro-Par 2000 Parallel Processing: 6th International. - Volume 1900 / 2000. -January, 2000.-P. 18-21.

3. M. Кузьминский. Отечественные микропроцессоры: Elbrus E2K // Открытые системы, № 05-06, 1999. С. 8-13.

4. К. Dieffendorf. The Russians Are Coming. Supercomputer Maker Elbrus Seeks to Join x86/IA-64 Melee // Microprocessor Report, V.13, №.2. February 15, 1999. P. 1-7.7. http•//open.specbench.org/cpu928. http://open.specbench org/cpu95

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

6. В.В. Воеводин, Вл. В. Воеводин, Параллельные вычисления. Санкт-Петербург «БХВ-Петербург», 2002.

7. Alfreds V. Aho, Ravi» Sethi, Jeffrey D. UHman, "Compilers. Principles, Techniques, and Tools", Addison-Wesley, Reading, 1986.

8. John R. Ellis. Bulldog: A compiler for VLIW Architectures. MIT Press, 1985

9. Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs and Koen G. Langendoen, Modern Compiler Design, by John Wiley & Sons,Ltd, 2000.

10. Randy Allen, Ken Kennedy, Optimizing Compilers for Modern Architectures. 2002 by Academic Press.

11. Steven S. Muchnick, "Advanced Compiler Design and Implementation", Morgan Kauffman, San Francisco, 1997.

12. Utpal Banerjee, Loop Transformations for Restructuring Compilers. Kluwer academic Publishers, 1993.

13. Utpal Banerjee. Dependence Analysis. Kluwer Acadmic Publishers. 1997

14. Miling Girkar, Constantine D.PolychronopouIos. "Extracting Task-Level Parallelism" ACM, July 1995.

15. Stephen Alstrup, Dov Harel, Peter W.Lauridsen, Mikkel Thorup, Dominators in Linear Time. Department of Computer Science, University of Copenhagen, 1985.

16. G. Ramalingam, On Loops, Dominators, and Dominance Frontier. PLDI 2000, Vancouver, Canada.

17. Vugranam C. Sreedhar, Yong-fong Lee, Guang R.Gao. DJ-Graphs and Their Applications to Flowgraph Analyses. ACAPS Tchnical Memo 70, May 11,1994.

18. Vugranam C. S. Sreedhar, Guang R.Gao. Computing phi-nodes in Linear Time Using DJ-graphs. ACAPS Tchnical Memo 75, January 18, 1994.

19. Keshav Pingali, Gianfranco Bilardi, Optimal Control Dependence Computation and the Roman Chariots Problem. ACM, 1997.

20. Richard* Johnson and Michael Schlansker, "Analysis Techniques for Predicated Code", In Proc. Of the 29th Annual Int'l Symp. On Microarchitecture, December 1996.

21. Fohn W. Sias, Wen-mei W. Hwu; David I. August: Accurate and Efficient Predicate Analysis with Binary Decision Diagrams. Proceedings of the 22rd Annual ACM/IEEE Internationsl Symposium on Microarchitecture, December 2000.

22. Nancy Ji.Warter,.Scott A. Mahlke, Wcn-meiW.Hwu, B. Ramakrishna Rau. Reverse If- Conversion. ACM-SIGPLAN-LDI-6/93/Albuquerque, N.M.

23. Maryam Emami- "A practical interprocedural alias analysis for optimizing/parallelizing C compiler". Master's thesis, School of Computer Science, McGill University, August 1993.

24. P.' Cousot, R. Gousot, "Abstract interpretation framework". Journal of logic and Computation, 2(4) 511-547, August 1992.

25. Eric James • Stoltz, Intermediate Compiler Analysis via. reference Chaining. Portland State University, Thesis, January 1995.

26. William-Bluine, Rudolf Eigenmann: Symbolic Range Propagation. University of Illinois at Urbana-Champaign, September 20,1994.

27. Williams Blume, Rudolf Eigenmann. Demand-driven, Symbolic Range . Propagation. University of Illinois at Urbana-Champaign.

28. Loren5 Taylor. Simson, Value-Driven Redundancy Elimination, Thesis, Rice University, Houston, Texas, April, 1996.

29. Pend Tu, David Padua. Efficient Building and Placing of Gating Functions -Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaingn, 1995.

30. Kwangkeun Yi andWilliams Ludwell Harrison III, Interprocedural Data Flow Analysis for Compile-time Memory Management. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

31. Evelyn* Duestenvald, Rajiv Gupta, Mary Lou Soffa; Demand-driven Computation of Interprocedural Data Flow. Department of Computer Science, University of Pittsburg, POPL'95 1/95 San Francisco, CA USA.

32. Evelyn Duesterwald, Rajiv Gupta, and Mary Lou Soffa, A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis. University of Pittsburg, ASM SISPLAN-SIGACT Symposium on Principles of Programming Languages, 1995.

33. Susan Horwitz, Thomas Reps, and Mooly Sagiv, Demand Interprocedural Dataflow Analysis. University of Wisconsin, Proceedings of the Third ASM SIGSOFT Symposium on Foundations of Software Engineering, Washington DC, October 10-13, 1995.

34. David.R.Chase, Mark Wegman, F.Kenneth Zadeck, Analysis of Pointers and Structures. ASM SIGPLAN'90 PLDI, June 20-22,1990.

35. Yuan-Shin Hwang, Joel Saltz, Compile-Time Analysis on Programs with Dynamic Pointer-Linked Data Structures. Depatment of Computer Science, University of Maryland, Nobember 8, 1996.

36. Xinan Tang, Rakesh Ghiya, Laurie J: Hendren, Guang R.Gao, Heap Analysis and Optimizations for Threaded Programs. School of Computing Science, McGill University, 1997.

37. Rakesh Ghiya, Practical Techniques for Interprocedural Heap Analysis. School of Computing Science, McGill University, Montreal, January 1996.

38. Keith* D.Cooper, Ken Kennedy, Fast Interprocedural Alias Analysis. Rice University, 1989.

39. Bjarne Steensgaard, Points-to Analysis in Almost Linear Time, Microsoft Research, 1996.

40. Keith3 D.Cooper, Ken Kennedy, Interprocedural Side-Effect Analysis in Linear Time. Rice University, 1988.

41. Robert P.Wilson, Monika S.Lam. Efficient context-sensitive pointer analysis for С programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language and Implementation, pages 1-12, June 1995.

42. Kleanthis Psarris and Konstantinos Kyriakopoulos, Data Dependence Testing in Practice. Division of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249.

43. Paul M.Petersen and David A.Padua, Experimental Evaluation of Some Data Dependence Tests (Extended Abstract), Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

44. Paul M.Petersen, David A.Padua, Static and Dynamic Evaluation of Data Dependence Analysis. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

45. Keshav Pingali, Micah Beck, Richard« Johnson, Mayan Moudgill, Paul Stodghill, Dependence Flow Graph: An Algebraic Approach to Program Dependencies. Department of Computer Science, Cornell University, Ithaca, NY 14853.

46. Jay Hoeflinger, Run-Time Dependence Testing by Integer Sequence Analysis. Center for Supercomputing Research & Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

47. Paul M.Petersen, David A.Padua, Dynamic Dependence Analysis: A Novel Method for Data Dependence Evaluation. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801-2932.

48. Sreedhar, Vugranam C. and Gao, Guang R. A linear time algorithm for placing cp-nodes // Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, California, January 1995. Pp. 62-73.

49. Дроздов А.Ю., Новиков C.B. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

50. Bilardi G., Pingali К. The Static Single Assignment Form and its Computation -Cornell University Technical Report, July, 1999.

51. Tarjan, Robert E. Depth first search and linear graph algorithms // SIAM Journal on Computing, 1(2), June 1972. Pp. 146-160.

52. Ronaldf Cytron, Jean Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth^Zadeck, "Efficiently Computing Static Single Assignment Form and the Program Dependence Graph", ACM TOPLAS, Vol. 13, No. 4, Oct. 1991, pp. 451490.

53. Thomas Lengauer, Robert Tarjan, "A Fast Algorithm for Finding Dominators in a Flowgraph", ACM TOPLAS, Vol. 1, No. 1, July 1979, pp. 121-141.

54. Боханко A.C., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

55. Боханко А.С., Дроздов А.Ю. Оптимизация «Расширенное удаление излишних операций чтения из памяти» // В трудах Международной молодежной научной конференции «XXX Гагаринские чтения», Москва, 2004.

56. David II August, Wen-mei W. Hwu, and Scott A. Mahlke. A Framework for Balancing Control Flow and Predication // Proceedings of the 30th annual IEEE/ACM International Symposium on Microarchitecture. December, 1997. P. 92-103.

57. Joseph- С. H. Park; Mike Schlansker. On Predicated Execution Software and System Laboratory HPL-91-58, May, 1991.

58. L. Garter, B. Simon, B. Calder, L. Carter, and J. Ferrante, "Predicated single static assignment ", in Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, October 1999.

59. J.R; Allen, K. Kennedy, C. Porterfield, J. Warren. Conversion of control dependences to data dependences, Conf. Record of POPL-IO, 1983.

60. Joseph A. Fisher. Trace Scheduling: A technique for global microcode compaction //Transactions on Computers, IEEE. July, 1981. V. C-30. P. 478-490.

61. S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, and R. A. Bringmann. Effective Compiler Support for Predicated Execution Using the Hyperblock. // in Proceedings of the 25th International Symposium on Microarchitecture. December, 1992. P. 45-54.

62. Дроздов А.Ю., Новиков C.B. Методы совместного планирования путей программы, предлагаемые для использования в современных оптимизирующих компиляторах. "Сборник тезисов XXI научно-технической конфренции войсковой части 03425" Москва, в/ч 03425,2003г.

63. Sebastian Winkel, "Optimal versus Heuristic Global Code Scheduling," micro, pp.43-55, 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2007), 2007

64. John? Wollenburg, "Condition awareness support for predicate analysis optimization", University of Illinois, 1997.

65. R.E. Bryant. Symbolic Boolean manipulation with ordered binary decision diagrams Technical Report CMU-CS-92-160, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, October 1992.

66. J. Ferrante, K. J. Ottenstein, and J.D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.

67. Le-ChumWu, Wen-mei W. Hwu. A New Data-Location Tracking Scheme for the Recovery of Expected Variables Values. Technical Report IMPACT-98-07.

68. Le-Ghun Wu, Rajiv Mirani, HarishPatil, Bruce Olsen, Wen-mei W. Hwu: A New Framework for Debugging Globally Optimized Code. ACM SIGPLAN Conference on Programming Language Design and Implementation, Atlanta, Georgia, May 1-4, 1999.

69. R: Gupta, "Debugging code reorganized by a trace scheduling compiler", Structred Programming, vol. 11, pp. 141-150, July 1990.

70. Боханко A.C., Дроздов А;Ю., Корнев P.M. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004 г.

71. Vadim Maslov, "Delinearisation: an Efficient Way to Break Multiloop Dependence Equations", Proceedings of PLDI'92, ACM, 1992.

72. Г. П. Кюнци, В. Крелле, "Нелинейное программирование", Москва, Советское Радио, 1965.

73. Дроздов А.КК, Степаненков A.M. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10,2004 г.

74. М. Wolfe, С. W. Tseng, "The Power test for data dependence", IEEE Transaction on Parallel and Distributed Systems, Vol. 3, No. 5, pp. 591-601, September 1992.

75. W. Pugh, "A practical algorithm for exact array dependence analysis", Communication of the ACM, 35(8):102-114, August 1992.

76. K. Psarris, K. Kyriakopoulos, "Data Dependence Testing in Practice", IEEE International Conference on Parallel Architectures and Compiler Techniques, October 12-16, 1999, California.

77. Brian R. Murphy, Monica S. Lam "Program Analysis with Partial Transfer Function", Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, January, 1999

78. Marc Shapiro, Susan Horwitz "Fast and Flow-Insensitive Points-To Analysis". Proceedings of 24th ACM SIGPLAN-SIGACT symposium of programming language, pp.1-14, Paris, France, January (1997).

79. Mooly Sagiv, Thomas Preps, Susan Horwotz "Precise Dataflow Analysis with Applications Constant Propagation". TAPSOFT 1995. pages 651-665.

80. Дроздов А.Ю., Владислав л ев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская

81. Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

82. R'. Wilson. "Efficient, context-sensitive pointer analysis for С programs". Phd thesis, Stanford University, 1997.

83. Laure J: Hendren, Marian- Emami, Rakesh Chiya, Clark» Verbrugge. "A Practical Context-Sensitizes Interprocedural Analysis Framework For С Compilers". ACAPS Technical Memo 72, 24 July 1993.

84. M. Hind'and» A. Pioli. "Assessing the effects of flow-sensitivity on pointer alias analyses". Lecture Notes in Computer Science, 1503, pages 57-81. Springer-Verlag, 1998.

85. Babayan B. A*. E2k Technology and Implementation. // Proceedings of the Euro-Par 2000 Parallel Processing: 6th International. - V. 1900/2000. - January, 2000. -P. 18-21.

86. Timothy G. Mattson,.Beverly A. Sanders, Berna L. Massingill. Patterns for Parallel Programming. Addison-Wesley, 2005.

87. ЗАО МЦСТ. Официальный сайт http://www.mcst.ru.

88. Simpson, Loren Taylor. Value-Driven Redundancy Elimination. Ph.D. Thesis, Rice University, Houston, Texas, 1996.

89. Wilson; Robert* Paul/ Efficient, Context-Sensitive Pointer Analysis For С Programs. Ph.D. Thesis, Stanford University, 1997.

90. J R. Ellis, "Bulldog: A Compiler for VLIW "Architectures", Doctoral Dissertation, , MIT Press Cambridge MA 1985.

91. D.F. Bacon, S. L. Graham, O.J. Sharp, "Compiler Transformations for HighPerformance Computing", ACM Computing Surveys, Vol. 26, No 4, December 1994.

92. Clifford^ N. Click, "Combining Analyses, Combining Optimizations", A thesis submitted in partial fulfillment of the requiiements for the degree Doctor of Philosophy. Houston, Texas, February 1995.

93. Intel1 Itaniunb2 Processor Reference Manual for Software Development and Optimization, Document Number: 25 111 0-001, June 2002. 179 p.

94. Y. N. Srikant, P. Shankar, "The compiler design handbook: optimizations and machine code generation", CRC PRESS, Boca Raton, 2003.

95. В; Ю.! Волконский, "Оптимизирующие компиляторы для архитектуры с явным параллелизмом команд и аппаратной поддержкой двоичной совместимости", Информационные технологии и вычислительные системы, №3,2004.

96. R. P. Colwell, R. P. Nix, J. J. O'Donnel, D. В. Papworth, P. K.,Rodman. A

97. VLIW Architecture for a Trace Scheduling Compiler // in Proceedings of the second International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS II). SIGPLAN Notices, V. 22, №10. -October, 1987,- P. 180-192.

98. Joseph A. Fisher. Very Long Instruction Word Architectures and the ELI-512 // in Proceedings of 10th International Symposium on Computer Architectures, IEEE. -June, 1983.-P. 140-150.

99. Joseph A. Fisher and John J. O'Donnel. VLIW Machines: Multiprocessors We Can Actually Program // CompCon 84'Proceedings, IEEE. February ,1984. - P. 299-305.

100. Randy Allen, Ken Kennedy. Optimizing Compilers for Modern Architectures // by Academic Press, 2002

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

102. W. A. Havanki, S. Banerjia, and T. MJ Conte. Treegion scheduling for wide-issue processors // Proceedings of the 4th International Symposium on HighPerformance Computer Architecture (HPCA-4), February 1998.

103. A. Nicolau. Uniform parallelism exploitation in ordinary programs // In ICPP, 1985.

104. Santosh.G. Abraham; Vinod Kathail, Brian» L. Deitrich: Meld Scheduling: Relaxing Scheduling Condtraints across Region Boundaries // Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, pp. 308321, 1996

105. B. R. Rau. Iterative modulo scheduling: An algorithm for software pipelining loops // In Proceedings of the 27th International Symposium on Microarchitecture, pp. 63-74, December 1994.

106. B. R. Rau> and J. A. Fisher. Instruction-level parallel processing: History, overview, and perspective // The Journal of Supercomputing, 7(l):9-50, January 1993.

107. Jay Bharadwaj, Kishore Menezes, Chris McKinsey. Wavefront scheduling: path based data representation and scheduling of subgraphs // Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, pp. 262271, 1999

108. Дроздов» А. Ю., Новиков С. В., Шилов В. Bi Эффективный алгоритм преобразования потока управления в поток данных // Информационные технологии. № 2. 2005. Приложение. С. 24-31.

109. Дроздов А. Ю., Новиков С. В. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии. № 3. 2005.

110. John Wollenburg. Condition awareness support for predicate analysis optimization // University of Illinois, 1997.

111. Волконский В. Ю., Окунев С. К. Оптимизации критического пути на предикатном представлении программы // Информационные технологии. № 9. 2003.С. 2-13.

112. Babaian, S. К. Okunev, V. Y. Volkonsky. Critical path optimization -unzipping: United States Patent 6,564,372 // B. A. Appl. No.: 504630; Filed: February 15,2000; Pub.: May 13,2003. 4 p.

113. Bi A. Babaian, S. K. Okunev, V. Y. Volkonsky. Method for removing dependent store-load pair from critical path: United States Patent 6,516,463 // Appl. No.: 771482; Filed: January 25, 2001; Pub.: February 4, 2003. 6 p.

114. В. A'. Babaian, S. К. Okunev, V. Y. Volkonsky. Critical path optimization -optimizing branch operation insertion: United States Patent 6,526,573 // Appl. No.: 505653; Filed: February 17,2000; Pub.: February 25, 2003 . 9 p.

115. P: P. Chang, S. A. Mahlke and« W. W. Hwu. Using profile information to assist classic compiler code optimizations // Software Practice and Experience, V. 21, №12. -1991. P. 1301-1321.

116. Thomas Ball and« James R. Larus. Branch Prediction For Free // SIGPLAN Notices, V. 28 № 6. June 1993. P. 300-313.

117. Youfeng Wu and James R. Larus. Static Branch Frequency and Program Profile Analysis // International Symposium on Microarchitecture (MICRO-27). 1994. P. 1-11.

118. Волконский BIICK, Масленников Д; M., Ровинский Е. ВГ Развитие метода статического предсказания профильной информации // Высокопроизводительные вычислительные системы и микропроцессоры. Выпуск 2. Сб. научных трудов ИМВС РАН. Москва, 2001. С. 37-51.

119. А. С. Боханко, С. В. Новиков, С. Л. Шлыков. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе. № 8. 2005, С. 73-80.

120. Дроздов А*. Ю:, Новиков С. В., Боханко А. С., Галазин А. Б. Def-Use граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. № 12. 2005. С. 3-14.

121. Р:Миллер, Л.Боксер. Последовательные и параллельные алгоритмы: общий подход. БИНОМ, Лаборатория знаний, Москва, 2006

122. Alexander Aiken, Alexandru Nicolau, Steven Novack. Resource-Constrained Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, December 1995, pp. 1248-1270

123. Walter Triebel. Itanium Architecture for Software Developers. Intel Press, 2000.

124. A.E. Eichenberger, E. S. Davidson, "Stage Scheduling: A Technique to Reduce the Register Requirements of a Modulo Schedule", Proceedings of the 28-th Annual IEEE/ACM International Syposium in Microarchitecture, pp 338-349, November 1995.

125. J.R. Allen, K. Kennedy, C. Porterfleld, and J: Warren. Conversion of control dependence to data dependence // In Proceedings of the Tenth Annual ACM Symposium on the Principles of Programming Languages, January 1983, P. 177189

126. Utpal Banerjee, Loop Transformations for Restructuring Compilers. Kluwer academic Publishers, 1993.

127. A. W. Lim and M. S. Lam, Maximizing Parallelism and Minimizing Synchronization with Affine Partitions Parallel Computing, Vol. 24, Issue 3-4, May 1998, Pages 445-475.

128. A. W. Lim, G. I. Cheong and M. S. Lam, An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication In Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing, June, 1999, pp. 228-237.

129. Воеводин B.B., Воеводин Вл.В. Параллельные вычисления. // Санкт-Петербург, "БХВ-Петербург" 2002. -608 с.