Monday, 23 November 2020

Cannon's Algorithm for Matrix Multiplication | Matrix Matrix Multiplication Parallel Algorithm

                     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