Cache的原理与地址映像机制PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,#,Cache,原理,与地址映像机制,1,2,重点,Cache,的工作原理,Cache,的基本结构,地址映像机制,替换策略,2,2025/4/12 周六,1.,问题的提出,避免,CPU“,空等”现象,CPU,和主存（,DRAM,）的速度差异,程序访问的局部性原理,一、,Cache,的工作原理,空间局部性,时间局部性,3,2025/4/12 周六,1.,问题的提出,避免,CPU“,空等”现象,CPU,和主存（,DRAM,）的速度差异,缓存,CPU,主存,容量小,速度高,容量大,速度低,一、,Cache,的工作原理,字,块,4,2025/4/12 周六,主存块,调入,缓存,主存块与缓存块,建立,了对应关系,标记记录,与某缓存块建立了对应关系的,主存块号,命中,未命中,主存块与缓存块,未建立,对应关系,主存块,未调入,缓存,2.,Cache,的命中率,5,2025/4/12 周六,(1)主存和缓存的编址,主存和缓存按块存储 块的大小相同,B,为块长,主存块号,主存储器,0,1,2,m,1,字块 0,字块 1,字块,M,1,主存块号,块内地址,m,位,b,位,n,位,M,块,B,个字,缓存块号,块内地址,c,位,b,位,C,块,B,个字,字块 0,字块 1,字块,C,1,0,1,2,c,1,标记,Cache,缓存块号,6,2025/4/12 周六,命中率,命中率：,CPU,访问,cache,的次数占总访问次数的比例。设,N,C,表示,cache,完成存取的总次数，,N,M,表示主存完成存取的总次数，,h,为命中率，则有：,h=N,C,/,（,N,C,+N,M,）,若,t,C,表示命中时的,cache,访问时间，,t,m,表示未命中时的主存访问时间，则,cache/,主存系统的平均访问时间,t,a,为：,t,a,=ht,c,+,（,1-h,）,t,m,目标：以较小的硬件代价使,cache/,主存系统的平均访问时间,t,a,越接近,t,c,越好，用,e,表示访问效率表示。,设,t,m,/t,c,=r,则有：,e=t,c,/t,a,=1/(r+(1-r)h),命中率,h,越接近于,1,越好，,r,值以,5,10,为宜，不宜太大。,7,2025/4/12 周六,3.Cache,的,读,操作,访问,Cache,取出信息送,CPU,访问主存,取出信息送,CPU,将新的主存块,调入,Cache,中,执行替换算法,腾出空位,结束,命中？,Cache,满？,CPU,发出访问地址,开始,是,否,是,否,8,2025/4/12 周六,4.Cache,的基本结构,Cache,替换机构,Cache,存储体,主存,Cache,地址映像,变换机构,由,CPU,完成,9,2025/4/12 周六,二、地址映射机制,主存和缓存的编址,主存块号,主存储器,0,1,2,m,1,字块,0,字块,1,字块,M,1,主存块号,块内地址,m,位,b,位,n,位,M,块,B,个字,缓存块号,块内地址,c,位,b,位,C,块,B,个字,字块,0,字块,1,字块,C,1,0,1,2,c,1,标记,Cache,缓存块号,10,2025/4/12 周六,二、地址映像机制,地址映像机制,A,C,=,f,(A,M,),常用的地址映像方式,直接映像方式,全相联映像方式,组相联映像方式,11,2025/4/12 周六,二、地址映像机制,1.,直接相联,字块,2,m,1,字块,2,c,+1,字块,2,c,+1,1,字块,2,c,+1,字块,2,c,字块,2,c,1,字块,1,字块,0,主存储体,字块,1,标记,字块,0,标记,字块,2,c,1,标记,Cache,存储体,t,位,0,1,2,c,1,字块,字块地址,主存字,块标记,t,位,c,位,b,位,主存地址,比较器（,t,位）,=,不命中,有效位,=1,？,*,m,位,Cache,内地址,否,是,命中,字块,2,c,+1,字块,2,c,字块,0,字块,0,12,2025/4/12 周六,检索过程：根据内存地址中的,t,位标记与,cache,的标记位相比较，然后将块地址与,cache,的块地址相比较，判断是否命中。,特点：硬件实现简单，成本低。但每个主存块只有一个固定的行可以存放。当,cache,的行数较少时发生冲突的可能性很大，频繁的置换会使,cache,的效率下降。,直接映射方式一般用于大容量的,cache,中。,13,2025/4/12 周六,二、地址映像机制,1.,直接相联,特点：,主存地址块映射到,Cache,的固定块,j,i,mod(,M,),实现简单,空间利用率低，冲突概率高,14,2025/4/12 周六,二、地址映像机制,2.,全相联,字块,2,m,1,字块,2,c,1,字块,1,字块,0,字块,2,c,1,字块,1,字块,0,标记,标记,标记,主存字块标记,字块内地址,主存地址,m,=,t,+,c,位,b,位,m,=,t,+,c,Cache,存储器,主存储器,字块,0,15,2025/4/12 周六,全相联映射方式的检索过程：,CPU,发出内存地址的块号部分（,s,位）与,cache,中,所有行,中的标记部分,同时比较,，若某行的标记与要访问的块号相同，命中，则再根据块内地址（,b,位）从该行中读取相应字；否则，未命中，则按内存地址从主存中读取一个字。,优点,:,灵活，,cache,可以得到充分利用。但当行数较多时要实现所有行中的标记部分同时参与比较，电路实现困难。,全相联映射方式一般用于小容量,cache,。,16,2025/4/12 周六,二、地址映像机制,2.,全相联,特点：,主存地址块映射到,Cache,的任意块,空间利用率高，冲突概率低,实现复杂,17,2025/4/12 周六,二、地址映像机制,3.,组相联,字块,2,m,1,字块,2,c,-,r,+1,字块,2,c,-,r,+1,字块,2,c,-,r,字块,2,c,-,r,字块,1,字块,0,字块,3,标记,字块,1,标记,字块,2,c,1,标记,字块,2,标记,字块,0,标记,字块,2,c,2,标记,字块内地址,组地址,主存字块标记,s,=,t,+,r,位,q,=,c,r,位,b,位,组,0,1,2,c,-,r,1,主存地址,Cache,主存储器,m,位,共,Q,组,，每组内两块（,r,=1),1,字块,0,字块,1,字块,0,字块,2,c,-,r,字块,2,c,-,r,+1,18,2025/4/12 周六,组相联映射,19,2025/4/12 周六,检索过程：,根据地址中的组地址找到,cache,的相应组，然后将该组的标记部分与内存地址的块号同时比较，判断是否命中。,特点：,组内有一定的灵活性，而且因组内行数的减少，比较的硬件电路比全相联方式简单些。,组相联映射的每组的行数,v,一般取值较小，典型值为,2,，,4,，,8,，,16,。为强调比较器的规模和存放的灵活性，常称组相联为,v,路组相联。,组相联映射,20,2025/4/12 周六,例如：设有一个,cache,的容量为,2K,字，每个块为,16,字，求,(1),该,cache,可容纳多少个块？,(2),如果主存的容量是,256K,字，则有多少个块？,(3),主存的字地址有多少位？,Cache,字地址有多少位？,(4),在直接映象方式下，主存中的第,i,块映象到,cache,中哪一个块中？,21,2025/4/12 周六,先进先出（,FIFO,）算法,把最先调入,cache,的字块替换出去,优点：实现容易、开销小,缺点：可能把一些常用的程序，如子程序、循环程序块，作为最早进入,Cache,块，替换出去,替换策略,22,2025/4/12 周六,先进先出,替换策略,23,2025/4/12 周六,近期最少使用,(LRU),算法,LRU,算法将近期内长久未被访问过的行换出。每行也设置一个计数器，,cache,每命中一次，命中行计数器清零，其它各行计数器增,1,。当需要替换时，将计数值最大的行换出。,这种算法保护了刚拷贝到,cache,中的新数据行，有较高的命中率。,替换策略,24,2025/4/12 周六,近期最少使用替换策略,25,2025/4/12 周六,随机替换,随机替换策略从特定的行位置中随机地选取一行换出。在硬件上容易实现，且速度也比前两种策略快。,缺点是降低了命中率和,cache,工作效率。,26,2025/4/12 周六,