3

我有一个从 1 迭代到 N 的循环，并随着时间的推移取模和。但是 N 非常大，所以我想知道是否有办法通过利用多线程来修改它。

给出示例程序

for (long long i = 1; i < N; ++i)
   total = (total + f(i)) % modulus;

f(i) 在我的例子中不是一个实际的函数，而是一个很长的表达式，会在这里占用空间。把它放在那里是为了说明目的。

4

5 回答 5

8

是的，试试这个：

double total=0;
#pragma omp parallel for reduction(+:total)
for (long long i = 1; i < N; ++i)
  total = (total + f(i)) % modulus;

编译：

g++ -fopenmp your_program.c

就是这么简单！不需要标题。该#pragma行自动启动了几个线程，平均划分循环的迭代，然后在循环之后重新组合所有内容。但请注意，您必须事先知道迭代次数。

此代码使用OpenMP，它提供了非常适合您的情况的易于使用的并行性。OpenMP 甚至内置在 GCC 和MSVC 编译器中。

此页面显示了一些其他可能的归约操作。

如果你需要嵌套的 for 循环，你可以写

double total=0;
#pragma omp parallel for reduction(+:total)
for (long long i = 1; i < N; ++i)
for (long long j = 1; j < N; ++j)
  total = (total + f(i)*j) % modulus;

并且外部循环将被并行化，每个线程运行自己的内部循环副本。

但是你也可以使用collapse指令：

#pragma omp parallel for reduction(+:total) collapse(2)

然后两个循环的迭代将自动划分。

如果每个线程都需要在循环之前定义的自己的变量副本，请使用以下private命令：

double total=0, cheese=4;
#pragma omp parallel for reduction(+:total) private(cheese)
for (long long i = 1; i < N; ++i)
  total = (total + f(i)) % modulus;

请注意，您不需要使用private(total)，因为这是由reduction.

于 2013-06-14T16:40:56.867 回答
2

假设 f(i) 是独立的，但运行时间大致相同，您可以自己创建 4 个线程，并让每个线程相加总和的 1/4，然后将总和作为值返回，然后加入每个线程. 这不是一个非常灵活的方法，特别是如果 f(i) 次的时间可以是随机的。

您可能还想考虑一个线程池，让每个线程计算 f(i)，然后得到下一个 i 求和。

于 2013-06-14T16:35:44.170 回答
0

您可以使用线程构建块

tbb::parallel_for(1, N, [=](long long i) {
  total = (total + f(i)) % modulus;
});

或者没有溢出检查：

tbb::parallel_for(1, N, [=](long long i) {
  total = (total + f(i));
});
total %= modulus;
于 2013-06-14T16:39:56.413 回答
0

为您的http://bisqwit.iki.fi/story/howto/openmp/#ReductionClause尝试 openMP 的并行处理total

于 2013-06-14T16:41:51.110 回答
0

如果f(long long int)是一个仅依赖于其输入且没有全局状态且加法的阿贝尔属性成立的函数，您可以获得如下显着优势：

for(long long int i = 0, j = 1; i < N; i += 2, j += 2)
{
    total1 = (total1 + f(i)) % modulus;
    total2 = (total2 + f(j)) % modulus;
}

total = (total1 + total2) % modulus;

通过允许编译器改进代码生成和 CPU 使用更多资源（这两个操作可以并行处理）并泵出更多数据并减少停顿，这样打破这一点应该会有所帮助。[我在这里假设一个 x86 架构]

当然，在不知道f真正的样子的情况下，很难确定这是否可行，或者它是否真的会有所帮助或产生可衡量的差异。

可能还有其他类似的技巧，您可以利用您的输入和平台的特殊知识 - 例如，SSE 指令可以让您做更多的事情。特定于平台的功能也可能有用。例如，可能根本不需要模运算，并且您的编译器可能会提供特殊的内在函数来执行模 N 加法。

我必须问，您是否分析过您的代码并发现这是一个热点？

于 2013-06-14T16:48:06.997 回答