Dewedseed's Blog

Metis 图分割工具

运用 Metis 工具分割非结构网格和结构网格用于并行计算

Question

  1. Metis 和 ParMetis 的区别
  2. Graph 和 Mesh 的区别
  3. 运用 Metis 划分结构网格
  4. 运用 Metis 划分非结构网格

Introduction

  1. “Metis” was a titaness in Greek mythology and presided over all wisdom and knowledge.
  2. Application
    • graph and mesh partitioning
    • compute fill-reducing orderings of sparse matrices
    • solving optimization problems arising in numerous areas
  3. Algorithm
    • multilevel k-way partitioning
    • multilevel recursive bisection
  4. Version
    • 5.x 版本相较 4.x 版本有较大变动
  5. Implement
    • Stand-alone Programs + File – Graph/Mesh/Weight
    • API – C/C++/Fortran

fill-reducing orderings

一种稀疏矩阵排列方法，旨在减少矩阵分解过程中的 fill-in 元素

Algorithm

Graph

  1. METIS 算法基于 multilevel graph partitioning paradigm
  2. multilevel paradigm 包含三个 Phase
    • graph coarsening: 图形粗化
    • initial partitioning: 初始化分割
    • graph uncoarsening: 图形细化
  3. multilevel recursive bisection
  4. multilevel k-way partitioning
    • minimize the resulting subdomain connectivity graph
    • enforce contiguous partitions
    • minimize alternative objectives
  5. METIS 算法通过将各点添加权重矢量从而均衡不同阶段和不同物理场中每个域的计算负载和存储资源

Mesh

METIS 通过 mpmetis 程序分割有限元或有限体积网格 (Mesh)

  1. 程序 m2gmetis 首先将网格转换为 Graph
    • Dual Graph: 将 Mesh Element 转换为 Graph Vertex
    • Nodal Graph: 将 Mesh Node 转换为 Graph Vertex
  2. 调用 Graph partitioning API 分割 Graph
  3. 还原网格

METIS 未直接提供网格的多约束分割功能，因此需要通过 m2gmetis 间接实现

Heterogeneous

异构计算

Data Structrue

Graph Data

  1. Graph
mindmap
  v1((1))
     v2((2))
     v3((3))
     v4((5))
  1. Graph file
1
2
3
4
5
6
7 11 111 3             |  (n m fmt ncon)
2 1 2 0 5 1 3 2 2 1    |  (s w1 w2 .. w_ncon v1 e1 v2 e2 .. vk ek)
...                    |  ...

n_vert, n_edge, vert_size/w_vert/w_edge, nw_vert
vert_size, w_vert, conn_vert, w_edge

Graph file format

  1. n = 7 number of vertices
  2. m = 11 number of edges
  3. fmt = 111 whether set vertex sizes, vertex weights, and edge weights
  4. ncon = 3 number of vertex weights
  5. s = 2 vertex size, amount of data that needs to be sent for vertex
  6. w = (1 2 0) weight of vertex
  7. v e = (5 1) (3 2) (2 1) (adjacent vertex, edge weight)
  1. API Graph CSR (Compressed storage format)
1
2
3
4
5
6
7
    1 --- 2 --- 3 --- 4
    |     |     |     |
    5 --- 6 --- 7 --- 8

 index  1   2     3     4   5    ... 8
  xadj  1   3     6     9   11   ... 19   21
adjncy  2 5 1 3 6 2 4 7 3 8 1  6 ... 4  7

CSR Format

  1. xadj index of adjacency array for each vertex
  2. xadj(n+1) - 1 is last index of adjacency array
  3. adjncy(2m) array of adjacency vertices of each vertex
  4. vwgt(n*ncon) weights of the vertices (same weight => NULL)
  5. adjwgt(2m) weights of the edges (same weight => NULL)

Mesh Data

  1. Mesh File
1
2
3
7 2          |  (ne ncon)
3 1 1 3 4 2  |  (w1 w2 .. w_ncon n1 n2 ..)
...

Mesh file format

  1. ne = 7 number of elements
  2. ncon = 2 optinal, number of element weights
  3. w = (3 1) element weight
  4. n = (1 3 4 2) element node array (unordered)
  1. API mesh format
1
2
3
4
5
6
7
    1 --- 2 --- 3 --- 4
    |  I  | II  | III |
    5 --- 6 --- 7 --- 8

index  1       2       3
 eptr  1       5       9       13
 eind  1 2 5 6 2 3 6 7 3 4 7 8

Mesh Data Structrue

  1. eptr index of eind array for each element
  2. eind list of element nodes (unordered)

Implementation

Multi-Block Structrual Mesh

  1. Strategies: top-down bottom-up
  2. Communication Cost
    • number of communication (edge cuts)
    • volume of communication
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
less edge cuts

    * -- * -- * -- * -- *
    |    |    |    |    |
    |    |    |    |    |
    |    |    |    |    |
    |    |    |    |    |
    |    |    |    |    |
    |    |    |    |    |
    |    |    |    |    |
    * -- * -- * -- * -- *

small volume of communication

    * ------- * ------- *
    |         |         |
    |         |         |
    |         |         |
    * ------- * ------- *
    |         |         |
    |         |         |
    |         |         |
    * ------- * ------- *
  1. Group and merge Small Blocks
  2. Method
    • REB Recursive Edge Bisection
    • IF Integer Factorization

IF Partition (N = 7, 73, 16, 27)

NPartition 7
NPartition 73
NPartition 16
NPartition 27

Error Accumulation of IF

  1. Block Partition

volume of single blockVs=V×1np(1±ε)volume of other blockVu=V−Vsnp−1=V×1np(1∓εnp−1)\begin{align} & \text{volume of single block} \qquad V_s = V \times \frac{1}{n_p} (1 \pm \varepsilon) \\ & \text{volume of other block} \qquad V_u = \frac{V - V_s}{n_p -1} = V \times \frac{1}{n_p} (1 \mp \frac{\varepsilon}{n_p - 1}) \\ \end{align}

  1. Load Imbalance

For single block(Vave−Vs)2=Vave2×ε2For other block(Vave−Vu)2=Vave2×ε2/(np−1)2VarianceS2=1np((Vave−Vs)2+(np−1)(Vave−Vu)2)DeviationS=Vaveεnp−1ImbalanceSVave=εnp−1\begin{align} & \text{For single block} \qquad (V_{ave} - V_s)^2 = V_{ave}^2 \times \varepsilon^2 \\ & \text{For other block} \qquad (V_{ave} - V_u)^2 = V_{ave}^2 \times \varepsilon^2/(n_p-1)^2 \\ & \text{Variance} \qquad S^2 = \frac{1}{n_p} \left( (V_{ave} - V_s)^2 + (n_p - 1) (V_{ave} - V_u)^2 \right) \\ & \text{Deviation} \qquad S = V_{ave} \frac{\varepsilon}{\sqrt{n_p - 1}} \\ & \text{Imbalance} \qquad \frac{S}{V_{ave}} = \frac{\varepsilon}{\sqrt{n_p - 1}} \\ \end{align}

Unstructural Mesh

Program

Fortran 中无法直接调用 metis.h 文件，需要编写接口，具体可参考

  1. metis | JCSDA
  2. METIS for fpm | gnikit
  3. fmetis | ivan-pi
  4. Formetis | SWIG-Fortran

Compile

Install

  1. 安装 Metis
1
2
3
4
5
6
7
8
9
10
11
12
# clone src
git clone https://github.com/KarypisLab/METIS.git
git clone https://github.com/KarypisLab/GKlib.git
wget https://github.com/KarypisLab/METIS/archive/refs/tags/v5.1.1-DistDGL-v0.5.tar.gz
# build GKlib (CMake 2.8, use cmake 3.28 here)
cd GKlib
make config prefix=$HOME/local/metis/metis-5.2.1 CONFIG_FLAGS='-D BUILD_SHARED_LIBS=ON -D CMAKE_INSTALL_PREFIX='$HOME'/local/metis/metis-5.2.1'
make && make install
# build metis
cd METIS
make config shared=1 cc=gcc prefix=$HOME/local/metis/metis-5.2.1
make install

Compile GKlib

https://github.com/KarypisLab/METIS/issues/82

  1. 添加环境
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#%Module

proc ModulesHelp {} {
  puts stderr "Program:     METIS $::version"
  puts stderr "Description: Karypis -- A set of serial programs for partitioning graphs, "
  puts stderr "                        partitioning finite element meshes, and producing "
  puts stderr "                        fill reducing orderings for sparse matrices. "
  puts stderr "Github:      https://github.com/KarypisLab/METIS"
  puts stderr {}
}

set             version     5.2.1
set             prefix      $HOME/local/metis/metis-$version

module-whatis "METIS -- Graphs and mesh partition program"

setenv          METIS_HOME         $prefix
setenv          METIS_INCLUDE      $prefix/include
setenv          METIS_LIB          $prefix/lib
prepend-path    PATH               $prefix/bin
prepend-path    LD_LIBRARY_PATH    $prefix/lib

Make

  1. Makefile

  2. CMake

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
## FindMETIS
set(METIS_ROOT ${PROJECT_SOURCE_DIR}/ext/METIS-5.2.1)

find_path(
  METIS_INCLUDE_PATH
  NAMES metis.h
  PATHS ${METIS_ROOT}/include
)

find_library(
  METIS_LIBRARY
  NAMES metis
  PATHS ${METIS_ROOT}/lib
  NO_DEFAULT_PATH
)

if(METIS_INCLUDE_PATH AND METIS_LIBRARY)
  set(METIS_FOUND TRUE)
  set(METIS_LIBRARY ${METIS_LIBRARY})
  set(METIS_INCLUDE_PATH ${METIS_INCLUDE_PATH})
else()
  set(METIS_FOUND FALSE)
endif()

## Find GKlib
set(GKLIB_ROOT ${PROJECT_SOURCE_DIR}/ext/METIS-5.2.1)

find_path(
  GKLIB_INCLUDE_PATH
  NAMES GKlib.h
  PATHS ${GKLIB_ROOT}/include
)

find_library(
  GKLIB_LIBRARY
  NAMES GKlib
  PATHS ${GKLIB_ROOT}/lib
  NO_DEFAULT_PATH
)

if(GKLIB_INCLUDE_PATH AND GKLIB_LIBRARY)
  set(GKLIB_FOUND TRUE)
  set(GKLIB_LIBRARY ${GKLIB_LIBRARY})
  set(GKLIB_INCLUDE_PATH ${GKLIB_INCLUDE_PATH})
else()
  set(GKLIB_FOUND FALSE)
endif()

## find package
find_package(GKLIB REQUIRED)
if(GKLIB_FOUND)
    include_directories(${GKLIB_INCLUDE_PATH})
    message(STATUS "GKLIB library: ${GKLIB_LIBRARY}")
    message(STATUS "GKLIB include: ${GKLIB_INCLUDE_PATH}")
else()
    message(FATAL_ERROR "GKLib library not found")
endif()
find_package(METIS REQUIRED)
if(METIS_FOUND)
    include_directories(${METIS_INCLUDE_PATH})
    message(STATUS "METIS library: ${METIS_LIBRARY}")
    message(STATUS "METIS include: ${METIS_INCLUDE_PATH}")
else()
    message(FATAL_ERROR "METIS library not found")
endif()

Linker Attention

注意 Cmake 中必须按照 METIS-GKLIB 顺序链接

1
target_link_libraries(${EXEC} ${METIS_LIBRARY} ${GKLIB_LIBRARY})

Reference

0%