축소 트리 개념

리덕션은 전체 배열을 하나의 값으로 축약하는 연산입니다. 예를 들어 모든 원소를 더해 하나의 총합으로 만듭니다. GPU에서 가장 흔한 패턴 중 하나입니다. 🌳

CPU에서는 원소를 하나씩 차례로 더합니다. 이는 O(n) 순차 단계이므로 숫자가 백만 개라면 서로 의존하는 덧셈을 백만 번 연속으로 수행해야 합니다.

핵심은 덧셈이 결합 법칙을 따른다는 점입니다. (a+b)+c는 a+(b+c)와 같습니다. 따라서 원하는 방식으로 쌍을 묶어 더할 수 있습니다.

묶는 방식에 제약이 없으므로 여러 독립적인 쌍을 동시에 더할 수 있습니다. 모든 스레드가 병렬 단계 하나에서 쌍 하나씩 처리합니다.

한 번 처리하면 원소의 절반이 사라집니다. 이를 반복하면 활성 원소 수가 계속 절반으로 줄어듭니다: 8에서 4, 2, 1로 줄어듭니다.

절반씩 줄이면 n단계가 아니라 log2(n)단계 만에 끝납니다. 원소가 백만 개여도 백만 단계가 아니라 약 20단계 만에 축약됩니다.

쌍을 연결해 그리면 이진 트리가 됩니다. 잎은 입력이고, 각 레벨에서 노드 수가 절반으로 줄며, 루트가 최종 합계입니다.

한 가지 구현 방법은 각 단계에서 스레드가 stride만큼 떨어진 이웃을 더하도록 하는 것입니다. 데이터 전체를 한 번 지날 때마다 stride가 두 배가 됩니다.

각 레벨은 이전 레벨이 끝나야 진행할 수 있으므로, 스레드는 파트너의 결과를 읽기 전에 장벽에서 기다려야 합니다.

전체 덧셈 횟수는 여전히 대략 n이며, 이것이 작업량입니다. 하지만 가장 긴 의존성 체인인 경로 길이는 log2(n)으로 줄어듭니다. 작업량은 같지만 기다리는 시간은 훨씬 짧습니다.

같은 트리는 모든 결합 법칙을 따르는 연산에 사용할 수 있습니다. 최댓값, 최솟값, 곱셈 또는 논리 AND가 그 예입니다. 연산자만 바꾸면 구조는 그대로 유지됩니다.

리덕션 트리를 배웠습니다. 쌍을 병렬로 더하고, 매 단계 절반으로 줄여 log2(n)단계 만에 끝냅니다. 결합 법칙을 따르는 모든 연산에 적용할 수 있습니다. 다음에는 워프를 계속 바쁘게 실행해 보겠습니다! 🎉