2 3

第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

### 2 3
4
5
6
### 7 8 9
### 10 11 12
故障字正确
含义P; P? M? P? M? M? M P? M? M? M?M
出 错 位
### 12 345678910 11 12
第4组
√√
√√
√S 0 0 0 0000011 1 1 1
第3组
√√
√
√
√S? 0 000111100 0 0 1
第2 组
√
√
√
√
√
S? 0 011001100 1 1 0
第1组
V
√
√
√
√
√
S? 0 10 1010101 0 1 0
观察表7.1可发现一个比较直观的规律：校验位 P,在码字中位于2'-'位，从该位开始
的连续 21-1位，以及每隔2'-'位后连续的2'-'位都被分配在P,对应的组。例如，P?从第
22-1=2位开始，码字中第2、3两位在P:对应的组，跳过4、5两位后的第6、7位、跳过8、9
两位后的第10,11位都在P?对应的组；校验位P?从第23-1=4位开始，码字中第4、5、6、7
共4位在P?对应组，跳过8、9、10、11共4位后，第12位也在 P?对应组。若后面还有第
M?、M?、M?等数据位，则它们在码字中位于第13、14、15位，因而，码字中第12、13、14、15
位共4位都在P?对应组，不过，超过12个数据位时，则需用5个校验位。
从表7.1中可看出，每一个数据位至少要参与两组奇偶校验位的生成，例如，M;与第1
组(P?)和第4组(P)有关，M,与第1组(P?)、第2组(Pa)和第4组(P)有关。而且，同一


<!-- page: 246 -->

存储器层次结构
组中只有一个校验位P,因此，可对同一组各位进行奇偶校验，生成对应的校验位P
3.校验位的生成和检错、纠错
分组完成后，就可对每组采用相应的奇(偶)校验，以得到相应的一个校验位。假定有
10个数据位，即M=M?M,M?M,M?M?M?M?M?M?,采用偶校验，则4个校验位与10个
数据位之间存在如下关系：
P?=M?M?M?+M?+M,+M,
P?=M?M?⊙M?+M?M?M?
P?=M?M?M?M?⊙M?+M。
P?=M?④M?④M?④M?+M,+M
根据上面的公式，可以求出每一组对应的校验位P(i=1,2,3,4)。数据M和校验位P一
起被存储。读出后的数据M'通过上述同样的公式生成得到新的校验位P',然后将读出后
的校验位 P"与新生成的校验位 P'按位进行异或操作，得到故障字S=S?S?S?S,根据S
的值可以确定是否发生了错误，并且在发生错误时能确定是校验位发生错误还是哪个数据
位发生了错误。
下面举例说明具体的检错、纠错过程。
例7.1假定一个7位数据M为M?M?M?M?M?M?M?=1101010,其对应的校验位为
P,M和P被存储或经传送后得到的新数据和新校验码分别为M'和P"。要求分别求出以
下情况下的故障字并验证其正确性。
(1)M'=1101010,P"=0011。
(2)M'=1111010,P"=0011。
(3)M'=1101010,P"=1011。
解：7个数据位和4个校验位构成的码字排列为M?M?M;P?M?M?M?P?M?P?P?,得
到数据M的校验位P中相应各位的取值如下：
P?=M?M?+M?+M?+M?=0+1+1+0+1=1
P?=M?④M?④M?④M?+M?=0④0+1+1+1=1
P?=M?④M?④M?=1④0+1=0
P?=M?M?+M,=0④1+1=0
(1)当M'=1101010,P"=0011时，因为M'=M,说明数据无错，故障字S应为0。验
证如下：因M'=M,故P'=P,同时P"=P,因此故障字S=P"④P'=P+P=0000。
(2)当M′=1111010,P"=0011时，说明数据第5位(M?)错，故障字S应该为9。验证
如下。
对M'生成新的校验位P'为
P1=M{④M2④M④M;+M'=0+1+1+1+1=0
P=M{④M'+M'④M^+M;=0+0+1+1+1=1
P’=MM+M=1+0+1=0
P'=M;④M+M'=1④1+1=1
因此，故障字 S为
S?=P'④P”=01=1
第7章
229
S?=P2+P"=1+1=0


<!-- page: 247 -->

计算机组成与系统结构(第3版)
230
S?=P'+P"=0④0=0
S?=P'④P”=1+0=1
根据故障字的值1001,可以判断出发生错误的位是在11位码字的第1001位(即第9位),
在这一位上排列的是数据位M?,所以验证正确。纠错时，只要将码字的第9位(即第5个数
据位)取反即可。
(3)当M'=1101010,P”=1011时，说明数据M无错，校验位P?错，故障位S应为8。
验证如下。
因为M'=M,所以P'=P,故障位S为
S?=P{④P”=1④1=0
S?=P/④P"=1④1=0
S?=P'+P"=0+0=0
S=P'+P"=0+1=1
根据故障字的值1000,可以判断出发生错误的位是在11位码字的第1000位(即第8位),
在这一位上排列的是校验位P,所以验证正确。这种情况下无须纠错。
从上述数据位数n=8、校验位数k=4的分组情况来看，如果两个数据有一位不同，那
么由于该位至少要参与两组校验位的生成，因而至少会引起两个校验位的不同，再加上数据
位本身一位的不同，所以其码距d=3。根据码距与检错、纠错能力的关系可知，这种码制只
能对单个位出错情况进行定位和纠错，因此被称为单纠错码(SEC)。
若校验码同时具有发现两位错和纠正一位错的能力，则称为单纠错和双检错码(SEC-
DED),简称“纠一检二”码。若要使上述介绍的单纠错码成为SEC-DED码，则码距需扩大
到d=4。为此，还需要增加一位校验位P;,可将 P。排列在码字的最前面，加入P;后的排
列顺序为
P?M?M?M?M?P?M?M?M?P?M?P?P
此外，还必须使得数据中的每一位都参与至少3个校验位的生成，从表7.1中可看出，除了
M?和M?参与了3个校验位的生成外，其余位都只参与了两个校验位的生成，因此可将这
些位加入到P?所在的组中，得到以下公式：
P?=M?④M?④M?④M?④M。④M。
这样，当任意一个数据位发生错误时，必将引起3个校验位发生变化，所以码距为4。
引入P;后，故障字S也增加了一位，即S=SsS?S?S?S?,按照类似的方法可以求出故
障字S中各位的值，根据S?S?S?S?S?的取值情况，即可按照相应规则发现两位错并纠正
一位错。
早期的固态硬盘(SSD)采用海明码进行检错和纠错。对SSD进行海明码校验时，通常
会将一页分成两组数据，各自进行检错和纠错。例如，对于页大小为512B的页，将被分成
两个 256B的数据组。每组数据都是256行×8列的矩阵，分别对矩阵中的行R。～Rz和列
C?～C,计算出16位行校验位RP。～RP?s和6位列校验位CP。～CPs。
6位列校验位CPa～CP;分成3组(组号i=0,1,2),第i组的两个列校验位为CP～
CP+对于第i组，将C?～C;列按每隔2'列划分成8/2'路，偶数路中的所有数据按位
异或生成校验位CPz,奇数路中的所有数据按位异或生成校验位CPz+。例如，当i=1
时，对应的列校验位为CP,和CP?,按每隔2'列对C。～C,列进行划分，可划分成8/2=4


<!-- page: 248 -->

存储器层次结构
路，第0路为C。和C?、第1路为C?和C、第2路为C?和C、第3路为C。和C;,将第0路
和第2路中所有列的每一位数字按位异或即可生成CP?,将第1路和第3路中所有列的每
一位数字按位异或即可生成CP?。
16位行校验位RP。～RP;分成8组(组号i=0～7),与列校验位类似，每组两个行校
验位为RP?～RP。对于第i组，将行R。～R按每隔2'行划分成256/2'路，偶数路中
的所有数据按位异或生成校验位RPz,奇数路中的所有数据按位异或生成校验位RPz+。
16个行校验位占两字节，6个列校验位再加两位1构成一字节，由3字节组成 ECC 信
息。SSD的页中除了包含512B或4KiB大小的数据区外，还有一个OOB(out-of-band)区，
用于记录ECC信息等元数据。以K9F1208 SSD为例，每页包含512字节的数据区和16字
节的 OOB区。写某页时，会将该页数据对应的 ECC信息计算出来，并写入OOB区。在读
该页信息时，则重新计算该页数据对应的ECC信息，并和记录在OOB区中的原ECC信息
进行比较运算，根据运算结果进行数据检/纠错。
随着 NAND闪存制造工艺的不断发展，要求控制芯片的纠错能力越来越高。因为海明
码只能纠正1位错或检测2位错，因此，采用纠错能力不强的海明码进行检错和纠错，已不
能满足要求，需要采用纠错能力更高的BCH码，甚至开始由BCH码向低密度奇偶校验码
LDPC 过渡来增加使用寿命。关于BCH码和 LDPC码的概念请参考有关资料。
*7.4.4循环冗余校验码
循环冗余校验码(cyclic redundancy check)简称 CRC码，是一种具有较强检错、纠错能
力的校验码，常用于外存储器的数据校验，在计算机通信中也被广泛采用。在数据传输中，
奇偶校验码是在每个字符信息后增加一位奇偶校验位来进行数据校验的，这样对大批量传
输的数据进行校验时，会增加大量的额外开销，尤其是在网络通信中，传输的数据信息都是
二进制比特流，因而没有必要将数据再分解成一个个字符，这样也就无法采用奇偶校验码，
因此，通常采用CRC码进行校验。
前面所介绍的奇偶校验码和海明校验码都是以奇偶检测为手段的，而循环冗余校验码
则是通过某种数学运算来建立数据和校验位之间的约定关系。因为CRC码的编码原理复
杂，本书仅对其编码方式和实现过程作简单介绍，而不详细进行数学推导。
1.CRC码的检错方法
假设要进行校验的数据信息M(x)为一个n位的二进制数据，将M(x)左移k位后，用
一个约定的生成多项式G(x)与之相除，G(x)是一个k+1位的二进制数，相除后得到的k
位余数就是校验位。这些校验位拼接到M(x)的n位数据后面，形成一个n+k位的代码，
称这个代码为循环冗余校验码(CRC码),也称(n+k,n)码，如图7.22所示。一个 CRC码
一定能被生成多项式整除，所以当数据和校验位一起送到接收端后，只要将接收到的数据和
校验位用同样的生成多项式相除，如果正好除尽，表明没有发生错误；若除不尽，则表明某些
数据位发生了错误。
2.校验位的生成
下面用一个例子来说明校验位的生成过程。假设要传送的数据信息为100011,数据信
息位数n=6,对应报文多项式为M(x)=x?+x+1。若约定的生成多项式为G(x)=x3+
1,即生成多项式位数为4位，则校验位位数k=3。生成校验位时，用x3M(x)去除以
第7章
231


<!-- page: 249 -->

计算机组成与系统结构(第3版)
232
数据(n位)-
校验位(k位)—
-CRC码(n+k位)-
图7.22 CRC码的组成
G(x),相除时采用“模2运算”的多项式除法，不考虑加法进位和减法借位。进行模2除法
时，上商的原则是当部分余数首位是1时上商为1,反之上商为0。然后按模2相减原则求
得最高位后面几位的余数。这样当被除数逐步除完时，最后的余数位数比除数少一位。得
到的余数就是校验码，本例中最终的余数有3位。
图7.23说明了利用“模 2”多项式除法计算x3M(x)÷G(x)的过程。
x3M(x)÷G(x)=(x?+x?+x?)÷(x1+1)
1001
100111
100011000
1001
0011
0000
0111
0000
1110
1001
1001
100111
100011111
1001
0011
0000
0111
0000
1111
1001
1001
101110
101011111
1001
0111
0000
1111
1001
1101
1001
1110
1001
1110
1001
111
1101
1001
1001
1001
000
1001
1001
0001
0000
001
(a)计算校验位
(b)余数为0,数据正确
图7.23 CRC的校验位计算及验证
(c)余数不为0.数据不正确
图7.23(a)计算出的校验位为111,CRC码为100011 111。如果要检查CRC码，可将
CRC码用同一个多项式相除，若余数为0,则说明无错；若余数不为0,则说明有错。例如，
若接收方的CRC码与发送方一致，即同为100011111时，用同一个多项式相除后余数为0,
如图7.23(b)所示；若接收方的CRC码有一位出错而变为101011111时，用同一个多项式
相除后余数不为0,如图7.23(c)所示。
3.CRC码的纠错
当接收方将收到的CRC码用约定的生成多项式G(x)去除，发现余数不为0时，需要
判断出错的位置。不同的出错位置其余数不同，而且对于不同的码字，在有确定的码制与生
成多项式情况下，只要出错位置相同，则余数一定相同。例如，表7.2给出了(7,4)循环码
中两种不同的码字，其中加粗的是出错位。可以看出其出错位置与余数的关系是相同的。
如果CRC码中有一位出错，用特定的G(x)进行模2除，则会得到一个不为0的余数。若对
余数补 0后继续除下去，则会出现一个有趣的现象：各次余数将会按照一个特定的顺序循


<!-- page: 250 -->

存储器层次结构
环。如在表7.2所示的例子中，若将第7位出错时对应的余数001后面补0,继续再除一次，
则会得到新余数010,在010后补0,继续再除一次，则会得到下一个余数100,如此继续下
去，依次得到011,110,111,⋯,反复循环。这是被称为“循环”冗余码的原因。
表 7.2 码字、余数和出错位的关系
码 字 举 例
D?D?D?D?P?P?P? D?D?D?D?P?P?P?
余 数
出错位
正确
1
1
0
1
1
1
0
1
1
0
0
000
无
错误
1
1
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
001
010
100
011
110
111
101
7
6
5
4
3
2
1
在网络通信中，通常数据位数n相当大，由几千个二进位构成一帧数据，因此，通常使
用CRC码来检测错误，发现错误则告知发送方要求重发，不用CRC来纠正错误。因此，只
要在接收方用约定的生成多项式进行模2除后，判断余数是否为0就行了。
7.5高速缓冲存储器
通过提高存储芯片本身的速度或采用多模块存储器结构可以缓解CPU和主存之间的
速度匹配问题。除了这两种方法以外，在CPU和主存之间设置高速缓存(cache)也可以提
高 CPU访问指令和数据的速度。
7.5.1程序访问的局部性
对大量典型程序运行情况分析的结果表明，在较短的时间间隔内，程序产生的地址往往
集中在存储器的一个很小的范围，这种现象称为程序访问的局部性，包括时间局部性和空间
局部性。时间局部性是指被访问的某个存储单元在一个较短的时间间隔内很可能又被访
问；空间局部性是指被访问的某个存储单元的邻近单元在一个较短的时间间隔内很可能也
被访问。
出现程序访问的局部性特征的原因不难理解。因为程序是由指令和数据组成的。指令
在主存中按顺序存放，其地址连续，循环程序段或子程序段通常被重复执行，因此，指令的访
问具有明显的局部化特性；而数据在主存中一般也是连续存放，特别是数组元素，常常被按
序重复访问，因此，数据也具有明显的访问局部化特征。
例如，以下是一个高级语言程序段：
sum=0;
第7章
233
for(i=0; i<n;i++)
sum+=a[i];


<!-- page: 251 -->

计算机组成与系统结构(第3版)
*v=sum;
234
对应的汇编程序段可由以下10条指令(10～19)组成：
I0
sum*-0
OxOFC
10
Il
ap*A
;A是数组的起始地址
0x100
Ⅱ
0x104
12
I2
i*-0
指令
0x108
13
13
if(i>=n)goto done
0x10C
14
;数组元素 a[i]的值
0x110
15
I4 loop:t*(ap)
0x114
16
sum*-sum+t;累加值在 sum中
I5
:
I6
ap*ap+4
;计算下一个数组元素的地址
17
i*i+1
0x400
a[0]
-A
I8
if(i<n)goto loop
0x404
a[1]
0x408
a[2]
I9 done:V*sum
;累加结果保存至地址V
数据
0x40C
a[3]
0x410
a[4]
上述描述中的sum、ap、i、n、t均为通用寄存器，A和
V为主存地址。假定每条指令占4字节，每个数组元素占
4字节，按字节编址，则指令和数组元素在主存中的存放
0x414
a[5]
:
0x7A4
-V
情况如图 7.24所示。
从图7.24可看出，在程序执行过程中，首先指令按
图7.24 指令和数组在主存中存放
10～13的顺序执行，然后，指令14～18 按顺序被循环执行
n次。只要n足够大，程序在一段时间内，就一直在该局部区域内执行。对于取指令来说，
程序对主存的访问过程为
0x0FC(10)→0x108(I3)→0×10C(I4)→0x11C(18)→0×120(I9)。
n次
上述程序对数组的访问在指令14中进行，数组下标每次加 4,按每次4字节连续访问主
存。因为数组在主存中连续存放，因此，该程序对数据的访问过程是：0x400→0x404→
0x408→0x40C→⋯→0x7A4。由此可见，在一段时间内，访问的数据也在局部的连续区
域内。
为了更好地利用程序访问的空间局部性，通常把当前访问单元以及邻近单元作为一个
主存块一起调入cache。这个主存块的大小以及程序对数组元素的访问顺序等都对程序的
性能有一定的影响。
例 7.2 假定数组元素按行优先方式存放在主存中，则以下两段伪代码程序段 A和 B
中，(1)对于数组a的访问，哪一个空间局部性更好?哪一个时间局部性更好?(2)变量
sum的空间局部性和时间局部性各如何?(3)对于指令访问来说，for 循环体的空间局部性
和时间局部性如何?
程序段A.
### 1 int sum-array-rows(int a[M][N])
### 2 (
### 3 int i,j,sum=0;
### 4 for(i=0;i<M;i++)
5
for(j=0;j<N;j++)
sum+=a[i][1]
6


<!-- page: 252 -->

存储器层次结构
### 7 return sum;
8
程序段 B:
Ox0FC
10
0x100
I
### 1 int sum-array-cols(int a[M][N])
2{
0x104
0x108
指令
for内/外循环「
0x10C
### 3 int 1,j,sum=0;
### 4 for(j=0;j<N;j++)
5
for(i=0; i<M;i++)
6
sum+=a[i][j];
### 7 return sum;
### 8 )
0x110
0x114
136
a[0][0]
0x400
A
0x404
a[0][1]
0x408
0x40C
a[0][2047]
教据
解：假定M、N都为2048,按字节编址，每个数组元素占
4字节，则指令和数据在主存中的存放情况如图7.25所示。
0x410
a[1][0]
0x414
a[1][1]
(1)对于数组a的访问，程序段 A和B的空间局部性相
差较大。
0x7A4
-V
程序 A对数组a的访问顺序为a[0][0],a[o][1],⋯,
a[0][2047];a[1][o],a[1][1],⋯,a[1][2047];⋯。由此可
见，访问顺序与存放顺序是一致的，故空间局部性好。
图 7.25 指令和二维数组在
主存中的存放情况
程序B对数组a的访问顺序为a[0][o],a[1][o],⋯,a[2047][o];a[o][1],a[1][1],⋯,
a[2047][1];⋯。由此可见，访问顺序与存放顺序不一致，每次访问都要跳过2048个数组元
素，即8192个单元，若主存与cache的交换单位小于8KB,则每次装入一个主存块到 cache
时，下个要访问的数组元素总不能被装入cache,因而没有空间局部性。
时间局部性在程序段 A和B中都较差，因为每个数组元素都只被访问一次。
(2)对于变量sum,在程序段 A和B中的访问局部性是一样的。空间局部性对单个变
量来说没有意义；而时间局部性在A和B中都较好，因为sum变量在A和B的每次循环中
都要被访问。不过，通常编译器都将其分配在寄存器中，循环执行时只要取寄存器的内容进
行运算，最后再把寄存器的内容写回到存储单元中。
(3)对于for 循环体，程序段 A和B中的访问局部性是一样的。因为循环体内指令按
序连续存放，所以空间局部性好；内循环体被连续重复执行2048×2048次，因此时间局部性
也好。
从上述分析可以看出，虽然程序段A和B的功能相同，但因为内、外两重循环的顺序不
同而导致两者对数组a访问的空间局部性相差较大，从而带来执行时间的不同。曾有人将
这两个程序(M=N=2048)放在2GHz Pentium4上执行以进行比较，其实际运行结果为：
程序段 A的执行只需要59393288个时钟周期，而程序段B则需要1277877876个时钟
周期。程序段 A比程序段B快了将近20.5 倍!
##### 7.5.2 cache 的基本工作原理
cache 是一种小容量高速缓冲存储器，由快速的SRAM组成，直接制作在CPU芯片内，
速度几乎与CPU一样快。在CPU和主存之间设置cache,把主存中被频繁访问的程序块
第7章
235


<!-- page: 253 -->

计算机组成与系统结构(第3版)
236
和数据块复制到 cache中。由于程序访问的局部性，大多数情况下，CPU能直接从 cache 中
取得指令和数据，而不必访问主存。
为便于 cache 和主存间交换信息，cache 和主存空间都被划分为相等的区域。主存中的
区域称为块(block),也称为主存块，它是 cache和主存之间的信息交换单位；cache中存放
一个主存块的区域称为行(line)或槽(slot)。
1.cache 的有效位
在系统启动或复位时，每个 cache行都为空，其中的信息无效，只有装入了主存块后信
息才有效。为了说明cache行中的信息是否有效，每个 cache行需要一个有效位(valid bit)。
有了有效位，就可通过将有效位清零来淘汰某cache行中的主存块，称为冲刷(flush),
装入一个新主存块时，再使有效位置1。
2.CPU 在 cache 中的访问过程
CPU执行程序过程中，需要从主存中取指令或读数据时，先检查 cache中有没有要访
问的信息，若有，就直接从cache中读取，而不用访问主存；若没有，再从主存中把当前访问
信息所在的一个主存块复制到cache中，因此，cache中的内容是主存中部分内容的副本。
图 7.26 给出了带 cache 的 CPU 执行一次访存操作的过程。
开始
CPU给出主存地址 AD
AD 所在块是否
在 cache 中?
是
否i
从 cache中取信息送CPU
从主存取出
AD单元所在块
在 cache中找到一
个对应的空闲行
将AD单元
内容送 CPU
将主存块复制到
cache 空闲行中
结束
cache缺失处理
图7.26 带 cache 的 CPU的访存操作过程
如图7.26所示，整个访存过程包括判断信息是否在 cache中，从 cache 中取信息或从主
存中取一个主存块到 cache等工作，当对应 cache 行已满而找不到空闲行时，还要选择将某
cache行中的信息替换到主存，以使新的主存块能够存放到该cache行中。这些工作要求在
一条指令执行过程中完成，因而只能由硬件来实现。因此，cache对程序员来说是透明的，
程序员编程时不用考虑信息存放在主存中还是在 cache中。
3. cache-主存层次的平均访问时间
如图7.26所示，在访存过程中，需要判断所访问信息是否在 cache中。若在 cache 中，


<!-- page: 254 -->

存储器层次结构
则称 cache命中(hit),命中的概率称为命中率p(hit rate),它等于命中次数与访问总次数之
比；若不在cache中，则为不命中(miss)①,其概率称为缺失率(miss rate),它等于不命中次
数与访问总次数之比。命中时，CPU在 cache中直接存取信息，所用的时间开销就是访问
cache的时间T,称为命中时间(hit time);缺失时，需要从主存读取一个主存块送 cache,同
时将所需信息送CPU,因此，所用时间开销为访问主存的时间T。和T.之和。通常把从主
存读入一个主存块到 cache的时间T。称为缺失损失(miss penalty)。
CPU 在 cache-主存层次的平均访问时间为
T,=p×T.+(1-p)×(Tm+T?)=T.+(1-p)×Tm
由于程序访问的局部性特点，cache的命中率可以达到很高，接近于1。因此，虽然Tm>T。,
但最终的平均访问时间仍可接近T
例7.3 假定处理器时钟周期为2ns,某程序有1000条指令组成，每条指令执行一次，
其中的4条指令在取指令时，没有在cache中找到，其余指令都能在cache中取到。在执行
指令过程中，该程序需要进行900次主存数据访问，其中，6次没有在 cache中找到。试问：
(1)执行该程序得到的 cache 命中率是多少?
(2)若cache中存取一个信息的时间为1个时钟周期，缺失损失为4个时钟周期，则
CPU 在 cache-主存层次的平均访问时间为多少?
解：(1)执行该程序时的总访问次数为1000+900=1900,未命中次数为4+6=10,故
cache命中率为(1900-10)/1900≈99.47??
(2)cache-主存层次的平均访问时间为1+(1-99.47?4=1.02个时钟周期，即
1.02×2ns=2.04ns,与cache的访问时间相近。