METIS 非结构化图形划分、网格划分和计算软件包网格划分和计算稀疏矩阵的填充还原排序的软件包稀疏矩阵的填充还原排序

date

Apr 23, 2025

slug

METIS

status

Published

1 引言

在串行和并行计算机上，为高度非结构化图找到良好的划分对于开发许多应用领域的高效解决方案至关重要。例如，在基于有限元方法的并行计算机上的大规模数值模拟中，需要将有限元网格分配给处理器。这种分配必须确保每个处理器分配到的元素数量相同，并且分配给不同处理器的相邻元素数量最小化。第一个条件的目标是平衡处理器之间的计算量，第二个条件的目标是减少由于相邻元素被分配到不同处理器而导致的通信量。通过首先将有限元网格建模为图，然后将其划分为等分，图划分可以成功满足这些条件。图划分算法还用于计算稀疏矩阵的填充减少排序。这些填充减少排序在使用直接方法求解稀疏线性方程组时非常有用。良好的稀疏矩阵排序可以显著减少求解方程组所需的内存和时间。此外，由图划分算法产生的填充减少排序特别适合于并行直接分解，因为它们在分解阶段可以实现高度的并行性。图划分还用于解决众多领域的优化问题，如超大规模集成电路（VLSI）设计、空间数据库的存储和访问、交通管理以及数据挖掘。

2 METIS 5.0 版本中的新特性

版本 5.0 几乎是对代码库的完全重写，其目的是简化和统一独立程序和 API，更好地支持 64 位架构，增强功能，并通过重构内部内存管理例程来减少内存需求。因此，独立程序和 API 的功能都发生了变化，使其与早期版本的 METIS 不兼容。然而，为了尽量减少代码修改，新的 API 在引入的大多数新参数上依赖于合理的默认值。以下是一些主要的功能相关变化和增强，这些功能可以通过命令行程序和 API 调用来访问。

多约束划分可以与最小化总通信量结合使用。

所有的图和网格划分例程现在都接受划分的目标大小作为输入，这使得它们能够计算出适合具有异构计算能力的并行架构的划分解决方案。

当使用多约束划分时，划分的目标大小是按每个划分约束对指定的。

多级 k-路划分算法可以计算出每个划分都是连续的划分解决方案。

所有的划分和排序例程都可以计算多个不同的解决方案，并选择最佳的一个作为最终解决方案。

网格划分和网格到图的转换例程可以处理混合元素网格。

命令行程序提供了对 METIS API 提供的全部功能的完全访问。

2.1 命令行程序的变化

表 1 显示了 v4.x 命令行程序如何映射到 5.0 版本提供的新命令行程序。作为这些变化的一部分，旧程序提供的所有功能都没有被移除。相反，新程序通过扩展这些程序可以接受的可选参数数量来实现这一点，这使得用户可以完全访问 METIS 的所有功能。在之前的版本中，如果用户想要访问 METIS 的一些高级功能，他们必须基于提供的 API 编写自己的程序。

2.1.1 迁移问题

为了支持新命令行程序提供的增强功能，图和网格文件的格式发生了变化（第 4.1 节）。在图文件的情况下，新格式是向后兼容的，因此为早期格式编写的图在被 gpmetis 和 ndmetis 使用时将正确工作。然而，新的网格文件格式不是向后兼容的，因此不应将它们与 mpmetis 和 m2gmetis 一起使用。幸运的是，通过稍微修改它们的头行，可以轻松地将它们转换为新格式。

2.2 API 例程的变化

表 2 显示了 v4.x API 例程如何映射到 5.0 版本提供的新 API。通过扩展新例程的调用序列以提供旧专用例程提供的功能，将不同核心函数的数量减少到七个。在大多数情况下，新 API 例程提供的功能是旧例程提供的功能的超集，特别是在与异构计算架构的划分、多约束划分和基于通信量的划分目标相关的领域。

2.2.1 迁移问题

由于所有 API 例程的调用序列以及在某些情况下它们的名称已经改变，迁移到新的 API 将需要代码修改。为了确保这些修改最小化，新的 API 例程允许用户为许多有合理默认值的参数提供 NULL 作为参数。因此，我们预计迁移到新的 API 将相当直接，只要应用程序不想利用新添加的功能。

3 METIS 概述

METIS 是一个用于划分大型不规则图、划分大型网格以及计算稀疏矩阵填充减少排序的串行软件包。METIS 由明尼苏达大学计算机科学与工程系开发，并免费分发。

其源代码可以直接从 http://www.cs.umn.edu/~metis 下载，并且也被包含在许多类 Unix 操作系统（如 Linux 和 FreeBSD）的软件分发中。METIS 中实现的算法基于多级图划分范式 [4, 3, 2]，该范式已被证明能够快速产生高质量的划分和填充减少排序。多级范式如图 1 所示，包括三个阶段：图粗化、初始划分和粗化解除。在图粗化阶段，从输入图中导出一系列逐渐变小的图。每个后续图都是通过将前一个图中最大数量的相邻顶点对折叠在一起构建的。这个过程一直持续到图的大小减少到只有几百个顶点。在初始划分阶段，计算最粗的（因此也是最小的）图的划分，使用相对简单的方法，如由 Kernighan-Lin [5] 开发的算法。由于最粗的图通常非常小，所以这一步非常快。最后，在粗化解除阶段，将最小图的划分投影到逐渐变大的图上，通过将折叠在一起的顶点对分配给它们对应的折叠顶点所在的同一个划分。在每次投影步骤之后，使用各种启发式方法细化划分，通过迭代移动顶点在划分之间移动，只要这种移动能够改善划分解决方案的质量。当划分解决方案被投影回原始图时，粗化解除阶段结束。METIS 在粗化过程中采用新方法逐步减小图的大小，并在粗化解除阶段细化划分。在粗化过程中，METIS 采用的算法使其更容易在最粗的图中找到高质量的划分。在细化过程中，METIS 主要关注靠近划分边界的部分。这些经过高度调整的算法使得 METIS 能够快速为各种不规则图、非结构化网格和稀疏矩阵产生高质量的划分和填充减少排序。

3.1 划分图

METIS 可以使用多级递归二分 [4] 或多级 k 路划分 [3] 范式将非结构化图划分为用户指定数量的 k 个部分。这两种方法都能够产生高质量的划分。然而，METIS 的多级 k 路划分算法提供了额外的能力（例如，最小化结果子域连通性图、强制连续划分、最小化替代目标等），因此它可能比多级递归二分更受青睐。METIS 划分图的独立程序是 gpmetis，其功能由 METIS PartGraphRecursive 和 METIS PartGraphKway API 例程实现。

3.2 替代划分目标

传统图划分问题的目标是计算一个 k 路划分，使得跨越不同划分的边的数量（或者在加权图的情况下是它们的权重之和）最小化。这个目标通常被称为边割。当划分用于将图或网格分配给并行计算机的处理器时，最小化边割的目标只是近似地反映了划分导致的真实通信成本 [1]。由 k 路划分导致的通信成本通常取决于以下因素：

(i) 总通信量，

(ii) 任何特定处理器需要发送和接收的最大数据量；以及

(iii) 处理器需要发送和接收的消息数量。METIS 的多级 k 路划分方法可以直接最小化划分导致的总通信量（第一个因素）。此外，METIS 还支持最小化第三个因素（这实际上减少了启动次数），并间接（在一定程度上）减少了第二个因素。

3.3 支持多阶段和多物理计算

传统图划分问题的表述在它可以有效建模的应用程序类型上是有限的，因为它规定只能平衡一个量。许多重要的多阶段和多物理计算需要同时平衡多个量。这是因为不同计算阶段之间存在同步步骤，因此，每个阶段必须单独平衡。也就是说，仅仅将每个阶段所需的相对时间相加，并基于这个总和计算划分是不够的。这样做可能会导致一些处理器在计算的一个阶段中工作量过多（因此，这些处理器可能在其他处理器空闲后仍在工作），而在另一个阶段中工作量不足。相反，至关重要的是每个处理器在计算的每个阶段都有相等的工作量。METIS 包含划分例程，可以在存在多个平衡约束的情况下划分图。现在每个顶点都被分配了一个 m 维的权重向量，划分例程的目标是在满足每个 m 权重在划分之间均匀分布的约束条件下最小化边割。例如，如果第一个权重对应于每个元素的计算量，第二个权重对应于每个元素所需的存储量，那么新算法计算出的划分将平衡每个划分中执行的计算量以及它所需的内存量。多约束划分算法及其应用在 [2] 中有进一步描述。当输入图指定了多个顶点权重时，gpmetis 程序会调用多约束划分例程，所有它的图划分 API 例程都允许指定多个平衡约束。

3.4 划分网格

METIS 提供了 mpmetis 程序，用于划分有限元或有限体积方法中产生的网格。这个程序以网格的元素-节点数组作为输入，并为网格的元素和节点计算一个 k 路划分。这个程序首先将网格转换为对偶图（即，每个元素成为一个图顶点）或节点图（即，每个节点成为一个图顶点），然后使用图划分 API 例程来划分这个图。METIS 采用了一种灵活的方法来为有限元网格创建图，这使得它可以处理具有不同且可能是混合元素类型的网格（例如，三角形、四面体、六面体等）。mpmetis 提供的功能由 METIS PartMeshNodal 和 METIS PartMeshDual API 例程实现。

3.5 为异构并行计算架构划分

包含具有不同计算和内存能力的处理节点的异构计算平台变得越来越常见。METIS 的图和网格划分程序和 API 例程被设计为将图划分为 k 个部分，使得每个部分包含总顶点数/元素数/节点数的预指定比例。此外，在多约束划分的情况下，这些预指定的比例是针对每个顶点权重提供的。通过将每个划分指定的权重与各种处理器的相对计算和内存能力相匹配，这些例程可以用来计算在异构架构上平衡计算的划分。

3.6 计算稀疏矩阵的填充减少排序

METIS 提供了 ndmetis 程序及其相关的 METIS NodeND API 例程，用于基于多级嵌套剖分范式 [4] 计算稀疏矩阵的填充减少排序。嵌套剖分范式基于计算对应于矩阵的图的顶点分隔器。分隔器中的节点被移动到矩阵的末尾，并且对剩下的两个部分递归地应用类似的过程。多级嵌套剖分范式在产生低填充的重排序方面非常有效。

3.7 将网格转换为图

METIS 提供了 m2gmetis 程序，用于将网格转换为 METIS 可以使用的图格式。这个程序可以生成网格的节点图或对偶图。对应的 API 例程是 METIS MeshToNodal 和 METIS MeshToDual。由于 METIS 没有直接计算多约束网格划分的 API 例程，这些例程可以用来首先将网格转换为图，然后将该图作为输入传递给 METIS 的图划分例程以获得此类划分。

4 METIS 的独立程序

METIS 提供了一系列程序，可用于划分图、划分网格、计算稀疏矩阵的填充减少排序，以及将网格转换为适用于 METIS 图划分程序的图。

4.1 输入文件格式

METIS 中的各种程序需要输入一个存储图或网格的文件。这些文件的格式在以下各节中描述。

4.1.1 图文件

METIS 中划分和填充减少排序程序的主要输入是待划分或排序的无向图。该图存储在一个文件中，并作为命令行参数之一提供给各个程序。图 G = (V, E) 包含 n 个顶点和 m 条边，存储在一个纯文本文件中，包含行（不包括注释行）。第一行，即标题行，包含有关图的大小和类型的信息，而剩下的行包含有关的每个顶点的信息。任何以‘%’开头的行都是注释行，将被跳过。标题行包含两个（ n, m ）、三个（）或四个（）参数。前两个参数（ n, m ）分别是顶点数和边数。注意，在确定边数 m 时，每对顶点 v 和 u 之间的边只计算一次，而不是两次（即，我们不分别计算边和）。例如，图 2 中的图包含 11 个顶点。fmt 参数用于指定图文件是否包含有关顶点大小、顶点权重和边权重的信息。fmt 参数是一个三位二进制数。如果最不显著位（即，从右到左的第 1 位）设置为 1，则图文件提供有关边权重的信息。如果第二不显著位（即，从右到左的第 2 位）设置为 1，则图文件提供有关顶点权重的信息。最后，如果第三不显著位（即，从右到左的第 3 位）设置为 1，则图文件提供有关顶点大小的信息。例如，如果 fmt 是 011，则图文件提供有关顶点权重和边权重的信息。注意，当未提供 fmt 参数时，假定顶点大小、顶点权重和边权重都等于 1。

ncon 参数指定与图的每个顶点相关联的顶点权重的数量。此参数的值决定 METIS 是否使用多约束划分算法（第 3.3 节）。如果省略此参数，则假定图的顶点具有单个权重。注意，如果 ncon 大于 0，则文件应包含所需的顶点权重，并且 fmt 参数应适当设置（即，从右到左的第 2 位应设置为 1）。剩下的 n 行存储有关图的实际结构的信息。具体来说，第 i 行（不包括注释行）包含与第 i 个顶点相关的信息。根据 fmt 和 ncon 参数的值，每行存储的信息略有不同。在最一般的形式（当 fmt = 111 且 ncon > 1）中，每行将具有以下结构（所有元素均为整数）：

其中 s 是顶点的大小，是与该顶点相关联的 ncon 个顶点权重，是与该顶点相邻的顶点，而是这些边的权重。顶点（即各个条目）的编号从 1 开始（而不是像 C 中那样从 0 开始）。此外，顶点大小和顶点权重必须是大于或等于 0 的整数，而边权重必须严格大于 0。

顶点大小与顶点权重：图格式允许指定顶点大小和顶点权重。这两个量被 METIS 用于完全不同的目的。顶点权重用于确保计算出的划分满足指定的平衡约束（例如，分配给每个划分的顶点权重之和在各划分之间相同）。另一方面，顶点大小用于确定总通信量，当使用 gpmetis 和 mpmetis 时，带有 -objtype=vol 选项。有关顶点大小如何用于确定通信量的更多详细信息，请参阅第 5.7 节，该节提供了计算总通信量的精确公式。

示例：图 2 通过提供一些示例来说明格式。图 G 的最简单格式是当所有顶点和边的大小和权重相同时。此格式如图 2(a) 所示。注意，在此情况下省略了可选的 fmt 参数。然而，存在边权重不同的情况。如图 2(b) 所示，现在每个顶点的邻接表中包含了边的权重以及与之相连的顶点。如果顶点 v 有 k 个相邻顶点，则 v 在图文件中的行包含个数字，每对数字存储 v 所连接的顶点以及该边的权重。注意，fmt 参数等于 001，表示图的边有权重。除了边有权重外，顶点也可以有权重，如图 2(c) 所示。在此情况下，fmt 的值为 011，图文件的每一行首先存储顶点的权重，然后是加权邻接表。最后，图 2(d) 展示了当图的顶点包含多个权重（本例中为 3 个）时输入文件的格式。在此情况下，fmt 的值为 011，ncon 的值为 3（因为我们有三组顶点权重）。图文件的每一行存储三个顶点权重，后跟邻接表。

4.1.2 网格文件

METIS 中网格划分程序的主要输入是待划分的网格。该网格以元素节点数组的形式存储在一个文件中。包含 n 个元素的网格存储在一个纯文本文件中，包含 n + 1 行。第一行（即标题行）包含有关网格的大小和类型的信息，而剩下的 n 行包含构成每个元素的节点。第一行包含两个整数参数。第一个参数是网格中的元素数 n 。第二个参数是可选的，表示与每个元素相关联的权重数。这相当于图文件中的 ncon 参数，用于指定对偶图中顶点的权重。如果省略此参数，则假定对偶图中顶点的权重为 1。

在第一行之后，剩下的 n 行存储元素节点数组。具体来说，对于元素 i ，第 i + 1 行存储与第 i 个元素相关联的 ncon 个整数权重（如果指定了可选的 ncon 参数），后跟构成该元素的节点。权重和节点之间用空格分隔。节点的编号从 1 开始。每个元素的节点可以以任意顺序存储。网格文件允许混合元素网格，因此每行中提供的节点数量可以不同。

4.1.3 目标划分权重文件

图和网格划分例程接受一个可选文件作为输入，该文件指定了各个划分的目标权重（使用 -tpwgts 选项）。该文件包含一系列行，其格式如下：

方括号中的部分表示可选部分。上述规范的含义如下：对于从 fromcnum 到 tocnum（包括）的约束，以及从 frompid 到 topid（包括）的划分，将分配目标权重 twgt。如果未提供 [- topid]，则 topid = frompid。如果未提供 [- tocnum]，则 tocnum = fromcnum。如果省略 [: fromcnum [- tocnum]]，则 fromcnum = 0 且 tocnum = ncon - 1。如果文件中未为所有目标划分权重/约束组合指定 twgt 规范，则未指定的组合的 twgt 将通过等比例分配每个约束的剩余总权重来确定。重要的是，对于每个约束，指定的 twgts 值之和必须小于或等于 1.0。例如，假设 ncon = 1，nparts = 5，则以下 tpwgts 文件：

指定的目标划分权重为：

注意，part[2] 和 part[3] 的 0.15 比例是由于剩余权重（1.0 - 0.7）的等比例分配得出的。

4.2 输出文件格式

METIS 的输出是一个划分文件或排序文件，具体取决于 METIS 是用于图/网格划分还是稀疏矩阵排序。这些文件的格式在以下各节中描述。

4.2.1 划分文件

包含个顶点的图的划分文件由行组成，每行包含一个数字。该文件的第行包含第个顶点所属的划分编号。划分编号从 0 开始，一直到划分数量减 1。

4.2.2 排序文件

包含个顶点的图的排序文件由行组成，每行包含一个数字。该文件的第行包含图的第个顶点的新顺序。排序文件中的编号从 0 开始。注意，排序文件存储的是排序的逆置换向量 iperm。设 \( A \) 是一个矩阵，\( A' \) 是重排序后的矩阵。逆置换向量将的第行（列）映射到的第 iperm[i] 行（列）。

4.3 程序

gpmetis

功能：将图划分为指定数量的部分。计算出的划分存储在一个名为 graphfile.part.nparts 的文件中，其中 graphfile 和 nparts 是指定的参数。

参数：

graphfile：存储待划分图的文件名（第 4.1.1 节）。

nparts：图将被划分成的部分数。该值应大于 1。

选项：

ptype=string：指定用于计算划分的方案。可能的值：

rb：多级递归二分。
kway：多级 k 路划分 [默认]。

ctype=string：指定在粗化过程中用于匹配图的顶点的方案。可能的值：

rm：随机匹配。
shem：排序重边匹配 [默认]。

iptype=string（仅当 -ptype=rb 时适用）：指定用于计算图的初始划分的方案。可能的值：

grow：使用贪婪策略增长二分 [默认]。
random：随机计算二分，随后进行细化。

objtype=string（仅当 -ptype=kway 时适用）：指定划分的目标函数。可能的值：

cut：最小化边割 [默认]。
vol：最小化总通信量。

no2hop：指定在粗化过程中，当标准匹配方法无法充分粗化图时，不执行任何 2 跳匹配。2 跳匹配对于具有幂律度分布的图非常有效。如果与早期版本的 METIS 相比，划分质量较低，则可以指定此选项以关闭这种类型的匹配。

contig（仅当 -ptype=kway 时适用）：指定划分例程应尝试产生连续的划分。注意，如果输入图不连通，则忽略此选项。

minconn（仅当 -ptype=kway 时适用）：指定划分例程应尝试最小化子域图的最大度，即每个划分是一个节点，边连接具有共享界面的子域的图。

tpwgts=filename：指定存储每个约束的目标权重的文件名（第 4.1.3 节）。默认情况下，对于每个约束，所有划分的大小相同。

ufactor=int：指定划分之间允许的最大负载不平衡。在 METIS OPTION UFACTOR 下描述。注意，在多约束情况下，相同的负载不平衡容差应用于所有约束。使用 -ubvec 提供每个约束的负载不平衡容差。

ubvec=string：指定每个约束的允许负载不平衡。该字符串必须包含一个以空格分隔的浮点数列表，每个约束一个。例如，对于三个约束，该字符串可以是 "1.02 1.2 1.35"，分别表示期望的最大负载不平衡为 2%、20% 和 35%。负载不平衡的定义类似于 -ufactor。如果提供，则此参数优先于 ufactor。

niter=int：指定在粗化解除过程的每个阶段细化算法的迭代次数。默认值为 10。

ncuts=int：指定将计算的不同划分数量。最终划分是实现最佳边割或通信量的划分。默认值为 1。

nooutput：指定不生成划分文件。

seed=int：选择随机数生成器的种子。

dbglvl=int：指定将打印到 stdout 的进度/调试信息的类型。提供的值对应于在第 5.4 节中描述的 METIS OPTION DBGLVL 的值的加法（按位或）。默认值为 0（不打印进度/调试信息）。

help：显示命令行选项及其描述。