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

• Боханко, Андрей Сергеевич
• кандидат технических наук
• 2005

Введение диссертации (часть автореферата) на тему «Распределение регистров методом раскраски графа несовместимости для современных вычислительных систем»

Актуальность работы.2

Цель диссертационной работы.3

Научная новизна.4

Апробация.5

Публикации.5

Краткое содержание работы.6

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

3.4 Выводы

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

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

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

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

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

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

Проведен анализ вопросов, связанных с распределением регистров, не зависящим от целевой платформы. Проведен анализ подходов к написанию платформонезависимого оптимизирующего компилятора. Представлены методы, позволяющие реализовать распределение регистров для практически всех современных архитектур на базе единого исходного кода. Предложен список параметров целевой архитектуры, достаточный для настройки платформонезависимого распределителя регистров. Такой не зависящий от целевой платформы распределитель регистров был реализован в рамках оптимизирующего компилятора для микропроцессора Эльбрус-ЗМ; его тестирование проведено на трех платформах: Эльбрус-ЗМ, Intel Itanium и SUN SPARC V8.

Заключение

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Боханко, Андрей Сергеевич, 2005 год

1. Арнольд 1997. Арнольд К., Гослинг Д. Язык программирования Java// Питер, Санкт-Петербург, 1997

2. Евстигнеев 1994. Евстигнеев В. А., Касьянов В. Н. Теория графов: алгоритмы обработки деревьев // ВО "Наука", Новосибирск, 1994

3. Ершов 1977. Ершов А. П. Введение в теоретическое программирование (беседа о методе) // Наука, Москва, 1977

4. Керниган 2001. Керниган Б., Ритчи Д. Язык программирования С, 3-е издание // С-Петербург, Невский Диалект, 2001

5. Рейли 1999. Рейли М. Как рождается микропроцессор Alpha" // Открытые Системы, №4, 1999, С. 14-21

6. Шланскер 1999. Шланскер М. С., Pay Б. Р. Явный параллелизм на уровне команд // Открытые Системы, № 11-12 (43^14), 1999, С. 8-16

7. Шривер 1999. Шривер Б., Капек П. Из чистого любопытства. Интервью с Джоном Коком // Открытые Системы, № 9-10 (41-42), 1999, С. 89-96

8. Aho 1986. Aho А. V., Sethi R., Ullman J. D. Compilers: principles, techniques, and tools // Addison-Wesley, Reading, Massachusetts, 1986

9. Beck 1993. Beck G. R., Yen D. W. L., Anderson T. L. The Cydra 5 minisupercomputer: architecture and implementation // The Journal of Supercomputing, №7, 1993, pp. 143-180

10. Bharadwaj 2000a. Bharadwaj J., McKinsey C. Wavefront scheduling: path based data representation and scheduling of subgraphs // Journal of instruction-level parallelism, Vol. 1, № 6, pp. 1-6, 2000

11. Bharadwaj 2000b. Bharadwaj J., Chen W. Y., Chuang W., Hoflehner G., Menezes K., Muthukumar K., Pierce J. The Intel IA-64 compiler code generator // IEEE MICRO, № 11, 2000, pp. 44-52

12. Briggs 1989. Briggs P., Cooper K. D., Kennedy K., Torczon L. Coloring heuristics for register allocation // Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, 1989, pp. 275-284

13. Briggs 1994. Briggs P., Cooper K. D., Torczon L. Improvements to graph coloring register allocation // ACM Transactions on Programming Languages and Systems, Vol. 16, № 3, 1994, pp. 428-455

14. Callahan 1991. Callahan D., Koblenz B. Register allocation via hierarchical graph coloring // Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, 1991, pp. 192-203

15. Chaitin 1981. Chaitin G., Auslander M„ Chandra A., Cocke J., Hopkins M„ Markstein P. Register allocation via coloring // Computer Languages, №1, 1981, pp. 47-57

16. Chaitin 1982. Chaitin G. Register allocation and spilling via graph coloring// Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction, SIGPLAN Notices, №6, 1982, pp. 98-105

17. Chow 1990. Chow F. C., Hennessy J. L. The priority-based coloring approach to register allocation // ACM Transactions on Programming Languages and Systems, Vol. 12, №4, pp. 501-536

18. Cocke 1988. Cocke J. Turing award lecture: the search for performance in scientific processors // Communications of the ACM, №3, 1998, pp. 250-253

19. Diefendorf 1999. Diefendorf K. The russians are coming: supercomputer maker Elbrus seeks to join x86/IA-64 melee // Microprocessor Report, Vol. 11, № 2, 1999

20. Drozdov 1993. Drozdov A., Moukhin, Kasinsky A., Okunev S., Ostanevich A., Rumyantsev Y., Sushentsov, Tikhonov V., Volkonski V., Yaremenko K. The optimizing compiler for the Elbrus-3 supercomputer // CSAM'93 Proceedings, pp. 127-128.

21. Dulong 1999. Dulong C., Krishnaiyer R„ Kulkarni D., Lavery D., Li W., Ng J., Sehr D. An overview of the Intel IA-64 compiler // Intel Technology Journal, Quarter 4, 1999

22. Eichenberger 1994. Eichenberger A. E., Davidson E. S. Minimum register requirements for a modulo schedule // Proceedings of the 27-th Annual International Symposium on Microarchitecture, San Jose, California, 1994, pp. 75-84

23. Eichenberger 1995. Eichenberger A. E. Register allocation for predicated code // Proceedings of the 28th annual international symposium on Microarchitecture, 1995, pp. 180-191

24. Ellis 1985. Ellis J. R. Bulldog: a compiler for VLIW architectures // MIT Press, Cambridge, Massachusetts, 1985

25. Fisher 1981. Fisher J. A. Trace scheduling: a technique for global microcode compaction // IEEE Transactions on Computers, Vol. C-30, pp. 478-490

26. Garner 1988. Garner R., Agrawal A., Brown W., Hough D., Joy W., Kleiman S., Muchnick S., Patterson D., Pendleton J., Tuck R. The scalable processor architecture SPARC, Proceedings of 1988 COMPCON Conference, 1988

27. GCC 2005. GCC internals manual // Free Software Foundation, URL: http://gcc.gnu.org/onlinedocs/ (August 2005)

28. Gillies 1996. Gillies D. M., Ju D. R„ Johnson R., Schlansker M. Global predicate analysis and its application to register allocation // Proceedings of the 29th annual ACM/IEEE International Symposium on Microarchitecture, 1996, pp. 114-125

29. Gordon 2001. Gordon A. D., Syme D. Toward a multi-language intermediate code // POPL'Ol Proceedings, pp. 248-260

30. Grune 2000. Grune D., Bal H. E., Jacobs C. J. H., Langendoen K. G. Modern compiler construction // John Wiley & Sons, New York, 2000

31. Gupta 1994. Gupta R., Soffa M. L., Ombres D. Efficient register allocation via coloring using clique separators // ACM Transactions on Programming Languages and Systems, Vol. 16, № 3, pp. 370-386

32. Hank 1993. Hank R. E. Machine independent register allocation for the IMPACT-C Compiler//MS Thesis, University of Illinois, Urbana, USA, 1993

33. Huck 2000. Huck J., Morriss D., Ross J., Knies A., Mulder H., Zahir R. Introducing The IA-64 Architecture // IEEE MICRO, №5, 2000, pp. 12-22

34. Hwu 1995. Hwu W. W„ Hank R. E., Gallagher D. M., Mahlke S. A., Lavery D. M., Haab G. E., Gyllenhaal J. C., August D. I. Compiler Technology for Future Microprocessors // Proceedings of the IEEE, Vol. 83, № 12, pp. 1625-1640

35. Johnson 1996. Johnson R., Schlansker M. Analysis techniques for predicated code // Proceedings of the 29th Annual International Symposium on Microarchitecture, 1996

36. Kathail 1993. Kathail V., Schlansker M., Rau B. HPL PlayDoh architecture specification: version 1.0 // Hewlett-Packard Laboratories Technical Report, HPL-93-80,1993

37. Makowski 1995. Makowski C., Pollock L. L. Achieving efficient register allocation via parallelism // Proceedings of the 1995 ACM symposium on Applied computing, 1995,pp. 123-129

38. Moore 1965. Moore G. Cramming more components onto integrated circuits // Electronic, Volume 38, № 8, 1965

39. Muchnick 1997. Muchnick S. S. Advanced compiler design and implementation // Morgan Kauffman, San Francisco, 1997

40. Nicolau 1993. Nicolau A., Novack S. Trailblazing: a hierarchical approach to percolation scheduling// Proceedings of the 1993 International Conference on Parallel Processing, 1993, pp. 120-124

41. Ning 1993. Ning Q., Gao G. R. A novel framework of register allocation for software pipelining // 20-th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1993, pp. 29-42

42. Norris 1993. Norris C., Pollock L. L. A schedular-sensitive global register allocator // Proceedings of the 1993 ACM/IEEE conference on Supercomputing, 1993, pp. 804813

43. Norris 1995. Norris C., Pollock L. L. An experimental study of several cooperative register allocation and instruction scheduling strategies // Proceedings of the 28th annual international symposium on Microarchitecture, 1995, pp. 169-179

44. Park 1991. Park J. С. H., Schlansker M. S. On predicated execution // Technical Report HPL-91-58, HP Laboratories, Palo Alto, California, 1991

45. Pinter 1993. Pinter S. S. Register allocation with instruction scheduling // Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, 1993, pp. 248-257

46. Ramalingam 1999. Ramalingam G. Identifying loops in almost linear time // ACM Transactions on Programming Languages and Systems, Volume 21, № 2, 1999, pp. 175-188

47. Rau 1989. Rau B. R., Yen D., Yen W., Towle R. The Cydra 5 departmental supercomputer: design philosophies, decisions, and trade-offs // IEEE Computer, Vol. 22, № l,pp. 12-35

48. Rau 1992. Rau B. R., Lee M., Tirumalai P. P., Schlansker M. S. Register allocation for software pipelined loops // Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation, 1992, pp. 283-299

49. Ritchie 1978. Ritchie D. M., Thompson K. The UNIX time-sharing system // The Bell System Technical Journal, № 4, 1978

50. Ryder 1986. Ryder B. G., Paull M. C. Elimination algorithms for data flow analysis // ACM Computing Surveys, N9, 1986, pp. 277-316

51. Smith 2004. Smith M. D., Ramsey N., Holloway G. A generalized algorithm for graph-coloring register allocation // Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, 2004, pp. 277-288

52. SPEC 2005. SPEC CPU2000 run and reporting rules // SPEC Open Systems Group, URL: http://www.spec.org/cpu2000/docs/runrules.html (August 2005)

53. Triebel 2000. Triebel W. Itanium architecture for software developers // Intel Press, 2000