Parallel graph partitioning

 

Given a graph, partition with the following constraints:
  • Balance the workload
    • All processors should perform the
      same amount of work.
    • Each graph node is weighted by the local depth.

  • Minimize the number of edge cuts
    • Processors must communicate information
      at interprocessor boundaries.
    • Graph partitioning must minimize the number of
      edge cuts in order to minimize cost of communication.
Monterey Bay graph.  

Introduction    Unstructured grids    Numerical method    Internal Waves    Summary
8