cache原理简介.ppt

计算机原理实验,Cache,A,2,存储器的层次结构,处理器具体执行程序运行速度1+GHz（1ns）但是：指令和数据在何处？磁盘容量巨大（可以认为无限）非常慢（10ms）如何匹配二者的速度？,A,3,存储器的层次结构,内存（DRAM）容量有限内存：128MB16GB，磁盘：10GB1TB包含磁盘数据的一个子集比磁盘快很多（10ns）还是比CPU慢很多解决方案：增加新的层次（Cache）,A,4,存储器的层次结构,A,5,存储器的层次结构,越靠近CPU的层次，其特性必须安装容量小（节约成本）速度更快（提高访问速度）包含下一个层次的数据的一个子集包含以上所有层次所存储的数据最高的层次应与CPU速度相同最低的层次（通常是磁盘）包含所有的数据比磁盘更低的层次？CDROM、磁带、Internet,A,6,存储器的层次结构例：图书馆,图书馆的藏书：数据图书馆书库：磁盘容量巨大，但取出一本书非常慢书桌：Cache书桌上的书取用速度很快但书桌空间狭小：只能放少数几本书特点短时间内，只需要看少数几本如果要看某本书的某一页，该书其它页也很有可能在最近要看,A,7,数据访问的局部特性,时间局部特性现在访问的数据，在不久的将来可能再次使用空间局部特性此处的数据被访问，其附近的数据可能即将被访问通常是很接近实际情况的假设Cache赖以发挥作用的条件Cache算法设计的依据,A,8,Cache设计,内存：磁盘的cache虚拟内存（VM：后面讲）CPUCache：内存的Cache定位：指定的内存单元映射到哪个Cache地址？确认：某Cache地址中存储的数据是否是需要的？速度：如何快速得到数据？Cache设计的基本问题所有Cache层次都需要考虑不同的层次用不同的解决方案,A,9,直接映射Cache,指定内存单元映射到一个确定的Cache单元多个内存单元可以映射到同一个Cache单元是否为所须？,A,10,直接映射Cache,多个内存地址可以映射到同一Cache块：如何知道Cache当前存储的是哪个？如果Cache块大于1字节（空间局部特性）如何处理？解决方案：把地址分解为3个域,tagindexoffset是否是选择Cache块块内需要的块偏移,A,11,直接映射Cache,所有域作为无符号数使用Index：需要的Cache块Offset：Cache块内字节偏移Tag：标准当前在Cache块中存储的数据是映射到哪个内存地址,A,12,直接映射Cache例子,条件：16KB直接映射Cache，4字块，32位体系结构首先确定3个域各自的位数Offset从Cache块内选择一个字节块大小：4words=16bytes=24bytes需要4bits来选择一个字节叫做：CacheLineSize,A,13,直接映射Cache例子,Index选择合适Cache行（叫做：CacheRow）Cache大小：16KB=214bytes块大小：24bytes(4words)Cache行数=Cache块数/每行快数（=1）=Cache大小行大小（块大小）=21424=210行需要10bits,A,14,直接映射Cache例子,Tag地址中其余位都是Tagtag长度=内存地址长度-offset-index=32-4-10bits=18bitsTag长度为18bits,A,15,直接映射Cache例子,访问如下4地址0 x00000014,0 x0000001C,0 x00000034,0 x00008014内存内容如右仅Cache/Memory层次,地址,内容,内存,00000030,00000034,00000038,0000003C,e,f,g,h,00008010,00008014,00008018,0000801C,i,j,k,l,A,16,直接映射Cache例子,把地址划分为域0 x00000014,0 x0000001C,0 x00000034,0 x00008014,00000000000000000000000000010100000000000000000000000000000111000000000000000000000000000011010000000000000000001000000000010100TagIndexOffset,A,17,直接映射Cache例子,观察3类事件cachemiss：Cache块无数据，从内存读入cachehit：Cache块包含合适的数据，直接从Cache中读出数据cachemiss,blockreplacement：错误的数据在Cache块中，抛弃现有数据，并从内存中读入合适的数据Validbit：标准Cache块是否有数据,A,18,直接映射Cache例子,A,19,读0 x00000014,00000000000000000000000000010100,Index,Tag,Index,Offset,A,20,从内存读入数据,1,0,a,b,c,d,00000000000000000000000000010100,Index,Tag,Index,Offset,0,0,0,0,0,0,0,0,0,A,21,从Cache读数据,00000000000000000000000000010100,1,0,a,b,c,d,Index,Tag,Index,Offset,0,0,0,0,0,0,0,0,0,A,22,读0 x0000001C,1,0,a,b,c,d,00000000000000000000000000011100,Index,Tag,Index,Offset,0,0,0,0,0,0,0,0,0,A,23,读0 x00000034,1,0,a,b,c,d,00000000000000000000000000110100,Index,Tag,Index,Offset,0,0,0,0,0,0,0,0,0,A,24,读0 x00008014,1,0,a,b,c,d,00000000000000001000000000010100,1,0,e,f,g,h,Index,Tag,Index,Offset,0,0,0,0,0,0,0,0,A,25,自己练习,事件：Hit,Miss,Missw.replace返回值：a,b,c,d,e,.,k,l读0 x00000030?00000000000000000000000000110000读0 x0000001c?00000000000000000000000000011100,.,Valid,Tag,0 x0-3,0 x4-7,0 x8-b,0 xc-f,0,1,2,3,4,5,6,7,.,1,2,i,j,k,l,1,0,e,f,g,h,Index,0,0,0,0,0,0,A,26,Cache的性能,衡量Cache性能的指标命中率（HitRate）、不命中率（MissRate）命中访问速度（HitTime）通常设为1未命中开销（MissTime）未命中附加开销（MissPenalty）MissTime-HitTime,A,27,Cache的性能,需要一个总指标平均访问时间（AverageAccessTime）Cache性能的硬指标：所有Cache设计必须为优化此指标努力,AverageAccessTime=HitTimeMissPenaltyMissRate,不是MissTime,A,28,Cache未命中的类型,加载新程序导致的未命中Cache还没有程序的任何信息会发生大量的未命中事件很难避免，一般不考虑对程序的影响也不大程序的大部分CPU开销在循环内部，不在程序开头“WarmUp”：把程序执行几次，让Cache获得程序的信息Cache性能讨论一般基于这种情况,A,29,Cache未命中的类型,冲突导致的未命中由于2个内存地址映射到同一Cache块，如果要同时访问这2个内存单元，则导致冲突直接映射Cache：很容易导致冲突如何减少冲突？调整Cache的参数Cache设计,A,30,Cache的参数,容量Cache有多少可以存储数据的空间并不是越大越好成本问题：可承受价格和生产成本的平衡技术问题：容量和速度的平衡.一般由于技术限制，在Cache设计初期就确定Cache设计一般指其它参数的调整以下内容在Cache容量固定的条件下讨论,A,31,Cache的参数,Cache块大小大于1Byte的块可以利用程序的空间局部特性对指令，此特性非常重要对数据，也有很大的好处块大小对Cache性能指标的影响MissPenalty=BlockSize/MemoryBandwidthBlockNumber=CacheSize/BlockSize,A,32,Cache的参数：块大小,后面假设块大小已经确定,A,33,Cache的参数,还有其它增加命中率的方法？只要减少冲突，就可以增加命中率如何减少冲突？一个内存单元可以映射到多个Cache块相关程度,A,34,全相关Cache,内存地址Tag：同以前Offset：同以前Index：不再操作？同一内存单元可以映射到任何Cache块如何实现？,A,35,全相关Cache,全相关Cache例：32字节块并行比较所有Tag,A,36,全相关Cache,好处解决了冲突：同一内存单元可以进入任何Cache块坏处每个Cache块需要一个比较器每个周期要把所有Cache单元的内容读出来全相关Cache不能做得很大在不需要大容量Cache的情况使用有最好的灵活性,A,37,第3类Cache未命中,因容量导致的未命中Cache容量比内存小，必然不可能把全部内容载入如果增加Cache容量，此类未命中率将下降全相关Cache的主要未命中类型如何既节约成本，又具有相关Cache的优点？,A,38,N路集相关Cache,内存地址Tag：同以前Offset：同以前Index：指向某Cache“行”（集：set）区别何在？每个集包含多个Cache块集内是全相关的，必须并行比较Tag集间相当于直接映射直接映射到集，然后用全相关,A,39,Cache的替换策略,如果发生Cache未命中事件，必须从内存读取数据，并存储到某个Cache块中究竟存储到哪个Cache块？替换策略直接映射Cache根据内存地址唯一确定全相关/N路集相关有多个可选择的块：如何决策？,A,40,Cache的替换策略,情况1如果有一可用Cache块未占用（空：Valid=0）当然存储在此处情况2如果所有可用Cache块都已经占用？必须废弃一个，然后存储在此处替换、替换策略,A,41,Cache的替换策略,选择使用频率（访问次数）最小的块实现非常困难需要统计访问次数需要对访问次数排序在内存Cache层次一般不采用选择最久未使用的块通常叫做：LRU（LeastRecentlyUsed）字面含义更象前一种算法但一般是这种含义其它替换算法,A,42,Cache替换策略例,Cache参数2路集相关共4块块大小可以不考虑访问顺序（内存块地址）0,2,0,1,4,0,2,3,5,4跟踪事件HitMissMissw.Replace,A,43,地址0,2,0,1,4,0,.,0,lru,1,lru,loc0,loc1,0:miss,载入(set0,loc0),2:miss,载入(set0,loc1),0:hit,1:miss,载入(set1,loc0),4:miss,载入(set0,loc1)，替换2,0:hit,A,44,Cache的参数,Cache参数对未命中率的影响,还有其它优化手段?减少未命中附加开销更大的内存带宽还有其它方法?,A,45,Cache性能参数计算例,假设：HitTime=1，MissPenalty=10，MissRate=5%在Cache采用初期的性能指标平均访问时间10.0510=1.5假设：HitTime=1，MissPenalty=100，MissRate=5%现在的