AI 연산에서의 Reduction

Reduction은 단순 배열 합 계산이 아니라, 실제 AI 모델 내부에서도 매우 자주 사용됩니다.

예를 들어:

• Loss 계산
• Softmax
• Attention score 합산
• Gradient accumulation
• Batch normalization 평균 계산
• Matrix multiplication의 partial sum

등 대부분의 딥러닝 연산 내부에는 Reduction이 포함됩니다.

특히 딥러닝 학습에서는 수천~수만 개의 값들을 합치거나 평균내는 과정이 반복되는데, 이 연산이 느리면 전체 학습 속도도 크게 감소하게 됩니다.

오늘은 GPU에서 AI 연산이 어떻게 병렬처리 되는지 살펴보고자 블로그글을 작성하게 되었습니다.

Reduction이란 ?

Reduction은 여러 개의 값을 하나의 값으로 줄이는 연산입니다.

예를 들어 배열 안에 숫자가 여러 개 있다고 해보겠습니다.
[7.0, 2.1, 5.3, 9.0, 11.2]

이 숫자들을 모두 더하면 최종적으로 34.6이라는 하나의 값이 나옵니다.
7.0 + 2.1 + 5.3 + 9.0 + 11.2 = 34.6

이처럼 여러 개의 데이터를 하나의 결과값으로 만드는 과정을 Reduction이라고 합니다.

Reduction은 덧셈에만 사용되는 개념은 아니고, 많은 숫자들을 줄이는 과정 모두 Reduction입니다. 배열에서 가장 큰 값을 찾는 것도 Reduction이고, 가장 작은 값을 찾는 것도 Reduction입니다.

예를 들어, [7, 2, 5, 9]
이 배열에서 최댓값을 찾으면 결과는 9입니다.
결국 여러 값 중에서 하나의 최댓값만 남았기 때문에 이것도 Reduction입니다.

즉, Reduction은 쉽게 말해, 많은 데이터 중에서 하나의 대표값을 뽑아내는 과정이라고 이해하면 됩니다.

여기서 중요한 점은 Reduction이 두 개의 값을 비교하거나 계산하는 연산을 반복해서 전체 결과를 만든다는 것 입니다.
예를 들어 합계를 구할 때는 두 값을 계속 더하고, 최댓값을 구할 때는 두 값 중 더 큰 값을 계속 선택합니다.

Reduction에서의 병렬

• Parallel Reduction = 병렬로 reduction을 수행하는 전체 개념
• Reduction Tree = 그 병렬 reduction을 트리 구조로 수행하는 방법

순차 방식에서는 8개의 값을 처리하려면 거의 8번에 가까운 단계가 필요합니다.

• 3이랑 1 비교 → 3
• 3이랑 7 비교 → 7
• 7이랑 0 비교 → 7
• 7이랑 4 비교 → 7

reduction tree에서는 3단계면 끝납니다.

• 8개 데이터 → log₂8 = 3단계
• 1024개 데이터 → log₂1024 = 10단계

즉, 시간복잡도는 O(N) -> O(log N)으로 줄어든다는 장점을 가지고 있습니다.

Reduction Tree 기반의 Parallel Reduction 과정

먼저 맨 위를 보면 Thread 0부터 Thread 7까지 총 8개의 thread가 있습니다.
그리고 아래의 0~15 숫자는 input array의 index를 의미합니다. 즉, 총 16개의 데이터를 reduction하는 상황입니다.
각 thread는 짝수 index 하나를 담당합니다.

예를 들어:

Thread 0 → input[0]
Thread 1 → input[2]
Thread 2 → input[4]
...
Thread 7 → input[14]

이처럼 각 thread는 자기 위치를 담당하고, 자기 위치만 수정합니다. 이를 owner computes 방식이라고 합니다.

이 그림에서 핵심은 세 가지인데요.

1. 첫 번째로 stride 값이 1 → 2 → 4 → 8처럼 계속 2배씩 증가한다는 점입니다.
2. 두 번째로 active thread 수는 8 → 4 → 2 → 1처럼 절반씩 감소합니다.
3. 세 번째로 partial sum이 점점 더 큰 범위를 포함하게 됩니다.

control divergence

여기에 문제점이 있습니다.
앞에서 본 그림에서는 stride가 이렇게 증가했습니다.

stride: 1 → 2 → 4 → 8

그러면 active thread는 이렇게 떨어져 있게 되겠죠.

1단계: Thread 0, 1, 2, 3, 4, 5, 6, 7
2단계: Thread 0, 2, 4, 6
3단계: Thread 0, 4
4단계: Thread 0

문제는 GPU에서 thread들이 보통 warp라는 단위로 묶여 실행된다는 것입니다. 보통 한 warp는 32개의 thread로 구성됩니다. 그런데 한 warp 안에서 어떤 thread는 계산하고, 어떤 thread는 계산하지 않으면 문제가 생깁니다.

실제로 논문에서는 input size가 256일 때 기존 방식의 자원 활용 효율이 약 35%밖에 안 된다고 설명합니다.

따라서 개선된 방식이 나오는데요.
아이디어는 active thread들을 멀리 떨어뜨리지 말고, 앞쪽에 연속적으로 모아두자.입니다.

즉 기존 방식은 active thread가 이렇게 됐다면:

• Thread 0, 2, 4, 6

개선 방식은 이렇게 되게 만드는 것입니다.

• Thread 0, 1, 2, 3

그러면 warp 단위로 봤을 때, 어떤 warp는 전부 일하고 어떤 warp는 전부 쉬게 만들 수 있습니다. 이러면 한 warp 안에서 계산하는 thread와 쉬는 thread가 섞이는 상황이 줄어듭니다.

memory 접근 효율

global memory를 자주 쓰지 않고, shared memory를 자주 사용하여, memory 접근 효율을 늘려보자는 아이디어를 떠올릴 수 있습니다.

처음엔 global memory를 통해서 input 값을 불러옵니다. 그 이후 계산 부터는 global memory가 아니라 shared memory에 저장합니다. 즉, 다음 과정 reduction 부터는 shared memory 안에서만 진행하는 것입니다.

마지막으로 최종 결과만 global memory의 output에 한 번 저장하면 memory 접근 효율성을 올릴 수 있습니다.

마무리

Reduction은 단순한 배열 합산 알고리즘처럼 보이지만, 실제로는 AI 연산과 GPU 병렬 처리의 핵심이 되는 패턴입니다.

특히:

• control divergence 최소화
• memory 접근 최적화
• warp 단위 실행 구조 이해

같은 개념들은 CUDA 최적화에서 매우 중요한 요소입니다.

딥러닝 모델이 커질수록 연산량도 폭발적으로 증가하기 때문에, 앞으로의 AI 시스템에서는 단순 모델 구조뿐 아니라 GPU 연산 최적화 역시 더욱 중요해질 것이라고 생각합니다.