METIS
∗
A Software Package for Partitioning Unstructured
Graphs, Partitioning Meshes, and Computing
Fill-Reducing Orderings of Sparse Matrices
Version 5.1.0
George Karypis
Department of Computer Science & Engineering
University of Minnesota
Minneapolis, MN 55455
karypis@cs.umn.edu
March 30, 2013
Metis [MEE tis]: ‘Metis’ is the Greek word for wisdom. Metis was a titaness in Greek mythology. She was the consort
of Zeus and the mother of Athena. She presided over all wisdom and knowledge.
∗
METIS is copyrighted by the regents of the University of Minnesota. Related papers are available via WWW at URL:
http://www.cs.umn.edu/˜karypis
1
Contents
1 Introduction 4
2 What is new in version 5.0 4
2.1 Changes in the command-line programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Migration issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Changes in the API routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Migration issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Overview of METIS 6
3.1 Partitioning a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Alternate partitioning objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Support for multi-phase and multi-physics computations . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Partitioning a mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5 Partitioning for heterogeneous parallel computing architectures . . . . . . . . . . . . . . . . . . . . . 8
3.6 Computing a fill-reducing ordering of a sparse matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.7 Converting a mesh into a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 METIS’ stand-alone programs 9
4.1 Input file formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1.1 Graph file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1.2 Mesh file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.3 Target partition weights file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Output file formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.1 Partition file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.2 Ordering file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
gpmetis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
mpmetis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
ndmetis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
m2gmetis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
graphchk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5 METIS’ API 20
5.1 Header files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 Use of NULL parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 C/C++ and Fortran Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.4 Options array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.5 Graph data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.6 Mesh data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.7 Partitioning objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.8 Graph partitioning routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
METIS PartGraphRecursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
METIS PartGraphKway . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.9 Mesh partitioning routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
METIS PartMeshDual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
METIS PartMeshNodal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.10 Sparse Matrix Reordering Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
METIS NodeND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2
5.11 Mesh-to-graph conversion routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
METIS MeshToDual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
METIS MeshToNodal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.12 Utility routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
METIS SetDefaultOptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
METIS Free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6 System requirements and contact information 35
7 Copyright & license notice 35
3
1 Introduction
Algorithms that find a good partitioning of highly unstructured graphs are critical for developing efficient solutions for
a wide range of problems in many application areas on both serial and parallel computers. For example, large-scale
numerical simulations on parallel computers, such as those based on finite element methods, require the distribution
of the finite element mesh to the processors. This distribution must be done so that the number of elements assigned
to each processor is the same, and the number of adjacent elements assigned to different processors is minimized.
The goal of the first condition is to balance the computations among the processors. The goal of the second condition
is to minimize the communication resulting from the placement of adjacent elements to different processors. Graph
partitioning can be used to successfully satisfy these conditions by first modelling the finite element mesh by a graph,
and then partitioning it into equal parts.
Graph partitioning algorithms are also used to compute fill-reducing orderings of sparse matrices. These fill-
reducing orderings are useful when direct methods are used to solve sparse systems of linear equations. A good
ordering of a sparse matrix dramatically reduces both the amount of memory as well as the time required to solve
the system of equations. Furthermore, the fill-reducing orderings produced by graph partitioning algorithms are par-
ticularly suited for parallel direct factorization as they lead to high degree of concurrency during the factorization
phase.
Graph partitioning is also used for solving optimization problems arising in numerous areas such as design of very
large scale integrated circuits (VLSI), storing and accessing spatial databases on disks, transportation management,
and data mining.
2 What is new in version 5.0
Version 5.0 represents nearly a complete re-write of the code-base whose purpose was to streamline and unify the
stand-alone programs and API, provide better support for 64 bit architectures, enhance its functionality, and reduce
the memory requirements by re-factoring its internal memory management routines. As a result, both the stand-alone
programs and API routines have changed, making it incompatible with the earlier versions of METIS. However, in
order to minimize the code changes that the revised API will require, the new API relies heavily on reasonable default
values for most of the new parameters that it introduced.
The following represents a list of some of the major functionality-related changes and enhancements that are ac-
cessible by both the command-line programs and the API routines.
• Multi-constraint partitioning can be used in conjunction with minimization of the total communication volume.
• All graph and mesh partitioning routines take as input the target sizes of the partitions, which among others,
allow them to compute partitioning solutions that are well-suited for parallel architectures with heterogeneous
computing capabilities.
• When multi-constraint partitioning is used, the target sizes of the partitions are specified on a per partition-
constraint pair.
• The multilevel k-way partitioning algorithms can compute a partitioning solution in which each partition is
contiguous.
• All partitioning and ordering routines can compute multiple different solutions and select the best as the final
solution.
• The mesh partitioning and mesh-to-graph conversion routines can operate on mixed element meshes.
• The command-line programs provide full access to the entire set of capabilities provided by METIS’ API.
4
Operation 4.x stand-alone program 5.x stand-alone program
Partition a graph pmetis
kmetis
gpmetis
Partition a mesh partnmesh
partdmesh
mpmetis
Compute a fill-reducing
ordering of a sparse matrix
oemetis
onmetis
ndmetis
Convert a mesh into a graph mesh2nodal
mesh2dual
m2gmetis
Graph format checker graphchk graphchk
Table 1: Mapping between the old 4.x and the new 5.x command-line programs.
2.1 Changes in the command-line programs
Table 1 shows how the v4.x command-line programs map to the new set of command-line programs provided by
the 5.0 version of METIS. As part of these changes, none of the functionality offered by the old programs has been
removed. On the contrary, the new programs have been extended to substantially increase the type of partitionings
and orderings that can be computed by them. This was achieved by expanding the number of optional parameters that
these programs can take, which allow users to have a complete access to all of METIS’ functionality. Prior to this
release, if users wanted to access some of the advance features of METIS, they had to write their own programs based
on the supplied API.
2.1.1 Migration issues
In order to support the enhanced functionality offered by the new command-line programs, the format of the graph
mesh files has changed (Section 4.1). In the case of the graph file, the new format is backwards compatible, so graphs
written for the earlier format will work correctly when used by gpmetis and ndmetis. However, the new mesh file
format is not backward compatible, and as such they should not be used with mpmetis and m2gmetis. Fortunately,
they can be easily converted to the new format by a slightly modifying their header line.
2.2 Changes in the API routines
Table 2 shows how the v4.x API routines map to the new set of APIs provided by the 5.0 version of METIS. The
number of distinct core functions has been reduced to seven by expanding the calling sequence of the new routines
to provide the functionally offered by the old specialized routines. In most cases, the functionality provided by the
new API routines is a superset of that offered by the old routines, especially in the areas related to partitioning for
heterogeneous computing architectures, multi-constraint partitioning, and communication volume-based partitioning
objectives.
2.2.1 Migration issues
Since the calling sequence of all the API routines and in some cases their names has changed, migrating to the new
API will require code modifications. To ensure that these modifications are minimal, the new API routines allow users
to provide NULL as the argument to many of the parameters for which there are reasonable defaults. Thus, we expect
the migration to the new API will be rather straightforward, as long as the application does not want to take advantage
of the newly added capabilities.
5
- 1
- 2
前往页