Параллельный алгоритм 2: метод Фокса…

Схема информационного взаимодействия

21 из 45

Параллельный алгоритм 2: метод Фокса…

Масштабирование и распределение подзадач по процессорам

–Размеры блоков могут быть подобраны таким образом,

чтобы общее количество базовых подзадач совпадало с числом процессоров p,

–Наиболее эффективное выполнение метода Фокса может быть обеспечено при представлении множества имеющихся процессоров в виде квадратной решетки,

–В этом случае можно осуществить непосредственное

отображение набора подзадач на множество процессоров - базовую подзадачу (i,j) следует располагать на процессоре

pi,j

22 из 45

Параллельный алгоритм 2: метод Фокса…

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

–Общая оценка показателей ускорения и эффективности

S p	n	2		p	E p	n2			1
						p (n	2
	n2 /
			p					/ p)

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

показателей ускорения и эффективности

23 из 45

Параллельный алгоритм 2: метод Фокса…

Анализ эффективности (уточненные оценки)

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

Tp calc q[(n2 / p) 2n / q 1 (n2 / p)]

- На каждой итерации алгоритма один из процессоров строки процессорной решетки рассылает свой блок матрицы A остальным

процессорам своей1	строки	q ( w(n	2	/ p) / )
Tp	comm log 2

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

процессорной решетки		2
2	comm w (n		p) /
Tp

Общее время выполнения параллельного алгоритма составляет

Tp q[(n2 / p) 2n / q 1 (n2 / p)] (q log2 q (q 1) )( w(n2 / p) / )

24 из 45

Параллельный алгоритм 2: метод Фокса…

Программная реализация…

–Начальный этап: Инициализация и распределение данных между процессорами:

•Создание новых коммуникаторов:

–размер процессорной решетки определяется при помощи функции MPI_Dims_create,

–Создание решетки производится при помощи функции

MPI_Cart_create

–Определение для каждого процесса координаты его положения в решетке: MPI_Cart_coords.

•Действия, связанные с инициализацией и распределением данных, выделены в отдельную функцию DataInitialization

Программа

25 из 45

Параллельный алгоритм 2: метод Фокса…

Программная реализация…

–Выполнение итерации: рассылка блоков матрицы A по

строкам процессорной решетки (функция

AblockCommunication )

•В каждой строке решетки определяется ведущий процесс Pivot, осуществляющий рассылку,

•Для рассылки используется блок pMatrixAblock, переданный в процесс в момент начального распределения данных,

•Выполнение операции рассылки блоков осуществляется при помощи функции MPI_Bcast (используется коммуникатор

RowComm)

Программа

26 из 45

Параллельный алгоритм 2: метод Фокса…

Программная реализация…

–Выполнение итерации: перемножение матричных блоков (функция BlockMultiplication)

•Блок матрицы А pAblock умножается на блок матрицы B pBblock, результат этого умножения прибавляется к блоку матрицы С pCblock

Программа

27 из 45

Параллельный алгоритм 2: метод Фокса…

Программная реализация

–Выполнение итерации: циклический сдвиг блоков матрицы B по столбцам процессорной решетки (функция BblockCommunication )

•Каждый процесс передает свой блок следующему процессу NextProc в столбце процессов,

•Каждый процесс получает блок, переданный из предыдущего процесса PrevProc в столбце решетки,

•Выполнение операций передачи данных осуществляется при помощи функции MPI_SendRecv_replace, которая

обеспечивает все необходимые пересылки блоков, используя при этом один и тот же буфер памяти pBblock

Программа

28 из 45

Параллельный алгоритм 2: метод Фокса…

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

–Сравнение теоретических оценок и экспериментальных данных

	Размер матриц	4 процессора
		Tp (модель)	Tp*
	500×500	0,5558	0,6417
	1000×1000	4,3056	4,6018
	1500×1500	14,3747	15,2201
	2000×2000	33,8881	35,9625

29 из 45

Параллельный алгоритм 2: метод Фокса

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

–Ускорение вычислений

		Параллельный алгоритм,
Размер	Последовательный	4 процессора
матриц	алгоритм
		Время	Ускорение
500×500	2,0628	0,6417	3,2146
1000×1000	16,5152	4,6018	3,5889
1500×1500	56,566	15,2201	3,7165
2000×2000	133,9128	35,9625	3,7237

30 из 45