On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
Copyright policy )On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
Summary: 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.
- Purdue University West Lafayette United States
- National Aeronautics and Space Administration United States
- Langley Research Center United States
- Purdue University System United States
Analysis of algorithms and problem complexity, algorithm performance, parallel algorithms, parallel architectures, cost of data movement in parallel numerical algorithms, system performance, shared memory multiprocessors, Theory of operating systems, highly parallel nonshared memory MIMD systems, Applications of graph theory to circuits and networks, communication network design, numerical software, Algorithms in computer science, VLSI complexity, interconnection networks
Analysis of algorithms and problem complexity, algorithm performance, parallel algorithms, parallel architectures, cost of data movement in parallel numerical algorithms, system performance, shared memory multiprocessors, Theory of operating systems, highly parallel nonshared memory MIMD systems, Applications of graph theory to circuits and networks, communication network design, numerical software, Algorithms in computer science, VLSI complexity, interconnection networks
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).67 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!