Segmented Reduction이란

Reduction

Reduction: 배열이나 데이터의 여러 값을 하나의 값으로 축약(집계)하는 연산

ex) sum, max, min 등

 

일반적으로 배열 전체의 합을 구한다거나 하는 식이 일반적인 Reduction 계산이다.

 

Segmented Reduction

Segmented Reduction: 여러 개의 독립적인 그룹(Segment)로 나눠서 그룹별 각각의 독립적인 Reduction을 수행하고 각 그룹별 값을 얻는 방식.

 

이때, Segment는 사전에 정의된, 각각 연산을 수행할 그룹이라고 생각하면 된다.

 

ex) 구간별 sum 계산

• 입력 배열: [1, 2, 3, 4, 5, 6, 7, 8]
• 세그먼트 경계: [0, 0, 0, 1, 1, 1, 2, 2] (3개의 세그먼트)
• 결과: [6, 15, 15]

 

하지만, 이 Segmented Reduction을 수행하기 위해선 data 전처리 과정이 필요하다.

• 각 data가 어느 segment에 속하는지 정의
• data를 segment 별로 정렬 또는 그룹화
• segment 별 index(경계값) 저장

 

Segmented Reduction을 왜 사용하는가?

이 segmented Reduction은 병렬 컴퓨팅(GPU, CUDA 등)에서 Data를 나누어 계산할 때, 연산을 최적화하기 위해 사용됨

각 그룹별 계산을 할 때, 각 구간을 segment로 사전에 나누고 병렬 계산을 하면 연산 최적화와 병렬 처리 효율성을 가진다.

 

단순히 dictionary나 이중 배열 등을 이용해서 계산을 할 수도 있지만, 이는 구조상 segmented 계산을 할 때 보다 구조가 불규칙하거나, 메모리 상 불연속성 등의 문제로 메모리 접근 등에서 segmented 계산을 하는 것보다 비효율적이다.

 

이런 이점으로 병렬 컴퓨팅을 사용하는 경우 병렬 계산 최적화를 위해서 data 구조를 segment 계산을 할 수 있게 구성하고, segmented 계산 함수를 사용하여 계산 속도를 올릴 수 있다.

 

Segmented Reduction의 단점

하지만, 이 segmented Reduction이 만능인 것은 아니다.

 

segmented Redution은 계산 구조상 위에서 언급한 전처리 과정이 필수적이다. 이 전처리 과정이 한 번만 수행된다면 문제가 없지만, data가 변하는 경우에는 이 data 전처리 과정을 그때마다 수행해야 한다. 특히, 정렬을 수행하는 것은 큰 계산 비용을 차지한다.

 

또한, data가 균등하지 않고 일부 segment에만 몰려있는 경우에는 이 일부 segment 연산을 수행하는 thread에서만 연산량이 많아지고, 병렬 처리가 제대로 이루어지지 않을 가능성이 있다.

 

즉, segmented reduction은 만능이 아니므로, 계산 구조에 맞춰서 data 구조와 계산 방식을 선택할 필요가 있다.