没有合适的资源?快使用搜索试试~ 我知道了~
首页metis manual
metis manual
需积分: 10 9 下载量 185 浏览量
更新于2023-06-03
评论
收藏 202KB PDF 举报
A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices
资源详情
资源评论
资源推荐
METIS
∗
A Software Package for Partitioning Unstructured
Graphs, Partitioning Meshes, and Computing
Fill-Reducing Orderings of Sparse Matrices
Version 4.0
George Karypis and Vipin Kumar
University of Minnesota, Department of Computer Science / Army HPC Research Center
Minneapolis, MN 55455
{karypis, kumar}@cs.umn.edu
September 20, 1998
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. This work was supported by IST/BMDO through Army Research Office
contract DA/DAAH04-93-G-0080, and by Army High Performance Computing Research Center under the auspices of the Department of the Army,
Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does
not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities
were provided by Minnesota Supercomputer Institute, Cray Research Inc, and by the Pittsburgh Supercomputing Center. Related papers are available
via WWW at URL: http://www.cs.umn.edu/˜karypis
1
Contents
1 Introduction 3
2 What is METIS 4
3 What is New in This Version 6
4 METIS’s Stand-Alone Programs 8
4.1 Graph Partitioning Programs . ...................................... 8
4.2 Mesh Partitioning Programs . ...................................... 9
4.3 SparseMatrixReorderingPrograms ................................... 11
4.4 Auxiliary Programs . . .......................................... 13
4.4.1 MeshToGraphConversion ................................... 13
4.4.2 GraphChecker .......................................... 14
4.5 Input File Formats . . . .......................................... 15
4.5.1 GraphFile ............................................ 15
4.5.2 MeshFile............................................. 16
4.6 OutputFileFormats............................................ 17
4.6.1 Partition File . .......................................... 17
4.6.2 OrderingFile........................................... 17
5 METIS’s Library Interface 18
5.1 GraphDataStructure........................................... 18
5.2 MeshDataStructure ........................................... 19
5.3 Partitioning Objectives .......................................... 19
5.4 Graph Partitioning Routines . ...................................... 21
METIS PartGraphRecursive .................................... 21
METIS PartGraphKway ...................................... 22
METIS PartGraphVKway ..................................... 23
METIS mCPartGraphRecursive .................................. 24
METIS mCPartGraphKway .................................... 26
METIS WPartGraphRecursive................................... 28
METIS WPartGraphKway..................................... 30
METIS WPartGraphVKway .................................... 32
5.5 Mesh Partitioning Routines . . ...................................... 34
METIS PartMeshNodal....................................... 34
METIS PartMeshDual ....................................... 35
5.6 SparseMatrixReorderingRoutines.................................... 36
METIS EdgeND .......................................... 36
METIS NodeND .......................................... 37
METIS NodeWND......................................... 39
5.7 Auxiliary Routines . . .......................................... 40
METIS MeshToNodal ....................................... 40
METIS MeshToDaul........................................ 41
METIS EstimateMemory...................................... 42
5.8 C and Fortran Support .......................................... 43
6 System Requirements and Contact Information 44
2
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 modeling 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.
3
2WhatisMETIS
METIS is a software package for partitioning large irregular graphs, partitioning large meshes, and computing fill-
reducing orderings of sparse matrices. The algorithms in METIS are based on multilevel graph partitioning described
in [8, 7, 6]. Traditional graph partitioning algorithms compute a partition of a graph by operating directly on the
original graph as illustrated in Figure 1(a). These algorithms are often too slow and/or produce poor quality partitions.
Multilevel partitioning algorithms, on the other hand, take a completely different approach [5, 8, 7]. These algo-
rithms, as illustrated in Figure 1(b), reduce the size of the graph by collapsing vertices and edges, partition the smaller
graph, and then uncoarsen it to construct a partition for the original graph. METIS uses novel approaches to succes-
sively reduce the size of the graph as well as to further refine the partition during the uncoarsening phase. During
coarsening, METIS employs algorithms that make it easier to find a high-quality partition at the coarsest graph. During
refinement, METIS focuses primarily on the portion of the graph that is close to the partition boundary. These highly
tuned algorithms allow METIS to quickly produce high-quality partitions for a large variety of graphs.
Traditional partitioning algorithms compute
a partition directly on the original graph!
Coarsening Phase
Initial Partitioning Phase
Refinement Phase
Multilevel partitioning algorithms compute a partition
at the coarsest graph and then refine the solution!
(b)
(a)
Figure 1: (a) Traditional partitioning algorithms. (b) Multilevel partitioning algorithms.
The advantages of METIS compared to other similar packages are the following:
☞ Provides high quality partitions!
Experiments on a large number of graphs arising in various domains including finite element methods, linear
programming, VLSI, and transportation show that METIS produces partitions that are consistently better than
those produced by other widely used algorithms. The partitions produced by METIS are consistently 10% to
50% better than those produced by spectral partitioning algorithms [1, 4].
☞ It is extremely fast!
Experiments on a wide range of graphs has shown that METIS is one to two orders of magnitude faster than other
widely used partitioning algorithms. Figure 2 shows the amount of time required to partition a variety of graphs
in 256 parts for two different architectures, an R10000-based SGI Challenge and a Pentium Pro-based personal
computer. Graphs containing up to four million vertices can be partitioned in 256 parts in well under a minute
on today’s scientific workstations. The run time of METIS is comparable to (or even smaller than) the run time
of some geometric partitioning algorithms that often produce much worse partitions.
☞ Provides low fill orderings!
The fill-reducing orderings produced by METIS are substantially better than those produced by other widely
used algorithms including multiple minimum degree. For many classes of problems arising in scientific compu-
tations and linear programming, METIS is able to reduce the storage and computational requirements of sparse
matrix factorization methods by up to an order of magnitude. Moreover, unlike multiple minimum degree, the
elimination trees produced by METIS are suited for parallel direct factorization. Furthermore, as Figure 2 illus-
trates, METIS is able to compute these ordering very fast. Matrices with over two hundred thousand rows can be
reordered in just a few seconds on current generation workstations and PCs.
4
METIS's Partitioning Performance
1.57sec
2.10sec
4.00sec
4.42sec
7.79sec
11.32sec
15.76sec
17.81sec
47.34sec
2.55sec
3.79sec
5.87sec
5.96sec
15.12sec
16.95sec
19.40sec
31.11sec
90.45sec
Brack2
Ocean
144
Mdual1
Troll
Auto
Mdual2
Big
Mdual3
MIPS R10000@200MHz Intel PPRO@200MHz
Number of
Vertices
Number of
Edges
Mdual3
4,039,160 8,016,848
Big
295,433 7,953,453
Mdual2
1,017,253 2,015,714
Auto
448,695 3,314,611
Troll
213,453 5,885,829
Mdual1
257,000 505,048
144
144,649 1,074,393
Ocean
143,437 409,593
Brack2
62,631 366,559
METIS's Ordering Performance
0.90sec
2.19sec
2.67sec
3.43sec
3.55sec
3.96sec
5.90sec
10.51sec
13.34sec
1.52sec
3.95sec
3.42sec
4.10sec
6.59sec
6.55sec
11.32sec
20.07sec
24.43sec
Inpro1
BCSSTK30
BCSSTK32
BCSSTK31
PDS-20
KEN18
FORT17
Troll
Ocean
MIPS R10000@200MHz Intel PPRO@200MHz
Number of
Vertices
Number of
Edges
Operation
Count
Ocean
143,437 409,593 1.26e+08
Troll
213,453 5,885,829 5.53e+10
Fort17
86,650 247,424 8.05e+06
Ken18
105,127 252,072 2.85e+08
PDS-20
33,798 143,161 3.82e+09
BCSSTK31
35,588 572,914 1.16e+09
BCSSTK32
44,609 985,046 1.32e+09
BCSSTK30
28,294 1,007,284 1.17e+09
Inpro1
46,949 1,117,809 1.24e+09
Figure 2: The amount of time required by METIS to partition various graphs in 256 parts and the amount of time required by METIS
to compute fill-reducing orderings for various sparse matrices.
The rest of this manual is organized as follows: Section 4 describes the user interface to the stand-alone programs
provided by METIS. Section 5 describes the stand-alone library that implements the various algorithms implemented
in METIS. Finally, Section 6 describes the system requirements for the METIS package.
5
剩余43页未读,继续阅读
jfchang
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0