c - 循环平铺。如何选择 block 大小？

Question

我正在尝试学习循环优化。我发现循环平铺有助于使数组循环更快。我尝试使用下面给出的两个代码块，有和没有循环阻塞，并测量两者所花费的时间。大多数时候我没有发现显着差异。我测试了不同的 block 大小，但我不确定如何选择 block 大小。如果我的方向错误，请帮助我。事实上，我发现没有 block 的循环工作得更快。

一个。带阻塞

int max = 1000000;
int B = 100;
for (i = 0; i < max; i += B)
{
     for (j = i; j < (i + B); j++)
     {
         array[j] = 0;
     }
 }

b。不阻塞

for (i = 0; i < max; i++)
{
    array[i] = 0;
 }

耗时:阻塞:耗时 - 6997000 纳秒

不阻塞运行时间 - 6097000 纳秒

Answer 1

正如此处所指出的，平铺是一种技术，旨在让您在处理工作集时将其保存在缓存中，以便享受内存延迟。如果你流过你的数据，你将看不到任何好处，因为你永远不会访问缓存，所以平铺将没有用。

您的示例循环以相同的顺序执行完全相同的工作，除了添加另一个分支并使分支模式稍微复杂一些(大多数预测器都能够应对，只是没有任何帮助)。

考虑以下示例 -

#include "stdlib.h"
#include "stdio.h"
#include <time.h>

#define MAX (1024*1024*32)
#define REP 100
#define B  (16*1024)
int main() { 
    int i,j,r;
    char array[MAX];

    for (i = 0; i < MAX; i++) {  // warmup to make things equal if array happens to fit in your L3
       array[i] = 0;
    }

    clock_t t1 = clock();

    // Tiled loop
    for (i = 0; i < MAX; i += B) {
        for (r = 0; r < REP; r++) {
             for (j = i; j < (i + B); j+=64) {
                 array[j] = r;
             }
        }
    }
    clock_t t2 = clock();

    // un-tiled loop
    for (r = 0; r < REP; r++) {
        for (i = 0; i < MAX; i+=64) {
             array[i] = r;
        }
    }

    clock_t t3 = clock();
    printf ("Tiled: %f sec\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
    printf ("Untiled: %f sec\n", (double)(t3 - t2) / CLOCKS_PER_SEC);
    printf ("array[0] = %d\n", array[0]);    // to prevent optimizing out all the writes
}

两个循环都在进行相同的访问(64 字节跳转是通过使用每个缓存行一次来对缓存施加压力，并防止 IPC 和指令调度成为瓶颈)。

平铺版本以 block 为单位对这些访问进行重新排序，以便重复单个 block 可以重复命中缓存。由于 block 大小设置为 16k，它可能适合大多数 L1 缓存并获得非常好的延迟。对于外循环的每次迭代，您将有 1 次迭代，您会错过所有缓存并进入内存(如果您的 L3 大于 32M，只需拨 MAX 甚至更高以确保)，并且 REP-1 从 L1 开始的迭代。

Untiled 版本也会重复自身 REP 次，但每次重复都会破坏缓存中的所有数据，使所有访问都进入内存，从而累积到更高的整体延迟。

用 gcc 4.8.1 (-O3) 编译让我在 Xeon 5670 @ 2.9GHz -

Tiled: 0.110000 sec
Untiled: 0.450000 sec
array[0] = 99

超过 4 倍 :)

请注意，untiled 版本仍然有一个好处 - 有一个单一的有序流，因此硬件预取器可以提前运行以有效地为您获取数据，从而在一定程度上减轻内存延迟影响。但是，如果您添加以下内容，您可以帮助 CPU 在银行版本中做类似的事情:

for (i = 0; i < MAX; i += B) {
    for (r = 0; r < REP; r++) {
         for (j = i; j < (i + B); j+=64) {
             array[j] = r;
             if (r == REP - 2)                         // SW prefetching
                 __builtin_prefetch(&array[j+B], 0);    
         }
    }
}

告诉 CPU 在完成当前 block 之前略微引入下一个 block 。对于条件分支的价格(每个 block 有一些错误预测)，您减少了下一个 block 的第一次迭代的执行时间 - 我进一步减少到:

Tiled: 0.070000 sec