《并行程序设计chapter-4》由会员分享，可在线阅读，更多相关《并行程序设计chapter-4（23页珍藏版）》请在金锄头文库上搜索。
1、第四章 并行抽象刘 轶 北京航空航天大学 计算机学院4.1 并行编程基本知识4.1并行编程基本知识一、数据和任务并行 并行计算的两种类型 数据并行(data parallel) 同时对不同数据项进行相同操作的并行 并行量随数据规模而增长 并行性可扩展 例：矩阵乘法 任务并行(task parallel) 同时完成不同计算或任务的并行 任务数固定 并行性不可扩展 例：网络服务 很多计算是混合型的，既有数据并行，又有任务并 行4.1并行编程基本知识二、Peril-L记号 一种用于描述并行算法的伪代码语言，在C语言基础上 扩展而来 并行线程 通过forall语句引入多线程forall ( in ()
2、 例：显示12行信息，每行信息的显示并行进行 forall ( index in ( 112 ) ) printf( “Hello world from thread %in”, index ); 运行结果？4.1并行编程基本知识 同步和协同 用于线程之间的同步 两种同步机制：互斥和barrier互斥块(exclusive block) 障栅(barrier)exclusive 语义：保证每次只有一个线程执行，如果一 个线程正在执行，其他线程只能等待例： forall ( index in ( 112 ) ) execlusiveprintf( “Hello world from thread
3、 %in”, index ); barrier 语义：使线程停止直到所有线程到达barrier例： forall ( index in ( 112 ) ) printf( “tweedle deen” );barrier;printf( “tweedle dumn” ); 4.1并行编程基本知识 存储器模型 提供两个地址空间 全局地址空间：可被所有线程访问 局部地址空间：只能被一个线程访问 forall语句内定义的变量位于局部地址空间，之外定义的变量位于全局地址 空间 假设全局变量访问时延，局部变量的访问可在单位时间内完成 Peril-L约定：全局地址空间中的变量加下划线 将数据从全局地址空间
4、映射到局部地址空间：localize()函数例： int datan; forall ( index in ( 0n-1 ) ) if ( dataindex 0 )dataindex = -dataindex; 4.1并行编程基本知识 规约(reduce)和扫描(scan) 规约(reduce) 组合一组值而产生单个值 如对数的序列求和：规约求和 扫描(scan)： 并行前缀操作：对一个数的序列求另一个序列 例：+；*； 全局数据 int seg = ceil( length / 4 ); forall ( j in ( 03 ) ) int priv_count = 0; 局部累加和int
5、 i, myBase = index * lengthPer;for ( i = u * seg; i min( length, j*(seg+1); i+ )if ( arrayi = 3 )priv_count+;exclusive total += priv_count; 累加到全局和 4.2并行性的表示2. 并行性的三种表示之二：无限并行性(Unlimited parallelism) 假定硬件能提供无限的并行性，编程时，尽可能地把算法中的并发性聚 集为顺序代码，以匹配硬件中的可用并行性assume that underlying hardware provides unlimited
6、 parallelism and therefore to expose all possible parallelism; when necessary, the concurrency in the algorithm can be aggregated into sequential code to match the available parallelism implemented in the hardware 缺点：实际效果不一定理想(并行粒度过细)int count = 0; forall ( i in ( 0n-1 ) ) count = +/(arrayi = 3 ? 1
7、: 0 ); 无限并行性示例3. 并行性的三种表示之三：可扩展并行性(Scalable parallelism)int arraylength; 全局数据 int t; 期望的线程数 int total; 计算结果 forall ( j in ( 0t-1 ) ) int size = mySize( array, 0 ); 计算全局数据本地部分的大小int myDatasize = localize( array ); 将全局数据映射为局部变量int i, priv_count = 0; 局部累加和for ( i = 0; i size; i+ )if ( myDatai = 3 )priv
8、_count+;total = +/priv_count; 累加到全局和 可扩展并行性主要特点： 将全局数据局部化； 使用拥有者计算的规则 优点：各并行线程之间没有交互，直到最后的规约，可扩展性很好4.2并行性的表示3. 并行性的三种表示之三：可扩展并行性(Scalable parallelism)确定随着计算规模的增大，问题的各组成部分如何增长 数据结构、工作负载等 定义一个充实(substantial)子问题集S，将大小为s的自然(natural)求解单 位分配给每个子问题 尽可能独立(independent)地求解这些子问题 强调“充实”子问题：旨在保证一个线程有足够的局部工作，以分担并
9、行 开销(如通信) 强调“自然”子问题：对一个计算进行划分往往不容易做到很平滑 强调“独立”子问题：减少子问题间的交互可减少闲置时间和通信优点：能够充分利用局部性，较好地适应问题规模和底层硬件的变化 缺点：程序较复杂，实现难度较大4.3 可扩展算法 本节内容主要针对数据并行，即数据并行的可扩展性 数据并行的一个重要问题：如何将数据分配给并行进程/线程 指导性原则：让每个进程/线程负责尽可能大的独立计算块，且 这些块之间的交互尽可能少4.3 可扩展算法一、独立计算块 理想的并行计算 由多个独立计算块组成 独立计算快：大的、独立的计算块，块之间没有交互 独立计算块所对应的并行进程/线程间几乎没有交
10、互，可充分发挥并行性 甚至能够在Internet环境下进行并行计算 完全由独立计算块组成的计算很少见 几乎所有的计算都需要进程/线程间交互，交互的数量在很大程 度上影响着程序性能 独立计算块的借鉴意义 如果更多地关注计算块，就可以提升并行程序的可扩展性 一般而言，计算块越大越好 可减少进程/线程间的相关性 指导性原则：让每个进程/线程负责尽可能大的独立计算块，且 这些块之间的交互尽可能少二、Schwartz算法 独立计算块指导原则在Schwartz算法上有很好的体现 Schwartz算法 一种树操作(tree operation)算法，可用于规约等操作 如果用P个进程对n个数进行+-规约操作，
11、有两种实现方法： 引入逻辑线程实现组合树，成对计算，充分发掘并行性 每个进程负责n/P个数据的局部计算，然后按树结构规约 分析表明，第2种方法性能优于第1种 原因：进程在一个紧凑循环中求和要优于在多个线程间切换 用树结构连接数据项 (数据成对计算，每个计算对应一个线程) 用树结构连接进程 (每个进程负责一组数据的计算)4.3 可扩展算法二、Schwartz算法 Schwartz算法进一步说明： 可扩展并行方法优于无限并行方法 局部计算体现出了独立计算块的原则 Schwartz算法实际上是局部计算和全局并行的组合 推而广之，对于基于树的算法(如规约、扫描)： 应将局部操作与P个叶节点的全局组合树
12、结合 使用具有更高扇出度的树4.3 可扩展算法三、静态为进程分配工作 数据到进程/线程的分配方式对程序性能影响很大 计算时的数据局部性问题 如果进程/线程处理的数据在内存中连续存储，则数据的局部性更好，有 助于提升程序性能 进程/线程间通信量问题 如果进程/线程相互间共享/交换数据较少，则能够更独立地进行计算，进 程/线程间互斥/同步/通信量较少，有助于提升程序性能 块分配 为了充分利用局部性，应尽可能将数据中的连续计算部分分 配给同一进程 对一维数组，数据应按索引连续分配到进程 对二维数组，有按二维块划分和按行划分两种方式 如果二维数组中元素的计算依赖于邻居结点值，则二维块分配方式更 优，原
13、因：有利于减少进程间通信 每个进程与其他进程交换 数据量 按块分配方案：16 按行分配方案：32 如数组扩展为1024x1024 ，进程个数256 按块分配方案：256 按行分配方案：2048 按行分配的优缺点分析 进程间通信数据量大，但 仅需2条消息，而按块分配 需4条消息 问题：得益是固定的，不 具可扩展性 按块分配的扩展性更好为16个进程分配16x16数组的两种方案 灰色块表示分配 给某一进程的数 据 黑色块表示需与 邻居进程通信获 得的数据一种典型的模板计算(stencil computation) Bi, j = ( Ai-1 , j + Ai , j+1 + Ai+1 , j + Ai , j-1 ) / 4.04.3 可扩展算法三、静态为进程分配工作 重叠区域 在二维数组计算中，数据的计 算依赖于其邻居数据，产生了 重叠区域(overlap region) 可以在分配存储时，分配额外 的存储空间，存放重叠区域的 数据，并使这些数据连续存储 作用：可减少进程间通信 循环分配和块循环分配 在某些计算中，块分配可能对负载平衡(load-balanc
