计算机体系结构

计算机体系结构

什么是存储系统？对于一个由两个存储器M1和M2构成的存储系统，设M1的命中率为h，两个存储系统的存储容量分别为s1和s2，访问速度分别为t1和t2，每千字节的价格分别为c1和c2。

在什么条件下，整个存储系统的每千字节的平均价格会接近于c2？ 写出这个存储系统的等效访问时间ta的表达式。

假设存储系统的访问效率e=t1/ta，两个存储系统的速度比r=t2/t1。试以速度比r和命中率h来表示访问效率e。

如果r=100，为了使访问效率e>0.95,要求命中率h是多少？

对于上一问所要求的命中率实际上很难达到。假设实际的命中率只能达到0.96。现在用一种缓冲技术解决这个问题。当访问M1不命中时，把包括被访问数据在内的一个数据块都从M2中取到M1中，并假设被取到M1中的每个数据平均可以被重复访问5次。请设计缓冲深度（即每次从M2中取到M1中的数据块的大小）

答：

两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个系统。这个系统对应用程序员透明，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。

s1<

Ta=h·T1+(1-h)·T2

E=1/(1-h)r+h??????*

将r=100代入*式得到h>99.946%

（1-0.96）/(n*5)=1-0.9995==>n=16 二

由三个访问速度、存储容量和每位价格都不相同的存储器构成一个存储系统，其中，M1靠近

M1 (T1,S1C1) M2 (T2,S2C2) M3 (T3,S3C3) CPU。回答下列问题：

写出这个三级存储系统的等效访问时间T，等效存储容量S和等效每位价格C的表达式。 在什么条件下，整个存储系统的每位平均价格接近于C3？ 答：

T=T1；S=S3；C=C3 S3>>S2

三

要求设计一个由Cache和主存储器构成的两级存储系统，已知Cache的容量有三种选择：64K

字节、128K字节、256K字节，他们的命中率分别为0.7、0.9、0.98。主存储器的容量为4M字节。并假设两个存储器的访问时间分别为t1和t2，每字节的价格分别为c1和c2。如果c1=20c2，t2=10t1。

在t1=20ns的条件下，分别计算三种Cache的等效访问时间。

如果c2=0.2美元/千字节，分别计算三种Cache每字节的平均价格。 根据三种Cache的等效访问时间和每字节的平均价格排列次序。 根据等效访问时间和平均价格的乘积，选择最优设计。

答：

T64K=0.7·20+0.3·200=74ns；T128K=0.9·20+0.1·200=38ns；T256K=0.98·20+0.02·200=23.6ns

C64K=（4·64+0.2·4000）/4064=0.26$/KB；C128K=(4·128+0.2·4000)/4128=0.32$/KB C256K=(4·256+0.2·4000)/4256=0.43$/KB；

74·0.26=19.24 38·0.32 =12.16 23.6·0.43=10.148==>256Kcache的方案最优 四

对于一个由Cache和主存储器构成的两级存储系统，已知Cache的容量s1=512字节， 主存储器的容量s2未知；Cache的命中率为h=0.95；Cache的访问时间t1=20ns,主存的访问时间t2未知；Cache的价格c1=0.01美元/字节，主存的价格c2=0.5美元/千字节。要求两个存储器的总价格不能超过15000美元。

在不超过预算的范围内，可能得到的主存的最大容量是多少？

为了使这个两级存储系统的等效访问时间达到40ns，主存的访问时间t2应该是多少？ 答：

（15000-0.01*512）/0.5=30MB(大约)

0.95·20+(1-0.95)·t2=40ns==>t2=420ns

五

假设程序中出现转移并且转移成功的概率为0.1，设计一个采用地位交叉方式访问的多体存储器，要求每增加一个存储体在一个存储周期中能够访问到的平均指令条数增加0.2条以上，请计算最多的并行存储体的个数。

根据存储体的加速比B转移概率λ和交叉存储体的个数m之间的关系： 答：

B=(1-(1-λ)m)/λ

B=10*(1-0.9m)

由上式求出m的最大值为16。

六

一台处理机的运算速度为1GIPS,每执行一条指令平均需要取指令一条和读/写数据两个，输入输出系统对存储器的访问可以忽略不计。主存储器采用DRAM芯片，工作周期为150ns，请设计存储系统方案，可以采取哪些措施来匹配存储器与CPU之间的速度差距？每一种措施大概能弥补多少倍？

答：

CPU频带宽度：（1+2）*1000MW/s=3000 MW/s DRAM频带宽度：6.67MW/s 前者大概是后者的450倍

由三条途径可以解决存储器的频带平衡问题：

第一种是多个存储器并行工作，例如并行访问存储器和交叉访问存储器，其加速比一般不会超过10。

第二种是设置各种缓冲存储器，例如先行缓冲栈、后行写数栈，通用寄存器等。加速比一般也不会超过10

第三种是采用Cache存储系统，一般有两级，如果调度方法适当，可以大大提高系统的加速比。 七

有16个存储器模块，每个模块的容量为4M字节，字长为32位。现在要用这16个存储器模块来构成主存，有如下几种组织方式： 16个存储器采用高位交叉方式构成存储器 16个存储器构成并行访问存储器

16个存储器采用低位交叉方式构成存储器 2路高位交叉8路低位交叉构成存储器 4路高位交叉4路低位交叉构成存储器 4路并行访问4路低位交叉构成存储器 问：

写出各种存储器的地址格式 比较各种存储器的优缺点

不考虑访问冲突，计算各种存储器的频带宽度 画出各种存储器的逻辑示意图 答：

存储器按字节寻址。16个存储器模块==>4位地址；4M字节容量==>22位地址。 16个存储器采用高位交叉方式构成存储器：

4位 22位 模块地址 模块内字节地址 16个存储器构成并行访问存储器： 22位 4位 模块内字节地址 选模块 16个存储器采用低位交叉方式构成存储器：

22位 4位 模块内字节地址 模块地址 2路高位交叉8路低位交叉构成存储器： 1位 22位 3位 选存储体 模块内字节地址 选模块 4路高位交叉4路低位交叉构成存储器

2位 22位 2位 选存储体 模块内字节地址 选模块 4路并行访问4路低位交叉构成存储器

2位 22位 2位 选模块 模块内字节地址 选模块 低位交叉存储器若采用流水线工作方式，一次能够取出一个数据块，带宽较高，但是如果一个存储器模块出错，整个存储体都无法正常工作，容错能力较差。高位交叉存储器一个模块出现故障其他模块仍然能够正常工作，容错能力较好，但如果所读的数据地址是连续的，则一个存储周期就只能读出一个存储字，带宽较低。并行存储器的并行性高，一个周期能同时读出多个数据，但是冲突大。

存储器按字节编址，按字存取。

16个存储器采用高位交叉方式构成存储器：

因为是高位交叉所以一个存储周期只能读出一个存储字B=10MW/s 16个存储器构成并行访问存储器：

一个周期能读出16个存储字B=160 MW/s 16个存储器采用低位交叉方式构成存储器: 一个周期能读出16个存储字B=160 MW/s 2路高位交叉8路低位交叉构成存储器： 一个周期能读出8个存储字B=80 MW/s 4路高位交叉4路低位交叉构成存储器: 一个周期能读出4个存储字B=40 MW/s 4路并行访问4路低位交叉构成存储器 一个周期能读出16个存储字B=160 MW/s

MBA 存储体0 MBR 存储体1 ...16个 MBR 存储体15 MAR MAR MAR ? 译码器

（高4位） 存储器地址寄存器（低22位） 高位交叉访问存储器的结构 MBR 存储体0 MBR MBR 存储体15 存储体1 ...16个 MAR MAR MAR ? 存储器地址寄存器（高22位） 低位交叉访问存储器的结构

（低4位） 译码器

数据寄存器MBR 存储体 （m字×w位） 地址寄存器MAR MBR 多路选择器 ?? ?? ??? 存储体（4M字节×128位） MAR22位 4 一般存储器 并行访问存储器

八

一个4*4的矩阵，要求在一个存储周期内实现按行、按列、按对角线和按反对角线的无冲突访问。至少需要多少个存储体？写出矩阵的各元素在存储体中的存放位置。 ① 00 01 02 03 00 00 00 01 00 10 00 10 11 12 13 01 00 01 01 01 10 01 20 21 22 23 10 00 10 01 10 10 10 30 31 32 33 11 00 11 01 11 10 11 ③iH ? iL 0 0 0 0 00 00 00 01 00 10 00 1 1 1 1 01 00 01 01 01 10 01 1 1 1 1 10 00 10 01 10 10 10 0 0 0 0 11 00 11 01 11 10 11 ⑤2（iL ? jH）＋（iH ? iL ? jL） 0 1 2 3 00 00 00 01 00 10 00 3 2 1 0 01 00 01 01 01 10 01 1 0 3 2 10 00 10 01 10 10 10 2 3 0 1 11 00 11 01 11 10 11 九

一个页式虚拟存储器的虚存空间大小为4GB,页面大小为4KB，每个页表存储字要占用4个字节。

计算这个页式虚拟存储器需要几级页表？

②2（iL ? jH） 0 0 00 00 00 01 2 2 01 00 01 01 0 0 10 00 10 01 2 2 11 00 11 01 ④iH ? iL ? jL 0 1 00 00 00 01 1 0 01 00 01 01 1 0 10 00 10 01 0 1 11 00 11 01 结果： 00 10 00 00 00 01 31 21 01 00 01 01 12 02 10 00 10 01 23 33 11 00 11 01 2 00 0 01 2 10 0 11 0 00 1 01 1 10 0 11 20 00 11 01 32 10 03 11 2 00 0 01 2 10 0 11 1 00 0 01 0 10 1 11 30 00 01 01 22 10 13 11 11 11 11 11 10 10 10 10 11 11 11 11 11 11 11 11 10 10 10 10 11 11 11 11 11 11 11 11 10 10 10 10 11 11 11 11

如果要求页表所占的总的储存页面数最小，请分配每一级页表的实际存储容量各为多少字节？

页表的哪些部分必须放在主存中？哪些可以放在辅存中？ 答：

页表占用：(4GB/4KB)*4=4MB；存储页表需：4MB/4KB=1000个页面==>共需两级页表 最少的形式一级页表4KB,二级页表4MB，共1001页（全部装满）。

一级页表和调入主存程序的相关页表必须在主存中，其它可以在辅存中。

十

在一个采用快慢表的虚拟存储器中，访问主存的命中率为99.99%，访问快表的命中率为99%，经过快表进行地址变换的时间仅是经过查页表进行地址变换时间的十分之一，磁盘存储器的访问速度仅是主存访问速度的万分之一 计算这个虚拟存储器的等效访问时间 计算这个虚拟存储器的访问效率 答：

访问虚拟存储器的时间包括地址变换时间，访问主存时间，访问磁盘时间。 设主存周期是T1,则TLB周期：0.1T1,磁盘周期:10000T1。 T等效=0.9999(2*0.01T1+0.99*1.1T1)+0.0001*10000T1=2.1T1 E效率=1/2.1=47.6% 十一

一个页式虚拟存储器按字节编址，页面大小为1K字节，每个数据的字长为4个字节。现有一个程序的页表如下：

虚页号 装入标志 主存页号 修改标志 访问方式

0 1 2 3 4 5 6

1 1 0 1 0 1 0

2 3 0 1 0 0 0

0 0 0 0 0 0 0

RW R R X RW R X

表中装入标志为1表示该虚页已经装入内存中，为0表示还未装入主存。修改标志为0表示该页还没有被修改过，为1表示该页已经被修改过。访问方式RW表示该页可以读也可以写，

但不能作为指令来执行；“R”表示该页只能读，不能写和执行；“X”表示该页只能作为指令来执行，不能读和写。

虚地址经变址寻址和基址寻址(B)+(X)+D形成。现有一个程序，出现下列访问主存的操作：

序号 操作 虚存地址

（B）

1 2

取数 取数

124 2000

(X) 30 1000

D 50 60

3 4 5 6 7 8 9 10

存数 存数 取数 取数 加并存数 加并存数 转移 转移

4000 1200 3000 4096 400 36 2500 3600

2000 4600 64 500 1200 360 600 1200

600 60 100 20 80 64 100 56

列出产生主存页面实效的操作序号。

如果不发生主存页面失效的话，计算访问主存的物理地址。 列出被修改过的主存页面号。

列出非法操作的序号。 答：

虚地址 虚页号 实页号 页内偏移 实地址 操作 合法性 0 1 2 3 4 5 6 7 8 9

204 3060 6600 5860 3740 4616 1680 460 3200 4856

0 3 6 5 3 4 1 0 3 4

2 1 无 0 1 无 3 2 1 无

50 60 无 60 100 无 80 64 100 无

2098 1084 无 0060 1124 无 3116 2128 1124 无

未改 未改 失效 未改 未改 失效 未改 修改 未改 失效

合法 非法 无 非法 非法 无 非法 合法 合法 无

失效操作：2、5、9。修改过的主存页号2。非法操作：1、3、4、6。 十二

一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存的容量是8M字节。

写出多用户虚地址的格式，并标出各字段的长度。 写出主存地址的格式并标出各字段的长度。

快表的字长是多少位？分几个字段？各字段的长度是多少？

慢表的容量是多少个存储字？每个存储字的长度是多少位？

画出多用户虚拟地址经快表或慢表变换成为主存实地址的逻辑示意图。 答：

虚地址格式：

6 10 12

用户ID 主存地址格式： 11

实页号 快表： 16

用户ID与虚页号 11 实页号 虚页号 页内偏移 12 页内偏移 慢表容量：8M/4K=2K个存储字， 1 11 装入位

多用户虚地址 实页号 用户号U

虚页号P 主存实地址 实页号p U,P 页内偏移D 页内偏移d P 实页号p

1 装入 P 实页号p 慢表 快表 多用户虚页号(U,P拼接) 慢 表 快表(按内容相联访问)

十三

一个虚拟存储器按照字节编址，最多有256个用户，每个用户最多要用4096页，每页1K字节。主存容量16M字节。快表按地址访问共32个存储字，它的地址码经散列变换得到，为减少散列冲突，快表分为两组，有两套独立的相等比较电路。 写出多用户虚地址和主存地址的格式，并标出各字段的长度。 散列变换部件的输入位数和输出位数各为多少？ 每个相等比较电路的位数是多少？

快表每个存储字的总长度是多少分为几个字段？每个字段的长度？ 画出多用户虚拟地址经快表或慢表变换成为主存实地址的逻辑示意图。

答：

虚地址格式：

8

用户ID 主存地址格式： 14

实页号 12 虚页号 10 页内偏移 10 页内偏移 散列变换部件输入： 用户ID和虚页号，20位，输出：32个存储字，5位。 相等比较电路的位数是20，用户ID和虚页号。 快表：

20

用户ID与虚页号

多用户虚地址

14 实页号 8 用户号ID 5位 12 虚页号P 14 实页号p 或 10 页内偏移D 10 拼接 页内偏移d 20位 不等 32行 不等 相等比较 相 ID与P拼接 等 p 散列变换 相等比较 相 等 ID与P拼接 p 多用户虚页号 实地址 多用户虚页号 实地址 快表（按地址访问，有两组）

十四

在页式虚拟存储器中，一个程序由P1~P5共5个页面组成。在程序执行过程中依次访问到的页面如下：

P2, P3, P2, P1, P5, P2, P4, P5, P3, P2, P5, P2

假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU和OPT三种页面替换算法

对这三页主存进行调度。

画出主存页面调入、替换和命中的情况表。 统计三种页面替换算法的页命中率 答： 时间t 页地址流 先进先出算法 （FIFO算法） 最久没有使用算法 （LFU算法） 最优替换算法 （OPT算法） 1 P2 2* 2 P3 2* 3 3 P2 2* 3 4 P1 2* 3 1 5 P5 5 3* 1 6 P2 5 2 1* 7 P4 5* 2 4 8 P5 5* 2 4 9 P3 3 2* 4 10 P2 3 2* 4 11 P5 3 5 4* 12 命中次数及P2 3* 5 2 命中率 3次 25% 5次 41.7% 6次 50% 调入 调入 命中 调入 替换 替换 替换 命中 替换 命中 替换 替换 2* 2 3 2 3* 2 3* 1 2* 5 1 2 5 1* 2 5* 4 2* 5 4 3 5 4* 3 5* 2 3* 5 2 3 5* 2 调入 调入 命中 调入 替换 命中 替换 命中 替换 替换 命中 命中 2* 2 3* 2 3* 2 3 1* 2 3* 5 2 3* 5 2 4* 5 2 4* 5 2 3* 5 2 3* 5 2 3 5 2 3 5 调入 调入 命中 调入 替换 命中 替换 命中 替换 命中 命中 命中 三种页面替换算法对同一个页地址流的调度过程

十五

一个程序由五个虚页组成，采用LFU替换算法，在程序执行过程中依次访问的页地址流如下： P4, P5, P3, P2, P5, P1, P3, P2, P3, P5, P1, P3 可能的最高页命中率是多少?

至少要分配给该程序多少个主存页面才能获得最高的命中率。

如果在程序执行过程种每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。

答：

7/12=58.3%；4个；1-5/（1024*12）=99.95%

十六

一个程序由1200条指令组成，每条指令的字长均为4个字节。假设这个程序访问虚拟存储器的字地址流依次为：12，40，260，280，180，800，500，560，600，1100，1200，1000。 采用FIFO页面替换算法，分配给这个程序的主存容量为2048个字节。在下列不同的页面大小情况下，分别写出这个程序执行过程中依次访问的虚存页地址流，并计算主存的页面命中率。

页面大小为1024个字节。 页面大小为512个字节。 页面大小为2048个字节。

比较上述三问可以得出什么结论？

如果把分配该程序的主存容量增加到4096个字节，页面大小位1024个字节，再做一遍又可以得到什么结论？ 答：

当页面大小增加到1K以后，再增加页面大小并不能显著地提高命中率，此时如果增加内存容

量就可以提高命中率。 1 2 3 4 5 6 7 8 9 10 11 12

十七

在计算机系统中设置虚拟存储器和Cache的主要目的各是什么？试举出这两种存储系统在具体实现时至少4个方面的差别，并说明主要理由。 答：

区别方面 目的 实现方法 两级存储器速度比 页或块的大小 等效容量

Cache存储系统 提高主存速度 全部硬件 3~10 1~16W 主存

虚拟存储系统 扩大主存容量 软件为主、硬件为辅

10 1KB~16KB 虚拟存储器

5

字地址 12 40 260 280 180 800 500 560 600 1100 1200 1000

字节地址

48 160 1040 1120 720 3200 2000 2240 2400 4400 4800 4000 命中率

1K页面 页面流 1 1 2 2 1 1 2 2 2 1 1 2 50%

L H L H H R H R H R H R

.5K页面 页面流 1 1 2 2 3 4 1 2 2 3 4 1 25%

L H L H L L R R H R R R

2K页面 页面流 1 1 1 1 1 1 1 1 1 1 1 1 50%

L H H H H R R R H R H R

4K内存 页面流 1 1 2 2 1 3 2 4 4 1 1 3

L H L H H L H L H R H H

58.3%

理由 硬件速度高 硬盘访问时间长 Cache成本大 命中率高

透明性 不命中时的处理

对系统和应用程序员

等待主存

只对应用程序员

任务切换

VM由软件实现 OS多任务、硬盘慢

十八

试比较下列5种Cache的主要优缺点： 第一种：直接映像方式的Cache 第二种：全相联映像方式的Cache 第三种：组相联映像方式的Cache

第四种：位选择组相联映像方式的Cache 第五种：段相联映像方式的Cache 并回答下列问题：

根据硬件的复杂性和实现所需要的成本排出5种Cache的次序，并说明理由。 根据块替换算法实现的灵活性排出5种Cache的次序，并说明理由。 解释各种Cache的块映像方式对命中率的影响。

在采用相联映像方式的Cache种，说明块大小、组数、Cache容量、块替换算法等对Cache性能的影响。 答：

根据实现所需的硬件复杂性和成本的排序：（从低到高） 直接映像方式 ，无需相联比较电路，按地址访问。

段相联映像方式 ，需要相联比较的部分最少，因为段的容量最大。

位选择组相联映像方式，组之间相联比较，组内直接映像，映像关系比组相联方式简单。 组相联映像方式，部分需要相联比较电路。

全相联映像方式，全部需要相联比较电路，按内容访问。

实现替换算法灵活性的排序：（从低到高） 直接映像方式,没有灵活性。

段相联映像方式，如果发生段失效，整个段内的数据都将作废，但段的容量很大。 位选择组相联映像方式，主存中的组和Cache中的组是多个块到一个块的映像。 组相联映像方式，主存中的组和Cache中的组是多个块到多个块的映像。 全相联映像方式，可以在任意位址映像，实现起来最灵活。

Cache命中率与容量的关系：

Cache的命中率随它的容量的增加而提高。 关系曲线可以近似地表示为H＝1－S－0.5。 Cache命中率与块大小的关系：

在组相联映象方式中，块的大小对命中率的影响非常敏感 块很小时，命中率很低。

随着块大小的增加，由于程序的局部性，命中率增加。 当块非常大时，进入Cache中的许多数据可能用不上。 当块大小等于Cache的容量时，命中率将趋近于零。 Cache命中率与组数的关系：

在组相联映象中，分组的数目对命中率的影响很明显。 随着组数的增加，Cache的命中率要降低。

当组数不太大时(512组以下)，命中率的降低相当少，

当组数超过一定数量时，命中率的下降非常快。 Cache命中率与替换算法的关系： 替换算法按照优先顺序：OPT、LFU、FIFO。

十九

假设在一个采用组相联映像方式的Cache中，主存由B0~B7共8块组成，Cache有2组，每组2块，每块的大小为16个字节，采用LFU块替换算法。在一个程序执行过程中依次访问这个Cache的块地址流如下：

B6, B2, B4, B1, B4, B6, B3, B0, B4, B5, B7, B3 写出主存地址的格式，并标出各字段的长度。 写出Cache地址的格式，并标出各字段的长度。

画出主存与C写出主存地址的格式，并标出各字段的长度。 写出Cache地址的格式，并标出各字段的长度。

画出主存与Cache之间各个块的映像对应关系。

如果Cache的各个块号为：C0、C1、C2和C3,列出程序执行过程

如果采用FIFO替换算法，计算Cache的块命中率。 采用LFU替换算法，计算Cache的命中率。

如果改为全相联映像方式，再做5.6可以得到什么结论？

如果在程序执行过程当中，每从主存装入一块到Cache，则平均要对这个块访问16次。计算Cache的命中率。 答：

主存地址格式：

1

区号 Cache地址格式: 1

组号

1 2 1 2 1 2

1 2 1 2 1 2 1 组号 1 块号 4 块内偏移 1 块号 4 块内偏移

时间t 块地址流 组相联 先进先出算法 （FIFO算法） 组相联 最久没有使用算法 （LFU算法） 全相联 先进先出算法 （FIFO算法） 全相联 最久没有使用算法 （LFU算法） B6 B6 B6 B2 B6 B6 B6 B2 1 B6 2 B4 B4 3 B2 B4 4 B1 B4 B1 B2 5 B4 B4 B1 B2 6 B6 B1 B2 7 B3 8 B0 9 B4 10 B5 B4 B3 11 B7 B5 B4 B3 12 命中次数及B3 B5 B4 B7 B3 命中率 3次 25% 3次 25% 3次 33% 3次 25% B4* B4* B0 B6 B3 B6 B3 B0* B5 B6 B3 B1 B1* B4 B6* B6* B6 B6* B7 调入 调入 调入 调入 命中 命中 替换 替换 替换 替换 替换 命中 B4 B4 B4 B1 B2 B4 B1 B2 B4 B1 B6 B2 B4 B1 B0 B1 B0 B4 B3 B2 B5 B4 B3 B2 B5 B4 B3 B7 B5 B4 B3 B7 B6* B6 B3 B3 B2 B2 调入 调入 调入 调入 命中 命中 替换 替换 替换 替换 替换 命中 B6 B6 B2 B6 B2 B4 B6 B2 B4 B1 B6 B2 B4 B1 B6 B2 B4 B1 B3 B2 B4 B1 B3 B0 B4 B1 B3 B0 B4 B1 B3 B0 B5 B1 B3 B0 B5 B7 B3 B0 B5 B7 调入 调入 调入 调入 命中 命中 替换 替换 命中 替换 替换 命中 B6 B6 B2 B6 B2 B4 B6 B2 B4 B1 B6 B2 B4 B1 B6 B2 B4 B1 B6 B3 B4 B1 B6 B3 B4 B0 B6 B3 B4 B0 B5 B3 B4 B0 B5 B7 B4 B0 B5 B7 B4 B3 调入 调入 调入 调入 命中 命中 替换 替换 命中 替换 替换 替换 两种块替换算法对同一个块地址流的调度过程

H'=1-(1-H)/n=95.3%

二十

在一个采用组相联映像方式的Cache中，Cache的容量为16KB。主存采用模8低位交叉方式访问，每个存储体的字长为32位，总容量为8MB。要求Cache的每一块在一个主存周期中分别从8个存储体中取得，Cache的每一组内共有4个块。要求采用按地址访问方式构成相联目录表，实现主存地址到Cache地址的变换并采用8个相等比较电路。 设计主存地址格式，并标出各字段的长度。 设计Cache地址格式，并标出各字段的长度。

相联目录表的行数是多少？

设计相联目录表每一行的格式，并标出每一个字段的长度。

每个比较电路的位数是多少？

画出主存地址经过相联目录表变换为Cache地址的逻辑示意图。 答：

主存地址格式：

9 9 2 3

区号 组号 块号 块内偏移 Cache地址格式： 9 2

组号 块号 3 块内偏移 组号9位,8个相等比较电路==>相联目录表应有64行。 相联目录表格式：

11 2 1 8 11 主存区号组内块号 缓存块号 标志 比较电路地位数是11位。 区号E 区内组号G 组号g Cache地址 b 组内块号B 组内块号b ≠ ?? ?? ?? ?? 或 相等比较 ＝ E, B ? 主存区号组内块号 2 缓存块号 1 标志 块内地址W 块内地址w 主存地址 ≠ 二十一

块失效 与 相等比较 ＝ E, B b ≠ 相等比较 ＝ e E, B b e 块表(按地址访问,读出的多个字段进行相联比较,e为有效位)

一个采用位选择组相联映像方式的Cache，要求Cache的每一块在一个主存周期内取得。主

存采用4个存储体的低位交叉访问，每个存储体的字长为4个字节，总容量为1MB。Cache的容量位1KB,每一组内由4个块。采用按地址访问的存储器构成相联目录表，实现主存地址到Cache地址的变换，采用4个相等比较电路。 设计主存地址格式，并标出各字段的长度。 设计Cache地址格式，并标出各字段的长度。 设计相联目录表每一行的格式、行数。

每个比较电路的位数是多少？

画出主存地址经过相联目录表变换为Cache地址的逻辑示意图。 答：

4体低位交叉==>每个块4个字、16个字节。 Cache容量1KB==>64个块 每组4个块==>16组

Cache16个组==>主存每区16块==>256B 主存1M==〉4K区

主存地址格式：

12

区号

Cache地址格式;

4

组号 4 块号 2 块内字号 2 块号 2 块内字号

相联目录表每行格式：

12 2 1 主存区号 缓存块号 标志

比较电路12位，比较主存区号。

主存地址 ≠ 相等比较 ＝ E b 块失效 与 区号E 4个 ? 12 主存区号 2 缓存块号 1 标志 区内块号B 组内块号b 或 块内地址W 块内w 组号g Cache地址 ≠ 相等比较 ＝ E b ≠ 相等比较 ＝ ?? ?? ?? ?? E b 区号E 块号b e 区号E 块号b e 区号E 块号b e 块表(按地址访问,读出的多个区号进行相联比较,e是有效位)

二十二

一个处理机使用10位地址，读数据的地址请求序列（十六进制）为54，58，104，5C， 108，60，F0，64，54，58，10C，5C，110，60，F0，64。假定CACHE的最初状态为 空，CACHE不命中时使用LRU替换算法，试分析在下列CACHE结构中，每个地址的 命中次数和不命中次数（自己指定CACHE的总容量）。 以块（2个字）为单位的全相联CACHE结构

以块（2个字）为单位的2路组相联CACHE结构

地址分布：十位地址，下面类似的表格应有4（256*4=1024=2）个，只用到前两个。 00 0 1 2 3 4 5 6 7 8 9 A B C D E F 01 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 6,14 7,15 0 13 1 1 2 2 3 3 4 1 ,9 8,16 4 3 5 5 6 6 7 7 8 2,10 8 5 9 9 A A B B C 4,12 C 11 D D E E F F 10

注意到这个地址分布似乎都集中在两行之内，不妨设CACHE的容量为32字节（字长16，地址码10位的机器一般都是16位机，例如8086）16字，8块。CACHE以块为单位访问，一次就装入4个字节的内容。

下两页图为算法过程，装入和替换为不命中，结果： 54 装入1 108 装入1 10C 替换1 命中1 58 装入1 命中1 104 装入1 5C 装入1 命中1 60 F0 64 装入1 命中1 装入1 命中1 装入1 命中1 110 替换1

过程： 全相联： 块号 1 2 3 4 5 6 7 8 1 2 3 4 00 0 1 2 3 4 5 6 7 8 9 A B C D E F 01 0 1 2 3 4 5 6 0 6,14 7,15 0 13 1 1 2 2 3 3 4 1 ,9 8,16 4 3 5 5 6 6 7 7 8 2,10 8 5 9 9 A A B B C 4,12 C 11 D D E E F F 54 58 104 5C 装入 装入 装入 装入 5 6 7 8 108 60 F0 64 装入 装入 装入 装入 9 10 11 12 54 58 10C 5C 命中 命中 替换 命中 13 14 15 16 110 60 F0 64 替换 命中 命中 命中 7 8 9 A B C D E F

组相联： 组号 1 块号 1 2 3 4 5 6 7 8 54 装入 58 装入 104 装入 5C 装入 5 108 装入 6 60 装入 7 F0 装入 8 64 装入 2 00 0 1 2 3 4 5 6 7 8 9 A B C D E F 01 0 1 2 3 4 5 6 1 2 3 4 9 10 11 12 54 58 10C 5C 命中 命中 替换 命中 13 14 15 16 110 60 F0 64 替换 命中 命中 命中 0 6,14 7,15 0 13 1 1 2 2 3 3 4 1 ,9 8,16 4 3 5 5 6 6 7 7 8 2,10 8 5 9 9 A A B B C 4,12 C 11 D D E E F F 7 8 9 A B C D E F 二十三 一个采用组相联映像方式的Cache共有8块，分成两组，用硬件比较对法实现LFU块替换算法。

共需要多少个触发器？多少个与门？ 画出其中一组的逻辑图。 答：

触发器个数=C2块数 ==>6*2=12 与门个数=块数=8 A LFU 0 1 R Tca S A

B C D LFU LFU LFU 0 R 1 TAB S 0 R 1 0 TBC S R TCD 1 0 S R TDA 1 TDB S 1 0 S R B C D 二十四

对于一个采用组相联映像方式和FIFO替换算法的Cache,发现它的等效访问时间太长，为此提出如下改进意见： 增大主存容量。 提高主存的速度。 增大Cache的容量。

提高Cache的速度。

Cache总容量和组大小不变，增大块的大小。 Cache总容量和块的大小不变，增大组的大小。 Cache总容量和块的大小不变，增加组数。 替换算法由FIFO改为LFU。

分析上述改进意见对等效访问时间有何影响，其影响的程度如何？ 答：

本文来源：https://www.bwwdw.com/article/27qg.html