Пример работы Fox's алгоритма

Рассмотрим работу Fox's алгоритма на примере умножения матриц 6-го порядка на 9-ти процессорах, то есть n=6, а р=9. В этом случае каждому процессору назначается подматрица порядка n/(р^1/2) = 2 от каждой из матриц А, В и С и Fox's алгоритм выполняет умножение матриц за р^1/2 = 3 этапа:

Этап 0 (шаг 1 (слева), шаг 2 (по центру), шаг 3 (справа)):

На начальном этапе происходит рассылка подматриц, стоящих на главной диагонали, процессорам, работающим с подматрицами в той же строке. Далее на каждом процессоре происходит умножение полученной диагональной подматрицы на подматрицу , хранящуюся на данном процессоре. Результат умножения помещается в подматрицу процессора (i, j). Здесь i, j изменяются от 0 до 2. Перед переходом к следующему этапу происходит перемещение подматрицы от процессора (i, j) к процессору (i-1 j), то есть к непосредственно "верхнему" процессору. Процессоры нулевой строки посылают подматрицы процессорам последней (в данном случае второй) строки.

Этап 1 (слева) и этап 2 (справа):  

На первом этапе также происходит рассылка, но только уже подматриц, где q = р^1/2 = 3, а i изменяется от 0 до 2. То есть процессоры нулевой, первой и второй строк получат подматрицы, и А₂,₀ соответственно. Далее на каждом процессоре происходит умножение полученной подматрицы на подматрицу полученную на предыдущем этапе от процессора непосредственно нижней строки. Результат умножения складывается с подматрицей и снова в нее записывается. Перед переходом к следующему этапу снова происходит восходящее перемещение подматриц , аналогичное их перемещению на этапе 0.

Второй(ив данном случае последний) этап работы Fox's алгоритма полностью аналогичен предыдущим этапам и может быть описан следующей последовательностью шагов:

§ рассылка подматрицы процессорам i-той строки (на рисунке эти подматрицы выделены)

§ умножение на процессоре (i, j) подматриц и (Понятно, что в общем случае, подматрицы на данном этапе и предыдущем не совпадают)

§ = +*

Заметим также, что перемещение подматриц на последнем этапе является излишним. После заключительного этапа мы получим 9 подматриц , которые будут составлять матрицу С, являющуюся решением данной задачи.

Варианты заданий

№ Варианта	Алгоритм умножения	Размер матрицы	Число процессоров
	Ленточный	10х10
	Фокс	16х16
	Ленточный	20х20
	Фокс	16х16
	Ленточный	10х10
	Фокс	16х16
	Ленточный	20х20
	Фокс	16х16
	Ленточный	10х10
	Фокс	16х16
	Ленточный	20х20
	Фокс	10х10
	Ленточный	16х16
	Фокс	20х20

Содержание отчета

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

· Подготовка 8 различных наборов исходных данных

· Текст параллельной программы на языке С.

· Результаты запуска программы на одном узле, время выполнения.

· Результаты запуска программы на нескольких узлах, время выполнения.

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

· Рекомендации по улучшению быстродействия программы.

Список литературы

1. Дональд Э.Кнут. Искусство программирования, т.3. Сортировка и

поиск 2-е изд.: Пер. с английского – М.: Издательский дом «Вильямс»,

2001.

2. Параллельные алгоритмы сортировки больших объемов данных, М.В. Якобовский, 2004, Учебный курс Intel WinterSchool.

Дата добавления: 2014-12-26