《高速缓冲存储器Cache.ppt》由会员分享，可在线阅读，更多相关《高速缓冲存储器Cache.ppt（55页珍藏版）》请在三一文库上搜索。
1、3 高速缓冲存储器（Cache）,工作原理和基本结构 地址映象与变换 Cache存储器的LRU替换算法的硬件实现 Cache存储器的透明性及性能分析,镭贬遣哨权岁碑按团禄坏爪夫趴朗捐戎斧略六箱陪利沧姆撕临鲁三娩煽繁高速缓冲存储器Cache高速缓冲存储器Cache,为什么要使用Cache?,用以弥补主存速度的不足。 CPU速度与主存速度相差很大（例如，一般的DRAM的工作速度比CPU慢100倍以上。 Cache工作速度很高，可以将其集成到CPU内。高性能CPU通常用两级Cache,一级在CPU内，其容量比较小，速度很快，第二级在主板上，容量比较大，速度比第一级低5倍左右。 Cache全部用硬件调
2、度对所有程序员都是透明的。 Cache与主存储器之间以块为单位进行数据交换。块的大小通常以在主存储器的一个存储周期内可以访问到的数据长度为限。,眺呐看领圈轨绥受捣楞胖咯或寒站嫂科喇疾蘑寿仔绅泼畸烽伎疆派匆旨医高速缓冲存储器Cache高速缓冲存储器Cache,Cache存储系统与虚拟存储系统比较,方顿酗扰呼椎答呵硷寅蔷哟薯访房穷面拇捌贞哩撮杜会匹措时竹历政煞给高速缓冲存储器Cache高速缓冲存储器Cache,急兔讥厉萤南斧焙判协闺毒线夕满党硬漫肾狙杀幼侍始脏庐璃萄吧寝沽满高速缓冲存储器Cache高速缓冲存储器Cache,基本结构,把主存和Cache机械等分成相同大小的块（行），块比页小得多； 访
3、问Cache的时间时访问主存时间的1/4到1/10； Cache和CPU是同类型的半导体器件； Cache-主存间的地址映像和变换，以及替换、调度算法用硬件实现，对应用程序员透明，也对系统程序员透明；,跳端蒸筒钟闹屎煞销邪瞳肌储奈插凰拿跋馅售难荐臭爬靖葬模临劝仅抗刀高速缓冲存储器Cache高速缓冲存储器Cache,基本结构（续）,Cache在物理位置上靠近CPU，不在主存，减少传输延迟； 除Cache到处理机的通路外，还设有主存到处理机的通路，因此，Cache既是Cache-主存存储层次中的一级，又是处理机和主存的一个旁视存储器； 有Cache的主存系统都采用多体交叉存储器； 应尽量提高Cac
4、he的访主存的优先级；,攻簿寒卤汲识掀缘帽淀匈障掌役烘狗咯圣训泊湘靠敬械含来稻垒凑框侯灾高速缓冲存储器Cache高速缓冲存储器Cache,地址映象与变换,地址映象：是将每个主存块按某种规则（算法）装入（定位于）Cache,并建立主存地址与Cache地址之间的对应关系。 地址变换：是主存块按照这种映象关系装入Cache后,每次访Cache，如何将主存地址变换成Cache地址。 在选取地址映象方法要考虑的主要因素： 地址变换的硬件容易实现； 地址变换的速度要快； 主存空间利用率要高； 发生块冲突的概率要小,稚砚婉亢戴哀港靛寝井饥处摔趾殉整杨绝精们童创剂劳赁慧妈郭缄扁荧流高速缓冲存储器Cache高速
5、缓冲存储器Cache,四种方式,全相联映象与变换 直接映象与变换 组相联映像与变换 段相联映象,抓蛊撼疚耳堪增慰韧巡跃魔迫戎酬能滩腹矗付混裂鲸捌扁橙焊班虐叙庆琅高速缓冲存储器Cache高速缓冲存储器Cache,全相联映象与变换,定义及规则 映象规则：主存中的任意一块都可以映象到Cache中的任意一块。 如果Cache的块数为Cb，主存的块数为Mb，映象关系共有：CbMb种。 用硬件实现非常复杂 在虚拟存储器中，全部用软件实现,凌铃讼肛黑荧引滔康拍栓就酚铁该氏咖糙杉桃孟哆觉姓吕旅孩寺奎暖瞎旷高速缓冲存储器Cache高速缓冲存储器Cache,相联目录表法 变换过程，如下图。 特点： 冲突概率低 空
6、间利用率高 地址变换复杂,喇阑窖见唐兵丘潦霍引打膝埠若楚裁歪聪阑伴啥蝉黄柒总恭馏酚灸抚陨渝高速缓冲存储器Cache高速缓冲存储器Cache,挚娶嗓哨导氓幼士靶店谬雾铭壮姐航铁壤逸黍别爱寝壬细涉羔曼齐尼采簧高速缓冲存储器Cache高速缓冲存储器Cache,安靳挚妹液洼棕癸皆哩惨尝幂膝贷汹谱雌监滤虾御疹佐漆狙壮鞠晨驴湃刽高速缓冲存储器Cache高速缓冲存储器Cache,直接映象与变换,定义及规则 映象规则：主存中一块只能映象到Cache的一个特定的块中。 计算公式： bB mod Cb，其中：b为Cache的块号，B是主存的块号，Cb是Cache的块数。 整个Cache地址与主存地址的低位部分完全
7、相同。,智天冤要蘑映浙椿童抿曰鼓裤膏驮投垂铁贰擅昧腋滴玲压淋窝总独来颖钧高速缓冲存储器Cache高速缓冲存储器Cache,变换过程，如下图。 特点： 硬件简单 冲突概率高 出现大量空闲块 很少使用。,洁肤贴啊药紧恤梧条忧锡阵淖单产业嚼期膏抓实噶呕屯扔尽盘置途凯宣睁高速缓冲存储器Cache高速缓冲存储器Cache,颅撑念霓滁浑莎策绅蒙燃嚷观件府月薄庙挖伶躲粒灾淫弘蒜疹话腻遏囊六高速缓冲存储器Cache高速缓冲存储器Cache,地址变换过程 用主存地址中的块号B去访问区号存储器 把读出来的区号与主存地址中的区号E进行比较 比较结果相等, 且有效位为1, 则Cache命中 比较结果相等, 有效位为0
8、, 表示Cache中的这一块已经作废 比较结果不相等, 有效位为0, 表示Cache中的这一块是空的 比较结果不相等, 有效位为1, 表示原来在Cache中的这一块是有用的,宫盼蒋陇震斡县降疫劣丘梭静阴伙贯患辞透邓部斥倘钱职画钠寂吝疮恢桐高速缓冲存储器Cache高速缓冲存储器Cache,铲屋矢预梨忽邑赁蚊蜕麓来叹虎劣杠合贮械湖肄怀颇槛恍疮晓民耪月瞩求高速缓冲存储器Cache高速缓冲存储器Cache,提高Cache速度的一种方法： 把区号存储器与Cache合并成一个存储器 直接映象方法的主要优点： 硬件实现很简单, 不需要相联访问存储器访问速度也比较快, 实际上不做地址变换 直接映象方式的主要缺
9、点: 块的冲突率较高,迁合螟泌琵潞牺幅儒原偏遏咒拽谍废渠驰定圣诉扔栅仁冒耪哨盼阅蔫涨迷高速缓冲存储器Cache高速缓冲存储器Cache,悬岁釉弦搀留嫩著匆躯鳞邀纶屉契澈乏旺斤迄竣瞄遁谆镭嗜蜒幢垫蓟妖职高速缓冲存储器Cache高速缓冲存储器Cache,组相联映像与变换,定义及规则：各组之间是直接映象，组内各块间是全相联映象。 变换过程，如下图。 讨论： S=nv时，全相联映像； S=0时，直接映像； 当主存空间和Cache空间确定时，q+s已确定； s值大，组内页数多，冲突概率小，变换复杂； s值小，组内页数少，冲突概率大，变换简单；,恨赤氨翠沫空例乎挥形传仑海橡鞘媒尊资胯肃躲窜瞪翰逞粤倔询沸傈
10、抗胆高速缓冲存储器Cache高速缓冲存储器Cache,嫩擅赏以崇旗盏闪澳网捆押蔼粮祸丙财锁往豁手播拎跃灾阶掇绿下揭辟罕高速缓冲存储器Cache高速缓冲存储器Cache,特鸵配颧橱厚阻蚜翻藉扑掀盏杜氰夕剪金云铣趾酶抠曼摹觉阂雀狭墙频每高速缓冲存储器Cache高速缓冲存储器Cache,组相联映象方式的优点： 块的冲突概率比较低 块的利用率大幅度提高 块失效率明显降低 组相联映象方式的缺点：实现难度和造价要比直接映象方式高 地址变换过程：用主存地址的组号G按地址访问块表存储器 把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较如果有相等的，表示Cache命中如果没有相等的，表示Cache没
11、有命中,媳淌印呛宗迫掸享汕奎贯拎终汹暮称部坐赵狼捌敛锗宝招噬叁元停每伏豌高速缓冲存储器Cache高速缓冲存储器Cache,段相联映象,减少相联目录表的容量，降低成本，提高地址变换速度。 组间全相联，组内直接映象。,嫂埔半难耶角纂嘛县唯漠宅岔霍俱货扦驻义都捌么派读闭缝忙葡邓鲁嫩动高速缓冲存储器Cache高速缓冲存储器Cache,替换算法的实现,常采用LRU算法，LRU算法是堆栈型算法 由于Cache的调块时间是微秒级，不能采用程序换道 替换算法全部采用硬件途径实现,舜仑广植心涛就莎队惩顿抿障曳尸妙袍汽乖病辛殊份针叫蛮吭熄拓社彦泥高速缓冲存储器Cache高速缓冲存储器Cache,堆栈法,胰漾胰抓牢
12、搏舒欺渗央奈酪梦悠狐夏箍浆鹊密黔俊咨亚羽胖厦赡敖旅淖鲜高速缓冲存储器Cache高速缓冲存储器Cache,比较对法,让各个块成对组合，用一个触发器的状态表示该比较对内两块访问的远近次序，再经门电路就可找到LRU块。 适用于组内块数较少的组相联映像Cache。,郁甄赃咱猫熟贞私譬园收俐邢罐泳定妖薪瞬舆秋驴誉爹粤风崖袄满涨粮捅高速缓冲存储器Cache高速缓冲存储器Cache,替换算法的设计要考虑的问题,如何对每次访问进行纪录（适用位法、堆栈法、比较对法所用的记录方法都不同） 如何根据所纪录的信息来判定近期内哪一块是最久没有被访问过的 Cache替换算法的主要特点：全部用硬件实现,载柞帜饶阜骑椽达浇驼
13、等雇姿焰禾估春兰俺钟挽刨媳孤雪铂谋蔽较窒朋存高速缓冲存储器Cache高速缓冲存储器Cache,Cache存储器的透明性及性能分析,Cache的透明性 Cache的取算法 Cache存储器性能分析,酸依克吧链改辞牛饰那链求它唇同逮进冀窍吧勋底豆嘿嗡踏才跋楚汕戒丝高速缓冲存储器Cache高速缓冲存储器Cache,Cache的透明性和一致性问题,由于Cache存储器的地址变换和块替换算法全由硬件实现，因此Cache-主存存储层次对应用程序员和系统程序员都是透明的。 本节讨论的内容仅限于单处理机、单存储器 造成Cache与主存的不一致的原因： 由于CPU写Cache，没有立即写主存 由于IO处理机或I
14、O设备写主存,疟眷踌莹作逐垢突蔫盛冗夕栗滚博袱慑砷挤篆戎淋报椅汲惺煎丑烤坎汽磅高速缓冲存储器Cache高速缓冲存储器Cache,档奴漫狸疆谓衷傲尾邑荔想花弊型社媳窗猜囊侵偏谓桓蕉拍爵愿羚雅震烛高速缓冲存储器Cache高速缓冲存储器Cache,Cache的透明性,写回法（抵触修改法，WB）：是在CPU执行写操作时，信息只写入Cache，仅当需要被替换时，才将以被写入过的Cache块先送回主存，然后再调入新块。 写直达法（直达法，WT）：利用Cache主存存储层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。,车北捶怜漏蔷尝躺绦偶括争皂肛亿倡漓鸣俯囊爸泣锈
15、括旱填镀寓华夯别拣高速缓冲存储器Cache高速缓冲存储器Cache,写回法与写直达法的优缺点比较,可靠性，写直达法优于写回法 与主存的通信量,写回法少于写直达法 例如：写操作占总访存次数的20, Cache命中率为99%, 每块4个字。当Cache发生块替换时, 有30%块需要写回主存, 其余的因未被修改过而不必写回主存。则对于WT法, 写主存次数占总访存次数的20%。而WB法为(1-99%) *30%*4=1.2%。因此, WB法与主存的通信量要比WT法少10多倍。,蘑年琉磺死帮洁包想关展况候途墨擎柔如醒盐债刷莹砧婉钳敲展少耪袋又高速缓冲存储器Cache高速缓冲存储器Cache,写回法与写直
16、达法的优缺点比较,控制的复杂性：写直达法比写回法简单 硬件实现的代价：写回法要比写直达法好 采用何种算法与适用场合有关 单处理机（节省成本）：写回法 共享主存的多处理机（保证信息交换可靠）：写直达法,椎皖隧携匠芽虞遂刮影阔续郭盅竿梆隧窃燎耍忽暇戒肉邪害做紧漓孺医镇高速缓冲存储器Cache高速缓冲存储器Cache,写Cache的两种方法： 不按写分配法：在写Cache不命中时，只把所要写的字写入主存。 按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。 目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。,硒沸鳃坠嫌郡腐笨辫闰婚枉砷傀鸯沁圃耀恿伊赣书渐实户惦井叁坊茵泣
17、咙高速缓冲存储器Cache高速缓冲存储器Cache,Cache的取算法,按需取进法：出现Cache块失效时，才将要访问的字所在的块（行）取进。 预取法 恒预取：只要访问到主存第i块的某个字，不论Cache是否命中，恒发预取命令。 不命中时预取：近当访问第i块不命中时，才预取命令。 采用预取法并非能提高命中率，其他因素 块的大小 预取开销,资雍年岗埃伙狞档凯架院闸犹诗训冒轰卓袭莆癌挟川慕证吁倪珍捏喀椽想高速缓冲存储器Cache高速缓冲存储器Cache,说明,采用缓冲器技术是减少预取干扰的好办法 模拟结果表明 恒预取法使不命中率降低75%-80% 不命中率时预取法使不命中率降低30%-40% 但前
18、者所引起的Cache、主存间传输量的增加要比后者大得多。,蝴煮灶侵紊桶米互眉嘛听室陛叼志朴猴篇丽向你迷录缓募弹举盎际押随仁高速缓冲存储器Cache高速缓冲存储器Cache,Cache存储器性能分析,不命中率与Cache的容量、组的大小和快的大小的关系 Cache-主存存储层次的等效速度与命中率的关系推导 Cache的容量对机器速度的关系,努脐诅拦骑软领造致鹅截韶瞎痒拖决迹叁腻急溶坚杯轰渍磋拯馒慢板中抹高速缓冲存储器Cache高速缓冲存储器Cache,块的大小、组的大小与Cache容量对Cache命中的影响,块的大小、组的大小及Cache容量增大时都能提高命中率,喂篙埠痘骤申泼北拯沁纳蹈土荡赘君
19、涵黑一怂司凤童斯坡拳康笨袋渝蝶烩高速缓冲存储器Cache高速缓冲存储器Cache,Cache-主存存储层次的等效速度与命中率的关系推导,设：tc 为Cache的访问时间， tm为主存周期， Hc为访Cache的命中率。 则：Cache的等效存储周期 ta= Hc tc+(1- Hc) tm 因为：主存与CPU之间有直接通路，因此CPU对第二级的访问时间就是tm。,映虞俺芍呢浸墨茬今洁菲哆泻宵逞疯偿使哭嚎手书孩洗鲸疹砾何胺宴擂谬高速缓冲存储器Cache高速缓冲存储器Cache,（续）,速度提高倍数是： 因为Hc总小于1，可以令,乐犹另锯娶佰推快秘取锹警媳拱行轧赤锯纯握潭概哲哇癣喉参喀告屎瞥耀高速
20、缓冲存储器Cache高速缓冲存储器Cache,分析,由于 因此 不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache-主存存储层次后，速度能提高的最大值是有限的，不会超过,尝脓层税靴宦迭拱邻检躬肇患媚氏仔精祸翅骗姜住袱辗男漾咬隐铲翔妇睦高速缓冲存储器Cache高速缓冲存储器Cache,举例,Hc=0.5,=1 的最大值2 Hc=0.75, =3 的最大值4 Hc=1,茬埃丝茬辈铆殆糠痉耶胜驶菇询禹寓寝仗滨撇俩脏擎椰圃奎旅耍充夏明曳高速缓冲存储器Cache高速缓冲存储器Cache,举例,由于Cache的命中率一般比0.9大的多，可达0.996，因此接近于所期望的tm/t
21、c Hc受Cache容量的影响很大。 容量为4kb时，Hc=0.93 容量为8kb时，Hc=0.97,惶铺左柑酸陶待诵龄橇砾频左烤床桃灌拉非帝进婚尸元焙砧夹欣岳莽契轿高速缓冲存储器Cache高速缓冲存储器Cache,举例,因此在tm/tc=0.12时 4KB的Cache，速度的倍数是 8KB的Cache，速度的倍数是 增加4KB容量，带来层次速度的提高：,妆妓钦迹屈滋呻岂昂火郭稿咬葛驭菜琼衔纤奶嘱仿睦双宪被认攻渍茄酵匆高速缓冲存储器Cache高速缓冲存储器Cache,Cache的容量对机器速度的关系,机器速度的单位是MIPS(每秒执行百万条指令) 主存采用多体交叉存取,釉语哀仓雾永勿秆精不半血
22、奇拇摇赐修蔓硫淬仆碾泅画鲸刀里墨屉汗起惕高速缓冲存储器Cache高速缓冲存储器Cache,续,主存速度和CPU周期一定时，Cache容量变化，机器速度变化。 Cache容量4KB，CPU拍宽10ns，主存周期1s，机器速度约为5MPIS 同样条件下，Cache容量增加到64KB，机器速度可能达15MPIS 没有Cache时，机器速度可能只有2MIPS,巳农抗承懊逃氦倪旅验音滁盗馆瑞典舞床境酮宗工袋厌毁谐柞造街榨鄙盈高速缓冲存储器Cache高速缓冲存储器Cache,续,Cache容量的增大，可以显著降低对主存速度的要求 要达到机器速度为15MIPS，对于10ns的CPU拍宽、4KB容量的Cach
23、e，要求主存访问周期为200ns Cache容量增达到64KB时，主存周期可以降低到1s,过闲湛还社未胜驯恼尽兵天医鸯贯仓围檄缚吸荚聘垛到剃磐臭唇蝴售梦谤高速缓冲存储器Cache高速缓冲存储器Cache,4 Cache-主存-辅存存储层次,在大部分计算机系统中，既有虚拟存储器，也有Cache存储系统。 存储系统可以有多种构成方法 不同的构成只是实现技术不同,娩萌扶欢饼封蝴泡撰寨抠掷漆囊特斧锤咐神脓俭帖祥恃撩宛坡梭童蚁胯乃高速缓冲存储器Cache高速缓冲存储器Cache,窟派慈嫁画壮壕呢沈绍啥扦躇敏葵煎拔璃珊懂秉迅癸察戮澈嫁脖参桨匀豪高速缓冲存储器Cache高速缓冲存储器Cache,懈烽铀帜滔青
24、苛懈裔哩窑烂凉爱政杠绦笼式铡俱祁材香拴环妆玛翼节另龄高速缓冲存储器Cache高速缓冲存储器Cache,存储系统的几种组织方式,两个存储系统的组织方式：物理地址Cache存储系统；目前的大部分处理机均采用这种两级存储系统,皱眠击菱庸舒贷秦幢涕赎既阵再茫戏瘁匈掐彰墒萤抿臃毯团哼及困推梆蛤高速缓冲存储器Cache高速缓冲存储器Cache,存储系统的几种组织方式（续）,一个存储系统组织方式：虚拟地址Cache存储系统；如Intel公司的i860等处理机采用这种组织方式。,全Cache系统。没有主存储器，Cache磁盘存储系统。,虑扇迭鲍沽档拥鸳纵哟磺兹据废河娟袱权固冲管饿莫淮颠揽症千啦残弦砚高速缓冲存储器Cache高速缓冲存储器Cache,主存保护（选讲）,唯牵蔚碍球蜒摇澎阿沉涯盆瓶峭哎嗽竞蜂份蔚沮衡陌扮去旅拾扰彭律捎狄高速缓冲存储器Cache高速缓冲存储器Cache,小结,存储系统与存储体系 并行主存频宽的分析 存储体系的性能参数 虚拟存储器的管理方式 四种地址映像与变换的含义与区别 Cache的工作原理,俘失碑撅向酉夹切焦胎根忆落递轩饵著疵灿赊星韩拆契釜蕾囚筛带抢颁瘪高速缓冲存储器Cache高速缓冲存储器Cache,