作业答案-华东理工大学计算机科学与工程系VIP免费

作业（1）习题2.6(P75)根据2.3.1节有关SP2的介绍，试回答：①SP设计者为了赶上市场作了什么决策？②SP设计者为了达到系统通用采用了什么相应的技术？③SP系统是如何支持4种SSI的：单一进入点、单一文件层次、单一控制点和单一作业管理系统？④SP设计者为了增加带宽，在通信子系统中主要使用了什么技术？答案：IBMSp2系统主要包含一下的一些特性：①为了赶上市场，遵循Moore定律，采用灵活的机群结构；②为了达到系统通用采用了标准的系统环境和标准的编程模式；③采用部分的单一系统映象支持4种SSI。④为了增加带宽，在通信子系统主要实现了同时连接以太网和高性能开关网。习题3.4(P99)综合比较等效率、等速度和平均延迟可扩放性度量标准之间的异同性。答案：三种度量可扩放性的标准是相互等效的。三种度量方法的基本出发点都是抓住了影响算法可扩放性的基本参数To,只是等效率标准采用解析计算的方法得到To；等速度标准将To隐含在所测量的执行时间中；而平均延迟标准则是保持效率为恒值时，通过调节W与p来测量并行与串行执行时间，最终通过平均延迟反映出To，所以等速度与平均延迟标准都是辅之以测试手段而得到有关性能参数来评判可扩放性的；而等效率标准则是通过解析计算开销参数To来评判可扩放性的。习题3.6(P99)使用40MHZ主频的标量处理器执行一个典型测试程序，其所执行的指令数及所需的周期数如表所示。试计算执行该程序的有效CPI、MIPS。指令类型指令数时钟周期数整数算术45,0001数据传送32,0002浮点15,0002控制转移8,0002答案：机器的时钟周期为τ，程序中指令总条数为IC，执行每条指令所需的平均时钟周期数为CPI，则一个程序在CPU上运行的时间T为：T=IC×CPI×τ=C×τCPI=C/ICC=(45000+32000*2+15000*2+8000*2)=155000CPI=1.55MIPS(MillionInstructionsPerSecond)MIPS=Ic/（T×106）=f/（CPI×106）=(40×106）/(1.55×106)≈25.8作业（2）习题5.3P136页给定序列(33,21,13,54,82,33,40,72)和8个处理器，试按照下述算法构造一个在PRAM-CRCW模型上执行的快排序所用的二叉树。（包括root值，Lc和Rc值，最后用处理器号表示的树）输入：A[1..n]和n个处理器，并且A[i]保存在Pi的LM中输出：二叉排序树root,Lc[1..n],Rc[1..n]在SM中Begin(1)foreachPipar-do(1.1)root=i(1.2)fi=root(1.3)Lci=Rci=n+1endfor(2)repeatforeachPi,i<>rootpar-doif(Ai1then//该结点为其父结点的左儿子C[h,j]=C[h+1,(j-1)/2]*B[h,j]endifendforendforend答案：①W(n)=3n②初始化将A[j]值赋给相应的B[0,j]；正向遍历过程如下：反向遍历的过程如下：以上只是给出了一种情况，如果数据改变了，也要会做。习题7.2P176页略习题7.5P176页略作业（3）略