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

• Автор: Ермолицкий, Александр Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 138 с. : ил.

Содержание
Введение

Глава 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. Выводы.
Заключение
Литература


V международной научно-практической конференции «Современные информационные технологии и ИТ-образование» , Москва, МГУ, г. V международной конференции «Параллельные вычисления и задачи управления» , Москва, ИПУ РАН, г. XLIX научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, г. HaXLVIII научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, г. Ермолицкий A. B., Шлыков С. Л. Автоматическая векторизация циклов со сложным управлением // сборник избранных трудов V международной научно-практической конференции «Современные информационные технологии и ИТ-образование» , М. ИНТУИТ. РУ, , С. Mukhanov L. Ilyin P. Shlykov S. Ermolitsky A. Breger A. Grabezhnoy A. Ермолицкий A. B., Нейман-заде М. Ермолицкий A. B. Методы повышения эффективности векторизации в оптимизирующем компиляторе // Вопросы радиоэлектроники, №3, , С. Ермолицкий A. B., Шлыков С. Л. Автоматическая векторизация выражений оптимизирующим компилятором // Приложение к журналу «Информационные технологии» №, , С. Ермолицкий A. B. Развитие метода автоматической векторизации циклов оптимизирующим компилятором // Труды XLIX научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, , С. Ермолицкий Л. В. Автоматическая векторизация условных выражений оптимизирующим компилятором // Труды XLVIII научной конференции «Современные проблемы фундаментальных и прикладных наук» , Москва, МФТИ, , С. Волконский В. Ю., Ермолицкий A. B., Ровинский Е. В. Развитие метода векторизации циклов при помощи оптимизирующего компилятора // Высокопроизводительные вычислительные системы и микропроцессоры №8, , С. Диссертация состоит из введения, трех глав и заключения. Список литературы составляет наименования. Объем диссертации составляет 8 страниц текста. Диссертация содержит рисунков. В главе 1 рассмотрены основные методы векторизации, описанные в литературе. Описаны короткие векторные инструкции, встречающиеся в современных микропроцессорах общего назначения. Проведено сравнение векторных инструкций, встречающихся в современных суперскалярных процессорах и традиционных векторных суперкомпьютерах. Приведен обзор существующих методов векторизации для современных микропроцессоров, а также вспомогательных преобразований, позволяющих повысить эффективность векторизации. Произведен анализ существующих методов, выявлены их основные недостатки. На основании проведенного анализа поставлена задача, решение которой позволит обеспечить повышение эффективности векторизации и вспомогательных преобразований. Глава 2 посвящена описанию нового алгоритма векторизации, который позволяет снять ограничения известных методов. Описано промежуточное представление компилятора, на уровне которого работают рассматриваемые методы. Предложены методы расширения данного алгоритма, для сложных рекуррентных выражений и ациклического кода. Предложен новый алгоритм векторизации циклов с произвольными разветвлениями управления и боковыми выходами. В заключительной части главы представлены экспериментальные результаты, демонстрирующие эффективность предложенных алгоритмов. Глава 3 посвящена вспомогательным преобразованиям, позволяющим повысить эффективность векторизации. Рассмотрены ограничения известных выравнивающих преобразований. Предложен усовершенствованный алгоритм выравнивающих преобразований, позволяющий выравнивать вектора инструкций обращения к памяти, используя минимальное количество проверок выровнен-ности и преобразований цикла. Предложен новый алгоритм частичной открут-ки итерации цикла для выравнивания кортежа инструкций обращения к памяти. Предложен новый алгоритм скрутки раскрученных программистом циклов, позволяющий применять к таким циклам выравнивающие преобразования. Предложен метод динамического арбитра, решающий проблему несоответствия профильной информации реальному исполнению программы. В заключительной части главы приведены результаты замеров эффективности предложенных алгоритмов. В заключении приводятся основные результаты диссертационной работы.