前缀和的并行化 (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]依赖于a[i-1]，所以我想到的唯一直接的方法就是等待每个a[i-1]数准备好，这花很多时间，没有意义。 openmp有解决这个问题的方法吗？

Answer 1

您是 18 世纪的 Carl Friedrich Gauss，您的小学老师决定用需要大量或重复算术的家庭作业问题来惩罚 class。上周你的老师让你把前 100 个数加起来，因为你很聪明，所以你算了 with a quick solution。你的老师不喜欢这样，所以他提出了一个他认为无法优化的新问题。在你自己的符号中，你可以这样重写问题

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 class 伙伴。让每个人处理数字的一个子集。为简单起见，您选择 size 为 100 和四个 class 伙伴 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
}

然后每个 class 伙伴再次像这样

同时返回他们的子集

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

你意识到 t class 队友花费大约相同的 K 秒来做算术，你可以在 2*K*size/t 秒内完成这项工作，而一个人会花费 K*size 秒。很明显，您至少需要两个 class 伙伴才能实现收支平衡。因此，如果有四个 class 队友，他们应该用一个 class 队友的一半时间完成比赛。

现在你用自己的符号写下你的算法

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)

你意识到你可以优化每个 classmate 必须添加前一个 classmate 的结果的部分，但是因为 size >> t 你认为它不值得努力。

您的解决方案远不如您添加计数的解决方案快，但是您的老师并不高兴他的几个学生比其他学生早得多完成。所以现在他决定一个学生必须慢慢地读取 b 数组到 class 并且当你报告结果 a 时也必须慢慢地完成。您称之为 read/write 带宽限制。 This severely limits the effectiveness of your algorithm.你现在打算做什么？

The only thing you can think of is to get multiple classmates to read and record different subsets of the numbers to the class at the same time.

前缀和的并行化 (Openmp)

Parallelization of a prefix sum (Openmp)

c

parallel-processing

loops

openmp