C++ OpenMP Parallel For Loop - std :: vectorに代わるもの

Question

このスレッドに基づいて、 std :: vectorをパラレルforループで共有するのに適したデータ構造はOpenMP and STL vectorです。主な特徴はスピードです。ループ中にベクトルのサイズを変更する必要があります。

Answer 1

あなたがリンクしている質問は、「STLベクタコンテナは、複数のスレッドが単一のコンテナに書き込む状況ではスレッドセーフではありません」ということです。 std::vectorが保持する基になる配列の再割り当てを引き起こす可能性のあるメソッドを呼び出すと、正しく記述されているように、これは真です。 push_back()、pop_back()およびinsert()は、これらの危険な方法の例です。

スレッドセーフの再割り当てが必要な場合は、ライブラリintel thread building blockにはconcurrent vector containersがあります。単一要素のプログラムでtbb :: concurrent_vectorを使うべきではありません。なぜなら、ランダムな要素にアクセスするのにかかる時間は、std :: vectorが同じ（O（1））を実行するのにかかる時間よりも長いからです。しかし、同時ベクトル呼び出しは、再配置が発生した場合でも、スレッドセーフな方法でpush_back(),pop_back(),insert()となります。

EDIT 1：スライド46とthe following Intel presentationの47はTBBを使用して、同時再配分の具体例を与える:: concurrent_vector

EDIT 2：あなたはインテルトレッドビルディングブロックを（使用して起動した場合ちなみに、それがオープンソースでありますほとんどのコンパイラで動作しますが、openmpよりC++/C++ 11の機能がはるかに良く統合されているので、openmpを使用してparallel_forを作成する必要はありません。Hereはtbbを使用するparallel_forの良い例です。

Answer 2

私はあなたがほとんどOpenMPでstd::vectorを使うことができ、まだ良い性能を持っていると思います。たとえば、次のコードはstd::vectorsを並列に埋め込み、最後にそれらを結合します。メインのループ/フィル機能がボトルネックになっている限り、これは一般的にうまく機能し、スレッドセーフでなければなりません。

std::vector<int> vec; 
#pragma omp parallel 
{ 
    std::vector<int> vec_private; 
    #pragma omp for nowait //fill vec_private in parallel 
    for(int i=0; i<100; i++) { 
     vec_private.push_back(i); 
    } 
    #pragma omp critical 
    vec.insert(vec.end(), vec_private.begin(), vec_private.end()); 
} 

編集：

のOpenMP 4.0は#pragma omp declare reductionを使用して、ユーザー定義の削減を可能にします。 私がこれまでに示してきたがために、ベクトルを満たさない：上記のコードは、編集

#pragma omp declare reduction (merge : std::vector<int> : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) 

std::vector<int> vec; 
#pragma omp parallel for reduction(merge: vec) 
for(int i=0; i<100; i++) vec.push_back(i); 

にして簡略化することができます。注文事項は、これは、この

std::vector<int> vec; 
#pragma omp parallel 
{ 
    std::vector<int> vec_private; 
    #pragma omp for nowait schedule(static) 
    for(int i=0; i<N; i++) { 
     vec_private.push_back(i); 
    } 
    #pragma omp for schedule(static) ordered 
    for(int i=0; i<omp_get_num_threads(); i++) { 
     #pragma omp ordered 
     vec.insert(vec.end(), vec_private.begin(), vec_private.end()); 
    } 
} 

のように行うことができればこれは、各スレッドのためのstd ::ベクトルを保存して、並列領域のシリアル外でそれらをマージ避けることができます。私はこの "トリック"について学んだhere。 私はユーザー定義の削減のためにこれを（または可能であれば）行う方法がわかりません。。これをユーザー定義の削減で行うことはできません。

私は、この質問からわかったクリティカルセクションが不要であることを知りましたparallel-cumulative-prefix-sums-in-openmp-communicating-values-between-thread。このメソッドは正しい順序も取得します

std::vector<int> vec; 
size_t *prefix; 
#pragma omp parallel 
{ 
    int ithread = omp_get_thread_num(); 
    int nthreads = omp_get_num_threads(); 
    #pragma omp single 
    { 
     prefix = new size_t[nthreads+1]; 
     prefix[0] = 0; 
    } 
    std::vector<int> vec_private; 
    #pragma omp for schedule(static) nowait 
    for(int i=0; i<100; i++) { 
     vec_private.push_back(i); 
    } 
    prefix[ithread+1] = vec_private.size(); 
    #pragma omp barrier 
    #pragma omp single 
    { 
     for(int i=1; i<(nthreads+1); i++) prefix[i] += prefix[i-1]; 
     vec.resize(vec.size() + prefix[nthreads]); 
    } 
    std::copy(vec_private.begin(), vec_private.end(), vec.begin() + prefix[ithread]); 
} 
delete[] prefix;