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时，S1C1S1C1C2C2C2S2S2C2CS2S11S11（2）Ta=h·T1+(1-h)·T2S23）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=163.2由3个接见速度、储藏容量和每位价格都不一样样的储藏器组成一个储藏系统，其中M1凑近CPU。回答以下问题：M1M2(T1,S1,C1)(T2,S2,C2)（1）写出这个三级储藏系统的等效接见时间T，等效储藏容量S和等效每位价格C的表达式。（2）在什么条件下，整个储藏系统的每位平均价格凑近于C3？【参照答案】解：设S1<S2<S3，T1<T2<T3，C1>C2>C3H1为在M1中接见的命中率H2为在M2中接见的命中率则（1）S=S3（利用地址映象和地址变换）

M3(T3,S3,C3T=H1·T1+(1-H1)T23·=H1·T1+(1-H1)(H2··T2+(1-H2)T3)·当H1→1，H2→1时，T≈T1C=(C1·S1+C2·S2+C3·S3)/(S1+S2+S3)2）当S3>>S2>>S1C=(C1·S1/S3+C2·S2/S3+C3)/(S1/S3+S2/S3+1)C33.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美元/KB1)h=0.7，t2=10t1=200nsTa=h×t1+(1-h)×t2=0.7×20+0.3×200=74nsh=0.9，t2=200nsTb=h×t1+(1-h)×t2=0.9×20+0.1×200=38nsh=0.98，t2=200nsTc=h×t1+(1-h)×t2=0.98×20+0.02×200=23.6ns1)s1=64KB，c1=20c2=4美元/KBCa=(c1×s1+c2×s2)/(s1+s2)=(4×64+0.2×4K)/(64+4K)≈0.26美元/KBs1=128KB，c1=20c2=4美元/KBCb=(4×128+0.2×4K)/(128+4K)≈0.32美元/KBs1=256KB，c1=20c2=4美元/KBCc=(4×256+0.2×4K)/(256+4K)≈0.43美元/KBTa>Tb>TcCa<Cb<CcTa×Ca=74ns×0.26美元/KB=19.24Tb×Cb=38ns×0.32美元/KB=12.16Tc×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级储藏层次的相应表达式。【参照答案】解：先考虑三级储藏系统。设S1<S2<S3，T1<T2<T3，C1>C2>C3H1为在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≈T1C=(C1·S1+C2·S2+C3·S3)/(S1+S2+S3)2）当S3>>S2>>S1C=(C1·S1/S3+C2·S2/S3+C3)/(S1/S3+S2/S3+1)≈C3上述可实行至n级：n储藏系统的每位平均价格：ciSici1n储藏系统的接见时间：Sii1n其中，nHi1THiTii1i1T1=10-7s，T2=10-2s，为使储藏层次的接奏效率e达到最大值的3.6设二级虚假储藏系统的80%以上，命中率H最少要达到多少？实质上这样高的命中率很难达到，那么从储藏层次上该如何改进？【参照答案】解：已知T1=0.1us,T2=10000us,e>=80%r=T2/T1=106设该储藏系统的平均接见时间为T，由T1T11e0.8THT1(1H)T2r(1r)H（4.6）得：H>=0.9999997由式（4.6）可知，要提高e，有两个路子：提高H，也许减小r。提高H的方法有：改进代替算法和调换策略，调整页面大小，提高主存容量等。减少r的方法有：采用多级储藏系统，减少级间速度之比。3.7一个页式虚假储藏器的虚存空间大小为4GB，页面大小为4KB，每个页表储藏字长4个字节。1）计算这个页式虚假储藏器需要采用几级页表？2）若是要求页表所占总的主存页面数最小，请分配每一级页表的实质储藏容量各为多少字节？3）页表的哪些部分必定存放在主存中？哪些能够放在辅存中？【参照答案】解：依题意，已知Nv=4GB,Np=4KB,Nd=4B(1)log2Nvlog2Np3212gNplog2Nv122log22(2)每页

虚假空间页面数为4GB/4KB=1M第1级页表为1页，储藏容量4KB，能够有1K个储藏字，指向第2级页表的1K1K个储藏字，共计1M个字，4MB容量，存放1M个页面信息。

页，第1级页表必定驻留主存，第2级页表中与目前正在运行的程序的相关页表可放在主存，其余部分必定放在辅存中，因为其容量高出了1页的大小。3.8在页式虚假储藏器中，一个程序由P1~P5共5个页面组成。在程序执行过程中依次接见到的页面以下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU和OPT三种页面代替算法对这3页主存进行调换。1）画出主存页面调入、代替和命中的情况表。2）统计3种页面代替算法的页命中率。【参照答案】解：主存页面调入、代替和命中的情况及3种页面代替算法的页命中率以下表：页地址P2P3P2P1P5P2P4P5P3P2P5P2命中率流FIFO2222*5555*3333中33333*22222*550.25111*44444*2入入中入换换换中换中换换LFU22222222*3333中5333*555555550.42111*444*222入入中入换中换中换换中中OPT222222*444*222中6333333333330.51*55555555入入中入换中换中中换中中3.9一个程序由5个虚页组成，采用LFU代替算法，在程序执行过程中依次接见的页地址流以下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P31）可能的最高页命中率是多少？2）最少要分配给该程序多少个主存页面才能获得最高的命中率？（3）若是在程序执行过程中每接见一个页面，平均要对该页面内的储藏单元接见次，求接见储藏单元的命中率。【参照答案】

1024解：（1）若分配给该程序5个页面，即程序全部装入主存，则可获得最高页命中率。需调入5次，命中7次，最高命中率为7/12≈0.58（2）最少分配4页可获得最高命中率，过程以下：P4P5P3P2P5P1P3P2P3P5P1P344444*1111111555555555553333333333命中7次222222222入入入入中换中中中中中中页地址流P4P5P3P2P5P1P3P2P2P5P1P3命中率堆S(1)453251322513栈S(2)45325133251内S(3)4532511325容S(4)443255132S(5)4444444n=1中中1n=2中1/12实n=3中中中2页2/12数n=4中中中中中中中中7n=5中中中中中中中7/123）命中率=7*1024/（7*1024+5）≈0.99933.10有一个Cache储藏器，主存共分8个块（B0~B7），Cache为4个块（C0~C3），采用组相联映像，组内块数2块，代替算法为LFU。在程序执行过程中依次接见主存的块地址流以下：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B31）写出主存地址格式，并标出各字段长度。2）写出Cache地址格式，并标出各字段长度。3）画出主存与Cache之间各个块的映像对应关系。（4）列出程序执行过程中Cache的块地址流情况。5）若用FIFO代替算法，计算Cache的块命中率。6）若用LFU代替算法，计算Cache的块命中率。（7）若改用全相联映像方式，再做（5）和（6），能够得出什么结论？（8）若在程序执行过程中，每从主存装入一块到Cache，则平均要对这个块接见16次，请计算在这种情况下的Cache命中率。【参照答案】解：（1）主存地址的格式（7位）区号（1位）组号（1位）组内块号（1位）块内地点（4位）（2）Cache地址的格式（6位）组号（1位）组内块号（1位）块内地点（4位）（3）主存与Cache之间各个块的映像对应关系B0B1B2C0B3C1B4C2B5C3B6CacheOPT法）B7（4）Cache块地址流（按C2，C3，C0，C1，C0，C2，C3，C1，C0，C1，C2，C3B6B2B4B1B4B6B3B0B4主存B7B3OPT法B5C2C3C0C1C0C2C3C1C0C1C2C3命中4次入入入入中中换换中换换中命中率0.3335）FIFO法B6B2B4B1B4B6B3B0B4B5B7B3FIFO法C2C3C0C1C0C2C2C0C1C0C3C2命中3次入入入入中中换换换换换中命中率0.256）LFU法B6B2B4B1B4B6B3B0B4B5B7B3LFU法C2C3C0C1C0C2C2C1C0C1C3C2命中4次入入入入中中换换中换换中命中率0.3337）全相联映像，重做（5）和（6）重做（5）B6B2B4B1B4B6B3B0B4B5B7B3FIFO法C0C1C2C3C2C0C0C1C2C2C3C0命中4次入入入入中中换换中换换中命中率0.333重做（6）B6B2B4B1B4B6B3B0B4B5B7B3LFU法C0C1C2C3C2C0C1C3C2C0C1C3命中3次入入入入中中换换中换换换命中率0.258）命中4次时，装入有8次，命中率为15*8+4/(16*8+4)=0.939=93.9%命中3次时，装入有9次，命中率为15*9+3/(16*9+3)=0.938=93.8%3.11有一个Cache储藏器，主存共分8个块（B0~B7），Cache为4个块（C0~C3），采用组相联映像，组内块数2块，代替算法为LRU。