PPLの並列アルゴリズム

　PPL（Parallel Pattern Library）をご存じでしょうか。Visual C++ 10.0（Visual Studio 2010）以降で提供されているマイクロソフト製の並列プログラミングをサポートするライブラリです。PPLの並列アルゴリズムで素数探しプログラムのパフォーマンスを向上させるお話。

素数探し

　とある正整数nがあって、2以上n未満のいかなる数もnを割り切ることができないとき、nは素数です。このルールに忠実に従うなら、nが素数であるか否かを判定する関数: is_prime()は以下のように定義できます。

list-1

bool is_prime(unsigned int n) {
  if ( n < 2U ) return false; // 0と1は素数じゃない
  // 2以上n未満の数 i が...
  for ( unsigned int i = 2U; i < n; ++i ) {
    // nを割り切るなら、nは素数じゃない
    if ( n % i == 0 ) return false;
  }
  return true;
}

　コレを使って5より大きな素数をすべて見つけるコードは:

list-2

// 2,3,5で割れない数は30の倍数+1,7,11...
unsigned int nth_prime_candidate(unsigned int x, unsigned int y) {
  static std::array<unsigned int,8> bias = { 1, 7, 11, 13, 17, 19, 23, 29 };
  return 30*x + bias[y];
}

inline unsigned int nth_prime_candidate(unsigned int n) {
  return nth_prime_candidate(n/8, n%8);
}

// 素数探し：見つけた素数はprimesに追加する
void prime_sequential(unsigned int limit, std::vector<unsigned int>& primes) {
    for (unsigned int i = 0; i < limit; ++i) {
        unsigned int n = nth_prime_candidate(i);
        if ( is_prime(n) ) primes.push_back(n);
    }
}

　処理時間を計測し、表示しましょうか。

list-3

inline std::chrono::milliseconds 
measure_exec(const std::function<void(unsigned int, std::vector<unsigned int>&)>& fun, 
             unsigned int limit, 
             std::vector<unsigned int>& result) {
  std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
  fun(limit, result);
  return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start);
}

int main() {
  const unsigned int LIMIT = 40000;
  vector<unsigned int> primes;
  vector<unsigned int>::size_type count;
  std::chrono::milliseconds durration;

  primes.clear();
  durration = measure_exec(&prime_sequential, LIMIT, primes);
  count = primes.size();
  cout << count << " primes found." << endl;
  cout << "----- sequential" << endl;
  cout << durration.count() << "[ms]" << endl;
}

　僕の愛機（CPU：i7-2600K）では、13845個の素数を見つけるのに5799[ms]かかりました。

PPLの並列アルゴリズム

　PPLでは"同時に（互いに干渉せずに）実行できる処理単位"を、タスク（task）と称しています。PPLの中ではCPUの力量に見合う数のスレッドを起こし、それらスレッドにユーザが定義した（複数の）タスクを投げ込んで処理を行います。そのからくりのおかげで、ユーザは明示的にスレッドを管理する必要がありません。加えて今回紹介する"parallel_"から始まる各種並列アルゴリズムはタスクの管理もユーザには任せず、「与えられた複数の処理を並列に実行し、全処理が完了するまで待つ（fork-join）」一連のパターンが関数内に封じ込められています。

　それでは、PPLが提供する並列アルゴリズムを1つずつ紹介しつつ、素数探しを高速化してみましょうか。