Распараллеливание циклов допускающих рекуррентные зависимости

• Автор: Штейнберг, Олег Борисович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Ростов-на-Дону
• Количество страниц: 116 с. : ил.

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

Глава 1 Понятия и определения теории графов и теории распараллеливания программ

1.1 Используемые в работе сведения теории графов

1.2 Граф информационных связей

1.3 ОРв.ДВОР

1.4 Используемые в работе понятия из теории преобразования программ

1.5 Условия распараллеливания циклов на основные параллельные архитектуры

1.6 Выводы к первой главе

Глава 2 «Разбиение цикла»

2.1 «Разбиение цикла» без использования вспомогательных преобразований

2.2 Приведение цикла к «разбиваемому» виду
2.2.1 Использование «перестановки операторов» для «разбиения цикла»
2.2.2 Использование преобразования «введение временных массивов» для «разбиения цикла»
2.2.3 «Растягивание скаляров» для «разбиения цикла»
2.2.4 «Обобщенное растягивание скаляров» для «разбиения цикла»
2.2.5 «Подстановка вперед» для «разбиения цикла»
2.3 Алгоритм «разбиения цикла» использующий «перестановку операторов», «введение временных массивов», «растягивание скаляров» и «повышение размерности массива»
2.4 «Слияние циклов»
2.5 Выводы ко второй главе

Глава 3 Распараллеливание программных циклов, использующее вспомогательные преобразования
3.1 Векторизация программных циклов
3.2 Распараллеливание рекуррентных циклов
3.2.1 Векторизация рекуррентных циклов
3.2.2 Распараллеливание циклов с линейной рекуррентной зависимостью
3.2.3 Совместное применение распараллеливания и векторизации циклов с линейной рекуррентной зависимостью
3.2.4 Распараллеливание рекуррентных циклов предварительными вычислениями суперпозиций
3.3 Использование «разбиения» при распараллеливании циклов
3.4 Выводы к третьей главе
Заключение
Список литературы

СПИСОК СОКРАЩЕНИЙ
ВУ - вычислительное устройство
ДВОР - диалоговый высокоуровневый оптимизирующий распараллеливатель
ОРС - оптимизирующая распараллеливающая система
ПЛИС - программируемая логическая интегральная схема
AVX - Advanced Vector Extensions - набор векторных команд, оперирующих
с 256-битными регистрами
MIMD - many instructions, multiple data
OPS - Optimizing parallelization system
SIMD - single instructions, multiple data
SSE - Streaming SIMD Extensions
SUIF - Stanford University Intermediate Format
DVM - distributed virtual machine
VLIW - very long instruction word

MIMD - many instructions, multiple data SIMD - single instructions, multiple data
Распараллеливание на данные виды архитектур было хорошо описано еще в 1974 году в работе Лэмпорта [60]. В этой работе Лэмпорт рассматривает параллельное выполнение программных циклов языка ФОРТРАН. Под распараллеливанием цикла понимается одновременное выполнение его итераций. Рассмотрено два способа параллельного выполнения цикла: синхронное и асинхронное.
Для асинхронного выполнения цикла используется обозначение:
Листинг 1.23. Асинхронное выполнение цикла.
DO 99 CONC FOR ALL I е S 99 loopbody (I)
CONC - сокращение от CONCURRENTLY
Асинхронное выполнение циклов соответствует современному выполнению на MIMD архитектуре, в частности, на многоядерных процессорах или высокопроизводительных кластерах. Для корректного асинхронного выполнения цикла необходимо, чтобы в теле цикла не было циклически порожденных зависимостей.
Для синхронного выполнения цикла используется обозначение:
Листинг 1.24. Синхронное выполнение цикла.
DO 99 SIM FOR ALL I S S 99 loopbody(I)
SIM - сокращение от SIMULTANEOUSLY (одновременно)
SIMD вычисления синхронны. На современных процессорах они представлены поддержкой выполнения векторных команд. К известным компьютерам прошлых лет с архитектурой SIMD относятся ILLIAC IV, Cray 1 и успешный отечественный суперкомпьютер ПС-2000. Синхронные