Методы автоматической векторизации на этапе компиляции для архитектур с поддержкой коротких векторных инструкций тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Ермолицкий, Александр Викторович

• Ермолицкий, Александр Викторович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Ермолицкий, Александр Викторович

Введение.

Глава 1. Методы автоматической векторизации.

1.1. Короткие векторные инструкции

1.2. Методы векторизации кода без разветвлений управления.

1.2.1. Метод векторизации для традиционных векторных машин

1.2.2. Метод векторизации, основанный на алгоритмах для традиционных векторных машин

1.2.3. Метод векторизации, основанный на раскрутке цикла

1.2.4. Метод векторизации на уровне цикла.

1.2.5. Метод векторизации на уровне линейного участка.

1.3. Методы векторизации кода с разветвлениями управления

1.3.1. Векторизация условного кода на уровне цикла.

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

1.4. Методы повышения эффективности векторизации за счет вспомогательных преобразований.

1.4.1. Динамические проверки выровненности

1.4.2. Открутка итераций цикла

1.4.3. Выборочная открутка итераций цикла

1.4.4. Дополнение массивов

1.5. Недостатки существующих методов.

1.6. Выводы.

Глава 2. Развитие методов автоматической векторизации

2.1. Развитие методов векторизации кода без разветвлений управления

2.1.1. Промежуточное представление.

2.1.2. Алгоритм векторизации циклов на основе раскрутки

2.1.3. Свойства векторизуемого выражения

2.1.4. Алгоритм векторизации рекуррентных выражений

2.1.5. Алгоритм векторизации ациклического кода.

2.2. Развитие методов векторизации кода с разветвлениями управления

2.2.1. Алгоритм векторизации циклов с разветвлениями управления

2.2.2. Алгоритм векторизации циклов с боковыми выходами

2.3. Экспериментальные результаты

2.4. Выводы.

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

3.1. Развитие методов выравнивания инструкций обращения к памяти

3.1.1. Алгоритм выравнивания инструкций цикла

3.1.2. Частичная открутка итерации цикла

3.2. Алгоритм скрутки раскрученных программистом циклов

3.3. Метод динамического арбитра.

3.4. Экспериментальные результаты

3.5. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

• разработка эффективного метода векторизации раскрученных вручную циклов;

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

• реализация указанных методов в составе оптимизирующего компилятора для микропроцессора «Эльбрус» и Sparc V9.

Предмет исследования составляют алгоритмические аспекты разработки оптимизирующих компиляторов для высокопроизводительных вычислительных систем:

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

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

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

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов и теории алгоритмов. Эффективность предложенных в работе алгоритмов и методов оценивалась путем замера времени исполнения программ на вычислительном комплексе с микропроцессором «Эльбрус» . Замеры производились на задачах пакетов SPEC CPU92, SPEC CPU95, SPEC CPU2000[2], а также на функциях высокопроизводительной библиотеки EML(Elbrus Math Library)[3].

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

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

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

• усовершенствованный алгоритм выравнивания инструкций обращения к памяти;

• новый алгоритм скрутки раскрученных вручную циклов.

Практическая ценность работы состоит в создании новых и усовершенствовании известных методов автоматической векторизации. Все представленные в диссертационной работе алгоритмы и методы реализованы в составе оптимизирующего компилятора языков высокого уровня Си, Си++, Фортран для микропроцессора «Эльбрус» и Sparc V9. Эффективность предложенных методов подтверждена замерами производительности на задачах из пакетов SPEC CPU92, SPEC CPU95, SPEC CPU2000, а также на функциях высокопроизводительной библиотеки EML.

Апробация

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

• на V международной научно-практической конференции «Современные информационные технологии и ИТ-образование» , Москва, МГУ, 2010 г.;

• on The IASTED International Conference on Informatics «Parallel and Distributed Computing and Systems» , Marina del Rey, USA, 2010;

• на V международной конференции «Параллельные вычисления и задачи управления» , Москва, ИПУ РАН, 2010 г.;

• на XLIX научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, 2006 г.;

• на XLVIII научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, 2005 г.

Публикации

По теме диссертации опубликовано 8 печатных работ, одна из которых - в журнале списка ВАК:

1. Ермолицкий A.B., Шлыков С.Л. Автоматическая векторизация циклов со сложным управлением // сборник избранных трудов V международной научно-практической конференции «Современные информационные технологии и ИТ-образование» , М.: ИНТУИТ.РУ, 2010, С. 604-611;

2. Mukhanov L., Ilyin Р., Shlykov S., Ermolitsky A., Breger A., Grabezhnoy A. Thread-level Automatic Parallelization in the Elbrus Optimizing Compiler // Proceedings of the The IASTED International Conference on Informatics «Parallel and Distributed Computing and Systems» , ACTA Press, Marina del Rey, USA, 2010;

3. Ермолицкий A.B., Нейман-заде М.И. Методы повышения эффективности автоматической векторизации вычислений // труды V международной конференции «Параллельные вычисления и задачи управления» , ИПУ РАН, 2010;

4. Ермолицкий A.B. Методы повышения эффективности векторизации в оптимизирующем компиляторе // Вопросы радиоэлектроники, №3, 2010, С. 41-50;

5. Ермолицкий A.B., Шлыков C.J1. Автоматическая векторизация выражений оптимизирующим компилятором // Приложение к журналу «Информационные технологии» №11, 2008, С. 17-21;

6. Ермолицкий A.B. Развитие метода автоматической векторизации циклов оптимизирующим компилятором // Труды XLIX научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, 2006, С. 48;

7. Ермолицкий A.B. Автоматическая векторизация условных выражений оптимизирующим компилятором // Труды XLVIII научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, 2005, С. 57;

8. Волконский В.Ю., Ермолицкий A.B., Ровинский Е.В. Развитие метода векторизации циклов при помощи оптимизирующего компилятора // Высокопроизводительные вычислительные системы и микропроцессоры №8, 2005, С. 34-56.

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

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

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

3.5. Выводы

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

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

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

4. Исследовано влияние описанных в данной главе алгоритмов на производительность задач из пакетов SPEC CINT и SPEC CFP. В результате экспериментальных исследований было установлено, что предложенные алгоритмы вспомогательных преобразований позволяют увеличить производительность рассмотренных приложений в среднем на 25%. Максимальное ускорение на отдельных задачах составило 83%.

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

6. Исследовано влияние описанных алгоритмов на рост размера кода. Средняя величина роста размера кода составила 1.5% для задач SPEC и 63% для функций библиотеки EML.

Заключение

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

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

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

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

3. Разработан новый алгоритм векторизации циклов с произвольными разветвлениями управления и боковыми выходами, что позволило получить прирост производительности до 83% и 117% на тестах пакетов SPEC CINT92 и SPEC CINT95 соответственно, а также - до 9.76 раз на функциях высокопроизводительной библиотеки векторных вычислений EML.

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

5. Разработан новый алгоритм скрутки раскрученных вручную циклов, позволивший улучшить эффективность автоматической векторизации до 11% на тестах пакета SPEC CINT2000.

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

Все представленные в диссертационной работе алгоритмы и методы реализованы в составе оптимизирующего компилятора с языков Си, Си++ и Фортран для микропроцессоров <Эльбрус» и Sparc V9 и играют важную роль в получении эффективного кода для этих вычислительных систем. Замеры производительности выполнялись на вычислительном комплексе <Эльбрус-ЗМ1» . Разработанные методы и алгоритмы могут быть адаптированы и использоваться для различных микропроцессоров, содержащих короткие векторные инструкции.

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

1. Ren, G. Wu, P., Padua, D. A preliminary study on the vectorization of multimedia applications for multimedia extensions. 1. 16th International Workshop of Languages and Compilers for Parallel Computing, pp 420-435. 2003

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

3. MCST. Elbrus Math Library. Electronic resource]. 2007. http: / / mossigplan.acm.org/EMLintroductionengl.pdf

4. Lee, R.B. Accelerating multimedia with enhanced microprocessors. IEEE Micro, volume 15, № 2:pp 22-32. 1995

5. Lee, R.B. Subword parallelism with max-2. IEEE Micro, volume 16, № 4:pp 51-59. 1996

6. Tremblay, M., O'Connor, J.M., Narayanan, V., He, L. Vis speeds new media processing. IEEE Micro, volume 16, № 4:pp 10-20. — 1996

7. Diefendorff, K., Dubey, P.K., Hochsprung, R., Scales, H. Altivec extension to powerpc accelerates media processing. IEEE Micro, volume 20, № 2:pp 85-95. 2000

8. Oberman, S., Favor, G., Weber, F. Amd 3dnow! technology: Architecture and implementations. IEEE Micro, volume 19, № 2:pp 37-48. — 1999

9. Peleg, A., Weiser, U. Mmx technology extension to the intel architecture. IEEE Micro, volume 16, № 4:pp 42-50. 1996

10. Thakkar, S.T., Huff, T. Internet streaming simd extensions. Computer, volume 32, № 12:pp 26-34. 1999

11. Raman, S.K., Pentkovski, V., Keshava, J. Implementing streaming simd extensions on the pentium iii processor. IEEE Micro, volume 20, № 4:pp 47-57. 2000

12. Hinton, G., Sager, D., Upton, M., Boggs, D., Carmean, D., Kyker, A., Roussel, P. The microarchitecture of the pentium 4 processor. Intel Technology Journal, volume 5, № 1. 2001

13. Boggs, D., Baktha, A., Hawkins, J., Marr, D.T., Miller, J.A., Roussel, P., Singhai, R., Toll, B., „ Venkatraman, K. The microarchitecture of the intel pentium 4 processor on 90nm technology. Intel Technology Journal, volume 8, № 1. 2004

14. Coke, J., Baliga, H., Cooray, N., Gamsaragan, E., Smith, P., Yoon, K., Abel, J., Valles, A. Improvements in the intel core 2 processor family architecture and microarchitecture. Intel Technology Journal, volume 12, № 3. — 2008

15. Espasa, R., Valero, M., Smith, J.E. Vector architectures: past, present and future. ICS '98: Proceedings of the 12th international conference on Supercomputing, pp 425-432. ACM, New York, NY, USA, 1998

16. Intel Corporation. Intel 64 and IA-32 Architectures Optimization Reference Manual Electronic resource]. — November 2009. www.intel.com/assets / pdf/manual /248966.pdf

17. Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M Electronic resource], — December 2009. www.intel.com/assets/pdf/manual/253666.pdf

18. Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2B: Instruction Set Reference, N-Z Electronic resource]. — December 2009. www.intel.com/assets/pdf/manual/253667.pdf

19. Larsen, S., Amarasinghe, S. Exploiting superword level parallelism withmultimedia instruction sets. SIGPLAN Not., volume 35, № 5:pp 145-156. — 2000

20. Larsen, S. Compilation techniques for short-vector instructions, phdthesis, Cambridge, MA, USA. — 2006. Adviser-Amarasinghe, Saman P.

21. Moving Picture Experts Group. MPEG Standart Electronic resource]. — 2010. http://mpeg.chiariglione.org/

22. Allen, R., Kennedy, K. Automatic translation of fortran programs to vector form. ACM Trans. Program. Lang. Syst., volume 9, № 4:pp 491-542. — 1987

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

24. Bilardi, G., Pingali, K. The static single assignment form and its computation, techreport. — 1999

25. Bilardi, G., Pingali, K. Algorithms for computing the static single assignment form. J. ACM, volume 50, № 3:pp 375-425. 2003

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

27. Cheong, G., Lam, М. An optimizer for multimedia instruction sets. Proceedings of the Second SUIF Compiler Workshop, http://www-suif.stanford.edu/suifconf/suifconf2. 1997

28. DeVries, D.J. A Vectorizing SUIF Compiler: Implementation and Performance, mthesis, Toronto, Ontario, Canada. — June 1997

29. Weiss, M. Strip mining on simd architectures. ICS '91: Proceedings of the 5th international conference on Supercomputing, pp 234-243. ACM, New York, NY, USA, 1991

30. Iancu, C., Chen, W., Yelick, K. Performance portable optimizations for loops containing communication operations. ICS '08: Proceedings of the 22nd annual international conference on Supercomputing, pp 266-276. ACM, New York, NY, USA, 2008

31. Kirsten, M. Loop Nest Optimization for SIMD Architectures, phdthesis. — 2008

32. Sreraman, N., Govindarajan, R. A vectorizing compiler for multimedia extensions. International Journal of Parallel Programming, volume 28:pp 363400. 2000

33. Krall, A., Lelait, S. Compilation techniques for multimedia processors. Int. J. Parallel Program., volume 28, № 4:pp 347-361. — 2000

34. Kennedy, K., Allen, J.R. Optimizing compilers for modern architectures: a dependence-based approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001

35. Bik, A.J.C., Girkar, M., Grey, P.M., Tian, X. Automatic intra-register vectorization for the intel architecture. Int. J. Parallel Program., volume 30, № 2:pp 65-98. 2002

36. Dantzig, G.B., Eaves, B.C. Fourier-motzkin elimination and its dual. J. Comb. Theory, Ser. A, volume 14, № 3:pp 288-297. 1973

37. Schrijver, A. Theory of linear and integer programming. John Wiley & Sons, Inc., New York, NY, USA, 1986

38. Rugina, R., Rinard, M. Pointer analysis for multithreaded programs. PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, pp 77-90. ACM, New York, NY, USA, 1999

39. Polychronopoulos, C.D. Parallel Programming and Compilers. Kluwer Academic Publishers, Norwell, MA, USA, 1988

40. Zima, H., Chapman, В. Supercompilers for parallel and vector computers. ACM, New York, NY, USA, 1991

41. Allen, J.R., Kennedy, K., Porterfield, C., Warren, J. Conversion of control dependence to data dependence. POPL '83: Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pp 177-189. ACM, New York, NY, USA, 1983

42. August, D.I., Hwu, W.m.W., Mahlke, S.A. A framework for balancing control flow and predication. MICRO 30: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, pp 92-103. IEEE Computer Society, Washington, DC, USA, 1997

43. Park, J.C.H., Schlansker, M. On predicated execution. — May 1991

44. Дроздов, А., Новиков, С., Шилов, В. Эффективный алгоритм преобразования потока управления в поток данных. Приложение к журналу «Информационные технологии», , № 2. — 2005

45. Волконский, В., Ермолицкий, А., Ровинский, Е. Развитие метода векторизации циклов при помощи оптимизирующего компилятора. Информационные технологии и вычислительные системы, , № 8:рр 34-56. — 2005

46. Bik, A.J.C., Girkar, М., Grey, P.M., Tian, X. Automatic detection of saturation and clipping idioms. LCPC, pp 61-74. 2002

47. Shin, J., Hall, M., Chame, J. Superword-level parallelism in the presence of control flow. CGO 05: Proceedings of the international symposium on Code generation and optimization, pp 165-175. IEEE Computer Society, Washington, DC, USA, 2005

48. Волконский, В., Дроздов, А., Ровинский, E. Метод использования мелкоформатных векторных операций в оптимизирующем компиляторе. Информационные технологии и вычислительные системы, , № 3:рр 63-77. — 2004

49. Eichenberger, A.E., Wu, P., O'Brien, K. Vectorization for simd architectures with alignment constraints. SIGPLAN Not., volume 39, № 6:pp 82-93. 2004

50. Wu, P., Eichenberger, A.E., Wang, A., Zhao, P. An integrated simdization framework using virtual vectors. ICS '05: Proceedings of the 19th annual international conference on Supercomputing, pp 169-178. ACM, New York, NY, USA, 2005

51. Bik, A.J.C. The Software Vectorization Handbook: Applying Intel Multimedia Extensions for Maximum Performance. Intel Press, 2004

52. Ермолицкий, А., Шлыков, С. Автоматическая векторизация выражений оптимизирующим компилятором. Приложение к журналу -^Информационные технологии:», , № И. — 2008

53. Wolfe, M.J. High Performance Compilers for Parallel Computing. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1995

54. Aho, A.V., Sethi, R., Ullman, J.D. Compilers: principles, techniques, and tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986

55. Волконский, В., Тихонов, В., Мареев, Е. Семантические конверторы в составе компиляторов. Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, , № 2:рр 21-37. — 2001

56. Дроздов, А., Степаненков, А. Технология оптимизации циклов для архитектур с аппаратной поддержкой конвейеризации. Информационные технологии и вычислительные системы, , № 3:рр 52-62. — 2004

57. Blume, W., Eigenmann, R. Demand-driven, symbolic range propagation. In Proceedings of the 8th Workshop on Languages and Compilers for Parallel Computing, pp 141-160. Springer Verlag, 1995

58. Bae, H., Eigenmann, R. Interprocedural symbolic range propagation for optimizing compilers. — 2005

59. Филиппов, А. Развитие метода нумерации значений. Программирование, , № 3:рр 54-68. 2010

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

61. Дроздов, А., Корнев, Р., Боханко, А. Индексный анализ зависимостей по данным. Информационные технологии и вычислительные системы, , № 3:рр 27-37. 20041. Список иллюстраций

62. Принцип работы инструкции векторного сложения.13

63. Общий вид выражения, содержащего зависимость по памяти. Здесь X некоторый массив; f, g и F - некоторые функции.19

64. Пример векторизации выражения, содержащего зависимость по памяти.20

65. Пример векторизации на основе раскрутки.22

66. Пример динамического разрыва зависимости по памяти.24

67. Метод векторизации индуктивной переменной.25

68. Метод векторизации редукции.25

69. Пример изоморфных и частично изоморфных выражений . 28

70. Пример частичной векторизации на уровне линейного участка . . 29

71. Пример слияния пар инструкций из PackSet.31

72. Пример формирования PackSet.32

73. Пример векторизации условного кода методом битового маскирования .36

74. Пример векторизации идиом вычисления максимума.37

75. Пример векторизации кода с разветвлением управления на уровне линейного участка.39

76. Использование динамической проверки выровненности.43

77. Пример выравнивания инструкций при помощи открутки итераций цикла.45

78. Пример применения выборочной открутки итераций цикла . 47

79. Пример массива с длиной измерения, не кратной длине вектора . 48

80. Общая схема оптимизирующей компиляции.54

81. Пример низкоуровневого промежуточного представления.56

82. Пример генерации специализированной векторной инструкции . . 58

83. Пример формирования OriginTable на фазе раскрутки циклов . . 60

84. Пример генерации векторных инструкций.62

85. Базовый алгоритм векторизации цикла.63

86. Алгоритм эвристики векторизации, раскрутки цикла и векторизации выражения.65

87. Пример векторизации цикла с доминирующей рекуррентностью . 66

88. Пример векторизации инструкции сдвига.69

89. Метод векторизации сложной редукции.70

90. Метод векторизации сдвига в памяти.72

91. Алгоритм генерации векторной инструкции в рекуррентном выражении .73

92. Пример векторизации изоморфных рекуррентных выражений . . 75

93. Алгоритм векторизации линейного участка.76

94. Схождение потоков данных в исходном цикле .80

95. Пример вычисления векторных предикатов дуг .81

96. Пример вычисления векторных предикатов и сведения потоков данных.83

97. Алгоритм выделения условного выражения.85

98. Алгоритм векторизации условного выражения.86

99. Пример векторизации инструкции записи под условием.87

100. Пример циклов с боковыми выходами.89

101. Расширенный алгоритм векторизации цикла.90

102. Пример неправильной векторизации цикла с боковым выходом . . 91

103. Пример векторизации цикла с боковым выходом.93

104. Прирост производительности за счет векторизации на задачах SPEC .94

105. Прирост производительности за счет векторизации на отдельных функциях EML (выровненные данные) .96

106. Прирост производительности за счет векторизации на отдельных функциях EML (невыровненные данные).97

107. Пример одношаговых инструкций и кортежей.101

108. Пример вычисления рэ-формы адреса инструкции.107

109. Пример выравнивания инструкций цикла.110

110. Пример цикла, все инструкции обращения к памяти которого входят в одну группу.111

111. Пример выравнивания вектора при помощи частичной открутки итераций цикла.113

112. Алгоритм частичной открутки итераций цикла.114

113. Пример скрутки раскрученного программистом цикла .117

114. Алгоритм скрутки цикла.118

115. Пример использования динамического арбитра.120

116. Прирост производительности за счет векторизации на задачах SPEC .122

117. Средний прирост производительности за счет векторизации на функциях EML.123

118. Рост размера кода в результате применения векторизации на задачах SPEC.125