并行文件系统的特点 计算机科学基础知识(一)The Memory Hierarc(6)

2、Direct-Mapped Cache和Set Associative Cache

如果每个cache set中只有一个cache line，也就是说E等于1，这样组织的cache就叫做Direct-Mapped Cache。这种cache的各种操作比较简单，例如判断是否cache hit。通过Set index后就定位了一个cache set，而一个cache set只有一个cache line，因此，只有该cache line的valid有效并且tag是匹配的，那么就是cache hit，否则cache miss。替换策略也简单，因为就一个cache line，当cache miss的时候，只能把当前的cache line换出。虽然硬件设计比较简单了，但是conflict Miss会比较突出。我们可以举一个简单的例子：

float dot_product(float x[8], float y[8])

{

int i; float sum = 0.0;

for(i=0; i<8; i++)

{

sum += x[i]*y[i];

}

return sum;

}

上面的程序是求两个向量的dot product，这个程序有很好的局部性，按理说应该有较高的cache hit，但是实际中未必总是这样。假设32 byte的cache被组织成2个cache set，每个cache line是16B。假设x数组放在0x0地址开始的32B中，4B表示一个float数据，y数组放在0x20开始的地址中。第一个循环中，当访问x[0]的时候（set index等于0），cache的set 0被加载了x[0]~x[3]的数据。当访问y[0]的时候，由于set index也是0，因此y[0]~y[3]被加载到set 0，从而替换了之前加载到set 0的x[0]~x[3]数据。第二个循环的时候，当访问x[1]，不能cache命中，于是重新将x[0]~x[3]的数据载入set 0，而访问y[1]的时候，仍然不能cache hit，因为y[0]~y[3]已经被flush掉了。有一个术语叫做Thrashing就是描述这种情况。

正是因为E＝1导致了cache thrashing，加大E可以解决上面的问题。当一个cache set中有多于1个cache line的时候，这种cache就叫做Set Associative Cache。ARM926的cache被称为four-way set associative cache，也就是说一个cache set中包括4个cache line。一旦有了多个cache line，判断cache hit就稍显麻烦了，因为这时候必须要逐个比对了，直到找到匹配的Tag并且是valid的那个cache line。如果cache miss，这时候就需要从main memory加载cache，如果有空当然好，选择那个flag是invalid的cache line就OK了，如果所有的cache line都是有效的，那么替换哪一个cache line呢？当然，硬件设计可以有多种选择，但是毫无疑问增加了复杂度。

还有一种cache被叫做fully Associative cache，这种cache只有一个cache set。这种cache匹配非常耗时，因为所有的cache line都在一个set中，硬件要逐个比对才能判断出cache miss or hit。这种cache只适合容量较小的cache，例如TLB。

3、写操作带来的问题

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-87804-6.html