C++ Parallel Algorithms | "병렬 알고리즘" 가이드

· 20분 읽기 · 수정 고급 튜토리얼
C++ Parallel Algorithms | "병렬 알고리즘" 가이드

이 글의 핵심

C++ Parallel Algorithms에 대한 실전 가이드입니다.

들어가며

C++17 병렬 알고리즘은 멀티코어 CPU를 활용하여 표준 알고리즘을 자동으로 병렬화합니다. std::execution::par를 추가하는 것만으로 std::sort, std::transform 등을 병렬 실행할 수 있습니다.

1. Execution Policy

실행 정책 종류

#include <algorithm>
#include <execution>
#include <vector>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 1. seq: 순차 실행 (기본)
    std::sort(std::execution::seq, v.begin(), v.end());
    
    // 2. par: 병렬 실행
    std::sort(std::execution::par, v.begin(), v.end());
    
    // 3. par_unseq: 병렬 + 벡터화
    std::sort(std::execution::par_unseq, v.begin(), v.end());
    
    return 0;
}

Execution Policy 비교

정책설명특징사용 시기
seq순차 실행단일 스레드작은 데이터
par병렬 실행멀티스레드큰 데이터, 독립적 연산
par_unseq병렬 + 벡터화SIMD + 멀티스레드큰 데이터, 단순 연산

2. 병렬 정렬

기본 정렬

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>

void benchmarkSort() {
    std::vector<int> v1(10000000);
    std::generate(v1.begin(), v1.end(), std::rand);
    
    auto v2 = v1;
    
    // 순차 정렬
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(v1.begin(), v1.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    // 병렬 정렬
    start = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, v2.begin(), v2.end());
    end = std::chrono::high_resolution_clock::now();
    auto par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "순차 정렬: " << seq_time.count() << "ms" << std::endl;
    std::cout << "병렬 정렬: " << par_time.count() << "ms" << std::endl;
    std::cout << "속도 향상: " << (double)seq_time.count() / par_time.count() << "x" << std::endl;
}

int main() {
    benchmarkSort();
    return 0;
}

출력 (4코어):

순차 정렬: 2341ms
병렬 정렬: 687ms
속도 향상: 3.4x

3. 병렬 변환

transform

#include <algorithm>
#include <execution>
#include <vector>
#include <cmath>
#include <iostream>

int main() {
    std::vector<double> data(10000000);
    std::iota(data.begin(), data.end(), 1.0);
    
    // 병렬 제곱근 계산
    std::transform(std::execution::par, 
        data.begin(), data.end(), data.begin(),
         { return std::sqrt(x); });
    
    std::cout << "첫 5개: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

출력:

첫 5개: 1 1.41421 1.73205 2 2.23607

for_each

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(1000000);
    std::iota(v.begin(), v.end(), 1);
    
    // 병렬 for_each
    std::for_each(std::execution::par, v.begin(), v.end(), 
         {
            x = x * x;  // 제곱
        });
    
    std::cout << "v[99]: " << v[99] << std::endl;  // 10000
    
    return 0;
}

4. 병렬 집계

reduce

#include <numeric>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(10000000);
    std::iota(v.begin(), v.end(), 1);
    
    // 병렬 reduce (합계)
    long long sum = std::reduce(std::execution::par, 
        v.begin(), v.end(), 0LL);
    
    std::cout << "합: " << sum << std::endl;
    
    return 0;
}

출력:

합: 50000005000000

transform_reduce

#include <numeric>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(1000000);
    std::iota(v.begin(), v.end(), 1);
    
    // 병렬 제곱합
    long long sum_of_squares = std::transform_reduce(
        std::execution::par,
        v.begin(), v.end(),
        0LL,
        std::plus<>(),
         { return static_cast<long long>(x) * x; }
    );
    
    std::cout << "제곱합: " << sum_of_squares << std::endl;
    
    return 0;
}

5. 병렬 검색

find

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(10000000);
    std::iota(v.begin(), v.end(), 1);
    
    // 병렬 find
    auto it = std::find(std::execution::par, v.begin(), v.end(), 5000000);
    
    if (it != v.end()) {
        std::cout << "찾음: " << *it << std::endl;
        std::cout << "인덱스: " << std::distance(v.begin(), it) << std::endl;
    }
    
    return 0;
}

count_if

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(10000000);
    std::generate(v.begin(), v.end(), std::rand);
    
    // 병렬 count_if (짝수 개수)
    auto count = std::count_if(std::execution::par, v.begin(), v.end(),
         { return x % 2 == 0; });
    
    std::cout << "짝수 개수: " << count << std::endl;
    
    return 0;
}

6. 자주 발생하는 문제

문제 1: 작은 데이터

#include <algorithm>
#include <execution>
#include <vector>
#include <chrono>
#include <iostream>

void benchmarkSmallData() {
    std::vector<int> small(100);
    std::generate(small.begin(), small.end(), std::rand);
    
    auto v1 = small;
    auto v2 = small;
    
    // 순차
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(v1.begin(), v1.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto seq_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    // 병렬 (오버헤드 > 이득)
    start = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, v2.begin(), v2.end());
    end = std::chrono::high_resolution_clock::now();
    auto par_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "순차: " << seq_time.count() << "μs" << std::endl;
    std::cout << "병렬: " << par_time.count() << "μs" << std::endl;
}

int main() {
    benchmarkSmallData();
    // 순차: 5μs
    // 병렬: 150μs (오버헤드)
    
    return 0;
}

문제 2: 공유 상태 (데이터 레이스)

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(1000000);
    std::iota(v.begin(), v.end(), 1);
    
    int sum = 0;
    
    // ❌ 데이터 레이스
    std::for_each(std::execution::par, v.begin(), v.end(), [&](int x) {
        sum += x;  // 여러 스레드가 sum에 동시 접근
    });
    
    std::cout << "잘못된 합: " << sum << std::endl;  // 예상과 다름
    
    // ✅ reduce 사용
    long long correct_sum = std::reduce(std::execution::par, v.begin(), v.end(), 0LL);
    
    std::cout << "올바른 합: " << correct_sum << std::endl;
    
    return 0;
}

문제 3: 예외 처리

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, -3, 4, -5};
    
    try {
        // 병렬 실행 중 예외
        std::for_each(std::execution::par, v.begin(), v.end(),  {
            if (x < 0) {
                throw std::runtime_error("음수 발견");
            }
        });
    } catch (const std::exception& e) {
        // 여러 스레드에서 예외 발생 가능
        // 첫 번째 예외만 잡힘
        std::cout << "예외: " << e.what() << std::endl;
    }
    
    return 0;
}

문제 4: 순서 의존 연산

#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // ❌ 순서 의존 (레이스)
    std::for_each(std::execution::par, v.begin(), v.end(), [&](int& x) {
        x = v[0] + 1;  // v[0]을 여러 스레드가 읽음 (위험)
    });
    
    // ✅ 독립적 연산
    std::for_each(std::execution::par, v.begin(), v.end(),  {
        x = x * 2;  // 각 요소 독립적
    });
    
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    return 0;
}

7. 지원 알고리즘

주요 알고리즘

#include <algorithm>
#include <numeric>
#include <execution>

// 정렬
std::sort(std::execution::par, v.begin(), v.end());
std::stable_sort(std::execution::par, v.begin(), v.end());
std::partial_sort(std::execution::par, v.begin(), v.begin() + 10, v.end());

// 검색
std::find(std::execution::par, v.begin(), v.end(), 42);
std::find_if(std::execution::par, v.begin(), v.end(), pred);
std::binary_search(std::execution::par, v.begin(), v.end(), 42);

// 변환
std::transform(std::execution::par, v.begin(), v.end(), v.begin(), func);
std::for_each(std::execution::par, v.begin(), v.end(), func);

// 집계
std::reduce(std::execution::par, v.begin(), v.end(), 0);
std::transform_reduce(std::execution::par, v.begin(), v.end(), 0, plus, func);

// 복사
std::copy(std::execution::par, v1.begin(), v1.end(), v2.begin());
std::copy_if(std::execution::par, v1.begin(), v1.end(), v2.begin(), pred);

// 기타
std::count(std::execution::par, v.begin(), v.end(), 42);
std::count_if(std::execution::par, v.begin(), v.end(), pred);
std::all_of(std::execution::par, v.begin(), v.end(), pred);
std::any_of(std::execution::par, v.begin(), v.end(), pred);

8. 실전 예제: 이미지 처리

#include <algorithm>
#include <execution>
#include <vector>
#include <cmath>
#include <iostream>

struct Pixel {
    unsigned char r, g, b;
};

class ImageProcessor {
    std::vector<Pixel> pixels;
    int width, height;
    
public:
    ImageProcessor(int w, int h) : width(w), height(h) {
        pixels.resize(w * h);
    }
    
    // 병렬 그레이스케일 변환
    void toGrayscale() {
        std::for_each(std::execution::par, pixels.begin(), pixels.end(),
             {
                unsigned char gray = static_cast<unsigned char>(
                    0.299 * p.r + 0.587 * p.g + 0.114 * p.b
                );
                p.r = p.g = p.b = gray;
            });
    }
    
    // 병렬 밝기 조정
    void adjustBrightness(int delta) {
        std::for_each(std::execution::par, pixels.begin(), pixels.end(),
            [delta](Pixel& p) {
                auto clamp =  {
                    return std::max(0, std::min(255, val));
                };
                
                p.r = clamp(p.r + delta);
                p.g = clamp(p.g + delta);
                p.b = clamp(p.b + delta);
            });
    }
    
    // 병렬 블러 (간단한 평균)
    void blur() {
        auto original = pixels;
        
        std::for_each(std::execution::par, pixels.begin(), pixels.end(),
            [&](Pixel& p) {
                int idx = &p - &pixels[0];
                int x = idx % width;
                int y = idx / width;
                
                // 3x3 평균 (간단화)
                int r_sum = 0, g_sum = 0, b_sum = 0, count = 0;
                
                for (int dy = -1; dy <= 1; ++dy) {
                    for (int dx = -1; dx <= 1; ++dx) {
                        int nx = x + dx;
                        int ny = y + dy;
                        
                        if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
                            int nidx = ny * width + nx;
                            r_sum += original[nidx].r;
                            g_sum += original[nidx].g;
                            b_sum += original[nidx].b;
                            ++count;
                        }
                    }
                }
                
                p.r = r_sum / count;
                p.g = g_sum / count;
                p.b = b_sum / count;
            });
    }
    
    // 병렬 픽셀 카운트
    int countBrightPixels(int threshold) {
        return std::count_if(std::execution::par, pixels.begin(), pixels.end(),
            [threshold](const Pixel& p) {
                int brightness = (p.r + p.g + p.b) / 3;
                return brightness > threshold;
            });
    }
};

int main() {
    ImageProcessor img(1920, 1080);
    
    img.toGrayscale();
    img.adjustBrightness(20);
    img.blur();
    
    int bright = img.countBrightPixels(128);
    std::cout << "밝은 픽셀: " << bright << std::endl;
    
    return 0;
}

정리

핵심 요약

  1. 병렬 알고리즘: C++17 멀티코어 활용
  2. Execution Policy: seq, par, par_unseq
  3. 성능: 큰 데이터에서 2-4배 향상
  4. 주의: 데이터 레이스, 순서 의존 금지
  5. 적용: 10,000개 이상, 독립적 연산

병렬 알고리즘 효과

데이터 크기연산 복잡도병렬 효과권장 정책
< 1,000낮음없음seq
1,000-10,000낮음낮음seq
> 10,000낮음중간par
> 10,000높음높음par
> 100,000단순매우 높음par_unseq

실전 팁

사용 원칙:

  • 큰 데이터 (10,000개 이상)에만 사용
  • 계산 집약적 연산에 효과적
  • 독립적 연산만 병렬화
  • 공유 상태 피하기

성능:

  • 프로파일링으로 효과 측정
  • 작은 데이터는 오버헤드 큼
  • 메모리 집약적 연산은 효과 낮음
  • CPU 코어 수에 따라 효과 다름

주의사항:

  • 데이터 레이스 방지 (std::atomic, reduce)
  • 예외 처리 신중 (std::terminate 가능)
  • 순서 의존 연산 금지
  • 디버깅 어려움 (TSan 사용)

다음 단계

  • C++ Execution Policy
  • C++ Thread
  • C++ Atomic

관련 글

  • C++ Algorithm Sort |
  • 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리