Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Глава 1. Распараллеливание программ в модели многогранников . . . 12
1.1 Подходы к распараллеливанию гнезд циклов . . . . . . . . . . . . . 12
1.2 Базовые понятия модели многогранников . . . . . . . . . . . . . . . 15
1.3 Этапы распараллеливания линейной программы . . . . . . . . . . . 18
1.3.1 Анализ зависимостей по данным . . . . . . . . . . . . . . . 18
1.3.2 Нахождение расписания вычислений . . . . . . . . . . . . . 19
1.3.3 Нахождение размещения вычислений и данных . . . . . . . 20
1.3.4 Разбиение операций программы на зерна вычислений
(тайлинг) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.5 Генерация кода . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Общие выводы по главе . . . . . . . . . . . . . . . . . . . . . . . . . 23
Глава 2. Метод нахождения пространственных и временных
отображений программ линейного класса для
распараллеливания гнезд циклов . . . . . . . . . . . . . . . . . 24
2.1 Аффинные отображения. Критерий оптимальности . . . . . . . . . 24
2.2 Одномерные аффинные расписания вычислений . . . . . . . . . . . 28
2.3 Многомерные аффинные расписания вычислений . . . . . . . . . . 31
2.4 Одномерные аффинные размещения вычислений . . . . . . . . . . 32
2.5 Одномерные аффинные размещения вычислений и данных.
Случай явно заданного расположения данных . . . . . . . . . . . . 36
2.6 Пример: распараллеливание LU-разложения . . . . . . . . . . . . . 41
2.7 Общие выводы по главе . . . . . . . . . . . . . . . . . . . . . . . . . 44
Глава 3. Инструментальная поддержка распараллеливания
программ линейного класса . . . . . . . . . . . . . . . . . . . . . 45
3.1 Организация информационного обмена между параллельными
процессами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Постобработка программного кода на языке C . . . . . . . . . . . . 51
3.2.1 Расстановка директив OpenMP . . . . . . . . . . . . . . . . . 52
3.2.2 Подготовка параллельных циклов для MPI . . . . . . . . . . 53
3
Стр.
3.2.3 Расстановка конструкций информационного обмена . . . . . 54
3.2.4 Оптимизация ветвлений . . . . . . . . . . . . . . . . . . . . 56
3.3 Транслятор ilpy: архитектура и возможности . . . . . . . . . . . . . 58
3.3.1 Полиэдральное представление программы OpenSCOP . . . 64
3.3.2 Анализ зависимостей по данным и обработка
многогранников зависимостей . . . . . . . . . . . . . . . . . 67
3.3.3 Формирование ограничений для зависимостей по данным . 70
3.3.4 Формирование ограничений для доступов к массивам . . . . 75
3.3.5 Нахождение расписания вычислений . . . . . . . . . . . . . 79
3.3.6 Нахождение размещения вычислений и данных . . . . . . . 81
3.3.7 Генерация программного кода . . . . . . . . . . . . . . . . . 85
3.4 Общие выводы по главе . . . . . . . . . . . . . . . . . . . . . . . . . 87
Глава 4. Экспериментальные исследования производительности
параллельных программ . . . . . . . . . . . . . . . . . . . . . . 88
4.1 Тестовая среда: сборка и запуск приложений . . . . . . . . . . . . . 88
4.2 LU-разложение квадратной матрицы . . . . . . . . . . . . . . . . . . 91
4.2.1 Распараллеливание с OpenMP . . . . . . . . . . . . . . . . . 91
4.2.2 Распараллеливание с MPI . . . . . . . . . . . . . . . . . . . . 93
4.3 Матричное произведение atax . . . . . . . . . . . . . . . . . . . . . 96
4.3.1 Распараллеливание с OpenMP . . . . . . . . . . . . . . . . . 96
4.3.2 Распараллеливание с MPI . . . . . . . . . . . . . . . . . . . . 101
4.4 Процедура syr2k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.4.1 Распараллеливание с OpenMP . . . . . . . . . . . . . . . . . 109
4.4.2 Распараллеливание с MPI . . . . . . . . . . . . . . . . . . . . 111
4.5 Алгоритм Флойда–Уоршалла . . . . . . . . . . . . . . . . . . . . . . 114
4.5.1 Распараллеливание с OpenMP . . . . . . . . . . . . . . . . . 114
4.5.2 Распараллеливание с MPI . . . . . . . . . . . . . . . . . . . . 117
4.6 Процедура gramschmidt . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.6.1 Распараллеливание с OpenMP . . . . . . . . . . . . . . . . . 121
4.6.2 Распараллеливание с MPI . . . . . . . . . . . . . . . . . . . . 123
4.7 Общие выводы по главе . . . . . . . . . . . . . . . . . . . . . . . . . 126
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4
Стр.
Словарь терминов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Список рисунков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Приложение А. Утилиты для поддержки тестовых запусков программ . 153
А.1 Библиотека макросов информационного обмена blockdist.h . . . . . 153
А.1.1 Вспомогательные конструкции и распределение массивов . 153
А.1.2 Обработка линейных массивов и строк матриц . . . . . . . . 157
А.1.3 Обработка столбцов матриц . . . . . . . . . . . . . . . . . . 162
А.1.4 Локализация результатов вычислений . . . . . . . . . . . . . 165
А.2 Скрипты сборки и запуска приложений . . . . . . . . . . . . . . . . 167
А.3 Реализация линейного конгруэнтного генератора . . . . . . . . . . . 171
А.4 Работа с памятью и измерение времени выполнения программ . . . 172
А.5 Макросы cloog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Приложение Б. Распараллеливание программы lu на языке C . . . . . . 176
Б.1 Описание программы . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Б.2 Журнал трансляции ilpy . . . . . . . . . . . . . . . . . . . . . . . . . 177
Б.3 Результат работы ilpy . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Б.4 Преобразования pluto . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Б.5 Статистика запусков lu (OpenMP) . . . . . . . . . . . . . . . . . . . 183
Б.6 Статистика запусков lu (MPI) . . . . . . . . . . . . . . . . . . . . . . 184
Приложение В. Распараллеливание программы atax на языке C . . . . 189
В.1 Описание программы . . . . . . . . . . . . . . . . . . . . . . . . . . 189
В.2 Журнал трансляции ilpy . . . . . . . . . . . . . . . . . . . . . . . . . 190
В.3 Результат работы ilpy . . . . . . . . . . . . . . . . . . . . . . . . . . 193
В.4 Преобразования pluto . . . . . . . . . . . . . . . . . . . . . . . . . . 211
В.5 Статистика запусков atax (OpenMP) . . . . . . . . . . . . . . . . . . 219
В.6 Статистика запусков atax (MPI) . . . . . . . . . . . . . . . . . . . . . 220
Приложение Г. Распараллеливание программы syr2k на языке C . . . . 235
5
Стр.
Г.1 Описание программы . . . . . . . . . . . . . . . . . . . . . . . . . . 235
Г.2 Журнал трансляции ilpy . . . . . . . . . . . . . . . . . . . . . . . . . 236
Г.3 Результат работы ilpy . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Г.4 Преобразования pluto . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Г.5 Статистика запусков syr2k (OpenMP) . . . . . . . . . . . . . . . . . 243
Г.6 Статистика запусков syr2k (MPI) . . . . . . . . . . . . . . . . . . . . 244
Приложение Д. Распараллеливание программы floyd на языке C . . . . 249
Д.1 Описание программы . . . . . . . . . . . . . . . . . . . . . . . . . . 249
Д.2 Журнал трансляции ilpy . . . . . . . . . . . . . . . . . . . . . . . . . 250
Д.3 Результат работы ilpy . . . . . . . . . . . . . . . . . . . . . . . . . . 251
Д.4 Преобразования pluto . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Д.5 Статистика запусков floyd (OpenMP) . . . . . . . . . . . . . . . . . . 255
Д.6 Статистика запусков floyd (MPI) . . . . . . . . . . . . . . . . . . . . 256
Приложение Е. Распараллеливание программы gramschmidt на
языке C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Е.1 Описание программы . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Е.2 Журнал трансляции ilpy . . . . . . . . . . . . . . . . . . . . . . . . . 262
Е.3 Результат работы ilpy . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Е.4 Преобразования pluto . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Е.5 Статистика запусков gramschmidt (OpenMP) . . . . . . . . . . . . . 291
Е.6 Статистика запусков gramschmidt (MPI) . . . . . . . . . . . . . . . . 291
Приложение Ж. Специальные возможности ilpy: оценка аффинных
отображений инструкций . . . . . . . . . . . . . . . . . . 294
