我正在尝试在一段时间内进行并行处理,结果如下:
while(!End){
for(...;...;...) // the parallel for
...
// serial code
}
for循环是while循环中唯一平行的部分。如果我这样做,我会有很多开销:
cycles = 0;
while(!End){ // 1k Million iterations aprox
#pragma omp parallel for
for(i=0;i<N;i++) // the parallel for with 256 iteration aprox
if(time[i] == cycles){
if (wbusy[i]){
wbusy[i] = 0;
wfinished[i] = 1;
}
}
// serial code
++cycles;
}
for循环的每次迭代都是相互独立的。
串行代码和并行代码之间存在依赖关系。
因此,通常不必太担心将并行区域放入循环中,因为现代openmp实现在使用线程团队等方面非常高效,只要循环中有很多工作,就可以了。但在这里,外循环计数为~1e9,内循环计数为~256,每次迭代所做的工作很少,开销可能与所做的工作量相当或更糟,性能也会受到影响。
所以这两者之间会有一个明显的区别:
cycles = 0;
while(!End){ // 1k Million iterations aprox
#pragma omp parallel for
for(i=0;i<N;i++) // the parallel for with 256 iteration aprox
if(time[i] == cycles){
if (wbusy[i]){
wbusy[i] = 0;
wfinished[i] = 1;
}
}
// serial code
++cycles;
}
这个:
cycles = 0;
#pragma omp parallel
while(!End){ // 1k Million iterations aprox
#pragma omp for
for(i=0;i<N;i++) // the parallel for with 256 iteration aprox
if(time[i] == cycles){
if (wbusy[i]){
wbusy[i] = 0;
wfinished[i] = 1;
}
}
// serial code
#pragma omp single
{
++cycles;
}
}
但实际上,不幸的是,每次迭代在时间阵列上的扫描既(a)速度慢,又(b)没有足够的工作来保持多个内核的繁忙——这是内存密集型的。如果线程数量超过两个,即使没有开销,也会因为内存争用而导致性能比串行差。诚然,你在这里发布的只是一个例子,而不是你真正的代码,但你为什么不对时间数组进行预处理,这样你就可以检查下一个任务何时可以更新:
#include <stdio.h>
#include <stdlib.h>
struct tasktime_t {
long int time;
int task;
};
int stime_compare(const void *a, const void *b) {
return ((struct tasktime_t *)a)->time - ((struct tasktime_t *)b)->time;
}
int main(int argc, char **argv) {
const int n=256;
const long int niters = 100000000l;
long int time[n];
int wbusy[n];
int wfinished[n];
for (int i=0; i<n; i++) {
time[i] = rand() % niters;
wbusy[i] = 1;
wfinished[i] = 0;
}
struct tasktime_t stimes[n];
for (int i=0; i<n; i++) {
stimes[i].time = time[i];
stimes[i].task = i;
}
qsort(stimes, n, sizeof(struct tasktime_t), stime_compare);
long int cycles = 0;
int next = 0;
while(cycles < niters){ // 1k Million iterations aprox
while ( (next < n) && (stimes[next].time == cycles) ) {
int i = stimes[next].task;
if (wbusy[i]){
wbusy[i] = 0;
wfinished[i] = 1;
}
next++;
}
++cycles;
}
return 0;
}
这比串行版本的扫描方法快约5倍(比OpenMP版本快得多)。即使您不断更新串行代码中的time/wbusy/wfinished数组,也可以使用优先级队列跟踪它们的完成时间,每次更新需要O(ln(N))时间,而不是扫描每次迭代需要O(N)时间。