Ленточный алгоритм

Алгоритм представляет собой итерационную процедуру, количество итераций которой совпадает с числом подзадач.

• На каждой итерации алгоритма каждая подзадача содержит по одинаковому количеству строк матрицы А и матрицы В
• При выполнении итерации проводится скалярное умножение содержащихся в подзадачах строк, что приводит к получению соответствующих элементов результирующей матрицы С
• По завершении вычислений в конце каждой итерации столбцы матрицы В должны быть переданы между подзадачами с тем, чтобы в каждой подзадаче оказались новые столбцы матрицы В и могли быть вычислены новые элементы матрицы C
• По завершении итераций строки собираются в единую матрицу C

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

Алгоритм Фокса

Пусть перемножаемые матрицы A и B имеют порядок n. Количество процессов является полноым квадратом, квадратный корень которого кратен n. В алгоритме Фокса матрицы разделяются среди процессов в виде клеток шахматной доски. При этом процессы рассматриваются как виртуальная двухмерная сетка, и каждому процессу назначена подматрица каждого множителя.
В конце работы полученные блоки собираются в единую матрицу.

Алгоритм состоит в следующем:

for(step = 0; step < q; step++)
{

• Выбрать подматрицу A в каждой строке
  для всех процессов
• В каждой строке для всех процессов разослать
  сетку подматриц, выбранную в этой строке для
  других процессов в этой строки
• В каждом процессе, перемножить полученную подматрицу
  A на подматрицу B, находящуюся в процессе
• В каждом процессе, отослать подматрицу B процессу,
  расположенному выше. (Для процессов первой строки
  отослать подматрицу в последнюю строку.)

}