并行计算程序设计

1、关 雪 峰测绘遥感国家重点实验室Warm Up本科生院高等数学大课结束，收集500张试卷需要批阅。武汉神龙汽车生成雪铁龙C5轿车，有发动机、轿厢、底盘、总装等工艺。第二章 并行程序设计主要内容一基本概念二并行编程模型三并行程序设计基本流程四并行计算的性能评价相关概念并行处理(parallel Processing)：在同一时间段内，在多个处理机中执行同一任务的不同部分。多道处理(multiprocessing)：强调由一台计算机利用一个处理机同时交错地执行多道程序。并发处理(concurrent, concurrency)：与多道处理类似。相关概念数据并行 (data parallelism)

2、：利用多个处理器对一个数据集上的不同元素同时进行相同的操作。任务并行 (Function/Task parallelism)：为了完成一个任务要对不同的数据元素同时进行不同的操作。相关概念节点（Node）A standalone computer in a box. Usually comprised of multiple CPUs/processors/cores, memory, network interfaces, etc. Nodes are networked together to comprise a cluster.CPU / Socket / Processor / Co

3、reCPU / Socket / Processor / Core处理器单元（Processing ElementProcessing Element）任务（Task）A logically discrete section of computational work. A task is typically a program or program-like set of instructions that is executed by a processor. A parallel program consists of multiple tasks running on multiple

4、 processors.作业（Job Job ）& &任务（TaskTask）相关概念通信（Communication）：并行任务都需要交换数据。有几种方法可以完成，例如：共享内存总线、网络传输，然而不管用什么方法，真实的数据交换事件通常与通信相关。计算/通信比（Communication to Computation Ratio，C-to-C Ratio）: Represents the amount of resulting communication between tasks of a parallel program。相关概念同步（Synchronization）：实

5、时并行任务的调度通常与通信相关。总是通过建立一个程序内的同步点来完成，一个任务在这个程序点上等待，直到另一个任务到达相同的逻辑设备点是才能继续执行。同步至少要等待一个任务，致使并行程序的执行时间增加。相关概念粒度（Granularity）：在并行计算中，粒度是用来定性描述离散任务中计算量的指标。粗糙级（Coarse）：在两个通信事件之间可以完成相对大量的可计算工作。精细级（Fine）：在两个通信事件之间只能完成相对较少量的可计算工作相关概念Parallel Overhead（额外开销）The amount of time required to coordinate parallel task

6、s, as opposed to doing useful work. Parallel overhead can include factors such as:Task start-up timeSynchronizationsData communicationsSoftware overhead imposed by parallel languages, libraries, operating system, etc.Task termination time相关概念Scalability-Refers to a parallel systems (hardware and/or

7、software) ability to demonstrate a proportionate increase in parallel speedup with the addition of more resources. Factors that contribute to scalability include:Hardware - particularly memory-cpu bandwidths and network communication propertiesApplication algorithmParallel overhead relatedCharacteri

8、stics of your specific application多线程MPICUDAHadoopSPARK第二章 并行程序设计主要内容一基本概念二并行编程模型三并行程序设计基本流程四并行计算的性能评价并行编程模型并行编程模型ThreadsDistributed Memory / Message PassingData ParallelHybrid多线程 线程模型的构成如下：操作系统调度主程序开始运行，加载所有必要 的系统资源和用户资源开始执行。创建一些可以被操作系统调度的并行任务（线程）去执行。每次线程都有自己的数据，而且共享整个主程序的资源。线程之间通过全局内存进行通信。这个需要同步构造

9、来确保多个线程不会同时更新同一块全局内存。线程执行完了就自动销毁，但是主程序在应用程序完成之前一直存在，维护必要的共享资源。多线程多线程开发模型通常共享内存体系架构和操作系统密切相关。典型代表：典型代表：POSIX Threads OpenMPIntel threading building blocks（Intel TBB）消息传递模型消息传递模型（Message Passing Model）消息传递模型面向分布式内存系统架构消息传递模型消息传递模型特征：A set of tasks that use their own local memory during computation. Ta

10、sks exchange data through communications by sending and receiving messages.Data transfer usually requires cooperative operations to be performed by each process. For example, a send operation must have a matching receive operation典型代表： Message Passing Interface (MPI) Message Passing Interface (MPI)数

11、据并行数据并行特征：并行工作集中在对某数据集执行相同的操作，而且数据集通常结构一致，如大型数组。相同操作通常称之为Kernel。典型代表：Fortran 95混合模式这个模型中，是由两个或多个模型组合在一起实现的。当前通用的混合模型的例子就是：由消息传递模型（MPI）和线程模型（POSIX）或者共享内存模型（OpenMP）组成而成。MPI + OpenMP并行层次与代码粒度甚细粒度指令级并行细粒度数据级并行中粒度控制级并行粗粒度任务级并行国家高性能计算中心（合肥）22222022-5-15第二章 并行程序设计主要内容一基本概念二并行编程模型三并行程序设计基本流程四并行计算的性能评价并行程序开发

12、策略自动并行化自动并行化通常依赖于编译器（自动并行化通常依赖于编译器（CompilerCompiler）The compiler analyzes the source code and identifies opportunities for parallelism.The analysis includes identifying inhibitors to parallelism and possibly a cost weighting on whether or not the parallelism would actually improve performance.Loops

13、(do, for) are the most frequent target for automatic parallelization.for (i=0;i=MAX;i+) ci=ai+bi;Automatic Automatic VectorizationVectorization参考Intel Compilers Guided Auto Parallelization并行程序库通常可以直接借助于并行数值计算库通常可以直接借助于并行数值计算库Scalapck（Scalable Linear Algebra PACKage）ScaLAPACK is a library of high-per

14、formance linear algebra routines for parallel distributed memory machines. ScaLAPACK solves dense and banded linear systems, least squares problems, eigenvalue problems, and singular value problems. CULA, an implementation of the Linear Algebra PACKage (LAPACK) interface for CUDA-enabled NVIDIA grap

15、hics processing units (GPUs).CULA is a next-generation linear algebra package that uses the GPU as a co-processor to achieve speedups over existing linear algebra packages. CULA provides the same functionality you receive with your existing package, only at a greater speed.手动并行（Manual Parallelizatio

16、n）Understand the Problem and the ProgramUnderstand the Problem and the ProgramDesign & ImplementationDesign & ImplementationDecomposition CommunicationsSynchronizationData DependenciesLoad BalancingGranularityI/ODebuggingDebuggingPerformance Analysis and TuningPerformance Analysis and Tuning

17、并行方法（Parallelization Methodology ）Fosters MethodologyPartitioningCommunicationAgglomerationMapping Massingills Methodology Finding Concurrency data vs. function Algorithm Structure pipeline, replicate Supporting Structure SPMD, fork/join Implementation Mechanisms barriers, locksAlgorithm Review了解问题，

18、确定hotspotKnow where most of the real work is being done. The majority of scientific and technical programs usually accomplish most of their work in a few places.Profilers and performance analysis tools can help hereFocus on parallelizing the hotspots and ignore those sections of the program that acc

19、ount for little CPU usageAlgorithm Review确定瓶颈（bottleneck）Identify bottlenecks in the program:Are there areas that are disproportionately slow, or cause parallelizable work to halt or be deferred? For example, I/O is usually something that slows a program down.May be possible to restructure the progr

20、am or use a different algorithm to reduce or eliminate unnecessary slow areas .并行应用编程过程PCAM设计并行应用的四个阶段划分(Partitioning)通信(Communication)组合(Agglomeration)映射(Mapping)划分：分解成小的任务，开拓并发性；通信：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高并行性能。 PCAM设计过程 划分方法描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功

21、能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：域分解(Domain Decomposition)功能分解(Functional Decomposition)域分解 划分的对象是数据，可以是程序中的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通信；域分解 示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：2022-5-15域分解 常见空间数据划分方式域分解 常见空间数据划分方式-空间填充曲线域分解 不规则区域的分解示

22、例：38382022-5-15域分解 常见空间数据划分方式-不规则四叉分解树域分解 常见空间数据划分方式-kd-Tree功能分解 划分的对象是计算（亦称为任务分解或计算划分），将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着存在大量的通信开销，要重新进行域分解和功能分解；功能分解是一种更深层次的分解。功能分解 示例1：搜索树示例2：气候模型2022-5-15划分判据 划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解

23、，是否合理？Loop carried data dependence划分判据数据依赖Data DependenciesData DependenciesA dependence exists between program statements when the order of statement execution affects the results of the program.A data dependence results from multiple use of the same location(s) in storage by different tasks.Depend

24、encies are important to parallel programming because they are one of the primary inhibitors to parallelism.For j =1 to 100For j =1 to 100A(J) = A(J-1) A(J) = A(J-1) * * 2.0 2.0 NextNext j j数据依赖Assume task S2 follows task S1 in sequential Assume task S2 follows task S1 in sequential program orderprog

25、ram orderTrue Data or Flow DependenceTrue Data or Flow Dependence: Task S2 is data dependent on task S1 if an execution path exists from S1 to S2 and if at least one output variable of S1 feeds in as an input operand used by S2 Represented by S1 S2 in task dependency graphsAnti-dependence: Anti-depe

26、ndence: Task S2 is antidependent on S1, if S2 follows S1 in program order and if the output of S2 overlaps the input of S1 Represented by S1 | S2 in dependency graphsOutput dependence: Output dependence: Two tasks S1, S2 are output dependent if they produce the same output variables Represented by S

27、1 O S2 in task dependency graphs数据依赖True Flow DependenceTask S1 produces one or more results used by task S2Task Dependency Graph Representation数据依赖Anti-DependenceTask S1 reads one or more values from one or more names (registers or memory locations) Task S2 writes one or more values to the same nam

28、es (same registers or memory locations read by S1) Then task S2 is said to be anti-dependent on task S1Task Dependency Graph Representation数据依赖Output (or Write) DependenceBoth tasks S1, S2 write to the same a name or names (same registers or memory locations) Then task S2 is said to be output-depend

29、ent on task S1Task Dependency Graph Representation数据依赖独立条件Let Pi and Pj be two program segments. Bernsteins conditionsBernsteins conditions describe when the two are independent and can be executed in parallel. For Pi, let Ii be all of the input variables and Oi the output variables, and likewise fo

30、r Pj. P i and Pj are independent if they satisfy 通信分析通信是PCAM设计过程的重要阶段；划分产生的任务集合，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信；功能分解确定了任务之间的数据流；任务是并发执行的，通信则限制了这种并发性； 四种通信模式局部/全局通信结构化/非结构化通信静态/动态通信同步/异步通信局部通信通信限制在一个邻域内，Point-to-point 全局通信通信非局部的例如：All to AllMaster-Worker结构化通信每个任务的通信模式是相同的；下面是否存在一个相同通信模式？非结构化通信没有一个统一的

31、通信模式例如：无结构化网格2022-5-15静态/动态通信通信伙伴的身份不随时间改变；动态通信中，通信伙伴的身份则可能由运行时所计算的数据决定且是可变的。 同步/异步通信同步通信时，接收方和发送方协同操作；异步通信中，接收方获取数据无需与发送方协同。Synchronous communicationsSynchronous communications are often referred to asblockingblocking communications since other work must wait until the communications have completed

32、.同步通信保证数据的一致性Asynchronous communicationsAsynchronous communications allow tasks to transfer data independently from one another.Asynchronous communications are often referred to asnon-blockingnon-blocking communications since other work can be done while the communications are taking place.Interleav

33、ing computation with communication is the single greatest benefit for using asynchronous communications.异步通信支持通信与计算的叠加通信判据 所有任务是否执行大致相当的通信?是否尽可能的局部通信？通信操作是否能并行执行?同步任务的计算能否并行执行？通信同步通信除了数据传递功能以外，重要的功能就是同步。同步基本类型BarrierMutex & LockSignal & semaphore同步BarrierUsually implies that all tasks are in

34、volvedEach task performs its work until it reaches the barrier. It then stops, or blocks.When the last task reaches the barrier, all tasks are synchronized.What happens from here varies. Often, a serial section of work must be done. In other cases, the tasks are automatically released to continue th

35、eir work.同步Lock / semaphoreCan involve any number of tasksTypically used to serialize (protect) access to global data or a section of code. Only one task at a time may use (own) the lock / semaphore / flag.The first task to acquire the lock sets it. This task can then safely (serially) access the pr

36、otected data or code.Other tasks can attempt to acquire the lock but must wait until the task that owns the lock releases it.Can be blocking or non-blocking任务组合 组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通信成本；保持映射和扩展的灵活性，降低软件工程成本；增加并行粒度A large number o

37、f fine-grained tasks does not necessarily produce an efficient parallel algorithm.Communication costs and task creation costs are overhead that canbe reduced by increasing granularity.组合判据 增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？处理器映射 每个任务要映射到具体的处理器，定位到运

38、行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务 不同的处理器任务之间存在高通信的 同一处理器映射实际是一种权衡，属于NP完全问题；负载平衡 静态的：事先确定；概率的：随机确定；动态的：执行期间动态负载；基于域分解的：递归对剖局部算法概率方法循环映射任务分配与调度负载平衡与任务分配/调度密切相关，任务分配通常有静态的和动态的两种方法。静态分配一般是任务到进程的算术映射。静态分配的优点是没有运行时任务管理的开销，但为了实现负载平衡，要求不同任务的工作量和处理器的性能是可以预测的并且拥有足够的可供分配的任务。静态调度静态调度（Static Sch

39、eduling）方案一般是静态地为每个处理器分配个连续的循环迭代，其中为迭代次数，是处理器数。也可以采用轮转轮转（Round-robin）的方式来给处理器分配任务，即将第i个循环迭代分配给第i mod p个处理器。任务分配与调度动态分配与调度相对灵活，可以运行时在不同处理器间动态地进行负载的调整。各种动态调度动态调度（Dynamic Scheduling）技术是并行计算研究的热点，包括基本自调度基本自调度SSSS（Self Scheduling）、块自调度块自调度BSSBSS（Block Self Scheduling）、 指导自调度指导自调度GSSGSS（Guided Self Schedu

40、ling）、因子分解调度因子分解调度FSFS（Factoring Scheduling）、梯形自调度梯形自调度TSSTSS（Trapezoid Self Scheduling）、 耦合调度耦合调度ASAS（Affinity Scheduling）、安全自调度安全自调度SSSSSS（Safe Self Scheduling）和自适应耦合调度自适应耦合调度AASAAS（Adapt Affinity Scheduling）。映射判据 采用集中式负载平衡方案，是否存在通信瓶颈？采用动态负载平衡方案，调度策略的成本如何？调试与调优调试（Debugging）-保证程序正确性Debugging parall

41、el codes can be incredibly difficult, particularly as codes scale upwards。多线程：Intel Parallel Studio XETotalView Visual StudioEclipse调试与调优调试（Debugging） Quickly find memory leaks and memory allocation errors Locate difficult-to-find threading errors like data races and deadlocks Detect out of bounds a

42、ccesses and dangling pointers调试与调优性能分析与调优（Performance Analysis and Tuning）As with debugging, analyzing and tuning parallel program performance can be much more challenging 调试与调优调试（Debugging）工具TAU: /research/tau/docs.phpHPCToolkit: /documentation.htmlOpen|S

43、peedshop: /wp/Vampir / Vampirtrace: http:/vampir.eu/Valgrind: /PAPI: /papi/mpitrace /tutorials/bgq/index.html#mpitracempiP: http:/ http:/ Delaunay Triangulation该算法通过对排序的点集递归二分，直到划分的每组只有23个点，2个点可以直接生成直线， 3个点为三角形

44、，然后对分组DT结果递归的合并，直至得到最终的DTMerge Process during D&C DTcan contain 23 points here, and also can be generalized to represent a rectangle blockDifferent job granularity & Different partition support(kd tree, quad tree, grid, strips,)The job kd tree of a D&C DTThe job queue created by a breadt

45、h-first tree traversal The job queue created by a breadth-first tree traversal Parallel pipelines mappingThreadTimeHuayi Wu, Xuefeng Guan and Jianya Gong (2011). ParaStream: A parallel streaming Delaunay triangulation algorithm for LiDAR Points on Multicore Architectures. Computers & Geosciences

46、, 37(9):1355-1363.第二章 并行程序设计主要内容一基本概念二并行编程模型三并行程序执行模式四并行程序设计基本流程五并行计算的性能评价并行计算的性能评价加速比定律适用于固定计算负载的Amdahl定律适用于扩展问题的 Gustsfson 定律相关概念（并行算法的）加速比 (speedup) 或加速系数(speedup factor)：完成计算的最佳串行算法所需的时间与完成相同任务的并行算法所需的时间之比。并行效率 (parallel efficiency)：加速比与所用处理机个数之比。并行效率表示在并行机执行并行算法时，平均每个处理机的执行效率。为了对一个并行任务评估，通常我们使用

47、在单处理机上运行最快的已知算法的执行时间与并行任务的执行时间进行比较，即加速比。加速比 S(p) =使用单处理器最佳串行算法执行时间使用单处理器最佳串行算法执行时间在具有在具有p p台处理机的系统上算法的执行时间台处理机的系统上算法的执行时间对于 p 个处理器来说，其最大加速比为 p。当计算任务可被分成相等执行时间的进程时，一个进程映射到一个处理器上时，若此时没有其它开销就可获得最大加速比 p。一般表示p：并行系统中处理器的个数 (the number of processors)W ：问题规模或工作负载 (workload)Ws ：应用问题中必须串行执行的部分Wp ：应用问题中可并行执行的部

48、分 W = Ws + Wpf ：串行执行部分 Ws 占全部工作负载 W 的比例 f = Ws / W 一般表示ts ：整个任务在串行机上执行所需的时间tp ：整个任务在并行机上执行所需的时间Ts：完成 Ws 所需要的时间Tp：在并行机上完成 Wp 所需要的时间S ：加速比：S(p) = ts / tp E ：并行效率：E = S(p) / p * 100%加速比定律适用于固定计算负载的Amdahl定律适用于扩展问题的 Gustsfson 定律适用于固定计算负载的Amdahl定律当并行计算机中处理器数目增加时，固定负载就被分配给更多的处理器去并行执行，其主要目的是想尽可能快地的得出结果，即计算任

49、务的实时性要求更高。Amdahl 定律 (1967) ：设 f 为给定计算任务中必须串行执行的部分所占比例 (0f 1)，对于一台含有 p 个处理器的并行计算机，其最大可能的加速比为：S =1f + (1-f) / pts( 1-f ) tsf ts多处理机多处理机：p个个处处理理机机单处理机单处理机串行部分串行部分可并行化部分可并行化部分tp( 1-f ) ts / pS =Ws + WpWs + Wp/p=f W + (1-f) Wf W +(1-f) W) /p=f + (1-f)f +(1-f) /p=1f +(1-f) /pS =ts f*ts +(1-f)ts/p=1f +(1-f

50、) /p在假设算法中每个计算步的执行时间是相等的情况在假设算法中每个计算步的执行时间是相等的情况下，算法的执行时间也常用下，算法的执行时间也常用计算步计算步来计算。来计算。Wp Wp Wp Wp Wp Wp Wp WpWs Ws Ws Ws Ws Ws Ws Ws 1 2 3 4 5 6 7 8 处理机个数处理机个数W 工作负载工作负载 Ts TsTs Ts Ts Ts Ts TsTpTpTpTpTpTpTpTp 1 2 3 4 5 6 7 8 处理机个数处理机个数T 执行时间执行时间S =ts f*ts +(1-f)ts/p=1f +(1-f) /p适用于扩展问题的Gustafson定律Am

51、dahl 定律的一个主要缺点：固定负载妨碍了并行机性能可扩展性的开发。有些计算任务要求在给定的时间内希望提高计算精度，即在给定的时间内增加处理器的数量使计算量提高，如我们希望数值天气预报的数据采样模型的单位更小。在精度占主导位置的应用领域中，我们希望象在小机器上解小问题一样，在大机器上能解规模大的问题，并使二者所花费的时间大体相同。 适用于扩展问题的Gustsfson定律Gustafson定律 (1988)：对于一台并行计算机，当问题中可并行部分扩大 p 倍时，其加速比也随之增长：S= f + (1-f) p =Ws + pWpWs + WpS =Ws + pWpWs + pWp/p若我们用若我们用 f 来表示，可将上式变为：来表示，可将上式变为：S =fW + p(1-f)WfW + p(1-f)W/p =f + p(1-f)f + (1-f)S= f + (1-f) p 1 2 3 4 5 6 7 8 处理机个数处理机个数W 工作负载工作负载WsWsWsWsWsWsWsWsWpWpWpWpWpWpWpWpTp Tp Tp Tp Tp Tp Tp TpTs Ts Ts Ts Ts Ts Ts Ts 1 2 3 4 5 6 7 8 处