西安交通大学研究生考试题

西安交通大学研究生考试题课程名称并行计算理论姓名学号I.II.III.IV.VVI.VII.一、判断正误（每题1分，共20分）1)在并行性概念中，两个事件若满足并发性则它们一定是同时发生的；2)等效率度量标准用于度量系统的可扩放性好坏，其中等效率函数为问题规模随处理器变化的函数，那么当该函数为线性函数时，表示原系统的可扩放性好；3)如果一个算法的加速比是超线性的，那么它的效率等于1；4)用PRAM-CREW和PRAM-CREW模型描述同一个并行问题，所得到的算法的复杂度一般相差logp倍，其中p为处理器数目；5)按照Flynn分类法，心动阵列（SystolicArray）属于SIMD结构；6)PCAM中，采用重复计算会增加计算量，所以计算时间相应增加。7)程序中使用MPI_ISend/MPI_IRecv实现通信时不会产生死锁。8)根据“表面-容积效应”，要想提高计算与通信之比，需要通过合并来增大任务的粒度；9)在并行算法设计中，对数划分方法是一种域分解方法；10)Batcher排序网络中，不允许输入序列中含有相同元素的情况，否则，有可能导致结果错误。11)根据BSP模型，计算被划分为由多个超级步组成；12)一个并行算法的计算量与它的执行时间相等；13)并行算法设计中的倍增技术主要适用于PRAM模型；14)2D-Mesh上的并行FFT算法的时间复杂度是O(n);15)OpenMP是数据并行语言，通过编译制导能有效地实现对循环的并行化；16)典型的OpenMP程序含有多个并行区域，相邻的并行区域存在并列和嵌套两种关系；17)OpenMP中，如果两个线程的执行具有同时性，那么它们肯定位于一个并行区域中；18)Pthreads通过pthread_join()实现与子线程的同步；19)Cilk中任何函数都可以由spawn派生为线程；20)Cilk的“工作窃取”方式的调度是一种动态的线程调度方式；二、填空（每空1分，共20分）a)DSM是MIMD结构的一种，其特点是分布共享存储，那么访存模型是(1)；b)可以完美嵌入（Congestion,Dilation或Expansion为1）到n个结点的超立方体网络中的网络有(2)和(3)；c)并行机可看作是开发和利用并行性所得到的结果，那么，如果这种并行机由多个处理器构成，则可以肯定地说是采用了(4)这一开发途径。d)按照体系结构的Flynn分类法，SMP与MPP同属于(5),但二者在体系结构上的最大区别是(6),如果考虑编程语言Cilk、Pthreads和MPI，那么SMP适合于(7)语言，而MPP适合于(8)语言；e)在各种网络中实现“多到多个人通信”时，对性能影响大的并且跟网络拓扑结构有关的指标是(9)；f)对2D-Mesh中的处理器结点进行编址的主要方法是(10)、(11)和(12)（如果记不住名词的话图示也可）；g)PRAM模型适用的体系结构是(13)，LogP模型适用的体系结构是(14)；h)DNS矩阵乘算法复杂度为(15)，所采用的并行机结构为(16)；i)采用指针跳跃技术求由n个结点构成的森林的根，那么时间复杂度上界是(17)，而时间复杂度下界是(18)；j)共享存储编程中，利用(19)实现并发单位之间的数据交换，而在分布存储编程中，利用(20)实现并发单位之间的数据交换。三、简答题（每题10分，共40分）1)如图所示为操作集合及其操作之间的依赖关系。其中结点表示操作，结点中的数字表示该操作的计算量；弧表示依赖关系，即射入结点只有在射出结点执行完成后才能开始执行。根据此图验证Brent定理（其中处理器个数为3），并进行必要的解释。2)针对LogP模型编写了一个并行程序，由a，b和c三个进程组成。在这个程序执行过程中，计算和通信是完全重叠的。其中三个进程之间发送短消息的情况如下：(a,b,10),(b,c,6),(c,a,8),(c,b,4),(b,a,2)，此外无其它任何消息发送。现在要问这个程序的执行时间是多少？注：(x,y,n)表示进程x向y发送n个短消息。3)试画出7个输入的双调排序网络。4)在p=2t个结点的2D-Mesh上求p个数之和，试问花费的时间是多少？假定是MIMD结构并且每个结点放一个数。961843231849618461868四、（20分）已知如下表所示的9个语言机制，试完成后续的问题。编号描述注释1cilk/spawn/synccilk语言的线程创建、同步机制2“work-stealing”cilk语言的线程调度机制3pthread_create/pthread_joinPthreads语言线程创建、同步机制4#pragmaompparallelOpenMP语言并行区域5#pragmaompforOpenMP语言数据并行6#pragmaompreductionOpenMP语言单点收集7MPI_cart_create/MPI_cart_shiftMPI语言笛卡尔拓扑及移位机制8MPI_send/recv/Isend/IrecvMPI语言点对点发送接收消息机制9MPI_Scatter/Gather/Reduce…MPI语言成组发送接收消息机制1一般而言，给定的并行语言机制是否适用于实现某些并行算法是首先要解决的问题，试描述一下对于表中的这些语言机制，根据什么指标或原则来判断适用于哪些并行算法的实现呢？2结合上述表格中的9个语言机制，对于下面列出的一些并行算法的内容，用编号标记出最适合的情况。a)模拟测试抽象算法和具体算法之间的时间关系；b)实现经理雇员（master-slave）计算模式；c)实现指针跳跃算法中的并发单位的创建；d)解决Cannon矩阵乘法中的分块矩阵的动态存放问题；e)实现PSRS排序算法中的全局交换；f)把循环划分成多个并发单位；