Enhancing data locality by using terminal propagation
- 1 January 1996
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 565-574 vol.1
- https://doi.org/10.1109/hicss.1996.495507
Abstract
Terminal propagation is a method developed in the circuit placement community for adding constraints to graph partitioning problems. This paper adapts and expands this idea, and applies it to the problem of partitioning data structures among the processors of a parallel computer. We show how the constraints in terminal propagation can be used to encourage partitions in which messages are communicated only between architecturally near processors. We then show how these constraints can be handled in two important partitioning algorithms, spectral bisection and multilevel-KL. We compare the quality of partitions generated by these algorithms to each other and to partitions generated by more familiar techniques.Keywords
This publication has 12 references indexed in Scilit:
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel ComputationsSIAM Journal on Scientific Computing, 1995
- Partitioning & mapping of unstructured meshes to parallel machine topologiesPublished by Springer Nature ,1995
- Dynamic load balancing with a spectral bisection algorithm for the constrained graph partitioning problemPublished by Springer Nature ,1995
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- Partitioning of unstructured problems for parallel processingComputing Systems in Engineering, 1991
- Partitioning Sparse Matrices with Eigenvectors of GraphsSIAM Journal on Matrix Analysis and Applications, 1990
- A Procedure for Placement of Standard-Cell VLSI CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Lower Bounds for the Partitioning of GraphsIBM Journal of Research and Development, 1973
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970