计算机系统结构第4章续

2.直接映象及其变换1)规则：主存中每一块只能映像到Cache中唯一一个特定位置，如图所示，主存的第i块只能映像到第imod2ncb块位置上。如图4.35所示：……Cache块位置012ncb-1主存块012nmb-1…2ncb-1块2ncb+02ncb+1…2·2ncb-1块2·2ncb+0…3·2ncb-1……0区1区2区2nmb－ncb-1区图4.35直接映象规则2)变换过程主存块号块内地址主存地址nmnmbnmrncbncrCache地址nc…2ncb项相联比较不等块失效区号…012ncb-1••相等访Cache区号(按地址访问存贮器)由2ncb中选1图4.36直接映象的地址变换过程3)优缺点优点：a)所需硬件简单，只需要容量较小的按地址访问的区号标志表存贮器和少量外比较电路，因此成本低。b)访问Cache与访问区号表、比较区号是否相符的操作是同时进行的。当Cache命中时就意味着省去了地址变换所花费的时间。缺点：直接映象法最致命的缺点就是Cache的块冲突率很高。只要有两个或两个以上经常使用的块恰好被映象到Cache的同一个块位置时，就会使得Cache的命中率急剧下降。而且，即使此时Cache中有大量的空闲块存在，仍然会发生块失效和块冲突，无法使用Cache中的空闲块，所以，Cache的利用率很低。正是因为这个原因才使得目前采用直接映象的Cache存贮器很少了。3.组相联映象及其变换1)思想：简要说明如下图4.37所示，将Cache空间和主存空间都分组，每组S块(S＝2s)。Cache一共2ncb个块，分成Q组(Q=2q)，整个Cache是一区。主存分成与Cache一样大小的2nd个区，其地址按区号、组号、组内块号、块内地址分成对应的4个字段。主存地址的组号、组内块号分别用q、s'字段表示，它们的宽度和位置与Cache地址的q、s是一致的。2)规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图4.37所示。组号q组内块号s块内地址ncr组号q组内块号s'块内地址nmr区号nd1位1位2位2位1位ncbnmbncnm块位置0块01122334455667789101112131415012301230123012301230123第0组第0组第1组第1组第0组第1组第0区(Cache容量)第1区(Cache容量)Cache主存组内全相联组间直接相联图4.37组相联映象规则3)讨论当组相联映象的S值大到等于Cache的块数(即s=ncb)时就变成了全相联映象，而当S值小到只有1块(即无s字段)时就变成了直接映象。因此全相联映象和直接映象只是组相联映象的两个极端。在Cache空间大小及块的大小都已经确定的情况下，Cache的总块数就定了，但结构设计者仍可以对S和Q值进行选择。Q和S的选取主要依据对块冲突概率、块失效率、映象表复杂性和成本、查表速度等的折衷权衡。组内块数S愈多，块冲突概率和块失效率愈低，映象表愈复杂、成本愈高，查表速度愈慢。所以通常采用在典型工作负荷下进行模拟而定。4)地址变换组号q组内块号s'块内地址nmr区号nd组号q组内块号s块内地址ncrnmnc直接直接相联比较不等块失效相等•相联比较nds's•nd＋s'表的总容量为2ncb＝2q·2s行2q组中选12s行4.段相联映象在全相联、直接相联、组相联映象的基础上还可以有各种变形，段相联就是一例。段相联实质上是组相联的特例。他是采用组间全相联、组内直接映象。为了与组相联加以区别，将这种映象方式称为段相联。就是说，段相联映象是把主存和Cache分成具有相同的Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象。如图4.42所示：块0块1块2Z－1Cache主存…块0块1块2Z－1…≈≈块0块1块2Z－1…块0块1块2Z－1…≈≈块0块1块2Z－1…段0段0(Z个段)段1段2nmb/Z－1段2ncb/Z－1图4.42具有每段Z个块的断相联映象段间全相联段内直接4.3.3替换算法的实现当访存发生Cache块失效，需要把主存块按所采用的映象规则装入Cache时，如果又出现Cache块冲突，就必须按某种策略选择将Cache中的哪一块替换出去。Cache——主存存贮层次的替换算法与虚拟存贮器的没有什么不同，不外乎也是FIFO法或LRU法，其中LRU法最为常用。1.堆栈法1)思想我们在4.2.2中讲过，LRU法是堆栈型替换算法，也讲了对于LRU算法，堆栈St中由栈顶到栈底的各项（行）恒反映出到t时刻，实存中各页被访问过的近远次序，以及每访问一页，堆栈St中各项的变换过程。结果是此堆栈的栈顶恒存放近期最近访问过的页的页号，而栈底恒存放近期最久没有方问过的页的页号，即准备被替换掉的页的页号。那么，我们在Cache——主存存贮层次中就可以按此思想实际组成一个硬件堆栈。2)过程（块号）（块号）（块号）（块号）（块号）2ncb个寄存器需重新排列的块号都下推一行被访问的块号（经相联比较找到）•寄存器堆栈压入ncb位近期最近访问过的块近期最久没有访问过的块图4.43全相联映象LRU法经堆栈实现（需要有相联比较功能）3)缺点：这种硬件堆栈既要求具有相联比较的功能，又要求能全下移、部分下移和从中间取出一项的功能，成本较高，因此只适用于组相联且组内块数较少的LRU替换场合。4)变形上述这种堆栈，各块被访问的先后次序由该项在堆栈中距离栈底是近还是远来反映。为了避免堆栈中各行存放的内容经常同时进行下移，以便节省成本，我们采用另一种变形，即将存放块号的寄存器的几何位置与Cache中的块号对应，而用寄存器存放值的大小来表示已被访问过的远近次序。以组相联为例，每一组均使用如图4.44那样的一个寄存器组，由2s个寄存器组成，每个寄存器为s位宽，可以存放表示从0到2s－1的次序值。如果让越是最近访问的，其次序值愈小，则只需通过相联比较求最大值（不是相联比较相符），找到该最大值所在的寄存器号，这就是对应Cache中应该被替换掉的块的块号。第0块的访问次序第1块的访问次序第2块的访问次序第2s-1块的访问次序块0块1块2块2s-12s个寄存器S位（其中一组）Cache存贮器（其中一组）图4.44组相联LRU法经寄存器实现（每组一个，需要有相联比较功能）2.比较对法1)思路比较法的基本思路是让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到LRU块。比如说有ABC三块，互相之间可以组合成ABBAACCABCCB6对，其中AB和BA、AC和CA、BC和CB是重复的，所以TAB为“1”，表示A比B更近被访问过；TAB为“0”，则表示B比A更近被访问过。TAC、TBC也类似定义。这样，当访问过的次序为ABC，即最近访问过的为A，最久未被访问过的为C，则这三个触发器状态分别为TAB＝1，TAC＝1，TBC＝1。如果访问过的次序为BAC，C为最久未被访问过的块，则此时必有TAB＝0，TAC＝1，TBC＝1。因此最久未被访问过的块C作为被替换掉的块的话，用布尔代数式必有：CLRU＝TAB•TAC•TBC+TAB•TAC•TBC＝TAC•TBC同理可得：BLRU＝TAB•TBC；ALRU＝TAB•TAC因此，完全可以用门、触发器等硬件组合实现，如图4.45所示：&&&010101TABTACTBCALRUBLRUCLRU•••访问B访问C访问A图4.15用比较对法实现LRU算法2)分析我们来看比较对法所用的硬件量。由于每块均可能作为LRU块，其信号需要用一个与门产生，例如ALRU与门要有从TABTAC来的输入，BLRU门要有从TAB，TBC来的输入，而与每块有关的对数个数为块数减去1，所以与门的扇入数是块数减去1。若p为块数，量量组合，比较对触发器的个数应为Cp2，即为p(p-1)/2。表4.2给出了比较对法块数p的取值与门数、门的输入端数及比较对触发器数的关系。3)总结替换算法实现的设计要围绕下面两点来考虑：a)如何对每次访问进行记录（使用位法、堆栈法和比较对法所用的记录方法都不同）；b)如何根据所记录的信息来判定近期内哪一块最久没有被访问过。由此可见，实现方法和所用的映象方法密切相关。例如，对于主存——辅存存贮层次的全相联映象宜于采用使用位法或类似的方法，而不宜采用堆栈法和比较对法；但对于Cache——主存存贮层次的组相联映象，因为组内块数较少，就宜于采用比较对法或堆栈法。替换算法的设计和实现也和器件的发展密切相关，随着器件技术的发展，尤其是高速相联存贮器片子的改进，已经而且必然会不断研制出新的更好的实现方法。4.3.4Cache的透明性及性能分析1.Cache的透明性分析1)两种问题的出现虽然Cache是主存的一部分副本，主存中某单元的内容却可能在一段时间里会与Cache中对应单元的内容不一致。例如，CPU往Cache写入，修改了Cache中某单元的内容，而在主存中对应于此单元的内容却可能仍是原来的，没有改变。这时，如果CPU或I/O处理机及其他处理机要经主存交换信息，那么主存内容跟不上Cache对应内容变化的这种不一致就会造成错误。同样，I/O处理机或其他处理机已把新的内容送入主存某个区域，而Cache中对应于此区域的副本内容却仍可能是原来的。这时，如果CPU要从Cache中读取信息，也会因为这种Cache内容跟不上主存对应内容变化的不一致而造成错误。因此，必须采取措施解决好由于读写过程中产生的Cache和主存对应内容不一致的问题。2)写回法写回法是在CPU执行写操作时，只是把信息写入Cache，仅当需要被替换时，才将已经被写入过的Cache块先送回主存，然后再调入新块。这种方法也称为抵触修改法，类似于虚拟存贮器中进行页面替换时的情况。因此，Cache——主存存贮层次的地址映象表中需对Cache中的每个块设置一个“修改位”，作为该块装入Cache后是否被修改过的标志。这样在块替换时，根据该块的修改位是否位1，就可以决定替换时是否先将该块存回主存原来的位置。3)写直达法写直达法也称为存直达法，它利用Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。这样，在块替换时，就不必先写回主存，而可以立即调入新页。显然，写回法是把开销花在每次需要替换的时候，而写直达法则把开销花在每次写入Cache时都附加一个比写Cache长的多的写主存时间。4)写不命中处理当出现写不命中时，无论是写回法还是写直达法都有一个在写时是否取的问题。一种是不按写分配法，即当Cache写不命中时只写入主存，该写地址单元所在块不从主存调进Cache。另一种是按写分配法，即当Cache不命中时除写入主存外，还把该写地址单元所在的块由主存调入Cache。这两种策略对不同的主存修改算法，其效果不同，但命中率差别不大。目前写回法一般采用按写分配法，而写直达法则一般采用不按写分配法。写回法和写直达法都需要有少量缓冲器。写回法中缓冲器用于暂存将要写回的块，使之不必等待被替换块写回主存后才开始进行Cache取。写直达法中缓冲器则用于缓冲由写Cache所要求的写回主存的内容，使CPU不必等待这些写主存完成就能往下运行。缓冲器由要存的数据和要存入的目标地址组成。在写直达系统中容量为4的缓冲器就可以显著改进其性能，IBM3033就是这样用的。要注意的这些缓冲器对Cache和主存是透明的。在设计时，要处理好可能由它们所引起的错误(如另一个处理机要访问的主存单元的内容正好仍在缓冲器中)。5)两种方法对比a)写回法有利于省去许多将中间结果写入主存的无谓开销。但是增加了Cache的复杂性。b)可靠性上写回法不如写直达法好。c)具体采用哪种方法还与系统使用场合有关。d)如果让多CPU共享主存交换信息改成共享Cache交换信息，信息的一致性就能得到保证。e)对于共享主存的多CPU系统，绝大多数还是采用各个CPU都有自己的Cache的方式与共享主存连接。这样的系统由于Cache的透明性，仅靠写直达法并不能保证同一主存单元在各个Cac