并行计算期末考试卷

并行计算期末考试试卷
考试科目:_ 并行计算 得分:__________
学生所在系:___________ 姓名:__________ 学号:___________
一、（15分）在新华社报道“中国成功研制千万亿次超级计算机”中有以下内容：
每秒钟１２０６万亿次的峰值速度和每秒５６３．１万亿次的Ｌｉｎｐａｃｋ实测性能，使这台名为“天河一号”的计算机位居同日公布的中国超级计算机前１００强之首，也使中国成为继美国之后世界上第二个能够研制千万亿次超级计算机的国家。
超级计算机又称高性能计算机、巨型计算机，是世界公认的高新技术制高点和２１世纪最重要的科学领域之一。
“随着我国经济的发展，环境控制、生物医药等领域已经对千万亿次甚至更高性能的计算机提出了现实需求。”国防科技大学校长张育林说。国防科技大学是“天河一号”的研制者。１９８３年面世的中国第一台亿次计算机“银河一号”，同样诞生在这所大学。“超级计算机的研制历程表明，我们要在高技术领域有所作为，必须走一条中国特色的自主创新之路。”张育林说，“一味追求国际排名是没有意义的，只有在核心技术、实际效益和人才培养上不断实现新的突破，科学研究才有了持续发展的动力。”

请简要回答以下问题：
1. 新闻中提到的“Linpack”指的是什么？它除了作为测试程序外，本身具有什么功能？
2. 峰值速度和Linpack实测速度各是如何得到的？实测速度与峰值速度的比值有什么含义？
3. 新闻中提到的“天河一号”采用了机群的体系结构。请简述机群结构的特点。

二、（15分）描述Amdahl加速比定律，并给出该定律的推导过程。举例说明可能出现超线性加速比的情况。超线性加速比的存在与Amdahl定律是否矛盾？

三、（10分）根据SIMD-TC上非递归求前缀和算法（课本算法6.9），对输入序列为（8，7，6，5，4，3，2，1）求前缀和。要求通过图示给出算法执行流程。

四、（15分）矩阵简单分块乘法执行在p个处理器的全连接结构（任意两个处理器有物理链路直接相连）上。输入矩阵A和B均为n×n阶。试分析算法的并行运行时间。

五、（15分）请给出PRAM-CREW模型上的快速排序的并行算法。输入为无序数组a[1]…a[n]，输出为有序数组b[1]…b[n]。

六、（15分）请列举常见的并行计算机结构模型、并行计算模型、并行程序设计模型。通过举例比较，说明上述三类模型的不同作用。

七、（10分）以下是一段并行程序
#include "mpi.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 1000

void main(int argc, char **argv)
{
int myid, numprocs;
int data[MAXSIZE], i, x, low, high, myresult, result;
char fn[255]={0};
FILE *fp;

MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
MPI_Comm_rank(MPI_COMM_WORLD, &myid);

if (myid == 0)
{
if ((fp = fopen("rand_data.txt","r")) == NULL)
{
printf("Can't open the input file: %s\n\n", fn);
exit(1);
}
for(i = 0; i < MAXSIZE; i++)
{
fscanf(fp, "%d\t", &data[i]);
printf(" %d",data[i]);
}
}

MPI_Bcast(data, MAXSIZE, MPI_INT, 0, MPI_COMM_WORLD);

x = MAXSIZE/numprocs;
low = myid * x;
high = low + x;
myresult = 0;
for(i = low; i < high; i++)
myresult += data[i];
printf("I got %d from %d\n", myresult, myid);

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. 请问上述程序中使用了MPI哪些群集通信的函数？它们各完成了什么功能?

八、（5分）以下是一段并行程序

#include <stdio.h>
#include "omp.h"

int main(int argc, char* argv[])
{
int i;
#pragma omp parallel for
for (i = 0; i < 4; i++ )
{
printf("i = %d\n", i);
}
return 0;
}

请问上述程序中使用的OPENMP的编译指导语句是什么？它的含义是什么? 试给出可能的运行输出结果。
 

› 《并行计算》实验教学大纲

› 多核编程与并行计算课程简介

› 并行计算期末考试卷