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

名词解释 请给出下列缩写的全称,并加以解释。 MPP、PCAM、 APRAM 2.请简要解释下列术语的含义。 共享变量模型、NUMA、加速比、logP 二、问答题 1.现在市场上常见的双CPU的计算机采用的是什么结构?简述该结构的特性。 2.何谓高速缓存一致性问题?请简述一致性维护的基本策略。 3.请简述并举例说明 Amdahl定律 4.请问如何将一个MPMD程序改写为SPMD程序? 、综合题 1.阅读以下题为“占据半壁江山IBM继续统治超级计算机排行榜”大众新闻报道,回 答问题 根据超级计算机500强组织最近发布的调查报告,IBM继续在超级计算机领域处于绝对的统 治地位。此调査每半年进行一次,这是自1993年以来的第26次调查。 目前,世界上500台最强悍的超级计算机中有219台属于IBM,其中前三名更是全部出自IBM 之手。位列第二的HP拥有169台。位列榜首的依旧是大名鼎鼎的蓝色基因一— Blue Gene/L,运 算速度为每秒280.6万亿次浮点运算。这一速度不久前刚刚刷新了世界记录。这台超级计算机是 为美国国家核安全局打造的,主要用于模拟核试验。紧随其后的也是蓝色基因,不过是IBM自 己的 Watson Blue Gene(WBG)系统,运算速度为每秒91.29万亿次浮点运算。第三名是位于劳伦 斯-利沃莫尔国家实验室的 ASC Purple,运算速度为每秒63.39万亿次浮点运算。IBM这219台超 级计算机的总运算速度为每秒1.214千万亿次浮点运算,占500强总运算能力的53%,远远甩开 了竞争对手。这是第一次一家公司的总速度突破千万亿次大关。 IBM将自己成功的原因归结于富有弹性的操作平台和强大的 Power处理器等因素,其中蓝色 基因使用的就是 Power处理器。 (1)请问文中提到的“排行榜”是按照什么方法对高性能计算机进行排序的?这种方法 具有什么样的优点和不足? (2)结合文中提到的髙性能计算的应用,谈谈为什么中国需要自行硏制高性能计算机, 并请举出两种国产系列高性能计算机品牌 (3)结合课程所学知识,请对文中“IBM将自己成功的原因归结于富有弹性的操作平 台和强大的 Power处理器等因素”进行分析评论。 2.假定A4和B4已加载到如下所示的4×4处理器阵列上,试用图表示 Cannon矩阵乘 法的具体过程

- 1 - 一、 名词解释 1． 请给出下列缩写的全称，并加以解释。 MPP、PCAM、APRAM 2．请简要解释下列术语的含义。 共享变量模型、NUMA、加速比、logP 二、 问答题 1．现在市场上常见的双 CPU 的计算机采用的是什么结构？简述该结构的特性。 2．何谓高速缓存一致性问题？请简述一致性维护的基本策略。 3．请简述并举例说明 Amdahl 定律。 4．请问如何将一个 MPMD 程序改写为 SPMD 程序？ 三、 综合题 1．阅读以下题为“占据半壁江山 IBM 继续统治超级计算机排行榜”大众新闻报道，回 答问题。 根据超级计算机 500 强组织最近发布的调查报告，IBM 继续在超级计算机领域处于绝对的统 治地位。此调查每半年进行一次，这是自 1993 年以来的第 26 次调查。 目前，世界上500台最强悍的超级计算机中有219台属于IBM，其中前三名更是全部出自IBM 之手。位列第二的 HP 拥有 169 台。位列榜首的依旧是大名鼎鼎的蓝色基因——Blue Gene/L，运 算速度为每秒 280.6 万亿次浮点运算。这一速度不久前刚刚刷新了世界记录。这台超级计算机是 为美国国家核安全局打造的，主要用于模拟核试验。紧随其后的也是蓝色基因，不过是 IBM 自 己的 Watson Blue Gene(WBG)系统，运算速度为每秒 91.29 万亿次浮点运算。第三名是位于劳伦 斯-利沃莫尔国家实验室的 ASC Purple，运算速度为每秒 63.39 万亿次浮点运算。IBM 这 219 台超 级计算机的总运算速度为每秒 1.214 千万亿次浮点运算，占 500 强总运算能力的 53％，远远甩开 了竞争对手。这是第一次一家公司的总速度突破千万亿次大关。 IBM 将自己成功的原因归结于富有弹性的操作平台和强大的 Power 处理器等因素，其中蓝色 基因使用的就是 Power 处理器。 （1）请问文中提到的“排行榜”是按照什么方法对高性能计算机进行排序的？这种方法 具有什么样的优点和不足？ （2）结合文中提到的高性能计算的应用，谈谈为什么中国需要自行研制高性能计算机， 并请举出两种国产系列高性能计算机品牌。 （3）结合课程所学知识，请对文中 “IBM 将自己成功的原因归结于富有弹性的操作平 台和强大的 Power 处理器等因素”进行分析评论。 2．假定 A44 和 B44 已加载到如下所示的 4 4 处理器阵列上，试用图表示 Cannon 矩阵乘 法的具体过程

A Ao.A A B,o Bo, 1 Bo. 2 B A1.o A1. A1.2A B B.1B12B1,3 A A2. 2A2 B20B21B22B2.3 A.。Aa.1A32|A3.3 B30B31B32B3.3 3.MMD机器上PSRS排序算法描述如下: 输入:长度为n的无序序列,P台处理器,每台处理器有m/p个元素 输出:长度为n的有序序列 n (1)均匀划分:n个元素均匀地划分成p段,每台处理器有m个元素。 (2)局部排序:各个处理器利用串行排序算法,排序m个数。 (3)选择样本:每台处理器各从自己的有序段中选取p个样本元素 (4)样本排序:用一台处理器将所有p2个样本元素用串行排序算法排序之 (5)选择主元:用一台处理器选取p-1个主元,并将其播送给其余处理器。 (6)主元划分:各处理器按主元将各自的有序段划分成p段 (7)全局交换:各处理器将其辖段按段号交换到相应的处理器。 (8)归并排序:处理器使用归并排序将所接收的诸段施行排序 ①试证明:当n≥p3时,上述算法的时间复杂度为O("1ogn) 令w表示P中第j段中的元素数,试证明上述算法在执行过程中,处理器中所积累 的元素数目不会超过2n/p,即∑v< 4.PRAM上对数划分算法描述如下: 输入:两非降有序序列A=(a12…,an),B=(b1…,bn),假定ogm和k(m)=m/kogm均为整数 输出:将A和B划分成(m)对段组(A,B),使得|B=lgm,∑|4|=n,且对于所 有1≤i≤k(m)-1,A和B中的每一个i元素均大于41和B中的每一个元素 (1)f(O)=0;j(k(m)=n

- 2 - 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 A A A A B B B B A A A A B B B B A A A A B B B B A A A A B B B B 3．MIMD 机器上 PSRS 排序算法描述如下： 输入：长度为 n 的无序序列，p 台处理器，每台处理器有 n p 个元素 输出：长度为 n 的有序序列 Begin （1） 均匀划分：n 个元素均匀地划分成 p 段，每台处理器有 n/p 个元素。 （2） 局部排序：各个处理器利用串行排序算法，排序 n/p 个数。 （3） 选择样本：每台处理器各从自己的有序段中选取 p 个样本元素。 （4） 样本排序：用一台处理器将所有 p 2 个样本元素用串行排序算法排序之。 （5） 选择主元：用一台处理器选取 p-1 个主元，并将其播送给其余处理器。 （6） 主元划分：各处理器按主元将各自的有序段划分成 p 段。 （7） 全局交换：各处理器将其辖段按段号交换到相应的处理器。 （8） 归并排序：处理器使用归并排序将所接收的诸段施行排序。 End ① 试证明：当 3 n p  时，上述算法的时间复杂度为 ( log ) n O n p 。 ② 令 j wi 表示 Pi 中第 j 段中的元素数，试证明上述算法在执行过程中，处理器中所积累 的元素数目不会超过 2 / n p ，即 1 2 p j i j n w = p   。 4．PRAM 上对数划分算法描述如下： 输入：两非降有序序列 ( ,..., ) A = a1 an , ( ,..., ) B = b1 bn ,假定 log m 和 k(m) = m log m 均为整数 输出：将 A 和 B 划分成 k(m) 对段组 ( , ) Ai Bi ，使得 | Bi |= log m，| Ai | = n ，且对于所 有 1  i  k(m) −1， Ai 和 Bi 中的每一个 i 元素均大于 Ai−1 和 Bi−1 中的每一个元素 Begin （1） j(0) = 0 ； j(k(m)) = n

(2)for i=l to k(m)-1 par-do (2.1)求rank(bogm:A) (2.2) j(i)=rank(blog A) end for (3)for i=0 to k(m)-1 par-do (3.1)B=(bm4…b (3.2)A=(a End ①试分析上述算法的时间复杂度。 令A=(0,1,2,7,9,116,17,18,19,23,24,25,27,28,30,33,34) B=(3,4,5,6,8,10,12,13,14,15,20,21,22,26,29,31)。 按上述算法,将其进行对数划分,并最终将它们归并

- 3 - （2） for i =1 to k(m) −1 par-do （2.1）求 ( : ) rank bilogm A （2.2） ( ) ( : ) j i = rank bilogm A end for （3） for i = 0 to k(m) −1 par-do （3.1） ( ,..., ) Bi = bilogm+1 b(i+1)logm （3.2） ( ,..., ) Ai = a j(i)+1 a j(i+1) end for End ① 试分析上述算法的时间复杂度。 ② 令 A = (0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34) B = (3,4,5,6,8,10,12,13,14,15,20,21,22,26,29,31) 。 按上述算法，将其进行对数划分，并最终将它们归并