中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（试卷）并行分布式试卷（一）

并行分布式试卷1 姓名 分数 填空(每空1分,共30分) 1.在并行机系统中,常用的静态互联网络有 2.在并行机系统中,常用的动态互联网络有 和 3.近代并行计算机体系结构模型包括 等 4.常用的并行存储访问模型(又叫并行存储结构)包括 5.常用的并行程序设计模型有 6.大型稀疏线性方程常用迭代解法有 7.常用的并行计算(或算法)模型有 等 8.我国自行研制的并行计算机三大系列是 二.简要回答(每题5分,共20分) 1.试述并行算法基本的设计技术 2.何谓XY选路算法何E-cube选路算法(可以例明之)? 3.何谓 Amdahl和 Gustfson加速定律及其推导过程? 4.何谓等效率、等速度和平均延迟可扩放性度量标准?并推导他们之间的等效性

1 并行分布式试卷 1 姓名____________________ 学号____________________ 分数_____________ 一． 填空（每空 1 分，共 30 分） 1． 在并行机系统中，常用的静态互联网络有__ ___________，__ _____________， ______________________，______________________，___________________等。 2． 在并行机系统中，常用的动态互联网络有___________________________________， _____________________________________和______________________________。 3． 近代并行计算机体系结构模型包括_______ _________，___________________， _______________________，____________ ______，_____________________等。 4． 常用的并行存储访问模型（又叫并行存储结构）包括_______________________， ________________________________，_____________________________等。 5． 常用的并行程序设计模型有____________ _______，__ _ _______________， ____________________________等。 6． 大型稀疏线性方程常用迭代解法有____________________，_ _________________， _________________________，__________________________等。 7． 常用的并行计算（或算法）模型有___________________，___ _________________， ________________________，______________________等。 8． 我 国 自 行 研 制 的 并 行 计 算 机 三 大 系 列 是 ___________________________ ， _____________________________，_____________________________。 二． 简要回答（每题 5 分，共 20 分） 1． 试述并行算法基本的设计技术。 2． 何谓 X-Y 选路算法何 E-cube 选路算法（可以例明之）? 3． 何谓 Amdahle 和 Gustfson 加速定律及其推导过程？ 4． 何谓等效率、等速度和平均延迟可扩放性度量标准？并推导他们之间的等效性

三.综合题(每题10分,共50分) 1.假定A4×4和B×4都已加载到4×4处理器阵列上,试图示 Cannon矩阵乘法的具体过 程 2.已知A=13 试用DNS方法,逐步求出矩阵乘积 34 78 C 3.欲求解Ax=b,则构造二次函数q(x)=xAx-x2b,试证明(x)20是Ax=b 的解。 4.假定b=∑v/a,0≤j≤n-1,以n8为例,推导Fr递归计算公式 5.参照下图,对于一个8点的蝶式网络,假定:①相应的处理器p(r,1)中已保存了倍 数矩阵元素呷),0≤i≤7,1≤r≤3。②输入序列A=(2,1-i,0,1,i0,0)。 试按下述SIMD-BF模型上算法,计算出d;和d,;之值 SIMD-BF模型上的FFT算法 输入:A=(a0…,an-1) 输出:d,1和d Begin (1) for i=0 to n-1 par-do 2

2 三．综合题（每题 10 分，共 50 分） 1． 假定 A44 和 B44 都已加载到 4  4 处理器阵列上，试图示 Cannon 矩阵乘法的具体过 程。 2． 已知       = 3 4 1 3 A ，      − − = 7 8 5 6 B ，试 用 DNS 方法 ，逐 步求 出矩 阵乘积 ? 21 22 11 12 =      = c c c c C 。 3． 欲求解 Ax=b，则构造二次函数 q x x Ax x b T T = − 2 1 ( ) ，试证明 0 ( ) =   x q x 是 Ax=b 的解。 4． 假定  − = = 1 0 n k k jk bj w a ，0  j  n −1 ，以 n=8 为例，推导 FFT 递归计算公式。 5． 参照下图，对于一个 8 点的蝶式网络，假定：① 相应的处理器 p(r, i)中已保存了倍 数矩阵元素 exp(r,i) w ，0  i  7，1 r  3。② 输入序列 A = (2,i,1− i,0,1,i,0,0) 。 试按下述 SIMD-BF 模型上算法，计算出 r i d , 和 r j d , 之值。 SIMD-BF 模型上的 FFT 算法 输入： ( ,..., ) A = a0 an−1 输出： r i d , 和 r j d , Begin (1) for i=0 to n-1 par-do ω0 ω0 ω0 ω0 ω4 ω4 ω4 ω4 ω0 ω0 ω4 ω4 ω2 ω2 ω6 ω6 ω 0 ω 4 ω 2 ω 6 ω 1 ω 5 ω 3 ω 7 a0 a1 a2 a3 a4 a5 a6 a7 d30 d31 d32 d33 d34 d35 d36 d37 r0 r1 r2 r3

endor (2) for rl to log n de for所有仅第r位不同且i在第r位为零的每对(iJj)par-do (2.1)d=d d (22)d,=d-1+ d endor

3 d0,i = ai endfor (2) for r=1 to log n do for 所有仅第 r 位不同且 i 在第 r 位为零的每对(i,j) par-do (2.1) r j r i dr i dr i d 1, exp( , ) , = −1, + − (2.2) r j r j dr j dr i d 1, exp( , ) , = −1, + − endfor endfor End

并行分布式试卷2 姓名_ 分数 填空选择题(20分) 1.对于高性能计算的需要是广泛的,比如在 等领 域中应用广泛 2.在并行系统中,系统互联网络有 和 类 3.近代常见的五种并行计算机体系结构模型包括 4.常用的并行计算模型有 等 5.中国工程院院士金怡濂研究员被授予2002年度国家最高科学技术奖。由 他担任总设计师主持研制的并行计算机系统为 系列 A.曙光 B神威 C.银河 D以上都不 6.关于加速比,下面的论述不对的是 A.严格的线性加速比是难以达到的 B.在某些算法或程序中,可能出现超线性加速现象 C.通信密集类的应用问题,加速比往往不是很高 D.加速比仅由算法决定,与应用问题的规模无关 二、简答题(20分) 何谓SMP结构?简述该结构的特性 2.试推导 Gustafson定律。 3.何谓并行计算的可扩放性?有哪三种典型的扩放性度量方法? 4.何谓PRAM模型?简述该模型的优缺点。 5.请举例说明并行算法的三种一般设计方法(策略)

4 并行分布式试卷 2 姓名____________________ 学号____________________ 分数_____________ 一、 填空选择题(20 分) 1. 对 于 高 性 能 计 算 的 需 要 是 广 泛 的 ， 比 如 在 __ ___________ ， __ _____________，______________________，______________________等领 域中应用广泛。 2. 在并行系统中，系统互联网络有___________________________________， _______________________________和______________________________三 类。 3. 近代常见的五种并行计算机体系结构模型包括_______ _________， ___________________，_______________________，____________ ______， _____________________。 4. 常 用 的 并 行 计 算 模 型 有 ____________ _______ ， __ _ _______________ ， ____________________________ ， __ _ ______________等。 5．中国工程院院士金怡濂研究员被授予 2002 年度国家最高科学技术奖。由 他担任总设计师主持研制的并行计算机系统为 _________ 系列。 A. 曙光 B 神威 C. 银河 D 以上都不 对 6．关于加速比，下面的论述不对的是_________ A. 严格的线性加速比是难以达到的； B. 在某些算法或程序中，可能出现超线性加速现象； C. 通信密集类的应用问题，加速比往往不是很高 D. 加速比仅由算法决定，与应用问题的规模无关 二、 简答题（20 分） 1．何谓 SMP 结构？简述该结构的特性。 2．试推导 Gustafson 定律。 3．何谓并行计算的可扩放性？有哪三种典型的扩放性度量方法？ 4．何谓 PRAM 模型？简述该模型的优缺点。 5．请举例说明并行算法的三种一般设计方法（策略）

三、综合题(60分) 1.试画出基于 Batcher比较器的双调序列8,6,4,2,0,1,3,5)的双调归并 排序网络,并在标出每个 Batcher比较器的输入和输出数据 2.使用指针跳跃技术求出下面森林的根,给出求解过程。 10 6 3.给出环上一到多(one-to-al的CT选路算法描述,并在下图中画出选路步骤 根据单一信包的通讯时间to(CT)=1n+mn+ln,试推导环上的通讯时 间 t(CT)。 (①(2③ 4.先写出矩阵乘法A-Bmn的Fox算法形式描述,然后分析Fox算法在p个 处理器组成的超立方上、使用CT选路的运行时间(注:p-超立方上的 fone-toall (CT)=(t, +mt e )log p )o 5.离散富里叶变换b=∑a20,0≤j≤n-1。对于n=8,试完成下面的蝶式 计算图中的列1到列3的相应标记,并求出b3和b6 列0 列1 列2

5 三、 综合题（60 分） 1. 试画出基于 Batcher 比较器的双调序列(8，6，4，2，0，1，3，5)的双调归并 排序网络，并在标出每个 Batcher 比较器的输入和输出数据。 2. 使用指针跳跃技术求出下面森林的根，给出求解过程。 3. 给出环上一到多(one-to-all)的 CT 选路算法描述，并在下图中画出选路步骤。 根据单一信包的通讯时间 one to one s w h t CT = t + mt + lt − − ( ) ，试推导环上的通讯时 间 t (CT) one−to−all 。 4. 先写出矩阵乘法 Ann  Bnn 的 Fox 算法形式描述，然后分析 Fox 算法在 p 个 处理器组成的超立方上、使用 CT 选路的运行时间(注：p-超立方上的 t one−to−all(CT) = (t s + mtw )log p )。 5. 离散富里叶变换  − = = 1 0 n k kj bj ak ，0  j  n −1 。对于 n=8，试完成下面的蝶式 计算图中的列 1 到列 3 的相应标记，并求出 b3 和 b6。 7 6 5 4 0 1 2 3 1 2 6 3 4 5 7 8 10 11 12 13 9 a0 a1 a2 a3 a4 a5 a6 a7 列0 列 1 列2 列 3