一、Cache概述1.1 什么是CacheCache高速缓冲存储器是位于CPU和主存之间的一种高速小容量存储器用于解决CPU与主存之间速度不匹配的问题。由于CPU速度远快于主存如果CPU每次都要等待主存响应会造成大量时间浪费。Cache通过存储最近使用过的数据和指令使CPU能够以接近自身速度访问存储器。1.2 程序访问的局部性原理Cache的设计基于程序访问的局部性原理包括时间局部性最近被访问的数据很可能在不久的将来再次被访问。空间局部性与最近被访问数据相邻的数据很可能被访问。例如循环体内的变量会被反复访问时间局部性数组元素通常按顺序访问空间局部性。二、Cache的基本结构2.1 Cache的组成Cache主要由以下部分组成存储体存放从主存调入的数据块地址映射机构将主存地址转换为Cache地址替换机构Cache满时决定替换哪个块写操作机构处理写命中和写不命中的策略2.2 基本概念块Block/LineCache和主存之间数据交换的基本单位。主存和Cache都被划分为大小相等的块。标记Tag用于标识Cache中存放的是主存中哪个块的数据。有效位Valid Bit表示该Cache行是否有效。三、地址映射方式重点地址映射是指主存块如何放置到Cache行中主要有三种方式3.1 直接映射Direct Mapped原理每个主存块只能映射到Cache中唯一确定的位置。映射公式Cache行号 主存块号 mod Cache行数地址结构标记TagCache行号Index块内地址Offset优点实现简单访问速度快无需替换算法。缺点不够灵活容易发生冲突不同块映射到同一行。3.2 全相联映射Fully Associative原理每个主存块可以映射到Cache中任意位置。地址结构标记Tag块内地址Offset优点最灵活冲突最少Cache利用率高。缺点硬件复杂需要比较所有行的标记成本高。3.3 组相联映射Set Associative原理Cache分成若干组每组包含若干行。主存块先映射到组直接映射再在组内任意放置全相联。映射公式组号 主存块号 mod 组数地址结构标记Tag组号Index块内地址OffsetK路组相联每组有K个Cache行称为K路组相联。如2路、4路、8路组相联。优点兼顾灵活性和实现复杂度是实际应用最广泛的方式。3.4 三种映射方式对比特性直接映射全相联映射组相联映射灵活性低高中冲突率高低中硬件复杂度低高中访问速度快慢较快四、替换算法重点当Cache已满且需要调入新块时需要选择一个块替换出去。4.1 随机算法Random随机选择一个块进行替换。实现最简单但可能替换掉即将使用的块。4.2 FIFO先进先出替换最早进入Cache的块。实现简单但没有考虑访问频率可能替换常用块。4.3 LRU最近最少使用★替换最久未被访问的块。符合局部性原理命中率较高是实际应用最广泛的算法。实现方式为每行设置计数器命中时清零未命中时计数器1替换计数器最大的行。4.4 LFU最不经常使用替换访问次数最少的块。需要记录访问次数实现较复杂。五、写策略重点写策略解决Cache与主存数据一致性问题分为写命中和写不命中两种情况。5.1 写命中Write Hit写直达Write Through同时写Cache和主存。优点是数据一致性好缺点是写速度慢。写回Write Back只写Cache替换时才写回主存。需要设置修改位Dirty Bit。优点是写速度快缺点是数据一致性差。5.2 写不命中Write Miss写分配Write Allocate先将主存块调入Cache再写入。通常与写回策略配合使用。非写分配No Write Allocate直接写入主存不调入Cache。通常与写直达策略配合使用。5.3 常见组合写直达 非写分配写回 写分配数据一致性好实现简单适合单处理器写效率高适合多处理器六、Cache性能分析重点6.1 命中率与缺失率命中率Hit RateCPU访问Cache命中的次数占总访问次数的比例。缺失率Miss Rate 1 - 命中率6.2 平均访问时间公式平均访问时间命中时间缺失率×缺失代价其中命中时间访问Cache所需时间通常1-3个时钟周期缺失代价从主存调入块所需时间通常50-100个时钟周期6.3 加速比加速比无Cache时的访问时间/有Cache时的平均访问时间6.4 影响Cache性能的因素Cache容量容量越大命中率越高但成本也越高访问速度可能降低。块大小块太小不能充分利用空间局部性块太大则块数减少且调入时间长。相联度相联度越高冲突越少但硬件越复杂访问时间越长。替换算法好的替换算法能提高命中率。
