摘要：CPU当前访问的数据若在高速缓存（Cache）中，就应该将已知的内存地址转换为Cache地址，具体转换的方式与当前内存和Cache的映像方式有关。每一种映像方式中二者地址间的关系的关键是搞清楚Cache和内存的地址结构。

　　关键词：内存；Cache；地址结构；地址映像
　　中图分类号：G642 文献标识码：A 文章编号：1007-9599　（2012）　19-0000-02
　　在现代计算机中，存储系统均采用三级层次结构，即外存-内存-Cache。当前进程肯定在内存中，但是否在Cache中主要和命中率有关。当CPU运行时，获取的是虚地址，该虚地址经过地址转换部件可自动转换为内存地址；若该内存地址所在的页已从内存调入Cache，则此时就应将内存地址转换为Cache地址。从内存地址到Cache地址的转换（或称映像）与内存和Cache的映像方式有关，二者映像的关键是在具体映像方式下二者的地址的表示方式，即地址结构。下面就直接映像、全相联映像和组相联映像这三种最常见的映像方式的地址结构及地址转换过程进行分析。
　　1 直接映像
　　直接映像方式要求能直接把内存地址转换为Cache地址，其实现原理如下：
　　1.1 Cache组织。从物理角度看，Cache的结构与内存结构完全相同，均是一维结构。在直接映像方式，系统对Cachec是以页为单位进行组织。此时，逻辑上Cache是一个二维结构的存储器。
　　假设：Cache长度为2k个单元，共分2p页，每页的大小为2i个单元，即，k=p+i。从逻辑上看，一个k位的Cache地址可转换为一个二维地址表示：
　　二维地址 Ap+i…Ai+1　（P位） Ai　…　A1 （i位）
　　含义 Cache页号 页内地址
　　即：一个Cache单元地址的高p位是页号，低i位是页内地址。
　　1.2 内存组织。在直接映像方式下，内存是先作页的划分，然后再把页组织成组（或称区），即将内存转换成一个三维结构的存储器。其中，内存页与Cache页的大小相同，内存一个组内包含的页数就是Cache的页数。
　　假设：内存长度为2n个单元，共分为2m个组，每个组包含2p页，每页的大小为2i个单元，即n=m+p+i。逻辑上一个n位的内存地址可分为三个部分：
　　三维地址 Am+p+i…　Ap+i+1（m位） Ap+i…Ai+1（P位） Ai…A1（i位）
　　含义 内存组号 内存组内页号 页内地址
　　即：一个内存单元地址的高m位是组号，中间的p位是页号，低i位是页内地址。其中，内存组号也称为内存标记。
　　1.3 映像规则。内存以页为单位调入Cache，当将内存页调入Cache时，内存的组内页号就是Cache的页号。由于内存页与Cache页的大小相等且以页单位进行管理，因此，二者的页内地址也相等，也即内存的组内页号及页内地址就是Cache的页号及页内地址。
　　由于内存容量远大于Cache容量，因此，组内页号相等的内存页有无数，这样，内存页与Cache页的对应关系就是1：多的映像关系。为了准确反映内存页与Cache页的映像，需要一张映像表来记录，该表主要记录内存组号（内存标记）与Cache页的关系，具体见下例。
　　例：某机现有一Cache容量为1KB，256B/页，内存容量1MB，存储器编址方式为字节。试问：
　　（1）地址为1a2b3H的内存单元按直接映像方式调入Cache，Cache地址？
　　（2）若已将内存的2、3、5、8页调入Cache，映像表的内容是什么？此时，如何判断7页是否在Cache中？
　　解：由题意可知：
　　可知内存7（111B）页的内存标记为1，组内页号为11。具体判断过程是：以页号11为索引访问映像表的11行，将获得的内存标记0与自身的内存标记1进行比较，现不相等，因此，说明7页不在Cache中。
　　2 全相联映像方式
　　2.1 Cache组织。Cache的组织与直接映像方式完全相同。即：
　　假设：Cache长度为2k个单元，共分2p页，每页的大小为2i个单元，这样，一个k位的Cache地址的高p位是页号，低i位是页内地址。
　　2.2 内存组织。内存的组织与Cache的组织完全相似，即以页的方式对内存进行组织。
　　假设：内存长度为2n个单元，每页的大小为2i个单元，这样，逻辑上一个n位的内存地址可分为二个部分：
　　二维地址 An…Ai+1（n-i位） Ai…A1（i位）
　　含义 内存页号 页内地址
　　即：一个内存单元地址共n位，其中：高n-i位是页号，低i位是页内地址。
　　2.3 映像规则。内存以页为单位调入Cache，内存的一页可调入Cache的任一页，即内存页与Cache无明确的映像关系。但由于二者页的大小相等，故二者的页内地址相等。现需一张映像表，主要用来记录二者页间的对应关系，表如下例所示。
　　例：某机现有一Cache容量为1KB，256B/页，内存容量1MB，存储器编址方式为字节。试问：若已将内存的2、3、5、8页调入Cache，映像表的内容是什么？此时，如何判断7页是否在Cache中？
　　解：由题意可知：
　　判断过程：以页号7（111B）作为关键字在映像表的主存页号列中按顺序方式进行搜索，现不能搜索到，则说明7页没有调入Cache。
　　3 组相联映像方式
　　组相联映像方式实际上是以上二种方式的折衷方式，期望具有直接映像方式地址转换速度快，同时具有全相联映像方式灵活性好的优点。
　　3.1 Cache组织。Cache的组织与直接映像方式中内存的组织相同，即将Cache先作页的划分，然后再作组的划分。 　　假设：Cache长度为2k个单元，共分为2c组，每组有2p1页，每页的大小为2i个单元，即：k=c+p1+i。这样，逻辑上一个k位的Cache地址可分为三个部分表示：
　　三维地址 Ac+p1+i…Ap1+i+1（c位） Ap1+i…Ai+1（P1位） Ai…A1（i位）
　　含义 Cache组号 Cache组内页号 页内地址
　　3.2 内存组织。内存的组织与Cache相同，即将内存先作页的划分，然后再作组的划分。
　　假设：内存长度为2n个单元，共分为2m个组，每个组包含2p2页，每页的大小为2i个单元，即，n=m+p2+i。此时，逻辑上一个n位的内存地址可分为三个部分：
　　三维地址 Am+p2+i…Ap2+i+1（m位） Ap2+i…Ai+1（P2位） Ai…A1（i位）
　　含义 内存组号 内存组内页号 页内地址
　　需要注意的是：
　　（1）二者页的大小相等；
　　（2）二者组的大小（即一组中包含的页数）不相等，即p1≠p2；
　　（3）内存一组中包含的页数等于Cache的组数，即p2=c。
　　3.3 映像规则。由于p2=c，因此，内存的一页只能调入组号与其组内页号相等的Cache组，但该内存页的页号与Cache的组内页号无关系，具体分配到哪页由当时该Cache组的空闲状态确定，即内存页只与Cache组号存在关系，而与Cache页号无关。此时，需要一线映像表，用来记录内存组号与Cache的组及组内页号间的映像关系，该表结构见下例。
　　例：某机现有一Cache容量为4KB，共分4组，256B/页；内存容量1MB，存储器编址方式为字节。试问：
　　（1）地址为1a2b3H的内存单元按组相联映像方式调入Cache，Cache地址？
　　（2）若已将内存的2、3、4、5、6、7、8页调入Cache，映像表的内容是什么？此时，如何判断7页是否在Cache中？
　　解：由题意可知：
　　Cache地址结构：2位组号 2位页号 8位页内地址
　　内存地址结构：10位组号 2位组内页号 8位页内地址
　　（1）由内存地址1a2b3H=0001　1010　0010　1011　0011B，可知：
　　低8位：1011　0011B为Cache的页内地址；中间2位：10B为Cache的组号；不能由内存地址准确地确定Cache的2位组内页号，故该内存单元在Cache的地址为：
　　10　XX　1011　0011B（XX代表不确定的二位2#数）
　　1）表中数据以2#表示；
　　2）假设Cache组内按页号顺序分配；
　　3）表中的数据项是调入到该组该页的相应的内存页的组号。
　　判断过程：以7（111B）页的组内页号11B为索引搜索11B行，按顺序方式在11B行搜索关键字1B（组号），现搜索到，说明7页已调入Cache。
　　4 总结
　　Cache与内存地址映像的关键首先是搞清楚在一种具体映像方式下Cache和内存的地址结构，即地址每个部分的逻辑含义；其次，根据已知条件确定每一部分地址的位数；第三，根据具体的映像方式确定二者地址中相等的关系。
　　参考文献：
　　[1]唐朔飞.计算机组成原理[M].北京：高等教育出版社.
　　[2]罗克露.计算机组成原理[M].北京：电子工业出版社.
　　[3]郑纬民.计算机系统结构[M].北京：清华大学出版社.