<p>我在<em>C</em>中编写了求和示例:结果显示为<a href="https://stackoverflow.com/a/459704/543411">CPU time</a>度量,我总是使用<code>gcc -O1 using-c.c</code>来编译(gcc版本:gcc版本4.9.0 20140604)。源代码如下。在</p>
<p>我选择矩阵大小为<code>n x n</code>。对于<code>n<2k</code>,行和列的总和没有任何可测量的差异(对于<code>n=2k</code>,每次运行6-7 us)。在</p>
<h3>行总和</h3>
<pre><code>n first/us converged/us
1k 5 4
4k 19 12
10k 35 31
20k 70 61
30k 130 90
</code></pre>
e、 g<code>n=20k</code>
^{pr2}$
<h3>列</h3>
<pre><code>n first/us converged/us
1k 5 4
4k 112 14
10k 228 32
20k 550 246
30k 1000 300
</code></pre>
<p>例如<code>n=20k</code></p>
<pre><code>Run 0 taken 552 cycles. 0 ms 552 us
Run 1 taken 358 cycles. 0 ms 358 us
Run 2 taken 291 cycles. 0 ms 291 us
Run 3 taken 264 cycles. 0 ms 264 us
Run 4 taken 252 cycles. 0 ms 252 us
Run 5 taken 275 cycles. 0 ms 275 us
Run 6 taken 262 cycles. 0 ms 262 us
Run 7 taken 249 cycles. 0 ms 249 us
Run 8 taken 249 cycles. 0 ms 249 us
Run 9 taken 246 cycles. 0 ms 246 us
</code></pre>
<h3>讨论</h3>
<p>行总和更快。我并没有从任何缓存中获益,也就是说,重复求和并不比初始求和快多少。列求和的速度要慢得多,但在5-8次迭代中它会稳步增加。在<code>n=4k</code>到{<cd8>}之间,这种增长最为明显,其中缓存有助于将速度提高约10倍。在较大的阵列中,加速仅为因子2。我还观察到,虽然行和收敛非常快(经过一次或两次试验),列求和收敛需要更多的迭代(5次或更多)。在</p>
<p>给我上一课:</p>
<ul>
<li>对于大型数组(超过2k个元素),求和速度存在差异。我相信这是由于从RAM获取数据到L1d缓存时的协同作用。虽然我不知道一次读取的块/行大小,但我假设它大于8个字节。所以下一个要总结的元素已经在缓存中了。在</li>
<li>列和速度首先受内存带宽的限制。当从RAM读取分散的块时,CPU似乎急需数据。在</li>
<li>当重复执行求和时,人们期望一些数据不需要从RAM中获取,并且已经存在于L2/L1d缓存中。对于行求和,这只对<code>n>30k</code>很明显,对于列求和,它已经在<code>n>2k</code>处变得明显。在</li>
</ul>
<p>使用<code>perf</code>,我看不出有什么大的区别。但是C程序的大部分工作是用随机数据填充数组。我不知道如何消除这些“设置”数据。。。在</p>
<p>以下是本例的<em>C</em>代码:</p>
<pre><code>#include <stdio.h>
#include <stdlib.h> // see `man random`
#include <time.h> // man time.h, info clock
int
main (void)
{
// seed
srandom(62);
//printf ("test %g\n", (double)random()/(double)RAND_MAX);
const size_t SIZE = 20E3;
const size_t RUNS = 10;
double (*b)[SIZE];
printf ("Array size: %dx%d, each %d bytes. slice = %f KiB\n", SIZE, SIZE,
sizeof(double), ((double)SIZE)*sizeof(double)/1024);
b = malloc(sizeof *b * SIZE);
//double a[SIZE][SIZE]; // too large!
int i,j;
for (i = 0; i< SIZE; i++) {
for (j = 0; j < SIZE; j++) {
b[i][j] = (double)random()/(double)RAND_MAX;
}
}
double sum = 0;
int run = 0;
clock_t start, diff;
int usec;
for (run = 0; run < RUNS; run++) {
start = clock();
for (i = 0; i<SIZE; i++) {
// column wise (slower?)
sum += b[i][1];
// row wise (faster?)
//sum += b[1][i];
}
diff = clock() - start;
usec = ((double) diff*1e6) / CLOCKS_PER_SEC; // https://stackoverflow.com/a/459704/543411
printf("Run %d taken %d cycles. %d ms %d us\n",run, diff, usec/1000, usec%1000);
}
printf("Sum: %g\n", sum);
return 0;
}
</code></pre>