Cache basics
1.cache基本概念
1.1Block
主存和cache间以及cache和CPU间复制数据的最小大小,通常为64B。
1.2cache hit&miss
以LLC为例,上级的cache如果在LLC中找到相应的块,就称为cache hit,就把相应的块复制到上级的cache中或者CPU中。相反,如果没有找到,就称为LLC miss,需要从主存里面复制相应的块到LLC或者直接到上级cache(根据inclusion的策略有区别)。
1.3Eviction
如果从LLC中复制了相应的块到上一级cache中,那么上一级cache中的块根据相应的替换策略进行块的替换或者叫驱逐。
2.cache locality
代码中的一部分指令常常会被经常使用,重复执行
for (i=0, i<N, i++){
for (j=0, j<M, j++){
... Loop Body ...
}
}
其中的Loop Body称为热点,在一段时间会被不断执行,称为时间局部性。 时间局部性:如果一个块被访问了一定次数,接下来很有可能还会被访问。 空间局部性:如果一个块被访问了一定次数,那么很有可能其周围的块也会被访问。
3.cache
上面这个图是cache的概述。
3.1替换策略
Random:随即替换cache,可看出对性能的影响十分大。 LRU:需要每次访问进行更新;完全的LRU策略只能在small associates上实行(i.e 2 way) ; pseudo-LRU一般用于较大的associate(4-8 way) FIFO:highly associate cache MRU NMRU
3.2写策略
cache hit
write through:修改cache中块的值,并同时修改主存中相应块的值。
write back:修改 Cache 中的 Block 的数值后将此 Block 标记为 Dirty Block,但并不会立即修改主存中相对应的 Block 的数值,而是等到 Cache 中的此 Block 被驱逐時 (Eviction),才会修改主存中相对应的 Block 的数值。此方式有数据丢失的危险,但是速度较快。
cache miss
write allocate:
將主存中含有想要写入的 Block 复制到 CPU Cache 中,并再修改 Cache 中该 Block 的数值后将该 Block 标记为 Dirty Block。
write no allocate:
仅仅是写到主存中,不会被写回到cache中。
common combination:
write through & write no allocate
write back & write allocate
3.3cacheline解释
上图是cache的组织方式,cache由set组成,set由line组成,cacheline由valid bit,tag,data组成,其中data是真正要缓存的内存地址中的数据,而tag是用来搜索cache line的标签。 内存地址分解如下:
内存地址被分成了3部分,tag,set index和block offset,这三部分分别用来在cache中定位数据。 cache根据寻址方式可以分为3类:
- 直接映射(direct mapped cache),相当于每个set只有1个cache line。
- 组相联(set associate cache):多个set,每个set中有n个cacheline,就称为n-way set cache
- 全相连,即只有一个set
Tag 是用来区分不同的 Block 的标记。Valid Bit 是用来区分 一个 Block 里的资料是否为有效的。
Valid -> 1 Invalid -> 0
Cache 的大小的计算公式为: data bytes
4.Inclusion&Exclusion
其中inclusive cache包含上一级的cache,因此如果由上一级cache的clean写回操作,直接复制就好,不需要写操作,对于exclusive不包含上一级cache的副本,因此不能避免dirty eviction。如果发生LLC miss,inclusive cache需要对LLC和L2同时进行write allocate,保证inclusive,对于exclusive则不需要。
5.cache miss(3C)
compulsory miss(cold cache)
- 程序刚开始执行时,cache中没有任何的块,因此发生了cache miss
capacity miss
- cache的容量太小了,没有办法覆盖到整个working set
conflict miss
- 虽然 Cache 还有很多空间,但在 Working Set 中的 任意两个 Block 可能无法同时存在 Cache 中。发生的原因可能是因为,此 2 个 Block 的 Index 相同。(也就是所谓的 Cache Thrash)