c++11에서 병렬 연산

Caffe 소스를 보니까 GPU 연산은 병렬인데 CPU 연산은 병렬로 처리하지 않고 있어서 c++에서 multi-core를 사용하는 방법에 대해 호기심이 생겼다. 물론 multi-thread를 사용하면 된다는 건 아는데 CUDA에서 GPU를 사용해서 for loop을 쉽게 병렬로 처리하듯이 multi-core CPU에 대해서도 쉽게 처리할 수 있는 방법이 없나 하는 것이다. Open MP와 같은 오픈소스를 사용해도 되겠지만, 표준 c++ 함수를 사용해서 구현할 수 있으리란 생각이 들었다.

사실, c++ 언어 표준 자체도 c++17까지 가고 있는데 c++11 조차도 그 동안 꺼려왔던게 사실이다. 시스템간 이식성 문제 때문에 오픈 소스들도 c++11을 적극적으로 사용하기 보다는 boost 같은 오픈소스 라이브러리를 사용하는 경우가 많다. 5년 쯤 됐으니 최소한 c++11정도는 사용해도 될 시점이 아닌가 싶기도 하다. 병렬연산에 대해 좀 찾아 보면서 c++11에 쓸만한 기능이 참 많은데 그 간에 활용을 안해왔다는 느낌이 든다. python 언어도 사정이 비슷한데 Deep Learning 오픈 소스들을 돌려 보면 python 2.x에서는 잘 돌아가는데 python 3.x에서는 삐걱대는 경우가 많더라. 포팅하는 것이 어려운 건 아니지만 시간을 들여야 한다.

아무튼 여기서는 multi-core 시스템에서 c++11기반의 multi-thread를 활용해서 병렬연산을 하는 방법에 대해 간단히 정리한다. Deep learning에서 기본적으로 수많은 matrix와 vector data 계산을 해야 하는데 multi-core를 활용하지 않을 이유가 없기 때문이다. 물론 multi-core CPU 연산 보다는 GPGPU 연산을 하는게 훨씬 빠르긴 하다. 하지만 Mobile 기기를 비롯한 실제 응용 환경에서는 GPU 연산을 하기 어렵기 때문에 CPU 기반의 병렬 연산도 당분간은 포기하기 어려울 것이다. Caffe나 Tensorflow 같은 오픈 소스 Deep Leaning Framework에서 CPU 버전과 GPU 버전이 공존할 수 밖에 없는 이유이기도 하다.

for-loop의 문제

Deep Learning과 같이 선형대수를 사용해야 하는 경우 수많은 계산을 for-loop에 의지해야 한다. 단순히 m x n matrix X에 대해서 각 인자들의 pow 값을 구하는 아래의 예와 같이 말이다. 대개는 두번째 예처럼 matrix를 vector로 변환해서 1차원 배열로 처리한다. BLAS 라이브러리들이 matrix를 다루는 방법이기도 하다.

for(i = 0; i < m; ++i) {
  for(j = 0; j < n; ++j) {
    Y[i][j] = pow(X[i][j], 2.0);
  }
}

for( i= 0; i < m*n; ++i) Y[i] = pow(X[i], 2.0);

이 글에서 다루려는 것은 multi-thread를 사용해서 위의 놈을 아래와 비슷하게 동작하도록  하려는 것이다. 물론 아래의 코드는 희망사항일 뿐이다. Open MP에서는 pragma directive를 사용해서 for가 parallel로 동작하도록 하더라.

parallel_for(i = 0; i < m*n; ++i) Y[i] = pow(X[i], 2.0);

아무튼, CPU core 수가 4개 라면 parallel_for가 최소한 4개의 thread를 사용해서 병렬 연산을 하도록 하려는 것이다.

사실, 해결 방법은 간단하다. m*n/(core 수 = thread 수) 만큼씩 배열을 쪼개서 계산을 하는 것이다. 이 경우 두 가지 방법을 생각해 볼 수 있는데 하나는 처음부터 쪼개서 thread를 할당하는 방법과 divide & conquer algorithm을 이용해서 쪼개면서 thread를 할당하는 방법이다.

CPU core 수

일단, c++11을 이용해 구현에 사용할 header 파일 들은 아래의 4개이다.

#include <thread>
#include <future>
#include <vector>
#include <functional>

CPU core 수는 아래와 같이 알아낼 수 있다.

const unsigned int HOST_NUM_THREADS = std::thread::hardware_concurrency();

배열을 쪼개서 thread에  균등 할당하기

실제 구현 방법은 여러가지가 있을 수 있겠으나, 여기서는 Core수만큼 Thread를 생성해서 최대 균등 할당량만큼씩 할당해 준다. 여분의 할당량이 있으면 main thread가 처리한다. 사실, c++11부터 도입된 lambda 함수를 과용하는 측면이 있다.

template<typename TF>
void parallel_for0(unsigned int begin, unsigned int end, const TF& func)
{
  auto length = end - begin;
  if(!length) return;

  auto f = [&func](unsigned int bs, unsigned int be) 
            { for(unsigned int i = bs; i < be; ++i) func(i); };

  unsigned int nthreads = HOST_NUM_THREADS;
  auto const blockSize = (end - begin) / nthreads;
  if(blockSize && (length % nthreads)) ++nthreads;
  std::vector<std::future void>> futures;
  unsigned int blockStart = begin;

  if(blockSize) {
    for(unsigned int i = 0; i < (nthreads - 1); ++i) {
      unsigned int blockEnd = blockStart + blockSize;
      futures.push_back(std::move(std::async(std::launch::async,
        [blockStart, blockEnd, &f]() { f(blockStart, blockEnd); })));
      blockStart = blockEnd;
    }
  }
  f(blockStart, end);
  for(auto & future : futures) future.wait();
}

Divide & Conquer Algorithms 적용

전체 배열 size를 반씩 나눠서 recursive하게 자신을 호출하면서 새로운 thread에 할당해 주고(divide), 각 thread가 자신의 할당량이 최대 균등 할당량보다 작아지면 실제 작업을 마치고 빠져나오게 된다(conquer).

template<typename TF>
void parallel_for(unsigned int begin, unsigned int end, const TF& func)
{
  auto length = end - begin;
  if(length <= 0) return;

  static auto const blockSize = length/HOST_NUM_THREADS;
  if(!blockSize || length <= blockSize) {
    for(unsigned int i = begin; i < end; ++i) func(i);
    return;
  }
 
  unsigned int mid = begin + length/2;
  auto future = std::async(std::launch::async, parallel<TF>, mid, end, func);
  parallel(begin, mid, func);
  future.get();
}

parallel_for 테스트

#include <iostream>
#include <chrono>
#include <ctime>

위의 헤더 파일이 필요하다.

std::vector<double> A(1000000, 1.0);
auto start = std::chrono::steady_clock::now();
//parallel_for0(0, m*k, [&](int i) { C[i] = ::pow(A[i], 2); });
parallel_for(0, m*k, [&](int i) { C[i] = ::pow(A[i], 2); });
auto end = std::chrono::steady_clock::now();
auto diff = end - start;
std::cout << "\nTime elapsed: "
          << std::chrono::duration<double, std::milli>(diff).count()
          << " ms" << "\n"; 

위의 두가지 버전의 parallel_for의 성능은 Divide & Conquer 방식이 쬐금 낫더라. 하지만 for-loop을 사용하는 것보다는 parallel_for를 사용하는 것이 당연히 빠르다. 물론 data size가 작으면 별 차이를 느끼지 못할 수도 있다.

Divide & Conquer를 이용한 parallel_sum 구현

위에서는 배열에 대해서만 언급했지만 c++11의 STL Container들로 위의 개념을 확장시킬 수 있을 것이다. Container에 대해서 iterator를 이용한 parallel_each와 parallel_sum을 생각해 볼 수 있는데, parallel_sum이 더 복잡하므로 parallel_sum만 다룬다. 두 가지 인터페이스가 있는데 하나는 iterator를 사용하는 방식이고, 하나는 container instance를 사용하는 방식이다. parallel_for에서는 int index를 사용했는데 여기서는 iterator pointer를 사용했다는 점만 다르고 Divide & Conquer logic은 동일하다.

template<typename TI, typename TR, typename TF>
TR parallel_sum(TI begin, TI end, TR init, const TF& func)
{
  auto length = end - begin;
  if(length <= 0) return init;
  static auto const blockSize = length/HOST_NUM_THREADS;
  TR result = 0;
  if(!blockSize || length <= blockSize) {
    for(TI it = begin; it < end; ++it) func(*it, result);
    return result;
  }
  TI mid = begin + length/2;
  auto future = std::async(std::launch::async, 
                           parallel_sum&<TI, TR, TF>, mid, end, init, func);
  TR sum = parallel_sum(begin, mid, init, func);
  return (sum + future.get());
}

template<typename TCon, typename TR, typename TF>
TR parallel_sum(TCon con, TR init, const TF& func)
{
  return parallel_sum(con.begin(), con.end(), init, func);
}

얼핏, parallel_for를 사용해서 for-loop에서 sum을 구하듯이 하면 되지 않겠느냐 생각할 수도 있겠지만 sum 자체가 shared variable이므로 parallel_for를 사용하려면 lock을 사용해야 한다. 이는 성능 저하를 의미하기 때문에 수학 계산에서는 lock-free 병렬 계산을 해야만 한다.

parallel_sum 사용

std::vector<double> A(1000000, 1.0);
double sum = 0;
//sum = parallel_sum(A.begin(), A.end(), sum, [](double item, double& r)
//        { r += 3*item + 2; });
sum = parallel_sum(A, sum, [](double item, double& r) { r += 3*item + 2; });

맺음말

흠, 사실 c++11만 해도 깊게 들어가면 배워야 할게 넘 많다. atomic 개념까지 들어가면 lock-free parallel 연산에 대한 도사가 될지도 모른다. 실제로 최근의 NVIDIA CUDA가 성능을 높이기 위해 이걸 파고 들고 있는 느낌이다. 언젠가는 모바일기기까지도 병렬 연산에 GPGPU를 사용하는 날이 올지 모른다.

아무튼, 병렬 계산에 관한  한 GPU를 사용할 수 있으면 GPU를 사용하는 것이 젤로 좋고, 차선책으로써 multi-core CPU를 사용하면 좀 낫다는 게 이 글의 요지다. 물론 데이터 량이나 계산 량이 많을 경우의 얘기다. 참고로, GPU와 CPU 연산을 함에 있어서 배열 size가 1만개 정도에서는 CPU와 GPU간의 성능차이가 별로 나지 않는다. 더구나 c++11의 random number generator와 cuRand를 비교하면 난수 갯수가 1만개 이내 일때는 CPU가 훨씬 빠르더라. 그런데 갯수가 1백만개를 넘어가면 GPU가 훨씬 빠르다.

multi-thread를 사용함에 있어서 CPU core 수와 같거나 조금 많은 정도가 최적의 성능을 준다. Divide & Conquer 방식에서 할당량(blockSize)을 줄이면 thread 수가 늘어나게 되는데 성능이 저하된다.


참고

구 버전의 SyntaxHighlighter를 사용했었는데 구글 site 들이 https 접속 방식으로 바뀌면서 블로그 Template의 http 링크들이 모두 무용지물이 됐다는 걸 알았다. 이 참에 다시 새 버전으로 바꾸면서 google drive에 Javascript를 올려 놓으면 된다는 글을 보게 돼서 신 버전으로 다시 회귀했다.