Постановка задачи

Одной из основных операций над матрицами является их перемножение. Эта операция используется практически везде: от компьютерной графики до расчета поверхностей самолетов.

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

Требуется реализовать последовательный и параллельный (Кэннона) алгоритмы. Реализацию параллельного алгоритма провести средствами MPI. Кроме того, необходимо провести сравнения времени работы последовательного и параллельного алгоритмов.

Описание алгоритма и метод решения

Наиболее простым методом решения поставленной задачи является последовательная схема перемножения матриц. Он представляется тремя вложенными циклами. Трудоемкость такого алгоритма О(n^3).

Double* A,B,C;

Int Size;

A= new * double [Size];

B= new * double [Size];

C= new * double [Size];

for (int i= 0; i < Size; i++)

{

A[i]= new double [Size];

B[i]= new double [Size];

C[i]= new double [Size];

}

for (int i= 0; i < Size; i++)

for (int j= 0; j < Size; j++)

{

A[i][j]= rand();

B[i][j]= rand();

C[i][j]= rand();

}

for (int i= 0; i < Size; i++)

for (int j= 0; j < Size; j++)

for (int k = 0; k < Size; k++)

C[i][j] = A[i][k] * B[k][j];

Алгоритм Кэннона

В первую очередь создается некоторое число Р исполняющих процессов. Это число должно быть полным квадратом. Процессы организуются в виртуальную декартову топологию. Исходные матрицы должны иметь размерность, кратную . Матрицы разбиваются на равное количество квадратных блоков. Блоки исходных матриц распределяются по исполняющим процессам. Затем для каждой строки i решетки подзадач блоки матрицы A сдвигаются на (i-1) позиций влево, для каждого столбца j решетки подзадач блоки матрицы B сдвигаются на (j-1) позиций вверх. Далее проводится итераций, во время которых сначала происходит перемножение блоков по методу трех вложенных циклов, и произведение складывается с текущим значением результирующего блока. Затем выполняется циклический сдвиг блоков матрицы А вдоль строк решетки и циклический сдвиг блоков матрицы В вверх по столбцам виртуальной решетки. После выполнения всех итераций результирующая матрица собирается из полученных на каждом процессе результирующих блоков.

Анализ эффективности

Алгоритм Кэнона требует q итераций. В ходе них, каждый процессор перемножает свои текущие блоки исходных матриц и формирует текущие значения своего блока в результирующей матрице (прибавляет свое полученное значение к исходному). Общее количество выполненных операций при этом будет иметь порядок . В результате получаем значение эффективности параллельной схемы перед последовательной:. Показатель эффективности будет иметь вид: . В соответствии алгоритмом на этапе инициализации проводится перераспределение блоков матриц A и B при помощи циклического сдвига матричных блоков по строкам и столбцам процессорной решетки. Трудоемкость передачи данных зависит от топологии сети. При топологии полного графа операции могут выполняться параллельно. Затраты на передачу блоков матриц A и B между процессорами во время выполнения итераций алгоритма тоже могут выполняться параллельно. Таким образом, время распределения матриц между процессами и время сдвига блоков матриц составляет: , где a - латентность, b - пропускная способность, w - размер элемента матрицы. Cложность выполнения скалярного умножения строки блока матрицы A на столбец блока матрицы B можно оценить как 2*(n/q)-1, количество строк и столбцов в блоках равно n/q. Трудоемкость операции блочного умножения равна . Для сложения блоков требуется операций. С учетом всех перечисленных выражений время выполнения вычислительных операций может быть оценено следующим образом: .Просуммировав все полученные соотношения, получим общее время выполнения алгоритма Кэннона: , где t - время выполнения скалярной операции.

Демонстрация

Алгоритм Кэннона

Результаты вычислительных экспериментов

CPU: AMD Athlon XP 6000+, 3.02 Ghz, RAM: 2 Гб RAM 800 MHz, Операционная система Microsoft Windows 7 Professional.

Латентность a – 37 мкс, пропускная способность b – 47,63 Мбайт/с, время выполнения скалярной операции t = 3 нс и величина w равна 8 байт.

Умножение матрицы на матрицу алгоритмом Кэннона

Размерность матрицы	Последовательный алгоритм, секунды	Алгоритм Кэннона
		Теоретические данные		Практические данные (тест проводился на 4х процессах)
		Tp, секунды	Sp	Tp, секунды	Sp
500	2,682453	0,712354	3,765618	0,609559	4,400648
1000	24,109888	7,165489	3,364723	7,889110	3,056097
1500	84,156007	23,954621	3,513143	24,504893	3,434253
2000	236,019478	56,534654	4,174775	57,258855	4,121973

Об автораx

Лабораторную работу выполнили студенты группы 8409 факультета ВМК: Макаров Дмитрий и Шилов Николай