- Cannon's algorithm
In
computer science , Cannon's algorithm is adistributed algorithm formatrix multiplication for two-dimensionalmesh es first described in1969 [http://dbpubs.stanford.edu:8090/pub/1994-25 Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes ] ] byLynn Elliot Cannon .It is especially suitable for computers laid out in an "N" × "N" mesh [http://www.ipp.mpg.de/de/for/bereiche/stellarator/Comp_sci/CompScience/csep/csep1.phy.ornl.gov/la/node6.html 4.2 Matrix Multiplication on a Distributed Memory Machine ] ] . While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been proven to be difficult [http://graal.ens-lyon.fr/~jfpineau/research.html Research ] ] .
The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors .
See also
*
Systolic array References
Bibliography
* Lynn Elliot Cannon, " [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=905686 A cellular computer to implement the Kalman Filter Algorithm] ", Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.
External links
* [http://www.cs.berkeley.edu/~demmel/cs267/lecture11/lecture11.html Lecture at Berkeley]
* [http://www.cs.mu.oz.au/498/notes/node30.html mu.oz.au]
Wikimedia Foundation. 2010.