第六章层次结构存储系统-3_24讲解.ppt

举例：Fully Associative Example: 32bits memory address, 32 B blocks. 比较器位数多长？ we need N 27-bit comparators 0 4 31 : Cache Data B 0 : Cache Tag (27 bits long) V : B 1 B 31 : B 32 B33 B 63 : Cache Tag Byte Select Ex: 0x01 = = = = = : 问题：需要多少个比较器？ 每行一个比较器！ 组相联映射（Set Associative） 组相联映射结合直接映射和全相联映射的特点 将Cache所有行分组，把主存块映射到Cache固定组的任一行中。也即：组间模映射、组内全映射。映射关系为： Cache组号=主存块号 mod Cache组数 举例：假定Cache划分为：8K字=8组x2行/组x512字/行 4=100 mod 8 (主存第100块应映射到Cache的第4组的任意行中。) 特点： 结合直接映射和全相联映射的优点。当Cache组数为1时，变为全相联映射；当每组只有一个槽时，变为直接映射。 每组2或4行（称为2-路或4-路组相联）较常用。通常每组4行以上很少用。在较大容量的L2 Cahce和L3 Cahce中使用4-路以上。 指出对应行取自哪个主存组群 指出对应地址位于哪个主存组群中 将主存地址标记和对应Cache组中每个Cache标记进行比较！ 例：如何对0120CH单元进行访问？ 0000 0001 0010 0000 1100B是第1组群中的001块（即第9块）中第12个单元。 所以，映射到第一组中。 假定数据在主存和Cache间的传送单位为512字。 Cache大小：213字=8K字=16行 x 512字/ 行 主存大小：220字=1024K字=2048块 x 512字/ 块 Cache索引 命中率、缺失率、缺失损失 Hit: 要访问的信息在Cache中 Hit Rate(命中率)：在Cache中的概率 Hit Time (命中时间) ：在Cache中的访问时间 Miss: 要找的信息不在Cache中 Miss Rate (缺失率) = 1 - (Hit Rate) Miss Penalty (缺失损失)：访问一个主存块所花时间 Hit Time Miss Penalty （Why?） Average access time(平均访问时间) Cache对程序员来说是透明的，以方便编程！ 要提高平均访问速度，必须提高命中率！ 看看命中率对平均访问时间的影响 设H是命中率，则平均访问时间T = HTC+ (1 - H)(TC+ TM) = TC+ (1 - H)TM 例1. 若H=0.85, Tc=1ns, TM=20ns，则T为多少？ 答： T = 4ns 例2. 若命中率H提高到0.95，则结果又如何？ 答： T = 2ns 例3. 若命中率为0.99呢？ 答: T = 1.2ns 访存速度与命中率的关系非常大！ 高速缓存的缺失率和关联度 三种映射方式 直接映射：唯一映射（只有一个可能的位置） 全相联映射：任意映射（每个位置都可能） N-路组相联映射：N-路映射（有N个可能的位置） 什么叫关联度？ 一个主存块映射到Cache中时，可能存放的位置个数 直接映射关联度？ 全相联映射关联度？ N-路组相联映射关联度？ 关联度和miss rate有什么关系呢？ 直观上，你的结论是什么？（ Cache大小和块大小一定时 ） 缺失率：直接映射最高，全相联映射最低 关联度最低，为1 关联度最高，为Cache行数 关联度居中，为N 替换(Replacement)算法 问题举例： 组相联映射时，假定第0组的两行分别被主存第0和8块占满，此时若需调入主存第16块，根据映射关系，它只能放到Cache第0组，因此，第0组中必须调出一块，那么调出哪一块呢？ 这就是淘汰策略问题，也称替换算法。 常用替换算法有： 先进先出FIFO （first-in-first-out） 最近最少用LRU （ least-recently used） 最不经常用LFU （ least-frequently used） 随机替换算法（Random） 等等 这里的替换策略和后面的虚拟存储器所用的替换策略类似，将是以后操作系统课程的重要内容，本课程只做简单介绍。有兴趣的同学可以自学。 SKIP 假定第0组的两行