Cannon's algorithm
From Wikipedia, the free encyclopedia
In computer science, Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes first described in 1969 [1] by Lynn Elliot Cannon.
It is especially suitable for computers laid out in an N × N mesh [2]. While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been proven to be difficult [3].
The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors [1].
Contents |
[edit] See also
[edit] References
- ^ a b Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes
- ^ 4.2 Matrix Multiplication on a Distributed Memory Machine
- ^ Research
[edit] Bibliography
- Lynn Elliot Cannon, A cellular computer to implement the Kalman Filter Algorithm, Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.
