《高速缓冲存储器的组成与运行原理.ppt》由会员分享，可在线阅读，更多相关《高速缓冲存储器的组成与运行原理.ppt（47页珍藏版）》请在三一办公上搜索。
1、1,第三单元 层次存储器系统,第三讲 高速缓冲存储器的组成与运行原理刘卫东,2,内容提要,Cache的目的基本原理Cache的三种映射方式提高Cache性能,3,CPU与DRAM性能比较,4,Cache的提出,一直以来，CPU和主存储器的速度总是有差距,CPU的发展一直以速度为主，以提高速度为核心,主存的发展一直以容量为主，以提高容量为核心,如何解决这之间的矛盾？,5,这不是一个技术问题，而是一个经济问题。从技术上说，能制造出多高速度的CPU，就能制造出同样速度的存储器，只不过是我们是否愿意付出如此高的价格。,有没有更好的办法？能否用廉价的高容量存储器实现相对的高速度呢？,6,程序的局部性原理
2、,程序在一定的时间段内通常只访问较小的地址空间两种局部性：时间局部性空间局部性,地址空间,访问概率,7,层次存储器系统,使用高速缓冲存储器Cache来提高CPU对存储器的平均访问速度。时间局部性：最近被访问的信息很可能还要被访问。将最近被访问的信息项装入到Cache中。空间局部性：最近被访问的信息临近的信息也可能被访问。将最近被访问的信息项临近的信息一起装入到Cache中。,8,MEMORY,CACHE CONTROL,CACHE的基本运行原理,数据总线,译码选一单元,比较选一行,读过程为例,地址总线,ADDR DATA,CACHE,CPU,9,要解决的主要问题,1.地址之间的映射关系：,如何
3、从主存地址得到Cache地址？,2.Cache中的内容是否已经是主存对应地址的内容？,3.Cache内容装入策略,如何提高Cache的命中率？,10,几个参数,块（Line）：数据交换的最小单位命中（Hit）：在较高层次中发现要访问的内容命中率（Hit Rate）：命中次数/访问次数命中时间：访问在较高层次中数据的时间失效（Miss）：需要在较低层次中访问块失效率（Miss Rate）：1-命中率失效损失（Miss Penalty）：替换较高层次数据块的时间+将该块交付给处理器的时间命中时间失效损失,11,参数典型数值,块大小：4128Byte命中时间：14周期失效损失：访问时间：610个周期
4、传输时间：222个周期命中率：80%99%Cache容量：1KB256KB,12,全相联方式,C P U,数据,地址,有效位,主存储器,CACHE,比较,译码,标志,数据,块号,块内地址,主存地址,13,全相连映射硬件实现举例,14,全相联方式的地址映射,特点,1.主存的字块可以和Cache的任何字块对应，利用率高，方式灵活。,2.标志位较长，比较电路的成本太高。如果主存空间有2m块，则标志位要有m位。同时，如果Cache有n块，则需要有n个比较电路。,使用成本太高,15,直接映射方式,C P U,数据,地址,有效位,主存储器,CACHE,比较,译码,译码,块内地址,块号,标志,数据,块号,块
5、内地址,主存地址,16,Cache 举例,8 块 cache每块16 字节“直接映射”:内存中的每个单元在Cache中只会有一个唯一的位置和它对应。,17,直接映射Cache 举例,假定有如下访问操作:Read location 0Read location 16Read location 32Read location 4Read location 8Read location 36Read location 32Read location 128Read location 148cache中命中和缺失各有多少次?,0-15,16-31,32-47,XXX 128-143,XXX 144-1
6、59,18,Cache 举例：续,Cache中命中和缺失次数?Read location 0:MissRead location 16:MissRead location 32:MissRead location 4:HitRead location 8:HitRead location 36:HitRead location 32:HitRead location 128:MissRead location 148:Miss命中率=4/9=45%注意:失效的原因启动失效冲突失效,0-15,16-31,32-47,XXX 128-143,XXX 144-159,19,直接映射 Cache:硬件
7、实现,20,增加块大小可以更好地利用空间局部性,直接映射 Cache:硬件实现,1,6,1,5,4,3,2,1,0,21,直接映射方式的地址映射,特点,1.主存的字块只可以和固定的Cache字块对应，方式直接，利用率低。,2.标志位较短，比较电路的成本低。如果主存空间有2m块，Cache中字块有2c块，则标志位只要有m-c位。且仅需要比较一次。,利用率低，命中率低，效率较低,22,两路组相联方式,C P U,数据,地址,有效位,主存储器,CACHE,译码,比较,比较,译码,译码,标志,数据,块号,块内地址,主存地址,23,两路组组相联方式的地址映射,特点,1.前两种方式的折衷方案。组间为全相连
8、，组内为直接映射。,2.集中了两个方式的优点。成本也不太高。,是常用的方式,24,组相连Cache访问举例,假设有下列访问主存顺序:Read location 0:MissRead location 16:MissRead location 32:MissRead location 4:HitRead location 8:HitRead location 36:HitRead location 32:HitRead location 128:MissRead location 148:MissRead location 0:HitRead location 128:HitRead locat
9、ion 4:HitRead location 132:Hit,0-1564-79,0-15,16-31,32-47,128-143,144-159,25,四路组相连Cache实现,26,三种映射方式比较,直接映射主存中的一块只能映射到Cache中唯一的一个位置定位时，不需要判断，只需替换全相连映射主存中的一块可以映射到Cache中任何一个位置N路组相连映射主存中的一块可以选择映射到Cache中N个位置全相连映射和N路组相连映射的失效处理从主存中取出新块为了腾出Cache空间，需要替换出一个Cache块不唯一，则需要判断应替出哪块,27,提高Cache的性能,1.提高命中率 2.缩短缺失后的处理
10、时间3.提高访问cache的速度,28,Cache缺失的原因,必然缺失（开机或进程切换）：首次访问数据块世事总是有缺憾注意：如果我们运行几百万条指令，有点必然缺失又何妨？冲突缺失多个 memory块映射到同一 cache块解决办法 1：增大 cache 容量解决办法 2：增加相连组数容量冲突Cache无法装入程序需要访问的所有块方案：增大 cache 容量无效缺失：其它进程（如I/O）修改了主存,29,影响 CACHE 命中率的因素,从 CACHE 本身诸因素看，可能：1.CACHE 的容量，大一些好2.CACHE 与主存储器每次交换 信息的单位量(Cache Line Size)适中3.CA
11、CHE 不同的组织方式，多路组相联更好4.CACHE 的多级组织可提高命中率5.CACHE 装满后的换字算法,30,Cache命中率,Cache Size in KB,Hit Rate,31,块大小和缺失率的关系,32,块大小的权衡,一般来说，数据块较大可以更好地利用空间局部性，但是：数据块大意味着缺失损失的增大：需要花费更长的时间来装入数据块若块大小相对Cache总容量来说太大的话，命中率将降低Cache块数太少一般来说，平均访问时间=命中时间 x 命中率+失效损失 x 缺失率,缺失损失,块大小,缺失率,利用空间局部性,较少的数据块：弥补时间局部性,平均访问时间,增加了缺失损失和缺失率,块大
12、小,块大小,33,Cache的替换算法,1.先进先出算法（FIFO）,将最早调入Cache的字块替换出去。容易实现，开销小。,2.最近最少使用算法（LRU）,需要计算字块的使用次数，开销大，但平均命中率比FIFO要高。,3.随机替换（RAND）,34,多级Cache,采用两级或更多级cache来提高命中率将Cache分解为指令Cache和数据Cache,35,CACHE 接入系统的体系结构,1.侧接法：像入出设备似的连接到 总线上，优点是结构简单，成本低，缺点是不利于降低总线占用率。,CPU,MEMORY,CACHE,Bus Master 1,Bus Master 2,总线,36,CACHE
13、接入系统的体系结构,2.隔断法：把原来的总线打断为两段，使 CACHE 处在两段之间，优点是有利于提高总线利用率，支持总线并发操作，缺点是结构复杂，成本较高。,CPU,MEMORY,CACHE,Bus Master 1,Bus Master 2,总线,37,改写主存储器的策略,若 CPU 改写了 CACHE 一单元内容后且尚未改变主存相应单元内容，则出现数据不一致性。有两种解决办法：1.接下来直接改写主存单元内容（Write Through）简便易行,但可能带来系统运行效率不高的问题。需要写入缓冲存储器。2.拖后改写主存单元内容（Write Back）一直拖到有另外的设备要读该内容过时的主存单
14、元时,则首先停止这一读操作，接下来改写主存内容，之后再起动已停下来的读操作。矛盾是如何检查是否是读无效内存单元的操作，这是通过 监视地址总线完成的，记下无效单元地址用于比较。控制复杂些，但可以提供更高的系统运行效率。,38,Pentium上的Cache,Intel的80386及更早的处理器芯片上并没有片上的高速缓冲存储器。80486：引入一个8K字节的片上Cache，其块大小为16字节，采用的是四路组相连映象方式。Pentium：芯片上已经有了两个8K字节的片上cache，一个用作指令缓存，另一个用作数据缓存。它们的块大小都为32字节，采用两路组相连的组织方式。,39,40,Pentium的数
15、据缓存,数据缓存由128组，每组两个cache块组成，从逻辑上可以看成是大小为4K字节的两“路”。每个cache块都有20位的标记位和两位的状态位与其对应，标记位即存放在该cache块中的主存块的地址的高20位，两位状态位可以标记出4个不同的块状态。替换算法采用的是最近最少使用法（LRU），所以对每组cache块还需要有1位的LRU位来表示CPU最近访问的是该组中的哪一块。采用拖后写策略。支持两级Cache。,41,Pentium Cache块的状态,修改态（M）：处于这个状态的cache块中的数据已经被修改过，和主存中对应的数据已不同，只能从cache中读到正确的数据。独占态（E）：处于本状
16、态的cache块的数据和主存中对应的数据块内容相同，而且在其它cache中没有副本。共享态（S）：处于本状态的cache块的数据和主存中对应的数据块内容相同，而且可能在其它cache中有该块的副本。非法态（I）：处于本状态的cache块中尚未装入数据。,42,两级Cache块的状态转换,I,L1:,L2:,S,I,E,E,M,M,读入数据,读入数据,第一次修改,第二次修改,多次修改,访问主存,第一次修改,访问主存,替换策略：S、E状态不需改写L2,43,写主存顺序,L2监听到其它总线主设备写请求，并要求该设备等待；L2将要被写的地址传给L1，如果L1中的数据在一次写之后有了新的修改（状态为M）
17、，则需要将L1中该块的数据写回到主存中。任何情况下，都将该块的状态标记为非法态（I）。如果L1中的数据与L2相同，则无须L1将数据写回主存中，而只要L2把自己的块的内容写回即可。但还是要把该块的状态标记为非法态（I）。L2唤醒总线主设备，由它完成写操作。,44,Cache,目标提高CPU访问存储器系统的平均速度策略利用一容量较小（降低成本）的高速缓冲存储器组织方式全相连、直接映射、组相连,45,Cache,包含性保证cache中的块和主存中的块进行映射一致性保证写回主存策略提高命中率块替换算法,46,Cache,局部性原理：任何时候，程序需要访问的只是相对较小的一些地址空间。时间局部性空间局部性三类主要的Cache缺失原因：无法避免的缺失：如：第一次装入块冲突：增大Cache容量、改进组织方式避免不断的块冲突容量冲突：增大Cache容量Cache设计总容量、块大小、组织方式替换算法写策略（命中时）：写直达、拖后写写策略（不命中时）：是否装入到Cache？,47,设计 Cache,有关方案cache 容量块大小组织方式替换算法写策略方案优化根据用途选择海量数据处理指令数据平衡(I-cache,D-cache)根据成本优化简单化常常就是优化,关联度,Cache 容量,块大小,Bad,Good,Less,More,Factor A,Factor B,
