Puzzle 14: 누적 합

개요

누적 합(prefix sum, scan 이라고도 합니다)은 시퀀스의 값을 차례로 더해 나가는 기본적인 병렬 알고리즘입니다. 정렬 알고리즘부터 과학 시뮬레이션까지 수많은 병렬 응용의 핵심에 자리하고 있으며, 숫자 시퀀스를 누적 합계로 변환하는 역할을 합니다. 순차적으로 계산하기는 간단하지만, GPU에서 효율적으로 만들려면 기발한 병렬적 사고가 필요합니다!

1D LayoutTensor a에 대해 누적 합을 계산하고 결과를 1D LayoutTensor output에 저장하는 커널을 구현하세요.

참고: a의 크기가 블록 크기보다 큰 경우, 각 블록의 합계만 저장합니다.

핵심 개념

이 퍼즐에서 배울 내용:

• 로그 복잡도를 가진 병렬 알고리즘
• 공유 메모리 협력 패턴
• 다단계 연산 전략

핵심 통찰은 순차 연산을 공유 메모리를 활용한 효율적인 병렬 알고리즘으로 변환하는 방법을 이해하는 것입니다.

예를 들어, 입력 시퀀스 \([3, 1, 4, 1, 5, 9]\) 가 주어지면, 누적 합은 다음과 같이 만들어집니다:

• \([3]\) (첫 번째 원소 그대로)
• \([3, 4]\) (3 + 1)
• \([3, 4, 8]\) (이전 합 + 4)
• \([3, 4, 8, 9]\) (이전 합 + 1)
• \([3, 4, 8, 9, 14]\) (이전 합 + 5)
• \([3, 4, 8, 9, 14, 23]\) (이전 합 + 9)

수학적으로, 시퀀스 \([x_0, x_1, …, x_n]\) 의 누적 합은 다음과 같습니다: \[ [x_0, x_0+x_1, x_0+x_1+x_2, …, \sum_{i=0}^n x_i] \]

순차 알고리즘이라면 \(O(n)\) 단계가 필요하겠지만, 여기서는 영리한 2단계 병렬 알고리즘으로 \(O(\log n)\) 단계만에 완료합니다! 위의 애니메이션에서 이 과정을 확인할 수 있습니다.

이 퍼즐은 개념을 단계적으로 익힐 수 있도록 두 파트로 나뉩니다:

• 🔰 기본 버전 모든 데이터가 공유 메모리에 들어가는 단일 블록 구현부터 시작합니다. 핵심 병렬 알고리즘의 원리를 파악하는 데 좋습니다.

• ⭐ 완성 버전 이어서 여러 블록에 걸치는 큰 배열을 처리하는 더 까다로운 경우에 도전합니다. 블록 간 조율이 필요합니다.

각 버전은 이전 버전 위에 쌓아 올리는 방식으로, 병렬 누적 합 연산에 대한 이해를 깊이 있게 발전시켜 줍니다. 기본 버전에서 핵심 알고리즘을 다지고, 완성 버전에서는 더 큰 데이터셋으로 확장하는 방법을 배웁니다 — 실제 GPU 애플리케이션에서 자주 마주치는 과제입니다.