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

、判断正误(每题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分