并行程序设计Chapter-4

第四章并行抽象,刘轶北京航空航天大学计算机学院,4.1并行编程基本知识,4.1并行编程基本知识,一、数据和任务并行并行计算的两种类型数据并行(dataparallel)同时对不同数据项进行相同操作的并行并行量随数据规模而增长并行性可扩展例：矩阵乘法任务并行(taskparallel)同时完成不同计算或任务的并行任务数固定并行性不可扩展例：网络服务很多计算是混合型的，既有数据并行，又有任务并行,4.1并行编程基本知识,二、Peril-L记号一种用于描述并行算法的伪代码语言，在C语言基础上扩展而来并行线程通过forall语句引入多线程,4.1并行编程基本知识,同步和协同用于线程之间的同步两种同步机制：互斥和barrier互斥块(exclusiveblock)障栅(barrier),4.1并行编程基本知识,存储器模型提供两个地址空间全局地址空间：可被所有线程访问局部地址空间：只能被一个线程访问forall语句内定义的变量位于局部地址空间，之外定义的变量位于全局地址空间假设全局变量访问时延，局部变量的访问可在单位时间内完成Peril-L约定：全局地址空间中的变量加下划线将数据从全局地址空间映射到局部地址空间：localize()函数,4.1并行编程基本知识,规约(reduce)和扫描(scan)规约(reduce)组合一组值而产生单个值如对数的序列求和：规约求和扫描(scan)：并行前缀操作：对一个数的序列求另一个序列例：+；*；whennecessary,theconcurrencyinthealgorithmcanbeaggregatedintosequentialcodetomatchtheavailableparallelismimplementedinthehardware缺点：实际效果不一定理想(并行粒度过细),无限并行性示例,3.并行性的三种表示之三：可扩展并行性(Scalableparallelism),可扩展并行性,主要特点：将全局数据局部化；使用拥有者计算的规则优点：各并行线程之间没有交互，直到最后的规约，可扩展性很好,4.2并行性的表示,3.并行性的三种表示之三：可扩展并行性(Scalableparallelism)确定随着计算规模的增大，问题的各组成部分如何增长数据结构、工作负载等定义一个充实(substantial)子问题集S，将大小为s的自然(natural)求解单位分配给每个子问题尽可能独立(independent)地求解这些子问题强调“充实”子问题：旨在保证一个线程有足够的局部工作，以分担并行开销(如通信)强调“自然”子问题：对一个计算进行划分往往不容易做到很平滑强调“独立”子问题：减少子问题间的交互可减少闲置时间和通信优点：能够充分利用局部性，较好地适应问题规模和底层硬件的变化缺点：程序较复杂，实现难度较大,4.3可扩展算法,本节内容主要针对数据并行，即数据并行的可扩展性数据并行的一个重要问题：如何将数据分配给并行进程/线程指导性原则：让每个进程/线程负责尽可能大的独立计算块，且这些块之间的交互尽可能少,4.3可扩展算法,一、独立计算块理想的并行计算由多个独立计算块组成独立计算快：大的、独立的计算块，块之间没有交互独立计算块所对应的并行进程/线程间几乎没有交互，可充分发挥并行性甚至能够在Internet环境下进行并行计算完全由独立计算块组成的计算很少见几乎所有的计算都需要进程/线程间交互，交互的数量在很大程度上影响着程序性能独立计算块的借鉴意义如果更多地关注计算块，就可以提升并行程序的可扩展性一般而言，计算块越大越好可减少进程/线程间的相关性指导性原则：让每个进程/线程负责尽可能大的独立计算块，且这些块之间的交互尽可能少,二、Schwartz算法独立计算块指导原则在Schwartz算法上有很好的体现Schwartz算法一种树操作(treeoperation)算法，可用于规约等操作如果用P个进程对n个数进行+-规约操作，有两种实现方法：引入逻辑线程实现组合树，成对计算，充分发掘并行性每个进程负责n/P个数据的局部计算，然后按树结构规约分析表明，第2种方法性能优于第1种原因：进程在一个紧凑循环中求和要优于在多个线程间切换,用树结构连接数据项(数据成对计算，每个计算对应一个线程),用树结构连接进程(每个进程负责一组数据的计算),4.3可扩展算法,二、Schwartz算法Schwartz算法进一步说明：可扩展并行方法优于无限并行方法局部计算体现出了独立计算块的原则Schwartz算法实际上是局部计算和全局并行的组合推而广之，对于基于树的算法(如规约、扫描)：应将局部操作与P个叶节点的全局组合树结合使用具有更高扇出度的树,4.3可扩展算法,三、静态为进程分配工作数据到进程/线程的分配方式对程序性能影响很大计算时的数据局部性问题如果进程/线程处理的数据在内存中连续存储，则数据的局部性更好，有助于提升程序性能进程/线程间通信量问题如果进程/线程相互间共享/交换数据较少，则能够更独立地进行计算，进程/线程间互斥/同步/通信量较少，有助于提升程序性能块分配为了充分利用局部性，应尽可能将数据中的连续计算部分分配给同一进程对一维数组，数据应按索引连续分配到进程对二维数组，有按二维块划分和按行划分两种方式如果二维数组中元素的计算依赖于邻居结点值，则二维块分配方式更优，原因：有利于减少进程间通信,每个进程与其他进程交换数据量按块分配方案：16按行分配方案：32如数组扩展为1024x1024，进程个数256按块分配方案：256按行分配方案：2048按行分配的优缺点分析进程间通信数据量大，但仅需2条消息，而按块分配需4条消息问题：得益是固定的，不具可扩展性按块分配的扩展性更好,为16个进程分配16x16数组的两种方案,灰色块表示分配给某一进程的数据黑色块表示需与邻居进程通信获得的数据,一种典型的模板计算(stencilcomputation)Bi,j=(Ai-1,j+Ai,j+1+Ai+1,j+Ai,j-1)/4.0,4.3可扩展算法,三、静态为进程分配工作重叠区域在二维数组计算中，数据的计算依赖于其邻居数据，产生了重叠区域(overlapregion)可以在分配存储时，分配额外的存储空间，存放重叠区域的数据，并使这些数据连续存储作用：可减少进程间通信,循环分配和块循环分配在某些计算中，块分配可能对负载平衡(load-balance)不利以LU分解为例将一个矩阵分解为2个矩阵的乘积，以求解线性方程组在矩阵上迭代，每次迭代会求得一行和一列的结果工作量在每次迭代后都会减少，按块分配的方法会导致某些进程(处理器)在进行一段时间后处于空闲状态为保证负载均衡，可以采用块-循环分配的方法，将块循环分配到各进程,4.3可扩展算法,三、静态为进程分配工作不规则分配有很多算法使用非数组的其他数据结构如非结构化网格(unstructuredgrid)，通常由三角形组成，常用于有限元计算仍可使用类似的原理，如交互发生在网格边界，可以得出进程间交互较小的划分方案划分方法分为两种：基于几何的划分基于图像理论的划分由于数据访问是非规则的，常常要到计算时才能得知需要哪些非本地数据为避免零散地获取非本地数据(消息数量众多，时延巨大)，可采用检查者/执行者(inspector/executor)技术，每次迭代的计算前，先检查需要哪些非本地数据，将其成批获取后，执行者再进行计算,四、动态为进程分配工作在很多应用中，难以进行静态的工作分配常见情形：新的工作在计算过程中产生，即后续的计算是通过当前计算得到的要求动态为进程/线程分配工作可以使用工作队列(workqueue)为进程动态分配工作队列中存放待计算的工作进程/线程动态从队列中取出工作，进行计算，将计算过程中产生的新工作添加到队列中通常可采用先进先出队列(FIFO)，此时各进程/线程构成了典型的生产者-消费者关系也可根据需要，采用后进先出(LIFO)、随机或优先级队列,工作队列是全局共享数据结构，可能需互斥访问,4.3可扩展算法,五、树树能够体现层次结构，是重要的数据结构对树结构进行并行计算时面临的问题树常用指针来表示，而