计算机系统结构参考答案

计算机系统结构习题解答112已知SE20,求作FESN关系曲线。将SE代入AMDAHL定律得ENFS2019115已知两种方法可使性能得到相同的提高，问哪一种方法更好。1用硬件组方法，已知SE40，FE07，解出SN40/12731496（两种方法得到的相同性能）2用软件组方法，已知SE20，SN40/127，解出FE273/3807184（第二种方法的百分比）3结论软件组方法更好。因为硬件组需要将SE再提高100（2040），而软件组只需将FE再提高184（0707184）。119由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。4150IIIC1415108215320451IIIIPI286066CIFMIS3（秒）374516PT23（忽略P124倒1行P125第8行文字，以简化题意）已知2种浮点数，求性能指标。13章作业评阅说明1作业应按时完成。缺大题的作业暂不签字，也不记分，退回补做；2解题要有主要过程，不能只写最终答数。含作图内容的题目，图占1/2的分值。作图形式应模仿教材中的例题，不能随意画（比如319题4问的实存状况图必须标示出应有的“”号）；3凡是计算题，得数应该是一个具体的数字，而不能只列一个算式；4今后的作业都要注意格式规范，考试更是如此。SN20101FE此题关键是分析阶码、尾数各自的最大值、最小值。原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要求。由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可用“最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“最小绝对值”回答。第1小问中，阶码全部位数为8，作无符号数看待真值为0255，作移127码看待真值为127128；尾数（不计符号位）有23位小数，另加1位整数隐藏位，所以尾数绝对值为1020223，有效位数P24；第2小问中，阶码全部位数为11，作无符号数看待真值为02047，作移1023码看待真值为10231024；尾数（不计符号位）有52位小数，另加1位整数隐藏位，所以尾数绝对值为1020252，有效位数P53。最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的组合。代入相关公式后得最终结果如下表。注如果修改题目，将1、2小问的尾数规定为纯小数（即1位隐藏位是小数点后第1位），则尾数真值降为原值的1/2，全部结果改为下表。213已知10条指令使用频度，求3种编码方法的平均码长与信息冗余量。1此问中的“最优HUFFMAN编码法”实际是指码长下限，即信源的平均信息量熵，代公式得H29566。2HUFFMAN编码性能如下表；32/8扩展编码是8/64/512法的变种，第一组2条指令，码长为2（1位扩展标志，1位编码）,第二组8条指令，码长为4（1位扩展标志，与第一组区别，加3位编码），编码性能如下表；43/7扩展编码是15/15/15法的变种，第一组3条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志）,第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表。33直接代公式计算存储层次性能指标。174NS，38NS，236NS20258，0315，0424（单位美元/K字节，换算成美元/字节还要除以1024）3T64KT128KT256KC64KC128KC256K32位64位最大绝对值12242129125321025最小绝对值212721023表数精度224253表数效率10010032位64位最大绝对值12242128125321024最小绝对值212821024表数精度224253表数效率100100HUFFMAN编码2/8扩展编码3/7扩展编码平均码长L2993132信息冗余量R110461759419092，1197，100064。答256K方案最优。319中3468问34通过作“实存状况图”模拟各虚块的调度情况，可获得CACHE的块地址流序列。此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“”号也容易导致淘汰对象错误。6H4/12338做法同315题3问，HCELL12168/121695845已知中断服务次序为32411中断屏蔽字表如下图；2中断过程示意图如右图。481F2105字节/秒，T5S2TSTD5S，通道时间图如下。作图时注意至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。虚存实页0123虚组0001实存1虚组120实组0231虚3虚组242实组1页4535虚组36677A虚页集合与实页集合的对应关系B对应关系表（为有关系）P624146304573C04444444444C1111100555C2666666666677C322222333333入入入入中中替替中替替中C230102310123时间中断请求主程序1级2级3级4级D1，D2D3，D4D1D2D3D4D10111D20010D30000D4011035，未处理D2第一次服务请求（即“无”。答160也可），20，404D2丢失第一次请求的数据；5增加通道的最大流量，动态改变设备的优先级，增加一定数量的数据缓冲器（教材P245）。59为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号16）再执行加法（任务编号711），其次在加法中采用“最少相关算法”（即二叉树算法）。右图A是计算顺序二叉树，其中任务16是乘法，任务711是加法。注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。右图B是时空图，由它得TP11/22T1/2TS64T54T/22T2E64T54T/622T1/3515T10NS108秒1F1，2，5，C100112状态转移图如下图A所示。3最小启动循环（3）,最小平均启动距离3T。4插入2个延迟，最小启动循环（2）,最小平均启动距离2T。5新预约表如下图B所示。6F1，3，7，C1000101，状态转移图如下图C所示。设优备先号级D11D24D32D43时间S0102030405060708090100110120130140150160170FA1B1A1B1A1B1A1B1A1B1A6B61234567891011A计算顺序二叉树65432101234567891214151822B时空图11112222333344445555666677778888999910101010111111117插入前TPMAX1/3T1/30NS，插入后TPMAX1/2T1/20NS。8插入前TP10/33T1/33NS，插入后TP10/26T1/26NS，如下图所示。12345678初态4，6，8S112初态3，4，6S211000101S34，6，84，6，810011S4125D110101011000111D225ABCS4S3S2S13TA插入前936D2D1S4S3S2S12TB插入后9281111111222222233333331010101010101011111111122222222210101010101010101066（注意阅读P372倒数第9行倒数第6行）已知N32，K加6，K乘7，K访存6，K倒数14，启动、输出延迟各1。求各小题总拍数。3V0存储器V3V1V2V4V0V3V6V4V5访存加乘8931831总拍数87（第4条功能部件冲突）4V0存储器V11/V0V3V1V2V5V3V4访存倒数加乘8168931总拍数72（各条依次链接）并行链接串行链接链接链接5V0存储器V1V2V3V4V5V6S0S1S2访存加乘9318总拍数48（标量看成1个分量的向量）6V3存储器V2V0V1S0S2S3V3V1V4访存加乘831931总拍数79（标量看成1个分量的向量）并行串行并行串行并行1V0存储器V1V2V3并行V4V5V6访存加乘931总拍数40（并行执行，以最长指令为准）2V2V0V1V3存储器V4V2V3乘访存加931831总拍数79（第3条错过时机，不能链接）并行串行（参见P372）73已知输入端编号131101B。1CUBE31101B0101B52PM23131323MOD1621MOD1653PM20131320MOD16124SHUFFLE1101B1011B115SHUFFLESHUFFLE1101BSHUFFLE1011B0111B7710用混洗交换网络模拟CUBE网。当模拟CUBE0功能时，只需一次交换即可完成；而模拟CUBEI且I0时，需先作NI步混洗，再作1步交换，最后作I步混洗才能完成，共计N1步。综上所述，下限为1步，上限为N1步。72613；1见下图实线。2见下图虚线；不会阻塞，因为两条路径的控制信号都是1110，形成级控模式，所以不会阻塞。3一次通过实现的置换数为1684294967296，全部置换数为N20922789888000，前者约占后者的002。7V3存储器V2V0V1V4V2V3存储器V4访存加乘8931831总拍数87（第4条功能部件冲突）8V0存储器V2V0V1V3V2V1V5V3V4访存加乘8831931931总拍数127（VI冲突，功能部件冲突）并行链接串行链接串行串行7273求作超立方体贪心选播树源结点编号的二进制形式1010在CUBE0CUBE3位分别与7、6、5、6个目的结点的二进制形式不同，所以总时间4（如某一位没有与源结点不同的目的结点，则该维不发送，总时间减少1），并且CUBE0方向应该最先发送，CUBE2方向最后发送，其它2个方向的发送先后顺序没有限制。我们可以采用CUBE0、CUBE1、CUBE3、CUBE2的发送顺序，生成的选播树如下图所示，总流量11。812问题为SA1B1A32B32，其中T乘4T，T加2T，T传1T。1在串行计算机上，各操作不论是否相关均不能重叠，总时间恒等于各操作单独时间之和，所以不必考虑运算顺序。T32T乘31T加324312T190T2设此双向环可以并行传送（即为“移数环”，因为SIMD系统各种数据操作都能并行）。按平均分配原则，每个结点内有4对数据。首先在各结点用串行算法它们的相乘与求和，需时T14T乘3T加4432T22T；然后用二叉树并行算法将8个结点中的部分和相加（见下图），其中并行加法需3次，每次级3级2级1级0000000000001000100100010001100110100010001010101011001100111011110001000100110011010101010111011110011001101110111101110111111111010CUBE010101011CUBE11010100010111001CUBE310100010100000001011001110010001CUBE210101110001001101000110000000100101111110011011110011101000101011014268120411153791315超立方体贪心选播树时间相同，而并行传送3次的每次时间却随距离倍增，依次为1、2、4步，所以有T2124T传3T加7132T13T；总时间TT1T235T96解法1设处理机甲执行一个任务的时间为R，则处理机乙执行一个任务的时间为2R。仍记C为一个任务与异机任务的通信时间，K为处理机甲分得的任务数。参考公式91得，总时间TRMAX2MK,KCMKK由于是MAX函数的转折点，所以T也可写成分段函数M32MKCKRT32当，当图形如下由于二次函数的上凸性，T的最小点只可能位于或KM二者之一。为求临界条件，32令T|K2/3MT|KM，得，解出。RMCR3232C32SS1S2S3S4S5S6S7S8右传20步加法1步右传21步加法1步右传22步加法1步TT2MR2MRMRMR02/3MMK02/3MMKA当时，KM处最低B当时，K2/3M处最低CR32CR结论当时，最佳分配参数；MCR32MK当时，最佳分配参数。32解法2设处理机乙执行一个任务的时间为R，则处理机甲执行一个任务的时间为R/2。仍记C为一个任务与异机任务的通信时间，K为处理机甲分得的任务数。参考公式91得，总时间TRMAXMK,K/2CMKK由于是MAX函数的转折点，所以T也可写成分段函数M3MKCKRT322/当，当，图形如下由于二次函数的上凸性，T的最小点只可能位于或KM二者之一。为求临界条件，32令T|K2/3MT|KM，得，解出。2/3231RMCRC34结论当时，最佳分配参数；MC4K当时，最佳分配参数。R332918问题为SA1B1A8B8，其中T加30NS，T乘50NS，T传10NS。将加法记为任务18，乘法记为任务915。TTMRMRMR/2MR/202/3MMK02/3MMKA当时，KM处最低B当时，K2/3M处最低CR34CR41在串行计算机上，同812题1问分析，共计15步运算，T8T加7T乘830750NS590NS。2多功能部件SISD计算机的工作方式可参考P346题183。为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运算（见下图）。T2T加7T乘230750NS410NS3同812题2问，设单向环可以并行传送（即为“移数环”，理由同812题2问）。TT加3T乘124T传30350710NS250NS算法改进将8对数据的加法由8个结点同时完成（共30NS）改成4个结点分两批完成（共60NS），这样要多花30NS；但由于结果在4个结点中，其后的累乘就只需要做2次传输，距离分别是1步、2步，省去了原来最费时间的第3次传输（410NS40NS），收支相抵之后还省下