作业答案-华东理工大学计算机科学与工程系.docx

作业（1）
习题2.6 (P75)
根据2.3.1节有关SP2的介绍，试回答：
① SP设计者为了赶上市场作了什么决策？
② SP设计者为了达到系统通用采用了什么相应的技术？
③ SP系统是如何支持4种SSI的：单一进入点、单一文件层次、单一控制点和单一作业管理系统？
④ SP设计者为了增加带宽，在通信子系统中主要使用了什么技术？
答案：IBM Sp2系统主要包含一下的一些特性：
① 为了赶上市场，遵循Moore定律，采用灵活的机群结构；
② 为了达到系统通用采用了标准的系统环境和标准的编程模式；
③ 采用部分的单一系统映象支持4种SSI。
④ 为了增加带宽，在通信子系统主要实现了同时连接以太网和高性能开关网。
习题3.4 (P99)
综合比较等效率、等速度和平均延迟可扩放性度量标准之间的异同性。
答案：三种度量可扩放性的标准是相互等效的。三种度量方法的基本出发点都是抓住了影响算法可扩放性的基本参数To,只是等效率标准采用解析计算的方法得到To；等速度标准将To隐含在所测量的执行时间中；而平均延迟标准则是保持效率为恒值时，通过调节W与p来测量并行与串行执行时间，最终通过平均延迟反映出To，所以等速度与平均延迟标准都是辅之以测试手段而得到有关性能参数来评判可扩放性的；而等效率标准则是通过解析计算开销参数To来评判可扩放性的。
习题3.6 (P99)
使用40MHZ主频的标量处理器执行一个典型测试程序，其所执行的指令数及所需的周期数如表所示。试计算执行该程序的有效CPI、MIPS。
指令类型
指令数
时钟周期数
整数算术
45,000
1
数据传送
32,000
2
浮 点
15,000
2
控制转移
8,000
2

答案：机器的时钟周期为τ ，程序中指令总条数为IC，执行每条指令所需的平均时钟周期数为CPI，则一个程序在CPU上运行的时间 T为：
T =IC×CPI×τ = C×τ

CPI = C/IC
C= (45 000+32 000*2+15 000*2+8 000*2) = 155 000
CPI =1.55
MIPS( Million Instructions Per Second)
MIPS = Ic / （T×106）= f / （CPI×106 ）
= (40×106 ）/(1.55×106)
≈ 25.8

作业（2）
习题5.3 P136页
给定序列(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)for each Pi par-do
(1.1) root=i
(1.2) fi=root
(1.3) Lci=Rci=n+1
end for
(2)repeat for each Pi, i<>root par-do
if (Ai< Afi) or (Ai= Afi and i<fi) then
(2.1)Lcfi=i
(2.2)if i=Lcfi then exit else fi= Lcfi end if
else
(2.3)Rcfi=i
(2.4)if i=Rcfi then exit else fi= Rcfi end if
end if
end repeat
End
答案：以下给出一种正确答案：
排序过程的数据分布如下
(a) 初始数据
处理器编号
1
2
3
4
5
6
7
8
对应的A[i]
33
21
13
54
82
33
40
72
(b) 执行完算法中的(1) 循环
root = 6
(c) 执行完一次(2)循环
处理器编号
1
2
3
4
5
6
7
8
对应的Lc [i]

1

对应的Rc [i]

8

(d) 再执行完一次(2)循环
处理器编号
1
2
3
4
5
6
7
8
对应的Lc [i]
3

1

7
对应的Rc [i]

8

5
(e) 再执行完一次(2)循环
处理器编号
1
2
3
4
5
6
7
8
对应的Lc [i]
3

1
4
7
对应的Rc [i]

2

8

5

所构造出的用处理器号表示的二叉树如图所示：

以上只是给出了一种情况，如果数据改变了，也要会做。
习题6.3 P158页
PRAM上对数划分算法描述如6.3所示。
① 试分析上述算法的时间复杂度。
答案：常数级，O(1)
习题6.6 P158页
①试分析算法6.9的总运算量
②假定序列为(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)for j=1 to n par-do //初始化
B[0,j]=A[j]
end if
(2)for h=1 to logn do //正向遍历
for j=1 to n/2h par-do
B[h,j]=B[h-1,2j-1]*B[h-1,2j]
end for
end for
(3)for h=logn to 0 do //反向遍历
for j=1 to n/2h par-do
(i) if j=even then //该结点为其父结点的右儿子
C[h,j]=C[h+1,j/2]
end if
(ii) if j=1 then //该结点为最左结点
C[h,1]=B[h,1]
end if
(iii) if j=odd>1 then //该结点为其父结点的左儿子
C[h,j]=C[h+1,(j-1)/2]*B[h,j]
end if
end for
end for
end
答案：①
②初始化将A[j]值赋给相应的B[0,j]；
正向遍历过程如下：

反向遍历的过程如下：

以上只是给出了一种情况，如果数据改变了，也要会做。
习题7.2 P176页
略
习题7.5 P176页
略

作业（3）
略