Пример работы 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), то есть к непосредственно "верхнему" процессору. Процессоры нулевой строки посылают подматрицы процессорам последней (в данном случае второй) строки.

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

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

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

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

§ = +*

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

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

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

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

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

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

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

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

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

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