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