填空题 常用的并行算法设计的基本技术有_______ _________，___________________，_______________________，____________ ______，_____________________，_______________________等。 常见的并行计算模型有____________ ______，_____________________，_______________________，____________ ______等。 PCAM设计过程分为_________，__________，_________ 和_________四步。 常见的并行程序设计模型包括__ ___________，__ _____________，______________________，______________________等。 问答题 请简述从上个世纪80年代至今，主流并行计算机体系结构的变化趋势。 基于蝶式计算原理的FFT在二维mesh连接和蝶式网络连接的处理器上均可并行实现。 （1）请问哪种实现效率较好？并给出原因。 （2）蝶式网络连接的处理器在实际的并行计算机系统并不常见，这是否会影响FFT在蝶式网络连接上的并行实现在实际中的使用？为什么？ 基本的开关技术有哪两种？各具有什么特点？ 阅读题 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 <mpi.h> #include <stdio.h> #include <math.h> #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．假定和已加载到如下所示的处理器阵列上，试用图表示Cannon矩阵乘法或者Fox矩阵乘法的具体过程（任选一种即可）。  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 ①请指出串行算法哪些部分可以并行化。②写出并行算法的形式化描述（需要注明计算模型类型），分析你的算法的时间复杂度。