搜索
作业（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,irootpar-doif(AiAfi)or(Ai=Afiandifi)then(2.1)Lcfi=i(2.2)ifi=Lcfithenexitelsefi=Lcfiendifelse(2.3)Rcfi=i(2.4)ifi=Rcfithenexitelsefi=RcfiendifendifendrepeatEnd答案：以下给出一种正确答案：排序过程的数据分布如下(a)初始数据处理器编号12345678对应的A[i]3321135482334072(b)执行完算法中的(1)循环root=6(c)执行完一次(2)循环处理器编号12345678对应的Lc[i]1对应的Rc[i]8(d)再执行完一次(2)循环处理器编号12345678对应的Lc[i]317对应的Rc[i]85(e)再执行完一次(2)循环处理器编号12345678对应的Lc[i]3147对应的Rc[i]285所构造出的用处理器号表示的二叉树如图所示：[6]{33}1,2,34,5,7,8[1]{33}2,3[3]{13}2[8]{72}4,75[7]{40}4[2]{21}[4]{54}[5]{82}以上只是给出了一种情况，如果数据改变了，也要会做。习题6.3P158页PRAM上对数划分算法描述如6.3所示。①试分析上述算法的时间复杂度。答案：常数级，O(1)习题6.6P158页①试分析算法6.9的总运算量?nW②假定序列为(1，2，3，4，5，6，7，8)，试用算法6.9求其前缀和。算法6.9前缀和：n个元素{x1,x2,…,xn}，前缀和是n个部分和，这里Si=x1＋x2…＋xi,1≤i≤n求解前缀和算法:输入：n=2k的数组A,k为非负整数输出：数组C，其中C(0,j)是第j和前缀和(1≤j≤n)begin(1)forj=1tonpar-do//初始化B[0,j]=A[j]endif(2)forh=1tologndo//正向遍历forj=1ton/2hpar-doB[h,j]=B[h-1,2j-1]*B[h-1,2j]endforendfor(3)forh=lognto0do//反向遍历forj=1ton/2hpar-do(i)ifj=eventhen//该结点为其父结点的右儿子C[h,j]=C[h+1,j/2]endif(ii)ifj=1then//该结点为最左结点C[h,1]=B[h,1]endif(iii)ifj=odd1then//该结点为其父结点的左儿子C[h,j]=C[h+1,(j-1)/2]*B[h,j]endifendforendforend答案：①nnW3②初始化将A[j]值赋给相应的B[0,j]；正向遍历过程如下：B[0,1]=1B[0,2]=2B[0,3]=3B[0,4]=4B[0,5]=5B[0,6]=6B[0,7]=7B[0,8]=8B[1,1]=3B[1,2]=7B[2,1]=10B[1,3]=11B[1,4]=15B[2,2]=26B[3,1]=36反向遍历的过程如下：C[0,1]=1C[0,2]=3C[0,3]=6C[0,4]=10C[0,5]=15C[0,6]=21C[0,7]=28C[0,8]=36C[1,1]=3C[1,2]=10C[2,1]=10C[1,3]=21C[1,4]=36C[2,2]=36C[3,1]=36以上只是给出了一种情况，如果数据改变了，也要会做。习题7.2P176页略习题7.5P176页略作业（3）略