并行算法的设计与(1)

1、并行算法设计与分析并行算法设计与分析 钟诚钟诚3236396， 教材陈国良.并行算法的设计与分析，第3版.北京:高等教育出版社,2009参考书1 陈国良. 并行计算结构算法 编程, 第3版. 北京：高等 教育出版社,20112 陈国良等. 并行算法实践.北京：高等教育出版社,20043 苏德富,钟诚. 计算机算法设计与分析,第2版. 北京：电子 工业出版社, 20054 C. Xavier, S. S. Iyenger著, 张云泉等译. 并行算法导论.北京： 机械工业出版社, 19985 Ananth Grama. 并行计算导论, 第2版,英文版. 北京:机械 工业出版社,2003为什么需要学

2、习研究并行算法？v 计算机算法+数据结构=计算机程序。v 计算机程序计算机程序+文档文档+控制数据控制数据=计算机软件。计算机软件。v 计算机软件+市场=（精神与物质的）财富。v 并行计算机并行计算机、并行算法可以显著加速大规模、复并行算法可以显著加速大规模、复杂问题的处理（求解）速度，可以获得问题的更杂问题的处理（求解）速度，可以获得问题的更精确（更好）的解。精确（更好）的解。v 客观世界的一切事物（对象）及其活动都是并发（并行）进行的，将事物（对象）及其活动映射 成计算机软件解时，设计开发的计算机软件（计算机程序、计算机算法）自然也应当是并行的！版权声明 本教学PPT仅供课堂教学教师使用第

3、一章 绪论1.1 引言引言 1. 并行处理并行处理 (Parallel Processing) 挖掘计算挖掘计算(Computing)过程的并发事件的信息处理过程的并发事件的信息处理. 2. 并发性并发性 (Concurrency) 并行性并行性(Parallelism) 同时性同时性(Simultaneity) 流水线流水线(Pipelining) 3. 并行处理的级别并行处理的级别(Parallel Processing Level) 指令级并行指令级并行(Instruction Level Parallelism-ILP, 指令内部并行指令内部并行,指令之间并行指令之间并行) 细粒度并行

4、细粒度并行 (fine grain parallelism/ tiny granularity parallelism ) 线程级并行线程级并行(Thread Level Parallelism-TLP) 中细粒度并行中细粒度并行 (fine- medium grain parallelism) 进程级进程级(Process Level Parallelism-PLP)/过程级过程级/算法级并行算法级并行 中粒度并行中粒度并行 (medium grain parallelism) 任务级并行任务级并行(Task Level Parallel) 粗粒度并行粗粒度并行 (coarse grain

5、parallelism) 4. 并行计算并行计算(Parallel Computing)学科学科 并行计算机体系结构并行计算机体系结构 (Parallel Computer Architectures) 并行算法并行算法 (Parallel Algorithms) 并行程序设计并行程序设计 (Parallel Programming)5. 多核处理器（多核处理器（Multi-core Processors，又称片上多处理器，又称片上多处理器-Chip Multi-Processor, CMP） 、众核处理器、众核处理器(Many-core Processors, 如如GPU)、多线程并行技术、

6、多线程并行技术(Multi-thread Parallel Techniques) 的出现与应用，使得并行算法的研究与开发显得极其的出现与应用，使得并行算法的研究与开发显得极其迫切且富有挑战性。迫切且富有挑战性。第一章 绪论1.2 并行算法的硬件基础并行算法的硬件基础1.2.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类v Flynn分类（分类（1966年）年） (1) 单指令流单数据流机器单指令流单数据流机器SISD，即传统的单处理机，即传统的单处理机 (2) 单指令流多数据流机器单指令流多数据流机器SIMD-Single Instruction Stream

7、Multiple Data Stream (3) 多指令流单数据流机器多指令流单数据流机器MISD （目前无实际的商用机器目前无实际的商用机器） (4) 多指令流多数据流机器多指令流多数据流机器MIMD-Multiple Instruction Stream Multiple Data Streamv 并行机的结构模型并行机的结构模型实际的机器体系结构实际的机器体系结构 PVP (Parallel Vector Processor, 并行向量机并行向量机) SIMD 阵列处理器（阵列处理器（SIMD PE） SMP (Symmetric Multiprocessor, 对称多处理机对称多处理机

8、) MPP (Massively Parallel Processor, 大规模并行处理机大规模并行处理机) Clusters ( 工作站机群工作站机群Workstation-Cluster, PC机群机群PC-Cluster, SMP机群机群 SMP-Cluster等等)；目前大部分目前大部分“超级并行计算机超级并行计算机”均采用均采用Clusters结构结构 DSM (Distributed Shared Memory, 分布共享存储多处理机分布共享存储多处理机) 第一章 绪论1.2.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类 结构模型物理机模型VPVPV

9、P交叉开关交叉开关SM(a) PVPP/CP/CP/C总线或交叉开关总线或交叉开关SM(b) SMP, 物理上单一地址空间物理上单一地址空间P/CP/CP/C定制网络定制网络LMLMLM虚拟分布共享存储虚拟分布共享存储(DSM) (d) DSM (MPP/Cluster),逻辑上单一地址空间逻辑上单一地址空间P/CP/CP/C定制网络定制网络LMLMLM(c) MPP, 物理物理/逻辑上多地址空间逻辑上多地址空间P/CP/CP/C定制定制/标准网络标准网络LMLMLM(e) Cluster/COW, 物理物理/逻辑上多地址空间逻辑上多地址空间第一章 绪论1.2.1 并行计算机的体系结构并行计算

10、机的体系结构: 并行计算机分类并行计算机分类 结构模型物理机模型SMPSMPSMPSAN/LANSMSMSMMPPMPPMPPSAN/LANDSMDSMDSM(f) SMP-Cluster(g) DSM-ClusterSMPMPPMPPWANLMDSMSM(h) Grid (Cluster of Clusters)1.2.1 并行计算机的互连网络并行计算机的互连网络v 静态互连网络静态互连网络(固定连接固定连接) connected graph: vertices = processing nodes, edges = communication links(1) 一维线性连接一维线性连接LA

11、(1-D Linear Array): 一维阵列一维阵列 不带环绕的1-D LA，带环绕的1-D LA, 通信直径n-1, n处理器数(2) 网孔连接网孔连接MC (Mesh Connected): 二维阵列二维阵列 互连函数: MC2+1(p)=(p+1) mod n, MC2-1(p)=(p-1) mod n MC2+n 1/2(p)=(p+n1/2) mod n, MC2-n 1/2(p)=(p-n1/2) mod n, p处理器编号 不带环绕的MC，带环绕的MC , 通信直径n1/2-1,1.2.1 并行计算机的互连网络并行计算机的互连网络v 网孔结构的扩展网孔结构的扩展: 可重构网孔

12、可重构网孔 RMESH (Reconfigurable Mesh) 网孔+可重构总线 动态重新设置并行计算机的互连结构，例如可动态设置成多条行总线、列总线或者对角线总线处理机阵列结构，也可动态将规模n n的二维RMESH结构设置成n个规模n1/2 n1/2的子MESH结构。每个处理器通过四个端口（N,E,S,W）与总线相连，在处理器内部有6个开关控制这四个端口之间的连接关系，如图a所示。这四个端口之间共有15种连接方式，如图b所示。 123123iijP(2,3)NESW: 开关NSEWNSEWNSEWNSEWNEWEWSNE,W,SNEW,S,NE,W,S,NEW,SNNSEWNSEWEWN

13、,SEWS,NNWS,EW,NESNW,SENSEWNSEWNSEWNSEWNE,W,SN,W,ESWS,N,ENW,S,ENE,SWNSEWNSEWNSEWNSEW(a)(b) 2D-RMESH结构1.2.1 并行计算机的互连网络并行计算机的互连网络v 静态互连网络静态互连网络 (3) 树形连接树形连接TC(Tree Connected) 二叉树，通信直径2(logn-1) 胖树(X树） 根结点处理器负载过重，瓶颈结点要求根结点处理和容错能力强千万亿次神威蓝光超级并行计算机群采用千万亿次神威蓝光超级并行计算机群采用胖树结构胖树结构连接机群中的处理器结点连接机群中的处理器结点 曙光曙光5000

14、A超级并行计算机群系统机采用超级并行计算机群系统机采用树结构树结构连接机群中的处理器结点连接机群中的处理器结点1.2.1 并行计算机的互连网络并行计算机的互连网络v 静态互连网络静态互连网络 (4) 树网连接树网连接MT(Mesh of tree) 1.2.1 并行计算机的互连网络并行计算机的互连网络v 静态互连网络静态互连网络(5) 金字塔连接金字塔连接 (Pyramid)(6) 超立方连接超立方连接HC (Hypercube Connected)互连函数: CCi(pm-1 pm-2 pi+1 pi pi-1 p1 p0 )= pm-1 pm-2 pi+1 pi pi-1 p1 p0 其中

15、pm-1 pm-2 pi+1 pi pi-1 p1 p0为处理器编号的二进制表示, pi 为对pi 求反, i=0m-1, m=log2n, n=2m ; 通信直径log2n. 不易扩展. 例例: n=16, CC0(0000 )= 0001, CC0(0001 )= 0000, CC0(0010 )= 0011, CC0(0011 )= 0010, CC0(0100 )= 0101, CC0(0101 )= 0100, CC0(0110 )= 0111, CC0(0111 )= 0110, CC0(1000 )= 1001, CC0(1001 )= 1000, 3立方立方 4立方立方1.2.

16、1 并行计算机的互连网络并行计算机的互连网络v 扩展的超立方结构扩展的超立方结构-光电超立方机器光电超立方机器 立方体内的结点(处理器)由电信号连接, 超立方体之间用光信号(光波)连接. 机器规模扩展容易. 电信号连接 光信号连接1.2.1 并行计算机的互连网络并行计算机的互连网络v 静态互连网络静态互连网络(7)立方环连接CCC (Cube Connected-Cycles)(8)洗牌交换连接SE(Shuffle Exchange)物理上是SIMD-SM机器互连函数: SH(pm-1 pm-2 p1 p0 )= pm-2 pm-3 p1 p0 pm-1 ,循环左移1位, m=logn EX(

17、pm-1 pm-2 p1 p0 )= pm-1 pm-2 p1 p0 , 奇偶相邻处理器交换数据 例: n=8个处理器的洗牌和交换函数: SH(p)=(0) (1,2,4) (3,6,5 ) (7); EX(p)=(0,1) (2,3) (4,5) (6,7) P0 - P1 (y) P2 - P3 P4 - P5(x) P6-P7特点：位于某个处理器中的数据，连续洗牌m次之后，数据又回到该处理器1.2.1 并行计算机的互连网络并行计算机的互连网络v 静态互连网络静态互连网络(9) 蝶形连接蝶形连接(Butterfly Connected) 对于k n的蝶形网络, k=log2n, 设Pr,i

18、 (0 r k, 0 i n)表示第r 行第i 列上的处理器,其中第k 行视同第0行. 蝶形网络互连函数: Butterfly(Pr,i )= Pr-1,j , r 0, j= i ,或者 j和 i的二进制表示从左边数起仅在第r 位不同.蝶形网络以2j增长方式展开翅膀, j=0k-1蝶形网络通信直径: k=log2n蝶形网络特别适用于离散富立页变换FFT的并行处理(做成专用的并行处理器).1.2.1 并行计算机的互连网络并行计算机的互连网络v 动态互连网络(非固定连接)总线Bus, 主要用于构造规模不大的SMP机器. P.21(2) 交叉开关Crossbar Switcher：一种高带宽网络

19、P.21(3) 多级互连网络Multistage Interconnection Network P.21 一种大型开关网络. 根据算法(应用)的需要, 动态动态地设置多级网络中各端口连通状各端口连通状态态, 从而使得在任一处理器与某个共享存储器模块之间构成一条路由(链路,通路), 该处理器可以访问此共享存储器模块单元中的内容(数据). 对于对于n个处理器、个处理器、n个共享存储模块的多级互连网络，其互连个共享存储模块的多级互连网络，其互连级数级数m=logn1.2.2 并行计算机的存储组织并行计算机的存储组织v存储器的层次结构 寄存器 容 量 高速缓冲存储器(SRAM) 每 和 一级缓存一级

20、缓存L1Cache 位 存 二级缓存二级缓存L2Cache (处理核共享处理核共享) 成成 取 三级缓存三级缓存L3Cache（CMP共享）共享） 本 时 增 间 主存储器DRAM 加 增 加 硬盘存储器 磁带机1.2.2 并行计算机的存储组织并行计算机的存储组织v存储器层次之间的数据传输（P.23 图 1.21）v各层存储器的性能参数 容量C：字节数 延迟L：读取一个字（Word, 32/64位）所需的时间 带宽B：1秒钟内各存储层传送的字节数 （P.24 图 1.22）v高速缓存一致性问题 当某个处理器第一次访问主存某一存储单元时，系统会将其副本同时传给与该处理器相连的高速缓存。以后当此处

21、理器再此访问此数据时，即可直接访问其高速缓存中的副本（数据）。 若另一个处理器也访问主存中同一存储单元，则此数据之副本也被传到其高速缓存中。 在上述情形下，若一个处理器改写了其高速缓存中（副本）的内容，但另一个处理器的高速缓存中（副本）的内容仍是原来的值，则产生了高速缓存中不一致性的问题。1.3 并行计算模型并行计算模型1.3.1 引言引言v设计并行算法时，用户可以不关心具体的并行计算机系统结构的细节。设计并行算法时，用户可以不关心具体的并行计算机系统结构的细节。v将各种并行计算机系统的一些共同属性抽象起来形成将各种并行计算机系统的一些共同属性抽象起来形成“并行计算模并行计算模型型”。v并行算

22、法的设计与分析依赖于并行计算模型。并行算法的设计与分析依赖于并行计算模型。v传统的顺序（串行）算法的设计与分析依赖于经典计算模型传统的顺序（串行）算法的设计与分析依赖于经典计算模型随机随机存取（访问）机器模型存取（访问）机器模型RAM（Random Access Machine）。）。1.3.2 共享存储的并行计算模型共享存储的并行计算模型PRAM模型模型 PRAM模型模型(Parallel Random Access Machine, 并行随机存取机器模型并行随机存取机器模型) 1、同步、同步PRAM模型（模型（SIMD-SM模型）模型） SM：Shared Memory v共享存储器的共享

23、存储器的SIMD机器模型机器模型：容量无限的共享存储器；有限：容量无限的共享存储器；有限/无限个无限个功能相同的处理器；任何时刻各个处理器均可通过共享存储器的存储功能相同的处理器；任何时刻各个处理器均可通过共享存储器的存储单元进行数据交换（通信）。单元进行数据交换（通信）。v特点：特点：硬件同步硬件同步各并行进程；时间复杂度分析：各并行进程；时间复杂度分析：计算时间（计算时间（通信时间通信时间转化成计算时间）转化成计算时间）；算法设计策略（方法）是串行算法设计思想的扩；算法设计策略（方法）是串行算法设计思想的扩展；展；隐藏了并行机的通讯、同步等细节隐藏了并行机的通讯、同步等细节（设计并行算法直

24、观、容易）（设计并行算法直观、容易）；忽略了忽略了SMSM的竞争、通讯延迟的竞争、通讯延迟等因素。等因素。1.3 并行计算模型并行计算模型v同步PRAM（SIMD-SM）模型结构图Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory1.3 并行计算模型并行计算模型v同步PRAM（SIMD-SM）分类PRAM-EREW模型模型 互斥读互斥写互斥读互斥写 不支持多个处理器同时读/写共享存储器同一单元。PRAM-CREW模型模型 并发读互斥写并发读互斥写 允许多个处理器同时读允许多个处理器同时读共享存储器同一单元，但不支持多个处理但

25、不支持多个处理器同时写器同时写共享存储器同一单元。PRAM-CRCW模型模型 并发读并发写并发读并发写 （理想化的模型） 支持多个处理器同时读/写共享存储器同一单元。 PRAM-CRCW模型的变形：模型的变形：CPRAM-CRCW (Common PRAM-CRCW)模型：仅允许写入相同数据PPRAM-CRCW(Priority PRAM-CRCW)模型：仅允许优先级最高（比（比如：处理器编号最小）如：处理器编号最小）的处理器成功写入。APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入。 1.3 并行计算模型并行计算模型v同步PRAM（SIMD-SM）分类P

26、RAM-EREW模型模型 互斥读互斥写互斥读互斥写 不支持多个处理器同时读/写共享存储器同一单元。PRAM-CREW模型模型 并发读互斥写并发读互斥写 允许多个处理器同时读允许多个处理器同时读共享存储器同一单元，但不支持多个处理但不支持多个处理器同时写器同时写共享存储器同一单元。PRAM-CRCW模型模型 并发读并发写并发读并发写 （理想化的模型） 支持多个处理器同时读/写共享存储器同一单元。 PRAM-CRCW模型的变形：模型的变形：CPRAM-CRCW (Common PRAM-CRCW)模型：仅允许写入相同数据PPRAM-CRCW(Priority PRAM-CRCW)模型：仅允许优先级

27、最高（比（比如：处理器编号最小）如：处理器编号最小）的处理器成功写入。APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入。 1.3 并行计算模型并行计算模型vPRAM-EREW、PRAM-CREW、PRAM-CRCW计算能力比较计算能力比较 设TM表示某个并行算法在并行计算模型M上运行所需的时间，则：qPRAM-EREW模型上模型上解决解决并发读冲突并发读冲突方法方法 将p 个处理器组织成一棵逻辑二叉树，采取自顶向下自顶向下（从树根到树叶）、逐层并行播送数据逐层并行播送数据的方法，树中第i 层上2i (i=1-log2p) 个处理器并行地从SM读出数据，然后

28、这些数据副本并行写入SM中其他单元： SM: x P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14CRCWCREWEREWTTT1.3 并行计算模型并行计算模型qPRAM-EREW模型上模型上解决解决并发写冲突并发写冲突方法方法 将p 个处理器组织成一棵逻辑二叉竞赛树的树叶结点，采取由底由底向上、逐层并行比较淘汰数据向上、逐层并行比较淘汰数据的方法，树中第i 层上2i (i= log2(p-1) - 0) 个处理器并行比较其左右孩子结点（处理器）的数据，胜者晋升到上一层继续比较，败者被淘汰，最后能够到达根结点的处理器成功将数据写入SM单元中：

29、SM: y P P0 0 P0 P1 P P0 0 P P1 1 P P2 2 P P3 3 P0 P1 P2 P3 P4 P5 P6 P7 因此，)log()log(pTOpTOTCRCWCREWEREW1.3 并行计算模型并行计算模型2. 异步APRAM（MIMD-SM）模型 P.28v模型特性每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行无全局时钟，各处理器异步执行；处理器通过SM进行通讯、交换数据；处理器之间的依赖关系，需在并行算法（程序）中显式地加入同步路障语句来需在并行算法（程序）中显式地加入同步路障语句来指定同步指定同步，即软件同步软件同步。算法（程序

30、）设计难度比APRAM模型稍难些。时间复杂度分析：并行（并发）进程生成时间并行（并发）进程生成时间、并行计算时间、并行计算时间、并行（并发）进程计算（处理）过程中的同步时间计算（处理）过程中的同步时间、并行（并发）进程结束的同步时间结束的同步时间。v指令类型：全局读、全局写、局部操作、同步v计算时间 设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。 令 为全局相内各处理器执行时间最长者，则APRAM上的计算时间为： 注：多核处理结构的多核计算模型就是异步注：多核处理结构的多核计算模型就是异步APRAM（MIMD-SM）模型）模型。

31、pht同步障次数BtTph1.3 并行计算模型并行计算模型2. 异步APRAM（MIMD-SM）模型v计算过程 异步APRAM（MIMD-SM）模型的计算过程由同步障分开的全局相组成。1.3 并行计算模型并行计算模型1.3.3 分布存储的并行计算模型1. SIMD-IN（ SIMD-DM）模型分布存储SIMD模型v模型特性q每个处理器均自己的存储器（分布式存储）每个处理器均自己的存储器（分布式存储）；q处理器之间通过互连网络相连，采用传递数据方式实现通讯传递数据方式实现通讯；q运行在各处理器的算法（进程）同步并行执行同步并行执行，处理器之间同步由硬件同步由硬件实现实现；q算法时间复杂度分析：计

32、算时间和选路选路( (路由，通信路由，通信) )时间时间。有些应用所需的选路(路由，通信)时间比其计算时间还要多。v模型的结构图1.3 并行计算模型并行计算模型1.3.3 分布存储的并行计算模型1. SIMD-IN（ SIMD-DM）模型分布存储SIMD模型vSIMD-IN（SIMD-DM）模型的常见模型模型的常见模型q SIMD-LC 一维线性连接q SIMD-MC 网孔连接q SIMD-TC 树形连接q SIMD-MT 树网连接q SIMD-HC 超立方连接q SIMD-CCC 立方环连接q SIMD-SE 洗牌交换连接q SIMD-BF 蝶形网络q SIMD-MIN 多级互连网络1.3

33、并行计算模型并行计算模型1.3.3 分布存储的并行计算模型2. BSP模型v模型特性q它是MIMD-DM模型模型中的一种；q每个处理器均自己的存储器（分布式存储）；q处理器之间通过互连网络相连，采用传递消息方式实现通讯传递消息方式实现通讯；q运行在各处理器上的算法（进程）异步并行执行异步并行执行q处理器之间的同步由算法（程序处理器之间的同步由算法（程序/软件）实现软件）实现；q算法时间复杂度分析：计算时间和选路（路由，通信）时间。有些应用所需的选路（路由，通信）时间比其计算时间还要多。v模型参数p：处理器数（带有存储器）L：同步障时间（Barrier synchronization time）

34、g：带宽因子（time steps/packet）=1/bandwidth1.3 并行计算模型并行计算模型1.3.3 分布存储的并行计算模型2. BSP模型v计算过程 BSP模型的计算过程由若干超级步组成 强调计算过程与通信过程的分离 限制至多h条消息的传递等1.3 并行计算模型并行计算模型1.3.3 分布存储的并行计算模型3. LogP模型v模型特性q分布存储的MIMD模型q点到点通讯的多处理机模型，其中通讯由一组参数描述q隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中q处理机之间实行隐式同步，即硬件同步q算法描述、设计和分析困难v模型参数qL：net

35、work latencyqo：communication overheadqg：gap=1/bandwidthqP：#processors注：L和g反映了通讯网络的容量1.3 并行计算模型并行计算模型1.3.4 层次层次存储的并行计算模型1. 串行计算系统的层次存储模型 （P.34-35）vHMM（层次存储）模型和HMM-BT（块传输的层次存储）模型vUMH （均匀存储层次）模型vRAM(h)模型h层随机存储模型2. 并行计算系统的层次存储模型 （P.36-37）vMemory-LogP模型模型 （ 共享存储共享存储-分布存储模型分布存储模型）vDRAM（h）模型）模型分布式分布式h层随机存储

36、模型层随机存储模型q本地结点模型为RAM(h)模型h层随机存储模型。q p个本地处理机结点通过互连网络连接起来。q处理机结点之间采用点到点消息传递方式交换信息。q将消息传递看成是另一层的存储层次访问；集合消息传递看成是另一将消息传递看成是另一层的存储层次访问；集合消息传递看成是另一层并发存储访问层并发存储访问 方便分析并行算法复杂度方便分析并行算法复杂度qDRAM(h)模型=RAM(h)模型+LogP远程存储访问模型。 SMP-Cluster，多核处理器机群系统就属于，多核处理器机群系统就属于DRAM（h）模型的实例）模型的实例。vHPM模型模型层次并行和存储模型层次并行和存储模型1.3 并行

37、计算模型并行计算模型1.3.5 其他其他并行计算模型MIMD-AC模型异步通信分布式计算模型比较器网络心动阵列和波前阵列判定树有向五环图 量子计算模型量子计算模型 量子物理，量子信息，量子位（Qubit），量子寄存器，n位的量子寄存器可表述 2n种状态，可并行地对量子寄存器中 2n种状态进行操作。量子计算机具有海量存储和天然并行性海量存储和天然并行性的特征。分子计算模型分子计算模型 用分子表示“处理（计算）单元”，分子状态表示数据（信息）值，并行地对分子操作，所有分子同时产生反应、改变分子状态（改变数据值）。空间并行性。空间并行性。1.4 并行算法的基础知识并行算法的基础知识1.4.1 并行算

38、法的定义与分类 1. 定义 并行算法： 一组可同时执行且可互相协作的诸进程的集合。一组可同时执行且可互相协作的诸进程的集合。 2. 分类 VLSI并行算法：在VLSI计算模型上开发的并行算法 、匹配等符号处理基于排序、选择、搜索非数值算法：基于代数等数学运算数值算法：各进程可以独立执行异步算法：进程执行需要相互等待同步算法：环境下网格计算：元计算网络计算：工作站机群局网环境下分布算法InternetCOW/法等如：随机算法、智能算非确定算法：时间复杂性确定的以及算法结果求解过程为确定的步骤确定算法：/1.4 并行算法的基础知识并行算法的基础知识1.4.2 并行算法的表述1. do stepi

39、to stepj in parallel 强调stepi , stepj 要并行执行 stepi stepj enddo2. for all par-do 语句强调n 个进程（线程）并行执行，每个进程（线程）均执行语句S1,S2,.Sk,，但每个进程计算处理的数据对象不同 for i=1 to n par-do 或 for i=1 to n do in parallel S1 S1 . . Sk Sk end for end for3. for all par-do 语句强调p个处理器并行执行，每个处理器均执行语句S1,S2,.Sk,，但每个处理器计算处理的数据对象不同 for all Pi,

40、 where 0ip-1 par-do 或 for all Pi, where 0i p-1 do in parallel S1 S1 . . Sk Sk end for endfor 1.4 并行算法的基础知识并行算法的基础知识1.4.3 并行算法复杂性的度量1、串行算法复杂性的度量 算法复杂性用关于输入数据规模n的函数f(n)来度量，特别是用当n充分大时f(n)的渐近度增长函数来度量v一些记号f(n)=O(g(n) 当n充分大时，f(n) cg(n), c常数 f(n)=Omega(g(n) 当n充分大时，f(n)cg(n), c常数f(n)=Qita(g(n) 当n充分大时，c1 g(n

41、) f(n) c2 g(n), c1 ， c2常数v平均情形复杂度、最坏情形复杂度1.4 并行算法的基础知识并行算法的基础知识1.4.3 并行算法复杂性的度量 2. 并行算法复杂性的度量v运行时间t(n): t(n)= tc (n) + tr (n) 计算时间tc (n)和选路(路由，通信)时间tr (n)v处理器数目p(n)， p(n) =n1-e, 0ep(n)，则为超线性加速(一般出现在某些特殊的应用中，如人工智能中的并行搜索等)v并行效率Ep(n)：Ep(n)=Sp(n)/p(n)， 0用用p台处理器去完成并行算法台处理器去完成并行算法A的第的第i时刻工作量，需时间时刻工作量，需时间

42、=用用p台处理器模拟并行算法台处理器模拟并行算法A的总时间为的总时间为 Brent定理揭示了定理揭示了并行算法工作量和运行时间的关系；并行算法工作量和运行时间的关系；提供了提供了并行算法并行算法的的WT(Work-Time)表示方法；表示方法；指明了指明了设计并行算法时应尽可能将每个设计并行算法时应尽可能将每个时间步的工作量均匀地分摊给时间步的工作量均匀地分摊给p台处理器，使各处理器处于活跃状态。台处理器，使各处理器处于活跃状态。)()(11)(1)(1)(1nTpnWpWpWpWnTiinTiinTii算法算法1.1 SIMD-SM模型上并行求和算法模型上并行求和算法（高层描述（高层描述不考

43、虑处理器数目及其不考虑处理器数目及其分配）分配） / 数据数据A1.n, n=2k Begin(1) for i=1 to n do in parallel /时间时间O(1 ), 工作量工作量n Bi=Ai; / A为原始数组为原始数组 endfor(2) for h=1 to log2n do / h为逻辑二叉树的层号为逻辑二叉树的层号 / h层上层上n/2h个结点（进程）个结点（进程） 并行执行并行执行 for i = 1 to n/2h do in parallel / 时间时间 O(1 ), 工作量工作量n/2h Bi=B2i-1+B2i; endfor endif(3) S=B1;

44、 / 时间时间O(1), 工作量工作量1 endfor End.时间时间T(n)=O(1)+ log2n*O(1)+O(1)=O(log2n)工作量工作量W(n) =n+(n/21 +n/22 +n/2log-1+n/2logn)+1=O(n)算法1.1 SIMD-SM模型上并行求和算法（高层描述）示意图： B1 (S) B1 B2 B1 B2 B3 B4 逐层并行 由底向上 B1 B2 . Bn/2-1 Bn/2 B1 B2 B3 B4 . Bn-3 Bn-2 Bn-1 Bn A1 A2 A3 A4 . An-3 An-2 An-1 An算法1.2 SIMD-SM模型上并行求和算法（低层描述

45、考虑处理器数目及其分配） / 数据A1.n, n=2k, 处理器数p=2q； / 处理器Ps求Am(s-1)+1.m*s的子和,m=n/p=2k-q , s=1 p Begin(1) for s=1 to p do in parallel(1.1) for j=1 to m=n/p do /时间O(n/p ) Bm(s-1)+j=Am(s-1)+j; / O(1)时间，A为原始数组为原始数组 endfor(1.2)for h=1 to log2n do / h为逻辑二叉树的层号 (1.2.1) if (k-q-h)=0 then / h层上并行工作量（结点数）大于等于处理器数 for i= 2

46、k-h-q (s-1)+1 to 2k-h-q *s do / 时间 O(2k-h-q )=O(n/(p*2h) Bi=B2i-1+B2i; endfor endif (1.2.2) if s= 2k-h then / 时间O(1),当前第s个子树的和Bs Bs=B2s-1+B2s; endif endfor(1.3) If s=1 the S=B1 endif endfor End.T(n)=O(n/p)+O(n/(p21 )+O(1)+ O(n/(p22 )+O(1) + +O( n/(p2log- 1 ) )+O(1)+O(n/(p2logn )+O(1)+O(1)=O(n/p+log2

47、n)1.5 并行算法的同步与通信1、并行算法的同步、并行算法的同步v 同步是在时间上强使各执行进程在某一点必须互相等待，确保各进程的正同步是在时间上强使各执行进程在某一点必须互相等待，确保各进程的正常顺序和对共享可写数据的正确访问。常顺序和对共享可写数据的正确访问。v 可用软件、硬件和固件的办法来实现同步：可用软件、硬件和固件的办法来实现同步： SIMD-SM(PRAM)/SIMD-IN上并行算法由硬件实现同步。上并行算法由硬件实现同步。 MIMD-SM (APRAM) 上并行算法由软件（算法）实现同步上并行算法由软件（算法）实现同步：例如，使用：例如，使用lock和和unlock等同步语句显

48、式设置临界区实现多个并发进程（线程）对共等同步语句显式设置临界区实现多个并发进程（线程）对共享变量的互斥访问。享变量的互斥访问。算法复杂度还包括进程生成时间、进程结束同步时间。算法复杂度还包括进程生成时间、进程结束同步时间。v 同步示例同步示例 MIMD-SM (APRAM)上的异步并行求和算法上的异步并行求和算法输入：输入：A=(a0,an-1), 处理器数处理器数p输出：输出：S=ai Begin (1) S=0； / S共享全局变量（总和）共享全局变量（总和） (2.3) lock(S) / 同步同步 (2) for all Pi where 0ip-1 para-do /异步并行异步并

49、行/ S=S+L； (2.1) L=0 ； / L局部变量（子和）局部变量（子和） (2.4) unlock(S) (2.2) for j=i to n step p do end for L=L+aj ； End end for | | P0 P1 P p-2 Pp-1(主）进程主）进程0 进程进程1 进程进程p-2 进程进程p-1 i=0 i=1 i= p-2 i= p-1 | | | | S=0 | | | | L=0 L=0 L=0 L=0 | | | |for j=i to n step p do for j=i to n step p do for j=i to n step p do for j=i to n step p doL=L+aj L=L+aj L=L+aj L=L+aj | | | |lock(S) lock(S) lock(S) lock(S) S=S+L S=S+L S=S+L S=S+Lunlock(S) unlock(S) unlock(S) unlock(S)2、并行算法的通信v SIMD-SM/MIMD-SM算法的通信算法的通信 通过读通过读/写共享存储器实现处理器（并行进程）之间的通信：写共享存储器实现处理器（并行进程）之间