Курс: Распараллеливающие преобразования программ

Общее

Содержание учебного материала

Раздел 1. Блочные вычисления

Тема 1.1. Оптимизация использования структуры памяти

Блочное перемножение матриц. Зависимость времени выполнения простых программ от соотношения времени вычислений ко времени обращений к памяти. Множественная сортировка. Неэффективность алгоритма Штрассена.

Тема 1.2. Модель времени выполнения программы на вычислительной системе

Архитектура современных процессоров. Сложность вычислений по обращениям к памяти.

Тема 1.3. Алгоритмы блочных вычислений.

Тайлинг. Решетчатые графы. Косой тайлинг. Слияние циклов для уменьшения кэш-промахов.

Раздел 2. Преобразования программ

Тема 2.1. Графовые модели программ

Управляющий граф программы. Граф вызовов функций. Граф информационных связей. Граф зависимостей по данным.

Тема 2.2. Преобразования линейных участков и циклов

Подстановка. Протягивание констант. Перестановка блоков.

Канонизация цикла. Раскрутка цикла. Развертка цикла. Гнездования цикла. Разбиение цикла. Приведение цикла к разбиваемому виду. Слияние циклов.

Тема 2.3. Распараллеливание циклов

Распараллеливание циклов на архитектуру MIMD.

Распараллеливание циклов на архитектуру SIMD.

Конвейеризация циклов.

Вопросы, выносимые на самостоятельное изучение

Применение преобразований в компиляторах с открытым кодом LLVM, GCC.

Полезные материалы

Учебник по преобразованиям программ

Как из последовательной программы сделать параллельную?

Диалоговый высокоуровневый оптимизирующий распараллеливатель

Быстрые программы = архитектуро-ориентированные алгоритмы и данные

Проблемы создания эффективного параллельного программного обеспечения

Задачи оптимизирующей компиляции для процессоров близкого будущего

Задания на разработку блочных и параллельных программ перемножения блочных треугольных матриц

Блочная верхнее-треугольная матрица имеет вид

А_1,1	А_1,2	А_1,3	…	А_1,N
0	А_2,2	А_2,3	…	А_2,N
...	…	…	…	…
…	…	…	…	…
0	0	0	…	А_N,N

Диагональные блоки являются верхне-треугольными матрицами.

Блочная нижнее-треугольная матрица выглядит аналогично.

Треугольные матрицы хранятся в памяти в виде одномерного массива, в котором подряд выписываются либо строки, либо столбцы. Блочная треугольная матрица также должна храниться в виде одномерного массива, в котором подряд выписываются блочные строки или блочные столбцы. При этом, элементы каждого блока должны лежать в памяти рядом. Элементы каждого блока размещаются, согласно стандарту языка Си, построчно.

При размещении указанной на рисунке блочной верхнее-треугольной матрицы поблочно построчно блоки расположатся в памяти в следующей последовательности:

А_1,1 , А_1,2 ,…, А_1,_N , А_2,1 , …, А_2,_N ,…, А_N_,N

При размещении этой же матрицы поблочно по столбцам блоки расположатся в памяти в следующей последовательности:

А_1,1 , А_1,2 , А_2,2 , А_1,3 , …, А_1,_N ,…, А_N_,N

Симметричные матрицы хранятся в памяти как треугольные (либо нижняя, либо верхняя).

Определить зависимость времени выполнения произведения матриц от размера блока. Построить таблицу с результатами численных экспериментов. Построить график зависимости.

Рассмотреть размеры матриц N = 1440 и 2880 (у этих чисел много делителей). Рассматривать размеры блоков, которые являются делителями размера матриц: 1, 6, 10, 15, 20, 24, 30, 36, 40, 50, 60, 72, 80, 96, 120, 144, 160, 180, 240, 360, 480, 720.

Для случая N = 1440 рассмотреть типы элементов матриц float и double и сравнить быстродействие, а для случая N = 2880 только double.

Использовать 2 разных компилятора, например, MS-VStudio и С++ семейства GCC. Пробовать разные опции компилятора.

Рассмотреть и сравнить по производительности разные способы распараллеливания.

параллельно выполнять перемножение двух блоков

1.1. одну горизонтальную полосу левого блока в разных ядрах процессора умножать на разные вертикальные полосы второго блока;

1.2. разные горизонтальные полосы левого блока в разных ядрах процессора умножать на разные вертикальные полосы второго блока;

в разных вычислительных ядрах параллельно выполнять произведения разных пар блоков.

2.1. один блок левой матрицы в разных ядрах процессора умножать на разные блоки правой матрицы;

2.2. разные блоки левой матрицы в разных ядрах процессора умножать на разные блоки правой матрицы;

Рассмотреть скалярное (не блочное) размещение данных и блочное перемножение. Сравнить результаты с аналогичным перемножением и блочным размещением.

Определить размер блока, при котором время выполнения минимально. Определить диапазон размеров блоков, в котором значения времени выполнения несущественно отличаются от минимального.

Проверить корректность (правильность) работы программы.

Отчет оформить в соответствии с ГОСТ 7.32, ГОСТ 19.301-79 ЕСПД (госты старые, но актуальные).

Пример

Задание 15. Умножения треугольной и прямоугольной матриц

Написать программу блочного умножения двух матриц C = A*B.

Матрица A прямоугольная. Хранится в виде одномерного массива по блочным столбцам.

Матрица B нижне -треугольная. Хранится в виде одномерного массива по блочным строкам.

Распараллелить блочную программу умножения двух матриц C = A*B с использованием технологии OpenMP двумя способами

· Распараллелить каждое перемножение блоков.

· Параллельно выполнять операции над различными блоками.

Определить оптимальные размеры блоков в обоих случаях.

Провести численные эксперименты и построить таблицу сравнений времени выполнения различных программных реализаций решения задачи. Определить лучшие реализации.

Проверить корректность (правильность) программ.

Конец Задания.

Примечание. Своевременное и качественное выполнение задания оценивается в 55 баллов. За задержку в сроках сдачи Отчета по программе снимается 10 баллов.

Пример тестовых заданий

Пример 1. Фрагмент программы

10 X(K) = A(I+1)

15 X(K) = 1

20 B = X(K)

равносилен ?

10 X(K) = A(I+1)

15 X(K) = 1

20 B = A(I+1)

Пример 2. Фрагмент программы

X = I+1

K = I-1

равносилен следующему ?

K = I-1

X = I+1

Пример 3. Фрагмент программы

DO 99 I = 1, 100

IF Y(I)<0 goto 99

K(I) = X(I-1)

99 CONTINUE

DO 88 I = 1, 100

X(I) = A(I+1)

88 CONTINUE

эквивалентен следующему циклу?

DO 99 I = 1, 100

IF Y(I)<0 goto 99

X(I) = A(I+1)

K(I) = X(I-1)

99 CONTINUE

Пример 4. Цикл

DO 99 I = 1, 100

99 X(I) = A(I+1)+K(I)-X(I-1)

эквивалентен следующему ?

DO 99 J = 1, 50

I = 2*J

X(I-1) = A(I)+K(I-1)-X(I-2)

99 X(I) = A(I+1)+K(I)-X(I-1)

Пример 5. Можно ли распараллелить на архитектуру SIMD цикл

DO 99 I = 1, 100

X(I) = A(I)+5

99 A(I) = X(I)+1

Примечание. Тестирование проводится письменно, каждый студент получает лист с пятью тестами по преобразованию программ. Отрицательные ответы следует письменно аргументировать.

За правильное выполнение тестового задания можно получить максимум 45 баллов – по 9 баллов за каждый тест. В тестовом задании приводится 5 тестов. При некорректных аргументах в ответе возможно снижение оценки.

Тематический план

Общее

Содержание учебного материала

Задания на разработку блочных и параллельных программ перемножения блочных треугольных матриц

Пример тестовых заданий