Prefix Sum : 효율적인 연산을 위한 가이드

Table of Contents

Multicore-GPU-Programming - This article is part of a series.

Part 1: Basic Parallel Architectures에 대해 알아보자

Part 2: c++로 알아본 쓰레드 프로그래밍

Part 3: 멀티쓰레드에서 쓰레드 간 작업을 어떻게 균일하게 분할할까?

Part 4: 멀티쓰레드에서 행렬 연산(matmul) 성능 증가시키는 방법들

Part 5: 멀티쓰레딩을 편리하게 해주는 OpenMP 사용법

Part 6: 그래프 구조를 더 효율적으로 저장하는 방법들

Part 7: This Article

Part 8: CUDA 프로그래밍 기초

Part 9: CPU-GPU 통신 및 CUDA를 활용한 이미지 프로세싱 기법

Part 10: CUDA와 Nvidia GPU 아키텍처: 스레드 계층, 메모리 계층 및 GPU 캐시 구조 이해하기

Part 11: CUDA Memories : 레지스터, 공유 메모리, 글로벌 메모리

Intro
#

병렬 컴퓨팅과 데이터 처리의 세계에서는 효율적인 알고리즘이 성능 최적화를 위해 매우 중요합니다. 본 포스팅에서는 데이터 처리 작업의 속도와 효율성을 높이는 강력한 기술인 prefix sum의 핵심 개념을 다룹니다. 기본적인 reduce 연산에 대한 이해를 시작으로, 병렬 reduce로의 전환을 탐구한 후, prefix sum과 그 병렬 버전에 대해 깊이 있게 다룹니다. 특히 Kogge-Stone 알고리즘과 Brent-Kung 알고리즘에 중점을 두어 그 중요성과 현대 컴퓨팅에서의 응용을 강조합니다.

Reduce
#

Sum reduce problem
#

sum 을 구하는 프로그램의 예시를 봅시다.

#include <chrono>
#include <iostream>

void worker(int *input, int size, int *output)
{
    for (int i = 0; i < size; ++i)
    {
        *output += input[i];
    }
}

int main()
{
    const int arraySize = 100000000;
    int *input = new int[arraySize];
    for (int i = 0; i < arraySize; ++i)
    {
        input[i] = i;
    }
    int totalSum = 0;

    auto start = std::chrono::high_resolution_clock::now();

    worker(input, arraySize, &totalSum);

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;

    std::cout << "Total Sum: " << totalSum << std::endl;
    std::cout << "Time taken (non-parallel): " << duration.count() << " seconds" << std::endl;

    delete[] input;
    return 0;
}

이 작업을 병렬화하고 싶을 때는 어떻게 할까요? 아래처럼 멀티 쓰레드로 하면 됩니다.

#include <chrono>
#include <iostream>
#include <thread>
#include <vector>

void worker(int *input, int start, int size, int *output)
{
    for (int i = start; i < start + size; ++i)
    {
        *output += input[i];
    }
}

int main()
{
    const int arraySize = 100000000;
    int *input = new int[arraySize];
    for (int i = 0; i < arraySize; ++i)
    {
        input[i] = i;
    }
    int numThreads = std::thread::hardware_concurrency();
    std::vector<std::thread> threads;
    std::vector<int> partialSums(numThreads, 0);

    int chunkSize = arraySize / numThreads;

    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < numThreads; ++i)
    {
        int start = i * chunkSize;
        threads.push_back(std::thread(worker, input, start, chunkSize, &partialSums[i]));
    }

    for (auto &t : threads)
    {
        t.join();
    }

    int totalSum = 0;
    for (const auto &sum : partialSums)
    {
        totalSum += sum;
    }

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;

    std::cout << "Total Sum: " << totalSum << std::endl;
    std::cout << "Time taken (parallel): " << duration.count() << " seconds" << std::endl;

    delete[] input;
    return 0;
}

하지만 결과를 보면 race condition 이 생겼음을 알 수 있습니다.

Try 1 : locks
#

고치는 첫번째 방법은 lock 을 사용하는 것입니다. 이 방법은 커다란 성능 저하를 일으킵니다.

std::mutex global_mutex;

void worker(int *input, int size, int *output)
{
    for (int i = 0; i < size; ++i)
    {
        global_mutex.lock();
        *output += input[i];
        global_mutex.unlock();
    }
}

그런데 앞서서 짧은 연산에는 lock 보다 atomic 이 낫다고 배웠습니다.

Try 2 : atomics
#

void worker(int *input, int size, std::atomic<int>* output)
{
    for (int i = 0; i < size; ++i)
    {
        *output += input[i];
    }
}

lock 보다는 성능 저하가 작지만, 여전히 atomic 도 느린 연산입니다.

다른 방법은 없을까요? 만약 무한대의 코어를 가지고 있다고 하면, 가장 최대로 병렬화할 수 있는 방법은 무엇일까요?

Serial reduce
#

만약 코어가 여러 개 있어도 순차적 연산이면 쓸모가 없습니다. 즉, 병렬화될 수 없습니다. 아래와 같이 순차적인 덧셈이 있는 연산이라고 할 때 \(O(N)\) 의 시간이 걸립니다.

Parallel reduce
#

병렬화를 하고 싶다면 병렬화가 가능하도록 코드를 작성해야 합니다. 이렇게 된다면 무한개의 코어가 있을 때 연산 시간은 \(O(logN)\) 으로 단축될 수 있습니다.

이제 유한개의 코어가 있을 때 병렬화를 어떻게 해야할지 알아봅시다.

Parallel prefix sum
#

Prefix Sum은 배열의 각 요소에 대해 이전 요소들의 합을 계산하는 방식입니다. (이 방법은 코딩테스트에서도 많이 사용됩니다.)

Prefix Sum을 사용하면 배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해줍니다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있습니다.

병렬 Prefix Sum의 알고리즘에는 Kogge-Stone 알고리즘과 Brent-Kung 알고리즘이 있습니다.

Kogge-Stone algorithm
#

초기 배열 A = {3,1,7,0,4,1,6,3} 이라고 합시다.

Kogge-Stone 알고리즘은 여러 단계로 나누어 수행됩니다. 각 단계에서는 이전 단계에서 계산된 값을 사용하여 새로운 값을 계산합니다. 아래는 각 단계의 일반적인 과정입니다:

단계 k에서, 각 프로세서는 거리 2^k 만큼 떨어진 이전 값을 더합니다.
이 과정을 통해 모든 요소는 자신의 이전 요소들과의 합을 계산하게 됩니다.

cpp 구현은 여기 있습니다.

만약 무한대의 코어가 있다면 병렬처리가 최대한으로 이루어져 각 연산 단계가 동시에 수행될 수 있어 \(O(logN)\) 의 시간이 걸립니다. 예를 들어, 입력 배열의 크기가 8인 경우 최대 3단계 안에 연산이 완료됩니다.

그러나 우리는 유힌개의 코어만 가지고 있습니다.🥲 첫 단계에서는 N-1 연산, 두번째에서는 N-2, … 마지막 단계에서는 N-N/2 번의 연산이 일어나 전체 연산량은 \(O(NlogN)\) 입니다. P개의 코어를 사용한다면 연산량은 \(O(\frac{N}{P} logN)\) 이 됩니다. 그리고 중간 결과를 저장하기 위해 추가적인 메모리가 필요합니다. 단계마다 새로운 배열을 생성해야 하므로, 총 \(O(log N)\) 배의 메모리가 추가로 필요합니다.

이러한 문제를 해결하기 위해 double buffering 를 사용하기도 합니다. 매번 새로운 배열을 생성하는 것보다 2개의 버퍼에 중간 결과를 저장하는 방법입니다. 이 방법으로 2배 이상의 메모리 공간을 절약할 수 있습니다.

Brent-Kung algorithm
#

Brent-Kung 알고리즘은 balanced binary tree 를 사용합니다. (실제 트리 구조는 아니고, 연산 패턴을 차용합니다.)

두 단계로 구성되는데, upsweep 단계와 downsweep 단계입니다.

Phase1 : upsweep

배열을 재귀적으로 절반씩 나누어 합을 구합니다. 중간 결과를 트리 구조로 저장합니다.

Phase2 : downsweep

이 단계에서는 중간 결과를 사용하여 최종 prefix sum을 계산합니다. 이 과정에서 다시 트리 구조를 따라가며 값을 계산합니다.

예시를 통해 자세히 봅시다.

초기화

입력 배열: A = [a0, a1, a2, a3, a4, a5, a6, a7]
출력 배열: S = [s0, s1, s2, s3, s4, s5, s6, s7]

Upsweep 단계

레벨0 : 각 요소는 그대로 유지됩니다.
S0: [a0, a1, a2, a3, a4, a5, a6, a7]
레벨1: 각 페어의 합을 계산합니다.
S1: [a0, (a0 + a1), a2, (a2 + a3), a4, (a4 + a5), a6, (a6 + a7)]
레벨2 : 레벨 1에서 계산된 값을 사용하여 더 큰 페어의 합을 계산합니다.
S2: [a0, (a0 + a1), (a0 + a1 + a2 + a3), a3, a4, (a4 + a5), (a4 + a5 + a6 + a7), a7]
레벨3 : 최종 합을 계산합니다.
S3: [a0, (a0 + a1), (a0 + a1 + a2 + a3), (a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7), a4, (a4 + a5), (a4 + a5 + a6 + a7), a7]

Downsweep 단계

레벨3 : 최종 합을 루트 노드로 유지하고 나머지 값들을 그대로 유지합니다.
S3: [a0, (a0 + a1), (a0 + a1 + a2 + a3), 0, a4, (a4 + a5), (a4 + a5 + a6 + a7), 0]
레벨2 : 중간 결과를 사용하여 아래로 내려가면서 값을 계산합니다.
S2: [a0, (a0 + a1), 0, (a0 + a1 + a2 + a3), a4, (a4 + a5), 0, (a4 + a5 + a6 + a7)]
레벨1 : 레벨 2에서 계산된 값을 사용하여 최종 프리픽스 합을 계산합니다.
S1: [a0, 0, (a0 + a1), (a0 + a1 + a2 + a3), a4, 0, (a4 + a5), (a4 + a5 + a6 + a7)]
레벨0 : 최종 프리픽스 합을 계산합니다.
S0: [0, a0, (a0 + a1), (a0 + a1 + a2), (a0 + a1 + a2 + a3), (a0 + a1 + a2 + a3 + a4), (a0 + a1 + a2 + a3 + a4 + a5), (a0 + a1 + a2 + a3 + a4 + a5 + a6)]

Brent-Kung 알고리즘은 새로운 메모리 공간이 필요 없습니다. 시간복잡도를 생각해보면, 두 단계에서 각각 \(logN\) 연산이 필요합니다(총 \(2logN\)). 따라서 시간복잡도는 \(logN\) 입니다. 연산량은 각 단계에서 N-1개의 연산이 필요하므로, \(O(N)\) 으로 표현할 수 있습니다. P개의 프로세서가 있다면 \(O(N/P)\) 가 걸릴 것입니다.