OpenMPを使用したタスクベースの並列処理の適用

Question

OpenMPを使用して並列化しようとしている次のコードがあります。

int ncip(int dim, double R){ 
int n, r = (int)floor(R); 

if (dim == 1) return 1 + 2*r; 

#pragma omp task shared(n, dim) 
n = ncip(dim-1, R); // last coord 0 

for(int i=1; i<=r; ++i){ 
    #pragma omp task shared(n, dim) 
    n += 2*ncip(dim-1, sqrt(R*R - i*i)); // last coord +- i 

} 
return n; 
} 

再帰呼び出しのためにタスクベースの並列処理を適用する必要がありますが、私の計算ではスピードアップが表示されません。私は間違って何をしていますか？この計算のスピードアップに役立つ提案はありますか？

Answer 1

並列性は無料ではありません。しかし、無意識のうちに、単純なプラグマは、たとえば次のようになります。 #pragma omp taskでは、スレッドの作成と同期、タスクの割り当てやキューイングなどのロジック全体が隠されているため、かなりのコストがかかります。計算の強さ、マルチスレッド自体の費用、 （マルチスレッディングの副作用、偽の共有など）、あなたは正（> 1）のスピードアップを観察します。

また、スレッド数は常に制限されています。スレッドごとに十分なワークロードを作成したら、作業共有構造を追加してコードを強化しないでください。スレッドは2つの別々の命令フローに魔法のように分割できません。つまり、すでに一番上のループがあり、使用可能なすべてのスレッドをビジー状態に保つのに十分な反復回数があれば、ネストされた並列処理を抽出しようとするものは何も得られません。

部分的な結果を記憶したり、再帰を完全に取り除くなど、他にもいくつかの手法を利用できるのでなければ、最上位の並列ループを1つだけ使用し、共有節へのスレッドセーフなアクセスを保証する節変数：

#pragma omp parallel for reduction(+:n) 
for (int i = 1; i <= r; ++i) 
{ 
    n = n + (2 * ncip(dim-1, sqrt(R*R - i*i))); 
} 

、その後、単純なシーケンス機能：

int ncip(int dim, double R) 
{ 
    int n, r = (int)floor(R); 

    if (dim == 1) 
    { 
     return 1 + 2*r; 
    } 

    n = ncip(dim-1, R); 

    for (int i = 1; i <= r; ++i) 
    { 
     n = n + (2 * ncip(dim-1, sqrt(R*R - i*i))); 
    } 

    return n; 
} 

DEMO