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

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

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

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

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

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

 А_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.          одну горизонтальную полосу левого блока в разных ядрах процессора умножать на разные вертикальные полосы второго блока;

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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