METIS

1. 개요

METIS Serial Graph Partitioning and Fill-reducing Matrix Ordering
개발	George Karypis, Vipin Kumar (미네소타대)
첫 공개	1995년경 (현행 5.x)
핵심 기법	다단계(multilevel) 그래프 분할
목적함수	edge-cut 최소화 + 부하 균형 제약
주력 기능	k-way 분할 · 메시 분할 · 중첩 분할 순서화
라이선스	Apache 2.0 (5.2.0부터)
형제 프로젝트	ParMETIS, hMETIS

코어 512개를 샀는데 한 코어만 죽어라 일하고 511개가 논다면, 그건 하드웨어 문제가 아니라 분할 문제다.

METIS는 미네소타대의 George Karypis와 Vipin Kumar가 만든 그래프·메시 분할 및 희소행렬 순서화 라이브러리로, 대규모 병렬 해석에서 계산 영역을 프로세스마다 나눠 주는 사실상의 표준 도구다. 격자 수백만 셀짜리 유한체적법 케이스를 128 랭크로 돌릴 때, “어느 셀이 어느 랭크로 가는가”를 결정하는 그 한 번의 호출이 대부분 METIS다.

분할 문제 자체는 NP-난해다. 정점 집합을 균형 있게 $k$개로 나누면서 잘리는 간선 가중치 합을 최소화하는 문제는 $k=2$에서도 이미 NP-완전이라, 최적해를 노리는 순간 게임이 끝난다. METIS의 존재 이유는 최적해가 아니라, 실무에서 쓸 만한 해를 그래프 크기에 거의 선형인 시간에 뽑아 준다는 것이다.¹

2. 무엇을 최소화하는가

METIS가 푸는 표준 문제는 이렇다. 가중 그래프 $G=(V,E)$를 서로소인 $V_1,\dots,V_k$로 나눌 때

$$\min \; \mathrm{cut}(P) = \sum_{\substack{(u,v)\in E \\ P(u)\neq P(v)}} w(u,v) \quad \text{s.t.} \quad \max_i \frac{w(V_i)}{w(V)/k} \le 1+\varepsilon$$

정점 가중치는 셀당 계산량, 간선 가중치는 두 셀 사이에 오갈 데이터량에 대응시킨다. 불균형 허용치 $\varepsilon$은 API에서 ufactor로 준다(5.x에서 ufactor=30이면 1.03배까지 허용). 균형 제약을 조이면 cut이 나빠지고, 풀면 특정 랭크가 늦게 끝나 전체가 기다린다 — 이 트레이드오프를 다이얼 하나로 노출한 게 ufactor다.

그런데 edge-cut은 통신량의 대리지표일 뿐 통신량 그 자체가 아니다. 한 정점이 이웃 3개를 다른 파티션에 두고 있으면 잘린 간선은 3개지만, 실제로는 자기 값 하나를 3곳에 보내면 되므로 통신 볼륨은 1(×수신처 수)이다. 진짜 목적함수는 총 통신 볼륨 $\sum_v (\lambda(v)-1)$ — 정점 $v$와 그 이웃이 걸친 서로 다른 파티션 수 $\lambda(v)$로 세는 값 — 이거나, 더 현실적으로는 최대 랭크 통신량이다. 이걸 정확히 다루려면 그래프가 아니라 하이퍼그래프 분할이 필요하고, 그게 hMETIS·PaToH·Zoltan-PHG의 영역이다.² 다만 격자처럼 정점 차수가 낮고 균질한 그래프에서는 edge-cut과 통신량이 거의 비례해서, CFD/FEM 실무에서는 METIS로 충분한 경우가 압도적이다.

3. 다단계 기법 — 세 국면

METIS의 알고리즘 전부는 “큰 그래프에서 좋은 분할을 직접 찾지 말고, 작게 줄여서 찾은 다음 되돌리며 다듬자”는 한 문장으로 요약된다. 다중격자법이 저주파 오차를 조대 격자에서 잡는 것과 발상이 똑같다.

3.1. 1) 코스닝 (coarsening)

원 그래프에서 정점들을 짝지어(matching) 하나의 초정점으로 합친다. 합쳐진 간선 가중치는 더해지고, 정점 가중치도 더해진다. 기본 전략은 HEM(heavy edge matching) — 정점을 임의 순서로 방문하며, 아직 짝이 없는 이웃 중 가장 무거운 간선으로 연결된 쪽과 짝을 짓는다. 무거운 간선을 미리 초정점 내부로 삼켜 버리면 그 간선은 애초에 잘릴 수 없으므로, 조대 그래프의 cut 자체가 작아진다. 매칭 한 번에 정점 수는 대략 절반씩 줄고, 이 과정을 정점 수가 수백 개(보통 $k$의 상수배) 수준이 될 때까지 반복해 그래프 계층 $G_0 \to G_1 \to \cdots \to G_m$을 쌓는다.

3.2. 2) 초기 분할 (initial partitioning)

최거친 그래프 $G_m$은 정점이 수백 개뿐이라 아무 방법이나 써도 싸다. METIS는 GGGP(greedy graph growing partitioning) 계열 — 임의 정점에서 시작해 이득이 가장 큰 이웃을 계속 흡수하며 절반을 채우는 방식 — 을 여러 무작위 시드로 반복하고 가장 좋은 것만 남긴다. 여기서 시드를 여러 개 굴리는 비용이 전체에서 무시할 수준이라는 게 다단계의 큰 이점이다.

3.3. 3) 비코스닝 + FM 정련 (uncoarsening + refinement)

초정점을 원래 정점들로 되돌리며 각 레벨에서 분할을 다듬는다. 다듬는 도구가 FM(Fiduccia–Mattheyses) 정련이다. 커니핸-린(KL)의 쌍 교환을 단일 정점 이동으로 바꾸고, 각 정점의 이득(gain, 옮겼을 때 줄어드는 cut) 값을 버킷 배열의 이중 연결 리스트에 담아 최대 이득 정점을 $O(1)$에 뽑는 자료구조가 핵심이다.

FM 패스의 성격은 이렇다.

• 한 패스에서 각 정점은 최대 한 번만 이동하고, 이동한 정점은 잠긴다(lock). 무한 진동 방지.
• 이득이 음수여도 일단 옮긴다. 지금 손해를 보고 넘어가야 국소최적을 탈출할 수 있다. 그리디만 하면 경계 하나 넘기고 끝난다.
• 이동 시퀀스의 누적 이득이 최대가 되는 접두사를 기억해 두었다가, 패스가 끝나면 그 지점 이후 이동을 전부 롤백한다. 즉 패스 전체는 “탐색해 보고 제일 좋았던 지점으로 되감기”다.

METIS는 여기에 경계 정련(boundary refinement) 을 얹는다. 이득이 0이 아닐 수 있는 정점은 어차피 파티션 경계에 있는 것들뿐이므로, 경계 정점만 우선순위 큐에 넣는다. 이 최적화 덕에 정련 비용이 그래프 크기가 아니라 경계 크기에 비례하게 된다. 조대 레벨에서 이미 좋은 분할을 잡아 놨기 때문에, 세밀한 레벨에서는 국소 수선만 하면 되고 — 그래서 전체가 빠르다.

4. k-way, 다중 제약, 그리고 순서화

$k$개로 나누는 방법은 두 갈래다. 재귀 이분할(METIS_PartGraphRecursive)은 2분할을 $\log_2 k$번 되풀이한다. 구현이 단순하지만 각 이분할이 자기 지역만 보므로 전역적으로 손해가 나고, 균형 제약도 층층이 곱해진다. 직접 k-way(METIS_PartGraphKway)는 최거친 그래프에서 바로 $k$조각을 만들고 비코스닝 내내 k-way FM으로 다듬는다. 큰 $k$에서 더 빠르고 대개 cut도 낫기 때문에 요즘 기본값은 이쪽이다.

다중 제약(multi-constraint) 분할은 정점에 가중치 벡터를 달아, 예컨대 “셀 수도 균형, 벽면 셀 수도 균형, 화학종 소스항 셀 수도 균형”을 동시에 맞춘다. 다물리 연성이나 적응 격자 세분화 후처럼 계산량 프로파일이 불균질한 문제에서 필수다.

메시는 그래프가 아니므로 변환이 필요하다. METIS_PartMeshDual은 셀을 정점, 면 공유를 간선으로 하는 쌍대 그래프를 만들고(FVM에 자연스럽다), METIS_PartMeshNodal은 절점 그래프를 만든다(유한요소법 쪽에서 쓴다).

그리고 METIS의 또 다른 주력은 분할이 아니라 순서화다. METIS_NodeND는 다단계 중첩 분할(nested dissection) 로 희소행렬의 채움 감소(fill-reducing) 순서를 만든다. 분리자(separator)를 찾아 행렬을 두 블록으로 가르고 분리자를 맨 뒤로 미는 것을 재귀적으로 반복하면, 촐레스키 분해·LU 분해의 채움이 극적으로 줄어든다. 3D 유한요소 행렬에서 AMD 같은 국소 휴리스틱보다 중첩 분할이 확실히 유리해서, 직접법 솔버(MUMPS, PARDISO, CHOLMOD 등)는 거의 다 METIS 순서화를 옵션으로 들고 있다. 사실 많은 사용자가 희소행렬 분해 때문에 METIS를 링크해 놓고도 자기가 METIS를 쓰는 줄 모른다.

5. 실무 접점과 대안

• OpenFOAM — decomposeParDict의 method에 scotch, metis, kahip, hierarchical, simple 등이 있다. 기본 배포판이 Scotch를 들고 다니는 것은 과거 METIS 라이선스가 상용에 걸림돌이었기 때문인데, 5.2.0에서 Apache 2.0으로 바뀌면서 그 이유는 사라졌다.
• 영역 분할법 — DDM의 조대 공간·부분영역 정의를 METIS 분할로 만든다. 슈바르츠 중첩은 분할 후 층을 넓혀 얻는다.
• MPI 기반 솔버 — 분할 결과가 그대로 랭크별 소유 셀 목록과 halo 교환 패턴이 된다. 병렬 컴퓨팅에서 부하 분산의 출발점.
• ParMETIS — METIS의 MPI 병렬판. 그래프 자체가 이미 분산돼 있어 직렬로 모을 수 없을 때, 그리고 AMR로 격자가 바뀐 뒤 적응형 재분할을 할 때 쓴다. 재분할은 목적함수가 다르다 — cut만 줄이면 되는 게 아니라 데이터를 옮기는 비용(migration cost) 까지 같이 재야 해서, ITR 파라미터로 둘의 상대 가중을 준다.
• 대안 — Scotch/PT-Scotch(INRIA), KaHIP(카를스루에, 품질 지향), Zoltan(Sandia, 하이퍼그래프·공간충전곡선 포함), 원조 Chaco. 스펙트럴 분할(피들러 벡터 기반)은 품질이 좋지만 고유값 계산 비용 때문에 대형 문제에서는 다단계에 밀렸다.³

실무 팁 하나. 분할 품질을 cut 숫자만 보고 판단하지 말 것. 랭크별 셀 수, 랭크별 경계면 수, 이웃 랭크 개수를 같이 봐야 한다. cut이 같아도 이웃이 4개인 분할과 30개인 분할은 실제 스케일링이 전혀 다르다.⁴

6. 관련 문서

• 영역 분할법
• 병렬 컴퓨팅 · MPI
• 희소행렬 · 촐레스키 분해 · LU 분해
• 메시 생성 · 격자
• 적응 격자 세분화
• 스펙트럴 군집화 · 피들러 벡터 · 그래프 컷
• 조합 최적화
• OpenFOAM · PETSc

7. Footnotes

1. 다단계 분할의 총 비용은 코스닝·초기분할·정련을 다 합쳐도 대략 $O(|V|+|E|)$ 수준이다. 백만 셀 격자를 수백 개로 쪼개는 데 몇 초면 끝나는 이유. 그 몇 초를 아끼겠다고 균등 인덱스 분할(simple)을 쓰면, 이후 며칠간 halo 통신으로 갚게 된다. ↩

2. 그래프에서는 간선이 정점 두 개를 잇지만 하이퍼그래프에서는 하나의 하이퍼에지가 임의 개수의 정점을 묶는다. “이 셀의 값이 필요한 모든 랭크”를 하이퍼에지 하나로 표현할 수 있어서 통신 볼륨을 정확히 센다. 정확한 대신 비싸다 — 세상은 공평하다. ↩

3. 스펙트럴 분할은 라플라시안의 두 번째로 작은 고유벡터(피들러 벡터) 부호로 자르는 우아한 방법이지만, 다단계 FM이 등장하자 “느린데 더 좋지도 않다”는 평가를 받으며 주류에서 밀려났다. 우아함은 논문에서만 통용되는 화폐다. ↩

4. METIS는 이웃 랭크 수(neighbor degree)를 직접 최소화하지 않는다. 지연시간(latency)이 대역폭보다 아픈 인터커넥트에서는 이게 실제 병목이 되기도 해서, 계층적 분할(노드 내부 먼저, 노드 간 나중)로 우회하는 게 정석이다. ↩