Search
Duplicate

AI/ Prefix Sum(inclusive scan)

Prefix Sum

Prefix Sum은 Cumulative Sum 또는 Inclusive Scan 또는 간단히 Scan이라고도 부르며, 다음과 같이 정의되는 입력 시퀀스의 prefix 합계를 의미한다.
yi=∑j=0ixjy_i = \sum_{j=0}^i x_j
이를 풀어 쓰면 다음과 같다.
y0=x0y1=x0+x1y2=x0+x1+x2y3=x0+x1+x2+x3...\begin{aligned} y_0 &= x_0 \\ y_1 &= x_0 + x_1 \\ y_2 &= x_0 + x_1 + x_2\\ y_3 &= x_0 + x_1 + x_2 + x_3 \\ ... \end{aligned}
예컨대 자연수에 대한 prefix sum은 삼각수(triangular number)가 된다.
input numbers
1
2
3
4
5
6
...
prefix sums
1
3
6
10
15
21
...
Prefix sum을 더 일반화하면 다음과 같이 정의할 수 있다.
yi=⊕j=0ixjy_i = \oplus_{j=0}^i x_j
여기서 ⊕\oplus는 덧셈이나 곱셈 같은 임의의 이항 연산(binary operation)을 나타낸다. 덧셈을 곱셈으로 바꾼 prefix product를 이용하면 factorial 계산을 수행할 수 있다. 아래 설명하는 prefix sum 알고리즘을 곱으로 바꾸어 사용하면 prefix product를 계산할 수 있고 이것으로 factorial을 병렬로 log⁡n\log n 시간에 계산할 수 있다.

Parallel Prefix Sum

prefix sum은 순차적으로 처리되므로 계산에 O(n)O(n) 시간이 걸린다. 이것을 병렬화하면 O(log⁡n)O(\log n) 시간에 연산을 수행할 수 있다. 이에 대한 알고리즘은 2가지가 존재한다.

Kogge-Stone Algorithm

Kogge-Stone 알고리즘 짧은 span을 가지기 때문에 더 병렬적이지만 작업량이 많아서 덜 작업 효율적이다. 병렬성이 높기 때문에 GPU로 작업하는 것이 유리하다.
Kogge-Stone 알고리즘을 절차는 아래 참조
1.
우선 ii를 00부터 log⁡2(n)\log_2(n)까지 반복
2.
1의 반복 내부에서 jj를 00부터 nn까지 아래를 병렬로 반복
•
j>2ij > 2^i이면, x[j]←x[j]+x[j−2i]x[j] \leftarrow x[j] + x[j-2^i]
구현 코드는 아래 참조
void koggeStoneScan(std::vector<int>& x) { int n = x.size(); int log_n = std::log2(n); for (int i = 0; i <= log_n; ++i) { int power = 1 << i; #pragma omp parallel for for (int j = 0; j < n; ++j) { if (j >= power) { x[j] += x[j - power]; } } } }
C++
복사

Blelloch Scan Algorithm

Blelloch Scan 알고리즘은 up-sweep 단계와 down-sweep 단계의 2중 span을 사용하기 때문에 덜 병렬적이지만 작업량이 적어서 더 작업 효율적이다. 병렬성이 떨어지지만 작업 효율적이기 때문에 CPU로 작업하는 것이 유리하다.
Up-sweep 단계는 Reduce라고도 불리며, 입력 배열의 부분 합을 계산하면서 트리 구조를 형성한다. 각 단계에서는 입력 배열의 크기를 절반으로 줄이고 중간 결과를 저장한다.
1.
각 레벨에서 dd를 00부터 log⁡2(n)−1\log_2(n) -1까지 반복
2.
1의 반복 내부에서 ii를 2d+1−12^{d+1}-1에서 nn까지 2d+12^{d+1} 간격으로 아래를 병렬로 반복
•
x[i]←x[i]+x[i−2d]x[i] \leftarrow x[i] + x[i-2^d]
Down-sweep 단계는 root 노드에서부터 하위 노드로 내려가면서 각 노드의 값을 적절히 분배한다. 이 과정에서 중간 결과를 사용하여 최종 누적 합을 계산한다.
1.
root 노드에 대해 x[n−1]=0x[n-1] = 0을 설정
2.
각 레벨에서 dd에서 00에서 log⁡2(n)−1\log_2(n)-1까지 반복
3.
2의 반복 내부에서 ii를 2d+1−12^{d+1}-1에서 nn까지 2d+12^{d+1} 간격으로 아래를 병렬로 반복
•
t←x[i−2d]t \leftarrow x[i - 2^d] (여기서 tt는 x[i−2d]x[i - 2^d]의 값을 저장하는 임시 변수)
•
x[i−2d]←x[i]x[i-2^d] \leftarrow x[i]
•
x[i]←x[i]+tx[i] \leftarrow x[i] + t
예컨대 입력 배열이 [1,2,3,4][1, 2, 3, 4]인 경우 다음과 같이 수행된다.
Up-sweep 단계
1.
d=0,stride=2d = 0, \text{stride} = 2
•
i=1:x[1]←x[1]+x[0]⇒[1,3,3,4]i = 1: x[1] \leftarrow x[1] + x[0] \Rightarrow [1, 3, 3, 4]
•
i=3:x[3]←x[3]+x[2]⇒[1,3,3,7]i = 3: x[3] \leftarrow x[3] + x[2] \Rightarrow [1, 3, 3, 7]
2.
d=1,stride=4d = 1, \text{stride} = 4
•
i=3:x[3]←x[3]+x[1]⇒[1,3,3,10]i = 3: x[3] \leftarrow x[3] + x[1] \Rightarrow [1, 3, 3, 10]
Down-sweep 단계
1.
초기화: x[3]←0⇒[1,3,3,0]x[3] \leftarrow 0 \Rightarrow [1, 3, 3, 0]
2.
d=1,stride=4d = 1, \text{stride} = 4
•
i=3:t←x[1],x[1]←x[3],x[3]←x[3]+t⇒[1,0,3,3]i = 3: t \leftarrow x[1], x[1] \leftarrow x[3], x[3] \leftarrow x[3] + t \Rightarrow [1, 0, 3, 3]
3.
d=0,stride=2d = 0, \text{stride} = 2
•
i=1:t←x[0],x[0]←x[1],x[1]←x[1]+t⇒[0,1,3,3]i = 1: t \leftarrow x[0], x[0] \leftarrow x[1],x[1] \leftarrow x[1] + t \Rightarrow [0, 1, 3, 3]
•
i=3:t←x[2],x[2]←x[3],x[3]←x[3]+t⇒[0,1,3,6]i = 3: t \leftarrow x[2], x[2] \leftarrow x[3],x[3] \leftarrow x[3] + t \Rightarrow [0, 1, 3, 6]
전체 코드는 아래 참조
void blellochScan(std::vector<int>& x) { int n = x.size(); int log_n = std::log2(n); // Up-sweep 단계 for (int d = 0; d < log_n ; d++) { int stride = 1 << (d + 1); int j = 1 << d; #pragma omp parallel for for (int i = stride - 1; i < n; i += stride) { x[i] += x[i - j]; } } // Down-sweep 단계 x[n - 1] = 0; for (int d = log_n - 1; d >= 0; d--) { int stride = 1 << (d + 1); int j = 1 << d; #pragma omp parallel for for (int i = stride - 1; i < n; i += stride) { int t = x[i - j]; x[i - j] = x[i]; x[i] += t; } } }
C++
복사

참고

Made with