Prefix Sum2 Parallel Prefix Sum (2) References Programming Massively Parallel Processors Contents Brent-Kung adder Algorithm A More Work-Efficient Parallel Scan Parallel Prefix Sum (1) 이전 포스팅에서 살펴본 Kogge-Stone 커널은 단순하고, 실제 어플리케이션에서의 효율성이 상당히 낮습니다. 위에서 살펴봤듯이, 어떠한 값들의 집합의 합을 계산하는 가장 빠른 병렬 방법은 reduction tree입니다. 충분한 execution units이 있다면, reduction tree는 \(log_2 N\)의 time unit으로 N개의 값에 대한 합을 계산할 수 있습니다. Tree는 출력값 계산에 사용할 수 있는 여러 개의 su.. 2021. 12. 17. Parallel Prefix Sum (1) References Programming Massively Parallel Processors Contents Kogge-Stone Scan 알고리즘 Background 수학적으로 inclusive scan 연산은 binary associative operator \(\oplus\)와 n개의 input 배열 \([ x_0, x_1, \cdots, x_{n-1} ]\)을 취해서 아래의 output 배열을 반환하는 연산입니다. \[ [x_0, (x_0 \oplus x_1), \cdots, (x_0 \oplus x_1 \oplus \cdots x_{n-1}) ] \] 만약 \(\oplus\)가 덧셈 연산이라면 [3 1 7 0 4 1 6 3]의 input 배열에 대한 inclusive scan 연산은 [3 4 .. 2021. 12. 15. 이전 1 다음
