c - 如何在C中并行填充数组

Question

我需要一种算法，它可以在 log(n) 时间内并行填充具有相同值的数组（大小为 n）。这意味着天真的解决方案for(i=0;i<=n-1;i++) T[i] = 10是不够的，因为它需要O(n)时间，我需要一些可以花费的东西O(log(n))。我提到这将在 PARALLEL 中完成，这一点非常重要。我在考虑依赖，但我似乎无法弄清楚。

Answer 1

像这个简单的循环一样，可以有多种方式让自己感到困惑

for (i = 0; i <= (SIZE / 2); i++) {
    arr[i]=10;
    arr[SIZE-(i+1)]=10;
}

这只是让你觉得它是 o(n/2) 但实际上你必须将值n时间写入内存。因此，无论您采用哪种方式，您最终都会执行分配操作n时间。

Answer 2

我将忽略其他人已经解决的将其称为“O（log n）”的问题，而是想概述一个解决方案。如果您不熟悉openMP，它是一个用于共享内存计算的并行框架。

#pragma omp parallel for shared(T)
for(int i = 0; i < n; i++) T[i] = 10;

如果你有 (n / log(n)) 处理器，那么你仍然会做 O(n) 工作，但每个处理器只需要做 O(n / (n / log(n))) 工作，或者 O （日志 n）。这大概就是你想要的。

这对这个问题的可行性意味着什么？

n     #num procs
4     2
16    4
256   32
65536 4096

我们可以得出结论，解决这个问题可能只对包含至少 16 个元素和最多 256 个元素的数组有意义（如果这个问题对您如此重要，您可以将其推高到 512，甚至 1024。）

迁移到分布式机器是另一回事——收集数组的通信成本将大大超过初始化中的并行性，因为所需的节点数量以 O(n / log(n)) 的速度增长。您需要在创建数组的节点上进行所有计算。

Answer 3

如果您使用 n 个处理器运行 n 个线程，那么它O(1)* n = O(n)总共仍然是处理器（并且性能会很糟糕）。

如果您运行线程t（t=n/factor但关键是它仍然是O(n)。

O(logn)仅当您可以基于某些条件（例如，排序数组的二进制搜索）跳过某些操作时，才能完成某些操作。为了初始化数组中的 n 个元素，您必须访问所有 n 个元素。只是你想要的是不可能的。