![]() This is done by shifting all submatrices A(i, j) to the left (with wraparound) by i steps and all submatrices B(i, j) up (with wraparound) by j steps.Įach block of A moves one step left and each block of B moves one step up (again with wraparound). ![]() The initial step of the algorithm regards the alignment of the matrixes.Īlign the blocks of A and B in such a way that each process can independently start multiplying its local submatrices. Process P(i, j) initially stores A(i, j) and B(i, j) computes block C(i, j) of the result matrix. Cannon’s algorithmĬonsider two n × n matrices A and B partitioned into p blocks.Ī(i, j) and B(i, j) (0 ≤ i,j ≤ √p ) of size (n ∕ √p)×(n ∕ √p) each. The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors. While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult. It is especially suitable for computers laid out in an N × N mesh. Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes.
0 Comments
Leave a Reply. |