Chapter 19

병렬 프로그래밍과 컴퓨테이셔널 씽킹

병렬은 black art가 아니라, 잘 정의된 사고 절차다

19.1 병렬 컴퓨팅의 목표 — 무엇을 위해 빨라지려는가

"GPU로 100배 빨라졌다"라는 말은 실제로 무슨 의미일까? 빨라진다는 건 한 종류가 아니다. 병렬 컴퓨팅이 실제로 추구하는 목표는 보통 세 가지로 정리된다.

같은 문제를 더 빨리 푼다. 영상 한 장의 MRI 재구성을 1시간에서 1분으로. "오늘 안에 결과를 본다"가 가능해진다. 이게 가장 흔히 말하는 가속(speedup).
같은 시간에 더 큰 문제를 푼다. 분자 동역학을 1만 atom에서 100만 atom으로. 시뮬레이션 box가 커지면 새로운 물리 현상이 보인다.
같은 시간에 더 정확하게 푼다. 격자 간격을 0.5 Å에서 0.1 Å로. 시간 스텝을 100배 작게. 같은 데드라인 안에서 더 정밀한 답.

이 셋은 같지 않다. 어떤 응용은 첫 번째만 중요하고, 어떤 응용은 두 번째가 본질이다. 사용자가 정확히 어느 쪽을 원하는지 모른 채 최적화를 시작하면 엉뚱한 곳에 힘을 쓰게 된다.

19.1.1 strong scaling vs weak scaling

이 두 목표를 정량화하는 표준 어휘가 strong scaling과 weak scaling이다.

strong scaling: 문제 크기를 고정하고 프로세서 수만 늘렸을 때 얼마나 빨라지나. 이상적으로는 P개의 프로세서로 P배. 현실은 통신/직렬 부분 때문에 결국 곡선이 꺾인다(Amdahl의 법칙).
weak scaling: 프로세서당 일감을 고정하고 프로세서 수와 문제 크기를 함께 늘렸을 때 처리 시간이 일정하게 유지되나. 이상적으로는 그래프가 평평한 직선. 현실은 통신량이 P에 따라 어떻게 늘어나느냐에 따라 결정된다(Gustafson의 법칙).

strong scaling이 안 나오는 응용을 두고 "확장성이 없다"고 말하기 전에 한 번 더 묻자. weak scaling은 어떤가? 사용자가 진짜 원하는 게 더 큰 문제라면, weak scaling이 좋은 것만으로도 도구로서 가치가 있다. 기상 시뮬레이션, 우주 시뮬레이션은 거의 항상 두 번째 목표 — 더 큰 도메인 — 가 본질이다.

감 잡기

"GPU 8장 묶어서 8배 빨라졌나요?"는 strong scaling 질문이다. "GPU 8장에 1억 셀을 8배 더 큰 박스로 돌릴 수 있나요?"는 weak scaling 질문이다. 후자가 답하기 더 쉽고, 종종 더 유용한 답이다.

19.2 알고리즘 선택 — 효율성 vs 병렬성의 trade-off

병렬화는 알고리즘이 정해진 뒤에 시작하는 게 아니라, 알고리즘 선택 자체가 병렬화의 일부다. 같은 문제를 푸는 알고리즘이 둘 있다고 하자.

알고리즘 A: 직렬 work O(N log N), 병렬화 어려움(연쇄 dependencies).
알고리즘 B: 직렬 work O(N√N), 병렬화 매우 쉬움(독립 부분 문제 분해).

CPU 1코어로는 A가 이긴다(상수 무시 시 N log N < N√N). 그러나 GPU에서는? B가 P개 코어를 모두 채워 돌릴 수 있고, A는 직렬 dependency 때문에 하나의 코어밖에 못 쓰면, 실제 wall-clock으로 B가 압승한다. 총 work이 더 많아도 더 빨리 끝난다는 게 병렬 세계의 흔한 풍경이다.

병렬 prefix sum(8장)은 좋은 예다. 직렬 buf[i]+=buf[i-1]은 O(N) work이지만 N단계 sequential. Hillis-Steele 같은 병렬 스캔은 O(N log N) work이지만 log N 단계로 끝난다. work-efficient Brent-Kung은 work을 다시 O(N)으로 낮추면서도 log N 단계를 유지한다 — 두 가지를 모두 잡은 영리한 디자인. complexity 분석은 병렬 세계에서 work과 depth(span) 둘 다 봐야 한다.

19.2.1 정확도를 약간 양보하기 — 근사 알고리즘

또 하나의 결정적 trade-off가 정확도다. 17장 MRI에서 __sincosf로 갈아탄 것, 18장에서 컷오프 비닝으로 r > r_cut을 무시한 것 — 둘 다 약간의 정확도를 양보하고 큰 성능을 얻은 결정이다.

비슷한 경우가 많다. N-body 문제에서 Barnes-Hut 트리는 O(N²)를 O(N log N)으로 낮추되 멀리 있는 입자들을 한 덩어리로 근사한다. PageRank의 power iteration은 정해진 횟수에서 끊는다 — 실제 고정점까지는 안 가도 충분히 가까운 답을 얻는다. 딥러닝 추론에서 FP16 양자화는 정확도 약간을 잃고 메모리 절반을 얻는다.

"정확하지만 안 끝나는 답"보다 "충분히 정확하고 시간 안에 끝나는 답"이 거의 항상 더 유용하다. 응용이 진짜로 요구하는 정확도를 사용자와 합의해 두는 것이 알고리즘 선택의 첫 단추다.

complexity의 함정

"O(N log N)이 O(N√N)보다 빠르다"는 점근적 진술이지, 작은 N에서는 거짓일 수 있다. GPU 응용에서는 N이 작을 때 — 예를 들어 한 워프 안에서 — 의 상수항과 메모리 패턴이 점근 상수보다 더 중요하다. 작은 N과 큰 N에서 알고리즘을 다르게 쓰는 hybrid 전략이 흔한 이유다.

19.3 문제 분해 — 어디를 자르고 어디를 묶을까

알고리즘이 정해지면 다음은 분해(decomposition)다. 같은 알고리즘도 어떻게 자르냐에 따라 GPU 친화도가 천지차이다.

19.3.1 output-centric vs input-centric

17장과 18장에서 본 scatter vs gather가 바로 이 분해 결정이다.

output-centric (gather): 출력 원소 하나당 스레드 하나. 각 스레드가 자기 출력을 만드는 데 필요한 입력을 끌어모은다. 출력 충돌이 없으니 atomic이 불필요. GPU가 가장 좋아하는 패턴.
input-centric (scatter): 입력 원소 하나당 스레드 하나. 각 스레드가 자기 입력의 기여를 여러 출력에 뿌린다. 출력 충돌 → atomic 필요. 입력이 작고 출력이 클 때, 또는 이웃 관계가 자명할 때 자연스러울 수 있지만, 보통 GPU에서는 손해다.

그러나 output-centric이 무조건 좋은 건 아니다. 예를 들어 sparse matrix-vector product에서 행 단위 출력 분해(CSR)는 행마다 일감 편차가 클 수 있고, 일부 행에 일감이 몰리면 그 워프가 꼬리를 잡고 늘어진다. 이런 경우 nonzero 단위 input-centric 분해 + 적절한 segment reduction이 더 균형을 잡기도 한다.

19.3.2 분해가 결정하는 세 가지

분해 방식은 세 가지를 결정한다.

간섭(interference): 출력 충돌이 있는가, 동기화 비용이 얼마나 드는가.
로드 밸런스(load balance): 모든 스레드/블록이 비슷한 양의 일을 하는가, 아니면 일부가 꼬리를 잡고 늘어지는가.
병렬성(parallelism): 충분히 많은 독립 작업이 있어 GPU SM 수십 개를 다 채울 수 있는가.

예: 영상 처리에서 픽셀 단위 분해는 병렬성이 풍부하고(수백만 픽셀) 간섭이 거의 없다. 반면 영상 처리의 connected component labeling을 컴포넌트 단위로 분해하면, 컴포넌트 수가 적어 병렬성 부족, 컴포넌트 크기가 들쭉날쭉해 로드 임밸런스, 같은 픽셀이 여러 컴포넌트에 의해 만져질 수 있어 간섭. 그래서 픽셀 단위 분해를 다시 시도하되, 알고리즘을 union-find 같은 병렬 친화 형태로 바꾼다 — 분해와 알고리즘이 서로 영향을 주고받는다는 좋은 예다.

   알고리즘 후보 ─┬─ 분해 후보 ─┬─ GPU 매핑 후보
       │             │             │
       └────[병렬성/효율/정확도 trade-off 평가]────┐
                                                  │
                                            [최종 디자인]

그림 19.1 — 알고리즘·분해·매핑은 한 번에 결정되지 않는다. 후보들의 조합에서 trade-off를 보고 고른다.

19.4 컴퓨테이셔널 씽킹 — 사고 절차로서의 병렬화

병렬 프로그래밍을 처음 배우는 사람이 가장 자주 하는 실수는 "내가 가진 직렬 코드를 어디부터 GPU로 옮길까?"라는 질문에서 시작하는 것이다. 이 질문은 잘못된 출발점이다. 직렬 코드는 직렬 사고의 산물이고, 병렬화는 사고를 다시 짜는 일이다.

대신 다음 절차로 접근하자.

1단계 — 본질적으로 직렬인 부분을 식별한다

모든 단계가 다 병렬화될 수 있는 건 아니다. 어떤 부분은 진짜로 순차적인 dependency를 가진다 — 예: 적분기의 다음 시간 스텝은 이전 스텝에 의존한다. 이 부분을 인정하고, Amdahl의 법칙으로 천장(ceiling)을 미리 그린다. "직렬 부분이 5%면 무한 병렬 자원으로도 20배가 한계"라는 사실을 처음에 알아두는 것이 시간을 아낀다.

2단계 — 병렬화 가능한 부분을 변환한다

병렬화 가능 부분을 일단 골랐다면, 그것을 GPU가 좋아하는 형태로 변환한다. scatter→gather, 인접 메모리 접근 패턴, 워프 정렬, 공유 메모리 활용 — 이 책 전반에서 본 도구들. 변환 자체가 알고리즘을 바꿀 수도 있다(예: 직렬 prefix sum → Brent-Kung 스캔).

3단계 — 도메인 특화 trade-off를 협상한다

도메인이 정확도, 메모리, latency 중 무엇에 민감한지 사용자/엔지니어와 합의한다. 의료 영상은 정확도에 민감하지만 일정 RMS 오차 안에서는 받아들인다. 게임 그래픽은 60 FPS가 절대선이고 픽셀 한 점 오차는 무시. 금융 backtesting은 결정성(determinism)이 정확도만큼 중요하다. 이 협상이 끝나야 어떤 근사가 허용되는지 정해진다.

4단계 — 알고리즘+분해 조합을 평가한다

한 가지 조합에 갇히지 말자. 같은 문제를 두세 가지 방식으로 분해해 보고, 작은 데이터로 빠르게 프로토타입을 돌려보고, 어느 쪽이 일을 잘 채우는지(occupancy), 어느 쪽이 메모리 효율적인지(coalescing), 어느 쪽이 통신이 적은지를 비교한다. 본격 최적화는 그 후에. 잘못된 분해 위에서 마이크로 최적화 백날 해도 한계가 명확하다.

좋은 사고법

병렬화는 마법이 아니라 절차다. (1) 직렬 천장 그리기, (2) 병렬 부분 변환, (3) 도메인 trade-off 협상, (4) 알고리즘+분해 조합 평가. 이 네 단계를 명시적으로 거치는 사람이 이긴다.

19.5 정리

17장과 18장이 도구 사용법이었다면, 19장은 그 도구를 언제 어떻게 꺼낼지에 대한 사고 틀이다. 같은 도구가 다른 도메인에서 다르게 쓰인다는 점이 핵심이다. scatter vs gather라는 분해 결정은 MRI에서도, 정전 포텐셜에서도, 다음 장에 볼 cluster halo exchange에서도 다시 등장할 것이다. 매번 어떤 제약(데이터 사이즈, 정확도 요구, 통신 비용)이 결정을 다르게 만드는지 음미하면서 보자.

20장에서는 단일 GPU를 넘어 여러 노드의 GPU 클러스터로 넘어간다. 그때 새로 등장하는 trade-off는 "GPU 사이의 통신"이다. 단일 노드에서는 무시했던 latency가 갑자기 dominant가 된다. 이 변화에 컴퓨테이셔널 씽킹이 어떻게 적용되는지 보자.

이 챕터에서 챙길 것

병렬 컴퓨팅의 목표는 셋: 더 빨리 / 더 큰 문제 / 더 정확하게. strong과 weak scaling으로 정량화한다.
알고리즘 선택은 병렬화의 일부다. work이 더 많은 알고리즘이 병렬에서는 이길 수 있다. work과 depth 둘 다 본다.
정확도 양보는 자주 옳은 결정이다. 사용자가 실제 요구하는 정확도를 합의해 두는 것이 출발점.
분해 방식은 간섭, 로드 밸런스, 병렬성을 결정한다. output-centric(gather)이 GPU 친화적인 디폴트.
병렬화는 사고 절차다: 직렬 천장 식별 → 병렬 부분 변환 → 도메인 trade-off 협상 → 조합 평가.