автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы автоматической векторизации на этапе компиляции для архитектур с поддержкой коротких векторных инструкций

УДК 004.4416 На правах рукописи

Ермолицкий Александр Викторович

МЕТОДЫ АВТОМАТИЧЕСКОЙ ВЕКТОРИЗАЦИИ НА ЭТАПЕ КОМПИЛЯЦИИ ДЛЯ АРХИТЕКТУР С ПОДДЕРЖКОЙ КОРОТКИХ ВЕКТОРНЫХ ИНСТРУКЦИЙ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 2 МАЙ 2011

Москва - 2011

4845989

Работа выполнена в ОАО <ИНЭУМ» им. И.С.Брука.

Научный руководитель:

кандидат физико-математических наук Нейман-заде Мурад Искендер-оглы

Официальные оппоненты:

доктор физико-математических наук, старший научный сотрудник Галатенко Владимир Антонович кандидат технических наук Чернис Евгений Натанович

Ведущая организация:

Защита состоится

г

ОАО «Институт точной механики и вычислительной техники им. С.А.Лебедева»

ЫЛ-01ЛА

2011 г. в

14

часов на заседании

диссертационного совета Д 409.009.01 при ОАО «Институт электронных управляющих машин им. И.С.Брука» , расположенном по адресу: 119334, г.Москва, ул.Вавилова д.24

С диссертацией можно ознакомиться в библиотеке ОАО «ИНЭУМ им. И.С.Брука» .

Автореферат разослан «2.^ » О^^ИЛЯ 2011 г.

Ученый секретарь

диссертационного совета,

кандидат технических наук, профессор

Красовский В.Е.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фортран для микропроцессора «Эльбрус» и 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 печатных работ, одна из которых -в журнале списка ВАК.

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

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

Содержание работы

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

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

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

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

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

2. Методы векторизации на уровне цикла. Используется раскрутка цикла (дублирование итераций цикла) с последующей заменой в цикле групп изоморфных скалярных инструкций соответствующими векторными инструкциями. При этом фазы раскрутки и генерации инструкций тесно взаимосвязаны.

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

Далее рассматриваются известные методы повышения эффективности автоматической векторизации за счет выравнивания адресов обращений к памяти. Инструкция обращения к памяти является выровненной, если адрес ячейки памяти, к которой она обращается, кратен формату инструкции. В результате векторизации формат инструкций обращения к памяти увеличивается, из-за чего эти инструкции могут стать невыровненными. В зависимости от архитектуры, обращение по невыровненному адресу приводит к возникновению блокировки либо исключительной ситуации. Для решения данной проблемы существуют известные вспомогательные преобразования, такие как открутка итераций цикла (Loop Peeling), динамические проверки выровненности с созданием версий цикла (Align Versioning) и дополнение массивов (Array Padding). Эти преобразования, выполняемые перед векторизацией, выравнивают либо динамически проверяют выровненность инструкций обращения к памяти, что позволяет значительно повысить эффективность автоматической векторизации во многих случаях.

Несмотря на свое многообразие, исследованные методы векторизации и вспомогательные преобразования имеют ряд недостатков.

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

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

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

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

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

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

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

Расширение применимости алгоритма автоматической векторизации к циклам с произвольными разветвлениями управления основывается на понятии векторного предиката (ВП) - вектора, элементы которого хранят предикатные значения. При векторизации каждой дуге/узлу управляющего графа исходного цикла ставится в соответствие ВП, j-ый элемент которого хранит значение true на г-ой итерации векторизованного цикла, если по соответствующей дуге или в соответствующий узел передается управление на fc-ой итерации исходного цикла (к = г * Lv + j, Lv - количество элементов ВП), и false в противном случае.

В отличие от традиционных векторных машин, современные процессоры общего назначения не поддерживают предикатное исполнение векторных инструкций. Вместо этого они предоставляют другой механизм поддержки вычислений с разветвлениями управления. В большинстве современных векторных расширений ВП представляет собой битовую маску - обычный векторный регистр, элемент которого заполняется единичными битами в случае значения true и нулевыми в случае значения false. Векторные предикаты вырабатываются инструкциями векторного сравнения, над ними определены основные булевы операторы (AND, OR, NOT и т.п.).

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

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

удаления в работе предложен ряд локальных оптимизаций векторных предикатных вычислений. Наряду с более чем 30 шаблонными преобразованиями, такими как X - ((Х&С)|(У&!С)) {X - У)&!С (где X и Г- произвольные вектора, а С - векторный предикат), выполняется оптимизация предикатных вычислений на основе построения дизъюнктивных нормальных форм (ДНФ) и последующего их упрощения с помощью правил булевой логики.

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

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

изменения, вызванные реорганизацией кода.

Реализация алгоритма векторизации циклов с разветвлениями управления и боковыми выходами позволила повысить производительность в 1.83 раза на задаче O23.eqntott (пакет тестов SPEC CINT92) и в 2.17 раз на задаче 124.m88ksim (SPEC CINT95). Эти целочисленные задачи содержат циклы с боковыми выходами, на которые приходится значительная часть времени исполнения.

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

x = f(x,g(i)) (1)

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

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

беременная, изменяющаяся на инвариантную величину на каждой итерации цикла

(как скалярные, так и векторные) заменяются реальными, доступными в целевой архитектуре.

Кроме того, в работе показано, что данный подход может быть использован для векторизации некоторых рекуррентных выражений, не представи-мых в виде (1). В частности, был предложен метод векторизации оператора сдвига массива в памяти, основанный на использовании фиктивной инструкции сдвига. Предложенный метод векторизации сложных рекуррентностей позволил на 11% увеличить производительность задачи 256.bzip2 из пакета SPEC CINT2000.

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

Практическая применимость предложенных в главе алгоритмов и методов исследовалась также на 373 функциях библиотеки EML(Elbrus Math Library), реализующих наиболее распространенные операции над векторами и матрицами. Предложенный алгоритм векторизации позволил дополнительно ускорить функции EMLb среднем2 на 6.3% по сравнению с известными алгоритмами; на отдельных функциях показатель роста производительности составил до 9.76 раз.

2 для усреднения использовалось среднее геометрическое

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

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

Формально задача выравнивания может быть сформулирована следующим образом. Имеется цикл, содержащий М инструкций обращения к памяти, часть из которых (возможно, все) могут быть невыровненными. Каждая инструкция имеет некоторый вес Wi, характеризующий величину накладных расходов на ее векторизацию в случае, когда она является невыровненной. Требуется выполнить вспомогательные (выравнивающие) преобразования, минимизирующие сумму:

м

У^ XiWi —* min, (2)

«=i

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

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

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

Алгоритм нахождения групп инструкций с одинаковой выровненно-стью базируется на использовании техники PS-форм (форма сумм произведений, Product Sums Form). PS-формой называется полином вида: Со + cixhixlt2...xifo + ... + СпХпдхп>2...хп^, где со, съ ..., Сп - некоторые константы, a Xij - результаты некоторых инструкций. В работе доказывается возможность представления адреса любой инструкции обращения к памяти в виде PS-формы в случае представления программы в форме SSA (форма статического единственного присваивания, Static Single Assignment). Показывается, каким образом с помощью представления адреса в виде PS-формы можно определить выровненность адреса и эквивалентность выровненности адресов двух инструкций. Использование PS-форм позволяет значительно увеличить эффективность алгоритма поиска инструкций с эквивалентной выравненностью.

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

3Вес группы равен сумме весов входящих в нее инструкций

4Изменение (шаг) адреса которых за итерацию цикла равно формату инструкции

возникает при работе с комплексными числами, мнимая и действительная часть которых хранится в одном массиве. Для формального описания подобной ситуации необходимо ввести понятие кортежа - множества инструкций чтения/записи одинакового формата, обращающихся к смежным ячейкам памяти: {a[i], a[i+l], a[i+2j, ..., a[i+k-l]}, где a - некоторый массив, а к - длина кортежа. Классическая открутка итераций цикла позволяет выровнять кортеж, только если следующее уравнение имеет целочисленное решение х для любых т (0 < т < Lv):

т + Sx —О mod L„ (3)

где гп - величина невыровненное™ первой инструкции кортежа, S - шаг адреса инструкций кортежа за итерацию цикла, х - количество откручиваемых итераций цикла, Lv - длина векторных регистров (все параметры измеряются в числе элементов векторных регистров). Уравнение (3) имеет решение для произвольного гп, если S и Lv являются взаимно простыми. Поскольку для всех современных архитектур Lv = 2" (п > 1), то выравнивание инструкций путем открутки итераций цикла возможно только для кортежа с нечетным шагом S. Это условие выполняется не всегда, например, при работе с комплексными числами S является четным.

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

Реализация предложенного алгоритма выравнивания, способного вырав-

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

В определенных случаях получению заметного эффекта от вспомогательных преобразований препятствует практикуемая программистами в целях оптимизации «ручная раскрутка» (дублирование тела) цикла. Для конкретной архитектуры она может не дать предполагаемого результата и препятствовать работе других оптимизаций. В частности, для таких циклов невозможно применение большинства вспомогательных преобразований, необходимых для эффективной векторизации. Для решения данной проблемы в работе предложен метод скрутки цикла - преобразование, обратное раскрутке цикла. Алгоритм скрутки основан на поиске изоморфных выражений в цикле и удалении созданных программистом копий тела цикла. Он выполняется перед остальными вспомогательными преобразованиями. Реализация предложенного метода в оптимизирующем компиляторе позволило достичь ускорения на 11% задачи 256.bzip2 из пакета тестов SPEC CINT2000.

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

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

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

Реализация динамического арбитра позволила существенно увеличить эффективность автоматической векторизации на функциях библиотеки ЕМ1.. Средний прирост производительности составил 43%.

Заключение

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

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

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

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

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

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

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

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

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

Список работ, опубликованных по теме диссертации

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

2. Mukhanov L., Ilyin P., 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. Ермолицкий А.В., Нейман-заде М.И. Методы повышения эффективности автоматической векторизации вычислений // труды V международ-

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

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

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

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

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

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

Подписано в печать 21 апреля 2011 г. Объем 1,2 п.л. Тираж 100 экз. Заказ №324 Отпечатано в Центре оперативной полиграфии ООО «Ол Би Принт» Москва, Ленинский пр-т, д. 37

Введение.

Глава 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» . Разработанные методы и алгоритмы могут быть адаптированы и использоваться для различных микропроцессоров, содержащих короткие векторные инструкции.

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