并行计算总复习之秘笈课件

1、并行计算总复习第一章：1并行计算与串行计算在算法和编程上有哪些显著差异？答： ·并行算法设计与并行计算机处理器的拓扑连接相关·并行算法设计和采用的并行计算模型有关。·并行计算有独自的通讯函数·并行算法设计时，如何将问题分解成独立的子问题是科学研究问题，并非所有的问题都可以进行分解。2多核与多处理机的异同点？多处理机：把多个处理器通过网络互连形成一个新机器。可以是专用，也可以是通用。拓扑连接是可以改变的。多核：在过去单个处理器芯片上实现多个“执行核”。但这些执行核都有独立的执行命令集合和体系结构。这些独立的执行核+超线程SMT技术组成多核处理器3对单处理器

2、速度提高的主要限制是什么？答： 晶体管的集成密度，功耗和CPU表面温度等第二章1 SIMD 和 MIMD 所代表的计算模型是什么？主要区别和各自的系统结构示意图。SPMD的含义是什么？SIMD指单指令多数据流模型；MIMD指多指令多数据流模型；SPMD指单程序多数据流模型，在SIMD中把指令改为程序表示每个处理器并行的执行程序。 SIMDMIMD硬件较少处理器较多处理器内存一个寻址系统，存储量小多个寻址系统，存储量大耗费较高，难开发易于开发（多个商业组件可用）加速高取决于应用2 若按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？基于共享地址空间：并行平台支持一个公共的数

3、据空间，所有处理器都可以访问这些空间。处理器通过修改存储在共享地址空间的数据来实现交互。基于消息传递：消息传递平台有p个处理节点构成，每个节点有自己的独立地址空间。运行在不同节点上的进程之间的交互必须用消息来完成，称为消息传递。这种消息交换用来传递数据、操作以及使多个进程间的行为同步。3 在理想并行计算模型中（并行随机访问计算机parallel random access machine(PRAM), EREW, ERCW CREW, 和CRCW表示的意思是什么？EREW：互斥读互斥写，这一类的PRAM独占访问内存单元，不允许并发的读写操作。最弱的PRAM模型，对内存访问提供最小的并发性。CR

4、EW：并发读互斥写。对内存单元允许多读，但对内存位置多写是串行的ERCW：互斥读并发写。对内存单元允许多写，但多读是串行的。CRCW：并发读并发写。对内存单元允许多读多写。最强大4 能画出多处理机系统中处理单元的基本互连结构图，Mesh, hypercube, W 网络，注意对顶点编号的要求。 Mesh:二维网格中每个维有sqrt（p）个节点，p为处理器的数目。hypercube:p为处理器数目，超立方体结构有logP维，每维上有两个节点超立方体的节点编号很有用，有两个p/2各节点的子立方体的编号，就可以一个前面加0一个前面加1实现，这样标号0110的节点和标号0101的节点相隔两个链路因为他

5、们有两位不同，性质以此类推。W 网络：设p个处理器processor（输入），p个存储区bank（输出）；该网络有sqrt（p）级输入：i；输出：jj=2i， 0<=i<=p/2-1;j=2i+1-p, p/2<=i<=p-1.数据选路时，假设从s（二进制表示）传送到t，从最高位起开始比较，相同的位走直通，不同的位走交叉。5 知道对静态网络的常用测度：直径，连通性，二分宽度(bisection width), cost.直径：网络中两个处理节点之间的最长距离称为网络直径。（越小越好）连通性：网络中任意两个节点间路径多重性的度量。连通性的一个度量是把一个网络分成两个不连通

6、的网络需要删除的最少弧数目。（越大越好）二分宽度：把网络分成两个相等网络时必须删去的最小通信链路数目。（越大越好）cost：网络中所需的通信链路的数量或线路数量。6 能说出一种解决多处理器系统中cache和内存数据一致性问题的方法。（侦听和基于目录） 用无效协议维持一致性，并用基于目录的系统来实现一致性协议。基于目录：为全局内存增加一个目录，维护一个bitmap，表示已缓存的处理器及相应的数据项状态。三状态协议含有无效、脏以及共享三种状态。工作原理：当一个处理器P1修改了共享数据，P1修改bitmap,state 为dirty,它自己可以继续修改。当另一处理器P2需要读该数据，目录告诉它p1目

7、前拥有该数据，并通知p1更新状态，并把数据送给P2.优点：减少数据无谓的移动和更新（把空间分的更细）缺点：连接复杂性高O(mp)7 能给出store-and-forward routing 和cut-through routing的思想。通讯费用是如何计算的？延迟时间， ts, th, twstore-and-forward routing：在此过程中，消息穿过有多个链路的路径时，路径上的每个中间节点接受和存储完整的消息后，就把消息转发给下一个节点。T = ts+（m tw+ th）l，th为消息头导致的开销。l为链路数。m为消息字长。cut-through routing：在此过程中，消息被

8、分成固定大小的单元，称为数据片。首先从源节点向目的节点发送跟踪程序以建立两点间的连接。连接完成后，数据片就一个接一个的发送。中间节点无需等待所有消息到达就可以发送数据片。当某一数据片被中间节点接收后，该数据片被传到下一节点。与store-and-forward routing不同，每个中间节点无需用缓冲区空间存储完整的信息。因此，中间节点只需要使用更少的内存和带宽，速度也快得多。T = ts + m tw + th*l，th为消息头导致的开销。l为链路数。m为消息字长。Tcomm= ts+lth+mtw；1)startuptime (Ts): 在数据包上加上必要的头、尾信息，错误检测矫正信息、

9、执行路由算法时间以及建立节点与路由器之间的接口。2）per-hop time (Th): node latency from u to v;3 )per-word-transfer time(Tw)(每个字的传输时间），如果通道带宽为r个字符每秒，每个字符的传输时间为Tw=1/r8 对Mesh 的X-Y_routing和对Hypercube的E-Cube routing的路由规则。Mesh 的X-Y_routing：消息首先沿X为出发，直到到达目标节点的列，再沿Y维到达目的节点。其路径长度为L = |Sx-Dx|+|Sy-Dy|;Sx，Sy为源节点坐标；Dx，Dy为目标节点坐标。Hypercu

10、be的E-Cube routing：考虑节点数为p的d维超立方体。令Ps和Pd分别为源节点和目标节点的编号。在E-Cube算法中，节点Ps计算Ps (+) Pd的值并沿k维发送消息，其中k是Ps (+) Pd中的最低非零有效位的位置。每个中间节点Ps收到信息，计算出Ps (+) Pd，再将消息沿着与最低非零有效位对应的维转发，直到消息到达目标节点。9 如何把linear array, mesh 和hypercube 相互嵌入？G(i,d)函数的计算。·linear array嵌入到hypercube：含2个节点的linear array可以嵌入到d维超立方体中，只需把linear a

11、rray 中的节点i 映射到hypercube的节点G（i,x）上。函数G（i，x）定义如下：G（0，1）=0；G（1，1）=1；G（i，x+1）= G（i，x） i<2G（i，x+1）=2+G(2-1-i,x) i2（已知d位葛莱码，对原项加前缀0，反映项加前缀1，可得到d+1位葛莱码）·mesh嵌入到hypercube：将mesh嵌入到到个节点的hypercube中，只须将mesh上的节点（i,j）映射到hypercube的节点G(i,r-1)|G(j,s-1)上，即node(i,j) >G(i,r-1)|G(j,s-1)·mesh嵌入到linear arr

12、ay 10把复杂网络嵌入的简单网络，能说明些什么问题？其意义是什么？一般对简单网络的带宽是怎么要求的？意义：高维上的网络一般布线复杂，有线的交叉和长短不一等问题。而加宽通讯带宽后的低维互连网络，可以取代高维复杂网络。如果带宽增加到可以抵消互连拥塞，就可按稠密网络一样运行。第三章11 dependency graph 的定义及画法。对同一问题dependency graph 的画法是否唯一？dependency graph表示任务间的依赖关系和任务的执行次序关系。是一种有向无环图，节点表示任务，边表示节点间的依赖性。边<u,v>表示u任务执行完后v任务才能执行。.不唯一13 并行算法

13、的粒度定义是什么？粒度大小在理论上和在实际上对并行算法的影响。分解问题得到的任务数量和大小决定了分解的粒度，将任务分解成大量的细小任务称为细粒度，而将任务分解成少量的大任务称为粗粒度。14在进程调度中，把processes 影射到processors的基本原则是什么？减少通讯，,1）设法将相互独立的任务映射到不同的进程中以获得最大并发度；2）确保关键路径上的任务一旦可执行就去执行它们，以使得总计算时间最短3）映射相互交互的任务到同一进程以便最小化进程间的交互。15在并行算法设计时，有几种把计算分解的技术？能给出名称并能举例说明。·Recursive decomposition (递归

14、分解）：可能产生太多任务使程序变慢 or 快速排序·Data decomposition : based on the independency of data（基于数据独立性分解）：根据对输出数据的划分来划分任务。例如：矩阵相乘·Exploration decomposition（探索分解）：对应于人工智能中基于解空间探索方法的问题求解，例如迷宫游戏·Speculative decomposition （投机分解）：用于分支语句中，在未能决定分支转向时，并行的计算多个分支，当最终决定转向时，正确的分支对应的计算将被利用，其他的被丢弃。·混合分解，将前面

15、的分解方法组合应用，在计算的不同阶段使用不同的分解方法。例如，快速排序，先数据分解然后再使用递归分解16为了解决由于数据分布密度不均匀问题，能说出3种以上可以帮助使并行任务的负载接近平衡的方法或思路。循环块分配、随机块分配、图划分17 能说明data parallel model, task graph model 和work pool model 的含义。·data parallel model（数据并行模型）：任务被静态或半静态的映射到进程，并且每个任务都对不同的数据进行相似的操作。这种并行性是把同样的操作并发的运用到不同的数据项上产生的结果，因此称为数据并行。·tas

16、k graph model（任务图模型）：使用任务之间的相互关系来提高本地性或减少交互开销。如果某一问题中，与任务对应的数据量远大于与任务相对应的计算，则通常用任务图模型来解决此类问题。·work pool model（工作池模型）：动态映射任务到进程以保持负载平衡，在这种映射中，任何任务可能由任何进程执行。进程可以产生工作并把它添加到工作池中。第四章18 Basic communication operations对偶的概念是什么？在对通讯原语研究中，为什么强调操作对之间的对偶性？能给出3个以上的对偶原语。·通信操作的对偶是原始操作的逆操作，可以通过逆转原操作中的通信方向

17、和消息序列来完成。·强调对偶的意义在于，研究一个问题，其对偶问题的解可以类似解决。·one-to-all broadcast / all-to-one reduction, all-to-all broadcast / all-to-all reduction, scatter / gather19 能画出下列操作的示意图，并能解释通信原语所完成的任务是什么one to all broadcast; all to one reductionall to all broadcast; all to all reductionscatter, gather, all reduc

18、e, prefix sum，all to all personalized communication. Circular shift·one to all broadcast; all to one reduction一个进程发送相同的数据给其他所有的进程；来自所有进程的数据通过一个相关的操作符组合起来，并被累加到一个目标进程的缓冲区中。·all to all broadcast; all to all reduction多对多广播是一对多广播的推广，其中所有p个节点同时发起一个广播；多对多规约是多对多广播的对偶，p个多对一规约同时进行，每个操作都有不同的目标节点。

19、83;scatter, gather, 散发：单个节点发送一个大小为m的唯一消息给每一个其他节点，散发与广播的不同点是：广播，所有进程接收到相同的消息；而散发，不同的节点接收到不同的消息。收集：一个节点从其他各个节点那里收集消息，与多对一规约不同，收集操作不涉及数据的组合与规约。·all reduce, prefix sum，全规约：等同于先进性一个多对一规约，再进行一个一对多广播。前缀和：n0n1,np-1 > S1,S2,Sp-1,其中·all to all personalized communication：每个节点发送一个大小为m的不同消息给其他每个节点，每

20、个节点都发送不同的消息给不同的节点，而在多对多广播中，每个节点发送相同的消息给所有其他节点。 ·Circular shift,循环q移位定义：在一个p节点的总体中，节点i发送一个数据包给节点（i+q）mod p，其中0<q<p。移位操作在某些矩阵计算及字符串、图像模式匹配上都有应用20能写出在hypercube上的·one to all broadcast/ ·all to one reduction P114P115·all-to-all personal broadcast;P131·all-to-all broadcast;

21、P118算法以及时间复杂性的分析。能举出2种以上在并行编程中的应用例子。第五章21并行算法的分析测度并行算法并行加速比S，效率E和费用cost的计算公式。说明在什么情况下可能出现超线性加速比？何谓费用最佳的并行算法cost-optimal？设计费用最佳的并行算法的思路是什么？·加速比S = Ts/Tp （Ts串行运行时间，Tp并行运行时间）理论上，加速比不可能超过处理器数p，但是加速比大于p是可能的，当加速比大于p时，称为超线性加速比；使用高速缓存或基于探索策略的并行算法都可能出现超线性效果。·效率E= S/p= Ts/（Tp*p）（p：处理器的个数）·Cost

22、= Tp*p, E = Ts/cost.Cost-optimal if cost(n) = O(Ts)>E = 1.cost-optimal:如果在并行计算机上，求解问题的成本作为属于数据大小的函数，与在单片机上的已知最快串行算法有着同样的渐进增长，那么称并行系统是成本最优的。设计费用最优的并行算法思路：把数据划分为p个部分用p个处理器分别来处理这p个部分用并行算法将p个结果合并根据费用最优得出p的值使p满足n = W(plogp)22 Amdahl定理的含义？如何证明？Amdahl定理：一个规模为W的问题的串行部分为Ws，那么，不管用多少处理器，W/Ws都是其加速比的上界。证明：因为W

23、 = Wp+WsTs = WTp=Ws+Wp/p又因为S= Ts/Tp 则S= W/(Ws+Wp/p)= (W/Ws)/(1+Wp/pWs)因为p->无穷大, 则S-> W/Ws 第六章23 MPI是什么的缩写，MPI是语言还是一个函数库？MPI：the Message Passing Interface MPI is a function library，used with other programming languages24 能说出三个MPI的基本函数,并作出解释。n MPI_Init 初始化MPIn MPI_Finalize 终止MPIn MPI_Comm_size 确

24、定进程个数n MPI_Comm_rank 确定被叫进程的标号n MPI_send 发送n MPI_Recv 接收25 MPI程序的基本结构是什么？一般的MPI程序都有MPI说明有哪些？异步模式，松散同步模式·启动和终止MPIMPI_Init(int *argc, char *argv) MPI_Finalize()·获取信息MPI_Comm_size(MPI_Comm comm, int *size)MPI_Comm_rank(MPI_Comm comm, int *rank)·发送和接收消息MPI_Send()MPI_Recv()26 MPI程序中容易出现什么形

25、式的死锁？发送与接受顺序上的死锁27 MPI是通过什么方法，实现在Mesh上的并行算法？能读懂MPI程序。MPI_Cart_create(comm,2,10,1,1,&comm_2d)从最初申请到的并发进程集合组成2维网格int MPI_Comm_rank(MPI_comm_old, MPI_Comm_new) 把过去的id 变换成新的2维网格下的 id 值int MPI_Cart_rank(MPI_Comm comm_cart, int *coords, int *rank)基于2维网格后的2维坐标，得到2维网格下的进程id） int MPI_Cart_coord(MPI_Comm

26、comm_cart, int rank, int maxdims, int *coordinate) 根据在新的2维环境下进程的id，返回在2维网格下的坐标，coordinate是数组 第七章28 Pthead的定义是什么？Pthread 程序一般要包含哪些语句？IEEE指定的一个标准的线程API，POSIX API。POSIX也称为Pthread线程的创建、终止 pthread_create pthread_exit等待所有线程运行完毕以便完成结果的合并 pthread_join29 在pthread中，thread之间的同步，对关键区域的共享使用时是如何实现的？使用mutex-lock(互

27、斥锁) 使得各个线程互斥的访问关键区域。要访问关键区域，线程必须首先获得互斥锁并锁定pthread_mutex_lock()，离开关键区域后,要进行解锁pthread_mutex_unlock()，mutex-lock被一个线程锁定后，不允许其他的线程进入关键区域。30 Mutex 的属性类型以及使用，条件变量和mutex_lock的一起使用。能用Pthread 语句写出简单的多线程之间对共享资源的共享的代码。·正常互斥锁：在任意时刻，只允许一个线程锁定互斥锁，已获得互斥锁的线程若试图再次锁定它，将导致死锁。·递归互斥锁：允许单一的线程多次锁定互斥锁，线程每锁定一个互斥锁时

28、，锁计数器加1，每次解锁计数器减1，如果任何其他线程想成功锁定一个递归互斥锁，锁计数器必须为0.·错误检查互斥锁：一个线程只能锁定一个互斥锁一次，当线程试图锁定一个已经锁定的互斥锁时，错误检查互斥锁将返回一个错误而不是死锁。31 Open MP 是什么形式的API?如何实现并发程序设计的？·OpenMP 是一种可以用FORTRAN, C以及 C+在共享地址空间计算机上进行编程的指令性的API。OpenMP命令提供对并发，同步以及数据处理的支持，但不需要显式设置互斥锁、条件变量、数据范围以及初始化。·使用parallel命令来创建一组线程#pragma omp pa

29、rallel clause list /parallel segment每个线程执行parallel segment中内容Parallel和命令for、sections一起使用实现迭代和任务的并发。·for命令用来在多个线程间分割并行迭代空间，一般形式如下：#pragma omp for clause list /* for loop*/ ·sections命令用于对非循环的并行任务分配,形式如下：#pragma omp sections clause list #pragma omp sectiontaskA();#pragma omp sectiontaskB();每个

30、段（即为相应的任务）分配给一个线程32能用Open MP 写出矩阵与向量，矩阵之间和易于并行计算的程序代码。矩阵乘#pragma omp parallel default(private) shared (a, b, c, dim) num_threads(4)#pragma omp for schedule(static)for (i = 0; i < dim; i+) for (j = 0; j < dim; j+) c(i,j) = 0;for (k = 0; k < dim; k+) c(i,j) += a(i, k) * b(k, j);第八章并发实现矩阵与向量的乘

31、法能给出如何实现矩阵转置的算法。能写出Cannon， Fox和简单矩阵乘法算法。33 并发实现矩阵与向量的乘法。A X·带状划分的矩阵-向量乘法 划分(行带状划分): Pi存放xi和a（i,0）,a（i,1）,a（i,n-1）, 并输出yi 算法: 对p=n情形 每个Pi向其他处理器播送xi(多到多播送)； 每个Pi计算； 注: 对p<n情形,算法中Pi要播送X中相应的n/p个分量·棋盘划分的矩阵-向量乘法 划分(块棋盘划分): Pi,j存放ai,j, xi置入Pi,i中 算法: 对p=n情形 每个Pi,i向Pj,i播送xi(一到多播送)； 按行方向进行乘-加与积累运

32、算，最后一列Pi,n-1收集的结果为yi； 注: 对p< n情形,p个处理器排成的二维网孔， 算法中Pi,i向Pj,i播送X中相应的个分量34 能给出如何实现矩阵转置的算法。算法: 按mesh连接进行块转置(不同处理器间) 进行块内转置(同一处理器内)35能写出Cannon， Fox和简单矩阵乘法算法。Cannon P255·初始时，把子矩阵Aij和Bij分配给处理器Pij 矩阵A的第i行循环左移i步，矩阵B的第j列循环上移j步；t=； 各处理器A块与B块进行乘-加运算；t-； if（t<>0）,A矩阵每行循环左移1步，B矩阵每列循环上移1步上面算法中，每个进程Pi

33、j中一共进行了次Aik与Bkj（）的相乘，从而完成矩阵A和B的乘法运算Fox 课件·初始时，把子矩阵Aij和Bij分配给进程Pij（同Cannon）Ai,i向所在行的其他处理器进行一到多播送； 各处理器将收到的A块与原有的B块进行乘-加运算; B块向上循环移动一步; 如果Ai,j是上次第i行播送的块，本次选择 向所在行的其他处理器进行一到多播送; 转执行-1次; 第九章36奇、偶排序的并行算法， 能叙述双调（Bitonic）排序的思路以及画法。知道该算法是如何在超立方体上实现的。·奇-偶排序的并行算法考虑每个进程一个元素的情况。在奇数排序阶段，每个奇数下标的进程将其元素与其

34、右边的相邻元素进行比较-交换；同样，在偶数排序阶段，每个偶数下标的进程将其元素与其右边的相邻元素进行比较-交换。·双调排序s = áa0,a1,an-1ñ 是一个双调序列并且 a0 a1 ··· an/2-1 and an/2 an/2+1 ··· an-1 ； 令子序列s1 = ámina0,an/2,mina1,an/2+1,minan/2-1,an-1ñs2 = ámaxa0,an/2,maxa1,an/2+1,maxan/2-1,an-1ñ 则s1与 s2都

35、是双调序列且s1中每个元素都小于s2中元素。这样原问题s排序就化简为两个较小的双调序列排序，并将结果连接起来。上述一个双调序列划分成两个较小双调序列的操作称作双调分裂。n个元素的序列进行logn次双调分裂即可完成排序。将任意序列转化为双调序列并最终完成排序/ /label：进程标号 d：超立方体维数第十章37 最小生成树和最短路径算法的并行实现；P319 P321·最小生成树Prim算法：设G（V，E）为加权无向连通图，A=（ai，j）为加权邻接矩阵。用Vt来保存最小生成树构造过程中的顶点。维护一个数组d，对于每个顶点，dv中保存从Vt中的任何顶点到顶点v的边中最小的权值。 任选一点

36、r加入Vt，dr=0对于所有，若边（r，v）存在，则令dv=w(r,v)，否则令dv=while VtV do 找到一个顶点u满足du=mindv| ; 将u加入到集合Vt；对于所有，更新dv的值； endwhile并行形式：令p为进程数，将集合V划分为p个子集，每个子集分配给不同的进程。每个进程Pi存储数组d中与Vi对应的部分。在while循环的每次迭代中，每个进程Pi计算d u=mind v| ，对所有的d u进行多对一规约操作得到全局最小值，并存储在P0中。此时进程P0中保存新的顶点u，它将被插入到Vt中。进程P0使用一对多广播将u广播给所有的进程。负责顶点u的进程将u标记为属于集合Vt，最后每个进程对自己本地