计算机体系结构

计算机体系结构

什么是存储系统？对于一个由两个存储器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以后，再增加页面大小并不能显著地提高命中率，此时如果增加内存容

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

画出主存地址经过相联目录表变换为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。

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

当4个存储体2路低位交叉方案中有一个存储器模块失效，则此时存储器组织为3体2路交叉存储器，并且最大存储器带宽减少位每周期6个字节。 方案1带宽高、容错差。方案2带宽低、容错好。 三十

说明采用层次存储器系统所追求的目标，以及能够达到这种目标是建立在什么基础之上的？ 答：

计算机存储器层次模型的目标应该是在合理的成本范围内，通过对各级存储器大小的配置，达到可接受的性能。

层次结构原理主要包含以下3个重要特性： 包含性：

M0? M1? M2?…… ? Mn

所有信息项最初存放在最外层Mn，在处理过程中，它的子集复制到Mn-1，同样， Mn-1的子集复制到Mn-2，……

如果在Mi中找到一个信息字，那么同一个字的复制品在所有的高层Mi+1，Mi+2，……，Mn中都一定可以找到。 一致性：

同一个信息项与后继存储器层次的副本是一致的。

如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改 。

局部性：

Hennessy和Patterson（1990年）提出了一条90-10规则：典型程序在10%的代码上可能要耗费其执行时间的90%（例如嵌套循环操作的最内层循环）。 时间局部性（temporal locality）：最近的访问项（指令或数据）很可能在不久的将来再次被访问。即对最近使用区域的集中访问 空间局部性（spatial locality）：一个进程访问的各项的地址彼此很近，例如，表操作或数组操作含对地址空间中某一区域的集中访问。 顺序局部性（sequential locality）：在典型程序中，除非转移指令产生不按次序的转移外，指令都是顺序执行的。

局部性原理指导我们去设计高速缓存、主存储器以及虚拟存储器组织。 三十一

一个按位编址的虚拟存储器，它可以满足1K个任务的需要，但在一段比较长的时间内，一般只有4个任务在使用，故用容量为4行的相联存储器组硬件来缩短被变换的虚拟地址中的用户位数。每个任务的程序空间最大可达4096个页，每页为512个字节，主存容量为230位。设快表用按地址访问的存储器构成，行数为32，快表的地址是经过散列技术形成的。为减少散列冲突，配有两套独立的相等比较电路（这时快表的每行包含两个单元，各存放一个进行地址变换的表目）。设计该地址变换机构，内容包括： 画出虚实地址经块表变换的逻辑图

相联存储器组种每个寄存器的相联比较位数 散列比较硬件的输入位数和输出位数 每个相等比较器的位数 快表的总位数 答：

多用户虚地址

相联比较

U1 U2 U3 U4

10 用户号U 00 01 10 11 5位 12 虚页号P 拼接 8 实页号p 或 9 3

字地址 位地址 9 3 实地址 字地址 位地址 相联寄存器组 ID 14位 不等 不等 相等比较 相 ID与P拼接 等 p 散列变换 相等比较 相 等 ID与P拼接 p 多用户虚页号 实页号 多用户虚页号 实页号 相联存储器组的每个寄存器相联比较位数为10位

散列硬件的输入是任务ID加上虚拟页号，所以输入为14位，快表是32行，故散列硬件输出为5位。

每个相等比较器的位数是14位。 快表的总位数：（14+8）*2*32=1408位 三十二 答：

某机主存的读写周期为1μs，现分别采用增设Cache方案和采用多体交叉存取方案来使其有效访问周期减少到0.2μs

若Cache的命中率为90%，则Cache的读写周期为多少？ 若访问冲突的概率为0.1，则需要多少个存储体？ 0.9*T+0.1*1=0.2==>T=1/9μs (1/m)*0.9+0.1*1=0.2==>m=9 三十三

答：

某计算机采用单地址格式，指令和数据的长度均为4个字节，存储系统由Cache和主存组成，Cache的存取周期是40ns。命中率为90%。若程序中访存指令占80%，且机器运行程序的速度位每秒400万条指令。试问该主存的供数率是多少？如果不配置Cache主存的供数率是多少？

每条指令平均访存次数： n=0.2*1+0.8*2=1.8

每秒访存次数： 4M*1.8=7.2M

设每秒访主存次数为N

(1/N)*0.1+0.9*40ns=1/7.2M==>N=0.97MW/s=3.88MB/s 如果没有Cache :

N=7.2MW/s=28.8MB/s

这样就要求较高的主存带宽。 三十四 答：

设有主存M1和辅存M2构成的2级存储体系，其中M1和M2的读出时间分别为1μs和1ms,经过实际测试2级存储系统的平均读出时间为100μs。给出两种改进设计的实现方法： 通过提高主存的命中率和提高辅存的访问速度来进行改进： 设命中率为H,系统周期T,M1周期TM1,M2周期TM2。 T=H* TM1+(1-H)* TM2

H=(T- TM1)/( TM1- TM2)=0.991 TM1=(T-H TM1)/(1-H)=10-4

三十五

简述写一次Cache一致性协议的工作原理 答：

写一次Cache算法是一种基于总线的多处理机系统的高速缓存一致性协议。 . 每份Cache中的副本可能出现的四种状态

（1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。 （2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。

（3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。

（4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到 局部命令（Local commands）

（1）P-Read：本地处理机读自己的Cache副本。 （2）P-Write：本地处理机写自己的Cache副本。

一致性命令 （1）Read-blk：从另一Cache读一份有效的副本。

（2）Write-inv：在写命中时在总线上广播一个无效命令。 （3）Read-inv：在写缺失时在总线上广播一个无效命令。

三十六

答：

假设Cache存储器的速度是主存的5倍，程序执行时90%的时间可以访问到Cache,求这种存储系统的加速比

5*0.9+0.1=4.6 三十七

解释虚拟共享存储器

答：

共享存储器：

易于编程，是单机的自然延伸； 程序员无数据划分的负担；

多进程并发的开销小，效率高，易于进程迁移，任务动态分配简单；

由于每个处理器都通过总线访问存储器，因而限制了处理器的个数，可扩展性

差。

分布存储器：

系统结构灵活，可扩展性好；

处理机数目可达成百上千，处理速度有巨大的发展潜力； 算法设计、编程以及任务动态分配比较困难；

很难在处理机之间传递复杂的数据结构，难于进程迁移； 不能支持需要存储空间的大规模数据处理要求。

分布存储的两种编程方法： （1）message-passing，用send，receive原语实现通信，要求程序员在进程的整个运行期间对数据的移动都很清楚； （2）romote procedure call，语言一级传送控制与数据，可以看作是本地调用，但透明度有限。 缺点：

这两种方法都是用来解决不同地址空间的问题，在结点间传递复杂数据结构时都比较困难，需要打包，传递指针也不可能实现。由于个处理机拥有不同的地址空间，使得进程迁移时，该进程所分配到的操作系统资源也得一起移动（打开的文件、文件存取控制块等），这很费时。 把共享和分布的优点结合起来：基于分布存储器的多处理机上，实现物理上分布但逻辑上共享的存储器系统就称为虚拟共享存储器。 三十八

假定在1000次内存访问中，1级Cache中有40次缺失，2级Cache上有20次缺失，缺失率分别为多少？ 答： 1级Cache: 40/1000=4% 2级Cache: 20/40=50% 三十九

由三个Cache存储器，每个有4个Block,每个Block有1个字，第一个Cache存储器采用全相联映像方式，第二个Cache采用2路组相联方式，第三个Cache采用直接映像方式。Block地址流如下：0、8、0、6、8

计算三种结构的缺失次数 答： 全相联：3 组相联：4 直接映像：5 四十

一个由高速缓冲存储器与主存储器组成的2级存储系统。已知主存容量为1MB,缓存容量为32KB,采用组相联方式进行地址变换，主存与缓存每一块为64B,缓存一工分为8组。

写出主存与缓存的地址格式（地址码长度及各字段名称与位数）

假定Cache的存取周期为20ns，命中率为95%，希望采用Cache以后的加速比大于10，求主存的存取速度 答：

主存地址：20位

5 3

区号 组号 6 块号

6 字号 Cache地址：15位

3

组号 6 块号

6 字号 设主存速度为T，缓存周期是它的k倍

kT*0.95+T*0.05=0.1T==>0.95k=0.05==>T=20*19=380ns

本文来源：https://www.bwwdw.com/article/0e9r.html