前缀和的并行化（Openmp）

我有两个向量，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世纪的卡尔弗里德里希高斯，你的小学老师决定用一个需要大量或平凡的重复算术的家庭作业来惩罚这个class级。 在前一周，你的老师告诉你加上前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) 

所以现在你知道该怎么做了。 找到同学。 让每个人都在数字的子集上工作。 为了保持简单，你选择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 

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

 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 

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

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

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