Minimization of Interprocessor Communication for Parallel Computation
- 1 November 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (11) , 1067-1075
- https://doi.org/10.1109/TC.1982.1675923
Abstract
This paper is concerned with minimizing the delay due to data communication during the execution of a parallel algorithm on an SIMD computer with a two-way circular unit-shift interconnection network. Algorithms are developed which determine, for a given parallel procedure, the order of computation within that procedure, for every parallel arithmetic expression, the alignment of operands for every binary operation, and the mapping and remapping of data into physical memories so that the communication cost is minimized. The proposed algorithms are applicable to array variables with special types of index functions.Keywords
This publication has 6 references indexed in Scilit:
- Computer Architecture: Challenges and Opportunities for the Next DecadeIEEE Micro, 2005
- A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review, 1978
- Some Complexity Results for Matrix Computations on Parallel ProcessorsJournal of the ACM, 1978
- Analysis Techniques for SIMD Machine Interconnection Networks and the Effects of Processor Address MasksIEEE Transactions on Computers, 1977
- Matrix multiplication by diagonals on a vector/parallel processorInformation Processing Letters, 1976
- Access and Alignment of Data in an Array ProcessorIEEE Transactions on Computers, 1975