并行计算总复习之秘笈

并行计算总复习第一章：1并行计算与串行计算在算法和编程上有哪些显著差异？答：·并行算法设计与并行计算机处理器的拓扑连接相关·并行算法设计和采用的并行计算模型有关。·并行计算有单独的通讯函数·并行算法设计时，如何将问题分解成独立的子问题是科学研究问题，并非所有的问题都可以进行分解。2多核与多处理机的异同点？ 多处理机：把多个处理器通过网络互连形成一个新机器。可以是专用，也可以是通用。拓扑连接是可以改变的。多核：在过去单个处理器芯片上实现多个“执行核〞。但这些执行核都有独立的执行命令集合和体系结构。这些独立的执行核+超线程SMT技术组成多核处理器3对单处理器速度提高的主要限制是什么？答：晶体管的集成密度，功耗和CPU外表温度等第二章1SIMD和MIMD所代表的计算模型是什么？主要区别和各自的系统结构示意图。SPMD的含义是什么？SIMD指单指令多数据流模型；MIMD指多指令多数据流模型；SPMD指单程序多数据流模型，在SIMD中把指令改为程序表示每个处理器并行的执行程序。

SIMDMIMD硬件较少处理器较多处理器内存一个寻址系统，存储量小多个寻址系统，存储量大消耗较高，难开发易于开发〔多个商业组件可用〕加速高取决于应用2假设按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？基于共享地址空间：并行平台支持一个公共的数据空间，所有处理器都可以访问这些空间。处理器通过修改存储在共享地址空间的数据来实现交互。 基于消息传递：消息传递平台有p个处理节点构成，每个节点有自己的独立地址空间。运行在不同节点上的进程之间的交互必须用消息来完成，称为消息传递。这种消息交换用来传递数据、操作以及使多个进程间的行为同步。3在理想并行计算模型中〔并行随机访问计算机parallelrandomaccessmachine(PRAM),EREW,ERCWCREW,和CRCW表示的意思是什么？EREW：互斥读互斥写，这一类的PRAM独占访问内存单元，不允许并发的读写操作。最弱的PRAM模型，对内存访问提供最小的并发性。CREW：并发读互斥写。对内存单元允许多读，但对内存位置多写是串行的ERCW：互斥读并发写。对内存单元允许多写，但多读是串行的。CRCW：并发读并发写。对内存单元允许多读多写。最强大4能画出多处理机系统中处理单元的根本互连结构图，Mesh,hypercube,网络，注意对顶点编号的要求。Mesh:二维网格中每个维有sqrt〔p〕个节点，p为处理器的数目。hypercube:p为处理器数目，超立方体结构有logP维，每维上有两个节点超立方体的节点编号很有用，有两个p/2各节点的子立方体的编号，就可以一个前面加0一个前面加1实现，这样标号0110的节点和标号0101的节点相隔两个链路因为他们有两位不同，性质以此类推。网络：设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知道对静态网络的常用测度：直径，连通性，二分宽度(bisectionwidth),cost.直径：网络中两个处理节点之间的最长距离称为网络直径。〔越小越好〕连通性：网络中任意两个节点间路径多重性的度量。连通性的一个度量是把一个网络分成两个不连通的网络需要删除的最少弧数目。〔越大越好〕二分宽度：把网络分成两个相等网络时必须删去的最小通信链路数目。〔越大越好〕cost：网络中所需的通信链路的数量或线路数量。6能说出一种解决多处理器系统中cache和内存数据一致性问题的方法。〔侦听和基于目录〕用无效协议维持一致性，并用基于目录的系统来实现一致性协议。基于目录：为全局内存增加一个目录，维护一个bitmap，表示已缓存的处理器及相应的数据项状态。三状态协议含有无效、脏以及共享三种状态。工作原理：当一个处理器P1修改了共享数据，P1修改bitmap,state为dirty,它自己可以继续修改。当另一处理器P2需要读该数据，目录告诉它p1目前拥有该数据，并通知p1更新状态，并把数据送给P2.优点：减少数据无谓的移动和更新〔把空间分的更细〕缺点：连接复杂性高O(mp)7能给出store-and-forwardrouting和cut-throughrouting的思想。通讯费用是如何计算的？延迟时间，ts,th,twstore-and-forwardrouting：在此过程中，消息穿过有多个链路的路径时，路径上的每个中间节点接受和存储完整的消息后，就把消息转发给下一个节点。T=ts+〔mtw+th〕l，th为消息头导致的开销。l为链路数。m为消息字长。cut-throughrouting：在此过程中，消息被分成固定大小的单元，称为数据片。首先从源节点向目的节点发送跟踪程序以建立两点间的连接。连接完成后，数据片就一个接一个的发送。中间节点无需等待所有消息到达就可以发送数据片。当某一数据片被中间节点接收后，该数据片被传到下一节点。与store-and-forwardrouting不同，每个中间节点无需用缓冲区空间存储完整的信息。因此，中间节点只需要使用更少的内存和带宽，速度也快得多。T=ts+mtw+th*l，th为消息头导致的开销。l为链路数。m为消息字长。Tcomm=ts+lth+mtw；1)startuptime(Ts):在数据包上加上必要的头、尾信息，错误检测矫正信息、执行路由算法时间以及建立节点与路由器之间的接口。2〕per-hoptime(Th):nodelatencyfromutov;3)per-word-transfertime(Tw)(每个字的传输时间〕，如果通道带宽为r个字符每秒，每个字符的传输时间为Tw=1/r8对Mesh的X-Y_routing和对Hypercube的E-Cuberouting的路由规那么。Mesh的X-Y_routing：消息首先沿X为出发，直到到达目标节点的列，再沿Y维到达目的节点。其路径长度为L=|Sx-Dx|+|Sy-Dy|;Sx，Sy为源节点坐标；Dx，Dy为目标节点坐标。Hypercube的E-Cuberouting：考虑节点数为p的d维超立方体。令Ps和Pd分别为源节点和目标节点的编号。在E-Cube算法中，节点Ps计算Ps(+)Pd的值并沿k维发送消息，其中k是Ps(+)Pd中的最低非零有效位的位置。每个中间节点Ps收到信息，计算出Ps(+)Pd，再将消息沿着与最低非零有效位对应的维转发，直到消息到达目标节点。9如何把lineararray,mesh和hypercube相互嵌入？G(i,d)函数的计算。·lineararray嵌入到hypercube：含2个节点的lineararray可以嵌入到d维超立方体中，只需把lineararray中的节点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嵌入到lineararray10把复杂网络嵌入的简单网络，能说明些什么问题？其意义是什么？一般对简单网络的带宽是怎么要求的？意义：高维上的网络一般布线复杂，有线的交叉和长短不一等问题。而加宽通讯带宽后的低维互连网络，可以取代高维复杂网络。如果带宽增加到可以抵消互连拥塞，就可按稠密网络一样运行。第三章11dependencygraph的定义及画法。对同一问题dependencygraph的画法是否唯一？dependencygraph表示任务间的依赖关系和任务的执行次序关系。是一种有向无环图，节点表示任务，边表示节点间的依赖性。边<u,v>表示u任务执行完后v任务才能执行。.不唯一13并行算法的粒度定义是什么？粒度大小在理论上和在实际上对并行算法的影响。分解问题得到的任务数量和大小决定了分解的粒度，将任务分解成大量的细小任务称为细粒度，而将任务分解成少量的大任务称为粗粒度。14在进程调度中，把processes影射到processors的根本原那么是什么？减少通讯，…,1〕设法将相互独立的任务映射到不同的进程中以获得最大并发度；2〕确保关键路径上的任务一旦可执行就去执行它们，以使得总计算时间最短3〕映射相互交互的任务到同一进程以便最小化进程间的交互。15在并行算法设计时，有几种把计算分解的技术？能给知名称并能举例说明。·Recursivedecomposition(递归分解〕：可能产生太多任务使程序变慢or快速排序·Datadecomposition:basedontheindependencyofdata〔基于数据独立性分解〕：根据对输出数据的划分来划分任务。例如：矩阵相乘·Explorationdecomposition〔探索分解〕：对应于人工智能中基于解空间探索方法的问题求解，例如迷宫游戏·Speculativedecomposition〔投机分解〕：用于分支语句中，在未能决定分支转向时，并行的计算多个分支，当最终决定转向时，正确的分支对应的计算将被利用，其他的被丢弃。·混合分解，将前面的分解方法组合应用，在计算的不同阶段使用不同的分解方法。例如，快速排序，先数据分解然后再使用递归分解16为了解决由于数据分布密度不均匀问题，能说出3种以上可以帮助使并行任务的负载接近平衡的方法或思路。循环块分配、随机块分配、图划分17能说明dataparallelmodel,taskgraphmodel和workpoolmodel的含义。·dataparallelmodel〔数据并行模型〕：任务被静态或半静态的映射到进程，并且每个任务都对不同的数据进行相似的操作。这种并行性是把同样的操作并发的运用到不同的数据项上产生的结果，因此称为数据并行。·taskgraphmodel〔任务图模型〕：使用任务之间的相互关系来提高本地性或减少交互开销。如果某一问题中，与任务对应的数据量远大于与任务相对应的计算，那么通常用任务图模型来解决此类问题。·workpoolmodel〔工作池模型〕：动态映射任务到进程以保持负载平衡，在这种映射中，任何任务可能由任何进程执行。进程可以产生工作并把它添加到工作池中。第四章18Basiccommunicationoperations对偶的概念是什么？在对通讯原语研究中，为什么强调操作对之间的对偶性？能给出3个以上的对偶原语。·通信操作的对偶是原始操作的逆操作，可以通过逆转原操作中的通信方向和消息序列来完成。·强调对偶的意义在于，研究一个问题，其对偶问题的解可以类似解决。·one-to-allbroadcast/all-to-onereduction,all-to-allbroadcast/all-to-allreduction,scatter/gather19能画出以下操作的示意图，并能解释通信原语所完成的任务是什么onetoallbroadcast;alltoonereductionalltoallbroadcast;alltoallreductionscatter,gather,allreduce,prefixsum，alltoallpersonalizedcommunication.Circularshift·onetoallbroadcast;alltoonereduction一个进程发送相同的数据给其他所有的进程；来自所有进程的数据通过一个相关的操作符组合起来，并被累加到一个目标进程的缓冲区中。·alltoallbroadcast;alltoallreduction多对多播送是一对多播送的推广，其中所有p个节点同时发起一个播送；多对多规约是多对多播送的对偶，p个多对一规约同时进行，每个操作都有不同的目标节点。·scatter,gather,散发：单个节点发送一个大小为m的唯一消息给每一个其他节点，散发与播送的不同点是：播送，所有进程接收到相同的消息；而散发，不同的节点接收到不同的消息。收集：一个节点从其他各个节点那里收集消息，与多对一规约不同，收集操作不涉及数据的组合与规约。·allreduce,prefixsum，全规约：等同于先进性一个多对一规约，再进行一个一对多播送。前缀和：n0n1,…,np-1—>S1,S2,…,Sp-1,其中·alltoallpersonalizedcommunication：每个节点发送一个大小为m的不同消息给其他每个节点，每个节点都发送不同的消息给不同的节点，而在多对多播送中，每个节点发送相同的消息给所有其他节点。·Circularshift,循环q移位定义：在一个p节点的总体中，节点i发送一个数据包给节点〔i+q〕modp，其中0<q<p。移位操作在某些矩阵计算及字符串、图像模式匹配上都有应用20能写出在hypercube上的·onetoallbroadcast/·alltoonereductionP114P115·all-to-allpersonalbroadcast;P131·all-to-allbroadcast;P118算法以及时间复杂性的分析。能举出2种以上在并行编程中的应用例子。第五章21并行算法的分析测度并行算法并行加速比S，效率E和费用cost的计算公式。说明在什么情况下可能出现超线性加速比？何谓费用最正确的并行算法cost-optimal？设计费用最正确的并行算法的思路是什么？·加速比S=Ts/Tp〔Ts串行运行时间，Tp并行运行时间〕理论上，加速比不可能超过处理器数p，但是加速比大于p是可能的，当加速比大于p时，称为超线性加速比；使用高速缓存或基于探索策略的并行算法都可能出现超线性效果。·效率E=S/p=Ts/〔Tp*p〕〔p：处理器的个数〕·Cost=Tp*p,E=Ts/cost.Cost-optimalifcost(n)=O(Ts)—>E=1.cost-optimal:如果在并行计算机上，求解问题的本钱作为属于数据大小的函数，与在单片机上的最快串行算法有着同样的渐进增长，那么称并行系统是本钱最优的。设计费用最优的并行算法思路：①把数据划分为p个局部②用p个处理器分别来处理这p个局部③用并行算法将p个结果合并④根据费用最优得出p的值使p满足n=(plogp)22Amdahl定理的含义？如何证明？Amdahl定理：一个规模为W的问题的串行局部为Ws，那么，不管用多少处理器，W/Ws都是其加速比的上界。证明：因为W=Wp+WsTs=WTp=Ws+Wp/p又因为S=Ts/Tp那么S=W/(Ws+Wp/p)=(W/Ws)/(1+Wp/pWs)因为p->无穷大,那么S->W/Ws第六章23MPI是什么的缩写，MPI是语言还是一个函数库？MPI：theMessagePassingInterfaceMPIisafunctionlibrary，usedwithotherprogramminglanguages24能说出三个MPI的根本函数,并作出解释。MPI_Init初始化MPIMPI_Finalize终止MPIMPI_Comm_size确定进程个数MPI_Comm_rank确定被叫进程的标号MPI_send发送 MPI_Recv接收25MPI程序的根本结构是什么？一般的MPI程序都有MPI说明有哪些？异步模式，松散同步模式·启动和终止MPIMPI_Init(int*argc,char***argv)MPI_Finalize()·获取信息MPI_Comm_size(MPI_Commcomm,int*size)MPI_Comm_rank(MPI_Commcomm,int*rank)·发送和接收消息MPI_Send()MPI_Recv()26MPI程序中容易出现什么形式的死锁？发送与接受顺序上的死锁27MPI是通过什么方法，实现在Mesh上的并行算法？能读懂MPI程序。MPI_Cart_create(comm,2,10,1,1,&comm_2d)从最初申请到的并发进程集合组成2维网格intMPI_Comm_rank(MPI_comm_old,MPI_Comm_new)把过去的id变换成新的2维网格下的id值intMPI_Cart_rank(MPI_Commcomm_cart,int*coords,int*rank)基于2维网格后的2维坐标，得到2维网格下的进程id〕intMPI_Cart_coord(MPI_Commcomm_cart,intrank,intmaxdims,int*coordinate)根据在新的2维环境下进程的id，返回在2维网格下的坐标，coordinate是数组第七章28Pthead的定义是什么？Pthread程序一般要包含哪些语句？IEEE指定的一个标准的线程API，POSIXAPI。POSIX也称为Pthread线程的创立、终止pthread_createpthread_exit等待所有线程运行完毕以便完成结果的合并pthread_join29在pthread中，thread之间的同步，对关键区域的共享使用时是如何实现的？使用mutex-lock(互斥锁)使得各个线程互斥的访问关键区域。要访问关键区域，线程必须首先获得互斥锁并锁定pthread_mutex_lock()，离开关键区域后,要进行解锁pthread_mutex_unlock()，mutex-lock被一个线程锁定后，不允许其他的线程进入关键区域。30Mutex的属性类型以及使用，条件变量和mutex_lock的一起使用。能用Pthread语句写出简单的多线程之间对共享资源的共享的代码。·正常互斥锁：在任意时刻，只允许一个线程锁定互斥锁，已获得互斥锁的线程假设试图再次锁定它，将导致死锁。·递归互斥锁：允许单一的线程屡次锁定互斥锁，线程每锁定一个互斥锁时，锁计数器加1，每次解锁计数器减1，如果任何其他线程想成功锁定一个递归互斥锁，锁计数器必须为0.·错误检查互斥锁：一个线程只能锁定一个互斥锁一次，当线程试图锁定一个已经锁定的互斥锁时，错误检查互斥锁将返回一个错误而不是死锁。31OpenMP是什么形式的API?如何实现并发程序设计的？·OpenMP是一种可以用FORTRAN,C以及C++在共享地址空间计算机上进行编程的指令性的API。OpenMP命令提供对并发，同步以及数据处理的支持，但不需要显式设置互斥锁、条件变量、数据范围以及初始化。·使用parallel命令来创立一组线程 #pragmaompparallel[clauselist] {//parallelsegment}每个线程执行parallelsegment中内容Parallel和命令for、sections一起使用实现迭代和任务的并发。·for命令用来在多个线程间分割并行迭代空间，一般形式如下： #pragmaompfor[clauselist]/*forloop*/·sections命令用于对非循环的并行任务分配,形式如下： #pragmaompsections[clauselist] { #pragmaompsection { taskA(); } #pragmaompsection { taskB(); }… } 每个段〔即为相应的任务〕分配给一个线程32能用OpenMP写出矩阵与向量，矩阵之间和易于并行计算的程序代码。矩阵乘#pragmaompparalleldefault(private)shared(a,b,c,dim)num_threads(4)#pragmaompforschedule(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);}}}第八章并发实现矩阵与向量的乘法能给出如何实现矩阵转置的算法。能写出Cannon，Fox和简单矩阵乘法算法。33并发实现矩阵与向量的乘法。AX·带状划分的矩阵-向量乘法划分(行带状划分):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(一到多播送)；②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi；注:对p<n情形,p个处理器排成的二维网孔，算法中Pi,i向Pj,i播送X中相应的个分量34能给出如何实现矩阵转置的算法。算法:①按mesh连接进行块转置(不同处理器间)②进行块内转置(同一处理器内)35能写出Cannon，Fox和简单矩阵乘法算法。CannonP255·初始时，把子矩阵Aij和Bij分配给处理器Pij①矩阵A的第i行循环左移i步，矩阵B的第j列循环上移j步；t=；②各处理器A块与B块进行乘-加运算；t--；③if〔t<>0〕,A矩阵每行循环左移1步，B矩阵每列循环上移1步上面算法中，每个进程Pij中一共进行了次Aik与Bkj〔〕的相乘，从而完成矩阵A和B的乘法运算Fox课件·初始时，把子矩阵Aij和Bij分配给进程Pij〔同Cannon〕①Ai,i向所在行的其他处理器进行一到多播送；②各处理器将收到的A块与原有的B块进行乘-加运算;③B块向上循环移动一步;④如果Ai,j是上次第i行播送的块，本次选择向所在行的其他处理器进行一到多播送;⑤转②执行-1次;第九章36奇、偶排序的并行算法，能表达双调〔Bitonic〕排序的思路以及画法。知道该算法是如何在超立方体上实现的。·奇-偶排序的并行算法考虑每个进程一个元素的情况。在奇数排序阶段，每个奇数下标的进程将其元素与其右边的相邻元素进行比拟-交换；同样，在偶数排序阶段，每个偶数下标的进程将其元素与其右边的相邻元素进行比拟-交换。·双调排序s=a0,a1,…,an-1是一个双调序列并且a0≤a1≤···≤an/2-1andan/2≥an/2+1≥···≥an-1；令子序列s1=min{a0,an/2},min{a1,an/2+1},…,min{an/2-1,an-1}s2=max{a0,an/2},max{a1,an/2+1},…,max{an/2-1,an-1}那么s1与s2都是双调序列且s1中每个元素都小于s2中元素。这样原问题s排序就化简为两个较小的双调序列排序，并将结果连接起来。上述一个双调序列划分成两个较小双调序列的操作称作双调分裂。n个元素的序列进行logn次双调分裂即可完成排序。将任意序列转化为双调序列并最终完成排序//label：进程标号d：超立方体维数第十章37最小生成树和最短路径算法的并行实现；P319P321·最小生成树Prim算法：设G〔V，E〕为加权无向连通图，A=〔ai，j〕为加权邻接矩阵。用Vt来保存最小生成树构造过程中的顶点。维护一个数组d，对于每个顶点，d[v]中保存从Vt中的任何顶点到顶点v的边中最小的权值。任选一点r参加Vt，d[r]=0②对于所有，假设边〔r，v〕存在，那么令d[v]=w(r,v)，否那么令d[v]=③whileVtVdo找到一个顶点u满足d[u]=min{d[v]|}; 将u参加到集合Vt； 对于所有，更新d[v]的值；endwhile并行形式：令p为进程数，将集合V划分为p个子集，每个子集分配给不同的进程。每个进程Pi存储数组d中与Vi对应的局部。在while循环的每次迭代中，每个进程Pi计算d[u]=min{d[v]|}，对所有的d[u]进行多对一规约操作得到全局最小值，并存储在P0中。此时进程P0中保存新的顶点u，它将被插入到Vt中。进程P0使用一对多播送将u播送给所有的进程。负责顶点u的进程将u标记为属于集合Vt，最后每个进程对自己本地的顶