Cannon's algorithm

Cannon's algorithm

In computer science, Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes first described in 1969 [http://dbpubs.stanford.edu:8090/pub/1994-25 Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes ] ] by Lynn 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.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • James W. Cannon — (b. January 30, 1943) is an American mathematician working in the areas of low dimensional topology and geometric group theory. He is an Orson Pratt Professor of Mathematics at the Brigham Young University.Biographical dataJames W. Cannon was… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history …   Wikipedia

  • Timeline of Islamic science and engineering — This timeline of Islamic science and engineering covers the general development of science and technology in the Islamic world during the Islamic Golden Age, usually dated from the 7th to 16th centuries.From the 17th century onwards, the advances …   Wikipedia

  • Geometric group theory — is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act (that is, when the… …   Wikipedia

  • Magma computer algebra system — Magma Developer(s) Computational Algebra Group, School of Mathematics and Statistics, University of Sydney Stable release 2.17 8 / May 27, 2011 Operating system …   Wikipedia

  • Connectionism — is a set of approaches in the fields of artificial intelligence, cognitive psychology, cognitive science, neuroscience and philosophy of mind, that models mental or behavioral phenomena as the emergent processes of interconnected networks of… …   Wikipedia

  • Charles Leedham-Green — Born Peebles, Scotland …   Wikipedia

  • Dehn function — In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group (that is a freely reduced word in the …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”