Graphics enhanced version of this site

A Separator-Based Framework for Automated Partitioning and Mapping of Parallel Algorithms for Numerical Solution of PDEs
E.J. Schwabe, G.E. Blelloch, A. Feldmann, O. Ghattas, J.R. Gilbert, G.L. Miller, D.R. O'Hallaron, J.R. Shewchuk, and S. Teng
Proceedings of the 1992 DAGS / PC Symposium, June, 1992, pp. 48 - 62.

Jump to: Download | Abstract | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [421 KB]
Compressed postscript (ps.gz) [308 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

This paper is a report on ongoing work in developing automated systems for the partitioning, placement, and routing of data that is necessary for the efficient parallel solution of large problems in scientific computing, specifically the numerical solution of partial differential equations. Many of these problems have as an iterated inner loop the formation of the product of a large sparse matrix and a vector of variables. This problem of sparse matrix-vector multiplication has an underlying combinatorial graph structure that can be exploited. Using geometric information from the original problem, we can partition this combinatorial graph using provably good two- or three-dimensional graph separators (depending on the dimension of the problem). The resulting partitions into subproblems have good load balancing properties and a relatively small amount of communication between subproblems. In order to develop effective heuristics for the placement of these subproblems on the available processors and the routing of messages between them, we must also carefully consider the characteristics of the target architectures. The first parallel machine we are considering is the iWarp system. The novel communication mechanism of the iWarp system allows us to draw an analogy between our placement and routing problem and certain area minimization problems in the field of VLSI circuit layout, giving us an additional collection of insights and heuristics which can be brought to bear on our problem.

E.J. Schwabe, G.E. Blelloch, A. Feldmann, O. Ghattas, J.R. Gilbert, G.L. Miller, D.R. O'Hallaron, J.R. Shewchuk, and S. Teng, "A Separator-Based Framework for Automated Partitioning and Mapping of Parallel Algorithms for Numerical Solution of PDEs," Proceedings of the 1992 DAGS / PC Symposium, June, 1992, pp. 48 - 62.

@inproceedings{Schwabe_1992_3207,
   author = "Eric J. Schwabe and Guy E. Blelloch and Anja Feldmann and Omar Ghattas and John R. Gilbert and Gary L. Miller and David R. O'Hallaron and Jonathan R. Shewchuk and Shang-Hua Teng",
   title = "A Separator-Based Framework for Automated Partitioning and Mapping of Parallel Algorithms for Numerical Solution of PDEs",
   booktitle = "Proceedings of the 1992 DAGS / PC Symposium",
   month = "June",
   year = "1992",
   pages = "48 - 62"
}