부하 분산

소프트웨어 시뮬레이션 마지막 수정: 2026-08-14 04:47:26

1. 개요[편집]

부하 분산 Load Balancing
목표	모든 프로세스가 동시에 끝나게 하기
효율 상한	$E \le \bar{L}/L_{\max}$ (평균 부하 / 최대 부하)
정적 기법	그래프 분할 · 공간 채움 곡선 · LPT
동적 기법	작업 훔치기 · 확산 재분배 · 측정 기반 재분할
고전 결과	작업 훔치기 $T_P \le T_1/P + O(T_\infty)$ (1994)
천적	데이터 이주 비용 · 부하의 시간 변동

코어 512개 중 511개가 놀고 한 개가 죽어라 일하는 순간, 당신이 산 것은 슈퍼컴퓨터가 아니라 아주 비싼 노트북이다.

부하 분산(load balancing)은 병렬 계산에서 각 프로세스·스레드가 맡는 일의 양을 고르게 맞춰, 전체 실행 시간을 결정하는 가장 느린 조각을 최소화하는 문제이자 그 기법의 총칭이다. 병렬 성능을 갉아먹는 요인은 크게 통신·동기화·불균형 셋인데, 앞의 둘이 코드 최적화의 문제라면 불균형은 작업을 나누는 결정 자체의 문제라 성격이 다르다.

이 문서는 부하를 어떻게 나누고 다시 나눌 것인가에 집중한다. 병렬 모델 일반(공유/분산 메모리, 표면 대 부피 비, 암달의 법칙, 강·약 스케일링)은 병렬 컴퓨팅에, 절단 최소화라는 조합 최적화 문제 자체는 그래프 분할과 METIS에, halo 교환 구조는 영역 분할법에 있다.

2. 불균형의 값 — 최대 조각이 전부다[편집]

프로세스 $i$ 의 계산량을 $L_i$ , 프로세스 수를 $P$ 라 하자. 동기화 지점이 있는 한 한 스텝의 시간은 최댓값이 결정한다.

T_{\text{par}} \ge \max_i L_i, \qquad \lambda = \frac{L_{\max}}{\bar{L}} = \frac{P\,\max_i L_i}{\sum_i L_i}

$\lambda$ 를 불균형 계수라 부른다. 병렬 효율의 상한은 곧바로

E = \frac{T_1}{P\,T_{\text{par}}} \le \frac{1}{\lambda}

가 된다. $\lambda = 1.25$ 면 코어를 아무리 잘 써도 효율 80%가 천장이라는 뜻이고, 이 손실은 코어를 늘려도 사라지지 않는다. 바로 이 점에서 불균형은 병렬 컴퓨팅의 암달의 법칙과 성격이 같다 — $1 - 1/\lambda$ 가 사실상 유효 순차 비율로 행세한다. 다른 점은 순차 부분이 알고리즘의 성질인 반면 불균형은 고칠 수 있는 결정이라는 것이고, 그래서 대형 코드에서 스케일링을 되살릴 때 제일 먼저 재는 숫자가 $\lambda$ 다.

한 가지 함정. $\lambda$ 는 계산량으로만 재면 안 된다. 통신을 기다리는 시간, 파일 I/O, 희소행렬 전처리기의 반복 횟수 차이 같은 것들이 전부 $L_i$ 에 들어가야 한다. 셀 수를 완벽하게 균등하게 나눠 놓고도 랭크마다 반복 횟수가 달라 불균형이 나는 경우가 실제로 흔하다.

3. 정적 분산[편집]

부하 분포를 실행 전에 알 수 있고 시간에 따라 변하지 않으면, 한 번 잘 나눠 놓고 끝내는 것이 최선이다.

그래프 분할 — 셀을 정점(가중치 = 계산량), 데이터 의존을 간선으로 놓고 균형 제약 아래 절단을 최소화한다. 부하 균형과 통신 최소화를 한 번에 다루는 유일한 정공법이라 CFD·유한요소법 병렬화의 기본값이다. 계산량 프로파일이 여러 종류면(벽면 셀, 화학종 소스항 셀 등) 다중 제약 분할을 쓴다.
공간 채움 곡선 — 셀을 힐베르트·모턴 순으로 정렬하고 가중치 누적합을 $P$ 등분한다. 절단 품질은 그래프 분할에 밀리지만 비용이 정렬 한 번이고 증분적이라, 뒤에 나올 동적 재분할에서 진가를 발휘한다.
블록·순환 배분 — 인덱스를 연속 덩어리로 자르거나(block) 라운드로빈으로 흩는다(cyclic). 조밀 선형대수처럼 삼각 구조 때문에 부하가 인덱스에 따라 기우는 경우 순환 배분이 균형을 자동으로 잡아 주고, 대신 국소성을 잃는다. ScaLAPACK류의 2차원 블록-순환 배분이 이 둘을 절충한 형태다.
LPT 그리디 — 독립 작업 $n$ 개를 기계 $P$ 대에 나누는 순수 스케줄링 문제라면 긴 것부터 가장 한가한 기계에 얹는 그리디가 있다. 최적 대비 $4/3 - 1/(3P)$ 이내라는 그레이엄(1969)의 고전적 보증이 있고, 구현이 열 줄이다. 빈 패킹과 사촌 관계.

정적 분산의 전제는 부하 예측이 맞는다는 것이다. 셀 수에 비례한다고 가정했는데 실제로는 화학 반응이 있는 셀이 열 배 비싸다면, 아무리 좋은 분할기를 써도 결과는 기울어진다. 그래서 실무에서는 한 번 돌려 보고 랭크별 시간을 측정해 정점 가중치를 다시 매기는 측정 기반 정적 분산을 자주 쓴다.

4. 동적 분산 — 작업 훔치기[편집]

부하가 실행 중에 바뀌거나 애초에 예측 불가능하면 실행 시간에 대응해야 한다. 공유 메모리 환경의 표준 답이 작업 훔치기(work stealing)다.

각 워커 스레드가 자기 작업 덱(deque)을 하나씩 갖는다.

자기 작업은 덱의 아래쪽에서 넣고 뺀다. LIFO라 깊이 우선으로 진행되고, 방금 만든 데이터를 바로 쓰므로 캐시가 뜨겁다.
덱이 비면 무작위로 다른 워커를 골라 그 덱의 위쪽에서 훔친다. 위쪽은 가장 오래된 작업, 즉 대개 가장 큰 부분트리라 훔치는 횟수가 줄어든다.

이 두 줄이 설계의 전부인데, 놀랍게도 이론적 보증이 붙는다. 블루모프와 라이저슨(1994)은 완전 엄격한 다중스레드 계산에 대해 기대 실행 시간이

T_P \;\le\; \frac{T_1}{P} + O(T_\infty)

임을 보였다. $T_1$ 은 총 작업량, $T_\infty$ 는 임계 경로 길이다. 즉 병렬성 $T_1/T_\infty$ 가 $P$ 보다 충분히 크면 선형 가속이 자동으로 나온다. 스케줄러를 튜닝할 필요 없이 “작업을 충분히 잘게 쪼개기만 하라”로 문제가 환원된다는 것이 이 결과의 실무적 의미다. Cilk에서 출발해 Intel TBB, OpenMP 태스크, Java ForkJoinPool, Go 런타임까지 오늘날 태스크 병렬 런타임은 거의 다 이 구조다.

한계는 명확하다. 덱을 공유해야 하므로 원칙적으로 노드 안(공유 메모리) 기법이다. 분산 메모리에서 훔치려면 원격 메모리 접근이나 메시지가 필요하고, 무엇보다 훔친 작업이 참조하는 데이터를 같이 옮겨야 한다. 데이터가 작고 작업이 무거운 문제(광선 추적, 몬테카를로 표본, 파라미터 스윕)에서는 분산 작업 훔치기도 잘 돌지만, 격자 셀처럼 데이터가 크고 이웃과 붙어 있어야 하는 문제에서는 답이 아니다.

5. 확산 기반 재분배[편집]

분산 메모리에서 부하가 조금씩 기우는 상황의 고전적 처방이 확산(diffusion)이다. 사이벤코(1989)의 정식화는 아름다울 만큼 단순하다. 프로세스 연결 그래프의 라플라시안을 $L = D - A$ , 부하 벡터를 $w$ 라 할 때

w^{(k+1)} = w^{(k)} - \alpha L\,w^{(k)}

를 반복한다. 이웃끼리 부하 차이에 비례하는 양을 주고받는 것이 전부이고, 실제로 이것은 라플라스 방정식의 명시적 시간 전진과 같은 식이다. 부하가 말 그대로 열처럼 퍼진다.

수렴 조건과 속도도 그대로 따라온다. $0 < \alpha < 2/\lambda_{\max}(L)$ 이면 수렴하고, 수렴률은 $\lambda_2(L)$ — 즉 피들러 벡터에 대응하는 대수적 연결도 — 가 지배한다. 프로세스 토폴로지가 성기고 길쭉하면(예: 1차원 링) $\lambda_2$ 가 작아 부하가 반대편까지 흘러가는 데 반복이 아주 많이 필요하다. 하이퍼큐브에서는 차원별로 한 번씩 짝지어 정확히 반씩 나누는 차원 교환(dimension exchange)이 $d$ 번에 완전 균형을 달성해, 반복 확산보다 훨씬 낫다.

반복이 싫으면 한 번에 풀어도 된다. 후와 블레이크(1999)의 방법은 $L\boldsymbol{\lambda} = w - \bar{w}$ 를 크리로프 부분공간법으로 한 번 풀고, 간선 $(i,j)$ 로 보낼 부하를 $\lambda_i - \lambda_j$ 로 정한다. 이렇게 얻은 흐름이 균형을 맞추는 흐름 중 $\ell_2$ 노름이 최소임을 보일 수 있다 — 즉 데이터를 최소한만 옮기는 재분배다. 반복 확산이 국소 정보만으로 같은 곳에 수렴하는 것과 대비하면, 전역 해를 한 번에 사서 이주량을 줄이는 거래다.

확산 계열의 공통 미덕은 이전 분할을 최대한 보존한다는 것이다. 처음부터 다시 분할하면 절단은 좋아질지 몰라도 거의 모든 셀이 랭크를 바꾼다. 확산은 경계에서만 부하가 오가므로 이주량이 근본적으로 작다.

6. 재분할할 것인가 참을 것인가[편집]

동적 부하 분산의 진짜 결정은 “어떻게”가 아니라 “할 것인가” 다. 재분할은 공짜가 아니다.

\underbrace{(\lambda - 1)\,\bar{L}\cdot N_{\text{steps}}}_{\text{참았을 때 누적 손해}} \quad \text{vs} \quad \underbrace{T_{\text{partition}} + T_{\text{migration}}}_{\text{재분할 비용}}

왼쪽은 앞으로 남은 스텝 수 $N_{\text{steps}}$ 에 비례해 커지고, 오른쪽은 한 번만 낸다. 그래서 판단은 부하가 얼마나 빨리 기우는가와 얼마나 더 돌 것인가에 달렸다. 짧은 해석에서는 기울어진 채로 끝내는 것이 이기고, 수만 스텝짜리에서는 주기적 재분할이 압도적으로 이긴다.

$T_{\text{migration}}$ 이 종종 $T_{\text{partition}}$ 보다 크다는 점도 중요하다. 백만 셀의 상태 변수를 랭크 사이로 실어 나르는 것은 분할기를 한 번 돌리는 것보다 비싸다. 그래서 재분할기의 목적함수는 절단 하나가 아니라 절단과 이주량의 가중합이다. ParMETIS가 두 항의 상대 가중을 ITR 파라미터로 노출하는 이유이고, 확산 기반 재분할과 공간 채움 곡선 기반 재분할이 이 무대에서 우세한 이유이기도 하다 — 둘 다 이전 분할과 비슷한 답을 내놓도록 설계돼 있다.

실무에서 흔한 절충은 이렇다.

주기적 재분할 — $N$ 스텝마다 무조건 한 번. 단순하고 예측 가능하다.
문턱 기반 — 측정한 $\lambda$ 가 임계값(예: 1.05)을 넘으면 발동. 부하가 안정적인 구간에서는 아무것도 안 한다.
과분해(overdecomposition) — 애초에 $P$ 보다 훨씬 많은 조각으로 나눠 놓고, 재분할 대신 조각을 재배치만 한다. 조각 단위가 작아 이주가 값싸고, 런타임이 부하를 측정해 옮길 수 있다. Charm++가 이 철학을 극단까지 밀어붙인 사례로, “부하의 지속성” — 즉 방금 무거웠던 객체는 다음 스텝에도 무겁다 — 이라는 경험칙 위에서 측정 기반 재배치를 돌린다.¹

7. 시뮬레이션 현장[편집]

입자 코드. 분자동역학이나 SPH에서 입자가 한쪽으로 뭉치면 공간 균등 분할은 즉시 무너진다. 처방은 두 갈래다. 영역 경계를 부하에 맞춰 옮기거나(재귀 좌표 이분의 절단면을 이동시키는 방식), 아예 공간이 아니라 상호작용 목록을 나누는 힘 분해(force decomposition)로 가거나. 전자가 통신에 유리하고 후자가 균형에 유리하다.
적응 격자 세분화. 충격파나 계면을 따라 세분화 영역이 매 스텝 이동한다. 부하 분포가 시간에 따라 계속 바뀌므로 정적 분할은 애초에 성립하지 않는다. SFC 기반 재분할이 사실상 표준이 된 무대이며, 세분화 판정 직후에 키를 다시 정렬하고 누적합을 $P$ 등분하는 것이 한 사이클이다.
다물리 연성. 유동-구조 연성이나 반응 유동에서는 물리마다 부하 프로파일이 다르다. 같은 격자를 물리별로 다르게 분할하면 각각은 균형이 잡히지만 연성 지점의 통신이 폭발하고, 하나로 통일하면 어느 한쪽이 기운다. 다중 제약 분할이 이 딜레마의 표준 타협안이다.
암시적 솔버. 랭크마다 크리로프 부분공간법 반복 횟수가 다른 것이 아니라 — 전역 반복이므로 횟수는 같다 — 전처리기 비용이 다르다. 불완전 분해의 채움이 랭크마다 다르면 셀 수를 완벽히 맞춰도 시간이 기운다. 이런 경우 정점 가중치를 셀 수가 아니라 측정한 시간으로 다시 매기는 것 외에 왕도가 없다.
GPU와 이종 시스템. CPU와 GPU가 섞이면 부하를 셀 수가 아니라 처리 속도 비율로 나눠야 한다. 그 비율이 문제·격자·정밀도에 따라 바뀌므로 자동 조율(auto-tuning) 루프가 붙는 것이 보통이다.² GPU 컴퓨팅 참고.

마지막으로 진단 요령 하나. 불균형인지 통신 병목인지부터 구분해야 한다. 랭크별 계산 시간과 대기 시간을 따로 재 보면 금방 갈린다 — 계산 시간의 분산이 크면 부하 문제이고, 계산 시간은 고른데 다들 대기가 길면 그건 부하 분산이 아니라 통신 패턴이나 MPI 동기화 구조의 문제다. 이 구분을 안 하고 재분할기부터 갈아 끼우면, 며칠을 쓰고도 $\lambda$ 가 원래 1.02였다는 사실만 알게 된다.³

8. 관련 문서[편집]

“지속성 원리”는 증명된 정리가 아니라 관찰이다. 반복 구조를 가진 과학 계산에서는 대체로 참이고, 그래서 런타임이 지난 스텝의 측정값으로 다음 스텝을 예측해도 잘 먹힌다. 반대로 부하가 매 스텝 무작위로 튀는 문제라면 측정 기반 재배치는 지난 전쟁을 다시 치르는 꼴이 된다. ↩
CPU:GPU 부하 비율을 손으로 박아 놓은 코드는 하드웨어가 한 세대 바뀌는 순간 조용히 나빠진다. 그리고 아무도 눈치채지 못한다 — 벤치마크는 여전히 “GPU 버전이 빠르다”고 말해 주니까. 이런 상수는 파일 맨 위에 크게 써 두거나 아예 측정으로 대체하는 편이 낫다. ↩
병렬 성능 문제의 절반은 “느린 이유를 잘못 짚어서” 생긴다. 프로파일러가 랭크별 타임라인을 뽑아 주는 시대에 추측으로 튜닝하는 것은 검증 및 확인 정신에 정면으로 반한다. 일단 재고 나서 고치자. ↩