Communication Issues in the Design and Analysis of Parallel Algorithms
- 1 March 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-7 (2) , 174-188
- https://doi.org/10.1109/tse.1981.230833
Abstract
As multiple processor systems become more widely accepted the importance of parallel programming increases. In this paper, approaches to the design and analysis of parallel algorithms are investigated. Through several examples, the importance of interprocessor communication in parallel processing is demonstrated. Various techniques that are applicable in the design and analysis of parallel algorithms are examined with emphasis on those techniques that incorporate communication aspects. The paper discusses several models of synchronous and asynchronous parallel computation and their use in analyzing algorithms. Relatively primitive methodologies for designing parallel algorithms are discussed and the need for more general and practical methodologies is indicated.Keywords
This publication has 40 references indexed in Scilit:
- Discrete Systems and FlowchartsIEEE Transactions on Software Engineering, 1978
- Critical Load Factors in Two-Processor Distributed SystemsIEEE Transactions on Software Engineering, 1978
- Decentralized parallel algorithms for matrix computationPublished by Association for Computing Machinery (ACM) ,1978
- The Honeywell Experimental Distributed Processor – an OverviewComputer, 1978
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Analysis Techniques for SIMD Machine Interconnection Networks and the Effects of Processor Address MasksIEEE Transactions on Computers, 1977
- Parallel algorithms for the transitive closure and the connected component problemsPublished by Association for Computing Machinery (ACM) ,1976
- A Heuristic Procedure for the Partitioning and Mapping of Computer Logic GraphsIEEE Transactions on Computers, 1971
- Quadratic Assignment Problem Algorithms and the Location of Indivisible FacilitiesManagement Science, 1966
- Assignment Problems and the Location of Economic ActivitiesEconometrica, 1957