ParMetis

ParMetis is a library and application suite for efficient partitioning of graphs and other manipulation of meshes and graphs. Graph partioning is important in load balancing and communication optimization in parallel calculations which use unstructured grids or large sparse matrices. ParMetis uses MPI.

ParMetis takes a large symmetric graph and splits it into k sub-graphs which maximally satisfy an objective function (least communication volume, fewest edge-cuts, etc.)

These subgraphs represent an efficient partitioning of the graph nodes on a distributed memory computer. Metis can also effceintly refine a partition when a graph changes slightly (such as when an unstructured grid evolves over time).

• ParMetis 2.0 (MPI parallelism)

• Setup
• Metis Applications
• Metis Programming
• Parallel Jobs
• Examples
• Documentation and Help

Setup

The modules package controls access to Metis software.

 module load parmetis

in your .profile.ext or .login.ext files, or type this command whenever you want to access Metis for a single session.

Metis Applications

Metis contains several stand alone applications for partitoning and manipulation of graphs and meshes. Information about the quality of the partition, timings, and diagnostics are written to stdout.

• pmetis/kmetis

  [pk]metis GraphFile Nparts

  partitions the graph in GraphFile into Nparts subgraphs.kmetis is in general faster when Nparts > 8, for small Nparts pmetis may be faster. The partitions are written to Nparts files with names GraphFile.part.Nparts.

• partnmesh/partdmesh

  part[nd]mesh MeshFile Nparts

  partitions a mesh into k equal sized parts. The mesh is first converted to graph and then kmetis is used to partioning the graph.

  partnmesh partitions by the vertices in the mesh, while partdmesh partitions by the elements in the mesh.

• oemetis/onmetis

  o[ne]metis GraphFile

  sparse matrix reordering programs which produce fill-reducing orderings from a graph file. The permutation between the original ordering and and the fill-reducing one is output to GraphFile.iperm, information about the quality of the permutation is output to stdout.

• Utility programs: mesh2nodal, mesh2dual, graphchk

  Mesh to graph conversion programs.

  mesh2nodal MeshFile
  produces a graph flie MeshFile.ngraph

  mesh2dual MeshFile
  produces a graph flie MeshFile.dgraph

  graphchk GraphFile
  Topological sanity check for undirected graph files.

Metis Programming

The libmetis is described fully in the manual and in proto.h. The three workhorse routines are compared below.

The API also includes for wieghted and constrained partitioning.

Examples

Consider the following 2d data set and a nearest neighbor undirected graph:

Data/Vertices	Nearest neighbor Graph

The graph above can be created from the data given by a variety of means, e.g., you can use the excellent program Triangle . From the adjacency matrix for the above graph Metis can produce a set of subgraphs which minimize communication required between subgraphs. The format for Metis graph files is :

Where nnodes and nsegments are the numbers of vertices and and segments respectively.

To break the graph above into 10 sub graphs use the command kmetis nersc_graph 10 which will produce a file nersc_graph.part.10 which lists the 10 partitions (labeled 0-9). In the image below color boundaries shows the distinct subgraphs.

Graph Partitions

Several other examples are in /usr/common/usg/metis/{version}/Graphs.

Documentation and Help

• Metis 4.0 Manual (Postscript)
• ParMetis 2.0 Manual (Postscript)