A Separator-Based Framework for
                     Automated Partitioning and Mapping of
              Parallel Algorithms for Numerical Solution of PDEs

          Eric J. Schwabe (1), Guy E. Blelloch (1), Anja Feldmann (1)
           Omar Ghattas (2), John R. Gilbert (3), Gary L. Miller (1)
     David R. O'Hallaron (1), Jonathan R. Shewchuk (1), Shang-Hua Teng (3)

         School of Computer Science (1)           Xerox Corporation (3)
      Department of Civil Engineering (2)      Palo Alto Research Center
         Carnegie Mellon University              3333 Coyote Hill Road
            Pittsburgh, PA 15213                  Palo Alto, CA 94304

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.


Proceedings of the First Annual Summer Institute on Issues and Obstacles in the
ractical Implementation of Parallel Algorithms and the Use of Parallel Machines
in Parallel Computation (DAGS/PC '92), pages 48-62, Dartmouth Institute for
Advanced Graduate Studies, June 1992.  PostScript (2247k).


Paper available through the URL
http://www.cs.cmu.edu/~quake-papers/dags92-pde-framework.ps


BibTeX entry:

@inproceedings{schwabe92,
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 {S}eparator-{B}ased {F}ramework for {A}utomated {P}artitioning and
  {M}apping of {P}arallel {A}lgorithms for {N}umerical {S}olution of {PDE}s},
booktitle = {Proceedings of the First Annual Summer Institute on Issues and
  Obstacles in the Practical Implementation of Parallel Algorithms and the Use
  of Parallel Machines in Parallel Computation (DAGS/PC '92)},
booktitle2 = {Proceedings of the 1992 DAGS/PC Symposium},
organization = {Dartmouth Institute for Advanced Graduate Studies},
pages = {48--62},
month = jun,
year = 1992
}