DCAHCE全定制数据CacheTag的设计与验证1(10).doc

FUL-CUSTOM DATA CACHE TAG BIT DESIGN AND VERIFICATION OF X-CHIPSET PROCESSOR分类号 TP302.2 学号 03060015 UDC 密级 公 开 工学硕士学位论文全定制数据Cache Tag的设计与验证硕士生 姓名 黄 平 学 科 专 业 计算机科学与技术 研 究 方 向 计算机系统结构 指 导 教 师 方 粮 研究员 国防科学技术大学研究生院二五年十一月Full Custom Design and Verification of Data Cache TagAuthor: Huang PingSupervisor: Prof. Fang LiangA Dissertation Submitted for the Masters DegreeComputer CollegeNational University of Defense TechnologyChangsha, Hunan, P. R. ChinaNovember, 2005目 录图目录1表目录1摘 要1ABSTRACT1第一章 绪论11.1 选题背景11.2 课题研究的内容、成果和意义21.3 本文的组织结构2第二章 Cache设计技术22.1 通用微处理器Cache概述22.1.1 Cache的引入22.1.2 片上Cache的工作原理22.2 Cache的组织结构22.2.1 Cache的存储映像22.2.2 查找方法22.2.3 替换策略22.3 写策略与一致性协议22.3.1 Cache写策略22.3.2 Cache的一致性协议32.4 Cache的性能分析32.4.1 Cache系统的加速比32.4.2 Cache性能的改进32.5 本章小节3第三章 数据Cache Tag的逻辑设计33.1 数据Cache设计要求33.2 总体结构33.2.1 准Harvard结构33.2.2 虚实结合的查找算法33.2.3 工作流程33.3 特征参数选取33.4 替换策略选取43.4.1 替换策略的选择43.4.2 替换策略的实现43.5 写策略与一致性协议43.5.1 写策略和一致性协议43.6 数据Cache的Tag43.7 本章小节5第四章 Cache Tag的物理设计54.1 Cache Tag的分体设计54.1.1 分立的标识存储体设计54.1.2 数据体与状态体的分立设计54.2 Tag的标识存储体设计54.2.1 存储阵列设计54.2.2 比较命中指示电路设计64.2.3 校验电路的设计74.3 Tag的状态位存储体设计74.3.1 MESI存储位的设计74.3.2 写修改位的设计74.3.3 LRU位的设计74.3.4 存储单元的尺寸选取74.3.5 字线保持逻辑84.4 版图布局的优化84.5 本章小结8第五章 数据Cache的验证85.1 验证方法方法概述85.2 X微处理器数据Cache验证方法85.3 版图级SPICE模拟85.3.1 版图级SPICE模拟85.3.2 译码电路的验证85.3.3 数据的读出电路验证85.3.4 比较命中输出电路的验证95.4 系统级验证95.4.1 译码电路的系统级验证95.4.2 伪LRU算法的验证95.4.3 一致性协议的验证95.5 本章小结10第六章 结束语106.1 全文的工作总结106.2 工作展望10致 谢10攻读硕士期间发表的论文10参考文献10图目录图1.1 处理器计算时间与访存时间的变化趋势1图2.1 存储器和CPU性能提高情况对比图2图2.2 Cache/主存系统结构示意图2图2.3 三种映象规则2图2.4 4路组相联并行标识比较2图2.5 多处理器系统中的Cache/主存关系3图2.6 MESI状态转换图3图3.1 数据Cache接口信号图3图3.2 Cache工作流程图3图3.3 三位记录位的LRU算法逻辑图4图3.4 伪 LRU替换策略4图3.5 两级Cache工作环境示意图4图3.6 L1/L2 Cache的MESI状态转换图4图3.7 数据Cache的逻辑结构示意图5图4.1 三端口Tag逻辑图5图4.2 存储单元版图示意图5图4.3 Tag逻辑位示意图（一）5图4.4 Tag逻辑位示意图（二）5图4.5 Tag总体逻辑组成示意图5图4.6 Tag标识存储体电路结构图5图4.7 AND型24译码器5图4.8 两级译码结构图5图4.9 动态译码电路5图4.10 Tag体4路中同一位数据的存取电路图5图4.11 Cache数据存储单元电路与版图6图4.12 存储单元写操作示意图6图4.13 存储单元读操作示意图6图4.14 Tag体写入控制逻辑6图4.15 差分电压灵敏放大器6图4.16 差放读出逻辑6图4. 17 常用敏感使能信号生成电路6图4.18 复制单元分布图6图4.19 Cache Tag比较命中判断逻辑图6图4.20 Cache Tag比较命中判断电路图7图4.21 Tag比较器电路7图4.22 命中判断示意图7图4.23 Tag到体的输出指示形成电路7图4.24 四输入的奇偶校验电路单元7图4.25 异或门和同或门7图4.26 状态位存储器布局图7图4.27 MESI位基本单元电路图7图4.28 写修改位基本单元电路图7图4.29 LRU位基本单元电路图7图4.30 MESI位存储体之版图8图4.31 字线保持逻辑图8图4.32 字线布局图（一）8图4.33 字线布局图（二）8图4.34 Tag体版图8图4.35 数据Cache的Tag总体逻辑图8图5.1 常规IC设计验证层次图8图5.2 SPICE激励流程图8图5.3 译码电路时序图8图5.4 差放读出时序图9图5.5 存储阵列读出时序图9图5.6 命中指示输出电路时序图（一）9图5.7 Tag到体的输出指示形成电路9图5.8 命中指示输出电路时序图（二）9图5.9 译码电路系统模拟时序图9图5.10 伪LRU算法的功能验证程序流程图9图5.11 LRU算法模拟示意图（一）9图5.12 LRU算法模拟示意图（二）9图5.13 LRU算法模拟示意图（三）9图5.14 LRU算法模拟示意图（四）9图5.15 MESI一致性协议验证程序流程图10图5.16 MESI一致性协议模拟仿真图（一）10图5.17 MESI一致性协议模拟仿真图（二）10表目录表3.1 各种块大小的情况下Cache的失效率53表3.2 改写LRU自身状态过程中的LRU算法4表3.3 读周期数据Cache的MESI状态转换4表3.4 写周期数据Cache的MESI状态转换4表3.5 查询周期数据Cache的MESI状态转换4摘 要在现代微处理器中，Cache是提高性能必不可少的重要功能部件，其大小和速度已成了衡量微处理器性能的一项重要指标。随着处理器速度的不断提高，如何保证Cache能够以与处理器相近的速度高效的为计算部件提供数据呢？我们知道，在组成Cache的两大功能模块中，Tag是核心，它不仅负责地址的比较，并以其结果触发整个Cache的运转。所以，微处理器的设计中，Cache Tag的高效设计是影响系统性能的关键之一。本文在对Cache技术深入研究的基础上，结合X微处理器的系统设计要求，设计并实现了X处理器中数据Cache Tag模块的逻辑、电路和版图设计，它能保证X处理器的数据Cache在单时钟周期内完成命中读写操作。本设计的最大特色是使用三个分立的Tag体分别响应U流水线、V流水线和监听总线的请求，它们之间互相独立，协同高效地实现了一个三端口Tag的功能要求，减小工程实现的难度，增加了系统的可靠性。其次是设计了一个高效可靠的动态判命中电路，提高了Tag的命中输出速度。我们还针对X处理器的4路组相联结构设计了一种全新的伪LRU算法，实现简单，高效可靠，从而有效的保证了Cache的高命中率。此外，为了验证LRU算法和一致性协议，我们在验证平台上做了相关的系统级模拟，逻辑模拟结果和设计初衷是吻合的。同时，还对一个完整的Tag体做了详细的SPICE模拟，重点分析了判命中电路的模拟结果。版图Spice模拟结果显示：在0.18m CMOS工艺下，Tag体中的数据读出为，Tag体向Bank体发出命中指示信号的时延仅，这一结果使得当处理器的设计主频为时，Cache数据的读写完全可以在半个时钟周期内完成，很好的满足了X处理器的需要。关键词：Cache，LRU，替换策略，一致性，验证ABSTRACTIn modern microprocessors, Cache has becoming an absolutely neccessary function component. Its speed has been one of the main criterions to evaluate the performance of microprocessors. On the basis of deep research on Cache technology, this paper presents the logical, circuits and layout design of the Tag module in the data Cache of the X microprocessor. According to the system design requirement, it makes sure that the X microprocessor can get the data from the data Cache in a cycle when hit. There are three glint points in the paper. The main feature is the design of three separate tags to realize a 3-ported Tag, which respectly response to the requests of U pipeline, V pipeline and Snooping bus. These three tags work separately, but implement the 3-ported Tags function together. The second one is a dynamic circuit designed for hit judgment, which reduce the comparing time sharply; and a totally new pseudo LRU mechanism is proposed, which not only effective, but also can be easily realized. On the system verification platform, the simulation in system level about the pseudo LRU mechanism and MESI protocol is taken, and the results conform to the original intension of our design. Simultaneously, deeply SPICE simulation on the entire Tag design is applied, and we focus on the simulation and analysis of the hit judgment circuit.The outputs of the SPICE simulation on layout shows, on the condition of 0.18m CMOS technology, the access time is 1.13ns, the delay of the “hit” signal effective is just 1.49ns, which makes the X microprocessor can easily acquire a data from data Cache, just in a cycle ,when the working frequency is 250MHz.Key Words: Cache, LRU, Replace strategy, Consistency, Verification绪论存储器是计算机系统的核心部件之一，其性能直接关系到整个计算机系统性能的高低。现在的计算机系统一般都采用多级存储器结构，由上至下依次为寄存器、主存、磁盘、光盘、磁带等，其特点是从外存储器到CPU中的寄存器逐级向上，存储容量逐级减小，而存取速度逐级提高，价格越来越贵。由于上下两级存储器间的速度可以相差l-2个数量级或者更高，因此，两级之间的数据交换常常成为系统瓶颈，严重降低了系统的性能。为了解决这个问题，通常采用的办法是在两级存储器之间增加一个高速缓冲存储器Cache。如今，Cache作为微处理器的一个重要部件，其大小和速度已成了衡量微处理器性能的一项重要指标。选题背景在当今的信息社会中，计算机系统已成为是整个信息处理的核心，作为知识经济的“脑细胞”的处理器俨然成为这个社会的核心中的核心，无所不在的分布在当代通信设备、网络设备等一切信息节点上。在这种趋势下，各个科技大国都把研制高性能处理器作为其在综合科技实力上竞争的一个热点，我国非常重视在这个领域的投入，每年微电子产业都以大于30%的增长率快速发展，但就总体而言，这个产业仍处起步阶段，与国际先进水平相比差距甚远。产量小、产品技术低，设计能力、制造技术、产品和市场开发都缺乏自主能力。微处理器虽然已有“方舟”、“龙芯”等几种型号，但其性能和相关应用还无法与国外芯片竞争，总之国内所需微处理器几乎全部从国外进口1。技术上受制于人不仅仅是经济受损，而且对国家安全构成严重的隐患，因为大多数处理器芯片都有用户所不知道的“后门”，生产厂商对外公布的指令集只是芯片所支持指令集的一个子集，掌握这些“后门”的人可以不费吹灰之力便可通过网络获得所需信息。用这样的芯片构筑的信息系统显然是毫无安全可言，因此研制开发自己的微处理器，已经迫在眉睫。在这样的大背景下，我们开始了一款通用高性能微处理器芯片的研发。我们设计的微处理器是一款高性能处理器，它的研制顺应了我国科技发展的需要。对这款芯片的开发，无论在高性能微处理器的体系结构，还是深亚微米设计方法学等相关领域，都将是一次非常有意义的探索。项目中，我有幸参与了此微处理器数据Cache部件的研制工作，主要负责Cache的Tag部分的研究和设计。Cache作为计算机系统中的重要部件，其速度的快慢对系统有着至关重要的影响。如何保证Cache能以与CPU相当的速度为处理器提供数据，怎样保证Cache的高命中率等都是值得研究的课题。高效的电路设计是保证Cache能快速响应的关键因素，这对Cache中的比较电路作出了更高的要求。在早期的计算机系统中，处理器与存储器的速度差距不是十分明显，因此早期处理器（如INTEL 8086）的是通过处理器接口直接读写片外存储器的。随着芯片制造工艺的发展，处理器与存储器之间的速度差距越来越大，处理器直接访问片外主存储器将会造成大量的CPU时间浪费。图1.1是2001年以来微处理器中计算时间与访存时间的变化趋势，在计算时间不断减少的同时，访存延迟改善很小，处理器性能越来越受制于访存延迟。单从计算速度来看，处理器拥有接近三倍的性能提升，但是整体性能提升却远不到三倍。为了解决二者的速度差异问题，高性能处理器普遍采用了Cache缓存技术，多级Cache缓存构成存储系统完成处理器内核的存储操作8，并通过系统总线或者DMA通道访问主存储器。图1.1 处理器计算时间与访存时间的变化趋势2Cache作为近几十年来计算机体系结构上最重要的改进，已成为计算机系统结构和微电子学等相关领域众多科技人员研究的热点。近些年来，随着工艺技术的进步和人们对高性能孜孜不倦的追求，新的微体系结构、新的算法、基于新算法和新工艺的逻辑和电路结构层出不穷。Cache的设计有了显著的变化，结构不断优化，速度不断提高，应用也越来越广泛。围绕这一课题，人们作了大量的工作，提出了不少有价值的构想。为了确保设计芯片的兼容性和通用性，我们研究了大量的相关文献，并采取正反向结合的设计方法实现微处理器的设计。我的毕业设计分三个阶段完成。第一阶段完成了收集整理相关资料，并学习吸收样片数据Cache部件的设计精华；反向设计和验证；第二阶段，在第一步的基础上，依据对参考样片中数据Cache Tag部件的深入分析、研究，找出了进一步提高性能的途径，完成了从逻辑、电路到版图的自主设计；最后对我们设计的整个Cache Tag部分做了系统级功能验证，并对单个Tag做了详细的SPICE模拟。课题研究的内容、成果和意义本课题研究主要内容包括以下几个方面：一、对Cache相关技术资料的搜集、整理和研究，特别是关于SRAM单元实现，存储阵列的组织、读出放大电路及其时序控制的研究。二、数据Cache的标识(Tag)和Cache数据存储体的设计。具体包括Cache整体结构设计、替换策略实现、Cache一致性和可测试性设计等，重点分析了数据Cache的Tag设计。三、利用系统级的功能验证验证了伪LRU算法和MESI一致性协议，并对本文所设计的数据Cache Tag的存储体进行SPICE模拟，重点对比较命中电路进行详细验证。课题研究的主要成果：设计实现了一个具有完整逻辑功能的高效率数据Cache 的Tag部件；系统级的模拟验证了算法和协议实现的正确性，版图级SPICE结果确保了部件工作时序的有效性。课题研究的意义：一、从我个人方面来讲，通过这次课题使我系统的研究了有关高速存储器的理论和一些实现，同时把我书本理论学习与工程实践结合起来，在工程实践中进一步得到巩固。二、从课题研究成果的角度来讲有两方面的实际意义。首先是我们的微处理器项目研制有很强的现实意义，并为以后的数据Cache设计奠定了基础；其次是对有关存储器的IP核的开发有积极意义，本课题研究设计的SRAM存储模块稍作改动就可以是一个IP核，可直接用在相关设计中。本文的组织结构本文重点介绍了X微处理器数据Cache Tag的逻辑结构设计、电路设计与优化、版图布局、及其功能验证。全文共分六章：第一章介绍了课题研究背景，课题研究内容、目的和意义及论文组织结构。第二章介绍了Cache作用和工作原理及Cache设计的关键技术。第三章介绍了数据Cache Tag的逻辑设计，重点是其工作方式和主要参数的选择。 第四章介绍了数据Cache Tag的物理设计，重点在存储比较电路的逻辑和版图实现。第五章介绍了对数据Cache Tag的版图级SPICE模拟和系统级的验证。第六章对全文进行了总结和未来工作进行展望。Cache设计技术通用微处理器Cache概述Cache作为提高CPU性能的重要部件，其随着CPU的发展而不断改进的过程可以概括为：从无到有，由小到大，先外后内，纵深配备，软硬兼施。Cache首先是在IBM 360/80计算机上实现的，随着计算机体系结构的不断革新，特别是半导体加工工艺水平的不断提高， Cache技术也逐渐应用到PC中。在80386时期出现外部Cache；80486时期开始有内部仅8KB的Cache；Peutium时期有了分离内部L1 Cache和外部L2 Cache；P3时已经把L2 Cache也集成到CPU内部；在P4处理器中则使用了一种先进的一级指令Cache动态跟踪缓存，大大提高了处理器的运算效率。Cache的引入近十多年来，CPU的性能提高得很快，在1980年至1986年之间，CPU以每年35的速度递增，而从1987年开始，CPU性能则是以每年提高55，但是主存性能的提高却慢得多，DRAM的速度每年仅提高75，如图2.1所示。因此，CPU和主存之间在性能的差距上越来越大。现代计算机大都采用Cache技术来解决这个问题。图2.1 存储器和CPU性能提高情况对比图5Cache也叫高速缓冲存储器，是一个速度等于或接近于上级存储的小容量存储器。它利用程序的局部性原理，保存下级存储器刚刚被访问过的数据及其邻近小范围的数据，利用较小的硬件投资，使得以后的多次访问在高速的Cache中有很高的命中率，从而大大减少实际访问下级存储器的频度。这样，由Cache和下级存储器组成的存储器与原下级存储器相比，访问方式不变、容量不变、每位成本稍贵，但实际的平均存取速度接近与上一级存储器，从而大大的改善了计算机系统的性能。片上Cache的工作原理图2.2给出了一个位于CPU与主存之间的Cache模型。Cache的容量与主存相比是很小的，差23个数量级，目前在主存容量配置是几百MB到一个GB的情况下，Cache的典型值是18MB。Cache的工作速度很快，一般接近于甚至同于CPU速度。由图可知，CPU与Cache之间的数据交换是以“字”为单位，而Cache与主存之间的数据交换是以“块”为单位，一个块由若干个字组成，是定长的。图2.2 Cache/主存系统结构示意图当CPU试图读取主存一个字时，发出此字内存地址（物理地址）到Cache和主存，此时Cache控制逻辑依据地址进行判断此字当前是否在Cache中。若是，此字立即由Cache递交给CPU，否则，要用主存读取周期把这个字从主存读出送到CPU，同时将含有此字的整个数据块从主存读出送到Cache中。由于程序的存储器访问具有局部性，为满足当前一次访问请求而取来的一个数据块，下面的多次访问很可能是读取此块中的其它字，从而大大加快了CPU的访存速度，提高了系统性能。在一个程序执行期间，我们用Nc表示由Cache完成存取的总次数，Nm表示由主存完成存取的总次数，那么可将命中率（hit ratio）H定义为：则1H为失效率（miss ratio）。若以tc表示Cache命中时的访问时间，tm表示未命中时的主存访问时间，则Cache/主存系统的平均访问时间ta为：于是，若用部件加速比来表示，则Cache部件的加速比可见，提高Cache的命中率能大大加速Cache部件的性能，从而提高整个系统的性能。当然，命中率是一个很复杂的问题，它不仅与程序的行为有关，还与Cache的设计有很大关系，如Cache的级数、容量、组织方式、块大小等。Cache的组织结构Cache是按块进行组织管理的。Cache和主存均被分割成大小相同的块，每个块由若干个字组成，信息以块为单位调入Cache。相应地，CPU的访存地址也被分割成两部分：块地址和块内偏移。如下所示：主存地址：块地址（标识和索引）块内偏移块地址用于查找该块在Cache中地位置，包括标识（Tag）和索引（Index），块内偏移用于确定所访问的数据在该块中的位置，同时表明了块的大小。由于Cache的容量比下级存储器小l-2个数量级、要保证Cache高效工作，必须考虑以下问题：1、存储映像：当把一个块调入Cache时，可以放在哪个位置上。2、查找算法：当所需要块在Cache中时，如何找到该块。3、替换算法：采用何种替换策略，使得访问Cache的命中率最高。4、写策略： 当进行写访问时，应进行哪些操作。5、一致性协议：如何保证Cache和下级存储器的数据具有一致性。这里先看看与Cache组织结构相关的存储映像、查找算法和替换规则，写策略和一致性协议将在下一节阐述。Cache的存储映像一般来说，主存容量远大于Cache的容量。因此，当要把一个块从主存调入Cache时，就有个如何放置的问题。这就是映象规则所要解决的。映象规则主要有三种：全相联映像法、直接映像法和组相联映像法35。直接映像直接映像是最简单的一种方法，是指主存中的每一个块只能放到Cache中唯一的一个地方。如图2.3（a）所示，图中的箭头的虚线表示映象关系。例如，主存的第9块只能放入Cache的第1块的（9 mod 8）位置。作为一个例子，图中画出了Cache大小为8块、主存大小为16块的情况。实际的Cache常包含几百个块，而主存则一般包含上百万个块。一般的，对于主存的第i块（即块地址为i），设它映象到Cache的第j块，则 j i mod (M）其中M为Cache的块数（此例中是8）。设M2m，则当表示为二进制数时，j实际上就是i的低m位。如下所示：主存块地址 i ：j因此，可以直接用主存块地址的低m位去选择直接映像Cache中的相应块。全相联映像全相连映像是指主存中的一块可以被放置到Cache中的任意一个位置的方法。如图2.3（b）所示。例如图中的第9块可以放到Cache中的任意位置。因为块地址也保存在Cache的标识中，因此一个主存块可以拷贝到Cache中的任意位置。此法的优点是映像灵活，命中率高。不足是硬件实现较为困难，主要是因为相联度越高，全比较输出代价高，速度慢。组相联映像组相联映像是上述两种方法的折衷方案。其基本思想是把Cache分为m组，每个组分为n块。主存块分配时对组是唯一的，即直接映射方法；在组内的位置可以任意，即全相联映射方法。这样，主存中的每一个块可以被放置到Cache中唯一的一个组中的任何一个位置。如图2.3（c）所示。组的选择常采用位选择算法，即：若主存第i块映象到Cache的第k组，则 k = i mod (G) 其中G为Cache的组数。设G2g，则当表示为二进制数时，k实际上就是i的低g位，如下所示：主存块地址 i ：k因此，可以直接用主存块地址的低g位去选择组相联Cache中的相应组。（a）全相联映射 （b）直接映射 （c）组相联映射图2.3 三种映象规则在上述三种映象规则中，全相联映象的Cache空间利用率最高，块冲突率最低，因而Cache命中率最高，但其实现硬件开销大，特别是全比较电路实现的代价高，很少被应用。直接映象由于每个主存块只有一个固定的位置可存放。两个索引相同的块往往容易发生冲突，导致失效率较高，但由于其硬件结构简单，成本低，使用得比较普遍。组相联则是集前两者之优点，性价比较高，使用得也相当广泛。查找方法当CPU访问Cache时，如何确定Cache中是否有所要访问的块？若有的话，如何确定其位置？这是通过查找目录表来实现的。Cache中设有一个目录表，该表所包含的项数与Cache的块数相同，每一项对应Cache的一个块，用于指出当前块中存放的信息是哪个主存块的。它实际上记录了主存块的块地址的高位部分，称为标识Tag。Cache中每一个块只能由其标识唯一确定它是主存的哪一个块。为了指出Cache中的块是否包含有效信息，一般在目录表中给每一项设置一个有效位。例如，当该位为“1”时表示：该目录项有效，也就是说Cache中相应块所包含的信息有效。当一个主存块被调入Cache中某一个位置时，他的标识就被填入目录表中与该Cache块对应的项中，并且该项的有效位被置“1”。根据映像规则的不同，一个主存块可以映像到Cache中的一个或多个候选位置。当CPU访问该主存块时，必须且只需查找它的候选位置所对应的标识即可。如果有与所访问的主存块相同的标识，且其有效位为“1”，则它所对应的Cache块即是所要查找的块。为了保证速度，对各候选位置的所对应的标识的检查比较应并行进行。因此候选位置越多，实现查找的机制就越复杂，代价就越高。图2.4 4路组相联并行标识比较直接映象Cache的候选位置少，只有一个；全相联Cache的候选位置最多，为M个；n路组相联则介于二者之间，为n个。并行查找的实现方法有两种：（1）用相联存储器（CAM）实现；（2）用单体多字存储器和比较器来实现。图2.4中画出了用第二种方法实现4路组相联的情况。这时需要4个比较器。CPU访存时，用本次访存地址中的索引Index从标识存储器中选取一行（对应于一组），并从改行读出4个标识，然后将它们与本次访存地址中的标识Tag进行并行比较。根据比较结果确定是否命中及该组中哪一个块是要访问的块（若命中）。若未命中，则向外发出Cache miss指示，启动所需块的调入。由图中可以看出，n越大，实现查找的机制就越复杂，代价就越高。直接映象的Cache的查找最简单：只需查找一个位置即可。所访问的块要么就在这个位置上，要么就不在Cache中。无论是直接映象还是组相联，查找时只需比较Tag，Index无需参加比较。这是因为Index已被用来选择要查找的组或块，而所有索引相同（且只有索引相同的相）的块都被映射到该组中。所以，该组中存放的块的索引一定与本次访存的Index相同。如果Cache的容量不变，提高相联度会增加每一组中的块数，从而减少Index的位数和增加Tag的位数。当采用类似与图2.4的并行比较方案时，不仅所需的比较器的个数随之增加，而且比较器的位数也随之增大。在全相联的情况下，Index的位数为0，块地址全都用作为Tag，此时，多采用CAM结构来作比较。替换策略由于Cache的容量总是远小于下一级存储器的容量，因此Cache中只能是下级存储器的部分拷贝。所以当要从主存调入一个块到Cache中时，会出现该块所映像到Cache中的位置恰好被占用的情况。这时就需要强迫调出Cache一块，以便腾出空间，调入当前需要的内存块。那么到底应该调出哪一块呢？这就涉及到替换策略的问题。直接映像Cache中的替换很简单，因为只有一个块，别无选择。而在组相联和全相联Cache中，则有多个数据块供选择，这就需要一个比较好的算法，如果算法选择不当，将大大增加调入调出的频度。例如把一个当前不需要但是很快就将使用的行调出，必然会降低系统的效率。常用算法有随机法、有先入先出（FIFO）算法、最不经常使用算法、最近最少使用算法等4513。随机法就是为了均匀使用一组中的块，随机地选择被替换的块。这种方法的优点是简单、易于硬件实现，但这种方法没有考虑Cache块过去被使用的情况，反映不了程序的局部性原理，所以失效率比LRU高。先入先出FIFO（First-In-First-Out）先入先出算法依据进入Cache的先后次序来替换，先进的块首先被替换掉。这种方法的优点是容易实现。它虽然利用了同一组中各块进入Cache的顺序这一“历史”信息，但不能正确反映程序的局部性。因为先进入的块，很可能是经常要用到的块。最不经常使用算法(LFU算法)该方法的思想是把最近一段时间内被访问次数最少的行调出。因此实现时需要对每一个行设置一个计数器，对该行的访问次数计数、在需要替换时比较各个计数器的值，淘汰计数次数最少的数据行。这种算法的问题是明显的，那些在程序前期被频繁访问而在后期不再使用的行，可能会在相当长的时间内不会被淘汰，而那些刚刚调入并将继续反复使用的行则可能因为其计数器中的值较小而频遭淘汰，这将严重影响系统的效率。最近最少使用算法(LRU算法)LRU算法的思想是将最近一段时间内最少被访问的块淘汰出局。因此也需要为每行设置一个计数器、但是计数方法与LFU算法不同。LRU算法是把命中行的计数器清零、其它各行计数器加1。当需要替换时，比较各行的计数器值，淘汰数值最大的行出局。这种方法所依据的是程序局部性原理的一个推论：如果最近刚用过的块很可能就是马上要用到的块，则最久没用过的块就是最佳的被替换者。在上面介绍的四种算法中，LRU算法比较符合Cache工作原理，失效率是最低的，是Cache设计中最常使用的方法。但LRU算法硬件实现比较困难，特别是当组的数目增加时，完全LRU的实现代价越来越高，因而经常只是近似地实现34。写策略与一致性协议按照存储层次的要求，Cache内容应是主存部分内容的一个副本。但是“写”访问却有可能导致它们内容的不一致。例如，当处理机进行“写”访问，往Cache写入新的数据后，则Cache中相应单元的内容已发生变化，而主存中该单元的内容却仍然是原来的。这就产生了所谓的Cache与主存内容的一致性问题。显然，为了保证正确性，主存的内容也必须更新。至于何时更新，这就是写策略所要解决的问题。Cache写策略考虑到一致性、命中率、速度等问题，普遍采用的写策略有以下两种。写直达法(write-through)该方式的原理是在CPU向Cache写入的同时，也把数据写入主存储器，也就是让Cache和主存中的数据同时修改，以保证Cache和主存中相应单元数据的一致性。但这并不是说全部解决了一致性问题。例如，在多处理器系统中各CPU都有自己的Cache，一个主存块若在多个Cache中都有一份拷贝的话，某各CPU以写直达法来修改自己的Cache和主存时，其它Cache中的原拷贝就过时了。即使是单处理器系统中，也有I/O设备不经过Cache直接向主存写入的情况。因此，仍旧要关注一致性问题。写回法(Write-back)这种方式的原理是CPU修改了Cache的内容后并不立即修改主存中相应的单元，而在被修改过的Cache块将从Cache中淘汰时(如更换页面)才把它写入主存储器的相应单元中。此策略使Cache在CPU和主存之间，不仅在读访问上，而且在写访问上都能起到高速缓存的作用。对一Cache行的多次写命中都在Cache中快速完成修改，只是需被替换时才写回速度较慢的主存，减少了访问主存的次数从而提高了效率。为了支持这种策略，每个Cache行必须配置一个修改位，以反映此行是否被CPU修改过。当某行被换出时，根据此行的修改位是否为“1”，决定是将该行的内容写回主存还是简单的弃之不管。写回法和写直达法各有特色。两者比较，写回法的特点是速度快，“写”操作能以Cache存储器的速度进行。而且对于同一单元的多个写最后只需一次写回主存，有些“写”只到达Cache，不到达主存，降低了所要求的存储器带宽。写直达法的优点是易于实现，而且下一级存储器中的数据总是最新的。由于“写”访问并不需要用到所访问单元中原有的数据。所以，当发生写失效时，是否调入相应的块，有两种选择：按写分配（Write allocate）：写失效时，先把所写单元所在的块调入Cache，再进行写入。不按写分配（no-write allocate）：写失效时直接写入下一级存储器而不将相应的块调入Cache。这两种方法都可以应用于写直达法和写回法。一般的，写回法Cache多采用按写分配（这样，以后对那个块的“写”就能够被Cache捕获；而写直达法Cache多采用不按写分配，因为以后对那个块的“写”仍然还要到达下一级存储器。Cache的一致性协议概述一致性要求是指，若Cache中某个字被修改，那么在主存（以及更高层次）上，该字的副本必须立即或最后加以修改，并确保它者引用主存上该字内容的正确性。图2.5 多处理器系统中的Cache/主存关系当代多处理器系统中，大都每个处理器都有自己的Cache，呈现出如图2.5所示的结构。同一主存块的拷贝能同时存于不同Cache中，若允许处理器各自能独立的修改自己的Cache，就会出现不一致问题。解决此问题有软件办法和硬件办法。硬件办法能动态的识别不一致产生的条件并予以及时处理，从而时Cache的使用有很高的效率。并且，此方法对程序员和系统软件开发人员是透明的，减轻了研制负担，从而普遍被采用。硬件方法也称为Cache一致性协议，分为两类：（1）目录协议 (Directory Protocol) ：它由位于主存的目录来保存有关各个局部Cache的全局性状态信息，并由一个集中式的主存/Cache控制器来维护Cache的一致性。（2）监听协议（Snooping Protocol）：它将维护Cache一致性的责任分散到各个Cache控制器。每个Cache控制器必须识别出，它的Cache中哪些块是与其它Cache共享的。当修改一个共享块是必须在系统中广播有关信息，其它Cache控制器监听到此信息时予以响应。根据广播的信息以及反应的不同，监听协议又分为写修改协议和写无效协议两种方式。写修改协议是，某处理器要修改他它的Cache中的一个共享块时要广播具体的修改字及地址，容纳有此共享块的各个Cache同时予以修改。写无效协议是，某一个处理器要修改它的Cache中的一个共享块时，无需广播具体的修改字，只需给出块地址和其它必要的指示信息，令其它Cache中此块变为无效，然后处理器对其Cache的此块完成一次本地写操作。MESI协议的状态转换MESI协议是一种采用写无效方式的监听协议。它要求每个Cache行有两个状态位，用于描述改行当前是处于修改态（M）、专有态（E）、共享态（S）或者无效态（I）中的那种状态，从而决定它的读/写操作行为。这四种状态的定义是： 修改态（Modified）：此Cache行已被修改过，内容不同于主存且为此Cache专用。 专有态（Exclusive）：此Cache行内容同于主存，但不出现于其它Cache中。 共享态（Shared）：此Cache行内容同于主存，也出现在其它Cache中 无效态（Invalid）：此Cache行的内容无效MESI协议适合以总线为互连机构的多处理器系统。各Cache控制器除负责相应自己CPU的内存读写操作（包括读/写命中与未命中）外，还要负责监听总线上的其它CPU的内存读写活动（包括读监听命中和写监听命中等）并对自己的Cache予以相应的处理。所有这些处理过程可以概括为图2.6，相关的基础知识在很多参考书中都有介绍，如有需要可参阅5或16。图2.6 MESI状态转换图Cache的性能分析计算机系统中设置Cache的一个主要目的就是为了提高存储系统的速度，因此评价Cache性能主要指标就是加速比513。Cache系统的加速比假设Cache的访问周期为Tc，主存访问周期Tm（一般情况下TmTc），Cache的命中率为H，所以在理想情况下（H=1），Cache的加速比Sp定义为： （2.1）但是Cache不可能是100命中，所以Cache平均访问周期T定义为： （2.2）用T代替（2.1）中的Tc后得到： （2.3）从这个关系式看到，系统加速比Sp是命中率H和主存周期Tm与Cache周期Tc比值的函数。对于设计好的系统，Tm和Tc的值是固定的，所以提高加速比最好的办法是通过对程序编译优化提高命中率H。对于Cache设计来说，最关心的是平均访存时间，因此对式（2.2）重新定义为： 平均访存时间命中率（H）命中开销失效率（1H）失效开销 （2.4）其中命中开销是指一次访问Cache所用的时间（Tc），失效开销是指Cache不命中时的访存时间(可能不止一个访存周期Tm)。Cache性能的改进从(2.4)式中可以看出，提高Cache性能要从下面三个方面改进：1)降低失效率2)提高Cache命中时间3)减少失效开销关于如何提高Cache性能，在文献5中介绍了15种方法，其中7种用于降低失效率，5种用于减少开销，3种用于减少命中时间，这里不再赘述。本章小节本章介绍了Cache的发展、Cache设计的关键技术、性能分析。重点对Cache的映像方式、查找算法、替换策略和一致性等方面做了较为深入的分析。数据Cache Tag的逻辑设计数据Cache设计要求我们的微处理器设计主频是250MHz，支持4K/4M分页，能支持两路超标量流出，它对数据Cache的功能、性能提出了如下要求：一、功能要求1、一般工作模式的数据读写：X处理器直接与Cache间的数据传送：64位及其以下X处理器通过Cache与主存打交道有两类读写总线周期：256位猝发式传送，用于Cache的行填入和行写出；64位及其以下的不可超高速缓存式传送：从Cache的旁路通过，主要用于I/O接口的数据传送2、支持两路超标量数据流出3、维护数据的一致性4、负责实现存储数据奇偶校验5、提供可测试性设计二、性能要求1、Cache命中率不小于95。2、单周期响应：若命中，Cache数据读写要求在一个CPU内周期完成；不命中的情况下，也要能在一个时钟周期内输出不命中的指示信号（Cache miss）。在处理器中，TLB和Cache是协同工作的两大块，它们一起共同支持数据的快速访问，我们总称之为快速数据存取模块。在我们的处理器中，它们与其它部件的接口由以下三部分组成，如图3.1所示。1、数据总线：包括由外引脚直接输入的64位数据总线（Data bus）U、V两路数据总线（U databus和V databus），以及和总线区打交道的64位数据总线（D_B64 databus）。还有与测试相关的32位数据总线。2、地址总线：Cache实地址输入总线32位；Cache虚地址输入总线32位（其中虚实地址的低12位公用）；Cache地址监听总线输入32位。3、其它相关控制信号。从设计要求可以看出，快速数据存取模块设计的具体任务就是设计实现两个高性能的高速缓存逻辑：一是TLB，用于加快线性地址向物理地址的转换速度；一是数据的L1 Cache，用于缓存一些可能近期被使用的数据。图3.1 数据Cache接口信号图设计要求中有两个条件比较苛刻：（1）速度要求。数据Cache的关键路径是读操作数据通路。从地址计算部件（AGU）给出线性地址开始，到虚实地址的转换、Cache标识的读出放大、标识的比较、Cache数据的读出放大、命中行数据输出，以及标识和数据的奇偶校验等，这么多的操作要在一个时钟周期内完成，难度非常大。速度与制造工艺、Cache组织结构、工作方式和电路实现等有关。（2）失效率要求。失效率与Cache组织结构、容量、相联度、块大小和替换算法等有关。本文重点讨论的是片上的L1 Cache的设计，因此在我们Cache中影响速度和失效率的主要因素着手，从系统结构级，到电路设计与优化级，直到版图的布局优化等方面采取了一系列的优化措施来满足这两个要求。总体结构准Harvard结构设计中，我们采用了一种准Harvard结构，即指令Cache和数据Cache在结构上是分开的，但指令和数据总线却是统一的。与采用单一存储体及数据总线的Von-Neumann结构以及Harvard结构相比它具有以下优点：分离Cache消除了单一Cache中指令块和数据块互相冲突而引起的失效，能使取数据与取指令同时并行，提高了处理器的效率；统一总线降低了成本。这种结构的不足是：限制了分配给指令和数据的空间，即无法完成在单一Cache中指令和数据所占空间的动态分配；自修改指令（Self-Modified Instruction）的再访问开销增大，因为修改过的指令需经过数据Cache写入主存，才能再访问，访问这些指令前数据Cache和指令Cache都必须清空。虚实结合的查找算法同Cache失效相比，Cache命中发生的频率高得多，按照“大概率事件优先”的指导思想，减少命中时间是一个简单可行的好方法。在整个Cache的运作中，如何提高地址的转化，快速寻址就显得相当重要了。为此有人提出了虚拟Cache技术4。考虑到页内位移在地址的虚实转化过程中是保持不变的，我们采用了一种虚实结合的查找算法。在X处理器中，虚地址和实地址的低12位公用，所以我们可以用虚拟地址的页内位移作为访问Cache的索引，但标识用物理地址。这样，当CPU发出访存请求后，在TLB中进行虚实地址转换的同时，可并行地通过索引（In