Scalable Libraries for Graph Partitioning

SUMMARY
We are pursuing research in the area of new parallel methods for graph partitioning and incremental graph partitioning.


Sample Mesh

PARTICIPATING INSTITUTIONS
NPAC, Syracuse University
School of Information Studies, Syracuse University

KEY CONTACTS
Sanjay Ranka | ranka@top.cis.syr.edu | (315) 443-4457
Geoffrey Fox | gcf@npac.syr.edu | (315) 443-4741

IMPACT
Efficient methods for graph partitioning and incremental graph partitioning are important for parallelization of a large number of unstructured and/or adaptive applications.

PROJECT DESCRIPTION
The key problem in efficiently executing irregular and unstructured data parallel applications is partitioning the data to minimize communication while balancing the load. Partitioning such applications can be posed as a graph-partitioning problem based on the computational graph. We are currently developing a library of partitioners (especially based on physical optimization) which aim to find good suboptimal solutions in parallel. The initial target use of these partitioning methods are for runtime support of data parallel compilers (HPF).

Results:


Summary of Different Partitioners

Important Features of Partitioners :
Quality of the Partitioning (I),
Computational Cost (II),
Incremental Remapping faster than ab intitio (III)
Naturally Improvable (IV),
Generally limited to graphs which have coordinate information (V)

REFERENCES
  1. Rahul Bhargava, Geoffrey Fox, Chao-Wei Ou, Sanjay Ranka and Virinder Singh, "Scalable Libraries for Graph Partitioning," 1993 Scalable Libraries Conference, Mississippi.

  2. N.P. Chrisochoides, C.E. Houstis, E.N. Houstis, Geometry based mapping strategies for PDE computation, Proceedings of the 5th International Conference on Supercomputing, Colonge-Germany, ACM Publications, p ages 115-127, 1991

  3. N.P. Chrisochoides, C.E. Houstis, E.N. Houstis, P.N. Papachiou, S.K. Kortesis, J .R. Rice, Domain Decomposer: A software tool for partitioning and allocation of PDE computations based on Geometry Decomposition strategies, Domain Decomposition Methods for Partial Differential Equations, Proceedings of the 4th International Symposium on Domain Decomposition Methods, Moscow, USSR, May 1990 (Glowinski et al., ed), SIAM Publications, pages 341-357, 1991.

  4. N.P. Chrisochoides, E. Houstis, J.R. Rice, Mapping Algorithms and Software Environment for Data Parallel PDE Iterative Solvers, To appear in the special issue of the Journal of Parallel and Distributed Computing on Data-Parallel Algorithms and Programming, 1993

  5. N.P. Chrisochoides, N. Mansour, G.C. Fox,Performance evaluation of data mapping algorithms for parallel single-phase iterative PDE solvers, Submitted to the special issue of the Journal of Concurrency Practi ce and Experience, 1993.

  6. N.P. Chrisochoides, J.R. Rice, Partitioning Heuristics for PDE Computations Based on Parallel Hardware and Geometry Characteristics, In Advances in Computer Methods for Partial Differential Equations VII ( R. Vich nevetsky, D. Knight, G. Richter, eds) IMACS, New Brunswick, NJ, pages 127-133, 1992.

  7. G. C. Fox &W. Furmanski. Load Balancing Loosely Synchronous Problems with a Neural Network.

  8. Nashat Mansour. Physical Optimization Algorithms for Mapping Data to Distributed-Memory Multiprocessors. PhD Thesis.

  9. Chao-Wei Ou, Sanjay Ranka, and Geoffrey Fox. Fast Mapping and Remapping Algorithm for Irregular and Adaptive Problems. Proceedings of the 1992 International Conference on Parallel and Distributed Systems, pages 279-283, December 1993.

  10. H. Simon 1991, Partitioning of unstructured mesh problems for parallel processing. Proc. Conf. Parallel Methods on Large Scale Structural Analysis and Physics Applications, Permagon Press.

Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu
This page maintained by Sanjay Ranka, ranka@top.cis.syr.edu