存储器

存储器的校验

汉明码的组成

关于纠错理论的介绍，在此不多赘述。

假设需要检测的数据为n位，则我们需要添加的检验位的位数k需要满足下列公式，当理解了如何检验数据的过程后就能对这个公式有一定程度的理解。

$$
2^{k} \geq n + k + 1
$$

汉明码是如何检验的呢？我们直接从栗子开始看。

假设我们需要传输的数据为1011，根据上面的原理，我们需要三个校验位，我们将它们放在数据的1，2，4位上，分别叫做P1,P2,P3（现在不理解也没关系）

每个校验会负责不同位置的校验，在本例中 P1负责的是1 3 5 7号位置 P2负责2 3 6 7号位置 P3负责 4 5 6 7号位置 （现在不理解没关系）

通常采用偶校验的方式，我们先来介绍如何算出校验位

偶校验其实就是，检验位负责的各位置之和要为偶数 所以 对于P1 P1+1+0+1 为偶 所以 P1 = 0

同理 算出P2 = 1 P3 = 0 于是 我们完整的汉明码即为 0110011

假设我们 接受到的数据为 0110111 （第五位出错，我们仅考虑一位出错）

接收方如何发现第五位出错的呢？

检查校验位，P1负责的1357会变为奇数，P2的则不变，P3负责的 4567 也会变为奇数 我们检查出错区域的重合部分 即可发现是第五位出错

现在 你可能还有一些疑惑。到底是如何规定哪些校验位负责哪些区域的呢？如何保证出错区域的重合部分仅有一个数呢？

其实，校验位所负责的部分为 二进制数值编码中，所在编号位置为1的所有位置（先别骂不说人话）

举个栗子 仍是上述栗子 共有7位 可以用三位二进制数表示 0 0 0

则P1负责的位数为 所有第一位为1 的数 001 011 101 111 即1357

当 某一位出错的时候，所有出错的检验位在对应位数的值为1（先别骂不说人话）

仍然是上面的栗子 我们通过检查可以发现 P1和P3不满足偶校验原则，所以出错位的二进制数值在 第一位和第三位为1，其余位为0 所以其为101

至此 你已经理解了为什么要将P1 P2 P3 放在1 2 4号位置 （现在不理解有关系QAQ）

提高访存速度的策略

单体多字系统

由于程序和数据在存储体内是连续存放的，因此 CPU 访存取出的信息也是连续的，如果可以在一个存取周期内，从同一地址取出 4条指令，然后再逐条将指令送至 CPU 执行，即每隔 1/4存取周期，主存向 CPU送一条指令，这样显然增大了存储器的带宽，提高了单体存储器的工作速度

图中示意了一个单体四字结构的存储器，每字 W位。按地址在一个存取周期内可读出 4xW位的指令或数据，使主存带宽提高到4倍。显然，采用这种办法的前提是：指令和数据在主存内必须是连续存放的，一旦遇到转移指令，或者操作数不能连续存放，这种方法的效果就不明显。

多体并行系统

多体并行系统就是采用多体模块组成的存储器。每个模块有相同的容量和存取速度，各模块各自都有独立的地址寄存器(MAR) 、数据寄存器(MDR)、地址译码、驱动电路和读／写电路，它们能并行工作，又能交叉工作。

高位交叉

并行工作即同时访问 N个模块，同时启动，同时读出，完全并行地工作（不过，同时读出的 N个字在总线上需分时传送）。图4.42是适合于并行工作的高位交叉编址的多体存储器结构示意图，图中程序因按体内地址顺序存放（一个体存满后，再存入下一个体），故又有顺序存储之称。
显然，高位地址可表示体号，低位地址为体内地址。按这种编址方式，只要合理调动，使不同的请求源同时访问不同的体，便可实现并行工作。例如，当一个体正与 CPU交换信息时，另一个体可同时与外部设备进行直接存储器访问，实现两个体并行工作。这种编址方式由于一个体内的地址是连续的，有利于存储器的扩充。

高位交叉并不能提高性能。

低位交叉

采用低位交叉的方式，连续的数据存在不同的存储器中。采用交叉编址的方式，显然低位地址用来表示体号，高位地址为体内地址。这种编址方法又称为模M编址(M等干模块数）

多体模块结构的存储器采用交叉编址后，可以在不改变每个模块存取周期的前提下，提高存储器的带宽。图4.44示意了CPU交叉访问4个存储体的时间关系，负脉冲为启动每个体的工作信号。虽然对每个体而言，存取周期均未缩短，但由于CPU交叉访问各体，使4个存储体的读／写过程重叠进行，最终在一个存取周期的时间内，存储器实际上向CPU提供了4个存储字。如果每个模块存储字长为32位，则在一个存取周期内（除第一个存取周期外），存储器向CPU提供了32x4=128位二进制代码，大大增加了存储器的带宽。

假设每个体的存储字长和数据总线的宽度一致，并假设低位交叉的存储器模块数为n，存取周期为T，总线传输周期为τ，那么当采用流水线方式（如图4.44所示）存取时，应满足T=nτ。为了保证启动某体后，经nτ时间再次启动该体时，它的上次存取操作已完成，要求低位交叉存储器的模块数大于或等千n。以四体低位交叉编址的存储器为例，采用流水方式存取的示意图如图4.45所示。

可见，对千低位交叉的存储器，连续读取n个字所需的时间 t1 为t1 =T+(n-1)τ

若采用高位交叉编址，则连续读取 n个字所需的时间 t2 为 t2 =nT

打个比方，总线跑的快，他需要从多个体中取数据，之前总线是敲敲第一家门，等存储体把数据送出来，送到CPU后，还要到第一家送货一直等。

而现在，连续的数据在不同的家门，总线只需要挨家挨户敲门，等第一家开门后送第一家，回来的时候第二家已经开门了，就能实现持久的送货，提高效率。

高速缓冲存储器

在多体并行存储系统中，由于I/0设备向主存请求的级别高于 CPU访存，这就出现了 CPU等待 I/0 设备访存的现象，致使 CPU 空等一段时间，甚至可能等待几个主存周期，从而降低了CPU 的工作效率。为了避免 CPU 与 I/0 设备争抢访存，可在 CPU 与主存之间加一级缓存，这样，主存可将 CPU 要取的信息提前送至缓存，一旦主存在与 I/0 设备交换时，CPU 可直接从缓存中读取所需信息，不必空等而影响效率。这就是Cache的由来。

Cache

局部性原理

• 时间局部性：程序马上要用的数据可能就是现在正在频繁访问的数据
• 空间局部性：程序马上要用的信息很可能就是现在正在访问的数据周围的数据

Cache访问主存是按照块来搬运的，每次将一块的数据搬运到Cache中

Cache的工作原理

主存由 2n 个可编址的字组成，每个字有唯一的 n位地址。为了与 Cache 映射，将主存与缓存都分成若干块，每块内又包含若干个字，并使它们的块大小相同（即块内的字数相同)。这就将主存的地址分成两段：高m位表示主存的块地址，低b位表示块内地址，则 2^m=M表示主存的块数。

同样，缓存的地址也分为两段：高c位表示缓存的块号，低 b位表示块内地址，则 2^c= C表示缓存块数，且 C远小于M。主存与缓存地址中都用 b位表示其块内字数，即B=2^b 反映了块的大小，称B为块长。

任何时刻都有一些主存块处在缓存块中。 CPU 欲读取主存某字时，有两种可能：一种是所需要的字巳在缓存中，即可直接访问 Cache(CPU 与 Cache 之间通常一次传送一个字） ；另种是所需的字不在Cache 内，此时需将该字所在的主存整个字块一次调入 Cache 中(Cache 与主存之间是字块传送）。如果主存块已凋入缓存块，则称该主存块与缓存块建立了对应关系。

上述第一种情况为 CPU访问 Cache命中，第二种情况为 CPU访问 Cache 不命中。由于缓存的块数 C远小于主存的块数M，因此，一个缓存块不能唯一地、永久地只对应一个主存块，故每个缓存块需设一个标记 ，用来表示当前存放的是哪一个主存块，该标记的内容相当于主存块的编号。 CPU读信息时，要将主存地址的高 m 位（或 m位中的一部分）与缓存块的标记进行比较，以判断所读的信息是否已在缓存中。
Cache 的容量与块长是影响 Cache 效率的重要因素，通常用”命中率”来衡量 Cache 的效率。

在一个程序执行期间，设 $N_c$ 为访问 Cache 的总命中次数，$N_m$ 为访问主存的总次数，则命中率 $h$ 为

$$
h = \frac{N_c}{N_c + N_m}
$$

设 $t_c$ 为命中时的 Cache 访问时间，$t_m$ 为未命中时的主存访问时间，$1-h$ 表示未命中率，则 Cache-主存系统的平均访问时间 $t_a$ 为

$$
t_a = ht_c + (1-h)t_m
$$

当然，以较小的硬件代价使 Cache-主存系统的平均访问时间 $t_a$ 越接近于 $t_c$ 越好。用 $e$ 表示访问效率，则有

$$
e = \frac{t_c}{t_a} \times 100% = \frac{t_c}{ht_c + (1-h)t_m} \times 100%
$$

显然，h越接近1，访问效率越高

Cache的基本结构原理框图

为便于Cache与主存交换信息，Cache和主存都被划分为大小相等的块，Cache块也称Cache
行，每块由若干字节组成，块的长度称为块长（也称行长）。因为Cache的容量远小于主存的容量，所以Cache中的块数要远少于主存中的块数，Cache中仅保存主存中最活跃的若干块的副本。因此，可按照某种策略预测CPU在未来一段时间内欲访存的数据，将其装入Cache。

CPU的读写请求与Cache变化过程

当CPU发出读请求时，若访存地址在Cache中命中，就将此地址转换成Cache地址，直接对Cache进行读操作，与主存无关：若Cache不命中，则仍需访问主存，并把此字所在的块一次性地从主存调入Cache。若此时Cache已满，则需根据某种替换算法，用这个块替换Cache中原来的某块信息。整个过程全部由硬件实现。值得注意的是，CPU与Cache之间的数据交换以字为单位，而Cache与主存之间的数据交换则以Cache块为单位。
当CPU发出写请求时，若Cache命中，有可能会遇到Cache与主存中的内容不一致的问题。
例如，由于CPU写Cache，把Cache某单元中的内容从X修改成X，而主存对应单元中的内容仍
然是X，没有改变，因此若Cache命中，需要按照一定的写策略处理，常见的处理方法有全写法和回写法，详见下文。

Cache——主存地址映射

由于Cache行数比主存块数少得多，因此主存中只有一部分块的信息可放在Cache中，因此
在Cache中要为每块加一个标记位，指明它是主存中哪一块的副本。该标记的内容相当于主存中块的编号。为了说明Cache行中的信息是否有效，每个Cache行需要一个有效位。Cache行中的信息是主存中某个块的副本，地址映射是指把主存地址空间映射到Cache地址空间，即把存放在主存中的信息按照某种规则装入Cache。地址映射的方法有以下3种。

直接映射

主存中的每一块只能装入Cache中的唯一位置。若这个位置已有内容，则产生块冲突，原来
的块将无条件地被替换出去（无须使用替换算法）。直接映射实现简单，但不够灵活，即使Cache的其他许多地址空着也不能占用，这使得直接映射的块冲突概率最高，空间利用率最低。

直接映射的地址结构及映射关系

假设Cache共有$2^{c}$行，主存有$2^{m}$块,在直接映射方式中，主存的第0块、第$ 2^c$块、第$2^{c+1}$
块···只能映射到Cache的第0行；而主存的第1块、第$ 2^c$+1块··只能映射
到Cache的第1行，以此类推。由映射函数可看出，主存块号的低c位正好是它要装入的Cache
行号。给每个Cache行设置一个长为t=m-c的标记（tag)，当主存某块调入Cache后，就将其
块号的高t位设置在对应Cache行的标记中

全相联映射

全相联映射允许主存中每一字块映射到Cache中的任何一块位置上。这种映射方式可以从已被占满的Cache中替换出任一旧字块。显然，这种方式灵活，命中率也更高，缩小了块冲突率。与直接映射相比，它的主存字块标记从t位增加到t+c位，这就使Cache“标记”的位数增多，而且访问Cache时主存字块标记需要和Cache的全部“标记”位进行比较，才能判断出所访问主存地址的内容是否已在Cache内。

这种方法需要很多逻辑电路，成本高，而且需要采用许多优化算法减少比较次数。

组相联映射

组相联映射是对直接映射和全相联映射的一种折中。它把Cache分为Q组，每组有R块，并有以下关系：

**i = j mod Q **

其中，i为缓存的组号，j为主存的块号。某一主存块按模Q将其映射到缓存的第i组内。

虚拟存储器

主存和辅存共同构成了虚拟存储器，二者在硬件和系统软件的共同管理下工作。对于应用程
序员而言，虚拟存储器是透明的。虚拟存储器具有主存的速度和辅存的容量。

概念

虚拟存储器将主存或辅存的地址空间统一编址，形成一个庞大的地址空间，在这个空间内，用户可以自由编程，而不必在乎实际的主存容量和程序在主存中实际的存放位置。

用户编程允许涉及的地址称为虚地址或逻辑地址，虚地址对应的存储空间称为虚拟空间或程序空间。实际的主存单元地址称为实地址或物理地址，实地址对应的是主存地址空间，也称实地址空间。虚地址比实地址要大很多。

CPU使用虚地址时，先判断这个虚地址对应的内容是否已装入主存。若已在主存中，则通过地址变换，CPU可直接访问主存指示的实际单元；若不在主存中，则把包含这个字的一页或一段调入主存后再由CPU访问。若主存已满，则采用替换算法置换主存中的交换块（页面）。

页式虚拟存储器

页式虚拟存储器以页为基本单位。主存空间和虚拟地址空间都被划分成相同大小的页，主存空间中的页称为物理页、实页、页框，虚拟地址空间中的页称为虚拟页、虚页。页表记录了程序的虚页调入主存时被安排在主存中的位置。页表一般长久地保存在内存中。

参考书籍 – 计算机组成原理第三版 王道考研计算机组成原理