Список сокращений ................................................................................................................................ 5
Введение .................................................................................................................................................. 6
Глава 1. Оптимизирующие преобразования программ для ускорения целевых алгоритмов ....... 22
1.1. Элементы теории преобразования программ.......................................................................... 22
1.2. Анализ информационных зависимостей в гнёздах циклов с помощью решетчатых графов ............................................................................................................................................................ 25
1.3. Анализ векторов расстояний информационных зависимостей на основе решетчатых графов ................................................................................................................................................ 28
1.4. Анализ гнёзд циклов итерационного типа с использованием решетчатых графов ............ 38
1.5. Описание некоторых используемых в работе преобразований программ ........................... 40
1.5.1. Перестановка циклов (Loop Interchange) .......................................................................... 40
1.5.2. Гнездование цикла (Loop Nesting) ..................................................................................... 41
1.5.3. Скашивание циклов (Loop Skewing) ................................................................................. 41
1.5.4. Метод гиперплоскостей (Loop Wavefront) ....................................................................... 44
1.5.5. Тайлинг (Loop Tiling, Loop Blocking) ............................................................................... 46
1.5.6. Скошенный тайлинг (Skewed Loop Tiling) ....................................................................... 50
1.6. Оптимизирующая распараллеливающая система (ОРС) ....................................................... 52
1.7. Выводы к главе 1 ....................................................................................................................... 54
Глава 2. Алгоритм оптимизации итерационных гнёзд циклов ........................................................ 55
2.1. Вычисление параметров преобразований на основе анализа информационных зависимостей ..................................................................................................................................... 56
2.2. Применение тайлинга ................................................................................................................ 59
2.3. Перестановка циклов внутри тайла для повышения временнóй локальности данных ...... 61
2.4. Применение метода гиперплоскостей и прагм OpenMP для параллельного выполнения тайлов ................................................................................................................................................. 65
2.5. Эквивалентность алгоритма оптимизации итерационных гнёзд циклов ............................. 71
2.6. Перспективы развития и применения преобразований гнёзд циклов на основе ОРС ........ 72
2.6.1. Преимущества высокоуровневого внутреннего представления для реализации преобразований программ ............................................................................................................ 72
2.6.2. Распараллеливание на вычислительные системы с распределённой памятью ............. 73
2.7. Выводы к главе 2 ....................................................................................................................... 75
Глава 3. Оценка ускорения алгоритмов итерационного типа .......................................................... 76
3.1. Про выбор оптимальных размеров тайлов .............................................................................. 77
3.2. Условия сходимости алгоритмов итерационного типа.......................................................... 84
3.3. Оценка ускорения алгоритма Гаусса – Зейделя для решения задачи Дирихле уравнения Лапласа .............................................................................................................................................. 84
3.4. Оценка ускорения алгоритма Гаусса – Зейделя для решения задачи Дирихле уравнения Пуассона ............................................................................................................................................ 87
3.5. Оценка ускорения алгоритма решения задачи теплопроводности ....................................... 88
3.6. Влияние перестановки циклов внутри тайла на ускорение алгоритма Гаусса – Зейделя для решения обобщённой задачи Дирихле ........................................................................................... 90
3.7. Сравнение с оптимизирующей распараллеливающей системой PLUTO ............................ 93
3.8. Об оптимальной цепочке преобразований .............................................................................. 95
3.9. Выводы к главе 3 ..................................................................................................................... 103
Глава 4. Реализация метода диалогового анализа текстов программ на базе ОРС ..................... 104
4.1. Символьный анализ ................................................................................................................. 104
4.2. Линеаризация выражений ....................................................................................................... 105
4.3. Примеры работы «диалогового анализатора» ...................................................................... 106
4.3.1. Уточнение информационных зависимостей для распараллеливания программ ........ 106
4.3.2. Уточнение информационных зависимостей для применения алгоритма оптимизации итерационных гнёзд циклов ....................................................................................................... 130
4.3.3. Уточнение условий выполнения тайлинга ..................................................................... 131
4.3.4. Диалоговое выполнение гнездования цикла .................................................................. 132
4.4. Сравнение динамического и диалогового подходов к оптимизации программ ................ 136
4.4.1. Пример динамического распараллеливания .................................................................. 136
4.4.2. «Диалоговый анализатор» учитывает возможность переполнения ............................. 137
4.4.3. «Диалоговый анализатор» учитывает возможность изменения погрешности ........... 137
4.5. Выводы к главе 4 ..................................................................................................................... 138
Заключение ......................................................................................................................................... 139
Библиография ..................................................................................................................................... 141
Приложения ........................................................................................................................................ 153
Приложение А. Свидетельство о государственной регистрации программы для ЭВМ ............. 153
Приложение Б. Сертификат участника Молодёжной конференции студентов и аспирантов в рамках «НСКФ-2018» ........................................................................................................................ 154
Приложение В. Сертификат участника летней школы Intel “Intel Summer Internship” ............... 155
Приложение Г. Диплом победителя полуфинала Студенческой лиги Международного инженерного чемпионата “CASE-IN” .............................................................................................. 156
Приложение Д. Конфигурация ЭВМ ................................................................................................ 157
Приложение Е. Гнездо циклов преобразованного с помощью ОРС алгоритма Гаусса – Зейделя для решения задачи Дирихле (листинг 3.3.1); d1, d2, d3 – размеры тайлов ................................. 158
Приложение Ж. Внутреннее гнездо преобразованного с помощью ОРС алгоритма Гаусса – Зейделя для решения обобщённой задачи Дирихле (листинг 3.6.1); d1, d2, d3 – размеры тайлов .............................................................................................................................................................. 162
Приложение З. Гнездо циклов, полученное с помощью PLUTO, для алгоритма Гаусса – Зейделя для решения обобщённой задачи Дирихле ...................................................................................... 164
Приложение И. Результаты оптимизации алгоритма Гаусса – Зейделя для решения задачи Дирихле уравнения Лапласа. Размерность задачи – 256 х 4000 х 4000. Компилятор – GCC, опция компилятора – -О3. Время выполнения исходного алгоритма – 10,915 сек. .................... 165
Приложение К. Результаты оптимизации алгоритма Гаусса – Зейделя для решения задачи Дирихле уравнения Лапласа. Размерность задачи – 256 х 4000 х 4000. Компилятор – ICC, опция компилятора – -О3. Время выполнения исходного алгоритма – 16,835 сек. ............................... 166
Приложение Л. Результаты оптимизации алгоритма Гаусса – Зейделя для решения задачи Дирихле уравнения Лапласа. Размерность задачи – 256 х 4002 х 4002, тип данных – double. Компилятор – GCC, опция компилятора – -О3. Время выполнения исходного алгоритма – 11,2024 сек........................................................................................................................................... 168
Приложение М. Результаты оптимизации алгоритма Гаусса – Зейделя для решения задачи Дирихле уравнения Пуассона. Размерность задачи – 256 х 4000 х 4000. Время выполнения исходного алгоритма – 14,7464 сек. ................................................................................................. 169
Приложение Н. Результаты оптимизации алгоритма решения задачи теплопроводности. Размерность задачи – 128 х 4000 х 4000. Время выполнения исходного алгоритма – 4,3616 сек. Одинарная точность ........................................................................................................................... 171
Приложение О. Результаты оптимизации алгоритма решения задачи теплопроводности. Размерность задачи – 128 х 4000 х 4000. Время выполнения исходного алгоритма – 5,5922 сек. Двойная точность ............................................................................................................................... 173
Приложение П. Результаты оптимизации алгоритма Гаусса – Зейделя для решения обобщённой задачи Дирихле без использования перестановки циклов внутри тайла. Размерность задачи – 256 х 2000 х 2000. Время выполнения исходного алгоритма – 7,0792 сек. .................................. 175
Приложение Р. Результаты оптимизации алгоритма Гаусса – Зейделя для решения обобщённой задачи Дирихле без использования циклов внутри тайла. Размерность задачи – 256 х 2000 х 2000. Время выполнения исходного алгоритма – 7,0792 сек. .................................. 177
Приложение С. Результаты оптимизации программы (листинг 3.8.1). Размерность задачи – 256 х 4000 х 4000 при помощи алгоритма оптимизации итерационных гнёзд циклов, без применения преобразований «линеаризация» и «вынос общих инвариантных выражений». Время выполнения исходного алгоритма – 25,24 сек. .................................................................... 179
Приложение Т. Результаты оптимизации программы (листинг 3.8.1). Размерность задачи – 256 х 4000 х 4000 при помощи алгоритма оптимизации итерационных гнёзд циклов, с использованием преобразований «линеаризация» и «вынос общих инвариантных выражений». Время выполнения исходного алгоритма – 25,24 сек. .................................................................... 181
