前缀和的并行化(Openmp)

Question

我有两个向量,a [n]和b [n​​],其中n是一个大数.

a[0] = b[0];

for (i = 1; i < size; i++) {
        a[i] = a[i-1] + b[i];
}

使用此代码,我们尝试实现a [i]包含b []中所有数字的总和,直到b [i].我需要使用openmp并行化这个循环.

主要的问题是a [i]取决于[i-1],因此我想到的唯一直接方法是等待每个[i-1]数字准备就绪,这需要花费大量时间并没有任何意义.openmp中有没有解决这个问题的方法？

Answer 1

你是18世纪的卡尔弗里德里希高斯,你的小学老师决定用一个需要很多或平凡的重复算术的家庭作业来惩罚这个班级.在前一周,你的老师告诉你要加上前100个计数数字,因为你很聪明,你想出了一个快速的解决方案.你的老师不喜欢这样,所以他想出了一个他认为无法优化的新问题.用你自己的表示法,你可以像这样重写问题

a[0] = b[0];   
for (int i = 1; i < size; i++) a[i] = a[i-1] + b[i];

然后你意识到了

a0  = b[0]
a1  = (b[0]) + b[1];
a2  = ((b[0]) + b[1]) + b[2]
a_n = b[0] + b[1] + b[2] + ... b[n]

再次使用您的符号,您将问题重写为

int sum = 0;
for (int i = 0; i < size; i++) sum += b[i], a[i] = sum;

如何优化这个？首先你定义

int sum(n0, n) { 
    int sum = 0;
    for (int i = n0; i < n; i++) sum += b[i], a[i] = sum;
    return sum;
}

然后你意识到了

a_n+1   = sum(0, n) + sum(n, n+1)
a_n+2   = sum(0, n) + sum(n, n+2)
a_n+m   = sum(0, n) + sum(n, n+m)
a_n+m+k = sum(0, n) + sum(n, n+m) + sum(n+m, n+m+k)

所以现在你知道该怎么做了.找t同学.让每个人都在数字的子集上工作.为了保持简单,你选择size100和四个同学,t0, t1, t2, t3然后每个人

 t0               t1                t2              t3
 s0 = sum(0,25)   s1 = sum(25,50)   s2 = sum(50,75) s3 = sum(75,100)

同时.然后定义

fix(int n0, int n, int offset) {
    for(int i=n0; i<n; i++) a[i] += offset
}

然后每个同学再次回到他们的子集,就像这样

t0             t1               t2                  t3 
fix(0, 25, 0)  fix(25, 50, s0)  fix(50, 75, s0+s1)  fix(75, 100, s0+s1+s2)

你意识到,t同学们花大约相同的K时间做算术,你可以在2*K*size/t几秒钟内完成工作,而一个人需要K*size几秒钟.很明显,你需要至少两个同学才能收支平衡.因此,对于四个同学,他们应该在一半时间内完成一个同学.

现在,您可以用自己的符号编写算法

int *suma;  // array of partial results from each classmate
#pragma omp parallel
{
    int ithread = omp_get_thread_num();    //label of classmate
    int nthreads = omp_get_num_threads();  //number of classmates
    #pragma omp single
    suma = malloc(sizeof *suma * (nthreads+1)), suma[0] = 0;

    //now have each classmate calculate their partial result s = sum(n0, n)
    int s = 0;
    #pragma omp for schedule(static) nowait
    for (int i=0; i<size; i++) s += b[i], a[i] = sum;
    suma[ithread+1] = s;

    //now wait for each classmate to finish
    #pragma omp barrier

    // now each classmate sums each of the previous classmates results
    int offset = 0;
    for(int i=0; i<(ithread+1); i++) offset += suma[i];

    //now each classmates corrects their result 
    #pragma omp for schedule(static)
    for (int i=0; i<size; i++) a[i] += offset;
}
free(suma)

你意识到你可以优化每个同学必须添加前一个同学的结果的部分,但因为size >> t你不认为这是值得的.

您的解决方案并不像添加计数数字的解决方案那么快,但是您的老师并不满意他的几个学生比其他学生更早完成.所以现在他决定一个学生必须b慢慢地把这个数组读到课堂上,当你报告结果时,a它也必须慢慢地完成.你称之为读/写带宽限制.这严重限制了算法的有效性.你现在要做什么？

你唯一能想到的就是让多个同学同时阅读和记录不同的数字子集.