통신 회피 알고리즘

수치해석 소프트웨어 마지막 수정: 2026-08-15 04:23:18

1. 개요[편집]

통신 회피 알고리즘 Communication-avoiding algorithms
전제	연산은 싸고 데이터 이동이 비싸다
비용 모형	$T \approx \gamma F + \beta W + \alpha S$ (연산·전송량·메시지 수)
이론적 뿌리	Hong & Kung (1981) I/O 복잡도 · Irony–Toledo–Tiskin (2004)
행렬곱 하한	$W = \Omega\!\left(n^3/(P\sqrt{M})\right)$
대표 알고리즘	TSQR/CAQR · 2.5D 행렬곱 · CALU · s-스텝 크릴로프
대가	여분 메모리, 피벗 전략 변경, 기저 조건수 관리

FLOPS는 20년째 기하급수적으로 늘었고, 메모리 지연은 거의 그대로다. 그러니까 알고리즘의 비용 함수를 바꿔 써야 한다.

통신 회피 알고리즘(communication-avoiding algorithm)은 연산 횟수가 아니라 데이터 이동량을 비용 함수로 놓고, 그 이동량의 이론적 하한을 먼저 증명한 다음 하한을 실제로 달성하도록 알고리즘을 다시 설계하는 수치선형대수의 한 흐름이다. 전통적인 알고리즘 분석이 ” $\frac{2}{3}n^3$ flops”를 세었다면, 여기서는 “메모리 계층 사이를 오간 워드 수 $W$ “와 “메시지 수 $S$ “를 센다.

동기는 하드웨어 추세 하나다. 부동소수점 처리량은 수십 년간 연 50~60%씩 늘어난 반면, 메모리 대역폭은 그 절반도 못 따라갔고 지연은 사실상 정체했다. 그 결과 오늘날 한 번의 배정밀도 곱셈 비용은 DRAM에서 한 워드를 끌어오는 비용의 100분의 1 수준이고, 노드 간이면 격차가 더 벌어진다. 알고리즘 A가 B보다 flops가 10% 많아도 통신이 절반이면 A가 이긴다 — 이 부등호가 이 분야의 전부다.¹

2. 비용 모형과 하한[편집]

한 프로세서(또는 한 메모리 계층)의 실행 시간을 이렇게 근사한다.

T \;\approx\; \gamma F \;+\; \beta W \;+\; \alpha S

$F$ 는 연산 수, $W$ 는 옮긴 워드 수(대역폭 항), $S$ 는 메시지 수(지연 항)다. $\alpha \gg \beta \gg \gamma$ 가 현실이고, MPI의 지연-대역폭 모형 $T=\alpha+\beta n$ 을 알고리즘 전체로 확장한 형태로 보면 된다.

핵심 정리는 행렬곱의 통신 하한이다. 홍(Hong)과 쿵(Kung)이 1981년 red-blue pebble game으로 순차 기계에서 빠른 메모리 크기가 $M$ 일 때 $n\times n$ 행렬곱이 $\Omega(n^3/\sqrt{M})$ 워드를 옮겨야 함을 보였고, 아이러니·톨레도·티스킨(2004)이 이를 분산 메모리로 옮겨 프로세서 $P$ 개, 프로세서당 메모리 $M$ 일 때

W \;=\; \Omega\!\left(\frac{n^3}{P\sqrt{M}}\right)

를 증명했다. 뒤이어 밸러드·뎀멜·홀츠·슈바르츠(2011)가 루미스-휘트니 부등식을 써서 이 하한이 행렬곱뿐 아니라 삼중 루프 구조를 갖는 거의 모든 밀집 선형대수(LU, 촐레스키, QR, 고유값 축약)에 적용됨을 보였다. 즉 하한은 특정 알고리즘의 성질이 아니라 문제의 성질이다.

여기서 즉각 따라 나오는 결론이 하나 있다. 하한이 $\sqrt{M}$ 에 반비례하므로, 메모리를 더 쓰면 통신을 줄일 수 있다. 이 한 줄이 다음 절 전체를 만든다.

3. 2.5D 알고리즘 — 메모리를 통신으로 바꾸는 환율[편집]

고전적인 병렬 행렬곱(SUMMA, 캐넌 알고리즘)은 $\sqrt{P}\times\sqrt{P}$ 격자에 행렬을 한 벌씩만 깔아 놓는다. 프로세서당 메모리는 $M = 3n^2/P$ 이고, 하한식에 넣으면 $W = \Omega(n^2/\sqrt{P})$ — 2D 알고리즘은 이 하한을 달성한다. 최소 메모리에서는 더 줄일 수 없다는 뜻이다.

반대쪽 극단이 3D 알고리즘이다. $P^{1/3}\times P^{1/3}\times P^{1/3}$ 큐브에 행렬을 $P^{1/3}$ 벌 복제해 깔면 통신이 $W = \Theta(n^2/P^{2/3})$ 까지 떨어진다. 대가는 메모리 $P^{1/3}$ 배.

2.5D 알고리즘(솔로모닉·뎀멜, 2011)은 그 사이를 연속적으로 잇는다. 복제 인자 $c$ ( $1 \le c \le P^{1/3}$ )를 두고 프로세서를 $\sqrt{P/c}\times\sqrt{P/c}\times c$ 로 배치하면

W \;=\; \Theta\!\left(\frac{n^2}{\sqrt{cP}}\right)

가 되어, 여분 메모리를 $c$ 배 쓰면 통신량이 $\sqrt{c}$ 배 줄어든다. 메모리 여유를 통신 절감으로 바꾸는 환율이 명시적으로 주어진 셈이고, 노드 메모리가 남아도는 요즘 기계에서 이건 공짜 점심에 가깝다. 같은 아이디어를 LU 분해에 적용한 것이 2.5D LU다.

4. TSQR — 집합통신 한 번으로 끝내는 QR[편집]

키 크고 얇은( $m \gg n$ ) 행렬의 QR 분해는 통신 회피의 교과서 사례다. 이 형상은 최소자승법, 블록 크릴로프, 무작위화 저계수 근사에서 계속 나온다.

고전적인 그람-슈미트 계열은 열을 하나씩 처리한다. 행렬의 행을 $P$ 개 랭크가 나눠 가진 상황에서 열 하나를 직교화하려면 내적이 필요하고, 내적 하나가 전역 축약 하나다. 즉 수정 그람-슈미트(MGS)는 $n$ 개 열에 대해 $O(n)$ 번의 집합통신을 요구한다. 열이 500개면 축약이 500번이고, 랭크가 수만이면 여기서 끝난다.

TSQR(Tall-Skinny QR, 뎀멜·그리고리·회멘·랑구)의 발상은 단순하다.

각 랭크가 자기 행 블록만 하우스홀더 변환 QR로 분해해 국소 $R$ 을 얻는다. 통신 0.
이웃한 두 $R$ 을 세로로 쌓아( $2n\times n$ ) 다시 QR한다. 이걸 이진 트리로 올린다.
트리 꼭대기에서 최종 $R$ 이 나온다.

축약 연산자가 “두 $R$ 을 합쳐 하나의 $R$ 로”인 축약 한 번이며, 라운드 수는 $\log_2 P$ 다. 열 수 $n$ 과 무관하게 집합통신이 하나로 줄었다는 것이 요점이고, 이 관점에서 TSQR은 지연 항의 하한을 달성한다. $Q$ 가 필요하면 트리의 각 노드에 남긴 하우스홀더 인자를 역순으로 적용해 암시적으로 만든다(그래서 $Q$ 를 명시적으로 쓰지 않는 용도가 훨씬 싸다).

수치적으로도 손해가 없다. **전 과정이 하우스홀더 반사뿐이므로 직교성 손실이 $O(u)$ **로, 밀집 하우스홀더 QR과 같은 등급이다. 통신을 한 번으로 줄인 다른 후보인 CholeskyQR( $A^{\top}A$ 를 만들어 축약 한 번)은 조건수가 제곱되어 $O(u\kappa^2)$ 를 감수해야 하는 것과 대비된다.² 일반적인 $m \times n$ 행렬로 확장해 패널마다 TSQR을 돌리는 것이 CAQR이고, 여기에 대응하는 LU 판본이 CALU다. CALU는 부분 피벗 대신 토너먼트 피벗(블록별로 후보 행을 뽑아 토너먼트로 올린다)을 쓰는데, 이론적 성장 인자 상한은 부분 피벗보다 나쁘지만 실측 안정성은 사실상 구별되지 않는다는 것이 이 방법이 받아들여진 근거다. 통신을 줄이려고 수치적 성질을 협상 테이블에 올린 첫 사례라는 점에서 상징적이다.

5. s-스텝 크릴로프 — 반복법의 동기화 없애기[편집]

크리로프 부분공간법은 반복마다 행렬-벡터 곱 한 번(이웃 통신)과 내적 몇 번(전역 축약)을 한다. 대규모에서 병목은 압도적으로 후자다. GMRES의 직교화는 스텝 $j$ 에서 $j$ 번의 축약을 요구하고, PETSc 같은 라이브러리가 파이프라인 변형을 따로 제공하는 것도 이 때문이다.

s-스텝 크릴로프(= 통신 회피 크릴로프)는 반복 $s$ 개를 묶는다.

행렬 거듭제곱 커널(matrix powers kernel): $[x, Ax, A^2x, \dots, A^sx]$ 를 통신 한 라운드로 만든다. 비결은 유령셀을 $s$ 겹 깊이로 한꺼번에 받아 오는 것 — 중복 계산을 감수하는 대신 메시지 수를 $s$ 배 줄인다. 희소 그래프의 지름이 작으면 $s$ 겹 halo가 폭발하므로, 이 커널의 실용 범위는 희소행렬의 구조가 결정한다.
한꺼번에 직교화: 그렇게 만든 $s+1$ 개 벡터를 TSQR/블록 그람-슈미트로 한 번에 직교화한다.

결과적으로 축약 횟수가 $1/s$ 로 줄어든다. 그런데 여기서 이 분야에서 제일 유명한 함정이 나온다.

단항식 기저 $A^jx$ 는 못 쓴다. 거듭제곱법이 그렇듯 $A^jx$ 는 지배 고유벡터 방향으로 급속히 수렴하므로, 벡터들이 서로 평행해지며 기저 행렬의 조건수가 $s$ 에 대해 지수적으로 나빠진다. 배정밀도에서 실용 한계는 대개 $s \approx 5\text{--}10$ 이고, 그 위에서는 직교화가 무의미해지며 수렴이 원래 알고리즘보다 오히려 느려진다.

처방은 기저를 바꾸는 것이다.

뉴턴 기저: $p_{j+1}(A)x = (A - \theta_j I)\,p_j(A)x$ 처럼 스펙트럼 근사값(리츠값 등)을 시프트로 넣는다. 시프트 순서를 레야(Leja) 순서로 잡는 것이 관건으로, 순서만 잘못 잡아도 조건수가 다시 폭발한다.
체비쇼프 기저: 스펙트럼을 감싸는 타원(또는 실구간)으로 스케일링한 체비쇼프 다항식 점화식을 쓴다. 구간 위에서 최대치가 균등하게 눌리므로 기저가 훨씬 고르게 퍼진다.

둘 다 스펙트럼 정보를 미리 조금 알아야 한다는 점에서 완전 공짜는 아니다. 그래서 실무에서는 처음 몇 반복을 표준 방식으로 돌려 리츠값을 모은 뒤 s-스텝으로 전환하는 하이브리드가 흔하다.

한편 지연을 회피하는 대신 숨기는 노선도 있다. 파이프라인 크릴로프(p-CG, p-GMRES)는 논블로킹 MPI_Iallreduce를 걸어 두고 그동안 행렬-벡터 곱을 돌린다. 수학은 그대로 두고 통신만 겹치는 쪽이라 안정성 리스크가 작은 대신, 절감폭도 s-스텝만큼 크지는 않다.

6. 전처리기라는 미해결 지대[편집]

s-스텝 이론이 깔끔하게 성립하는 것은 전처리 없는 반복법에서다. 그런데 실전에서 크리로프 부분공간법은 전처리기 없이 쓰이지 않고, 강한 전처리기일수록 통신 집약적이다.

영역 분할법 계열은 부분영역 안에서만 놀아서 s-스텝과 궁합이 나쁘지 않다. 다만 조대 공간(coarse space) 해가 전역 통신이라 그 부분이 남는다.
다중격자법은 격자 계층을 오르내리며 통신하는데, 최상위 조대 격자에서는 프로세서당 미지수가 몇 개뿐이라 전형적인 지연 지배 구간이 된다. 조대 격자를 소수 랭크에 모으는 agglomeration이 사실상 필수.
불완전 LU 계열은 삼각 풀이가 본질적으로 순차적이라 애초에 확장이 안 된다.

“통신 회피 반복법”이 논문 수에 비해 프로덕션 코드에서 덜 보이는 이유가 대체로 여기 있다. 커널 하나를 최적화해도 전처리기가 매 반복 전역 동기화를 하면 절감이 통째로 먹힌다.

7. 어디까지 실전인가[편집]

정직하게 정리하면 이렇다.

밀집 선형대수는 확정 승리. TSQR·CAQR·2.5D 행렬곱·CALU는 라이브러리(SLATE, Elemental 등)와 벤더 구현에 들어가 있고, 특히 TSQR과 CholeskyQR2는 GPU 환경에서 사실상 기본값이다. 무작위화 SVD 같은 최신 기법이 키 큰 얇은 QR을 안에서 부르므로 수혜 범위가 넓다.
s-스텝 크릴로프는 조건부. 기저 조건수 관리와 전처리기 문제 때문에 아직 범용 기본값은 아니다. 다만 “축약 횟수를 세라”는 사고방식 자체는 완전히 정착해서, 요즘 솔버 논문은 flops 대신 동기화 횟수를 표에 적는다.
아이디어의 파급. 역행렬 대신 QR을 반복하는 QDWH 계열 스펙트럼 분할, 분자동역학의 통신 최소화 분해, 딥러닝의 통신 절감 분산 학습까지 같은 발상이 흘러들었다. 결국 “무엇을 세느냐”를 바꾸는 일이고, 그건 알고리즘 설계에서 제일 값싼 혁신이다.³

8. 관련 문서[편집]

이 부등호를 처음 배우면 “그럼 지금까지 flops 세던 건 뭐였나” 싶은데, 1970~80년대에는 정말로 곱셈이 제일 비쌌다. 알고리즘 교과서의 비용 함수가 하드웨어의 화석이라는 사실을 이 분야만큼 노골적으로 보여 주는 예도 드물다. ↩
그래서 선택지는 늘 셋이다. 안전하고 통신 한 번인 TSQR, 빠르지만 $\kappa^2$ 인 CholeskyQR, 그리고 두 번 돌려 $O(u)$ 를 되찾는 CholeskyQR2. GPU에서 CholeskyQR2가 TSQR을 이기는 경우가 흔한데, 행렬-행렬 곱 두 번이 트리 구조 순회보다 하드웨어에 잘 맞기 때문이다. 통신 회피가 항상 통신 회피 알고리즘의 승리로 끝나지는 않는다. ↩
물론 논문 제목에 “communication-avoiding”을 붙이는 것이 유행이던 시기가 있어서, 실제로는 블록 크기만 키운 것을 그렇게 부르는 사례도 있었다. 구별법은 간단하다 — 통신 하한을 명시하고 그것을 달성했다고 주장하는지 보면 된다. ↩