如何在C和java中生成cpu缓存效果？

Question

在Ulrich Drepper的论文中,每个程序员应该了解内存,第三部分:CPU缓存,他显示了一个图表,显示了"工作集"大小与每个操作消耗的cpu周期之间的关系(在这种情况下,顺序读取).并且图中有两个跳转,表示L1缓存和L2缓存的大小.我编写了自己的程序来重现c中的效果.它只是简单地从头到尾顺序读取一个int []数组,我尝试了不同大小的数组(从1KB到1MB).我将数据绘制成图形并且没有跳跃,图形是直线.

我的问题是:

1. 我的方法有问题吗？生成cpu缓存效果的正确方法是什么(查看跳转).
2. 我在想,如果它是顺序读取,那么它应该像这样操作:当读取第一个元素时,它是缓存未命中,并且在缓存行大小(64K)内,将有命中.借助预取,将隐藏读取下一个缓存行的延迟.它会连续地将数据读入L1缓存,即使工作集大小超过L1缓存大小,它也会驱逐最近最少使用的数据,并继续预取.因此,大多数缓存未命中都将被隐藏,从L2获取数据所消耗的时间将隐藏在读取活动之后,这意味着它们同时运行.相关性(在我的情况下是8路)将隐藏从L2读取数据的延迟.那么,我的节目现象应该是对的,我错过了什么吗？
3. 是否有可能在java中获得相同的效果？

顺便说一句,我在linux中这样做.

---

编辑1

感谢Stephen C的建议,这里有一些额外的信息:这是我的代码:

int *arrayInt;

void initInt(long len) {
    int i;
    arrayInt = (int *)malloc(len * sizeof(int));
    memset(arrayInt, 0, len * sizeof(int));
}

long sreadInt(long len) {   
    int sum = 0;
    struct timespec tsStart, tsEnd;

    initInt(len);

    clock_gettime(CLOCK_REALTIME, &tsStart);
    for(i = 0; i < len; i++) {
        sum += arrayInt[i];
    }
    clock_gettime(CLOCK_REALTIME, &tsEnd);
    free(arrayInt);
    return (tsEnd.tv_nsec - tsStart.tv_nsec) / len;
}

在main()函数中,我尝试过从1KB到100MB的数组大小,仍然相同,每个元素的平均耗时为2纳秒.我认为时间是L1d的访问时间.

我的缓存大小:

L1d == 32k

L2 == 256k

L3 == 6144k

---

编辑2

我已将代码更改为使用链接列表.

// element type
struct l {
    struct l *n;
    long int pad[NPAD]; // the NPAD could be changed, in my case I set it to 1
};

struct l *array;
long globalSum;

// for init the array
void init(long len) {
    long i, j;

    struct l *ptr;

    array = (struct l*)malloc(sizeof(struct l));
    ptr = array;
    for(j = 0; j < NPAD; j++) {
        ptr->pad[j] = j;
    }
    ptr->n = NULL;

    for(i = 1; i < len; i++) {
        ptr->n = (struct l*)malloc(sizeof(struct l));
        ptr = ptr->n;
        for(j = 0; j < NPAD; j++) {
            ptr->pad[j] = i + j;
        }
        ptr->n = NULL;
    }

}

// for free the array when operation is done
void release() {
    struct l *ptr = array;
    struct l *tmp = NULL;
    while(ptr) {
        tmp = ptr;
        ptr = ptr->n;
        free(tmp);
    }
}

double sread(long len) {
    int i;
    long sum = 0;

    struct l *ptr;
    struct timespec tsStart, tsEnd;


    init(len);

    ptr = array;

    clock_gettime(CLOCK_REALTIME, &tsStart);
    while(ptr) {
        for(i = 0; i < NPAD; i++) {
            sum += ptr->pad[i];
        }
        ptr = ptr->n;
    }
    clock_gettime(CLOCK_REALTIME, &tsEnd);

    release();

    globalSum += sum;

    return (double)(tsEnd.tv_nsec - tsStart.tv_nsec) / (double)len;
}

最后,我将打印出globalSum以避免编译器优化.正如你所看到的,它仍然是一个顺序读取,我甚至尝试了高达500MB的数组大小,每个元素的平均时间大约是4纳秒(也许是因为它必须访问数据'pad'和指针' n',两次访问),与1KB的数组大小相同.所以,我认为这是因为像prefetch这样的缓存优化很好地隐藏了延迟,我是对的吗？我将尝试随机访问,并将结果放在以后.

---

编辑3

我试过随机访问链表,这是结果:

第一个红线是我的L1缓存大小,第二个是L2.所以我们可以看到那里有点跳跃.有时潜伏期仍然很好.

Answer 1

这个答案不是一个答案，而是更多的笔记。

首先，CPU倾向于在高速缓存行上运行，而不是在单个字节/字/双字上运行。这意味着，如果您顺序读取/写入一个整数数组，则对高速缓存行的第一次访问可能会导致高速缓存未命中，但是随后对同一高速缓存行中不同整数的访问将不会。对于64字节的高速缓存行和4字节的整数，这意味着您每16次访问只会导致一次高速缓存未命中。这会稀释结果。

其次，CPU具有“硬件预取器”。如果它检测到高速缓存行是按顺序读取的，则硬件预取器将自动预取它预测接下来需要的高速缓存行（以尝试在需要它们之前将其取入高速缓存）。

第三，CPU做其他事情（例如“乱序执行”）来隐藏获取成本。您可以测量的时间差（在缓存命中和缓存未命中之间）是CPU无法隐藏的时间，而不是获取的总成本。

这三件事加在一起意味着：为了顺序读取整数数组，可能是在您从前一个缓存行进行16次读取时，CPU预取了下一个缓存行；并且任何缓存未命中成本都不会引起注意，并且可能会完全隐藏。为了防止这种情况；您希望一次“随机”访问每个高速缓存行，以最大化“在缓存中适合工作集”和“在缓存中不适合工作集”之间的性能差异。

最后，还有其他因素可能会影响测量。例如，对于使用分页的操作系统（例如Linux和几乎所有其他现代操作系统），在所有这些之上（TLB /转换后备缓冲区）都有一层整个缓存，一旦工作集超过一定大小，TLB就会丢失; 在图表的第四个“步骤”中应可见。还有来自内核的干扰（IRQ，页面错误，任务切换，多个CPU等）；可能会在图表中显示为随机的静态/错误（除非经常重复测试并且丢弃异常值）。缓存设计（缓存关联性）中还存在一些工件，这些工件可以通过依赖于内核分配的物理地址的方式降低缓存的有效性。这可能被视为“步骤”