scientific article; zbMATH DE number 3970105
[For the entire collection see Zbl 0592.00028.] The author gives a survey on the design and analysis of parallel algorithms. Besides listing of a general result on the potential speedup obtainable by parallel computation, special attention is paid to the impact of the interconnection network of a parallel computer on the communication complexity of an algorithm which is the number of data transfers necessary during a complete computation. Various interconnection networks are briefly described. The only parallel algorithms presented in more detail are the Fast Fourier Transform to provide an example of an interconnection network adapted to the computational and data-flow structure of an algorithm, and the multiplication of matrices which is used to illustrate the concept of systolic arrays. The survey is slightly too superficial and far from being complete. Nevertheless, it may be recommended as a starting point to someone new to the field of parallel algorithms, since many references to the relevant literature are given.
- On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
- Your favorite parallel algorithms might not be as fast as you think
- scientific article; zbMATH DE number 4126681 (Why is no real title available?)
- Communication complexity and parallel computing
- Complexity theory and algorithms
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3736902)