CodeZine(コードジン)

特集ページ一覧

PPLの並列アルゴリズム

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2014/02/18 14:00
目次

parallel_for

for ( T i = first; i < last; i += step ) {
  func(i);
}

 という、典型的なループにおいて、ループ内の処理func(i)を複数個同時にやってしまうのがparallel_for(first, last, step, func)です(stepを省略すると1とみなされます)。素数探しはこんな実装。

list-8
void prime_parallel_for(unsigned int limit, vector<unsigned int>& primes) {
    critical_section cs;
    parallel_for(0U, limit, [&primes, &cs](unsigned int i) {
        unsigned int n = nth_prime_candidate(i);
        if (is_prime(n)) {
            critical_section::scoped_lock guard(cs);
            primes.push_back(n);
        }
    });
}

parallel_for_each

 標準C++ライブラリ:<algorithm>に定義されたstd::for_each()の並列版がparallel_for_each()です。"コンテナの各要素に対して関数オブジェクトを適用"を並列に(複数個同時に)行ってくれます。

list-9
void prime_parallel_for_each(unsigned int limit, vector<unsigned int>& primes) {
    vector<unsigned int> candidates(limit);

    iota(begin(candidates), end(candidates), 0U);
    parallel_transform(begin(candidates), end(candidates), begin(candidates),[](unsigned int n) { return nth_prime_candidate(n);});
    critical_section cs;
    parallel_for_each(begin(candidates), end(candidates), 
                        [&primes,&cs](unsigned int n) { 
                            if ( is_prime(n) ) {
                                critical_section::scoped_lock guard(cs); 
                                primes.push_back(n);
                            }
                        });
}

 このコードでは素数候補を詰め込んだコンテナ:candidatesを作るのにstd::transform()の並列版: parallel_transform()を使っています。

 parallel_invoke(),parallel_for(),parallel_for_each()を使った3つの素数探しの実行時間を、並列アルゴリズムを使わない版と比べてみました。

 スピードはどれも大差なく、並列アルゴリズムを使わない版よりおよそ4倍速くなっています。CPUはi7-2600K、コアは4つだけどhyper-threadingを有効にしているので同時に8つのスレッドが動きます。なので8倍速くなるのを期待していたのですが……コアがいくつあろうがメモリ・バスは一本しかないのだし、スレッド・コンテキストの切り替えにも相応のオーバーヘッドを伴いますから、まぁこんなもんでしょう。アルゴリズムを一切変更せずに4倍速くなったのだから上等と言えるでしょうね。

 ところでこれら並列アルゴリズムによる素数探し、見つけた素数はvector<unsigned int>に蓄えられていますが、昇順に並んではいません。PPLが用意してくれているソート関数をいくつか紹介しておきましょう。

  • parallel_sort(first, last, comp):std::sort()の並列版。2つのイテレータ:firstとlastに挟まれた半開区間[first,last)を(比較オブジェクトcompの結果に基づいて)ソートします。
  • parallel_buffered_sort(first, last, comp):作業領域を内部的に確保することでより高速化したparallel_sort。
  • parallel_radixsort(first, last, key):ソート対象がunsigned intに限定されるものの、とにかく高速。要素型がunsigned intであればkeyは不要ですが、それ以外であった場合は各要素からunsigned int型のソート・キーを作る関数オブジェクト:keyを与えます。

 上記3種の並列ソートとstd::sort()の処理時間を比べてみました。

list-10
#undef NDEBUG

#include <iostream>
#include <numeric>
#include <vector>
#include <chrono>
#include <cassert>

#include <ppl.h>

using namespace std;
using namespace concurrency;

template<typename Function>
inline const std::chrono::milliseconds measure_exec(const Function& fun) {
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
    fun();
    return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start);
}

int main() {
    const unsigned int N = 5000000;    
    vector<unsigned int> src(N);

    { // setup initial data to be sorted
    iota(begin(src), end(src), 0U);
    random_shuffle(begin(src), end(src));
    }

    {
        vector<unsigned int> c(src);
        cout << "----- sort" << endl;
        auto dur = measure_exec([&]() {
            sort(begin(c), end(c));
        });
        assert(is_sorted(begin(c), end(c)));
        cout << dur.count() << "[ms]" << endl;
    }

    {
        vector<unsigned int> c(src);
        cout << "----- parallel_sort" << endl;
        auto dur = measure_exec([&]() {
            parallel_sort(begin(c), end(c));
        });
        assert(is_sorted(begin(c), end(c)));
        cout << dur.count() << "[ms]" << endl;
    }

    {
        vector<unsigned int> c(src);
        cout << "----- parallel_buffered_sort" << endl;
        auto dur = measure_exec([&]() {
            parallel_buffered_sort(begin(c), end(c));
        });
        assert(is_sorted(begin(c), end(c)));
        cout << dur.count() << "[ms]" << endl;
    }

    {
        vector<unsigned int> c(src);
        cout << "----- parallel_radixsort" << endl;
        auto dur = measure_exec([&]() {
            parallel_radixsort(begin(c), end(c));
        });
        assert(is_sorted(begin(c), end(c)));
        cout << dur.count() << "[ms]" << endl;

        ref(c);
    }
}

 実行結果は……

 ……ほほぉ、std::sort()はかなり速いソートなんですけど、並列ソートはさらにその4倍以上のスピード、特にparallel_radixsort()のスピードが際立っています。大量のデータをソート、あるいは頻繁にソートしなければならないアプリケーションには(コア数に依存するとはいうものの)かなり役に立ちそうです。

  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • επιστημη(エピステーメー)

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"り わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5