Введение
ГЛАВА 1. Распараллеливащие/оптимизирующие преобразования программ 19
1.1 Об исследованиях распараллеливания программ 20
1.2. Информационная зависимость в программе 29
I .3. Корректность преобразований 35
1.4. Преобразования программ. 38
1.4.1. Перестановка фрагментов 38
1.4.2 Канонизация циклов 40
1.4.3. Раскрутка цикла. 42
1.4.4. Расщепление одномерного цикла, 44
1.4.5. Разрыв итераций, гнездование цикла и подобные им преобразования 46
1.4.6. Развертка цикла 50
1.4.7. Расщепление вершин (Введение временных массивов) 52
1.4.8. Растягивание скаляров (Замена переменной массивом) 53
1.4.9. Разбиение цикла 54
1.4.10. Слияние циклов 56
1.4.11. Приведение цикла к разбиваемому виду , 58
1.5. Преобразования индексных переменных в многомерных циклах 66
1.5.1. Информационная зависимость в многомерных циклах 67
1.5.2. Расщепление многомерных циклов 70
1.5.3. Подстановка вперед 72
1.5.4. Подстановка 76
1.5.5. Переименование переменных 80
Выводы к первой главе 93
ГЛАВА 2. Распараллеливание рекуррентных циклов 94
2.1. Циклы с рекуррентно вычисляемыми переменными 96
2.2. Распараллеливание линейных рекуррентных циклов и решение слау с треугольными ленточными матрицами 100
2.3. Циклы с нелинейной рекуррентной зависимостью 106
2.4. Постоянные линейные рекуррентные зависимости 109
2.5. Принцип сдваивания для вычисления рекуррентных циклов 116
2.6. Параллельное вычисление рекуррентных циклов с опережающим вычислением коэффициентов 125
2.7. Распараллеливание рекуррентных циклов с условными операторами 133
2.7.1. Частично рекуррентные циклы с условными операторами 134
2.7.2. Вычисление суперпозиции условных операторов 138
2.7.3. Обобщение вычисления минимального элемента массива 142
Выводы ко второй главе 149
ГЛАВА 3. Влияние пересылок данных на эффективность параллельных вычислений 150
3.1. Об оптимальном количестве процессоров при параллельном вычислении программных циклов 150
3.1.1. Устройства для обменов данными 151
3.1.2. Размещение массивов ,..„ 154
3.1.3. Рекуррентное вычисление массивов данных 155
3.1.4. Вычисление циклов при горизонтальном размещении данных 157
3.1.5. Вычисление скалярных переменных . 159
3.1.6. Остальные циклы и программы 161
3.1.7. Возможность вычислений без пересылок данных при параллельном решении матричных задач 163
3.2. Оптимальные параллельные переразмещения многомерных массивов 168
3.2.1. Пересылки данных .172
3.2.2. Вспомогательные теоретико-числовые результаты 174
3.2.3. Преобразования циклов 177
3.2.4. Преобразования массива на суперкомпьютере с универсальным коммутатором 179
3.2.5. Преобразования массива на суперкомпьютере с кольцевой сетью... 181
Выводы к третьей главе 185
ГЛАВА 4. Распараллеливание программ для суперкомпьютеров с архитектурой перестраиваемого конвейера 187
4.1. Автоматическая синхронизация конвейера при распараллеливании циклов 190
4.1.1. Граф вычислений программы 190
4.1.2. Граф вычислений и информационные зависимости 192
4.1.3. Отображение цикла на архитектуру компьютера 198
4.1.4. Синхронизация конвейера 199
4.2. Отображение программных циклов на перестраиваемый конвейер 208
4.2.1. Предварительные преобразования перед конвейеризацией 208
4.2.2. Разбиение программы на кадры 215
4.2.3. Двумерная конвейеризация , , 217
4.2.4. Распараллеливание рекуррентных циклов для суперкомпьютера со структурно-процедурной реализацией вычислений 223
4.3. Бесконфликтные размещения массивов для суперкомпьютеров со структурно-процедурной организацией вычислений 229
4.3.1. Определения, обозначения и постановка задачи 230
4.3.2. Размещение массивов для оптимального выполнения циклов 234
4.3.3. Размещение массивов для оптимального выполнения развертки цикла 239
4.3.4. Размещение массивов в пересекающихся множествах сегментов памяти.. 242
4.3.5. Расширение класса индексных выражений 245
4.3.6. Основной алгоритм размещения данных ..248
4.3.7. Улучшения разбиения множества массивов 250
4.3.8. Вычисление множества бесконфликтных размещений массива с самим собой , 252
4.3.9. Совместные бесконфликтные размещения двух массивов 255
4.3.10. Совместные бесконфликтные размещения нескольких массивов 256
Выводы к четвертой главе 259
ГЛАВА 5. Открытая распараллеливающая система 261
5.1 Структура открытой распараллеливающей системы 262
5.1.1. Библиотека преобразований программ 264
5.1.2. Архитектурно ориентированные комбинации преобразований 267
5.1.3. Внутреннее представление 275
5.1.4. Анализ информационных зависимостей .277
5.1.5. Размещение данных и разбивка программы 280
5.1.6. Канонический вид операторов и выражений 280
5.2 Другие элементы и особенности системы 2s3
5.2Л. Отладка и тестирование модулей системы 283
5.2.2. Метол проб и ошибок при автоматическом распараллеливании 284
5.2.3. Программная реализация 290
5.2.4. Полуавтоматическое распараллеливание 292
5.2.5. Обучающая программа на основе ОРС 296
5.2.6. Сравнение ОРС с системой POLARIS 297
5.2.7. Дополнительные возможности ОРС 299
Выводы к пятой главе 304
Заключение 306
Список литературы
