我有一个循环,从1到N迭代,并在时间上进行模块化求和。但是N非常大,所以我想知道是否有一种方法可以通过利用多线程来修改它。
以下是示例程序
for (long long i = 1; i < N; ++i)
total = (total + f(i)) % modulus;
在我的情况下,f(i)并不是实际的函数,而是一个很长的表达式,在这里会占用很多空间。把它放在这里只是为了说明目的。
我有一个循环,从1到N迭代,并在时间上进行模块化求和。但是N非常大,所以我想知道是否有一种方法可以通过利用多线程来修改它。
以下是示例程序
for (long long i = 1; i < N; ++i)
total = (total + f(i)) % modulus;
在我的情况下,f(i)并不是实际的函数,而是一个很长的表达式,在这里会占用很多空间。把它放在这里只是为了说明目的。
是的,请尝试这个:
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
隐含了。total %= modulus
。这个减法语句只会为您添加每个线程的总计,通常情况下不会在“0”和“modulus-1”之间。 - SirGuy假设f(i)是独立的,但大致运行时间相同,您可以创建4个线程,让每个线程对总数的1/4进行求和,然后返回总和作为值,并加入每个线程。这不是一个非常灵活的方法,特别是如果f(i)的时间可以是随机的。
您还可以考虑使用线程池,使每个线程计算f(i),然后获取下一个i进行求和。
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;
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。
我必须问一下,您是否对代码进行了分析,并发现这是一个热点?
i+=2, j+=2
。另外,请注意 OP 循环从 1
开始,虽然这只是一个小细节(有些人可能会挑剔)。 - didierc尝试使用openMP的并行for循环和reduction子句来处理你的total
http://bisqwit.iki.fi/story/howto/openmp/#ReductionClause