(3)组相联映象及其变换方法(υ 映像规则 地址变换规则 区号E区内组号G组内块号D块内地址W主存地址 块Q 组号g组内块号d块内地址wCa地址 块Q(M-1) 块2Q-1 块K-1 不相等(相联比较 相等 块失效 Cache命中 块QM(U-1) 组M Q块 QM(U-I 块NQ 区号E组内块号D组内块号d有效位 组M-1 块
(3)组相联映象及其变换方法(续1) 主存 块0 块Q-1 块Q 块Q(M-1) 块K-1 块2Q-1 组0 组1 组M-1 Cache 块0 块Q-1 块Q 块Q(M-1) 块K-1 块2Q-1 块QM(U-1) 块QM(U-1) +Q-1 块N-Q 块N-1 块QM(U-1) +2Q-1 组0 组1 组M-1 组0 组1 组M-1 区0 区U-1 块QM(U-1) +Q 相联比较 区号E 有效位 主存地址 Cache地址 区号E 块内地址W 组内块号d 块内地址w Q块 1 块失效 Cache命中 不相等 相等 区内组号G 组内块号D 组号g 组内块号D 组内块号d 按地址访问 块表 主存地址 映像规则 地址变换规则
52.3 Cache替换算法及实现 o当CPU读 Cache时,有两种可能: -)需要的数据已在 Cache中,那么只需直接访问 Ca ache i 二)是需要的数据尚未装入 Cache,则CPU从主存储 器中读取信息的同时,需按所需的映象规则将该地址所 在的那块存储内容从主存储器拷贝到 Cache中。 o对于第二种情况,若该块所映象的 Cache块位置已全部 被占满,则必须选择将 Cache中的某一块替换岀去,需 要 Cache替换算法解决如何选择被换岀块的问题
5.2.3 Cache替换算法及实现 当CPU读Cache时，有两种可能： (一) 需要的数据已在Cache中，那么只需直接访问 Cache； (二)是需要的数据尚未装入Cache，则CPU从主存储 器中读取信息的同时，需按所需的映象规则将该地址所 在的那块存储内容从主存储器拷贝到Cache中。 对于第二种情况，若该块所映象的Cache块位置已全部 被占满，则必须选择将Cache中的某一块替换出去，需 要Cache替换算法解决如何选择被换出块的问题
Cache替换算法 o随机替换算法 随机法是 Cache替换算法中最简单的一种。这种方法是随机地选 择可以被替换的一块进行替换。有些系统设置一个随机数产生 器,依据所产生的随机数选择替换块,进行替换 o先进先出替换算法(FIFO 这种策略总是把最先调入的 Cache块作为被替换的块替换出去 最近最少使用替换算法①LRU LRU法是依据各块的使用情况,总是选择最近最久没被使用的 块作为被替换的块进行替换。因为目前为止最久没有被访问的 块,很可能也是将来最少访问的块
Cache替换算法 随机替换算法 随机法是Cache替换算法中最简单的一种。这种方法是随机地选 择可以被替换的一块进行替换。有些系统设置一个随机数产生 器，依据所产生的随机数选择替换块，进行替换。 先进先出替换算法(FIFO) 这种策略总是把最先调入的Cache块作为被替换的块替换出去。 最近最少使用替换算法(LRU) LRU法是依据各块的使用情况，总是选择最近最久没被使用的 块作为被替换的块进行替换。因为目前为止最久没有被访问的 块，很可能也是将来最少访问的块
Cache替换算法( o堆栈替换算法 堆栈替换算法使用栈顶到栈底各项的先后次序来记录 Cache中或 Cache中同一组内各个块被访问的先后顺序。栈顶恒存放近期最 近被访问过的块的块号,栈底恒存放近期最久没有被访问过的 块的块号,即准备被替换掉的块的块号(LRU堆栈实现)。 o比较对替换算法 LRU算法用一组硬件的逻辑电路记录同一组中各个块使用的时 间和次数,然后按照各个块被访问过的时间顺序排序,从中找 出最久没有被访问过的块。用一个两态的触发器的状态来表示 两个块之间的先后顺序,再经过门电路就可以找到LRU块
Cache替换算法(续1) 堆栈替换算法 堆栈替换算法使用栈顶到栈底各项的先后次序来记录Cache中或 Cache中同一组内各个块被访问的先后顺序。栈顶恒存放近期最 近被访问过的块的块号，栈底恒存放近期最久没有被访问过的 块的块号，即准备被替换掉的块的块号（LRU堆栈实现）。 比较对替换算法 LRU算法用一组硬件的逻辑电路记录同一组中各个块使用的时 间和次数，然后按照各个块被访问过的时间顺序排序，从中找 出最久没有被访问过的块。用一个两态的触发器的状态来表示 两个块之间的先后顺序，再经过门电路就可以找到LRU块
Cache替换算法(续2 o各种 Cache替换算法的优缺点 (1)随机替换算法: 优点是简单,容易实现;缺点是没有考虑到 Cache块的使用历 史情况,没有利用程序的局部性特点,从而命中率较低,失效 率较高。 (2)FIFO替换算法: 优点是由于它不需记录各个块的使用情况,实现起来也较容 易;缺点是虽然考虑到了各块进入 Cache的先后顺序这一使用 “历史”,但还不能正确地反映程序的局部性特点。 (3)LRU替换算法: LRU算法较好地反映了程序的局部性特点,失效率较低, LRU算法比较复杂,硬件实现较困难,特别是当组的大小增加 时,LRU的实现代价将越来越高
Cache替换算法(续2) 各种Cache替换算法的优缺点 (1)随机替换算法： 优点是简单，容易实现；缺点是没有考虑到Cache块的使用历 史情况，没有利用程序的局部性特点，从而命中率较低，失效 率较高。 (2)FIFO替换算法： 优点是由于它不需记录各个块的使用情况，实现起来也较容 易；缺点是虽然考虑到了各块进入Cache的先后顺序这一使用 “历史”，但还不能正确地反映程序的局部性特点。 (3) LRU替换算法： LRU算法较好地反映了程序的局部性特点，失效率较低，但 LRU算法比较复杂，硬件实现较困难，特别是当组的大小增加 时，LRU的实现代价将越来越高