OpenMP |依存する繰り返しを含むループを並列化する

Question

エンコード関数を並列化しようとしていますが、単純にpragmaを追加しようとしましたが、結果は間違っていました。私は反復が（code変数によって）依存していると考えていたので、それらを直接並列化することはできません。

int encodePrimeFactorization(int number){ 
    int code = 0; 
    for (int i=PF_NUMBER-1; i>=0 ; i--){ 
     code = code * 2; 
     int f = prime_factors[i]; 
     if (number % f == 0){ 
     code = code + 1; 
     } 
    } 
    return code; 
} 

を反復ごとに独立させる方法はありますか？

Answer 1

はい。あなたは、アルゴリズムでこの方法を見れば少なくとも私にとっては、それはそれについて考える方が簡単です：

int code = 0; 
for (int i=PF_NUMBER-1; i>=0 ; i--) { 
    code = code << 1; 
    int f = prime_factors[i]; 
    if (number % f == 0){ 
    // The last bit of code is never set here, 
    // because it has been just shifted to the left 
    code = code | 1; 
    } 
} 

今、あなたが設定しながら、既にセットビットをシフトすることができます

int code = 0; 
for (int i=PF_NUMBER-1; i>=0 ; i--) { 
    int f = prime_factors[i]; 
    if (number % f == 0){ 
    code = code | (1 << i); 
    } 
} 

今ではなりました些細な削減。設定中に既にセットビットをシフトすることができます：

int code = 0; 
#pragma omp parallel for reduction(|,code) 
for (int i=PF_NUMBER-1; i>=0 ; i--) { 
    int f = prime_factors[i]; 
    if (number % f == 0){ 
    code |= (1 << i); 
    } 
} 

つまり、パフォーマンスは向上しません。これは31ビットまでしか動作しませんが、これは並列化のオーバーヘッドの恩恵を受けるにはあまり働きません。これがコード内のホットな部分である場合は、その周辺で並列処理を適用する必要があります。