第四节 高速存储器
1,双端口存储器由于 CPU和主存储器在速度上不匹配，而且在一个
CPU周期中可能需要用几个存储器字，这便限制了高速计算,
①,双端口存储器的逻辑结构双端口存储器是指同一个存储器具有两组相互独立的读写控制线路,是一种高速工作的存储器。
它提供了两个相互独立的端口，即左端口右端口。它们分别具有各自的地址线、数据线和控制线，可以对存储器中任何位置上的数据进行独立的存取操作。
②,无冲突读写控制当两个端口的地址不相同时，在两个端口上进行读写操作，
一定不会发生冲突。当任一端口被选中驱动时，就可对整个存储器进行存取，每一个端口都有自己的片选控制和输出驱动控制。
③,有冲突的读写控制当两个端口同时存取存储器同一存储单元时，便发生读写冲突。
为解决此问题，特设置了 BUSY标志。由片上的判断逻辑决定对哪个端口优先进行读写操作，而暂时关闭另一个被延迟的端口。
2,多模块交叉存储器
1).
一个由若干个模块组成的主存储器是 线性编址 的 。
这些地址在各模块有两种安排方式：
一种是 顺序方式,一种是 交叉方式 。
顺序方式,某个模块进行存取时，其他模块不工作，
某一模块出现故障时，其他模块可以照常工作，通过增添模块来扩充存储器容量比较方便。但各模块串行工作，存储器的带宽受到了限制。
交叉方式,地址码的低位字段经过译码选择不同的模块,而高位字段指向相应模块内的存储字。连续地址分布在相邻的不同模块内，同一个模块内的地址都是不连续的。对连续字的成块传送可实现多模块流水式并行存取，大大提高存储器的带宽。
2).多模块交叉存储器的基本结构四模块交叉存储器结构框图演示每个模块各自以等同的方式与 CPU传送信息。 CPU
同时访问四个模块，由存储器控制部件控制它们分时使用数据总线进行信息传递。这是一种并行存储器结构。
3).二模块交叉存储器举例无等待状态成块存取示意图演示
4)相联存储器
（ 1） 在计算机系统中，相联存储器主要用于虚拟存储器中存放分段表、页表和快表；
（ 2）在高速缓冲存储器中，相联存储器作为存放
cache的行地址之用。这是因为，在这两种应用中，
都需要快速查找。
作用,
相联存储器的基本原理：
把存储单元所存内容的某一部分作为检索项 (即关键字项 )，去检索该存储器，并将存储器中与该检索项符合的存储单元内容进行读出或写入。
相联存储器的组成：
相联存储器由存储体、检索寄存器、屏蔽寄存器、符合寄存器、比较线路、代码寄存器、控制线路等组成。
第五节 校 验 码计算机系统工作过程中,由于脉冲噪声,串音,传输质量等原因,有时在信息的形成,存取,传送中会造成错误 。 为减少和避免这些错误,一方面要提高硬件的质量,另一方面可以采用抗干扰码,其基本思想是,
按一定的规律在有用信息的基础上再附加上一些冗余信息,使编码在简单线路的配合下能发现错误,确定错误位置甚至自动纠正错误 。
通常,一个 K位的信息码组应加上 r位的校验码组 (奇偶校验码的 r＝ 1),组成位抗干扰码字 (在通信系统中称为一帧 )。
抗干扰码可分为 检错码 和 纠错码 。
检错码是指能自动发现差错的码 。
纠错码是指不仅能发现差错而且能自动纠正差错的码 。
这两类码之间并没有明显的界限 。 纠错码也可用来检错,
而有的检错码可以用来纠错 。
抗干扰码的编码原则是在不增加硬件开销的情况下,用最小的校验码组,发现,纠正更多的错误 。
一般情况,校验码组越长,其发现,纠正错误的能力越强 。
1,奇偶校验码是一种最简单的检错码，分,
横向奇偶校验,纵向奇偶校验、横向纵向奇偶校验数字 0 1 2 3 4 5 6 7 8 9
校验码字
C1
C2
C3
C4
C5
C6
C7
0 l 0 1 0 l 0 1 0 1
0 0 1 l 0 0 1 1 0 0
0 0 0 0 l l 1 l 0 0
0 0 0 0 0 0 0 0 l 1
l 1 l l l l l l 1 l
1 1 1 1 1 1 1 1 l l
0 0 0 0 0 0 0 0 0 0
l
0
0
0
0
0
0
数字 0 l 2 3 4 5 6 7 8 9 横向校验码字
Cl
C2
C3
C4
C5
C6
C7
0 l 0 l 0 l 0 l 0 1
0 0 l l 0 0 1 1 0 0
0 0 0 0 1 1 l 1 0 0
0 0 0 0 0 0 0 0 1 l
1 1 1 l l l l 1 l 1
l 1 1 l 1 1 1 l l l
0 0 0 0 0 0 0 0 0 0
l
0
0
0
0
0
0
纵向校验 0 l l 0 l 0 0 1 1 0 l
这种码具有较强的检错能力,它能检查出的错误类型如下
(1)可检查出某行,某列的所有奇数个错误 。
(2)能发现大部分偶数个错误 。 如某个码字 (列向 )发生偶数个位的错误时,虽然不能由纵向奇偶校验码检查出来,
但却可以由横向奇偶校验检查出来 。
(3)能发现突发长度 ≤n-4-1(n为行数,即字符长度 )的突发错误
(4)可以纠正不能同时满足行,列校验关系的 I位错误 。 因为 1位错了,对应的行和列能够同时发现,从而能定出差错的位置 (即坐标 ),从而加以纠正 。
但是,这种码不能检查出某些互相补偿的偶数个错误,
因为它既不破坏横向奇偶校验关系,又不破坏纵向奇偶校验关系 。
2,存储器的校验在计算机运行过程中,由于种种原因致使数据在存储过程中可能出现差错 。 为了能及时发现错误并及时纠正错误,通常可将原数据配成海明编码 。
海明码是由 RichardHanming于 1950年提出的，它具有一位纠错能力。
编码纠错理论,① 任何一种编码是否具有检测能力和纠错能力,都与编码的最小距离有关 。
编码最小距离是指在一种编码系统中,任意两组合法代码之间的最少二进制位数的差异 。
编码纠错理论,② L -1=D+C 且 D≥C
即编码最小距离 L越大,则其检测错误的位数 D也越大,纠正错误的位 数 C也越大,且纠错能力恒小于或等于检错能力 。
例如：当编码最小距离 L=3时,
这种编码可视为最多能检错二位,
或能检错一位,纠错一位 。
可见,倘若能在信息编码中增加几位检测位,增大 L，
显然便能提高检错和纠错能力 。
海明码 就是根据这一理论提出的具有一位纠错能力的编码 。
③ 设欲检测的二进制代码为 n位,为使其具有纠错能力,需增添 k位检测位,组成 n十 k位的代码 。 为了能准确对错误定位以及指出代码没错,新增添的检测位数 k应满足：
编码纠错理论,
2 k≥n+k+1
由此关系可求得不同代码长度 n所需检测位的位数 k，如表
n k(最小 )
1 2
2— 4 3
5— 11 4
12— 26 5
27— 57 6
58— 120 7
k的位数确定后,便可由它们所承担的检测任务,设定它们在被传送代码中的位置及它们的取值 。
设 n+k位代码自左至右依次编为第 1,2,3,…… n十 k位,
而将 k位检测位记作 Ci,(i=1,2,4,8…… ),分别安插在
n十 k位代码编号的第 1,2,4,8…… 2k-1位上 。 这些检测位的位置设置,是为了保证它们能分别承担 n十 k位信息中,
不同数位所组成的,小组,的奇偶检查任务,使检测位和它所负责检测的小组中 1的个数为奇数或为偶数,
2 k≥n+k+1
C1 检测的 g1小组包含第 1,3,5,7,9,11…… 位其余检测位的小组所包含的位也可类推 。 这种小组的划分有如下特点
C2 检测的 g2小组包含第 2,3,6,7,10,11,14,15…… 位
C3 检测的 g3小组包含第 4,5,6,7,12,13,14,15…… 位如果按配偶原则来配置海明码，则
① 每个小组 gi 有一位且仅有一位为它所独占,这一位是其他小组所没有的,即 g i,组独占第 2 i-1位 (i=1,2,3,…… )
② 每两个小组 gi和 gj共同占有一位是其他小组没有的,即每两小组 gi和 gj共同占有第 2 i-1+2 j-1位 (i,J=l,2,…… )；
③ 每三个小组 gi,gj和 gl,共同占有第 2i-1+2J-1+2l-1位,是其他小组所没有的；依次类推,便可确定每组所包含的各位 。
例如,欲传递信息为 b4b3b2b1，
解,∵ (n=4),根据 2k≥n+k+1,可求出配置成海明码需增添检测位
∴ k=3，且它们位置的安排应如下：
二进制序号 1 2 3 4 5 6 7
名称 C1 C2 b4 C3 b3 b2 b1
如果按配偶原则来配置海明码,则
C1 =b4⊕ b3 ⊕ b1 应使 1,3,5,7位中的,1”的个数为偶数；
C2 =b4⊕ b2⊕ b1 应使 2,3,6,7位中的,1”的个数为偶数；
C3 = b3⊕ b2⊕ b1 应使 4,5,6,7位中的,1”的个数为偶数：
例如,欲传递信息为 b4b3b2b1=0101
C1 =b4⊕ b3 ⊕ b1= 0⊕ 1 ⊕ 1=0
C2 =b4⊕ b2⊕ b1=0⊕ 0⊕ 1=1
C3 =b3⊕ b2⊕ b1=1⊕ 0⊕ 1=0
故 0101的海明码应为：
C1 C2 b4 C4 b3 b2 bl，即 0100101。
求海明码
C1 应使 1,3,5,7位中的,1”的个数为偶数；
C2 应使 2,3,6,7位中的,1”的个数为偶数；
C3 应使 4,5,6,7位中的,1”的个数为偶数
2．海明码的纠错过程海明码的纠错过程，实际上是对传送后的海明码形成新的检测位 Pi(i=1,2,4,8……),
根据 Pi的状态，便可直接指出错误的位置。
Pi的状态是由原检测位 Ci及其所在小组内,1”的个数确定的倘若按配偶原则配置的海明码,
其传送后形成新的检测位 Pi应为 0,否则说明传送有错,
并且还可直接指出出错的位置 。
由于 Pi与 Ci有其对应关系,故 Pi可由下式确定：
P1=1⊕ 3 ⊕ 5 ⊕ 7 即 P1=C1 ⊕ b4 ⊕ b3 ⊕ bl
P2=2 ⊕ 3 ⊕ 6 ⊕ 7 即 P2=C2 ⊕ b4 ⊕ b2 ⊕ b1
P4=4 ⊕ 5 ⊕ 6 ⊕ 7 即 P4=C4 ⊕ b3 ⊕ b2 ⊕ b1
例,设已知传送的正确海明码 (按配偶原则配置 )为 0100101，
若传送后接收到的海明码为 0100111,查出错位则新的检测位为
P4=4⊕ 5 ⊕ 6 ⊕ 7,即 P4=0 ⊕ 1 ⊕ 1 ⊕ 1=1
P2=2 ⊕ 3 ⊕ 6 ⊕ 7,即 P2=1 ⊕ 0 ⊕ 1 ⊕ 1=1
P1=1 ⊕ 3 ⊕ 5 ⊕ 7,即 P1=0 ⊕ 0 ⊕ 1 ⊕ 1=0
有意思的是,P4,P2,P1所构成的二进制值恰恰是出错的位置,
海明码常常被用在纠错 一位 的场合,若欲实现检错两位,
实用时还得再增添一位检测位 。
即 P4P2P1=110，表示第六位出错。
发现错误后，计算机便自动地将错误的第六位,1”
纠正为,0”。
1,cache的功能
cache是介于 CPU和主存之间的小容量存储器，存取速度比主存快。它能高速地向 CPU提供指令和数据，
加快程序的执行速度。它是为了解决 CPU和主存之间速度不匹配而采用的一项重要技术。
第六节 cache
CPU与 cache之间的数据交换是以字为单位，而 cache与主存之间的数据交换是以块为单位。一个块由若干定长字组成的。当 CPU读取主存中一个字时，便发出此字的内存地址到 cache和主存。此时 cache控制逻辑依据地址判断此字当前是否在 cache中：若是，此字立即传送给 CPU；若非，则用主存读周期把此字从主存读出送到 CPU，与此同时，把含有这个字的整个数据块从主存读出送到 cache中。由始终管理 cache使用情况的硬件逻辑电路来实现 LRU替换算法
2,cache的基本原理
3.cache的命中率增加 cache的目的，就是在性能上使主存的平均读出时间尽可能接近 cache的读出时间。
因此,cache的命中率应接近于 1。
由于程序访问的局部性,这是可能的 。
在一个程序执行期间，设 Nc表示 cache完成存取的总次数，
Nm表示主存完成存取的总次数,h定义为命中率，则有若 tc表示命中时的 cache访问时间,tm表示未命中时的主存访问时间,1-h表示未命中率，则 cache/主存系统的平均访问时间 ta为,t
a=htc+(1-h)tm
设 r=tm/tc表示主存慢于 cache的倍率,e表示访问效率，则有,
为提高访问效率，命中率 h越接近 1越好,r值以 5— 10
为宜，不宜太大。命中率 h与程序的行为,cache的容量、组织方式、块的大小有关。
【 例 5】 CPU执行一段程序时,cache完成存取的次数为
1900次，主存完成存取的次数为 100次，已知 cache存取周期为 50ns，主存存取周期为 250ns，求 cache/主存系统的效率和平均访问时间。
【 解 】
h=Nc/(Nc+Nm)=1900/(1900+100)=0.95
r=tm/tc=250ns/50ns=5
e=1/(r+(1-r)h)=1/(5+(1-5)× 0.95)=83.3%
ta=tc/e=50ns/0.833=60ns
4,主存与 cache的地址映射
cache的容量很小，它保存的内容只是主存内容的一个子集，且 cache与主存的数据交换是以块为单位。
地址映射 即是应用某种方法把主存地址定位到 cache
中 。
地址映射方式有 全相联方式,直接方式 和 组相联方式 三种
① 全相联映射方式它的主要 缺点 是比较器电路难于设计和实现,因此只适合于小容量 cache采用。
② 直接映射方式缺点：是每个主存块只有一个固定的行位置可存放,容易产生冲突。因此适合大容量 cache采用。
多对一的映射
cache的行号 i和主存的块号 j有如下函数关系：
I = j mod m （ m为 cache中的总行数）
一个主存块只能拷贝到 cache的一个特定行位置上去 。
③ 组相联映射方式 前两种方式的折衷方案。
它将 cache分成 u组，每组 v行，主存块存放到哪个组是固定的，至于存到该组哪 一行是灵活的，
即有如下函数关系：
m＝ u× v 组号 q＝ j mod u
组相联映射方式中的每组行数 v一般取值较小，
这种规模的 v路比较器容易设计和实现。而块在组中的排放又有一定的灵活性,冲突减少。
5,替换策略
cache工作原理要求它尽量保存最新数据，必然要产生替换。
对直接映射的 cache来说，只要把此特定位置上的原主存块换出 cache即可。
对全相联和组相联 cache来说,就要从允许存放新主存块的若干特定行中选取一行换出。
★ 最不经常使用 (LFU)算法
LFU算法将一段时间内被访问次数最少的那行数据换出。
每行设置一个计数器。从 0开始计数，每访问一次,被访行的计数器增 1。
当需要替换时，将计数值最小的行换出，同时将这些行的计数器都清零。
这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，不能严格反映近期访问情况。
★ 近期最少使用 (LRU)算法
LRU算法将近期内长久未被访问过的行换出。
每行也设置一个计数器,cache每命中一次，命中行计数器清零，其它各行计数器增 1。
当需要替换时，将计数值最大的行换出。
这种算法保护了刚拷贝到 cache中的新数据行，有较高的命中率。
★ 随机替换随机替换策略从特定的行位置中随机地选取一行换出。
在硬件上容易实现，且速度也比前两种策略快。
缺点是降低了命中率和 cache工作效率。
6,cache的写操作策略
CPU对 cache的写入更改了 cache的内容。可选用写操作策略使 cache内容和主存内容保持一致。
★ 写回法当 CPU写 cache命中时，只修改 cache的内容，而不立即写入主存；只有当此行被换出时才写回主存。
这种方法减少了访问主存的次数,但是存在不一致性的隐患。
实现这种方法时，每个 cache行必须配置一个修改位，以反映此行是否被 CPU修改过。
★ 全写法当写 cache命中时,cache与主存同时发生写修改，因而较好地维护了 cache与主存的内容的一致性。
当写 cache未命中时，直接向主存进行写入。
cache中每行无需设置一个修改位以及相应的判断逻辑。
缺点是降低了 cache的功效。
★ 写一次法基于写回法并结合全写法的写策略,写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。这便于维护系统全部 cache的一致性。
7,奔腾 PC机的 cache
奔腾 PC机采用两级 cache结构。
安装在主板上的 2级 cache(L2)采用 2路 组相联映射 方式，集成在 CPU内的 1级 cache(L1)也采用 2路 组相联映射 方式,L1
又是 L2的子集,从而使 L1未命中处理时间大大缩短。
CPU中的 L1分设成各 8KB的指令 cache和数据 cache,有利于 CPU高速执行程序。
数据 cache采用 2路组相联结构，采用 LRU替换算法，
1,双端口存储器由于 CPU和主存储器在速度上不匹配，而且在一个
CPU周期中可能需要用几个存储器字，这便限制了高速计算,
①,双端口存储器的逻辑结构双端口存储器是指同一个存储器具有两组相互独立的读写控制线路,是一种高速工作的存储器。
它提供了两个相互独立的端口，即左端口右端口。它们分别具有各自的地址线、数据线和控制线，可以对存储器中任何位置上的数据进行独立的存取操作。
②,无冲突读写控制当两个端口的地址不相同时，在两个端口上进行读写操作，
一定不会发生冲突。当任一端口被选中驱动时，就可对整个存储器进行存取，每一个端口都有自己的片选控制和输出驱动控制。
③,有冲突的读写控制当两个端口同时存取存储器同一存储单元时，便发生读写冲突。
为解决此问题，特设置了 BUSY标志。由片上的判断逻辑决定对哪个端口优先进行读写操作，而暂时关闭另一个被延迟的端口。
2,多模块交叉存储器
1).
一个由若干个模块组成的主存储器是 线性编址 的 。
这些地址在各模块有两种安排方式：
一种是 顺序方式,一种是 交叉方式 。
顺序方式,某个模块进行存取时，其他模块不工作，
某一模块出现故障时，其他模块可以照常工作，通过增添模块来扩充存储器容量比较方便。但各模块串行工作，存储器的带宽受到了限制。
交叉方式,地址码的低位字段经过译码选择不同的模块,而高位字段指向相应模块内的存储字。连续地址分布在相邻的不同模块内，同一个模块内的地址都是不连续的。对连续字的成块传送可实现多模块流水式并行存取，大大提高存储器的带宽。
2).多模块交叉存储器的基本结构四模块交叉存储器结构框图演示每个模块各自以等同的方式与 CPU传送信息。 CPU
同时访问四个模块，由存储器控制部件控制它们分时使用数据总线进行信息传递。这是一种并行存储器结构。
3).二模块交叉存储器举例无等待状态成块存取示意图演示
4)相联存储器
（ 1） 在计算机系统中，相联存储器主要用于虚拟存储器中存放分段表、页表和快表；
（ 2）在高速缓冲存储器中，相联存储器作为存放
cache的行地址之用。这是因为，在这两种应用中，
都需要快速查找。
作用,
相联存储器的基本原理：
把存储单元所存内容的某一部分作为检索项 (即关键字项 )，去检索该存储器，并将存储器中与该检索项符合的存储单元内容进行读出或写入。
相联存储器的组成：
相联存储器由存储体、检索寄存器、屏蔽寄存器、符合寄存器、比较线路、代码寄存器、控制线路等组成。
第五节 校 验 码计算机系统工作过程中,由于脉冲噪声,串音,传输质量等原因,有时在信息的形成,存取,传送中会造成错误 。 为减少和避免这些错误,一方面要提高硬件的质量,另一方面可以采用抗干扰码,其基本思想是,
按一定的规律在有用信息的基础上再附加上一些冗余信息,使编码在简单线路的配合下能发现错误,确定错误位置甚至自动纠正错误 。
通常,一个 K位的信息码组应加上 r位的校验码组 (奇偶校验码的 r＝ 1),组成位抗干扰码字 (在通信系统中称为一帧 )。
抗干扰码可分为 检错码 和 纠错码 。
检错码是指能自动发现差错的码 。
纠错码是指不仅能发现差错而且能自动纠正差错的码 。
这两类码之间并没有明显的界限 。 纠错码也可用来检错,
而有的检错码可以用来纠错 。
抗干扰码的编码原则是在不增加硬件开销的情况下,用最小的校验码组,发现,纠正更多的错误 。
一般情况,校验码组越长,其发现,纠正错误的能力越强 。
1,奇偶校验码是一种最简单的检错码，分,
横向奇偶校验,纵向奇偶校验、横向纵向奇偶校验数字 0 1 2 3 4 5 6 7 8 9
校验码字
C1
C2
C3
C4
C5
C6
C7
0 l 0 1 0 l 0 1 0 1
0 0 1 l 0 0 1 1 0 0
0 0 0 0 l l 1 l 0 0
0 0 0 0 0 0 0 0 l 1
l 1 l l l l l l 1 l
1 1 1 1 1 1 1 1 l l
0 0 0 0 0 0 0 0 0 0
l
0
0
0
0
0
0
数字 0 l 2 3 4 5 6 7 8 9 横向校验码字
Cl
C2
C3
C4
C5
C6
C7
0 l 0 l 0 l 0 l 0 1
0 0 l l 0 0 1 1 0 0
0 0 0 0 1 1 l 1 0 0
0 0 0 0 0 0 0 0 1 l
1 1 1 l l l l 1 l 1
l 1 1 l 1 1 1 l l l
0 0 0 0 0 0 0 0 0 0
l
0
0
0
0
0
0
纵向校验 0 l l 0 l 0 0 1 1 0 l
这种码具有较强的检错能力,它能检查出的错误类型如下
(1)可检查出某行,某列的所有奇数个错误 。
(2)能发现大部分偶数个错误 。 如某个码字 (列向 )发生偶数个位的错误时,虽然不能由纵向奇偶校验码检查出来,
但却可以由横向奇偶校验检查出来 。
(3)能发现突发长度 ≤n-4-1(n为行数,即字符长度 )的突发错误
(4)可以纠正不能同时满足行,列校验关系的 I位错误 。 因为 1位错了,对应的行和列能够同时发现,从而能定出差错的位置 (即坐标 ),从而加以纠正 。
但是,这种码不能检查出某些互相补偿的偶数个错误,
因为它既不破坏横向奇偶校验关系,又不破坏纵向奇偶校验关系 。
2,存储器的校验在计算机运行过程中,由于种种原因致使数据在存储过程中可能出现差错 。 为了能及时发现错误并及时纠正错误,通常可将原数据配成海明编码 。
海明码是由 RichardHanming于 1950年提出的，它具有一位纠错能力。
编码纠错理论,① 任何一种编码是否具有检测能力和纠错能力,都与编码的最小距离有关 。
编码最小距离是指在一种编码系统中,任意两组合法代码之间的最少二进制位数的差异 。
编码纠错理论,② L -1=D+C 且 D≥C
即编码最小距离 L越大,则其检测错误的位数 D也越大,纠正错误的位 数 C也越大,且纠错能力恒小于或等于检错能力 。
例如：当编码最小距离 L=3时,
这种编码可视为最多能检错二位,
或能检错一位,纠错一位 。
可见,倘若能在信息编码中增加几位检测位,增大 L，
显然便能提高检错和纠错能力 。
海明码 就是根据这一理论提出的具有一位纠错能力的编码 。
③ 设欲检测的二进制代码为 n位,为使其具有纠错能力,需增添 k位检测位,组成 n十 k位的代码 。 为了能准确对错误定位以及指出代码没错,新增添的检测位数 k应满足：
编码纠错理论,
2 k≥n+k+1
由此关系可求得不同代码长度 n所需检测位的位数 k，如表
n k(最小 )
1 2
2— 4 3
5— 11 4
12— 26 5
27— 57 6
58— 120 7
k的位数确定后,便可由它们所承担的检测任务,设定它们在被传送代码中的位置及它们的取值 。
设 n+k位代码自左至右依次编为第 1,2,3,…… n十 k位,
而将 k位检测位记作 Ci,(i=1,2,4,8…… ),分别安插在
n十 k位代码编号的第 1,2,4,8…… 2k-1位上 。 这些检测位的位置设置,是为了保证它们能分别承担 n十 k位信息中,
不同数位所组成的,小组,的奇偶检查任务,使检测位和它所负责检测的小组中 1的个数为奇数或为偶数,
2 k≥n+k+1
C1 检测的 g1小组包含第 1,3,5,7,9,11…… 位其余检测位的小组所包含的位也可类推 。 这种小组的划分有如下特点
C2 检测的 g2小组包含第 2,3,6,7,10,11,14,15…… 位
C3 检测的 g3小组包含第 4,5,6,7,12,13,14,15…… 位如果按配偶原则来配置海明码，则
① 每个小组 gi 有一位且仅有一位为它所独占,这一位是其他小组所没有的,即 g i,组独占第 2 i-1位 (i=1,2,3,…… )
② 每两个小组 gi和 gj共同占有一位是其他小组没有的,即每两小组 gi和 gj共同占有第 2 i-1+2 j-1位 (i,J=l,2,…… )；
③ 每三个小组 gi,gj和 gl,共同占有第 2i-1+2J-1+2l-1位,是其他小组所没有的；依次类推,便可确定每组所包含的各位 。
例如,欲传递信息为 b4b3b2b1，
解,∵ (n=4),根据 2k≥n+k+1,可求出配置成海明码需增添检测位
∴ k=3，且它们位置的安排应如下：
二进制序号 1 2 3 4 5 6 7
名称 C1 C2 b4 C3 b3 b2 b1
如果按配偶原则来配置海明码,则
C1 =b4⊕ b3 ⊕ b1 应使 1,3,5,7位中的,1”的个数为偶数；
C2 =b4⊕ b2⊕ b1 应使 2,3,6,7位中的,1”的个数为偶数；
C3 = b3⊕ b2⊕ b1 应使 4,5,6,7位中的,1”的个数为偶数：
例如,欲传递信息为 b4b3b2b1=0101
C1 =b4⊕ b3 ⊕ b1= 0⊕ 1 ⊕ 1=0
C2 =b4⊕ b2⊕ b1=0⊕ 0⊕ 1=1
C3 =b3⊕ b2⊕ b1=1⊕ 0⊕ 1=0
故 0101的海明码应为：
C1 C2 b4 C4 b3 b2 bl，即 0100101。
求海明码
C1 应使 1,3,5,7位中的,1”的个数为偶数；
C2 应使 2,3,6,7位中的,1”的个数为偶数；
C3 应使 4,5,6,7位中的,1”的个数为偶数
2．海明码的纠错过程海明码的纠错过程，实际上是对传送后的海明码形成新的检测位 Pi(i=1,2,4,8……),
根据 Pi的状态，便可直接指出错误的位置。
Pi的状态是由原检测位 Ci及其所在小组内,1”的个数确定的倘若按配偶原则配置的海明码,
其传送后形成新的检测位 Pi应为 0,否则说明传送有错,
并且还可直接指出出错的位置 。
由于 Pi与 Ci有其对应关系,故 Pi可由下式确定：
P1=1⊕ 3 ⊕ 5 ⊕ 7 即 P1=C1 ⊕ b4 ⊕ b3 ⊕ bl
P2=2 ⊕ 3 ⊕ 6 ⊕ 7 即 P2=C2 ⊕ b4 ⊕ b2 ⊕ b1
P4=4 ⊕ 5 ⊕ 6 ⊕ 7 即 P4=C4 ⊕ b3 ⊕ b2 ⊕ b1
例,设已知传送的正确海明码 (按配偶原则配置 )为 0100101，
若传送后接收到的海明码为 0100111,查出错位则新的检测位为
P4=4⊕ 5 ⊕ 6 ⊕ 7,即 P4=0 ⊕ 1 ⊕ 1 ⊕ 1=1
P2=2 ⊕ 3 ⊕ 6 ⊕ 7,即 P2=1 ⊕ 0 ⊕ 1 ⊕ 1=1
P1=1 ⊕ 3 ⊕ 5 ⊕ 7,即 P1=0 ⊕ 0 ⊕ 1 ⊕ 1=0
有意思的是,P4,P2,P1所构成的二进制值恰恰是出错的位置,
海明码常常被用在纠错 一位 的场合,若欲实现检错两位,
实用时还得再增添一位检测位 。
即 P4P2P1=110，表示第六位出错。
发现错误后，计算机便自动地将错误的第六位,1”
纠正为,0”。
1,cache的功能
cache是介于 CPU和主存之间的小容量存储器，存取速度比主存快。它能高速地向 CPU提供指令和数据，
加快程序的执行速度。它是为了解决 CPU和主存之间速度不匹配而采用的一项重要技术。
第六节 cache
CPU与 cache之间的数据交换是以字为单位，而 cache与主存之间的数据交换是以块为单位。一个块由若干定长字组成的。当 CPU读取主存中一个字时，便发出此字的内存地址到 cache和主存。此时 cache控制逻辑依据地址判断此字当前是否在 cache中：若是，此字立即传送给 CPU；若非，则用主存读周期把此字从主存读出送到 CPU，与此同时，把含有这个字的整个数据块从主存读出送到 cache中。由始终管理 cache使用情况的硬件逻辑电路来实现 LRU替换算法
2,cache的基本原理
3.cache的命中率增加 cache的目的，就是在性能上使主存的平均读出时间尽可能接近 cache的读出时间。
因此,cache的命中率应接近于 1。
由于程序访问的局部性,这是可能的 。
在一个程序执行期间，设 Nc表示 cache完成存取的总次数，
Nm表示主存完成存取的总次数,h定义为命中率，则有若 tc表示命中时的 cache访问时间,tm表示未命中时的主存访问时间,1-h表示未命中率，则 cache/主存系统的平均访问时间 ta为,t
a=htc+(1-h)tm
设 r=tm/tc表示主存慢于 cache的倍率,e表示访问效率，则有,
为提高访问效率，命中率 h越接近 1越好,r值以 5— 10
为宜，不宜太大。命中率 h与程序的行为,cache的容量、组织方式、块的大小有关。
【 例 5】 CPU执行一段程序时,cache完成存取的次数为
1900次，主存完成存取的次数为 100次，已知 cache存取周期为 50ns，主存存取周期为 250ns，求 cache/主存系统的效率和平均访问时间。
【 解 】
h=Nc/(Nc+Nm)=1900/(1900+100)=0.95
r=tm/tc=250ns/50ns=5
e=1/(r+(1-r)h)=1/(5+(1-5)× 0.95)=83.3%
ta=tc/e=50ns/0.833=60ns
4,主存与 cache的地址映射
cache的容量很小，它保存的内容只是主存内容的一个子集，且 cache与主存的数据交换是以块为单位。
地址映射 即是应用某种方法把主存地址定位到 cache
中 。
地址映射方式有 全相联方式,直接方式 和 组相联方式 三种
① 全相联映射方式它的主要 缺点 是比较器电路难于设计和实现,因此只适合于小容量 cache采用。
② 直接映射方式缺点：是每个主存块只有一个固定的行位置可存放,容易产生冲突。因此适合大容量 cache采用。
多对一的映射
cache的行号 i和主存的块号 j有如下函数关系：
I = j mod m （ m为 cache中的总行数）
一个主存块只能拷贝到 cache的一个特定行位置上去 。
③ 组相联映射方式 前两种方式的折衷方案。
它将 cache分成 u组，每组 v行，主存块存放到哪个组是固定的，至于存到该组哪 一行是灵活的，
即有如下函数关系：
m＝ u× v 组号 q＝ j mod u
组相联映射方式中的每组行数 v一般取值较小，
这种规模的 v路比较器容易设计和实现。而块在组中的排放又有一定的灵活性,冲突减少。
5,替换策略
cache工作原理要求它尽量保存最新数据，必然要产生替换。
对直接映射的 cache来说，只要把此特定位置上的原主存块换出 cache即可。
对全相联和组相联 cache来说,就要从允许存放新主存块的若干特定行中选取一行换出。
★ 最不经常使用 (LFU)算法
LFU算法将一段时间内被访问次数最少的那行数据换出。
每行设置一个计数器。从 0开始计数，每访问一次,被访行的计数器增 1。
当需要替换时，将计数值最小的行换出，同时将这些行的计数器都清零。
这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，不能严格反映近期访问情况。
★ 近期最少使用 (LRU)算法
LRU算法将近期内长久未被访问过的行换出。
每行也设置一个计数器,cache每命中一次，命中行计数器清零，其它各行计数器增 1。
当需要替换时，将计数值最大的行换出。
这种算法保护了刚拷贝到 cache中的新数据行，有较高的命中率。
★ 随机替换随机替换策略从特定的行位置中随机地选取一行换出。
在硬件上容易实现，且速度也比前两种策略快。
缺点是降低了命中率和 cache工作效率。
6,cache的写操作策略
CPU对 cache的写入更改了 cache的内容。可选用写操作策略使 cache内容和主存内容保持一致。
★ 写回法当 CPU写 cache命中时，只修改 cache的内容，而不立即写入主存；只有当此行被换出时才写回主存。
这种方法减少了访问主存的次数,但是存在不一致性的隐患。
实现这种方法时，每个 cache行必须配置一个修改位，以反映此行是否被 CPU修改过。
★ 全写法当写 cache命中时,cache与主存同时发生写修改，因而较好地维护了 cache与主存的内容的一致性。
当写 cache未命中时，直接向主存进行写入。
cache中每行无需设置一个修改位以及相应的判断逻辑。
缺点是降低了 cache的功效。
★ 写一次法基于写回法并结合全写法的写策略,写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。这便于维护系统全部 cache的一致性。
7,奔腾 PC机的 cache
奔腾 PC机采用两级 cache结构。
安装在主板上的 2级 cache(L2)采用 2路 组相联映射 方式，集成在 CPU内的 1级 cache(L1)也采用 2路 组相联映射 方式,L1
又是 L2的子集,从而使 L1未命中处理时间大大缩短。
CPU中的 L1分设成各 8KB的指令 cache和数据 cache,有利于 CPU高速执行程序。
数据 cache采用 2路组相联结构，采用 LRU替换算法，
