并行更新1000000个项目的数组

Question

这是去年考试中提出的一个问题.

考虑以下C代码片段:

int i, array[1000000];
array[0] = 0;
for (i = 1; i < 1000000; i++)
array[i] = array[i-1] + 3;

我们可以简单地并行运行for循环中的1,000,000个数组更新语句吗？如果没有,请更改update语句,使其可以并行运行并仍然生成相同的最终数据内容.

据我所知,不可能在for循环中并行运行1,000,000个数组更新语句.我想到的唯一方法就是使用不是平行的递归,并使用1000000个线程,这不是一个好主意.

那么是否有另一种方法可以与非常少的更新语句并行完成此操作？我们可以使用openMPI或openCL

编辑:这不是一个家庭作业问题,但我认为它是作为一些学校的家庭作业.这是过去的试卷.我在这里上传了它

Answer 1

问题是你不能并行化这个循环,也不能只用2个线程,因为每次迭代都取决于前面的.

你的算法产生:

array[0] = 0;
array[1] = 3;
array[2] = 6;
...

因此,您可以以每次迭代不依赖于前一次的方式编写update语句:

int i, array[1000000];
array[0] = 0;
for (i = 1; i < 1000000; i++)
    array[i] = 3*i;

通过这种方式,您已经删除了数据依赖性,并且可以轻松地并行化循环(例如,使用OpenMP或MPI).