用多线程C++程序加速求和循环

Question

用多线程C++程序加速求和循环

3

我有一个循环，从1到N迭代，并在时间上进行模块化求和。但是N非常大，所以我想知道是否有一种方法可以通过利用多线程来修改它。

以下是示例程序

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

在我的情况下，f(i)并不是实际的函数，而是一个很长的表达式，在这里会占用很多空间。把它放在这里只是为了说明目的。

- MrP

如果你真的想加速它，尝试使用CUDA。另外，我可以问一下这个循环的目的是什么吗？ - aaronman

3

一种非常简单的优化方法是将%取模操作推迟到最后。从算术角度来看，除非你是为了防止溢出而这样做，否则在循环内部执行该操作是没有必要的。（感谢@Xaqq指出我之前过于笼统的概括。） - Scott Mermelstein

@ScottMermelstein 如果没有它可能会溢出。但是，如果可以在最后保存它，请这样做。 - Xaqq

需要取模，否则会溢出。 - MrP

@JoeRunde 没错，但我不知道怎么做，所以才问的。 - MrP

显示剩余2条评论

5个回答

2

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

您还可以考虑使用线程池，使每个线程计算f(i)，然后获取下一个i进行求和。

- Tom Tanner

这不是一个有效的答案，因为它是对我所要求的内容的重新表述。 - MrP

0

你可以使用 Threading Building Blocks。

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;

- user1810087

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。

我必须问一下，您是否对代码进行了分析，并发现这是一个热点？

- Nik Bougalis

我不知道如何正确地对代码进行性能分析，但它是一个热点。 - MrP

我认为你的意思是 i+=2, j+=2。另外，请注意 OP 循环从 1 开始，虽然这只是一个小细节（有些人可能会挑剔）。 - didierc

0

尝试使用openMP的并行for循环和reduction子句来处理你的totalhttp://bisqwit.iki.fi/story/howto/openmp/#ReductionClause

- rectummelancolique

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Richard · Accepted Answer

是的，请尝试这个：

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隐含了。