On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
- 1 December 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (12), 1180-1194
- https://doi.org/10.1109/TC.1984.1676393
Abstract
This paper describes two models of the cost of data movement in parallel numerical algorithms. One model is a generalization of an approach due to Hockney, and is suitable for shared memory multiprocessors where each processor has vector capabilities. The other model is applicable to highly parallel nonshared memory MIMD systems. In this second model, algorithm performance is characterized in terms of the communication network design. Techniques used in VLSI complexity theory are also brought in, and algorithm-independent upper bounds on system performance are derived for several problems that are important to scientific computation.Keywords
This publication has 25 references indexed in Scilit:
- A Combinatorial Limit to the Computing Power of VLSI CircuitsIEEE Transactions on Computers, 1983
- Quotient NetworksIEEE Transactions on Computers, 1982
- Introduction to the configurable, highly parallel computerComputer, 1982
- Using the Augmented Data Manipulator Network in PASMComputer, 1981
- Planar Circuit Complexity and The Performance of VLSI Algorithms +Published by Springer Nature ,1981
- On Stable Parallel Linear System SolversJournal of the ACM, 1978
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Parallel Tridiagonal Equation SolversACM Transactions on Mathematical Software, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- Fast Fourier TransformsPublished by Association for Computing Machinery (ACM) ,1966