朱贵宪　魏胜利

摘要：计算机组成原理是计算机科学与技术专业的专业基础课，其中缓存—主存地址映射方式作为该门课程的一个重要知识点，理解起来比较困难，该文以一个初学者的角度，用固定缓存和主存容量的办法详细解析主存—缓存地址映射方式，为学习本课程的学生提供参考。

关键词：主存；缓存；地址映射；计算机组成原理

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）19-0292-03

Abstract： Composition Principle of Computer is a professional basic course for computer science and technology. The Cache - Main Memory address mapping mode as an important knowledge of this course and it is difficult to understand. This article details resolution of this mapping method by fixed cache and main memory capacity from the perspective of a beginner. This provide reference for the learning of this course students.

Key words： Main Memory；Cache；Address Mapping；Composition Principle of Computer

1 主存的相关概念

计算机硬件系统的组成包括5个部分，分别是：运算器，控制器，存储器，输入系统和输出系统。其中存储器作为记忆部件，用来存放程序以及程序运行时所使用的数据。根据功能的不同，存储器可分为主存储器、高速缓冲存储器和辅助存储器。主存储器简称主存，有时也称内存，由半导体存储器构成，用于存放CPU执行程序时所需要的指令和数据。存储容量、存取时间是衡量主存储器性能的重要指标，存储容量是指存储器能存储二进制信息的总数量。存储器划分为多个存储单元，每个单元存放一组二进制信息。为了便于读出或者写入信息，存储器所有存储单元都用二进制数进行编号，这些编号称为“内存地址”。计算机按照内存地址对存儲单元进行访问，存储单元越多，需要的地址位数也就越多。如果地址总线是[n]位，则能够编址[2n]个存储单元。如果每个存储单元能够存放一个字节的二进制数据，则该存储器的容量为[2n]字节，即[2n]B。存取时间指的是存储器完成一次“写”操作（数据存入存储器）或者完成一次“读”操作（数据从存储器中取出）所需要的时间。存取时间反映了存储器读写数据的速度，它的快慢取决于存储器存储介质的物理特性和存储器的组织结构。

2 缓存的相关概念

由于计算机的CPU速度不断提高，主存的速度很难满足高速CPU的要求，所以通常在CPU与主存之间设置一级高速缓存（Cache）来解决二者之间的速度不匹配问题。主存、缓存与CPU之间的接方式如图1所示。由于计算机程序中的大部分指令和数据在主存中都是连续存放的，所以只要将CPU近期用到的指令和数据提前从主存送到缓存里面，在执行程序时，CPU就可以直接从缓存中读取信息，从而减少CPU访问主存的次数，提高计算机执行程序的速度。但由于缓存采用高速的半导体芯片制造，价格高且容量小，因此在程序执行过程中就要不断地将数据从主存调入缓存或者将缓存中的数据调出到主存。主存与缓存之间的数据调入调出完全是由硬件完成的，如何实现缓存与主存之间数据的高效传输，就需要熟知缓存与主存之间的地址映射方式。

3 缓存—主存系统存储结构

为了便于理解缓存—主存地址映射方式，应首先熟悉缓存—主存系统存储结构，如图2所示。这里假设缓存地址总位数为11位，缓存容量为2KB。把缓存地址分为两段，高[c]位表示缓存块号，低[b]位表示块内地址，[2c=C]表示缓存块数，这里采用高3位（[c=3]）表示块号，那么该缓存可以划分为0～7共8块；用低八位（[b=8]）表示块内地址，根据块内字数计算公式：[2b=B]，则每一块的块内字数B（也称块长）为256字，缓存总容量为8×256=2048字。依据图2，可以理解为把2KB的缓存划分成8块，每一个缓存块都内含256个存储单元，每个存储单元能保存一个字节（8位二进制数）的信息。

同时假设主存地址总位数为20位，容量为1MB。由于主存与缓存之间以块为单位进行数据传递，这就要求主存与缓存的块内字数相等（256字），所以仍需要8位表示块内地址，剩余12位表示缓存块号，即[m=12]，依据主存的块数计算公式：[2m=M]，可得主存块数为4096块。这样就可以把容量为1MB的主存划分为4096块，每一块都内含为256个存储单元，每个存储单元同样都可以保存一个字节的信息。

由于现实中主存的容量远远大于缓存的容量，所以主存的块数也远远大于缓存的块数。

4 缓存与主存的地址映射方式

缓存与主存的地址映射方式指的是缓存与主存地址之间的对应关系，常见的映射方式包括：直接映射，全相联映射和组相联映射。

4.1 直接映射

直接映射是指每个主存块都能按照某一固定的对应关系映射到可用的缓存块中。

在直接映射方式中，依据公式[i=jmodC]或者公式[i=jmod2c]，即可建立主存块与缓存块之间的对应关系。假设缓存块数是[C]=8，与之对应[c=3]，主存中的第4095块即[j=4095]，按照公式[i=jmod2c]去对应，可以计算出其对应缓存中的第7号缓存块，即[i]=7，依次类推，主存的4094块对应缓存的第6号块，主存的4093块对应缓存的第5号块，主存的4088块对应缓存的第0块。主存与缓存之间映射关系如图3所示。

根据图3可以看出，直接映射中每个缓存块可以对应若干个主存块，而每个主存块固定的对应某一个缓存块。

直接映射方式中主存地址由高[m]位和低[b]位组成，其中高[m]位又被分成两个部分：低[c]位是指缓存字块的地址，高[t]位是指主存字块标记。这里设[m]=12，[c]=3，则[t]=12-3=9，这时主存地址分为3个部分，[t]=9，[c]=3，[b]=8，主存地址构成如图4所示。可以理解为把主存的4096个字块分成0～511共512组（注意：这里的组和后面组相连的组概念不同），每一组都给予其赋一个9位的二进制编码，称为主存字块标记，依据图4，第0组的赋值是000000000，第511组的赋值为111111111，这两个赋值也是它们各自对应的主存字块标记，每一组内都含有8个字块，且这8个字块和缓存中的8个字块依次连接，主存共有512×8=4096块，缓存为8个字块，共2048个字。根据图3的分析可知多个主存块对应某一个缓存块，在上述的例子中，对于任一缓存块，共有4096/8=29=512个主存块与之对应，主存字块标记就是用来区分这些对应于同一个缓存块的不同主存块的。

CPU发来的主存地址中，高[m]位地址包含[t]位主存字块标记和[c]位缓存字块地址，可以根据中间的[c]位字段得出其对应的缓存块号，如图4所示，比如主存中的字块0，其主存地址高[m]位当中的低[c]位是000，那么其对应的缓存中的第0号缓存块，假设主存地址中间的[c]位字段为111，根据此内容可以在缓存中找到对应的字块7，缓存中字块7的内容具体是主存中第0组字块7的内容，还是第N（N≤511）组中字块7的内容，就需要利用缓存的[t]位标记与主存地址中的主存字块标记（[t]位）进行比较，若相等，如本例缓存的[t]位标记为111111111，主存字块标记也是111111111，则说明主存当中某一组（这里指第511组）的第7块的数据已经被预先送入到缓存中，即称之为命中，若不相等，表示主存块与缓存块还没有建立对应关系，即未命中，主存与缓存之间的映射关系如图4所示。

直接映射的优点在于实现简单，缺点是不够灵活，此外，当程序恰好需要重复访问对应同一个缓存块而不同的主存块时，就要不停地进行替换，从而降低了缓存命中率。

4.2 全相联映射

全相连映射方式中，主存的每一字块可映射到缓存的任一字块中，只要缓存中有空位，即可将主存映射到该位置，当缓存中没有空位时，可从缓存中替换出任一字块。采用全相联映射时，主存地址中主存字块标记为[t+c]位，即[m]位。当CPU访问某主存字时，需将主存字块标记同缓存中所有标记进行比较，以确定该主存块是否已经存放在缓存中。比如CPU希望访问主存的第4095字块中的某个存储单元，就需要先利用主存地址中的高[m]位（111111111111），与缓存中的8个字块前面各自对应的12位缓存标记进行比对，如图5所示，缓存中字块0的缓存标记刚好为111111111111，与主存地址中的高[m]位相同，称为命中，说明主存的第4095字块已经被预先存放到缓存的0字块当中。该映射方式所需要的硬件电路复杂，成本更高，而且有时需要多次比较，工作效率较低。

4.3 組相联映射

组相连映射中，将缓存块分成了[K]组，每组含[R]块，每一个主存块可以映射到[K]组缓存块中相应组内的任一块，设[i]为缓存组号，[j]为主存块号，[i]、[j]、[K]之间的关系为：[i=jmodK]。本例缓存共有8块，假设分成0～3共4组，即[K]=4，每组含2块（通常将组内含有两个字块的组相联映射称为二路组相联，此时[r=1]），即[R=2r=2]块。主存共有0～4095共有4096块，主存的第4095块，代入公式[i=jmodK]后，可计算出[i]为3，即主存的4095块对应缓存的第3组，依次类推，主存的第4094块对应缓存的第2组，主存的第4093块对应缓存的第1组，主存的4092块对应缓存的第0组，它们之间的地址映射关系如图6所示。

二路组相联映射（[r=1]）与直接映射相比，缓存字块地址字段由[c]位（3位）变为组地址字段[q]位（[q=c-r=2]），其中[2c=8]表示缓存的总块数，[2q=4]表示缓存的分组个数，[2r=2]表示组内包含的块数，如图6所示，这样就实现了把缓存中的8个字块分成4组，每组2块。对于缓存的分组总结起来可以理解为：缓存的总块数[÷]组内块数=缓存分组个数，即[2c÷2r=2q]，[q=c-r]。

在二路组相连映射中，主存地址分为主存字块标记[s]、组地址[q]和字块内地址[b]共3个字段。设主存的块内地址[b=8]位，[c=3]，[r=1]，[q=2]，主存字块标记字段变为[s=t+r]等于10位，形成1024个编码，组地址[q]为2位，形成4个编码，相当于把主存分成了1024部分，每部分包含4个字块，每个字块对应缓存中的一个缓存组。

假如CPU发来的主存地址的高[m]位为1111111111 11，首先根据组地址[q]（11），找到其对应的缓存组为第3组，再根据主存字块标记[s]（1111111111），与缓存的字块6和字块7前面的标记进行比对，假设缓存字块7前面的标记是10个1，则比对成功，说明主存的第4095字块已经被预先存放到缓存第3组的字块7当中。

通常将组内含有两个字块的组相联映射称为二路组相联，同理还有四路组相联（[r=2]，[R=4]）等，当[r=0]时，组相联映射则变成直接映射，当[r=c]时，则变成了全相联映射方式。

5 相关例题

例题：已知主存容量为1M×8位，缓存容量为2K×8位，块长为256个8位的字，按字地址访存，请分别写出在直接映射、全相联映射和二路组相联映射方式下主存的地址格式。若主存的容量变为1M×16位，缓存容量不变，在四路组相连方式下主存地址的格式又是什么？

解：（1）主存容量为1M字，所以主存地址为20位，缓存的容量为2K字，所以缓存的地址为11位，又因为块长为256个字，按字地址进行访存，所以块内地址占8位，缓存共有[2048÷256=8]块，缓存字块地址[c=3]位，在直接映射方式下，主存的字块标记长度为[20-3-8=9]位。

（2）在全相联映射方式中，除8位作为块内地址外，其他为均为主存字块标记，即[20-8=12]位。

（3）二路组相联即每组内有二个字块的组相联映射。每块256个字，每组2块，所以缓存共有[2048÷256÷2=4]组，组地址长度[q=2]，主存字块标记长度为[20-2-8=10]位。

（4）若主存容量变为1M×16位，字长仍然为8位，按字地址寻址，主存容量可看作2M×8位，即主存地址为21位，其中块内地址占8位，由四路组相连可知，缓存内共有[2048÷256÷4=2]组，所以组地址为1位，主存的字块标记长度为[21-1-8=12]位。

6 结束语

该文通过介绍主存、缓存的作用以及与之相关的概念，引出对缓存—主存地址映射方式的解析。为了便于理解，固定主存容量为1MB，缓存容量为2KB，主存和缓存的块长皆为256个8位的字，在此前提下对缓存—主存地址映射方式进行具体详细的分析，较好的化解了初学者对这部分内容在理解上的困惑。

参考文献：

[1] 魏胜利. 计算机组成原理[M]. 成都： 电子科技大学出版社， 2016.

[2] 唐朔飞. 计算机组成原理[M]. 北京： 高等教育出版社， 2012.

[3] 纪禄平. 计算机组成原理-面向实践能力培养[M]. 北京： 电子工业出版社， 2017.

[4] 白中英. 计算机组成原理[M]. 北京： 科学出版社， 2013.