Блочная
верхнее-треугольная матрица имеет вид
|
А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 баллов.