Постановка задачи
Даны квадратные матрицы A и B размерности n x n. Необходимо реализовать параллельный алгоритм вычисляющий произведение матриц: C = A x B
Метод решения
Последовательный алгоритм умножения матриц реализуется по определению:
Параллельная схема
Для данной задачи удобно использовать блочные операции. Матрица A может быть представлена в виде блочной матрицы размерности q x q. Каждый блок A_ij имеет размерность (n/q) x (n/q). Рассмотрим две квадратные матрицы A и B размерности n x n, разделенные на p блоков. p = q²
Каждому процессу соответствует один блок матрицы.
Для вычисления блока C_ij необходимо знать значения блоков A_ik и B_kj (k = 0 … q):
Изображение 1. Данные необходимые для вычисления блоков результирующей матрицы.
Распределим вычисления процессов в строке на шаги. На каждом шаге все процессы будут использовать разные блоки. После перемножения текущих блоков процессы обмениваются по очереди блоками, каждый процесс получает блок, который раньше им не использовался.
В начале вычислений необходимо распределить блоки таким образом, чтобы каждый процесс P_ij получил те блоки, которые необходимы для вычисления подматрицы C_ij. Необходимо переместить все блоки A_ij влево на i позиций с переносом, а блоки B_ij вверх на j позиций с переносом.
Далее повторять до тех пор, пока не будут перемножены все q пар блоков:

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

Анализ эффективности Время распределения данных для двух матриц: где a – латентность, B – пропускная способность среды передачи, w – размер элемента матрицы.

Время выполнения операции перемножения блоков: t – время выполнения одной операции.

Время передача данных между процессорами при выполнении основной части алгоритма:
Время сбора блоков данных результирующей матрицы со всех процессов:
Количество итераций равно q, следовательно, общее время будет вычисляться по формуле:
Демонстрация
Результаты вычислительных экспериментов Конфигурация: Intel Core2 CPU 6420 (2.13GHz), 1.00GB RAM.

Размер матриц	Время работы (мс)				Ускорение
	Последовательный алгоритм	Параллельный алгоритм
		Количество процессов	Теоретическое время	Практическое время
600	1438	4	432	406	3.5419
		9	192	468	3.0736
1800	58 657	4	11 664	29 719	1.9737
		9	5 184	27 110	2.1637
2400	149 766	4	27 648	72 203	2.0742
		9	12 288	74 812	2.0018

Об авторах Работу выполнили: Гудков Сергей, Замыслов Сергей, группа 8410.