A Mapping Strategy for Parallel Processing
- 1 April 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (4) , 433-442
- https://doi.org/10.1109/tc.1987.1676925
Abstract
This paper presents a mapping strategy for parallel processing using an accurate characterization of the communication overhead. A set of objective functions is formulated to evaluate the optimality of mapping a problem graph onto a system graph. One of them is especially suitable for real-time applications of parallel processing. These objective functions are different from the conventional objective functions in that the edges in the problem graph are weighted and the actual distance rather than the nominal distance for the edges in the system graph is employed. This facilitates a more accurate quantification of the communication overhead. An efficient mapping scheme has been developed for the objective functions, where two levels of assignment optimization procedures are employed: initial assignment and pairwise exchange. The mapping scheme has been tested using the hypercube as a system graph.Keywords
This publication has 6 references indexed in Scilit:
- Correspondence processes in dynamic scene analysisProceedings of the IEEE, 1981
- On the Mapping ProblemIEEE Transactions on Computers, 1981
- Dual Processor Scheduling with Dynamic ReassignmentIEEE Transactions on Software Engineering, 1979
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977
- A Review of the Placement and Quadratic Assignment ProblemsSIAM Review, 1972
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961