Параллельный алгоритм 3: метод Кэннона…
Распределение данных – Блочная схема
A B C
X 
= 
Базовая подзадача - процедура вычисления всех элементов одного из блоков матрицы С
|
A A ...A |
|
|
|
B B ...B |
|
|
C |
00 |
C |
01 |
...C |
0q 1 |
|
|
|
q |
|
|||||||
|
00 01 |
0q 1 |
|
|
|
00 01 |
0q 1 |
|
|
|
|
|
|
|
|
, |
Cij |
|
Ais Bsj |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
A |
A |
...A |
|
B |
B |
...B |
|
c |
q 10 |
C |
q 11 |
...C |
q 1q 1 |
|
|
|
s 1 |
|
||||||
|
q 10 |
q 11 |
q 1q 1 |
|
|
q 10 q 11 |
q 1q 1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||
31 из 45
Параллельный алгоритм 3: метод Кэннона…
Выделение информационных зависимостей
–Подзадача (i,j) отвечает за вычисление блока Cij, все подзадачи образуют прямоугольную решетку размером qxq,
–Начальное расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы располагаемые блоки в подзадачах могли бы быть перемножены без каких-либо дополнительных передач данных:
•в каждую подзадачу (i,j) передаются блоки Aij, Bij,
•для каждой строки i решетки подзадач блоки матрицы A сдвигаются на (i-1) позиций влево,
•для каждого столбца j решетки подзадач блоки матрицы B сдвигаются на (j-1) позиций вверх,
–процедуры передачи данных являются примером операции
циклического сдвига
32 из 45
Параллельный алгоритм 3: метод Кэннона…
Перераспределение блоков исходных матриц на начальном этапе выполнения метода
A0,0 |
|
A0,1 |
|
A0,2 |
|
A0,0 |
|
A0,1 |
|
A0,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B0,0 |
|
B0,1 |
|
B0,2 |
|
B0,0 |
|
B1,1 |
|
B2,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C0,0=0 |
|
C0,1=0 |
|
C0,2=0 |
|
C0,0=0 |
|
C0,1=0 |
|
C0,2=0 |
A1,0 |
|
A1,1 |
|
A1,2 |
|
A1,1 |
|
A1,2 |
|
A1,0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1,0 |
|
B1,1 |
|
B1,2 |
|
B1,0 |
|
B2,1 |
|
B0,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C1,0=0 |
|
C1,1=0 |
|
C1,2=0 |
|
C1,0=0 |
|
C1,1=0 |
|
C1,2=0 |
A2,0 |
|
A2,1 |
|
A2,2 |
|
A2,2 |
|
A2,0 |
|
A2,1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B2,0 |
|
B2,1 |
|
B2,2 |
|
B2,0 |
|
B0,1 |
|
B1,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C2,0=0 |
|
C2,1=0 |
|
C2,2=0 |
|
C2,0=0 |
|
C2,1=0 |
|
C2,2=0 |
|
|
|
|
|
|
|
|
|
|
|
33 из 45
Параллельный алгоритм 3: метод Кэннона…
Выделение информационных зависимостей
–В результате начального распределения в каждой базовой подзадаче будут располагаться блоки, которые могут быть перемножены без дополнительных операций передачи данных,
–Для получения всех последующих блоков после выполнения операции блочного умножения:
•каждый блок матрицы A передается предшествующей подзадаче влево по строкам решетки подзадач,
•каждый блок матрицы В передается предшествующей подзадаче вверх по столбцам решетки.
34 из 45
Параллельный алгоритм 3: метод Кэннона…
Масштабирование и распределение подзадач по процессорам
–Размер блоков может быть подобран таким образом, чтобы количество базовых подзадач совпадало с числом имеющихся процессоров,
–Множество имеющихся процессоров представляется в
виде квадратной решетки и размещение базовых подзадач (i,j) осуществляется на процессорах pi,j (соответствующих узлов процессорной решетки)
35 из 45
Параллельный алгоритм 3: метод Кэннона…
Анализ эффективности
–Общая оценка показателей ускорения и эффективности
S p |
n2 |
|
p |
E p |
n2 |
|
1 |
n2 / |
|
|
|
||||
|
p (n2 |
|
|||||
|
p |
|
/ p) |
||||
Разработанный способ параллельных вычислений позволяет достичь идеальных
показателей ускорения и эффективности
36 из 45
Параллельный алгоритм 3: метод Кэннона…
Анализ эффективности (уточненные оценки)
- Алгоритм Кэннона отличается от метода Фокса только видом выполняемых в ходе вычислений коммуникационных операций,
следовательно: |
2 |
/ p) 2n 1 |
Tp calc (n |
|
- На этапе инициализации производится перераспределение |
|
блоков матриц А и B при помощи циклического сдвига матричных |
|
блоков по строкам и столбцам процессорной решетки |
|
(предполагаем, что топология системы представляет собой |
|
полный граф) |
Tp1 comm 2 w (n2 p) / |
На каждой итерации алгоритма после умножения матричных блоков процессоры передают свои блоки предыдущим процессорам по строкам (для блоков матрицы A) и столбцам (для блоков матрицы B)
Tp2 comm 2 w (n2 |
p) / |
Общее время выполнения параллельного алгоритма составляет
Tp q[(n2 / p) 2n / q 1 (n2 / p)] (2q 2)( w(n2 / p) / )
37 из 45
Параллельный алгоритм 3: метод Кэннона…
Результаты вычислительных экспериментов
–Сравнение теоретических оценок и экспериментальных данных
4 процессора
Размер матриц |
Tp(модель) |
Tp* |
|
||
500×500 |
0,5908 |
0,6676 |
1000×1000 |
4,4445 |
4,7065 |
1500×1500 |
14,6868 |
15,4247 |
2000×2000 |
34,4428 |
36,5024 |
38 из 45
Параллельный алгоритм 3: метод Кэннона
Результаты вычислительных экспериментов
–Ускорение вычислений
|
|
Параллельный |
|
|
Последовательный |
алгоритм, |
|
|
4 процессора |
||
Размер |
алгоритм |
|
|
|
|
|
|
матриц |
|
Время |
Ускорение |
500×500 |
2,0628 |
0,6676 |
3,0899 |
1000×1000 |
16,5152 |
4,7065 |
3,509 |
1500×1500 |
56,566 |
15,4247 |
3,6672 |
2000×2000 |
133,9128 |
36,5024 |
3,6686 |
39 из 45
Заключение…
Рассмотрены три возможных параллельных реализации одной из наиболее часто используемых матричных операций – матричного умножения:
–Алгоритм 1 – ленточное разбиение данных,
–Алгоритм 2 – метод Фокса (блочная схема),
–Алгоритм 3 – метод Кэннона (блочная схема)
Представлена программная реализация метода Фокса
Теоретические оценки позволяют достаточно точно определить показатели эффективности параллельных вычислений
40 из 45