OpenMP |并行化一个循环与依赖迭代

Question

我想并行化一个编码函数，我尝试在for处添加一个简单的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; 
} 

有没有一种方法，使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位，这对于并行开销的好处太小了。如果这是你代码中的热门部分，你必须找到它来应用并行化。