Оптимизация объектного кода для процессорных архитектур с поддержкой параллелизма на уровне команд
Диссертация
Разработан алгоритм планирования потока команд для процессоров с длинным командным словом путем перебора планов выполнения по методу динамического программирования. В алгоритме предусмотрены оптимизации, направленные на сокращение перебора, которые позволяют обеспечить приемлемое время обработки входных программ. Разработан оптимизирующий кросс-компилятор с языка Си для отечественных целевых ЭВМ… Читать ещё >
Содержание
- 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. Алгоритмы планирования
- 2. 6. 3. Глобальное планирование
- 2. 6. 4. Аппаратная поддержка глобального планирования
- 2. 6. 5. Метод доминантного параллелизма при планировании в древовидных областях
- 2. 6. 6. Планирование по прогнозу значений данных
- 2. 7. Особенности генерации кода для ЦПОС
- 2. 8. О роли языковых расширений
- 2. 9. Сводка методов оптимизации для процессоров с поддержкой параллелизма на уровне команд
- 3. 1. Характеристика процессора 1В
- 3. 2. Общие сведения о компиляторе для 1В
- 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В
- 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. 1. Сравнение с другими методами планирования
- 4. 1. 1. Списочное планирование
- 4. 1. 2. Методы планирования на основе ЦЛП
- 4. 1. 3. Метод планирования с использованием дизъюнктивных графов
- 4. 2. Измерение эффективности кода для процессора 1В
- 4. 2. 1. Цели и методика измерений
- 4. 2. 2. Результаты измерений
- 4. 2. 3. Конвейеризация и развертка циклов
- 4. 2. 4. Замена адресации со смещением на адресацию с постинкрементацией адресного регистра
- 4. 2. 5. Перестановки обращений к памяти
- 4. 2. 6. Оценка эффективности оптимизаций
- 4. 2. 7. Распределение регистров
Список литературы
- Ахо А., Сети Р., Ульман Д., Компиляторы: принципы, технологии и инструменты. — М., Издательский дом «Вильяме», 2001.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, том 2. М., Мир, 1978.
- Балашов В.В., Капитонова А. П., Костенко В. А., Смелянский Р. Л., Ющенко Н. В. Метод и средства оценки времени выполнения оптимизированных программ. Программирование #5, 2000, с. 52- 61.
- Вьюкова Н.И., Галатенко В. А., Самборский С. В., Шумаков С. М. Алгоритм планирования потока команд для VLIW-процессоров. М.: НИИСИ РАН, 2002.
- Вьюкова Н.И., Галатенко В. А., Самборский С. В., Шумаков С. М. Генерация эффективного кода для процессорных архитектур с явным параллелизмом. М.: НИИСИ РАН, 2001.
- Вьюкова Н.И., Галатенко В. А., Самборский С. В., Шумаков С. М. О проблеме оптимизации кода для процессорных архитектур с явным параллелизмом. Труды международной конференции «Параллельные вычисления и задачи управления». — М.: ИПУ РАН, 2001.
- Вьюкова Н.И., Галатенко В. А., Самборский С. В., Шумаков С. М. Описание VLIW-архитектуры в оптимизирующем постпроцессоре. М.: НИИСИ РАН, 2001.
- Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М., Мир, 1975.
- Дорошенко А.Ю., Куйвашев Д. В. Архитектура модульного кросскомпилятора для микропроцессоров с очень длинным командным словом. Проблемы программирования, 2000 г., N 3−4, с. 122−134 (наукр. языке).
- Ю.Дорошенко А. Ю., Куйвашев Д. В. Интеллектуализация векторизующих компиляторов для микропроцессоров с длинным командным словом. -Проблемы программирования, 2001 г., N 1−2, с. 138−151 (на укр. языке).
- П.Евстигнеев В. А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом (обзор). Программирование, 1991, N 2, стр. 69−80.
- Ершов А.П. Введение в теоретическое программирование. М., Наука, 1977.
- З.Калашников Д. В., Машечкин И. В., Петровский М. И. Планирование потока инструкций для конвейерных архитектур. Москва, МГУ, Вестник Московского университета, серия 15 (вычислительная математика и кибернетика), N4, 1999, с. 39−44.
- Н.Касьянов В. Н. Оптимизирующие преобразования программ. М.: Наука, 1988 г.
- Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М., Мир, 1985.
- Скворцов С.В. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов. Программирование 1996, N 2, стр. 41−52.
- Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации. Программировние, 1992, N 3, стр. 16−37.
- Шланскер М.С., Pay Б. Р. Явный параллелизм на уровне команд. Открытые Системы, #11−12, 1999.
- Шумаков. С.М. Обзор методов оптимизации кода для процессоров поддержкой параллелизма на уровне команд. М.: НИИСИ РАН, 2002.
- ADSP-21 000 Family. С Tools Manual. Analog Devices, Inc. http://www.analog.com/publications/documentation/C-Toolsmanual/books. htm
- Aho A.V., Sethi R, Ullman J.D.: Compilers Principles, Techniques, and Tools, Addison-Wesley, 1986
- 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.
- 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.
- 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.
- 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.
- 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 22 903.
- 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.
- Bharadwaj J., Menezes K. McKinsey C. Wavefront Scheduling: Path Based Data Representation and Scheduling of Subgraphs. The Journal of Instruction-Level Parallelism, May 2000.
- 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
- 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.
- Eichenberger A. E., Lobo S. M. Efficient Edge Profiling for ILP-Processors. Proceedings of PACT 98, 12−18 October 1998 in Paris, France.
- Fisher J. A. Global code generation for instruction-level parallelism: Trace Scheduling-2. Tech. Rep. HPL-93−43, Hewlett-Packard Laboratories, June 1993
- Fisher J.A. Trace scheduling: A Technique for Global Microcode Compaction. IEEE Transaction on Computers, vol. 7, pp. 478−490, July 1981.
- Gebotys С. H., Gebotys R. J. Complexities In DSP Software Compilation: Performance, Code Size, Power, Retargetability. 1060−3425/98, IEEE, 1998.
- Grossman J.P. Compiler and Architectural Techniques for Improving the
- Effectiveness of VLIW Compilation. submitted to ICCD 2000.
- 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.
- Hoogerbrugge J., Augusteijn L. Instruction Scheduling for TriMedia. The Journal of Instruction-Level Parallelism, February 1999
- Horst E., Kloosterhius W., Heyden J. А С Compiler for the Embedded R.E.A.L DSP Architecture. Материал получен с телеконференции comp.dsp.
- 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.
- IA-64 Application Developer’s Architecture Guide. Intel, May 1999.
- ISO/IEC 9899:1999(E). Programming Languages C. — ISO/IEC, 1999.
- 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.
- 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.
- Leung A., Palem K.V. Scheduling Time-Constrained Instructions on Pipelined Processors. Submitted for publication to ACM TOPLAS, 1999.
- 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.
- Leupers R. Instruction Scheduling for Clustered VLIW DSPs. -Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT'00).
- Leupers R. Novel Code Optimization Techniques for DSPs.- 2nd European DSP Education and Research Conference, Paris/France, Sep 1998.
- 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.
- 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.
- 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.
- 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.
- Mahlke S.A., Lin D.C., Chen W.Y., Hank R.E., Bringmann R.A. Effective
- Compiler Support for Predicated Execution Using the Hyperblock. -Proceedings of the 25th Annual International Workshop on Microprogramming (Portland, Oregon), pp. 45−54, Dec. 1992.
- Martin M. M., Roth A., Fischer C. N. Exploiting Dead Value Information. -30th International Symposium on Microarchitecture, pages 125—135, December 1997.
- Moreno J.H. Dynamic Translation of tree-instructions into VLIW. IBM Research Report, 1996.
- Motorola DSP96000 User’s Manual. Motorola, Inc., 1990.
- Pai V. S., Adve S. Code Transformation to Improve Memory Parallelism. -The Journal of Instruction-Level Parallelism, May 2000.
- 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.
- 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.
- Pozzi L. Compilation Techniques for Exploiting Instruction Level Parallelism, a Survey. Milano, Italy, 1998.
- 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.
- Rao S. IA-64 Code Generation. Electrical and Computer Engineering, June 2000.
- Stallman R. Using and Porting GNU CC. FSF, Boston, USA.