并行分布式试卷1
姓名____________________
学号____________________ 分数_____________
1．填空（每空1分，共30分）
1．在并行机系统中，常用的静态互联网络有__ ___________，__ _____________，_
_____________________，______________________，___________________等。
2．在并行机系统中，常用的动态互联网络有___________________________________，
_____________________________________和______________________________。
3．近代并行计算机体系结构模型包括_______ _________，___________________，_
______________________，____________ ______，_____________________等。
4．常用的并行存储访问模型（又叫并行存储结构）包括_______________________，
________________________________，_____________________________等。
5．常用的并行程序设计模型有____________ _______，__ _ _______________，___
_________________________等。
6．大型稀疏线性方程常用迭代解法有____________________，_ _________________，
_________________________，__________________________等。
7．常用的并行计算（或算法）模型有___________________，___ ________________
_，________________________，______________________等。
8．我国自行研制的并行计算机三大系列是___________________________，________
_____________________，_____________________________。
2．简要回答（每题5分，共20分）
1．试述并行算法基本的设计技术。
2．何谓X-Y 选路算法何E-cube 选路算法（可以例明之）?3．何谓Amdahle 和Gustfson 加速定律及其推导过程？
4．何谓等效率、等速度和平均延迟可扩放性度量标准？并推导他们之间的等效性。
三．综合题（每题10分，共50分）
1．假定44⨯A 和44⨯B 都已加载到44⨯处理器阵列上，试图示Cannon 矩阵乘法的具体
过程。
2．已知⎥⎦⎤⎢⎣⎡=4331A ，⎥⎦
⎤
⎢⎣⎡--=8765B ，试用DNS 方法，逐步求出矩阵乘积
?22211211
=⎥⎦
⎤
⎢
⎣⎡=c c c c C 。
3．欲求解Ax=b ，则构造二次函数b x Ax x x q T T -=2
1
)(，试证明
0)
(=∂∂x
x q 是Ax=b 的解。
4．假定∑-==
1
n k k jk
j a w
b ，10-≤≤n j ，以n=8为例，推导FFT 递归计算公式。
5．参照下图，对于一个8点的蝶式网络，假定：① 相应的处理器p(r, i)中已保存了倍
数矩阵元素),exp(i r w ，70≤≤i ，31≤≤r 。
② 输入序列)0,0,,1,0,1,,2(i i i A -=。
试按下述SIMD-BF 模型上算法，计算出i r d ,和j r d ,之值。
SIMD-BF 模型上的FFT 算法输入：),...,(10-=n a a A 输出：i r d ,和j r d ,Begin
(1)for i=0 to n-1 par-do
i
i a d =,0endfor
(2)for r=1 to n log do
for 所有仅第r 位不同且i 在第r 位为零的每对(i,j) par-do
(2.1) j
r i r i r i r d d d ,1)
,exp(,1,--+=ω
4
6
77
d 30
d 31
d 32
d 33
d 34
d 35
d 36
d 37
r 0
r 1
r 2r 3
(2.2) j
r j r i r j r d d d ,1)
,exp(,1,--+=ωendfor endfor
End
并行分布式试卷2
姓名____________________学号____________________ 分数_____________
1、填空选择题(20分)
1.对于高性能计算的需要是广泛的，比如在__ ___________，__ _________
____，______________________，______________________等领域中应用广泛。
2. 在并行系统中，系统互联网络有___________________________________，
_______________________________和______________________________三类。
3. 近代常见的五种并行计算机体系结构模型包括_______ _________，____
_______________，_______________________，____________ ______，__ ___________________。
4.常用的并行计算模型有____________ _______，__ _ _______________，
____________________________，__ _ ______________等。
5．中国工程院院士金怡濂研究员被授予2002年度国家最高科学技术奖。
由他担任总设计师主持研制的并行计算机系统为 _________ 系列。
A. 曙光 B 神威 C. 银河 D 以上都不对
6．关于加速比，下面的论述不对的是_________
A. 严格的线性加速比是难以达到的；
B. 在某些算法或程序中，可能出现超线性加速现象；
C. 通信密集类的应用问题，加速比往往不是很高
D. 加速比仅由算法决定，与应用问题的规模无关
2、简答题（20分）
1．何谓SMP结构？简述该结构的特性。
2．试推导Gustafson定律。
3．何谓并行计算的可扩放性？有哪三种典型的扩放性度量方法？
4．何谓PRAM模型？简述该模型的优缺点。
5．请举例说明并行算法的三种一般设计方法（策略）。
3、综合题（60分）
1.试画出基于Batcher比较器的双调序列(8，6，4，2，0，1，3，5)的双调归
并排序网络，并在标出每个Batcher比较器的输入和输出数据。
2.使用指针跳跃技术求出下面森林的根，给出求解过程。
9
3.给出环上一到多(one-to-all)的CT 选路算法描述，并在下图中画出选路步骤。
根据单一信包的通讯时间h w s one to one lt mt t CT t ++=--)(，试推导环上的通讯时
间)(CT t all to one --。
4.先写出矩阵乘法n n n n B A ⨯⨯⨯的Fox 算法形式描述，然后分析Fox 算法在p 个处理器组成的超立方上、使用CT 选路的运行时间(注：p -超立方上的p mt t CT t w s all to one log )()(+=-- )。
5.离散富里叶变换∑-==1
0n k kj
k j a b ω，10-≤≤n j 。
对于n =8，试完成下面的蝶式
计算图中的列1到列3的相应标记，并求出b 3和b 6。