并行计算总复习.doc

并行计算总复习题型：1 问答题；2 算法描述；3 走例子说明对算法的理解第二章SIMD 和 MIMD 所代表的计算模型是什么？主要区别和各自的系统结构示意图。SPMD的含义是什么？若按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？在理想并行计算模型中（parallel random access machine(PRAM), EREW, CREW, 和CRCW表示的意思是什么？能画出多处理机系统中处理单元的基本互连结构图， Mash, hypercube, W 网络， 对静态网络的测度：直径，连通性，二分宽度(bisection width), cost.能说出一种解决多处理器系统中cache和内存数据一致性问题的方法。能给出store-and-forward routing 和cut-through routing的思想通讯费用是如何计算的？延迟时间， ts, th, tw对Mesh 的X-Y_routing和对Hypercube的E-Cube routing的路由规则。如何把linear array, mesh 和hypercube 相互嵌入？G(i,d)函数的计算。把复杂网络嵌入的简单网络，能说明些什么问题？其意义是什么？一般对简单网络的带宽是怎么要求的？第三章dependency graph 的定义及画法。对同一问题dependency graph 的画法是否唯一？并行算法的粒度定义是什么？把processes 影射到processors的基本原则是什么？减少通讯，,在并行算法设计时，有几种把计算分解的技术？能举例说明。能说明data parallel model, task graph model 和work pool model 的含义。第四章Basic communication operations能画出下列操作的示意图one to all broadcast; all to one reductionall to all broadcast; all to all reductionscatter, gather, all reduce, prefix sum，all to all personalized communication. Circular shift,能写出在hypercube上的one to all broadcast/ all to one reductionall-to-all personal broadcast;all-to-all broadcast;算法以及时间复杂性的分析。能举出2种以上在并行编程中的应用列子。第五章并行算法的分析测度并行算法并行加速比S，效率E和费用cost的计算公式。说明在什么情况下可能出现超线性加速比？何谓费用最佳的并行算法cost-optimal？设计费用最佳的并行算法的思路是什么？Amdahl定理的含义？如何证明？第六章MPI是什么的缩写，MPI是语言还是一个函数库？能说出三个MPI的基本函数,并作出解释。MPI程序的基本结构是什么？MPI程序中容易出现什么形式的死锁？MPI是通过什么方法，实现在Mesh上的并行算法？能读懂MPI程序。第七章Pthead的定义是什么？在pthread中，thread之间的同步，对关键区域的共享使用时是如何实现的？Mutex 的属性类型以及使用，条件变量和mutex_lock的一起使用。 Open MP 是什么形式的API?如何实现并发程序设计的？能看懂Open MP程序第八章并发实现矩阵与向量的乘法能给出如何实现矩阵转置的算法。能写出Cannon， Fox和简单矩阵乘法算法。第九章奇、偶排序的并行算法， 能叙述双调（Bitonic）排序的思路以及画法。知道该算法是如何在超立方体上实现的。第十章最小生成树和最短路径算法的并行实现；图的连通分支的并发实现；寻找图的极大独立集算法的思想第12章Dynam