第4章存储体系(续).ppt

2.直接映象及其变换 1)规则：主存中每一块只能映像到Cache中唯一一个特定位置，如图所示，主存的第i块只能映像到第i mod2ncb块位置上。如图4.33所示： 2)变换过程 3)优缺点 优点： a)所需硬件简单，只需要容量较小的按地址访问 的区号标志表存储器和少量外比较电路，因此 成本低。 b)访问Cache与访问区号表、比较区号是否相符 的操作是同时进行的。当Cache命中时就意味着 省去了地址变换所花费的时间。 缺点：直接映象法最致命的缺点就是Cache的块 冲突率很高。只要有两个或两个以上经常使用的块 恰好被映象到Cache的同一个块位置时，就会使得 Cache的命中率急剧下降。而且，即使此时Cache 中有大量的空闲块存在，仍然会发生块失效和块冲 突，无法使用Cache中的空闲块，所以，Cache的 利用率很低。正是因为这个原因才使得目前采用直 接映象的Cache存储器很少了。 3.组相联映象及其变换 1)思想：简要说明如下图4.35所示，将Cache空间和主存空间都分组，每组S块(S＝2s)。Cache一共2ncb个块，分成Q组(Q= 2q)，整个Cache是一区。主存分成与Cache一样大小的2nd个区，其地址按区号、组号、组内块号、块内地址分成对应的4个字段。主存地址的组号、组内块号分别用q、s 字段表示，它们的宽度和位置与Cache地址的q、s是一致的。 2)规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图4.35所示。 3)讨论 当组相联映象的S值大到等于Cache的块数(即s= ncb) 时就变成了全相联映象，而当S值小到只有1块(即无s 字段)时就变成了直接映象。因此全相联映象和直接映 象只是组相联映象的两个极端。在Cache空间大小及 块的大小都已经确定的情况下，Cache的总块数就定 了，但结构设计者仍可以对S和Q值进行选择。Q和S 的选取主要依据对块冲突概率、块失效率、映象表复 杂性和成本、查表速度等的折衷权衡。组内块数S愈 多，块冲突概率和块失效率愈低，映象表愈复杂、成 本愈高，查表速度愈慢。所以通常采用在典型工作负 荷下进行模拟而定。 4)地址变换 4.段相联映象 在全相联、直接相联、组相联映象的基础上还可 以有各种变形，段相联就是一例。段相联实质上是 组相联的特例。他是采用组间全相联、组内直接映 象。为了与组相联加以区别，将这种映象方式称为 段相联。就是说，段相联映象是把主存和Cache分 成具有相同的Z块的若干段，段与段之间采用全相 联映象，而段内各块之间采用直接映象。如下图所示： 4.3.3 替换算法的实现 当访存发生Cache块失效，需要把主存块按所采 用的映象规则装入Cache时，如果又出现Cache块冲 突，就必须按某种策略选择将Cache中的哪一块替 换出去。Cache——主存存储层次的替换算法与虚 拟存储器的没有什么不同，不外乎也是FIFO法或 LRU法，其中LRU法最为常用。 1.堆栈法 1)思想 我们在4.2.2中讲过，LRU法是堆栈型替换算法， 也讲了对于LRU算法，堆栈St中由栈顶到栈底的各 项（行）恒反映出到t时刻，实存中各页被访问过的 近远次序，以及每访问一页，堆栈St中各项的变换 过程。结果是此堆栈的栈顶恒存放近期最近访问过 的页的页号，而栈底恒存放近期最久没有方问过的 页的页号，即准备被替换掉的页的页号。那么，我 们在Cache——主存存储层次中就可以按此思想实 际组成一个硬件堆栈。 2)过程 3)缺点： 这种硬件堆栈既要求具有相联比较的功能，又要 求能全下移、部分下移和从中间取出一项的功能， 成本较高，因此只适用于组相联且组内块数较少的 LRU替换场合。 4)变形 上述这种堆栈，各块被访问的先后次序由该项在 堆栈中距离栈底是近还是远来反映。为了避免堆栈 中各行存放的内容经常同时进行下移，以便节省成 本，我们采用另一种变形，即将存放块号的寄存器 的几何位置与Cache中的块号对应，而用寄存器存 放值的大小来表示已被访问过的远近次序。以组相 联为例，每一组均使用如图4.39那样的一个寄存器 组，由2s个寄存器组成，每个寄存器为s位宽，可以 存放表示从0到2s－1的次序值。如果让越是最近访 问的，其次序值愈小，则只需通过相联比较求最大 值（不是相联比较相符），找到该最大值所在的寄 存器号，这就是对应Cache中应该被替换掉的块的 块号。 2.比较对法 1)思路 比较法的基本思路是让各个块成对组合，用一个 触发器的状态来表示该比较对内两块访问的远近次