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

• Шумаков, Сергей Михайлович
• кандидат физико-математических наук
• 2002

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

Оглавление.

1. Введение.

2. Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд.

2.1. ILP-платформы.

2.2. Критерии оптимизации кода.

2.3. Круг проблем, связанных с оптимизацией кода для ILP-процессоров.

2.4. Области планирования.

2.5. Усиление параллелизма в пределах областей планирования

2.5.1. Преобразования циклов.

2.5.2. Встраивание функций.

2.5.3. Снятие зависимостей по данным.

2.5.4. Соотношение программного и аппаратного параллелизма.

2.6. Планирование команд.

2.6.1. Алгоритмы планирования.

I 2.6.2. Координация планирования и распределения регистров.

2.6.3. Глобальное планирование.

2.6.4. Аппаратная поддержка глобального планирования.

2.6.5. Метод доминантного параллелизма при планировании в древовидных областях.

2.6.6. Планирование по прогнозу значений данных.

2.7. Особенности генерации кода для ЦПОС.

2.8. О роли языковых расширений.

2.9. Сводка методов оптимизации для процессоров с поддержкой параллелизма на уровне команд.

3. Компилятор с оптимизирующим постпроцессором - детальное описание.

3.1. Характеристика процессора 1В577.

3.2. Общие сведения о компиляторе для 1В577.

3.3. Роль базового компилятора.

3.4. Постпроцессирование.

3.4.1. Примеры оптимизаций, выполняемых постпроцессором.

3.4.2. Основные понятия.

3.4.3. Последовательность обработки входного ассемблерного файла.

3.4.4. Аппаратная совместимость.

3.4.5. Модель линейного участка и постановка задачи планирования.

3.4.6. Алгоритм планирования.

3.4.7. Учет аппаратных задержек.

3.4.8. Сокращение перебора.

3.4.9. Подбор вариантов команд.

3.4.10. Модификация команд.

3.5. Настройка постпроцессора на архитектуру 1В577.

3.5.1. Регистры.

3.5.2. Классы регистров.

3.5.3. Соглашения о связях.

3.5.4. Ресурсы.

3.5.5. Свойства команд.

3.5.6. Варианты.

3.5.7. Псевдокоманды (модификаторы).

3.5.8. Динамические ресурсы.

3.5.9. Реализация аппаратных ограничений при помощи псевдорегистров.

4. Оценки эффективности.

4.1. Сравнение с другими методами планирования.

4.1.1. Списочное планирование.

4.1.2. Методы планирования на основе ЦЛП.

4.1.3. Метод планирования с использованием дизъюнктивных графов.

4.2. Измерение эффективности кода для процессора 1В577.

4.2.1. Цели и методика измерений.

4.2.2. Результаты измерений.

4.2.3. Конвейеризация и развертка циклов.

4.2.4. Замена адресации со смещением на адресацию с постинкрементацией адресного регистра.

4.2.5. Перестановки обращений к памяти.

4.2.6. Оценка эффективности оптимизаций.

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

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

Актуальность темы.

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

С аппаратной точки зрения наиболее перспективными в данном классе архитектур признаются процессоры с длинным командным словом. Их быстрое развитие ставит сложные задачи перед разработчиками инструментальных средств программирования. Некачественный компилятор способен нивелировать преимущества, предоставляемые высокопроизводительной аппаратурой. Укажем, что компания Hewlett-Packard, параллельно с созданием архитектуры IA-64, выделяет миллионы долларов на развитие инструментальных средств.

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

Таким образом, для полного использования преимуществ микропроцессоров с длинным командным словом нужны новые исследования, новые методы оптимизации объектного кода.

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

Основными целями диссертационной работы являются:

- исследование методов оптимизации объектного кода для микропроцессорных архитектур с параллелизмом на уровне команд;

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

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

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

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

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

Практическая ценность.

Реализован оптимизирующий компилятор для отечественного микропроцессора 1В577. Этот компилятор используется в НИИСИ РАН, КБ "Корунд".

Апробация.

Основные положения диссертационной работы докладывались на международной конференции «Параллельные вычисления и задачи управления», Москва, ИПУ РАН 2001 и на семинаре «Современные сетевые технологии», МГУ, 2001.

Публикации.

По теме диссертации опубликовано 5 печатных работ - [4], [5], [6], [7],

19].

Объем и структура работы.

Диссертация состоит из 4 глав, заключения и списка литературы.

Первая глава является введением.

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

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

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

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

Список литературы насчитывает 70 названий.

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

5. Заключение

В диссертационной работе получены следующие основные результаты.

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

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

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

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

5. Разработан оптимизирующий кросс-компилятор с языка Си для отечественных целевых ЭВМ на основе микропроцессора 1В577. Компилятор позволяет сочетать преимущества программирования на языке высокого уровня с качеством объектного кода, близким к ручному, что подтверждено полученными экспериментальными оценками.

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

Список литературы диссертационного исследования кандидат физико-математических наук Шумаков, Сергей Михайлович, 2002 год

1. Ахо А., Сети Р., Ульман Д., Компиляторы: принципы, технологии и инструменты. - М., Издательский дом "Вильяме", 2001.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, том 2. М., Мир, 1978.

3. Балашов В.В., Капитонова А.П., Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Метод и средства оценки времени выполнения оптимизированных программ. Программирование #5, 2000, с. 52- 61.

4. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Алгоритм планирования потока команд для VLIW-процессоров. М.: НИИСИ РАН, 2002.

5. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Генерация эффективного кода для процессорных архитектур с явным параллелизмом. М.: НИИСИ РАН, 2001.

6. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. О проблеме оптимизации кода для процессорных архитектур с явным параллелизмом. Труды международной конференции "Параллельные вычисления и задачи управления". - М.: ИПУ РАН, 2001.

7. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Описание VLIW-архитектуры в оптимизирующем постпроцессоре. М.: НИИСИ РАН, 2001.

8. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М., Мир, 1975.

9. Дорошенко А.Ю., Куйвашев Д.В. Архитектура модульного кросскомпилятора для микропроцессоров с очень длинным командным словом. Проблемы программирования, 2000 г., N 3-4, с. 122-134 (наукр. языке).

10. Ю.Дорошенко А.Ю., Куйвашев Д.В. Интеллектуализация векторизующих компиляторов для микропроцессоров с длинным командным словом. -Проблемы программирования, 2001 г., N 1-2, с. 138-151 (на укр. языке).

11. П.Евстигнеев В.А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом (обзор). Программирование, 1991, N 2, стр. 69-80.

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

13. З.Калашников Д.В., Машечкин И.В., Петровский М.И. Планирование потока инструкций для конвейерных архитектур. Москва, МГУ, Вестник Московского университета, серия 15 (вычислительная математика и кибернетика), N4, 1999, с. 39-44.

14. Н.Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988 г.

15. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М., Мир, 1985.

16. Скворцов С.В. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов. Программирование 1996, N 2, стр. 41-52.

17. Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации. Программировние, 1992, N 3, стр. 16-37.

18. Шланскер М.С., Pay Б.Р. Явный параллелизм на уровне команд. Открытые Системы, #11-12, 1999.

19. Шумаков. С.М. Обзор методов оптимизации кода для процессоров поддержкой параллелизма на уровне команд. М.: НИИСИ РАН, 2002.

20. ADSP-21000 Family. С Tools Manual. Analog Devices, Inc. http://www.analog.com/publications/documentation/C-Toolsmanual/books. htm

21. Aho A.V., Sethi R, Ullman J.D.: Compilers Principles, Techniques, and Tools, Addison-Wesley, 1986

22. Allen J.R., Kennedy K., Porterfield C., Warren J.D. Conversion of Control Dependence to Data Dependence. Proceedings of the 1 Oth ACM Symposium on Principles of Programming Languages. Jan. 1983, pp. 177-189.

23. Araujo G., Malik S. Optimal Code Generation for Embedded Memory Non-Homogeneous Register Architectures. 8th Int. Symp.on System Synthesis (ISSS), 1995, pp. 36-41.

24. Araujo G., Malik S., Lee M. Using Register-Transfer Paths in Code Generation for Heterogeneous Memory-Register Architectures. In ACM IEEE Design Automation Conference (DAC), number 33, pp. 591-596, June 1996.

25. Baneijia S., Havanki W.A., Conte T.M. Treegion Scheduling for Highly Parallel Processors. Proceedings of the 3rd International Euro-Par Conference (Euro-Par'97, Passau, Germany), pp. 1074-1078, Aug. 1997.

26. Benitez M. E., Davidson J. W. Target-specific Global Code Improvement: Principles and Applications. Technical Report CS-94-42, Department of Computer Science, University of Virginia, VA 22903.

27. Bernstein D., Rodey M. Global Instruction Scheduling for Superscalar Machines. Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pp.241-255, June 1991.

28. Bharadwaj J., Menezes K. McKinsey C. Wavefront Scheduling: Path Based Data Representation and Scheduling of Subgraphs. The Journal of Instruction-Level Parallelism, May 2000.

29. Cooper K.D., Schielke P.J., Subramanian D. An Experimantal Evaluationof List Scheduling. Department of Computer Science, Rice University, Houston, TX, USA: Technical Report, http://cs-tr.cs.rice.edu/Dienst/UI/2.0/Describe/ncstrl.rice-cs/TR98-326

30. Eichenberger A. E., Davidson E. S., Abraham S. G. Minimizing Register Requirements of a Modulo Schedule via Optimum Stage Scheduling. -International Journal of Parallel Programming, February, 1996.

31. Eichenberger A. E., Lobo S. M. Efficient Edge Profiling for ILP-Processors. Proceedings of PACT 98, 12-18 October 1998 in Paris, France.

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

33. Fisher J.A. Trace scheduling: A Technique for Global Microcode Compaction. IEEE Transaction on Computers, vol. 7, pp. 478-490, July 1981.

34. Gebotys С. H., Gebotys R. J. Complexities In DSP Software Compilation: Performance, Code Size, Power, Retargetability. 1060-3425/98, IEEE, 1998.

35. Grossman J.P. Compiler and Architectural Techniques for Improving the

36. Effectiveness of VLIW Compilation. submitted to ICCD 2000.

37. Havanki W. A., Banerjia S., Conte Т. M. Treegion Scheduling for Wide Issue Processors. Proc. 4th Intl. Symp. on HighPerformance Computer Architecture, Feb. 1998, pp. 266-276.

38. Hoogerbrugge J., Augusteijn L. Instruction Scheduling for TriMedia. The Journal of Instruction-Level Parallelism, February 1999

39. Horst E., Kloosterhius W., Heyden J. А С Compiler for the Embedded R.E.A.L DSP Architecture. Материал получен с телеконференции comp.dsp.

40. Hsu P.Y.T., Davidson E.S. Highly Concurrent Scalar Processing. -Proceedings of the 13th Annual International Symposium on Computer Architecture, pp. 386-395. June 1986.

41. IA-64 Application Developer's Architecture Guide. Intel, May 1999.

42. ISO/IEC 9899:1999(E). Programming Languages C. - ISO/IEC, 1999.

43. Kiyohara Т., Gyllenhaal J. C. Code Scheduling for VLIW/ Superscalar Processors with Limited Register Files. Proceedings of the 25th International Symposium on Microarchitecture, Dec. 1992, pp. 197-201.

44. Leung A., Palem K.V. A fast algorithm for scheduling timeconstrainedinstructions on processors with ILP. In The 1998 International Conference on Parallel Architectures and Compilation Techniques (PACT 98), Paris, October, 1998.

45. Leung A., Palem K.V. Scheduling Time-Constrained Instructions on Pipelined Processors. Submitted for publication to ACM TOPLAS, 1999.

46. Leupers R. Code Generation for Embedded Processors. ISSS 2000, Madrid/Spain, Sept 2000.51 .Leupers R. Function Inlining under Code Size Constraints for Embedded Processors. ICCAD'99, San Jose (USA), Nov 1999.

47. Leupers R. Instruction Scheduling for Clustered VLIW DSPs. -Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT'00).

48. Leupers R. Novel Code Optimization Techniques for DSPs.- 2nd European DSP Education and Research Conference, Paris/France, Sep 1998.

49. Leupers R., Marwedel P. Time-Constrained Code Compaction for DSPs. -8th Int. System Synthesis Symposium(ISSS), 1995. Trans.on VLSI Systems, Vol. 5, no. 1, March 1997.

50. Liao S., Devadas S., Keutzer K., Tjiang S., Wang A. Storage Assignmentto decrease code size. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 186-195, 1995.

51. Lin W:-Y., Lee C.G., Chow P. An Optimizing Compiler for the TMS320C25 DSP Chip. Proceedings of the 5th International Conference on Signal Processing Applications and Technology, pp. I-689-I-694, October 1994.

52. Mahlke S. A., Chen W. Y., Hwu W. W., Rau B. R., Schlansker M. S. Sentinel Scheduling for VLIW and Superscalar Processors. ASPLOS-V Conference Proceedings, October 1992.

53. Mahlke S.A., Lin D.C., Chen W.Y., Hank R.E., Bringmann R.A. Effective

54. Compiler Support for Predicated Execution Using the Hyperblock. -Proceedings of the 25th Annual International Workshop on Microprogramming (Portland, Oregon), pp. 45-54, Dec. 1992.

55. Martin M. M., Roth A., Fischer C. N. Exploiting Dead Value Information. -30th International Symposium on Microarchitecture, pages 125—135, December 1997.

56. Moreno J.H. Dynamic Translation of tree-instructions into VLIW. IBM Research Report, 1996.

57. Motorola DSP96000 User's Manual. Motorola, Inc., 1990.

58. Pai V. S., Adve S. Code Transformation to Improve Memory Parallelism. -The Journal of Instruction-Level Parallelism, May 2000.

59. Pendry A., Fenwick J. В., Norris J. C. Using SUIFas a Front-end Translator for Register Allocation and Instruction Scheduling Research. In Second SUIF Compiler Workshop, Stanford, CA, August 1997.

60. Pinter S. Register Allocation with Instruction Scheduling: a New Approach. -Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 248-257, 1993.

61. Pozzi L. Compilation Techniques for Exploiting Instruction Level Parallelism, a Survey. Milano, Italy, 1998.

62. Rajagopalan S., Vachharajani M,. Malik S. Handling Irregular ILP Within Conventional VLIW Schedulers Using Artificial Resource Constraints. -CASES'00, November 17-19, 2000, San Jose, California.

63. Rao S. IA-64 Code Generation. Electrical and Computer Engineering, June 2000.

64. Stallman R. Using and Porting GNU CC. FSF, Boston, USA.