c - 并行更新包含 1000000 个项目的数组

Question

这是往年考试的题目。

Consider the following fragment of C code:

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

Can we simply run 1,000,000 of the array update statement in the for loop in parallel? If not, change the update statement so that it can run in parallel and still produce the same final contents of the array.

我知道不可能简单地在 for 循环中并行运行 1,000,000 条数组更新语句。我想到的唯一方法是使用非并行的递归，以及使用 1000000 个线程，这不是一个好主意。

那么有没有另一种方法可以用很少的更新语句并行完成这项工作？我们可以使用 openMPI 或 openCL

编辑:这不是家庭作业问题，但我认为它在某些学校被作为家庭作业给出。这是来自过去的试卷。我上传了here

Answer 1

问题是你不能并行化那个循环，也不能只有 2 个线程，因为每次迭代都依赖于前一次迭代。

您的算法产生:

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

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

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

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