In this post, we will see Cannon's Algorithm for Matrix Multiplication | Matrix Matrix Multiplication Parallel Algorithm | cannon's algorithm for matrix multiplication,cannon's algorithm,matrix matrix multiplication parallel algorithm,matrix matrix multiplication,matrix matrix multiplication in parallel computing,matrix matrix multiplication algorithm,matrix matrix multiplication example,matrix matrix multiplication parallel implementation
Watch this video to know Cannon's Algorithm for Matrix Multiplication | Matrix Matrix Multiplication Parallel Algorithm :
Watch on YouTube: https://www.youtube.com/watch?v=Vk-mJcj7y_I
Cannon’s Algorithm
(Matrix Matrix Multiplication Parallel Algorithm)
e.g.
A=
2 3 4 5
9 8 7 6
5 4 2 3
8 7 3 4
B=
3 5 7 6
2 7 6 3
7 5 3 2
4 3 2 5
Here, every element of matrix is possesed by separate process.
Hence, total number of processes in this example(p)=16
Total number of steps: sqrt(p)=sqrt(16)=4
Step 1:
Find A1 from A by following process:
A=
2 3 4 5 ←0 Left Shift
9 8 7 6 ←1 Left Shift
5 4 2 3 ←2 Left Shift
8 7 3 4 ←3 Left Shift
A1=
2 3 4 5
8 7 6 9
2 3 5 4
4 8 7 3
Find B1 from B by following process:
B=
3 5 7 6
2 7 6 3
7 5 3 2
4 3 2 5
↑ ↑ ↑ ↑
0 1 2 3
Up Up Up Up
Shift Shift Shift Shift
B1=
3 7 3 5
2 5 2 6
7 3 7 3
4 5 6 2
C1[i][j]=A1[i][j] * B1[i][j]
C1=
6 21 12 25
16 35 12 54
14 9 35 12
16 40 42 6
Step 2:
Find A2 from A1 by following process:
A1=
2 3 4 5 ←1 Left Shift
8 7 6 9 ←1 Left Shift
2 3 5 4 ←1 Left Shift
4 8 7 3 ←1 Left Shift
A2=
3 4 5 2
7 6 9 8
3 5 4 2
8 7 3 4
Find B2 from B1 by following process:
B1=
3 7 3 5
2 5 2 6
7 3 7 3
4 5 6 2
↑ ↑ ↑ ↑
1 1 1 1
Up Up Up Up
Shift Shift Shift Shift
B2=
2 5 2 6
7 3 7 3
4 5 6 2
3 7 3 5
C2[i][j]=A2[i][j] * B2[i][j]
C2=
6 20 10 12
49 18 63 24
12 25 24 4
24 49 9 20
Step 3:
Find A3 from A2 by following process:
A2=
3 4 5 2 ←1 Left Shift
7 6 9 8 ←1 Left Shift
3 5 4 2 ←1 Left Shift
8 7 3 4 ←1 Left Shift
A3=
4 5 2 3
6 9 8 7
5 4 2 3
7 3 4 8
Find B3 from B2 by following process:
B2=
2 5 2 6
7 3 7 3
4 5 6 2
3 7 3 5
↑ ↑ ↑ ↑
1 1 1 1
Up Up Up Up
Shift Shift Shift Shift
B3=
7 3 7 3
4 5 6 2
3 7 3 5
2 5 2 6
C3[i][j]=A3[i][j] * B3[i][j]
C3=
28 15 14 9
24 45 48 14
15 28 6 15
14 15 8 48
Step 4:
Find A4 from A3 by following process:
A3=
4 5 2 3 ←1 Left Shift
6 9 8 7 ←1 Left Shift
5 4 2 3 ←1 Left Shift
7 3 4 8 ←1 Left Shift
A4=
5 2 3 4
9 8 7 6
4 2 3 5
3 4 8 7
Find B4 from B3 by following process:
B3=
7 3 7 3
4 5 6 2
3 7 3 5
2 5 2 6
↑ ↑ ↑ ↑
1 1 1 1
Up Up Up Up
Shift Shift Shift Shift
B4=
4 5 6 2
3 7 3 5
2 5 2 6
7 3 7 3
C4[i][j]=A4[i][j] * B4[i][j]
C4=
20 10 18 8
27 56 21 30
8 10 6 30
21 12 56 21
Final Result
C= C1 + C2 + C3 + C4
60 66 54 54
116 154 144 122
49 72 71 61
75 116 115 95
No comments:
Post a Comment