6．4．2 高速缓存—主存地址映射及变换
地址映射是指把主存地址空间映射到Cache地址空间，具体地说就是把存放在主存中的程序按照某种规则装入到Cache中，并因此建立主存地址与Cache地址之间的对应关系。
地址变换是指在程序运行时，根据地址映射把主存地址变换成Cache地址。地址变换和地址映射是紧密相关而又不同的两个概念。
常用的地址映射方式有全相联映射、直接映射和组相联映射。
1．全相联映射及其地址变换
（1）全相联映射
相联映射方式是指主存中任一个块能够映射到Cache中任意一块的位置，如图6．23所示。这是一种最灵活但成本最高的一种方式。
图6．23 全相联映射方式
为简单起见，本书只画出了Cache大小为4块，主存大小为8块的情况。
如果Cache的块数为C b（例如C b＝4），主存的块数为M b（例如M b＝8），则主存和Cache之间的映射关系有C b×M b（4×8＝32）种，可用目录表来存放这种映射关系。目录表的每一行表示一种映射，目录表如图6．24所示。目录表的内容包含三个部分：主存块号B、Cache块号b和1个有效位。有效位是用来表示目录表中由主存块号B与Cache块号b建立的映射关系是否有效。有效位为“1”表示有效，Cache第b块中存放的数据是主存第B块中数据的副本；有效位为“0”表示无效，不是正确副本。目录表可用相联存储器构成。
（2）地址变换
在执行程序时，CPU 先访问Cache，用主存块号B 与从目录表读出的主存块号字段进行逐一比较。如果有相等的，而且有效位为“1”，表示要访问的数据已经装入到Cache中。
当有效时，将目录表中的b送入Cache地址寄存器的b位置，主存块内地址W 送到Cache地址寄存器的w 位置，形成Cache地址，访问Cache后，把读出的字送向CPU，从而完成读出。
如果不相等，且有效位为“0”，这时要用主存地址去访问主存，从主存读出一字送向CPU。同时还要依照替换算法淘汰Cache中一个块；把主存读出的该字所在的块全部写入Cache；修改目录表中的一行，得到新的Cache主存-映射。
图6．24 全相联映射目录表和地址变换
2．直接映射及地址变换
（1）直接映射
直接映射方式是规定主存中的每一个块只能被放置到Cache中的唯一一个位置。
根据Cache的大小把主存分成若干个区（域），因此主存容量是Cache容量的若干倍。主存每区分块，Cache也分成若干块，块大小一致。主存每区的大小和Cache的大小一致，或者说主存每区含的块数和Cache含的块数相同。主存中某区的一块存入Cache时只能存入Cache中块号相同的位置。例如0区中的第0块和1区中的第0块都只能映射到Cache的块0中，如图6．25所示。为了简化问题，图6.25中主存分为2个区，每个区分为4个块。Cache也分为4个块。
此时主存的地址由区号E、区内块号B和块内地址W 构成，而Cache的地址由块号b（b＝B）和块内地址w（w＝W）构成。
图6．25 直接映射
（2）地址变换
在程序执行过程中，用主存地址的组内块号B去访问Cache，把读出的区号E（同时也读出了这一块的所有数据）和主存地址的区号E进行比较。
如果比较结果相等且有效位为“1”，则Cache命中，表示要访问的某块已在Cache中。与此同时，读出的数据通过一个多路选择器（1/W），在块内地址W 的控制下，把所需的字输出到CPU。
如果结果相等但有效位为“0”，表示此Cache块已经无效（可以淘汰），只要把从主存中读出的新块装入到Cache中，有效位置“1”即可。
如果结果不等说明没有命中，而有效位为“0”，说明此Cache块已无效（即空白），可把从主存读出的新块装入到Cache，将主存区号写到Cache的区号字段，有效位置“1”。
如果结果不相等，有效位为“1”，虽然未命中，但此Cache块不能废弃。于是先将此Cache块内容写回主存原单元（原区原块位置），然后把从主存读出新块装入Cache。当然主存区号也要写到Cache的E字段。工作过程原理如图6．26所示。
图6．26 直接映射方式地址变换
全相联映射方法需要用算法决定将Cache的块分配给相应的主存的块。直接映射方法节省了计算时间，提高了调入页面的效率。
直接映射方法的另一优点是硬件实现简单，无须进行地址变换，因而访问速度较快。由于直接映射的这一特点，若主存中两个或两个以上的块都映射到Cache的同一块中，而这些块又都是当前常用块时就产生了冲突，这时即使Cache有许多空闲块也不能使用，因而造成Cache空间利用率降低，并且Cache的命中率会很低。这一点正好是全相联映射方式的优点。
3．组相联映射及其地址变换
（1）组相联映射
组相联映射的基本原理是：将Cache存储空间的块分成若干组，主存空间的块按Cache组数分成若干区，每个区内的块与Cache组之间采用直接映射，而组内各块则采用全相联映射，即主存块存放到哪个组是固定的，存到该组中哪一个块是灵活的，因而可以增加命中率和系统效率。
组间直接映射是指某组内的Cache块只能与固定的一些主存块建立映像关系，这种映像关系可用下式表示：
G′＝B mod G
式中，B 是主存的块号，G 为Cache的组数，G′为主存块B 对应的Cache的组号。例如，Cache组0只能和满足B mod G＝0的主存块（即块0、块G、块2G 等）建立映像关系，Cache的组1只能和满足B mod G＝1的主存块（即块1、块G＋1、块2G＋1…）建立映像关系，以此类推。
组内全相联映像是指和某Cache组相对应的主存块可以和该组内的任意一个Cache块建立映射关系，设C＝2c表示Cache的字块总数，现将Cache分成G＝2g组，每组V＝2v个块，则G∗V＝2g∗2v＝2c，即c＝g＋v。此时的Cache称为V 路组相联Cache。
综上可得组相联的映像函数：
L＝(B mod G)∗V＋K＝(B mod 2g)∗2v＋K
式中，B 是主存的块号，L 是Cache的块号，K 是组内块号，0≤K≤V-1。
图6．27为路组相联映像示意图。其中Cache每2块组成一组，即V＝2，v＝1。主存块0、G、2G…1均直接对应Cache的组0，其内容可以存放在该组内的第0、1块的任何一块中，对应的Cache块号分别为0、1。主存块1、G＋1、2G＋1…均对应Cache的组1，其内容可以存放在该组内的第0、1块的任何一块中，对应的Cache块号分别为3、4，依此类推。
图6．27 组相联映射
可以看出，当Cache每组仅有1块时，就成了直接映射方式；而当Cache只有一个组时，就成了全相联映射方式。组相联映射方式既避免了全相联方式时分配页面时的大量计算，也减少了直接映射方式时块的冲突，提高了存储体系的效率，因而在计算机中得到广泛的应用。
（2）地址变换
在组相联方式下，主存地址中的“主存块号”被进一步划分为“主存字块标记”与“Cache组号”，即主存地址分为三部分：主存字块标记（s位）、Cache组号（g 位）、块内地址（b位），主存地址位数m＝w＋b＝s＋g＋b。“主存字块标记”（也即主存区号）为写入Cache标记中的内容。
Cache地址也由三部分组成，其中的“Cache组号”“块内地址”与主存地址中的“Cache组号”“块内地址”对应（位数与内容均相同），从主存地址中，就可以直接提取出这两部分的值。而“组内块号”即为组相联的映像函数中的K，占v 位。Cache地址位数n＝c＋b＝g＋v＋b位。“Cache组号”与“组内块号”构成了“Cache块号”，如图6.28所示。
图6.28 Cache块号
组相联检索过程如图6．29所示，其命中与未命中的处理方法与全相联映射和直接映射一样。但检索时，首先根据“组号”直接找到Cache组，然后用“主存地址标记”字段与该组的每个Cache块标记逐一比较以确定是否命中。
图6．29 组相联映射方式的地址变换