3.并行主存与存储

3.并行主存与存储

3.1 什么是存储系统？对于一个由两个存储器M1和M2构成的存储系统，设M1的命中率为h ，两个存储器的容量分别为S1和S2，访问速度分别为T1和T2，每千字节的价格分别为C1和C2。

（1）在什么情况下，整个存储系统的每千字节的平均价格接近于C2？

（2）写出这个存储系统的等效访问时间Ta 的表达式。

（3）假设存储系统的访问效率e=T1/Ta ，两个存储器的速度比r=T2/T1。试以速度比r 和命中率h 来表示访问效率e 。

（4）写出r=5,20,100时，访问效率e 和命中率h 的关系式。

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

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

【参考答案】

解：存储系统是指多个性能各不相同的存储器用硬件或软件方法连接成一个系统。这个系统对应用程序员透明。在应用程序员看来，它是一个存储器，其速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等或接近，单位容量的价格接近最便宜的那个存储器。

（1）当S2>>S1

（2）Ta=h·（3）e=T1/Ta=T1/(h·T1+(1-h)·T2)

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

=1/(h+ (1-h)·r)

（4）r=5,

e=1/(5-4h); r=20, e=1/(20-19h);

r=100, e=1/(100-99h)。

（5）由e=1/(h+ (1-h)·r)= 1/(h+ (1-h)·100)>0.95

得 h>94/94.05=99.958%

（6）h=0.96 设缓冲深度为A ，则n=5·A

由 h’=99.95%=(h+n -1)/n 求得A=16

3.2 由3个访问速度、存储容量和每位价格都不相同的存储器构成一个存储系统，其中M1靠近CPU 。回答下列问题：

（1表达式。

（2）在什么条件下，整个存储系统的每位平均价格接近于C3？

【参考答案】

解：设S1C2>C3

H1为在M1中访问的命中率

H2为在M2中访问的命中率

则（1）

S=S3（利用地址映象和地址变换）

T=H1·T1+(1-H1)·T23

=H1·T1+(1-H1)·(H2·T2+(1-H2)·T3)

当H1→1，H2→1时，T≈T1

C=(C1·S1+C2·S2+C3·S3)/(S1+S2+S3)

（2）当S3>>S2>>S1

C=(C1·S1/S3+C2·S2/S3+C3)/(S1/S3+S2/S3+1)

≈C3

3.3要求设计一个由Cache和主存构成的两级存储系统，已知Cache的容量有三种选择：64KB、128KB和256KB，它们的命中率分别为0.7、0.9和0.98。主存容量为4MB。设两个存储器的访问时间分别为t1和t2，每字节的价格分别为c1和c2。如果c1=20c2时，t2=10t1。

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

（2）如果c2=0.2美元/KB，分别计算三种Cache每字节的平均价格。

（3）根据三种Cache的等效访问时间和每字节的平均价格排列次序。

（4）根据等效访问时间和平均价格的乘积，选择最优的设计。

【参考答案】

解：已知c1=20c2，t2=10t1，s2=4MB，t1=20ns，C2=0.2美元/KB

(1) 1) h=0.7，t2=10t1=200ns

Ta=h×t1+(1-h)×t2=0.7×20+0.3×200=74ns

2) h=0.9，t2=200ns

Tb=h×t1 +(1-h)×t2=0.9×20+0.1×200=38ns

3) h=0.98，t2=200ns

Tc=h×t1 +(1-h)×t2=0.98×20+0.02×200=23.6ns

(2) 1) s1=64KB，c1=20c2=4美元/KB

Ca=(c1×s1+c2×s2)/(s1+s2)

=(4×64+0.2×4K)/(64+4K)≈0.26美元/KB

2) s1=128KB，c1=20c2=4美元/KB

Cb=(4×128+0.2×4K)/(128+4K)≈0.32美元/KB

3) s1=256KB，c1=20c2=4美元/KB

Cc=(4×256+0.2×4K)/(256+4K)≈0.43美元/KB

(3) Ta>Tb>Tc

Ca

(4) Ta×Ca=74ns×0.26美元/KB=19.24

Tb×Cb=38ns×0.32美元/KB=12.16

Tc×Cc=23.6ns×0.43美元/KB=10.148

∵Tc×Cc最小

∴第3种设计最优

3.4一个二级虚拟存储系统，CPU访问主存M1和辅存M2的平均时间分别为1us和1ms。经实测，此虚拟存储器平均访问时间为100us。试定性提出使虚拟存储器平均访问时间能从100us下降到10us的几种方法，并分析这些方法在硬件和软件上的代价。

【参考答案】

解：已知T1=1us, T2=1ms, T=100us

由T=H·T1+(1-H)·T2

得H=(T-T2) / (T1-T2)=(100-1000)/(1-1000)=0.901

分析：（1）在H= 0.901的情况下，提高主存速度，极限情况使T1=0，此时，

T=H·T1+(1-H)·T2=(1-0.901)·1ms≈99us>>10us，

说明此法不行

（2）提高H。设T=10us, 则

H=(T-T2) / (T1-T2)=(10-1000)/(1-1000)=0.991

为此，须从改进替换算法和调度策略，调整页面大小，提高主存容量等多方面综合采取

措施。其中，替换算法和调度策略主要是在软件上增加代价，调整页面大小可能会增加辅助硬件的代价，而提高主存容量主要是增加硬件的代价，辅助硬件的代价也可能会略有增加。

3.5 由两级存储系统关于每位平均价格c 及访问时间Ta 之表达式进一步推广导出n 级存储层次的相应表达式。

【参考答案】

解：先考虑三级存储系统。

设S1C2>C3

H1为在M1中访问的命中率

H2为在M2中访问的命中率

则（1）S=S3（利用地址映象和地址变换）

T=H1·T1+(1-H1)·T23

=H1·T1+(1-H1)·(H2·T2+(1-H2)·T3)

当H1→1，H2→1时，T ≈T1

C=(C1·S1+C2·S2+C3·S3)/(S1+S2+S3)

（2）当S3>>S2>>S1

C=(C1·S1/S3+C2·S2/S3+C3)/(S1/S3+S2/S3+1)≈C3

上述可推广至n 级：

存储系统的每位平均价格：

存储系统的访问时间：

其中， 3.6 设二级虚拟存储系统的T1=10-7s ，T2=10-2s ，为使存储层次的访问效率e 达到最大值的80%以上，命中率H 至少要达到多少？实际上这样高的命中率很难达到，那么从存储层次上该如何改进？

【参考答案】

解：已知 T1=0.1us, T2=10000us, e>=80% r=T2/T1=106

设该存储系统的平均访问时间为T ，

由

（4.6）

由式（4.6）可知，要提高e ，有两个途径：提高H ，或者减小r 。

提高H 的方法有：改进替换算法和调度策略，调整页面大小，提高主存容量等。 减少r 的方法有：采用多级存储系统，减少级间速度之比。

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

（1）计算这个页式虚拟存储器需要采用几级页表？

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

（3）页表的哪些部分必须存放在主存中？哪些可以放在辅存中？

【参考答案】

解：依题意，已知Nv=4GB, Np=4KB, Nd=4B

(1) ∑∑==?=n i i n i i i S S c c 11

i n i i T H T ?=∑=111=∑=n i i H