## 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 :

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