CPU cache

hudeya

　　cache是一种小而快的缓冲器，用在CPU和main memory之间进行数据读写。
　　在processor访问主memory时，首先检查cache中是不是有一份copy，如果cache hit，则直接访问cache。
　　现在的cache多有很多的level，L1目前多是split的，分为data和instruction，L2和L3多是cores之间share的。
　　instruction cache：加速instruction fetch，data cache：加速data fetch and store。
　　还有另外的一种cache，TLB(Translation lookaside buffer)，MMU(memory management unit)中的部件，
　　主要加速virtual---physical的address translation，包含data和instruction。
　　cache的大小多是4，8，16KB这样倍数增加。
　　Cache entries
　　cache和memory之间的数据交换是以固定大小来交换的，叫做cache line，
　　当一个cache line从memory copy到cache时，一个cache entry会被创建，cache entry除了包含数据还有一部分的memory location信息。
　　processor读写main memory时，首先根据地址检查相应的cache line，找到，成为cache hit。
　　没有找到称为cache miss，当cache miss时，首先新建一个cache entry，并从main memory中copy data。
　　Cache performance
　　cache miss对于read操作影响最大，CPU需要等待，
　　对于write操作，数据从main memory copy到cache的操作可以background执行，影响不是很大。
　　Replacement policies
　　当需要新添加一个cache entry时，必须有一个cache entry要被撤销掉(evict)，基本原则是选择未来最不可能被用到的cache entry 替换。
　　最常用的算法时，least_recently used(LRU)
　　为了更有效的利用cache资源，在系统初始化时，一些memory address被设置为non-cacheable，
　　Write policies
　　如果数据会被写入cache，那之后的某个时间一定会被写入main memory，写入的时间叫做write policy。
　　write-through：每次的cache write都会被写入main memory。
　　write-back：cache write后不会立即写入main memory，只是标记为dirty，
　　当1)read cache miss，首先cache entry evict，然后read new data to cache;
　　2)write cache miss，该cache evict，然后新建cache entry，读data。
　　main memory中的数据，可能被DMA或者multi-core processor改变，导致cache coherence问题。
　　CPU stall
　　由于cache miss而带来的CPU的等待，称为cpu stall，消耗掉几百条指令的执行时间。
　　目前的一些措施：1)out-of-order execution，应用在intel的core中。
　　2)simultaneous multithreading(SMT)，或者hyper-threading(HT)
　　Cache entry structure
　　tag------data block------flag bits
　　data block，中保存cache line的数据，cache的大小等于每个data block的大小乘上block的个数，不包括tag/flag/error correction code等空间。
　　tag，中保存data的部分address in main memory。
　　Flag bits，对于instruction cache，一个cache entry，只有一个bit，valid，表示当前数据是不是valid
　　对于data cache，一个cache entry，有两个bit，valid bit和dirty bit。
　　Associativity
　　如果main memory中的数据，可以选择cache中的任意entry进行copy，replacement，这样的方式叫做：fully associative
　　如果main memory中的每个entry，只能选择cache中的一个entry，这样的方式叫做：direct mapped
　　如果main memory中的每个entry，可以去cache中的N和place，这样的方式叫做：N-way set associative
　　associativity也是一种trade-off，越大的N-way set associativity，cache miss会越少，但是遍历时间会更长，增加很多逻辑。

　　Cache miss
　　cache miss可以分为三大类：
　　1)instruction read miss，影响最大的miss，导致thread的执行to wait/stall
　　2)data read miss，影响相对较小的miss，一些not dependent on cache read的instruction可以先执行。
　　3)data write miss， 由于write可以进入queue，并且对后续的instruction影响较小。
　　影响cache miss的因素：size，associativity，block size，
　　根据Mark Hill的研究，可以将cache miss的原因分为三部分：
　　1)Compulsory miss，第一次访问memory中的某个地址，与cache size和associativity无关。可以通过prefetching和更大的cache block来保证。
　　2)Capacity miss，与block size和associtivity无关，只是因为cache大小总是有限的。
　　3)Conflict miss，1)mapping miss，由于某个特定的associativity，而导致的，无法避免。
　　2)replacement miss，由于replacement policy导致的。
　　Address translation
　　目前的很多程序，或者跑在自己的一段virtual address上保存自己的code和data，或者所有的程序跑在一个整体的virtual address上。
　　拥有virtual memory的系统，要求必须有一个translate的机构，将virtual address变为physical address。
　　目前多在MMU中实现，包含TLB。
　　在address translation过程中，最重要的三个方面：
　　1)Latency：在virtual address产生的几个cycle之后，physical address才能在MMU中产生。
　　2)Aliasing：多个virtual address可能对应一个physical address，所以processor必须保证physical address上的更新以program的order来进行，
　　3)Granularity：virtual address多分为pages，每一个page可以单独map。
　　Cache根据tag/index与physical/virtual address的关系，可以分为四类：
　　1)PIPT(Physical indexed, physical tagged)：use physical address for both index and tag。最简单却也是最慢的方式，因为MMU必须先将
　　virtual address变为physical address。(不会有aliasing问题)，优点：low latency
　　2)VIVT(virtual indexed, virtual tagged)：use virtual address for both index and tag。最快的方式，但是存在aliasing问题，
　　多个virtual address对应同一个physical address，存在coherency问题。
　　同一个virtual address对应多个physical address，存在homonyms问题。
　　没有办法区分是否对应同一个physical address
　　3)VIPT(virtual indexed, physical tag)：virtual address for the index，physical address in the tag，可以避免homonyms，保持部分VIVT的优点。
　　4)PIVT(physical indexed, virtual tag)：用的较少。