高速缓冲存储器Cache的工作原理及技术实现

桂林理工大学2013年春季学期课程论文题目：高速缓冲存储器Cache的工作原理及技术实现 专业： 网络工程 班级： 网络11-2班 学号： 姓名： xxx 信息科学与工程学院2013年7月【内容摘要】缓冲存储器用在两个工作速度不同的硬件之间,在交换信息过程中起到缓冲作用，它能提高计算机系统的工作效益。高速缓冲存储器Cache是架设在CPU与内存之间的临时存储器，它的容量比内存小但交换速度快，主要用来提高CPU提取数据的速度 ，Cache作为PC系统中一个重要功能部件 ，已成为评价和选购P C系统的重要指标 ，下面主要谈谈Cache的原理 、设计及发展趋势。【关键词】Cache CPU命中率映像局部性原理【前言】 我们通常都认为计算机的速度是由CPU决定的, 虽然CPU主频的提升会带动系统性能的改善，但系统性能的提高不仅仅取决于CPU，还要有其它的硬件或软件来充分发挥它的速度，与系统架构、指令结构、信息在各个部件之间的传送速度及存储部件的存取速度等因素有关，特别是与CPU/内存之间的存取速度有关。我们知道要使用的软件都要通过主存储器(内存)才能运行,而主存储器的运行速度和CPU之间有一个数量级的差距,这就限制了CPU速度潜力的发挥，若CPU工作速度较高，但内存存取速度较低，则造成CPU等待，降低处理速度，浪费CPU的能力。如500MHz的P，一次指令执行时间为2ns,与其相配的内存（SDRAM）存取时间为10ns，比前者慢5倍，CPU和PC的性能怎么发挥出来？如何减少CPU与内存之间的速度差异？有4种办法：一种是在基本总线周期中插入等待，这样会浪费CPU的能力。另一种方法是采用存取时间较快的SRAM作存储器，这样虽然解决了CPU与存储器间速度不匹配的问题，但却大幅提升了系统成本。第3种方法是在慢速的DRAM和快速CPU之间插入一速度较快、容量较小的SRAM，起到缓冲作用；使CPU既可以以较快速度存取SRAM中的数据，又不使系统成本上升过高，这就是Cache法。还有一种方法，采用新型存储器。目前，一般采用第3种方法。它是PC系统在不大增加成本的前提下，使性能提升的一个非常有效的技术。高速缓冲存储器Cache的运行速度高于主存储器数倍,与CPU速度差不多,容量较小。【正文】一、高速缓冲存储器的结构Cache的功能是用来存放那些近期需要运行的指令与数据。目的是提高CPU对存储器的访问速度。为此需要解决2个技术问题：一是主存地址与缓存地址的映象及转换； 二是按一定原则对Cache的内容进行替换。 Cache的结构和工作原理如下图所示。 主要由三大部分组成： Cache存储体：存放由主存调入的指令与数据块。 地址转换部件：建立目录表以实现主存地址到缓存地址的转换。 替换部件：在缓存已满时按一定策略进行数据块替换，并修改地址转换部件。Cache通常由相联存储器实现。相联存储器的每一个存储块都具有额外的存储信息，称为标签(Tag)。当访问相联存储器时，将地址和每一个标签同时进行比较，从而对标签相同的存储块进行访问。Cache的3种基本结构如下：1、全相联Cache。地址映象规则：主存的任意一块可以映象到Cache中的任意一块 (1) 主存与缓存分成相同大小的数据块。 (2) 主存的某一数据块可以装入缓存的任意一块空间中。 全相联方式的对应关系如下图所示。如果Cache的块数为Cb，主存的块数为Mb，则映象关系共有CbMb种。在全相联Cache中，存储的块与块之间，以及存储顺序或保存的存储器地址之间没有直接的关系。程序可以访问很多的子程序、堆栈和段，而它们是位于主存储器的不同部位上。因此，Cache保存着很多互不相关的数据块，Cache必须对每个块和块自身的地址加以存储。当请求数据时，Cache控制器要把请求地址同所有地址加以比较，进行确认。这种Cache结构的主要优点是，它能够在给定的时间内去存储主存器中的不同的块，命中率高；缺点是每一次请求数据同Cache中的地址进行比较需要相当的时间，速度较慢，成本高，因而应用少。2、直接映像Cache。地址映象规则： 主存储器中一块只能映象到Cache的一个特定的块中。 (1) 主存与缓存分成相同大小的数据块。 (2) 主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数与缓存的总块数相等。 (3) 主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。直接相联映象规则如下图直接映像Cache不同于全相联Cache，地址仅需比较一次。在直接映像Cache中，由于每个主存储器的块在Cache中仅存在一个位置，因而把地址的比较次数减少为一次。其做法是，为Cache中的每个块位置分配一个索引字段，用Tag字段区分存放在Cache位置上的不同的块。单路直接映像把主存储器分成若干页，主存储器的每一页与Cache存储器的大小相同，匹配的主存储器的偏移量可以直接映像为Cache偏移量。Cache的Tag存储器(偏移量)保存着主存储器的页地址(页号)。以上可以看出，直接映像Cache优于全相联Cache，能进行快速查找，其缺点是当主存储器的组之间做频繁调用时，Cache控制器必须做多次转换。3.组相联映象方式组相联的映象规则： (1) 主存和Cache按同样大小划分成块。 (2) 主存和Cache按同样大小划分成组。 (3) 主存容量是缓存容量的整数倍，将主存空间按缓冲区的大小分成区，主存中每一区的组数与缓存的组数相同。 (4) 当主存的数据调入缓存时，主存与缓存的组号应相等，也就是各区中的某一块只能存入缓存的同组号的空间内，但组内各块地址之间则可以任意存放， 即从主存的组到Cache的组之间采用直接映象方式；在两个对应的组内部采用全相联映象方式。 下图示出了组相联的映象关系， 图中缓存共分Cg个组，每组包含有Gb块； 主存是缓存的Me倍，所以共分有Me个区， 每个区有Cg组，每组有Gb块。那么， 主存地址格式中应包含4个字段：区号、区内组号、组内块号和块内地址。 而缓存中包含3个字段：组号、组内块号、块内地址。主存地址与缓存地址的转换有两部分，组地址是按直接映象方式，按地址进行访问，而块地址是采用全相联方式，按内容访问。组相联Cache是介于全相联Cache和直接映像Cache之间的一种结构。这种类型的Cache使用了几组直接映像的块，对于某一个给定的索引号，可以允许有几个块位置，因而可以增加命中率和系统效率。优点：块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。 缺点：实现难度和造价要比直接映象方式高。二、Cache的工作原理及技术实现1、读取顺序CPU要读取一个数据时，首先从Cache中查找，如果找到就立即读取并送给CPU处理；如果没有找到，就用相对慢的速度从内存中读取并送给CPU处理，同时把这个数据所在的数据块调入Cache中，可以使得以后对整块数据的读取都从Cache中进行，不必再调用内存。正是这样的读取机制使CPU读取Cache的命中率非常高（大多数CPU可达90%左右），也就是说CPU下一次要读取的数据90%都在Cache中，只有大约10%需要从内存读取。这大大节省了CPU直接读取内存的时间，也使CPU读取数据时基本无需等待。总的来说，CPU读取数据的顺序是先Cache后内存。2、基于程序访问的局部性对大量典型程序运行情况的分析结果表明，在一个较短的时间间隔内，由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内。指令地址的分布本来就是连续的，再加上循环程序段和子程序段要重复执行多次。因此，对这些地址的访问就自然地具有时间上集中分布的倾向。数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象，就称为程序访问的局部性。根据程序的局部性原理，可以在主存和CPU通用寄存器之间设置一个高速的容量相对较小的高速缓冲存储器Cache，把正在执行的指令地址附近的一部分指令或数据从主存调入这个存储器，供CPU在一段时间内使用。这对提高程序的运行速度有很大的作用。系统正是依据此原理，不断地将与当前指令集相关联的一个不太大的后继指令集从内存读到Cache，然后再与CPU高速传送，从而达到速度匹配。CPU对存储器进行数据请求时，通常先访问Cache。由于局部性原理不能保证所请求的数据百分之百地在Cache中，这里便存在一个命中率。即CPU在任一时刻从Cache中可靠获取数据的几率。命中率越高，正确获取数据的可靠性就越大。一般来说，Cache的存储容量比主存的容量小得多，但不能太小，太小会使命中率太低；也没有必要过大，过大不仅会增加成本，而且当容量超过一定值后，命中率随容量的增加将不会有明显地增长。只要Cache的空间与主存空间在一定范围内保持适当比例的映射关系，Cache的命中率还是相当高的。一般规定Cache与内存的空间比为4：1000，即128kBCache可映射32MB内存；256kBCache可映射64MB内存。在这种情况下，命中率都在90以上。至于没有命中的数据，CPU只好直接从内存获取。获取的同时，也把它拷进Cache，以备下次访问。3、缓存分类前面是把Cache作为一个整体来考虑的，现在要分类分析了。Intel从Pentium开始将Cache分开，通常分为一级高速缓存L1和二级高速缓存L2。在以往的观念中，L1 Cache是集成在CPU中的，被称为片内Cache。在L1中还分数据Cache（I-Cache）和指令Cache（D-Cache）。它们分别用来存放数据和执行这些数据的指令，而且两个Cache可以同时被CPU访问，减少了争用Cache所造成的冲突，提高了处理器效能。在P4处理器中使用了一种先进的一级指令Cache动态跟踪缓存。它直接和执行单元及动态跟踪引擎相连，通过动态跟踪引擎可以很快地找到所执行的指令，并且将指令的顺序存储在追踪缓存里，这样就减少了主执行循环的解码周期，提高了处理器的运算效率。以前的L2 Cache没集成在CPU中，而在主板上或与CPU集成在同一块电路板上，因此也被称为片外Cache。但从P开始，由于工艺的提高L2 Cache被集成在CPU内核中，以相同于主频的速度工作，结束了L2 Cache与CPU大差距分频的历史，使L2 Cache与L1 Cache在性能上平等，得到更高的传输速度。L2Cache只存储数据，因此不分数据Cache和指令Cache。在CPU核心不变化的情况下，增加L2 Cache的容量能使性能提升，同一核心的CPU高低端之分往往也是在L2 Cache上做手脚，可见L2 Cache的重要性。现在CPU的L1 Cache与L2 Cache惟一区别在于读取顺序。4、读取命中率CPU在Cache中找到有用的数据被称为命中，当Cache中没有CPU所需的数据时（这时称为未命中），CPU才访问内存。从理论上讲，在一颗拥有2级Cache的CPU中，读取L1 Cache的命中率为80%。也就是说CPU从L1 Cache中找到的有用数据占数据总量的80%，剩下的20%从L2 Cache读取。由于不能准确预测将要执行的数据，读取L2的命中率也在80%左右（从L2读到有用的数据占总数据的16%）。那么还有的数据就不得不从内存调用，但这已经是一个相当小的比例了。在一些高端领域的CPU（像Intel的Itanium）中，我们常听到L3 Cache，它是为读取L2 Cache后未命中的数据设计的种Cache，在拥有L3 Cache的CPU中，只有约5%的数据需要从内存中调用，这进一步提高了CPU的效率。为了保证CPU访问时有较高的命中率，Cache中的内容应该按一定的算法替换。一种较常用的算法是“最近最少使用算法”（LRU算法），它是将最近一段时间内最少被访问过的行淘汰出局。因此需要为每行设置一个计数器，LRU算法是把命中行的计数器清零，其他各行计数器加1。当需要替换时淘汰行计数器计数值最大的数据行出局。这是一种高效、科学的算法，其计数器清零过程可以把一些频繁调用后再不需要的数据淘汰出Cache，提高Cache的利用率。5、无阻塞Cache分级结构微处理器性能由如下几种因素估算：性能=k(f1/CPI(1H)N) 式中：k为比例常数，f为工作频率，CPI为执行每条指令需要的周期数，H为Cache的命中率，N为存储周期数。虽然，为了提高处理器的性能，应提高工作频率，减少执行每条指令需要的周期数，提高Cache的命中率。同时分发多条指令和采用乱序控制，可以减少CPI值；采用转移预测和增加Cache容量，可以提高H值。为了减少存储周期数N，可采用高速的总线接口和不分块的Cache方案。以前提高处理器的性能，主要靠提高工作频率和提高指令级的并行度，今后则主要靠提高Cache的命中率。设计出无阻塞Cache分级结构。Cache分级结构的主要优势在于，对于一个典型的一级缓存系统的80的内存申请都发生在CPU内部，只有20的内存申请是与外部内存打交道。而这20的外部内存申请中的80又与二级缓存打交道。因此，只有4的内存申请定向到DRAM中。Cache分级结构的不足在于高速缓存组数目受限，需要占用线路板空间和一些支持逻辑电路，会使成本增加。综合比较结果还是采用分级Cache。L1 Cache的设计有在片一级分离和统一设计两种方案。Intel、AMD、原DEC等公司将L1 Cache设计成指令Cache与数据Cache分离型。因为这种双路高速缓存结构减少了争用高速缓存所造成的冲突，改进了处理器效能，以便数据访问和指令调用在同一时钟周期内进行。但是，仅依靠增加在片一级Cache的容量，并不能使微处理器性能随之成正比例地提高，还需设置二级Cache。在L1 Cache结构方面，一般采用回写式静态随机存储器（SRAM）。目前，L1 Cache容量有加大的趋势。L2 Cache的设计分芯片内置和外置两种设计。如AMD K63内置的256kB L2 Cache与CPU同步工作。外置L2 Cache，一般都要使二级Cache与CPU实现紧密耦合，并且与在片一级Cache形成无阻塞阶层结构。同时还要采用分离的前台总线(外部I/O总线)和后台总线(二级Cache总线)模式。显然，将来随着半导体集成工艺的提高，如果CPU与二级Cache集成在单芯片上，则CPU与二级Cache的耦合效果可能更佳。由于L2 Cache内置，因此，还可以在原主板上再外置大容量缓存1MB2MB，它被称为L3 Cache。6、PC中的Cache技术的实现PC中Cache的发展是以80386为界的。目前，PC中部分已实现的Cache技术如表1所示表1 pc中部分已实现的cache技