Nearest-Neighbor Mapping of Finite Element Graphs onto Processor Meshes
- 1 December 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (12), 1408-1424
- https://doi.org/10.1109/tc.1987.5009494
Abstract
The processor allocation problem is addressed in the context of the parallelization of a finite element modeling program on a processor mesh. A heuristic two-step, graph-based mapping scheme with polynomial-time complexity is developed: 1) initial generation of a graph partition for nearest-neighbor mapping of the finite element graph onto the processor graph, and, 2) a heuristic boundary refinement procedure to incrementally alter the initial partition for improved load balancing among the processors. The effectiveness of the approach is gaged both by estimation using a model with empirically determined parameters, as well as implementation and experimental measurement on a 16 node hypercube parallel computer.Keywords
This publication has 9 references indexed in Scilit:
- A Partitioning Strategy for Nonuniform Problems on MultiprocessorsIEEE Transactions on Computers, 1987
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- The anticipated impact of supercomputers on finite-element analysisProceedings of the IEEE, 1984
- Heuristic Models of Task Assignment Scheduling in Distributed SystemsComputer, 1982
- A Task Allocation Model for Distributed Computing SystemsIEEE Transactions on Computers, 1982
- On the Mapping ProblemIEEE Transactions on Computers, 1981
- Task Allocation in Distributed Data ProcessingComputer, 1980
- Models for Dynamic Load Balancing in a Heterogeneous Multiple Processor SystemIEEE Transactions on Computers, 1979
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977