（计算机科学与技术专业论文）数据cache+tag的全定制设计与验证.pdf

望堕型鲎垫查盔兰堑室尘堕兰垡鎏苎 摘要 在现代微处理器中，c a c h e 是提高性能必不可少的重要功能部件，其大小和速度已成 了衡量微处理器性能的一项重要指标。随着处理嚣速度的不皈提高，对c a c h e 中决定其速 度的t a g 部分进行全定制设计研究，具寄重要的理论和现实意义。 本文在对c a c h e 技术深入研究的基础上，结合x 微处理器的系统设计要求，设计并实 现了数据c a c h e 中t a g 模块的逻辑、电路和版图设计，它能有效的保证x 处理器的数据 c a c h e 在单周期内完成命中读写操作。 本文的t a g 设计有三大特点。首先是使用三个分立的t a g 体分别响应u 流水线、v 流 水线和监听总线的请求，它们之间彼此独立，协同高效地实现了个三端口t a g 的功能要 求，减小了工程实现的难度，增加了系统的可靠性；其次是设计了一个高效可靠的动态判 命中电路，提高了t a g 的命中输出速度：最后，我们针对x 处理器的4 路组摆联结构设计 了一种全新的伪l r u 算法，实现简单，裹效可靠，从谣有效的保诞了c a c h e 的离翕中率。 此外，为了验证l r u 算法和一致性协议，我们在验证平台上做了相关的系统缀功能 模拟，逻辑模拟结果和设计初襄是吻合的。同时，还对一个完整的t a g 体做了详细的s p i c e 模拟，重点分析了判命中电路。 模拟结果表明：在o 1 8 “mc m o s 工艺下，以地址译码开始为参考点，到t a g 体中的 数据读出耗时为1 1 3 ”s ，到t a g 体向b a n k 体发出命中指示信号的时延仅1 4 8 ”s ，这一结果 使得当处理器的设计主频为2 5 0 膨时，c a c h e 数据的读写完全可以在半个时钟周期内完 成，很好的满足了x 处理器的需要。 关键词：c a c h e ，l r u ，替换策略，一致性，验证 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t 工nm o d e mm i c r o p r o c e s s o r s ，c a c h eh a s b e c o m i n g a 1 1 a b s o l u t e i yn e c c e s s a r y f u n c t i o n c o m p o n e n t ，i t ss p e e da n ds i z eh a sb e e n0 n eo ft h em a i nc r i t e r i o n st oe v a l u a t et h ep e r f b r n l a l l c eo f 王h i e r o p r o c e s s o f s + w i t h 也ei m p 羚v e m e n to f 鼎ep r o e e s s o f ss p e e dc o n t i 王l h o 璐l y ，t h cs 扎d yo fh o w t od e s i g na nc h et a gi n 向l lc u s t o mm o d ep r o v i d e sm o r ci m p o r t a n ts i g n m c a t i o l l n o to n i yi n n l e o d ，b u ta l s oi np r a c t i c e 0 n 也eb a s i so fd e e pr e s e a r c ho nc a c h et e c h n o l o g y ，t h i sp a p e rp r e s e n t s 也el o 西c a l ，c i r c u i t s a n dl a y o u td e s i g no f 龇t a gm o d u l ei nt h ed a t ac a e h eo ft h ex m i c r o p f o e e s s o r ，a c c o r d i n gt ot l l e s y s t e md e s i g nr e q u i r e m e m ，w h i c em a k e ss u r ct 1 1 a tt h exm i c r 叩r o c e s s o rc a ng e tt 1 1 ed a t a 丘o m t h ed a t ac a c h ei nac y c l ew h e nh i t 强e 陀a r e 妇e en 戚f e a t u f e si 珏妇p a p c f 。t h ef i f s to n ei s 妞如s i 辨o f 她es 印a r a t e t a g s t or e a l i z ea 3 - p o n e dt a g ，w h i c hr c s p e c n yr e s p o n s et ot h er e q u e s t so fup i p e i i n e ，vp i p e l i n ea 1 1 d s n o o p i n gb u s n l e s et h r e et a g sw o r ks e p a r a t e l y ，b u ti m p l e m e n tt l l e3 p o r t e dt a g sn m c t i o n t o g e t h e r t h es e c o n do n ei s 8d y n a f n i cc i r c u i td e s i g n e df o rl l i t 耍l d g m e n t ，w h i c hr e d u c e 娃】e c o m p 撕n gt i m e 鼎a 毕l y ，a n df i n a l l yat o t 甜l yn e wp s e u d o 己r um e e h a n 主s mi sp r o p o s e d ，w h i c h n o to n l ye f f e c t i v e ，b u ta l s oc a nb ee a s i l yr e a i i z e d o n 也es y s t e mv e r i f i c a t i o np l a t f 0 h n ，m e c t i o ns i m u l a t i o ni ns y s t e ml e v e la b o mm e p s e u d ol r u m e c h a n i s ma n dm 毯s ip f o t o c o li sl a k e n ，a f l d 盘ef e s u l t sc o n f o h nt ot h eo r 逗虹a l i n t e n s i o no fo u rd e s i g n s i m u i t a n e o u s l y ，d e e p l ys p i c es i m u l a t i o no nt h ee m i r et a gd e s i g i li s a p p l i e d ，a 1 1 dw ef o c u so nt h e s i m u l a t i o na n da n a l y s i so f t h eh “j u d g m e n tc i r c u i t t h eo u t p m so f m es i m u l a t i o ns h o w t l l a t ，o n t h cc o 删t i o n o f o 1 8 蚌m c m o s t e c h n o l o g y ，t 圭l e a c c e s s 畦m ei s1 13 n s ，妇曲l a y 删i lt h e “h i t s i g 划o u 肇u 撕n ge 恐c 缸e l yi sj 蜮1 4 9 n s ，w 毯c h m a k e s 也ex m i c r o p r o c e s s o rc a ne a s i l ya c q u i r ead a t af o md a t ac a c h e ，j u s ti nac y c l e ，w h e n 也e w o r k i n g 丘e q u e n c yi s2 5 0 m h z k e yv v o r d s ：c a c h e ，l r u ，r e p l a c es t r a l e g y ，c o n s s t e n c y ，v e r i f i c a l i o n 第i i 页 国防科学技术火学研究生院学位论文 图目录 处理器计算时间与访存时间的变化趋势2 毒储器和c p u 性自提裹攮况对毖图4 c a c h e 主存系统结构示意图5 主存地统构成示意图6 直接映射块地址构成图7 组相联方式下块圭| 甄址的构成示意图7 三种映象规则8 4 路组相联并行标识比较9 多处理器系统中的c a c h e 垃：存关系1 2 m e s i 状态转换图1 3 数据c a c h e 接日傣号图1 6 c a c h e 工作流程图1 8 三位记录位的l r u 算法逻辑图2 l 伪l r u 替换策略2 2 l l 几2c a c h e 的m e s i 状态转换图2 3 数据c a c h e 的逻辑结构示意图，2 6 三端口t a g 逻辑图2 9 存储单元版图示意图，3 0 t a g 逻辑位示意图( 一) 3 l t a g 逻辑位示意图( 二) 3 l t a g 总体逻辑组成示意图3 l t a g 标识存储体电路结构图3 2 m q d 型2 4 译码器3 2 两级译码结构图3 3 动态译码电路3 3 t a g 体4 路中同一位数据的存取电路图3 4 c a c h e 数据存储孽元电路与舨图3 4 存储单元写操作永意图3 5 存储单元读操作永意图3 6 t a g 体写入控制逻辑3 7 差分电压灵敏放大器3 7 差敬读出逻辑3 8 常用敏感使能信号生成电路3 9 第1 v 页 j 2 3 4 5石7堵9，2 3 4 6 7 ，2 3 4 s 6 7 8 9 m n他”褂强 ，2 2 2 2 2 2 2 2 2 3 3王王1王小屯禾电t t 重t 重t t t t t 重t t 图匪图图图图图图图图图图蓬图图露图图图闰图图匮图匿图匿图丽匿图图图 国防科学技术大学研究生院学位论文 图4 1 8 复制单元分布图3 9 图4 1 9c a c h et a g 比较命中判断逻辑图4 0 图4 2 0c a c h et a g 比较命中判断电路图4 0 图4 2 1 t a g 比较器电路4 1 图4 - 2 2 命中判断示意图4 2 图4 2 3 t a g 到体的输出指示形成电路4 2 图4 2 4 四输入的奇偶校验电路单元4 4 图4 2 5 异或门和同或门一4 4 图4 2 6 状态位存储器布局图4 4 图4 2 7 m e s i 位基本单元电路图4 5 图4 2 8 写修改位基本单元电路图4 6 图4 2 9l r u 位基本单元电路图4 6 图4 ，3 0m e s i 位存储体之版图4 7 图4 _ 3 1 字线保持逻辑图4 8 图4 - 3 2 字线布局图( 一) 4 8 图4 3 3 字线布局图( 二) 4 9 图4 3 4t a g 体版图4 9 图5 1 常规i c 设计验证层次图5 0 图5 2s p i c e 激励流程图5 2 图5 3 译码电路时序图5 2 图5 4 差放读出时序图5 3 图5 5 存储阵列读出时序图5 4 图5 6 命中指示输出电路时序图( 一) 5 4 图5 7t a g 到体的输出指示形成电路5 5 图5 8 命中指示输出电路时序图( 二) 5 5 图5 9 译码电路系统模拟时序图5 6 图5 1 0 伪l r u 算法的功能验证程序流程图5 7 图5 1 il r u 算法模拟示意图( 一) 5 7 图5 1 2l r u 算法模拟示意图( 二) 一5 8 图5 1 3l r u 算法模拟示意图( 三) 5 8 图5 1 4l r u 算法模拟示意图( 四) 5 9 图5 1 5m e s i 一致性协议验证程序流程图6 0 图5 1 6m e s i 一致性协议模拟仿真图( 一) 6 0 图5 1 7m e s i 一致性协议模拟仿真图( 二) 6 l 第v 页 国防科学技术大学硬究生豌学位论文 表目录 表3 ，1各种块大小的情况下c a c h e 的失效率1 9 表3 2改写l r u 自身状态过程中豹l r u 算法2 l 表3 3 读周期数据c a c h e 的m e s i 状态转换2 4 表3 ，4 写周粥数霸c a c h c 的m 嚣s i 状态转换2 4 表3 5 查询周期数据c a c h e 的m e s i 状态转换2 5 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方钋，论文中不包含其他入已 盔发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说欢芳表示谶意。 学位论文题目：熬鲞鱼! 煦羔! g 鲤全塞劁遮盐耋验堑 学位论文作者签名盔生日期：多k 7 年2 一月= 2 昭 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和偌阕；可以终学位论文鲤全都或部分蠹容编入有关数据库进行捡索， 可畈采j 拜3 影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：数量垒! 塾! ! g 鲤全基剑送鼓当坠堑 学位论文作者签名：二董叠 日期：抄年，2 月j 。日 一i ， 、 作者指导教师签名： 巫堡 未日期：，少三叫珲，上月。岛日 国酚科学技术犬学研究生院学位论文 第一章绪论 存储器是计算机系统的核心部件之一，其性能直接关系到整个计算机系统性能的高 低。现在的计算机系统一般都采用多级存储器结构，由上至下依次为寄存器、主存、磁盘、 光纛、磁带等，其特点是从外存储器到c p u 中的寄存器逐级向上，存储容量逐级减小，丽 存取速度逐级提商，价格越来越贵。由于上下两级存储器间的速度可以相差1 2 个数量级 或者更高，因此，两级之间的数据交换常常成为系统瓶颧，严重降低了系统的性能。 为了解决这个问题，通常采用的办法是在鼹级存镶嚣之间增加一个高速缓冲存储器 c a c h e 。如今，c a c h e 作为微处理器的一个重要部件，其大小和速度已成了衡量微处理器 性能的一项重簧指标。 l 。l 选遂背景 在当今的信息社会中，计算机系统已成为是整个信息处理的核心，作为知识经济的“脑 缨脆”豹处理器俨然成为这个社会的孩心中的核心，无所不在地分布在当代逯信设冬、溺 络设备等一切信息节点上。在这种趋势下，各个科技大豳都把研制高性能处理器作为其在 综合科技实力上竞争的一个热点，我国非常重视在这个领域的投入，每年微电子产业都以 大于3 0 的增长枣快速发展，但就总体而吉，这个产业仍处于起步阶段，与国际先进水平 褶比差距甚远。产量，j 、产品技术糕，设计能力、裁造技术、产品秘市场开发都缺乏努主 能力。微处理器虽然已有“方舟”、“龙芯”等几种型号，但其性能和相关应用还无法与 国外：占片竞争，总之国内所需微处理器几乎全部从国外进口【l 】。技术上受制于人不仅仅是 经济受损，罚虽对国家安全构成严重的隐患，困为大多数处理器芯片都套用户所不知道的 “艏门”，生产厂商对外公布豹指令集只是芯片所支持指令集的一个予集，掌握这魑“后 门”的人可以通过网络不费吹灰之力便获得所需信息。用这样的芯片构筑的信息系统显然 是毫无安全可富，因此研制开发自己的微处理器，已经追在眉睫。在这样的大背景下，我 们开始了一款邋羽高佳能微处理器芯片的磷发。 我们设计的微处理器是一款高性能处理器，它的研制顺应了我国科技发展的需要。对 这款芯片的开发，无论在高性能微处理器的体系结构，还是深亚微米设计方法学等相关领 域，部将是一次j # 常有意义的搽索。 项目中，我脊幸参与了此微处理器数据c a c h e 部件的研髑工作，主要负责c a c h e 的t a g 部分的研究和设计。c a c h e 作为计算机系统中的重要部件，其速度的快慢对系统有着至关 重要的影响。如何保证c a c h e 能以与c p u 棚当的速度为处理器提供数据，怎样保诞c a c h e 豹裔余中率等都楚值得礤究的课题。 在早期的计算机系统中，处理器与存储器的速度差距不是十分明强，因此早期处理器 ( 如i n t e l8 0 8 6 ) 是通过处理器接口直接读写片外存储器的。随着芯片制造工艺的发展， 第l 页 国防科学技术大学研究生院学位论文 处理器与存储器之间的速度差距越来越大，处理器直接访问片外主存储器将会造成大量的 c p u 时间浪费。图1 1 是2 0 0 1 年以来微处理器中计算时间与访存时间的变化趋势，在计算 时间不断减少的同时，访存延迟改善很小，处理器性能越来越受制于访存延迟。单从计算 速度来看，处理器拥有接近三倍的性能提升，但是整体性能提升却远不到三倍。为了解决 二者的速度差异问题，高性能处理器普遍采用了c a c h e 缓存技术，多级c a c h e 缓存构成存 储系统完成处理器内核的存储操作1 8 】，并通过系统总线或者d m a 通道访问主存储器。 c 为计算肿间m 为访存时同 图i 1 处理器计算时间与访存时间的变化趋势【2 】 c a c h e 作为近几十年来计算机体系结构上最重要的改进，己成为计算机系统结构和微 电子学等相关领域众多科技人员研究的热点。近些年来，随着工艺技术的进步和人们对高 性能孜孜不倦的追求，新的微体系结构、新的算法、基于新算法和新工艺的逻辑和电路结 构层出不穷。c a c h e 的设计有了显著的变化，结构不断优化，速度不断提高，应用也越来 越广泛。在高端的处理器中c a c h et a g 中存储的地址由最初的物理地址变为现在的虚拟地 址，按需要激活或休眠部分存储体等方法的提出大大的节省了c a c h e 的功耗口”。 为了确保设计芯片的兼容性和通用性，我们研究了大量的相关文献，并采取正反向结 合的设计方法实现微处理器的设计。我的毕业设计分三个阶段完成。第一阶段完成了收集 整理相关资料，并学习吸收样片数据c a c h e 部件的设计精华；反向设计和验证；第二阶段， 在第一步的基础上，依据对参考样片中数据c a c l l et a g 部件的深入分析、研究，找出了进 一步提高性能的途径，完成了从逻辑、电路到版图的自主设计；最后对我们设计的整个 c a c h et a g 部分做了系统级功能验证，并对单个t a g 做了详细的s p i c e 模拟。 1 2 课题研究的内容、成果和意义 本课题研究主要内容包括以下几个方面： 一、对c a c h e 相关技术资料的搜集、整理和研究，特别是关于s r a m 单元实现，存储 阵列的组织、读出放大电路及其时序控制的研究。 二、数据c a c h e 的标识( t a g ) 和c a c h e 数据存储体的设计。具体包括c a c h e 整体结构设 计、替换策略实现、c a c h e 一致性和可测试性设计等，重点分析了数据c a c h e 的t a g 设计。 三、利用系统级的功能验证验证了伪l r u 算法和m e s i 一致性协议，并对本文所设计 第2 页 国防科学技术大学研究生院学位论文 的数据c a c h et a g 的存储体进行s p i c e 模拟，重点对比较命中电路进行详细验证。 谦题研究的主要成果： 设计实现了一个其有完整逻辑功能的商效率数据c a c h e 的t a g 部件：系统级的功能模 拟验证了替换算法和一致性协议实现的正确性，整个t a g 模块的版图级s p i c e 模拟结果确 保了部镩工作辩序的有效性。 课题研究的意义： 、从我个人方面来讲，通过这次课题使我系统的研究了有关高速存储器的理论和具 体实现，同时把书本的理论知识与工程实践结合起来，在工程实践中迸一步得到巩固。 二、从课题研究成果的角度来讲有两方面的实际意义。首先是我们的微处理器项目研 制有缀强的现实意义，并为以后更裔性能的数据c a c h e 设计奠定了蒸础：其次是对有关存 储器的l p 核的开发有积极意义，本谋题研究设计的s r a m 存储模块稍作改动就可以是一 个i p 核，可壹接用在相关设计中。 l 。3 本文的组织结构 本文重点介绍了x 微处理器数据c a c h et a g 的逻辑结构设计、电路设计与优化、版图 布局、及其功能验证。全文共分六章： 第一章介绍了课题研究背景，课题研究内容、目的和意义及论文组织结构。 第二章介绍了e a 馥e 的作用和工作淼理及c a c h e 设计的关键技术。 第三章介绥了数据c a c 沁t a g 的逻辑设计，重点是其工作方式和主要参数的选择。 第四章介绍了数据c a c h et a g 的物理设计，重点在存储比较电路的逻辑和版图实瑗。 第五章介绍了对数据c a c h et a g 模块的版图级s p i c e 模拟和系统级的验证。 第六章对全文进行了总结和未来工作进行展望。 第3 页 国防科学技术大学研究生院学位论文 第二章c 8 c h e 设计技术 c a c h e 首先魑在i b m3 6 0 8 0 计算机上实现的，随着计算机体系结构的不断革新，特别是半导体加 工工艺水平的不断提高 c a c h e 技术也逐渐应用到p c 中。在8 0 3 8 6 时期出现外部c a c h e ；8 0 4 8 6 时期 开始有了盎帮仗8 的c a c h e ：p e u t i u m 对期有了分离建部l lc a c h e 帮外部l 2 c a e h e ；p 3 时飘经把l 2 c a c h e 集成到c p u 内部：在p 4 处理器中则使用了一种先进的一级指令c a c h e 一动态跟踪缓存，大大 提高了处理器的运算效率。 e a c h e 作为提寒c p u 性能的震要帮 牛，随蓑c p u 豹发展翅不断改进的过程可鞋概括为：鼠无有， 由小到大，先外霜肉，纵深配备，软硬兼施。 2 1 1c a c h e 的引入 2 1 通用微处理器c a c h e 概述 睾矮的计算机系统中，处理器的计算速度和访存速度相差不大，处理器可戬直接读写 片外存储器。随着体系结构和半导体工艺的进步，近十多年来，c p u 的性能提高褥很快， 在t 9 8 0 年至1 9 8 6 年之间，c p u 是以每年3 5 的速度递增，而从1 9 8 7 年开始，c p u 性能 则是以每年提高5 5 ，但是熏存性能的提高却慢得多，d r a m 的速度每年仅提高7 5 】， 如蔫2 1 所示。因此，c p u 和主存之闻在性缝的差距上越来越大，形成了所谓的访存瓶颈 问题，现代计算机大都采用c a c h e 技术来解决这一难题。 ， 芦 一。妙一一 1 9 8 0 1 9 8 51 9 9 01 9 9 5 2 0 0 0 年份 r 。“。“”1 。1 1 一 口存储器 c p u i 图2 ，i存储器和c p u 性能提高情况对比图 c a c h e 也叫高速缓冲存储器，是一个速度等于或接近于上级存储的小容量存储器。它 和用程序的局部牲原理，保存下级存储器网l 剐被访闼过的数据及其邻远小范围的数据，使 樽以后的多次访问在高速的c a c h e 中有很高的命中率，从而大大减少实际访问下级存储器 的频度。这样，由c a c h e 和下级存储器组成的存储系统与原下级存储器相比，访问方式不 第4 页 搬蝴 瞄 咖 渤 加 。 * i 3 2 l 国防科学技术大学研究生院学位论文 变、容量不变、每位成本稍贵，但实际的平均存取速度接近于上一级存储器，从而大大的 改善了计算机系统的性能。 21 2 片上c a c h e 的工作原理 图2 2 给出了一个位于c p u 与主存之间的c a c h e 模型。c a c h e 的容量与主存相比是很 小的，相差2 3 个数量级，目前在主存容量配置是几百m b 到一个g b 的情况下，c a c h e 的典型值是1 2 m b 。c a c h e 的工作速度很快，一般接近于甚至同于c p u 速度。由图可知， c p u 与c a c h e 之间的数据交换是以“字”为单位，而c a c h e 与主存之间的数据交换是以“块 为单位，一个块由若干个字组成，是定长的。 物理地址 c p u上 主存 圭 fc a 。h 。 垫 图2 2c a c h e 主存系统结构示意图 当c p u 试图读取主存的某个字时，向地址总线发出存储有此字的内存地址( 物理地址) 到c a c h e 和主存，此时c a c h e 控制逻辑依据地址判断此字当前是否在c a c h e 中。若是，此 字立即由c a c h c 递交给c p u ，否则，要用主存读取周期把这个字从主存读出送到c p u ，同 时将含有此字的整个数据块从主存读出送到c a c h e 中。由于程序的存储器访问具有局部性， 为满足当前一次访问请求而取来的一个数据块，下面的多次访问很可能是读取此块中的其 它字，从而大大加快了c p u 的访存速度，提高了系统性能。 在一个程序执行期间，我们用札表示由c a c h e 完成存取的总次数，。表示由主存完 成存取的总次数，那么可将命中率( 1 1 i tr a t i o ) 日定义为： 日： 丝 ( 2 】) n c + n 。 则l 日为失效率( m i s sr a t i o ) 。若以表示c a c h e 命中时的访问时间，0 表示未命中 时的主存访问时间，则c a c h e 主存系统的平均访问时间t ，为： = h f 。+ ( 1 一日) m 。 ( 2 2 ) 于是，若用部件加速比来表示，则c a c h e 部件的加速比 第5 页 国防科学技术大学研究生院学位论文 c 刮p 丽靠2 志4 南旺s ， f ” 可见，提高c a c h e 的命中率能大大加速c a c h e 部件的执行效率，从而提高整个系统的 性能。当然，命中率是一个徽复杂的问题，它不仅与程序的行为有关，还与c a c h e 的设计 存很大关系，如c a c h e 的级数、容量、缀织方式、块大，l 、等。 2 2c a c h e 的组织结构 c a c h e 是按缺进行组织管理的。c a c h e 和主存均被分割成大小相同的块，每个块由若 干个字组成，信息以块为单位调入c a c h e 。相应地，c p u 的访存地址也被分割成块地址和 块内偏移两部分，如图2 3 所示： 主存地址： 块地址c 标识和索引，块内偏移 图2 3 主存遗址构成示意图 块地址用予查找该块在c a c h e 中的位鬻，包括标识( t a g ) 和索引( h d e x ) 两部分， 块内偏移用于确定所访问的数据在该块中的位置，同时表明了块的大小。 由于c a c h e 的容量比下级存储器小l 2 个数量级，要保证c a c h e 高效工作，必须考虑 以f 趣遂： 1 、存储映像：当把一个块调入c a c h e 时，可以放在哪个位置上 2 、查找算法：当所需要块在c a c h e 中时，如何找到该块 3 、替换算法：采用俘秘替换策略，使褥访润c a c h c 的鑫中率最籀 4 、写策略：当进行写访问对，应进行哪些操作 5 、一致性协议：如何保证c a c h e 和下级存储器的数据具有一致憔 这里先看着与c a c h e 组织结构相关的存储映像、查找算法和替挟规则，写策略和一致 性协议将在下节阐述。 2 2 1c a c h e 的存储映像 一般来说，主存容量远大予c a c h e 的容羹。因此，当要把一个块从主存调入e a c h e 时， 就有个如何放嚣的问题，这正是映象规则所要解决的。映象规则主要有三种：全相联映像 法、直接映像法和组相联映像法【3 “、5 j 。 塞接睽像 直接映像是最简单的一种方法，是指主存中的每一个块只能放到c a c h e 中唯一的一个 地方。如图2 6 ( a ) 所示，图中箭头的虚线表示映象关系。例如，主存的第9 块只能放入 第6 页 国防科学技术大学研究生院学位论文 c a c h e 的第l 块的( 9m o d8 ) 位置。作为一个例子，网2 6 中画出了c a c h e 大小为8 块、 主存大小为1 6 块的情况。实际的c a c h e 常镪含几百个块，而主存则一般包含上百万个块。 一般的，对于主存的第i 块( 即块地皱为i ) ，设宦映象到c a c h e 的第i 块，则 j = im o d ( m ) 其中m 为c a c h e 的块数( 此例中是8 ) 。设m = 2 “，则当表示为二二进制数时，i 实际 上就是i 的低m 位。如图2 4 掰示： 主存块地址i ， 翻2 4 直接妖射块地址构成圈 因此，可以直接用主存坟地址的低m 位去选择直接映像c a c h e 中的相应块。 全相联映像 全相连陕像是指主存中的一块霹以毅放置到c a c h e 中的任意一个位置的方法。鲡图2 ，6 ( b ) 所示。例如图中的第9 块可以放到c a c h e 中的任意位置。因为块地址也保存在c a c h e 的标识中，因此一个主存块可以拷贝到c a c h e 中的任意位置。此法的优点是映像灵活，命 中搴高。不足是硬件实现较为隧难，主要是医为相联度越高，全比较输出代价离，速度慢。 组相联映像 组相联映像是上述两种方法的折衷方案。其基本思想是把c a c h e 分为m 组，每个组分 为n 块。主存块分配时对组是难一的，目g 豢接映射方法；在组内的位置可以任意，即全相 联浃对方法。这样，主存中静每一个块可以镀放置到c a c h e 中难一的一个组中的任俺一个 位镊。如图2 6 ( c ) 所示。 组的选择常采用位选择算法，即：若主存第i 块映象到c a c h e 的第k 组，则 k = i m o d ( g ) 其中g 为c a c h e 的组数。设g = 2 8 ，则当表示为二进制数时，k 实际上就是i 的低g 位，如下所示： 主存块地址i ： k 图2 s 组相联方式下块地址的构成示意图 因此，可良赢接用主存决地址的低g 位去选择组檑联c a c h e 中的镯应缝。 第7 页 垦堕型兰垫查查鲎翌垄尘堕堂垡笙茎 ( a ) 直接映射( b ) 全相联映射( c ) 组相联映射 图26 三种映象规则 在上述三稚软象规刚中，全相联映象的c a c l e 空闻零j 用率最高，块冲突率最低，因而 c a c h e 命中率最高，但其实现硬件开销大，特别是全比较电路实现的代价高，很少被应用。 直接映象由于每个主存块只肖一个固定的位鼹可存放。两个索引相同的块往往容易发生冲 突，导致失效率较高，僵由予荚硬件结构筠零，成本鬣，使用褥毙较蛰遍。缓摆联则是集 前两者之优点，性价比较高，使用得也相当广泛。 2 2 2 查找方法 当c p u 访问c a c h e 对，如何确定c a c h c 中是否有所要访问的块? 若有的话，如何确定 其位置? 这是通过查找目录表来实现的。c a c h e 中设有一个目录表，该表所包含的项数与 c a c h e 的块数相同，每一项对应c a c h e 的一个块，用于指出当前块中存放的信息是哪个主 存袭的。它实际上记录了主存块的块遗址的葱位部分，称为标识n g 。c a c h e 中每一个块 只能由其标识唯一确定它是主存的哪一个块。 为了指出c a c h e 中的块怒否包含有效信息，一般在目录表中给每项设置一个霄效位。 铡翅，当该位为“l ”时表示：该目录矮肖效，也就是说c a c h e 中相应块所包含斡信息有 效。当一个主存块被调入c a c h e 中菜一个位置时，他的标识就被填入目录表中与浚c a c h e 块对应的项中，并且该项的有效位被置“l ”。 根据映像规则的不同，一个主存块可以映像到c a c h e 中的一个或多个候选位置。当c p u 访问该主存块时，必须且只需查撬它的候选纽鬟所对应l ：l 句标识郄可。妇果有与所访闻的主 存块相同的标识，且其有效位为“l ”，则它所对应的c a c h e 块即魁所要查找的块。为了 保证速度，对各候选位置的所对应的标识的检鹰比较应并行进行。因此候选位置越多，实 现褒找豹极制裁越复杂，代价就越高。 燕8 页 善防科学技术大学研究生院学位论文 目泶袭 ( 标识存储嚣) 黼2 74 路组相裁并行标谖眈较 蠹接映象c a c h e 的候选憾置少，只有一个：全棚联c a c h e 的候选位置最多，为m 个； n 路缀根联则介予二霍之阉，为n 个。并行查我的实现方法蠢掰种：( 1 ) 熙楣联存储器( e a m ) 实现；( 2 ) 用单体多字存储器和比较嚣寒实现。图2 。4 中画寤了用第二种方法实现4 路组 相联的情况。这时需要4 个比较器。c p u 访存时，用本次访存地址中的索引i n d e x 从标识 存储器中选取一行( 对应予组) ，并从该行读出4 个标识，然后将它们与本次访存魄垃 中的标识t a g 进行并行魄较。根据比较结采确定是否命中以及该组中哪一个块是要访阏的 块( 若命中) 。嚣束命中，剡囱外发出c a c h em i s s 指示，启动所需块的调入。 由图中可以磊出，n 越大，实现查找的桃制就越复杂，代价就越离。煮接映象的c a c h e 的查找最简单：只需霾找一个位置即可。所访阉的块要么就在这个位受上，要么不在c a c h e 中。 无论是赢接映象还是组相联，查找时只需比较t a g ，i n d e x 无需参加比较。这是因为 h l d e x 避被翻来选择要套找豹组或块，雨所有索弓| 相同( 置只有索；| 捐丽) 的块都被跌翦圣 到该组中。所以，该组孛存放的块的索霉| 一定与本次谤存的i 珏d e x 相间。如果c a c h e 的容 量不变，提高褶联度会增掬每一组中静块数，从而减少猿d e x 的位数和增加t a g 豹僚数。 当采用类似予图2 4 的并行比较方案时，不仅所需的比较器的个数随之增加，瓤且比较器 的位数 熟随之增大。在全棚联的情况下，l n d e x 的位数为o ，块地址全都用作为t a g ，此踺， 多采用c a m 结构来作b e 较。 2 2 ，3 替换策酶 由于c a c h e 的容量总是远小于下一级存撩嚣的容量，因此c a c h e 中炅能是下级存储器 的部分拷贝。所以当要从主存调入一个块到c a c h e 中时，会出现该块所映像到c a c h e 中的 位置恰好被占用豹情况。这时就需要强追调出c a c h e 中的菜一块，以便腾蠢空| 嘲，调入当 前需要的内存块。那么巅筑斑该调出哪块昵? 这就涉及到替换策潞的润题。 直接映缘c a c h c 中的替换撮简单，因为只鸯一个块，别无选择。瓶在缀相联和全糯联 c a c h e 中，则有多个数据块供选择，这就需要一个比较好的算法，如果算法选择不当，将 第9 页 翻防科学技术大学研究生院学位论文 大大增加调入调出的频度。例如把一个当前不需要但是很快就将使用的行调出，必然会降 低系统的效率。常用算法有随机法、有先入先出( f i f o ) 算法、最不经常使用( 己f u ) 算 法、最近最少使羽( l r u ) 算法等h 硝f 1 3 ：l 。 随机法 就是为了均匀使用一组中的各块，随机地选择被替换的块。这种方法的优点是简单、 易于硬件实现，健这魏方法没有考虑c a c h e 块过去被使用憋清况，反欢不了程窿的局部惶 原理，所以失效率比l r u 高。 先入先出f i f o ( f i r s t i n _ f i r s t 0 u t ) 先入先出算法依据进入c a c h c 的先盛次穿来替换，先进的块首先救替换捧。这秘方法 的优点是容易实现。它虽然稠用了同一缀中各块进入c a c h c 的顺序这一“历史”信惠，但 不能正确反映稷序的局部性。因为先进入的块，很可能是经常要用到的块。 最不经常使用算法( l f u 算法) 该方法的恩葱是把最近一段对间内被访瓣次数最少魏行调出。霆l 毙实瑰时需要对每一 个行设置一个计数器对该行的访问次数计数，在需要替换时比较各个计数器的值，淘汰计 数次数最少的数据行。这种算法的问题是明显的，那些在程序前期被频繁访问而在后期不 露使用的行，可能会在相当长的时闻内不会被淘汰，丽那些刚嚣0 调入并将继续反复使用的 行剐可能因为其计数器中的夔较小面颓遭淘汰，这将严熏影响系统的效率。 最近最少使用算法( l r u 算法) l r u 算法的思想是将最近一段时间内最少被访问的块淘汰出局。闲此也需要为每行设 置一个计数器、但是计数方法与l f u 算法不同。基u 箨法是把命中露的计数器瀵零、其 它各行计数器加l 。当需要替换时，比较各行的计数器值，淘汰数值最大的行出局。这种 方法所依据的是程序局部性原理的一个推论：如果最近刚用过的块很可能就是马上露用到 的块，则最久没用过的块就是最佳的被替换者。 在上面介绍的四释算法中，l r u 算法比较符合e a c h e 工作原理，爽效率是最 螽的，是 c a c h e 设计中最常使用的方法。但l r u 算法硬件实现比较困难，特别是当组的数目增加时， 完念l r u 的实现代价越来越离，因而经常只是近似地实现【3 4 l 。 2 3 写策略与一致性协议 按照存储层次的要求，c a c h e 内容应是主存部分内容的一个副本。但是“写”访问却 有可能导致它们内容的不一致。铡如，当处理器进行“写”访问，往c a c h e 写入新的数据 后，则c a c h e 中相应单元的内容已发生变化，而主存中该单元的内容却仍然是原来的。这 就产生了所谓的c a c h e 与主存内容的一致性问题。显然，为了保证正确性，主存的内容也 必须雯耨。至于俺时更薪，这就是写簧略掰要解决的润憨。 2 3 1c a c h e 写策略 第1 0 页 国防科学技术大