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

• Иванов, Дмитрий Сергеевич
• кандидат технических наук
• 2012

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

Введение

Глава 1. Методы распределения регистров

1.1. Основные понятия и определения

1.2. Особенности организации регистровых файлов для ШБС-архитектур.

1.3. Существующие методы распределения регистров

1.4. Недостатки существующих методов распределения регистров

1.5. Постановка задачи.

1.6. Выводы.

Глава 2. Технология распределения регистров при планировании инструкций.

2.1. Глобальное и локальное распределение регистров

2.2. Сбор информации о сетях

2.3. Глобальное распределение регистров перед планированием инструкций

2.4. Откачка в память после глобального распределения

2.5. Планирование инструкций и локальное распределение регистров

2.6. Откачка сетей в память.

2.7. Удаление лишних инструкций

2.8. Оценка сложности алгоритма

2.9. Результаты применения алгоритма

2.10. Выводы.

Глава 3. Особенности технологии для архитектур класса УЬПУ

3.1. Планирование инструкций с использованием широкого командного слова.

3.2. Распределение регистров

3.3. Особенности распределения регистров при наличии глобальных меток

3.4. Взаимодействие с другими фазами компилятора

3.5. Архитектуры VLIW и ЕРЮ

3.6. Результаты применения алгоритма

3.7. Выводы.

Введение диссертации (часть автореферата) на тему «Комплексная технология распределения регистров и планирования инструкций в оптимизирующем компиляторе вычислительных комплексов семейства "Эльбрус"»

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

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

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

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

Особенностью данного исследования стало его проведение применительно к различным микропроцессорным архитектурам. С одной стороны, это архитектуры RISC-класса, представленные в данной работе SPARC-совместимыми микропроцессорами «МЦСТ-R» разработки ЗАО «МЦСТ» , на базе которых выпускаются и создаются вычислительные комплексы для широкого класса перебазируемых и встраиваемых систем. В этом варианте планирование инструкций в процессе компиляции (статическое планирование) применяется в силу относительной простоты аппаратуры, исключающей возможность динамического планирования. С другой стороны, это архитектуры класса VLIW, использующие концепцию широкого командного слова, согласно которой компилятор в фазе планирования инструкций осуществляет наполнение командного слова набором инструкций, допускающих их одновременное выполнение рядом исполнительных устройств процессора. Типовым представителем, использовавшимся при проведении данного исследования, является микропроцессорная архитектура «Эльбрус» , рассчитаная на создание высокопроизводительных стационарных информационно-вычислительных комплексов стратегического применения.

Таким образом, актуальность данного исследования обусловлена его установкой на повышение эффективности оптимизаций, реализуемых при компиляции программ для микропроцессоров с архитектурами классов RISC и VLIW, в частности - для высокопроизводительных вычислительных комплексов семейства «Эльбрус» различного применения.

Цель исследования. Основная цель исследования состояла в повышении производительности вычислительного комплекса при исполнении откомпилированной программы за счет объединения фаз распределения регистров и планирования инструкций при ее компиляции. Наряду с этим, ставилось требование увеличить скорость компиляции программ. Соответственно, решались следующие задачи:

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

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

• Поиск дополнительных резервов производительности за счет удаления избыточных инструкций в процессе планирования

• Экспериментальная оценка увеличения быстродействия компилируемых программ и скорости работы компилятора для вычислительных комплексов на базе микропроцессоров «Эльбрус» и микропроцессоров типа «МЦСТ-R» ;

• Реализация комплексной технологии распределения регистров и планирования инструкций в оптимизирующем компиляторе языков Си/Си++.

Предмет исследования составляют:

• особенности организации регистровых файлов для RISC-архитектур вообще и для VLIW-архитектур [1] в частности

• методы распределения регистров и подходы к учету влияния фаз распределения регистров и планирования инструкций друг на друга

• конечная эффективность и производительность результирующего кода

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов и теории алгоритмов. Оценка эффективности представленных решений выполнялась путем замера времени исполнения программ на вычислительных комплексах с микропроцессорами «Эльбруо и МЦСТ-R. Замеры производились на пакетах задач SPEC CPU95 и SPEC CPU2000 [2]

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

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

• алгоритм распределения регистров при помощи битовых векторов с использованием представления регистрового файла в виде битовой матрицы;

• снижение алгоритмической сложности распределения регистров;

• комплексный метод оптимизации использования памяти в области стека процедуры;

• методы учета аппаратных особенностей архитектур с широким командным словом для распределения регистров при планировании инструкций.

Практическая ценность результатов работы состоит в реализации методов, объектов и алгоритмов комплексной технологии распределения регистров и планирования инструкций в составе оптимизирующего компилятора с языков высокого уровня Си и Си++ для вычислительных комплексов на базе микропроцессоров с архитекурой «Эльбрус» и архитектурой SPARC. Их эффективность подтверждена при исполнении пакетов SPEC CPU2000 и SPEC CPU95.

Апробация

Результаты, полученные в работе, изложены в ряде печатных публикаций, докладывались на научных конференциях, в частности:

• на 49-й научной конференции МФТИ (2006 г.)

• на 50-й научной конференции МФТИ (2007 г.)

• на XXXVII Международной молодежной научной конференции "Гагарин-ские чтения "(Москва, МАТИ, 2011 г.)

• на научно-технической конференции "Перспективные направления развития средств вычислительной техники"в ОАО "НИЦЭВТ"(2011 г.)

• на семинаре Института системного программирования РАН (2011 г.)

• на семинарах секции программного обеспечения ЗАО «МЦСТ» и ОАО «ИНЭУМ» (2006 - 2011 гг.)

Публикации

По теме диссертации опубликовано шесть печатных работ: в Иванов Д.С. Распределение регистров и планирование инструкций в оптимизирующих компиляторах вычислительных средств ЗАО "МЦСТ"// Сборник тезисов докладов научно-технической конференции "Перспективные направления развития средств вычислительной техники Москва 2011, С.54-55

• Иванов Д.С. Удаление лишних инструкций при планировании инструкций и распределении регистров // Научные труды XXXVII Международной молодежной научной конференции "Гагаринские чтения т.4.М.:МАТИ, 2011, С.66-67

• Иванов Д.С. Распределение регистров при планировании инструкций для архитектуры Эльбрус-ЭОмикро // Вопросы радиоэлектроники, Серия Электронная Вычислительная техника, Выпуск 3, 2011, С.70-82

• Иванов Д.С. Распределение регистров при планировании инструкций для УЫ\¥-архитектур // Программирование, № 6, 2010, С.74-80

• Иванов Д.С. Особенности распределения регистров при планировании команд для архитектур с широким командным словом //' Труды 50-й научной конференции МФТИ, 2007,С.55-56

• Иванов Д.С. Распределение регистров при планировании операций для архитектуры Эльбрус-ЭОмикро // Труды 49-й научной конференции МФТИ, 2006, С.46

Структура и объем работы

Диссертация состоит из введения, трех глав и заключения. Список литературы составляет 41 наименование. Объем диссертации составляет 117 страниц текста. Диссертация содержит 15 рисунков.

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

3.7. Выводы

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

2. Распределение регистров на спланированном коде и планирование кода

4>

В н

J3

2 О

Я > чЭ

U g В о О и СЙ 1 * ТЗ ей •с ад В г» оо г

ЧО

Benchmark

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

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

4. Применение предложенной технологии позволяет существенно снизить алгоритмическую сложность распределения регистров. В промышленном компиляторе для архитектуры «Эльбрус» удалось добиться снижения суммарного времени работы фаз распределения регистров и планирования инструкций в 3 раза для задач пакета SPEC CFP2000.

5. Предложенные методы позволяют увеличить производительность компилируемых программ в условиях дефицита регистров и сохранить ее при наличии достаточного количества регистров. В промышленном компиляторе для архитектуры «Эльбрус» удалось добиться увеличения производительности компилируемых программ в среднем на 10% при искусственном ограничении размера регистрового окна.

Заключение

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

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

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

1) Исследованы предложенные в литературе методы распределения регистров и их взаимодействие с планированием инструкций, показана тесная взаимосвязь между задачами распределения регистров и планирования инструкций

2) Предложен метод объединения фаз планирования инструкций и распределения регистров на основе разделения задачи распределения регистров на две подзадачи: распределение регистров для глобальных сетей перед планированием и распределение регистров для локальных сетей при планировании инструкций

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

4) Предложена классификация групп лишних инструкций и рассмотрены методы их удаления при планировании инструкций и распределении регистров

5) Исследованы особенности реализации предложенных методов для различных архитектур и показана применимость предложенных методов для архитектур RISC и VLIW

6) Исследовано взаимодействие объединенной фазы планирования инструкций и распределения регистров с другими фазами компилятора и предложены варианты взаимного расположения этих фаз

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

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

1. Ахо, А., Лам, М., Сети, Р., Ульман, Д. Компиляторы. Принципы, технологии, инструментарий. Вильяме, Москва, 2011

2. Standard Performance Evaluation Corporation. The SPEC Benchmark Suites. CPU-intensive benchmark suite. Electronic resource]. — 1995-2000. http: / / www.spec.org/cpu

3. SPARC International, Inc., Englewood Cliffs, NJ, USA. SPARC architecture manual. Version 8. — 1992

4. ARM Limited. The ARM-THUMB Procedure Call Standard. 1998

5. Галазин, А. Методы оптимизации доступа к подсистеме памяти на этапе компиляции для микропроцессорных систем с архитектурой широкого командного слова, phdthesis, Москва. — 2008. Научный руководитель -Нейман-заде, М.И.

6. Hennessy, J.L., Patterson, D.A. Computer Organization and Design: the Hardware/Software interface. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2009

7. Ершов, А.П. Сведение задачи распределения памяти при составлении программ к задаче раскраски вершин графа, techreport, АН СССР. — 1961

8. Chaitin, G.J. Register allocation & spilling via graph coloring. SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction, pp 98-105. ACM, New York, NY, USA, 1982

9. Briggs, P., Cooper, K.D., Kennedy, K., Torczon, L. Coloring heuristics for register allocation. PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, pp 275-284. ACM, New York, NY, USA, 1989

10. Callahan, D., Koblenz, B. Register allocation via hierarchical graph coloring. SIGPLAN Not., volume 26, № 6:pp 192-203. 1991

11. Goodman, J.R., Hsu, W.C. Code scheduling and register allocation in large basic blocks. ICS '88: Proceedings of the 2nd international conference on Supercomputing, pp 442-452. ACM, New York, NY, USA, 1988

12. Pinter, S.S. Register allocation with instruction scheduling. PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, pp 248-257. ACM, New York, NY, USA, 1993

13. Berson, D.A., Gupta, R., Sofïa, M.L. Ursa: A unifed resource allocator for registers and functional units in vliw architectures, techreport, Pittsburgh, PA. 1992

14. Muchnick, S.S. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA, USA, 1997

15. Norris, C., Pollock, L.L. Register allocation over the program dependence graph. PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, pp 266-277. ACM, New York, NY, USA, 1994

16. Berson, D.A., Gupta, R., Soffa, M.L. Gurrr: a global unified resource requirements representation. IR '95: Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, pp 23-34. ACM, New York, NY, USA, 1995

17. Proebsting, T.A., Fischer, C.N. Demand-driven register allocation. ACM Trans. Program. Lang. Syst., volume 18, № 6:pp 683-710. 1996

18. Goodwin, D.W., Wilken, K.D. Optimal and near-optimal global register allocations using 0-1 integer programming. Softw. Pract. Exper., volume 26, № 8:pp 929-965. 1996

19. Lueh, G.Y., Gross, T. Call-cost directed register allocation. PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, pp 296-307. ACM, New York, NY, USA, 1997

20. Park, J., Moon, S.M. Optimistic register coalescing. PACT '98: Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p 196. IEEE Computer Society, Washington, DC, USA, 1998

21. Chen, G., Smith, M.D. Reorganizing global schedules for register allocation. ICS '99: Proceedings of the 13th international conference on Supercomputing, pp 408-416. ACM, New York, NY, USA, 1999

22. Pu, C., Wilken, K. A faster optimal register allocator. MICRO 35: Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, pp 245-256. IEEE Computer Society Press, Los Alamitos, CA, USA, 2002

23. Koes, D., Goldstein, S.C. A progressive register allocator for irregular architectures. CGO '05: Proceedings of the international symposium on Code generation and optimization, pp 269-280. IEEE Computer Society, Washington, DC, USA, 2005

24. Matz, M. Design and implementation of a graph coloring register allocator for gcc. techreport. — 2003

25. Smith, M.D., Ramsey, N., Holloway, G. A generalized algorithm for graph-coloring register allocation. PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pp 277-288. ACM, New York, NY, USA, 2004

26. Боханко, А. Распределение регистров методом раскраски графа несовместимости для современных вычислительных систем, phdthesis, Москва. — 2005. Научный руководитель Волконский, В.Ю.

27. Xu, W., Tessier, R. Tetris: a new register pressure control technique for vliw processors. LCTES '07: Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pp 113122. ACM, New York, NY, USA, 2007

28. Quintao Pereira, F.M., Palsberg, J. Register allocation by puzzle solving. PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pp 216-226. ACM, New York, NY, USA, 2008

29. Baev, I.D. Techniques for region-based register allocation. CGO '09: Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization, pp 147-156. IEEE Computer Society, Washington, DC, USA, 2009

30. Touati, S.A.A., Barthou, D. On the decidability of phase ordering problem in optimizing compilation. Proceedings of the 3rd conference on Computing frontiers, CF '06, pp 147-156. ACM, New York, NY, USA, 2006

31. Morgan, R. Building an optimizing compiler. Digital Press, Newton, MA, USA, 1998

32. Allen, R., Kennedy, K. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann, San Francisco, CA, USA, 2001

33. Останевич, А. Планирование операций при генерации кода для архитектур с явно выраженным паралелизмом. phdthesis, Москва. — 1999. Научный руководитель Волконский, В.Ю.

34. Briggs, P., Cooper, K.D., Torczon, L. Rematerialization. PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, pp 311-321. ACM, New York, NY, USA, 1992

35. Triebel, W. Itanium Architecture for Software Developers. Intel Press, USA, 2000

36. SPARC International, Inc., Englewood Cliffs, NJ, USA. SPARC architecture manual. Version 9. — 1994

37. P754, I.T. ANSI IEEE 754-1985, Standard for Binary Floating-Point Arithmetic. IEEE, New York. 1985

38. Распределение регистров путем раскраски графа методом Четина 18

39. Квадратный граф, раскрашиваемый двумя цветами. 19

40. Оптимистическая раскраска графа методом Бриггса. 19

41. Четыре этапа технологии распределения регистров при планировании инструкций: сбор информации о сетях, глобальное распределение регистров, откачка глобальных сетей и в память и локальное распределение регистров при планировании инструкций. 37

42. Планирование по приоритетам с разметкой графа зависимостей . 67

43. Изменение производительности компилируемых программ в результате изменения схемы распределения регистров с раскраски графа несовместимости на распределение регистров при планировании инструкций в компиляторе для архитектуры SPARC. . . 81

44. Чтения значения сети в случае нескольких условных использований 95

45. Относительная производительность комбинированной схемы и схемы с раздельными планированием инструкций и распределением регистров.106

46. Отношение суммарного времени работы фаз планирования и распределения регистров для комбинированной и раздельно схем . . 107