Перемножение матриц. Алгоритм Кэннона.

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

Для выполнения задачи необходимо:

1. Реализовать последовательный алгоритм умножения матриц;

2. Реализовать алгоритм умножения матриц Кэннона, используя MPI для обеспечения параллелизма выполнения;

3. Выполнить теоретические оценки ускорения;

4. Провести серийные эксперименты, из которых рассчитать реальное ускорение (замедление) алгоритма.

Описание алгоритма

Пусть поставлена задача перемножения матриц А и В: C = A * B , где C,A,B — квадратные матрицы размером n*n.

Последовательный алгоритм

При последовательной реализации используется формула

Блочный алгоритм перемножения матриц

В блочном алгоритме матрицы разбиваются на блоки, представляющие собой подматрицы исходных матриц. При этом каждый блок Сij матрицы C определяется как произведение соответствующих блоков матриц A и B.

Алгоритм Кэннона перемножения матриц

Алгоритма Кэннона — блочный. Идея алгоритма состоит в изменении схемы начального распределения блоков перемножаемых матриц между процессорами вычислительной системы. Начальное расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы располагаемые блоки на процессорах могли бы быть перемножены без каких-либо дополнительных передач данных между процессорами. При этом подобное распределение блоков может быть организовано таким образом, что перемещение блоков между процессорами в ходе вычислений может осуществляться с использованием более простых коммуникационных операций. Этап инициализации алгоритма Кэннона включает выполнение следующих операций передач данных:

1. на каждый процессор pij передаются блоки Aij, Bij;

2. для каждой строки i процессорной решетки блоки матрицы A сдвигаются на (i-1) позиций влево;

3. для каждого столбца j процессорной решетки блоки матрицы B сдвигаются на (j-1) позиций вверх.

Отсюда следует, что для корректной работы алгоритма потребуется n*n=p процессов. Основной этап алгоритма Кэннона представляет из себя цикл, в котором производятся вычисления блоков матрицы С, а основные коммуникационные операции: циклический сдвиг влево блоков матрицы A и циклический сдвиг вверх блоков матрицы В. В итоге алгоритм Кэннона выглядит следующим образом:

1.1 Для всех строк, кроме первой, производится циклический сдвиг влево блоков матрицы A

1.2 Для всех столбцов, кроме первого, производится циклический сдвиг вверх блоков матрицы В.

2.1 Вычисляется C(i,j) = C(i,j) + A(i,j) * B(i,j)

2.2 Осуществляется цикл для i от 0 до n–1: для всех строк производится циклический сдвиг влево блоков матрицы A; для всех столбцов производится циклический сдвиг вверх блоков матрицы В; вычисляется C(i,j) = C(i,j) + A(i,j) * B(i,j).

Демонстрация

Схема перераспределения блоков матриц А и В

Теоретические оценки эффективности

Из уже выведеных оценок алгоритма определим:

Временные затраты на перемножение блоков:

Временные затраты на передачу блока:

Временные затраты всего параллельного алгоритма:

Ускорение: