一个前缀和的并行化 (Openmp)

Question

一个前缀和的并行化 (Openmp)

5

我有两个向量，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[]中第i个元素之前的所有数字的总和。我需要使用openmp并行化此循环。

主要问题是a[i]依赖于a[i-1]，因此直接等待每个a[i-1]数字准备好是唯一想到的方式，但这需要很长时间，而且毫无意义。在openmp中是否有解决此问题的方法？

- cppstudy

这是作业吗？ - villintehaspam

为什么你需要并行化呢？在我看来，这似乎是一个顺序问题。如果你不仅仅是针对a向量进行操作，而是对多个向量进行操作，那么它可以被并行化。 - Alex

5

主要问题在于a[i]依赖于a[i-1]。实际上不是这样。a[i]等于b[0]到b[i]的和。您已经草拟了一种串行计算的方式，但串行计算并不是计算的基本特征。请搜索“并行前缀和”来了解更多信息。 - High Performance Mark

@villintehaspam 不，它不是，但我不明白这会如何改变问题所在。 - cppstudy

@Alex，我需要并行处理来尝试减少计算时间，因为n是一个非常大的数字。 - cppstudy

@HighPerformanceMark 感谢您的回答，我发现您的指导很有用。看起来我需要重建算法，以便可以并行处理它。 - cppstudy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Z boson · Accepted Answer

你是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)

你意识到，如果有一个和你一样需要 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 时也必须慢慢进行。你称之为读/写带宽受限。这严重限制了你的算法的效果。你现在该怎么办？你唯一能想到的就是让多个同学同时读取和记录不同子集的数字给班级听。