块映射策略

块映射策略是指当需要将来自内存的新数据块装入高速缓存时，由块映射策略决定它的存放位置。根据块在高速缓存内的位置，块映射策略可分成直接映射、全相联映射和组相联映射。

背景在主存和CPU之间可设置一个速度很快而容量相对较小的存储器，在其中存放CPU当前正在使用以及一个较短的时间内将要使用的程序和数据，这样，可大大加快CPU访问存储器的速度，提高机器的运行效率。

Cache的功能是用来存放那些近期需要运行的指令与数据，目的是提高CPU对存储器的访问速度，为此需要解决2个技术问题：

一是主存地址与缓存地址的映射及转换，就是块映射策略。1

二是按一定原则对Cache的内容进行替换，就是块替换策略。

详细介绍全相联映射方式全相联映射是指主存中任意一个块都可以映射到Cache中任意一个块的方式，也就是说，当主存中的某一块需调入Cache时，可根据当时Cache的块占用或分配情况，选择一个块给主存块存储，所选的Cache块可以是Cache中的任意一个块。例如，设Cache共有2块，主存共有2块，当主存的某一块j需调进Cache中时，它可以存入Cache的块0、块1、…、块i、…或块2-1的任意一块上。如图一所示。

在全相联映射方式下，CPU的访主存地址为如图二形式：

其中，M为主存的块号，W为块内的字号。而CPU访Cache的地址形式为，如图三所示：

其中，C为Cache的块号，W为块内的字号。

主存地址到Cache地址的转换是通过查找一个由相联存储器实现的块表来完成的，其形成过程如图四所示。

当一个主存块调入Cache中时，会同时在一个存储主存块号和Cache块号映射表的相联存储器中进行登记。CPU访存时，首先，根据主存地址中的主存块号M在相联存储器中查找Cache块号C，若找到，则本次访Cache命中，于是将对应的Cache块号取出，并送访Cache地址的块号C字段，紧接着将主存地址的块内字号W直接送Cache地址的块内字号W字段，从而形成一个访Cache的地址，最后根据该地址完成对Cache单元的访问。

优点：命中率比较高，Cache存储空间利用率高。

缺点：相联存储器庞大，比较电路复杂，访问相关存储器时，每次都要与全部内容比较，速度低，成本高，因而只适合于小容量的Cache之用，应用少。

直接相联映射地址映象规则：主存储器中一块只能映象到Cache的一个特定的块中。

(1)主存与缓存分成相同大小的数据块。

(2)主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数与缓存的总块数相等。

(3)主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。

图五表示出了直接相联映象规则。可见，主存中各区内相同块号的数据块都可以分别调入缓存中块号相同的地址中，但同时只能有一个区的块存入缓存。由于主、缓存块号相同，因此，目录登记时，只记录调入块的区号即可。

图六表示出了主、缓冲地址格式、目录表的格式及地址变换规则。主、缓存块号及块内地址两个字段完全相同。目录表存放在高速小容量存储器中，其中包括二部分：数据块在主存的区号和有效位。目录表的容量与缓存的块数相同。

地址变换过程：用主存地址中的块号B去访问目录存储器，把读出来的区号与主存地址中的区号E进行比较，比较结果相等，有效位为1，则Cache命中，可以直接用块号及块内地址组成的缓冲地址到缓存中取数；比较结果不相等，有效位为1，可以进行替换，如果有效位为0，可以直接调入所需块。

优点：地址映象方式简单，数据访问时，只需检查区号是否相等即可，因而可以得到比较快的访问速度，硬件设备简单。

缺点：替换操作频繁，命中率比较低。

举例：上例中，主存容量为1M，Cache的容量为32KB，每块的大小为16个字（或字节）。划出主、缓存的地址格式、目录表格式及其容量。

容量：与缓冲块数量相同即211=2048（或32K/16=2048）。

组相联映射方式组相联映射实际上是直接映射和全相联映射的折中方案，其组织结构如图七所示。主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同，组间采用直接映射，组内采用全相联映射。也就是说，将Cache分成u组，每组v块，主存块存放到哪个组是固定的，至于存到该组哪一块则是灵活的。例如，主存分为256组，每组8块，Cache分为8组，每组2块。

主存中的各块与Cache的组号之间有固定的映射关系，但可自由映射到对应Cache组中的任何一块。例如，主存中的第0块、第8块……均映射于Cache的第0组，但可映射到Cache第0组中的第0块或第1块；主存的第1块、第9块……均映射于Cache的第1组，但可映射到Cache第1组中的第2块或第3块。

优点：块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。

缺点：实现难度和造价要比直接映象方式高。

常采用的组相联结构Cache，每组内有2、4、8、16块，称为2路、4路、8路、16路组相联Cache。组相联结构Cache是前两种方法的折中方案，适度兼顾二者的优点，尽量避免二者的缺点，因而得到普遍采用。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学