《并行计算》课程教学资源（讲义）测验习题2

填空题 常用的并行算法设计的基本技术有 2.常见的并行计算模型有 等 3.PCAM设计过程分为 和 四步 4.常见的并行程序设计模型包括 等 问答题 1.请简述从上个世纪80年代至今,主流并行计算机体系结构的变化趋势。 2.基于蝶式计算原理的FFT在二维mesh连接和蝶式网络连接的处理器上均可并行实 现 (1)请问哪种实现效率较好?并给出原因。 (2)蝶式网络连接的处理器在实际的并行计算机系统并不常见,这是否会影响FFT在 蝶式网络连接上的并行实现在实际中的使用?为什么? 3.基本的开关技术有哪两种?各具有什么特点? 阅读题 1.阅读以下新闻报道,回答问题。 2004年6月29日国家科技部今日在人民大会堂宣布:“863计划重点项目一—曙光4000A通 过鉴定验收,曙光4000A实现了对每秒10万亿次运算速度的技术和应用的双跨越,成为国内计算能 力最强的商品化超级计算机”。在今年6月22日刚刚公布的全球高性能计算机TOP500排行榜中,曙 光400A以每秒Ⅱ1万亿次的峰值速度和80610亿次 Linpack计算值位列全球第十,这是中国超级计 算机得到国际同行认可的最好成绩。随着曙光4000A的推出,中国已经成为继美、日之后第三个跨 越了10万亿次计算机研发、应用的国家 曙光4000A拥有自主研制的机群系统软件包括机群管理系统、机群部署系统、机群作业管理系 统、并行文件系统、机群监控系统、机群并行通信系统、机群髙可用系统、机群负载均衡系统等。 (1)请问文中提到的“TOP500排行榜”是按照什么方法对高性能计算机进行排序的 这种方法具有什么样的优点和不足? (2)结合髙性能计算的应用,谈谈为什么中国需要硏制高性能计算机。 (3)文中所说的机群系统指的是什么?它具有什么样的特点? 2.以下是一段用MPI实现的并行程序代码,用来并行求一组数的和。 #include #include

- 1 - 一、 填空题 1．常用的并行算法设计的基本技术有_______ _________，___________________， _______________________，____________ ______，_____________________， _______________________等。 2．常见的 并行 计算 模型 有____________ ______ ，_____________________， _______________________，____________ ______等。 3．PCAM 设计过程分为_________，__________，_________ 和_________四步。 4．常见的并行程序设计模型包括 __ ___________ ， __ _____________ ， ______________________，______________________等。 二、 问答题 1．请简述从上个世纪 80 年代至今，主流并行计算机体系结构的变化趋势。 2．基于蝶式计算原理的 FFT 在二维 mesh 连接和蝶式网络连接的处理器上均可并行实 现。 （1）请问哪种实现效率较好？并给出原因。 （2）蝶式网络连接的处理器在实际的并行计算机系统并不常见，这是否会影响 FFT 在 蝶式网络连接上的并行实现在实际中的使用？为什么？ 3．基本的开关技术有哪两种？各具有什么特点？ 三、 阅读题 1．阅读以下新闻报道，回答问题。 2004 年 6 月 29 日 国家科技部今日在人民大会堂宣布：“863 计划重点项目——曙光 4000A 通 过鉴定验收，曙光 4000A 实现了对每秒 10 万亿次运算速度的技术和应用的双跨越，成为国内计算能 力最强的商品化超级计算机”。在今年 6 月 22 日刚刚公布的全球高性能计算机 TOP500 排行榜中，曙 光 4000A 以每秒 11 万亿次的峰值速度和 80610 亿次 Linpack 计算值位列全球第十，这是中国超级计 算机得到国际同行认可的最好成绩。随着曙光 4000A 的推出，中国已经成为继美、日之后第三个跨 越了 10 万亿次计算机研发、应用的国家。 曙光 4000A 拥有自主研制的机群系统软件包括机群管理系统、机群部署系统、机群作业管理系 统、并行文件系统、机群监控系统、机群并行通信系统、机群高可用系统、机群负载均衡系统等。 （1）请问文中提到的“TOP500 排行榜”是按照什么方法对高性能计算机进行排序的？ 这种方法具有什么样的优点和不足？ （2）结合高性能计算的应用，谈谈为什么中国需要研制高性能计算机。 （3）文中所说的机群系统指的是什么？它具有什么样的特点？ 2．以下是一段用 MPI 实现的并行程序代码，用来并行求一组数的和。 #include #include

#include #define size 10 oid main (int argc, char *argv) nt myid, numprocs int data [SIze], i, x, low, high, myresult, result char fn[255 char x*fp MPI Init(&argc, &argv) PI Comm size(MPI COMM WORLD, &numprocs): MPI Comm rank(MPI COMM WORLD, &myid if (myid 0)[/* Open input file and initialize data * strcpy (fn, getenv("HOME")) strcat(fn, "/data") f ((fp fopen(fn, " r"))== NULL)( printf("Can't open the input file: %s \n\n", fn) exit(1) for(i=0: i SIZE: i++) fscanf(fp, %d", &data[il) / broadcast data * MPI Bcast(data, SIZE, MPI INT, 0, MPI COMM WORLD); /k Add my portion Of data * X= SIZE/numprocs id*k if(myid = numprocs -1) high SIZE ult =0: f high: i++) myresult + datalil /=* Compute global sum * PI Reduce(&myresult, &result, 1, MPI INT, MPI SUM, 0, MPI COMM WORLD) f(myid 0) printf(" The sum is %d \n", result) MPI Finalize o 请回答以下问题: (1)请问上述并行程序的并行执行的进程数是何时指定的,如何确定的?在程序中 使用什么函数得到了进程数的信息

- 2 - #include #define SIZE 10 void main(int argc, char *argv) { int myid, numprocs; int data[SIZE], i, x, low, high, myresult, result; char fn[255]; char *fp; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); if (myid == 0) { /* Open input file and initialize data */ strcpy(fn,getenv("HOME")); strcat(fn,"/data"); if ((fp = fopen(fn,"r")) == NULL) { printf("Can’t open the input file: %s\n\n", fn); exit(1); } for(i = 0; i < SIZE; i++) fscanf(fp,"%d", &data[i]); } /* broadcast data */ MPI_Bcast(data, SIZE, MPI_INT, 0, MPI_COMM_WORLD); /* Add my portion Of data */ x = SIZE/numprocs; low = myid * x; high = low + x; if(myid == numprocs - 1) high = SIZE; myresult = 0; for(i = low; i < high; i++) myresult += data[i]; /* Compute global sum */ MPI_Reduce(&myresult, &result, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD); if (myid == 0) printf("The sum is %d.\n", result); MPI_Finalize(); } 请回答以下问题： (1) 请问上述并行程序的并行执行的进程数是何时指定的，如何确定的？在程序中， 使用什么函数得到了进程数的信息

(2)试分析上述并行程序对应的并行算法的时间复杂度 (3)说明上述并行程序是如何对计算任务进行划分的。请问这种划分方式是循环划分 还是块划分?试写出另一种划分方式的代码 (4)试对上述并行程序的加速比进行分析,并以此为例简要说明 Amdahl定律和 Gustafson定律的不同 (5)结合上述并行程序的输入输出部分,说明SPMD程序的特点。 (6)请问上述程序中使用了MPI哪些群集通信的函数?它们实现了什么功能? 四、综合题 1.假定A4和B已加载到如下所示的4×4处理器阵列上,试用图表示 Cannon矩阵乘 法或者Fox矩阵乘法的具体过程(任选一种即可)。 Aoo Ao. Ao2Ao Boo Bo. 1 Bo.2 B Al.A B.0B.:B12|B A2.0A A B2.0B2 B2 A B B3. 1 B B 以下是上三角方程组回代解法的串行算法的形式化描述。 Begin (1)for i=n downto l do (1.1)x=b/ar (1.2)fo bj= j ajXi endfor endo End ①请指出串行算法哪些部分可以并行化。②写出并行算法的形式化描述(需要注明 计算模型类型),分析你的算法的时间复杂度

- 3 - (2) 试分析上述并行程序对应的并行算法的时间复杂度。 (3) 说明上述并行程序是如何对计算任务进行划分的。请问这种划分方式是循环划分 还是块划分？试写出另一种划分方式的代码。 (4) 试对上述并行程序的加速比进行分析，并以此为例简要说明 Amdahl 定律和 Gustafson 定律的不同。 (5) 结合上述并行程序的输入输出部分，说明 SPMD 程序的特点。 (6) 请问上述程序中使用了 MPI 哪些群集通信的函数？它们实现了什么功能? 四、 综合题 1．假定 A44 和 B44 已加载到如下所示的 4 4 处理器阵列上，试用图表示 Cannon 矩阵乘 法或者 Fox 矩阵乘法的具体过程（任选一种即可）。 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 2．以下是上三角方程组回代解法的串行算法的形式化描述。 Begin (1)for i=n downto 1 do (1.1)xi=bi/aii (1.2)for j=1 to i-1 do bj=bj-ajixi aji=0 endfor endfor End ①请指出串行算法哪些部分可以并行化。②写出并行算法的形式化描述（需要注明 计算模型类型），分析你的算法的时间复杂度