13. 병렬 처리 패턴: Fork-Join·작업 훔치기(work-stealing)·데이터 병렬 vs 작업 병렬

난이도: 중상

1. Fork-Join 모델

fork 는 하나의 큰 작업을 독립적인 하위 작업으로 나눠 동시에 실행하도록 펼치는 것, join 은 그 하위 작업들이 끝나길 기다려 결과를 합치고 다음 단계로 넘어가는 동기화 지점이다. 한 틱은 보통 의존성 DAG 로 표현한다: 예) 입력 적용 → (AI ∥ 물리 ∥ AoI계산) → 충돌해결 → 스냅샷직렬화 → 송신. 화살표가 의존성이고, 같은 단계의 ∥ 작업은 병렬로 fork 했다가 다음 단계 전에 join 한다.

join 은 배리어 다. 모든 하위 작업 중 가장 느린 것(critical path)이 끝나야 통과하므로, 부하가 불균형하면 빠른 워커가 놀며 기다린다. 즉 join 지점이 암달의 법칙(concurrency/problem12)의 직렬 구간처럼 작동해 확장성의 상한을 만든다. join 을 줄이려면 단계 경계를 느슨하게(파이프라이닝) 하거나 의존성을 더 잘게 쪼갠다.

2. 작업 훔치기(work-stealing)

각 워커는 자기 전용 덱(double-ended queue) 을 갖는다. 워커는 자기가 새로 fork 한 작업을 덱의 한쪽(아래, bottom)에 push 하고, 처리할 때도 같은 쪽에서 LIFO 로 pop 한다. 일이 떨어진 워커는 다른 워커의 덱 반대쪽(위, top)에서 FIFO 로 하나 훔친다.

• 자기 것 LIFO: 방금 fork 한 작업은 캐시에 데이터가 따뜻하고, fork-join 의 재귀 구조상 가장 최근 작업이 보통 가장 작은 하위 트리라 지역성이 좋다. push/pop 이 같은 끝이라 대개 원자 연산 없이(소유 워커 단독 접근) 빠르다.
• 훔치기 FIFO: 덱의 오래된(위쪽) 작업은 보통 더 큰 하위 트리라, 한 번 훔치면 큰 덩어리를 가져가 추가 훔치기 빈도가 준다. 소유 워커의 bottom 접근과 도둑의 top 접근이 양 끝으로 갈려 경합이 적다(보통 CAS 한 번).

중앙 단일 큐 vs work-stealing: 단일 큐는 구현이 단순하지만 모든 워커가 한 락/원자 변수에 몰려 코어가 늘수록 경합이 병목(concurrency/problem5 false sharing 도). work-stealing 은 평상시 지역 덱만 만져 경합이 거의 없고 부하가 자동 분산된다. 대신 구현이 복잡하고, 작업 수가 적거나 입자도가 크면 훔치기 이득이 작다.

3. 데이터 병렬 vs 작업 병렬

• 데이터 병렬: 같은 연산을 많은 원소에 적용. 예) 엔티티 1만 개 위치 적분, 데미지 일괄 계산. 범위 분할(range split) 로 [0..N) 을 청크로 나눠 parallel_for 한다. SoA 레이아웃(os_memory/problem12)·SIMD 와 궁합이 좋다.
• 작업 병렬: 서로 다른 일을 동시에. 예) 물리·AI·사운드·네트워크 송신을 별도 작업으로. 기능 분할(functional split), 의존성 DAG 로 조율. 작업마다 부하가 달라 work-stealing 의 동적 분산이 특히 유효.

실무 틱 루프는 둘을 섞는다: 상위는 작업 병렬(시스템별), 각 시스템 내부는 데이터 병렬(엔티티 범위).

4. 입자도(granularity)와 오버헤드

• 너무 잘게: 작업 1개당 스케줄링·덱 push/pop·캐시 이동·join 부기 비용이 실제 계산보다 커진다. 수십 ns 짜리 작업을 수만 개 만들면 오버헤드가 지배.
• 너무 크게: 부하 불균형이 커지고(한 청크가 늦으면 전체가 기다림) 코어를 못 채운다.
• 순차 임계값(sequential cutoff): 재귀 분할에서 "원소 수가 임계값(예: 256~1024) 이하면 더 안 나누고 그냥 순차 처리"하는 컷오프를 둔다. 청크 크기는 보통 작업당 수 µs 수준이 되게 잡고(수천~수만 원소), 프로파일로 조정한다.

5. 함정

• (a) 블로킹 I/O 를 워커에: 잡 워커 수는 보통 코어 수에 맞춰 고정돼 있다. 그 워커가 디스크/네트워크/락에서 블로킹되면 코어 하나가 통째로 놀고, 여러 개가 블로킹되면 잡 시스템 전체가 멈춘다(스레드 기아). I/O 는 별도 I/O 풀/비동기로 빼고(concurrency/problem8 async), CPU 잡 워커는 계산만.
• (b) 거짓 공유·오버서브스크립션: 워커들이 같은 캐시 라인의 다른 변수를 갱신하면 false sharing 으로 캐시 라인이 핑퐁(concurrency/problem5). 워커별 누산기를 캐시 라인 정렬로 분리한다. 또 (코어 수 + 다른 풀들) 합이 코어 수를 넘으면 오버서브스크립션 → 컨텍스트 스위치·캐시 오염으로 느려진다. 풀 크기 총합을 코어 수에 맞춘다.
• (c) 공유 상태 최소화: 가능한 한 분할 소유(각 워커가 자기 범위만 쓰기) 후 결과 병합(reduce) 으로 동기화를 join 지점 한 곳에 모은다. 작업 도중 공유 자료구조를 락으로 보호하기 시작하면 경합이 work-stealing 이득을 깎는다. 변경이 필요하면 워커-로컬 버퍼에 모았다가 마지막에 합친다(map-reduce 식).

정리

Fork-Join 으로 틱을 DAG 로 표현하고, work-stealing 으로 부하를 동적 분산하며, 데이터/작업 병렬을 적절히 섞고, 입자도를 순차 컷오프로 조절하고, 블로킹·false sharing·공유 상태를 피하는 것이 잡 시스템 설계의 핵심이다. 확장성의 상한은 결국 join(직렬 구간)과 공유 자원 경합이 정한다(concurrency/problem12 암달).