使用 Open MP 并行化前缀和

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] 中所有数字的总和。我需要使用 Open MP 并行化这个循环。

主要问题是a[i]依赖于a[i-1]，所以我想到的唯一直接的方法是等待每个a[i-1]数字准备好，这需要很多时间时间并没有任何意义。 Open MP 有没有办法解决这个问题？

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

同学。让每个人处理数字的一个子集。为了简单起见，您选择

size

为 100 和四位同学

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

时也必须慢慢地完成。您将其称为读/写带宽限制。 这严重限制了你的算法的有效性。你现在要做什么？

你唯一能想到的就是让多个同学同时读取并记录不同的数字子集到全班。