Cannon's algorithm
In computer science, Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes first described in 1969 by Lynn Elliot Cannon.[1][2]
It is especially suitable for computers laid out in an N × N mesh.[3] While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been proven to be difficult.[4]
The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.[2]
The Scalable Universal Matrix Multiplication Algorithm (SUMMA) [5] is a more practical algorithm that requires less workspace and overcomes the need for a square 2D grid. It is used by the ScaLAPACK, PLAPACK, and Elemental libraries.
See also
References
- ^ Lynn Elliot Cannon, A cellular computer to implement the Kalman Filter Algorithm, Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.
- ^ a b Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes, dbpubs.stanford.edu
- ^ 4.2 Matrix Multiplication on a Distributed Memory Machine, ipp.mpg.de
- ^ Research, graal.ens-lyon.fr
- ^ Robert A. van de Geijn and Jerrell Watts, " SUMMA: scalable universal matrix multiplication algorithm, Concurrency: Practice and Experience. Volume 9, Issue 4, pages 255–274, April 1997.
External links
 | This applied mathematics–related article is a stub. You can help Wikipedia by expanding it. |