병렬 컴퓨팅

1. 개요

병렬 컴퓨팅 Parallel computing
분야	전산과학 × 소프트웨어
주요 모델	MPI(분산 메모리), OpenMP(공유 메모리), CUDA·HIP(GPU)
핵심 기법	도메인 분할, 그래프 분할
이론적 한계	암달의 법칙(Amdahl's Law)

한 사람이 아홉 달 걸리는 일은, 아홉 사람이 한 달 만에 끝낼 수 없다. 그런데 우리는 매일 그걸 시도한다.

병렬 컴퓨팅(parallel computing)은 하나의 큰 계산 문제를 여러 개의 부분 작업으로 나누어 다수의 연산 장치(코어·노드·GPU)에서 동시에 처리해 전체 계산 시간을 줄이는 기법이다. 오늘날 대규모 시뮬레이션 — 항공기 전기체 전산유체역학, 자동차 충돌 명시적 동해석, 수백만 원자 분자동역학 — 은 단일 코어로는 수십 년이 걸리기에, 병렬화 없이는 아예 성립하지 않는다. 2000년대 중반 트랜지스터를 줄여도 전력 밀도가 일정하게 유지되던 데나드 스케일링(Dennard 1974)이 누설 전류 때문에 무너지면서 클럭은 3~4 GHz 언저리에 묶였고, 무어의 법칙이 계속 공급하는 트랜지스터는 코어 수로 쓰이기 시작했다. 그 이후로 “빠른 코드”란 사실상 “잘 병렬화된 코드”와 동의어가 됐다.¹

병렬화의 핵심 난제는 계산을 나누는 것 자체가 아니라, 나뉜 조각들이 서로 데이터를 주고받는 통신 비용이다. 계산은 코어를 늘릴수록 빨라지지만 통신은 오히려 늘어난다. 이 줄다리기가 병렬 컴퓨팅의 모든 것을 지배한다.

2. 두 개의 메모리 모델: MPI와 OpenMP

병렬 프로그래밍은 메모리를 어떻게 공유하느냐에 따라 크게 두 진영으로 나뉜다.

공유 메모리(shared memory) 모델에서는 여러 스레드가 하나의 메모리 공간을 함께 본다. 대표 표준이 OpenMP로, 기존 C/C++/Fortran 코드의 반복문 위에 #pragma omp parallel for 한 줄만 얹으면 스레드로 쪼개진다. 진입 장벽이 낮은 대신, 한 노드 안의 코어 수(요즘 서버 기준 수십~수백 개)까지만 확장 가능하고, 소켓이 둘 이상이면 메모리 접근 시간이 위치마다 다른 NUMA 효과까지 신경 써야 하며, 데이터 경쟁(race condition)이라는 지뢰가 깔려 있다.

분산 메모리(distributed memory) 모델에서는 각 프로세스가 자기만의 독립된 메모리를 갖고, 필요한 데이터는 명시적으로 메시지를 보내 주고받는다. 표준은 MPI(Message Passing Interface). MPI_Send/MPI_Recv로 손수 통신을 짜야 해서 고통스럽지만, 수천~수백만 코어의 슈퍼컴퓨터로 확장하는 사실상의 표준이다(PGAS 언어나 Charm++ 같은 대안도 있지만 점유율은 비교가 안 된다).² 대규모 HPC 코드(LAMMPS, OpenFOAM, GROMACS, PETSc)는 거의 다 MPI 기반이며, 노드 내부는 OpenMP, 노드 간은 MPI로 섞는 하이브리드 MPI+OpenMP가 오랫동안 HPC의 정석이었다. 지금은 노드 안의 주력이 GPU로 넘어가 MPI+CUDA/HIP 조합이 상위 슈퍼컴퓨터의 기본형이 됐다(GPU 컴퓨팅 참고).

3. 도메인 분할

시뮬레이션을 어떻게 코어에 나눠줄 것인가. CFD·유한요소법·MD처럼 공간 위의 문제라면 답은 대개 도메인 분할(domain decomposition)이다. (여기서 말하는 건 일감을 나누는 자료 분할이다. 같은 이름으로 부분영역 문제를 엮어 선형계를 푸는 수치 알고리즘 계열도 있는데, 그쪽은 영역 분할법 문서가 다룬다.) 계산 격자나 원자 집합을 공간적으로 여러 조각(subdomain)으로 쪼개, 각 조각을 한 프로세스가 맡는다.

각 조각은 자기 내부를 독립적으로 계산하지만, 경계에서는 이웃 조각의 값이 필요하다. 그래서 조각 테두리에 이웃의 데이터를 복사해두는 유령 셀(ghost cell / halo)을 두고, 매 시간 스텝마다 이 halo만 교환한다. 여기서 병렬 효율의 핵심 지표가 나온다 — 표면 대 부피 비(surface-to-volume ratio). 조각이 클수록(부피↑) 계산량 대비 통신량(표면↑)이 작아 효율적이다. 숫자로 보면 분명하다. 셀 1억 개짜리 격자를 정육면체 조각으로 나누고 조각마다 한 겹짜리 halo를 둔다면, 한 변이 $n$ 셀인 조각의 halo/내부 비는 $6n^2/n^3 = 6/n$ 이다.

코어 수	코어당 셀	한 변 $n$	halo/내부
1,000	10만	46.4	0.13
10,000	1만	21.5	0.28
100,000	1,000	10.0	0.60

코어를 100배 늘리는 동안 통신할 셀의 상대 비중은 4.6배($100^{1/3}$) 뛴다. 2차 정확도 도식처럼 halo가 두 겹이면 이 비가 대략 두 배가 된다. 그래서 무작정 코어를 늘려 조각을 잘게 쪼개면, 어느 순간 통신이 계산을 압도해 오히려 느려진다.³

좋은 분할은 (1) 각 조각의 계산량을 균등하게(부하 균형, load balancing) 나누고 (2) 조각 간 경계 면적을 최소화해야 한다. 이 조합 최적화 문제(NP-난해)를 다단계 휴리스틱으로 푸는 것이 METIS(Karypis & Kumar 1998)·ParMETIS·Scotch·Zoltan 같은 그래프 분할 라이브러리의 일이다. 입자가 한쪽으로 몰리는 분자동역학이나 적응 격자 세분화 문제에서는 계산 중에 부하가 계속 바뀌므로, 실행 도중 조각을 다시 나누는 동적 부하 균형(dynamic load balancing)이 필요하다(부하 분산 참고).

4. 암달의 법칙: 병렬화의 천장

아무리 코어를 들이부어도 프로그램에는 순차적으로만 실행되는 부분(입출력, 초기화, 축약 연산 등)이 남는다. 암달의 법칙(Amdahl’s Law)은 이 순차 부분이 전체 가속의 상한을 못박는다는 냉정한 진실이다. 병렬화 가능 비율을 $p$, 코어 수를 $N$이라 하면 최대 속도 향상은

$$S(N) = \frac{1}{(1-p) + \dfrac{p}{N}}$$

이다(Amdahl 1967은 식 없이 말로 논증했고, 이 식은 후대의 정리다). 코어를 무한히 늘려도($N \to \infty$) 속도 향상은 $1/(1-p)$에서 멈춘다. 예컨대 코드의 95%를 병렬화해도($p=0.95$) 이론적 최대 가속은 고작 20배다. 나머지 5%가 발목을 잡는다.

$p$	$N=8$	$N=64$	$N=128$	$N=1024$	상한
0.90	4.7	8.8	9.3	9.9	10
0.95	5.9	15.4	17.4	19.6	20
0.99	7.5	39.3	56.4	91.2	100

병렬 효율 $E = S/N$ 으로 보면 더 잔인하다. $p=0.99$ 라도 1024코어에서 효율은 9%다. 게다가 이 식은 통신 비용을 0으로 놓은 낙관적 상한이라, 실제 곡선은 이보다 아래에 있고 어느 지점부터는 꺾여 내려간다.⁴

이 비관론을 반박한 것이 구스타프손의 법칙(Gustafson’s Law)이다. 실무에서는 코어가 많아지면 같은 문제를 빨리 푸는 게 아니라 더 큰 문제를 같은 시간에 푼다는 관찰이다. 병렬 기계에서 잰 실행시간 중 순차 부분의 비율을 $s$ 라 하면, 같은 일을 단일 코어로 했을 때 대비 스케일드 속도 향상은

$$S_{\text{scaled}}(N) = s + (1-s)N = N - s\,(N-1)$$

이다(Gustafson 1988). $s=0.05$ 면 128코어에서 121.7배, 1024코어에서 972.9배다. 암달 식과 모순이 아니라 질문이 다르다 — 암달은 고정된 문제를, 구스타프손은 코어와 함께 커지는 문제를 본다. 문제 크기가 코어에 비례해 커지면 순차 부분의 비중이 상대적으로 줄어 확장성이 살아난다. 슈퍼컴퓨터가 여전히 코어를 늘리는 명분이 바로 이것이다.

5. 강 스케일링 vs 약 스케일링

병렬 성능을 평가하는 두 가지 잣대가 있고, 둘을 헷갈리면 벤치마크가 통째로 거짓말이 된다.

구분	문제 크기	이상적 결과	지배 법칙
강 스케일링	고정	코어 N배 → 시간 1/N	암달의 법칙
약 스케일링	코어당 고정(총 크기↑)	코어 N배 → 시간 일정	구스타프손의 법칙

강 스케일링(strong scaling)은 문제 크기를 고정한 채 코어만 늘려 시간이 얼마나 줄어드는지를 본다. 도메인 조각이 점점 작아지므로 통신 비중이 커져, 어느 지점부터는 효율이 급락한다. 약 스케일링(weak scaling)은 코어당 작업량을 일정하게 두고 문제와 코어를 함께 키운다. 계산 시간이 코어 수와 무관하게 평평하면 이상적이다. 논문에서 “우리 코드는 100만 코어까지 확장됩니다”라고 자랑할 때는 십중팔구 약 스케일링 이야기다. 강 스케일링으로 그렇게 나오는 코드는 거의 없다. 이런 성능 평가 역시 넓게 보면 검증 및 확인의 일부이며, 실제 가속 한계는 상당 부분 GPU 컴퓨팅이나 통신 토폴로지 최적화로 밀어붙인다.

6. 관련 문서

• GPU 컴퓨팅 · MPI · PETSc
• 영역 분할법 · 그래프 분할 · 부하 분산
• 전산과학
• 전산유체역학
• 분자동역학 · LAMMPS · GROMACS
• 유한요소법 · 격자
• 적응 격자 세분화
• OpenFOAM
• 희소행렬 · 크리로프 부분공간법
• 검증 및 확인

7. Footnotes

1. 그래서 요즘 신입 해석 엔지니어에게 “코드 잘 짜?”라고 물으면, 사실은 “MPI 데드락 안 내고 짤 수 있어?”라는 뜻인 경우가 많다. ↩

2. MPI로 짠 코드를 처음 돌리면 반드시 한 번은 데드락(deadlock)에 빠져 밤을 새운다. 두 프로세스가 서로 “너 먼저 받아”라며 영원히 기다리는 상황. 이걸 안 겪은 HPC 개발자는 없다. 일종의 통과의례. ↩

3. 코어를 두 배로 늘렸는데 계산이 더 느려지는 마법을 처음 목격하면 컴퓨터가 고장 난 줄 안다. 아니다. 그게 물리다. 정확히는 통신 물리다. ↩

4. 암달의 법칙은 병렬 컴퓨팅 강의 첫 시간에 배우고, 실무 3년 차에 뼈저리게 다시 배운다. “왜 코어 128개 붙였는데 4배밖에 안 빨라져요?” — 식을 거꾸로 풀면 128코어에서 4배는 $p \approx 0.76$, 즉 순차 부분이 약 24% 라는 뜻이다. 5%짜리 순차 부분이었다면 17배는 나왔어야 한다. 그러니 범인은 “그 5%“가 아니라 아무도 병렬화 안 한 입출력·전처리 덩어리이거나, 식에 아예 없는 통신 비용이다. ↩