高速缓存内存优化数组转置:C

typedef int array[2][2]; void transpose(array dst, array src) { int i, j; for (j = 0; j < 2; j++) { for (i = 0; i < 2; i++) { dst[i][j] = src[j][i]; } } } 

src数组从地址0开始,dst数组从地址0x10开始。

L1数据缓存,直接映射,写分配,8字节块大小。

缓存总大小为16个数据字节。

src和dst数组的每个条目的命中或错过是什么?

答案是:

 src: [0][0] -> miss, [0][1] -> miss, [1][0] -> miss, [1][1] -> hit dst: [0][0] -> miss, [0][1] -> miss, [1][0] -> miss, [1][1] -> miss 

如果缓存总大小为32个数据字节,答案是:

 src: [0][0] -> miss, [0][1] -> hit, [1][0] -> miss, [1][1] -> hit dst: [0][0] -> miss, [0][1] -> hit, [1][0] -> miss, [1][1] -> hit 

我不确定这两种结果。 我不太了解数组和缓存的概念。

因此,在第一个实例中,您有两个8字节的缓存行,总共16个字节。 我假设int数据大小为4个字节。 鉴于数组在C中的位置以及您提供的偏移量,这些是可以缓存的内存行:

 Cacheable lines: #A: &src[0][0] = 0x00, &src[0][1] = 0x04 #B: &src[1][0] = 0x08, &src[1][1] = 0x0C #C: &dst[0][0] = 0x10, &dst[0][1] = 0x14 #D: &dst[1][0] = 0x18, &dst[1][1] = 0x1C 

然后我们需要知道程序访问每个内存地址的访问顺序。 我假设没有可能导致编译器重新排序的优化。

 Access order and cache behavior (assuming initially empty): #1: load src[0][0] --> Miss line A = cache slot 1 #2: save dst[0][0] --> Miss line C = cache slot 2 #3: load src[0][1] --> Hit line A = cache slot 1 #4: save dst[0][1] --> Hit line C = cache slot 2 #5: load src[1][0] --> Miss line B = cache slot 1 (LRU, replaces line A) #6: save dst[1][0] --> Miss line D = cache slot 2 (LRU, replaces line C) #7: load src[1][1] --> Hit line B = cache slot 1 #8: save dst[1][1] --> Hit line D = cache slot 2 

我认为,这与你的第二个答案相符。 然后使用32字节(4行)的高速缓存大小,假设所有其他因素都是常量:

 Access order and cache behavior (assuming initially empty): #1: load src[0][0] --> Miss line A = cache slot 1 #2: save dst[0][0] --> Miss line C = cache slot 2 #3: load src[0][1] --> Hit line A = cache slot 1 #4: save dst[0][1] --> Hit line C = cache slot 2 #5: load src[1][0] --> Miss line B = cache slot 3 #6: save dst[1][0] --> Miss line D = cache slot 4 #7: load src[1][1] --> Hit line B = cache slot 3 #8: save dst[1][1] --> Hit line D = cache slot 4 

它们完全相同。 唯一的区别是如果你重新转换。 在第一种情况下,你会得到完全相同的行为(好吧,你从缓存中充满了所有错误的东西开始,所以它也可能是空的)。 但是,在较大的缓存情况下,第二次调用所需的一切都已缓存,因此不会出现缓存未命中。

我和你的答案之间的差异很可能是由于我们对循环计数寄存器(i和j)的编译器行为的假设。 我认为它们都存储在寄存器中(因此不会影响数据缓存)。 您可能需要假设它们位于内存中(因此与缓存交互)以获得预期结果。