组相联映像Set

8.2高速缓冲存储器解决CPU与主存之间的速度矛盾2基本概念Cache在CPU和主存之间引入速度更快的小容量存储器，称高速缓冲存储器（CacheMemory）。它存放当前最活跃的程序和数据，使得在大部分情况下，CPU访问的是Cache而不是主存，大大提高了CPU访问内存的速度。CPU高速缓存Cache主存MM辅助硬设备3基本概念（续）Cache能提高访问速度的原因：物质基础：Cache由双极型超高速半导体存储器(如ECL)组成，速度通常是主存的5～10倍。程序执行的局部性原理CPU对内存的访问在一段相对较短的时间间隔内往往集中于某个局部，特别是碰到循环程序、反复调用的子程序、递归程序等就更是如此，这就是所谓的“程序执行的局部性原理”。Cache与主存之间的地址变换和数据替换等控制全部用硬件实现，无需CPU的介入。合理设计映像方法和替换算法，提高命中率。分块4地址的映像与变换地址映像(Mapping)：把信息从主存复制到Cache的规则或算法。地址变换：将主存地址变换为Cache地址的过程。地址映像与变换的三种基本方式：直接方式（DirectMapping）全相联方式（AssociativeMapping）组相联方式（Set-AssociativeMapping）第0块第1块第15块MMCache第15块第0块第1块5直接方式地址映象（DirectMapping）策略：先将主存和Cache以同样大小分块(也称为行)，主存再按整个Cache的大小分为若干个区。例：内存16MB，Cache8KB，每块512B，那么Cache将分为16块,主存共32K块，分为2K区第0块第0块第0块第0块第1块第15块第1块第1块第1块第15块第15块第15块第0区第1区第X区第Y块Cache第Y块第0块第1块主存区号块号块内地址MM映像规则：主存某一区第Y块只能装入到Cache的第Y块。每个Cache块对应了2048个主存块需记录主存的区号第15块第2047区9位4位11位直接方式地址变换123地址变换表(TAG)单元个数与Cache块数一致，地址即Cache块号，存放内容是Cache块对应的主存区号。·区号XY0115比＝命中Cache第Y块第0块第0块第0块第0块第1块第15块第1块第1块第1块第15块第15块第15块第15块第0块第1块第0区第1区第X区第2047区第Y块主存地址XYZ主存区号区内块号块内地址Cache地址MMTag7直接方式小结优点：地址变换简单，命中时直接由主存地址提取到Cache地址。不命中时替换算法简单不足：映像关系固定，不灵活“抖动”现象会造成命中率下降。第0块第0块第1块SUB:…第1块RET第0区第1区CALLSUBNEXT:LOOPNEXTCache第0块第1块8全相联映像（AssociativeMapping）映像方法：主存和Cache以同样大小分块。假设某机内存16MB，Cache为8KB，按512B划分块，那么主存将划分为32K块（块地址需15位），Cache将划分为16块（块地址需4位)，块内地址均为9位.映像规则：内存中某一块可以装入Cache的任何一块中。需要记录对应关系——地址变换表(TAG)单元数与Cache块数一致且对应内容是对应Cache块所存放的主存的块号15位9位主存块号块内地址主存第0块第1块第x块第32767块Cache第0块第1块第m块第15块地址变换表块号x01m1515位9全相联方式地址映象及变换4位9位主存地址Cache块号块内地址Cache地址Tag相联比较Cache主存＝命中15位9位主存块号块内地址第0块第1块第x块第0块第1块第m块第15块第32767块x01m全相联方式地址映象及变换123本例中，参与相联比较的位数为16×15=240。存放15位的主存块号。15地址变换表是相联存储器10全相联映像优点：主存的块装入Cache的位置没有限制，只要Cache有空闲块便可装入，只有全部装满才会出现冲突。不足：无法直接从主存块号中获取Cache块号，使得其地址变换机构相对复杂，使用了相联存储器，成本较高。前面的例子中，使用的相联比较器的位数为16×15=240位。11组相联映像（Set-AssociativeMapping）映像方法：是上两种方式的折中。即主存和Cache按同样大小分块；Cache分为若干组，如两块一组；主存按Cache组数分区。映像规则：主存任何一区的第n块只能映像至Cache的第n组（直接方式），可以是第n组两块中的任何一块（全相联方式）。即组间直接方式，组内全相联方式。第K块第0块第1块第0块第1块第0组第Y组第7组第0块第0块第0块第1块第7块第1块第1块第0区第X区第4095区第Y块第6块第7块12位主存块号3位9位主存区号块内地址Cache12组相联映像当主存第X区、第Y块装入cache时，装入cache的Y组中的任一块(设为k)，将区号X填入地址变换机构的对应单元。第0块第0块第0块第1块第7块第1块第1块第0区第X区第4095区第Y块第6块第7块Cache第K块第0块第1块第0块第1块第0组第Y组第7组区号XTagK命中组相联映像的地址变换12312位主存块号3位9位主存区号块内地址Cache第K块第0块第1块第0块第1块第0组第Y组第7组区号XTag区号X相联比较块号块内地址Cache地址组号14组相联映像参与全相联比较的位数为：2×(12)=24。若每组只有一块，将成为直接方式，若总共只有一组，将成为全相联方式。优缺点：介于全相联方式和直接方式之间，硬件电路成本比全相联方式低，Cache利用率和命中率又比直接方式高。18Cache读/写操作命中（Hit）：要访问的单元已在Cache中●读操作：直接从Cache中读。●写操作：■写回法（Writeback）：只写入Cache，当该块将被置换时，再写入主存。可为每个块设置M(Modified)位，M位为1时表示当前Cache行中包含的数据与存储器中的数据不一致。■透写法（Writethrough）：同时写入Cache和主存。无须一致性维护，但效率低，因为有些中间结果不必写入主存。未命中（Miss）：要访问的存储单元不在Cache中●读操作：■直接从主存中读取该单元，然后将该块置换到Cache。■先将该块装入，然后再从Cache中读。●写操作：按写分配法：写入主存，同时装入该块到Cache中不按写分配法：直接写入主存，不装入该块到Cache中19替换算法（ReplacementAlgorithms）替换算法：当引起对Cache块的位置争用时，更换块的算法。只有相联映像才需要替换算法先进先出算法FIFO（FirstInFirstOut）对进入Cache的块按先后顺序排队，先淘汰最早进入的块。最早装入的块有可能仍在使用。最近最少使用算法LRU（LeastRecentlyUsed）保留最近被访问的块，淘汰较长时间没有访问的块。随机法（Random）20最近最少使用算法LRU块号放在表中排队。刚访问到的块号移到表首，其余块号下移。表尾是近期最少访问的块。例：每组4块（4-way组相联）的块号表初始访问块3访问块1访问块0装入新块03102103102103132223已替换新内容21最近最少使用算法LRU（续）四路组相联LRU算法的另一种实现：每块用一个2位的计数器表示被访问的时间。每次访问到的块的计数器清0，同组中计数值比该页原计数值低的计数器加1。调入新块时，替换计数值最大的块。可以证明，4块的计数值各不相同。初始计数值访问块3访问块1访问块0装入新块块001201块112012块223330块33012323MM-Cache层次工作过程示意图Cache存放当前最活跃的程序和数据。大部分情况下，CPU访问的是Cache而不是主存，提高了CPU访存的速度。DBMMCPUABCache块号块内地址块内地址主存块地址地址变换替换算法部件Cache存储器多字高速总线不命中(已满)不命中(未满)命中24作业8.28.38.58.6