5

我发现有时将一个循环分成两个或多个循环会更快

for (i=0; i<AMT; i++) {
    a[i] += c[i];
    b[i] += d[i];
}
     ||
     \/
for (i=0; i<AMT; i++) {
    //a[i] += c[i];
    b[i] += d[i];
}
for (i=0; i<AMT; i++) {
    a[i] += c[i];
    //b[i] += d[i];
}

在我的台式机 win7、AMD Phenom(tm) x6 1055T 上,双循环版本运行速度更快,时间减少了大约 1/3。

但如果我正在处理任务,

for (i=0; i<AMT; i++) {
    b[i] = rand()%100;
    c[i] = rand()%100;
}

将 b 和 c 的分配分成两个循环并不比一个循环快。

我认为操作系统使用一些规则来确定某些代码是否可以由多个处理器运行。

我想问我的猜测是否正确,如果我是正确的,那么多个处理器会自动(无需线程编程)用于加速我的程序的规则或场合是什么?

4

3 回答 3

4

您的编译器可能正在对更简单的循环进行矢量化。在汇编器输出中,您会看到这是使用 SIMD 指令(如Intel 的 SSE)编译的程序来处理比一个数字更大的数据块。自动向量化是一个难题,编译器可能无法对同时更新的循环进行向a量化b。这可以部分解释为什么将复杂循环分成两部分会更快。

在“赋值”循环中,每次调用都rand()依赖于先前调用的输出,这意味着向量化本质上是不可能的。将循环分成两部分不会像第一种情况那样从 SIMD 指令中受益,因此您不会看到它运行得更快。查看编译器生成的汇编代码会告诉您编译器执行了哪些优化以及它使用了哪些指令。

即使编译器对循环进行向量化,程序也不会使用多个 CPU 或线程;没有并发。发生的情况是,一个 CPU 能够在多个数据点上并行运行单个执行线程。并行编程和并发编程之间的区别很微妙但很重要。

缓存局部性也可以解释为什么将第一个循环分成两个使其运行得更快,但不能解释为什么将“分配”循环分成两个不能。b有可能c在“分配”循环中足够小,以至于它们可以放入缓存中,这意味着循环已经具有最佳性能并且进一步破坏它不会带来任何好处。如果是这种情况,makebc更大将迫使循环开始破坏缓存并将循环分成两个将具有预期的好处。

于 2013-04-02T06:45:10.367 回答
2

优化由编译器(http://en.wikipedia.org/wiki/Loop_optimization)完成。如果您使用的是 GCC,请查看此页面http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html以获取可用优化规则的列表。

另一方面,看到您正在使用消耗大量 CPU 时间的 rand() 函数。

于 2013-04-02T06:37:45.090 回答
0

我想问我的猜测是否正确,如果我是正确的,那么多个处理器会自动(无需线程编程)用于加速我的程序的规则或场合是什么?

不,猜测不对。在所有三种情况下,代码都在单个内核上运行。

出于某些其他原因,将第一个循环分成两个使其更快。也许您的编译器能够生成更好的代码,或者 CPU 更容易预取正确的数据等。如果不分析生成的机器代码,就很难判断。

于 2013-04-02T06:40:07.350 回答