并行算法的设计与分析(1)

并行算法设计与分析

钟诚3236396，chzhong@

教材陈国良.并行算法的设计与分析，第3版.北京:高等教育出版社,2009参考书[1]陈国良.并行计算——结构•算法•编程,第3版.北京：高等教育出版社,2011[2]陈国良等.并行算法实践.北京：高等教育出版社,2004[3]苏德富,钟诚.计算机算法设计与分析,第2版.北京：电子工业出版社,2005[4]C.Xavier,S.S.Iyenger著,张云泉等译.并行算法导论.北京：机械工业出版社,1998[5]AnanthGrama.并行计算导论,第2版,英文版.北京:机械工业出版社,2003为什么需要学习研究并行算法？

计算机算法+数据结构=计算机程序。

计算机程序+文档+控制数据=计算机软件。计算机软件+市场=（精神与物质的）财富。

并行计算机、并行算法可以显著加速大规模、复杂问题的处理（求解）速度，可以获得问题的更精确（更好）的解。客观世界的一切事物（对象）及其活动都是并发（并行）进行的，将事物（对象）及其活动映射成计算机软件解时，设计开发的计算机软件（计算机程序、计算机算法）自然也应当是并行的！版权声明

本教学PPT仅供课堂教学教师使用第一章绪论1.1引言

1.并行处理(ParallelProcessing)

挖掘计算(Computing)过程的并发事件的信息处理.2.并发性(Concurrency)

并行性(Parallelism)同时性(Simultaneity)流水线(Pipelining)3.并行处理的级别(ParallelProcessingLevel)

指令级并行(InstructionLevelParallelism-ILP,指令内部并行,指令之间并行)

细粒度并行(finegrainparallelism/tinygranularityparallelism)

线程级并行(ThreadLevelParallelism-TLP)

中细粒度并行(fine-mediumgrainparallelism)

进程级(ProcessLevelParallelism-PLP)/过程级/算法级并行

中粒度并行(mediumgrainparallelism)

任务级并行(TaskLevelParallel)

粗粒度并行(coarsegrainparallelism)4.

并行计算(ParallelComputing)学科并行计算机体系结构(ParallelComputerArchitectures)

并行算法(ParallelAlgorithms)

并行程序设计(ParallelProgramming)5.多核处理器（Multi-coreProcessors，又称片上多处理器-ChipMulti-Processor,CMP）、众核处理器(Many-coreProcessors,如GPU)、多线程并行技术(Multi-threadParallelTechniques)的出现与应用，使得并行算法的研究与开发显得极其迫切且富有挑战性。第一章绪论1.2并行算法的硬件基础1.2.1并行计算机的体系结构:并行计算机分类Flynn分类（1966年）

(1)单指令流单数据流机器SISD，即传统的单处理机

(2)单指令流多数据流机器SIMD-SingleInstructionStreamMultipleDataStream(3)多指令流单数据流机器MISD（目前无实际的商用机器）

(4)多指令流多数据流机器MIMD-MultipleInstructionStreamMultipleDataStream并行机的结构模型－实际的机器体系结构－PVP(ParallelVectorProcessor,并行向量机)

－SIMD阵列处理器（SIMDPE）－SMP(SymmetricMultiprocessor,对称多处理机)

－MPP(MassivelyParallelProcessor,大规模并行处理机)

－Clusters(工作站机群Workstation-Cluster,PC机群PC-Cluster,SMP机群SMP-Cluster等)；目前大部分“超级并行计算机”均采用Clusters结构－DSM(DistributedSharedMemory,分布共享存储多处理机)第一章绪论1.2.1并行计算机的体系结构:并行计算机分类

结构模型－物理机模型VPVPVP…交叉开关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并行计算机的体系结构:并行计算机分类

结构模型－物理机模型SMPSMPSMP…SAN/LANSMSMSMMPPMPPMPP…SAN/LANDSMDSMDSM(f)SMP-Cluster(g)DSM-ClusterSMPMPPMPP…WANLMDSMSM(h)Grid(ClusterofClusters)1.2.1并行计算机的互连网络

静态互连网络(固定连接)

connectedgraph:vertices=processingnodes,edges=communicationlinks(1)一维线性连接LA(1-DLinearArray):一维阵列

不带环绕的1-DLA，带环绕的1-DLA,通信直径n-1,n处理器数(2)网孔连接MC(MeshConnected):二维阵列

互连函数:MC2+1(p)=(p+1)modn,

MC2-1(p)=(p-1)modnMC2+n

1/2(p)=(p+n1/2)modn,MC2-n

1/2(p)=(p-n1/2)modn,p处理器编号不带环绕的MC，带环绕的MC,通信直径n1/2-1,1.2.1并行计算机的互连网络网孔结构的扩展:可重构网孔RMESH(ReconfigurableMesh)

网孔+可重构总线

动态重新设置并行计算机的互连结构，例如可动态设置成多条行总线、列总线或者对角线总线处理机阵列结构，也可动态将规模n

×n的二维RMESH结构设置成n个规模n1/2×n1/2的子MESH结构。每个处理器通过四个端口（N,E,S,W）与总线相连，在处理器内部有6个开关控制这四个端口之间的连接关系，如图a所示。这四个端口之间共有15种连接方式，如图b所示。

123123iijP(2,3)NESW:开关NSEWNSEWNSEWNSEWNEW{EWSN}{E,W,SN}{EW,S,N}{E,W,S,N}{EW,SN}NSEWNSEW{EWN,S}{EWS,N}{NWS,E}{W,NES}{NW,SE}NSEWNSEWNSEWNSEW{NE,W,S}{N,W,ES}{WS,N,E}{NW,S,E}{NE,SW}NSEWNSEWNSEWNSEW(a)(b)2D-RMESH结构1.2.1并行计算机的互连网络

静态互连网络

(3)树形连接TC(TreeConnected)

二叉树，通信直径2(logn-1)胖树(X树）

根结点处理器负载过重，瓶颈结点要求根结点处理和容错能力强千万亿次神威蓝光超级并行计算机群采用胖树结构连接机群中的处理器结点

曙光5000A超级并行计算机群系统机采用树结构连接机群中的处理器结点1.2.1并行计算机的互连网络

静态互连网络

(4)树网连接MT(Meshoftree)1.2.1并行计算机的互连网络

静态互连网络(5)金字塔连接(Pyramid)(6)超立方连接HC(HypercubeConnected)互连函数:CCi(pm-1pm-2…pi+1pipi-1…p1p0)=pm-1pm-2…pi+1

~pipi-1…p1p0

其中pm-1pm-2…pi+1pipi-1…p1p0为处理器编号的二进制表示,~pi

为对pi

求反,i=0~m-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.1并行计算机的互连网络

扩展的超立方结构----光电超立方机器

立方体内的结点(处理器)由电信号连接,超立方体之间用光信号(光波)连接.机器规模扩展容易.

电信号连接光信号连接1.2.1并行计算机的互连网络

静态互连网络(7)立方环连接CCC(CubeConnected-Cycles)(8)洗牌交换连接SE(ShuffleExchange)——物理上是SIMD-SM机器互连函数:SH(pm-1pm-2…p1p0)=pm-2pm-3…p1p0pm-1,循环左移1位,m=lognEX(pm-1pm-2…p1p0)=pm-1pm-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

------P3P4

-----P5(x)P6------P7特点：位于某个处理器中的数据，连续洗牌m次之后，数据又回到该处理器1.2.1并行计算机的互连网络

静态互连网络(9)蝶形连接(ButterflyConnected)

对于k×n的蝶形网络,k=log2n,设Pr,i(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=0~k-1蝶形网络通信直径:k=log2n蝶形网络特别适用于离散富立页变换FFT的并行处理(做成专用的并行处理器).1.2.1并行计算机的互连网络动态互连网络(非固定连接)总线Bus,主要用于构造规模不大的SMP机器.P.21(2)交叉开关CrossbarSwitcher：一种高带宽网络

P.21(3)多级互连网络MultistageInterconnectionNetworkP.21

一种大型开关网络.

根据算法(应用)的需要,动态地设置多级网络中各端口连通状态,从而使得在任一处理器与某个共享存储器模块之间构成一条路由(链路,通路),该处理器可以访问此共享存储器模块单元中的内容(数据).

对于n个处理器、n个共享存储模块的多级互连网络，其互连级数m=logn1.2.2并行计算机的存储组织存储器的层次结构

寄存器

容

量

高速缓冲存储器(SRAM)

每

和

一级缓存L1Cache

位存二级缓存L2Cache(处理核共享)

成取三级缓存L3Cache（ CMP共享）本

时

增

间

主存储器DRAM

加

增

加

硬盘存储器

磁带机1.2.2并行计算机的存储组织存储器层次之间的数据传输（P.23图1.21）各层存储器的性能参数

容量C：字节数

延迟L：读取一个字（Word,32/64位）所需的时间

带宽B：1秒钟内各存储层传送的字节数（P.24图1.22）高速缓存一致性问题

当某个处理器第一次访问主存某一存储单元时，系统会将其副本同时传给与该处理器相连的高速缓存。以后当此处理器再此访问此数据时，即可直接访问其高速缓存中的副本（数据）。若另一个处理器也访问主存中同一存储单元，则此数据之副本也被传到其高速缓存中。

在上述情形下，若一个处理器改写了其高速缓存中（副本）的内容，但另一个处理器的高速缓存中（副本）的内容仍是原来的值，则产生了高速缓存中不一致性的问题。1.3并行计算模型1.3.1引言设计并行算法时，用户可以不关心具体的并行计算机系统结构的细节。将各种并行计算机系统的一些共同属性抽象起来形成“并行计算模型”。并行算法的设计与分析依赖于并行计算模型。传统的顺序（串行）算法的设计与分析依赖于经典计算模型——随机存取（访问）机器模型RAM（RandomAccessMachine）。1.3.2共享存储的并行计算模型——PRAM模型

PRAM模型(ParallelRandomAccessMachine,并行随机存取机器模型)1、同步PRAM模型（SIMD-SM模型）SM：SharedMemory共享存储器的SIMD机器模型：容量无限的共享存储器；有限/无限个功能相同的处理器；任何时刻各个处理器均可通过共享存储器的存储单元进行数据交换（通信）。特点：硬件同步各并行进程；时间复杂度分析：计算时间（通信时间转化成计算时间）；算法设计策略（方法）是串行算法设计思想的扩展；隐藏了并行机的通讯、同步等细节（设计并行算法直观、容易）；忽略了SM的竞争、通讯延迟等因素。1.3并行计算模型同步PRAM（SIMD-SM）模型结构图ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory1.3并行计算模型同步PRAM（SIMD-SM）分类PRAM-EREW模型——互斥读互斥写

不支持多个处理器同时读/写共享存储器同一单元。PRAM-CREW模型——并发读互斥写

允许多个处理器同时读共享存储器同一单元，但不支持多个处理器同时写共享存储器同一单元。PRAM-CRCW模型——并发读并发写（理想化的模型）

支持多个处理器同时读/写共享存储器同一单元。

PRAM-CRCW模型的变形：CPRAM-CRCW(CommonPRAM-CRCW)模型：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)模型：仅允许优先级最高（比如：处理器编号最小）的处理器成功写入。APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入。1.3并行计算模型同步PRAM（SIMD-SM）分类PRAM-EREW模型——互斥读互斥写

不支持多个处理器同时读/写共享存储器同一单元。PRAM-CREW模型——并发读互斥写

允许多个处理器同时读共享存储器同一单元，但不支持多个处理器同时写共享存储器同一单元。PRAM-CRCW模型——并发读并发写（理想化的模型）

支持多个处理器同时读/写共享存储器同一单元。

PRAM-CRCW模型的变形：CPRAM-CRCW(CommonPRAM-CRCW)模型：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)模型：仅允许优先级最高（比如：处理器编号最小）的处理器成功写入。APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入。1.3并行计算模型PRAM-EREW、PRAM-CREW、PRAM-CRCW计算能力比较设TM表示某个并行算法在并行计算模型M上运行所需的时间，则：PRAM-EREW模型上解决并发读冲突方法

将p个处理器组织成一棵逻辑二叉树，采取自顶向下（从树根到树叶）、逐层并行播送数据的方法，树中第i

层上2i(i=1-log2p)个处理器并行地从SM读出数据，然后这些数据副本并行写入SM中其他单元：

SM:x

P0P1P2P3P4P5P6P7P8P9P10P11P12P13P141.3并行计算模型PRAM-EREW模型上解决并发写冲突方法

将p个处理器组织成一棵逻辑二叉竞赛树的树叶结点，采取由底向上、逐层并行比较淘汰数据的方法，树中第i

层上2i(i=log2(p-1)-0)个处理器并行比较其左右孩子结点（处理器）的数据，胜者晋升到上一层继续比较，败者被淘汰，最后能够到达根结点的处理器成功将数据写入SM单元中：

SM:y

P0

P0P1

P0P1P2P3P0P1P2P3P4P5P6P7

因此，1.3并行计算模型2.异步APRAM（MIMD-SM）模型P.28模型特性每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯、交换数据；处理器之间的依赖关系，需在并行算法（程序）中显式地加入同步路障语句来指定同步，即软件同步。算法（程序）设计难度比APRAM模型稍难些。时间复杂度分析：并行（并发）进程生成时间、并行计算时间、并行（并发）进程计算（处理）过程中的同步时间、并行（并发）进程结束的同步时间。指令类型：全局读、全局写、局部操作、同步计算时间

设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。令为全局相内各处理器执行时间最长者，则APRAM上的计算时间为：

注：多核处理结构的多核计算模型就是异步APRAM（MIMD-SM）模型。1.3并行计算模型2.异步APRAM（MIMD-SM）模型计算过程

异步APRAM（MIMD-SM）模型的计算过程由同步障分开的全局相组成。1.3并行计算模型1.3.3分布存储的并行计算模型1.SIMD-IN（SIMD-DM）模型——分布存储SIMD模型模型特性每个处理器均自己的存储器（分布式存储）；处理器之间通过互连网络相连，采用传递数据方式实现通讯；运行在各处理器的算法（进程）同步并行执行，处理器之间同步由硬件实现；算法时间复杂度分析：计算时间和选路(路由，通信)时间。有些应用所需的选路(路由，通信)时间比其计算时间还要多。模型的结构图1.3并行计算模型1.3.3分布存储的并行计算模型1.SIMD-IN（SIMD-DM）模型——分布存储SIMD模型SIMD-IN（SIMD-DM）模型的常见模型

SIMD-LC一维线性连接

SIMD-MC网孔连接

SIMD-TC树形连接

SIMD-MT树网连接

SIMD-HC超立方连接

SIMD-CCC立方环连接

SIMD-SE洗牌交换连接

SIMD-BF蝶形网络

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

BSP模型的计算过程由若干超级步组成强调计算过程与通信过程的分离限制至多h条消息的传递等1.3并行计算模型1.3.3分布存储的并行计算模型3.LogP模型模型特性分布存储的MIMD模型点到点通讯的多处理机模型，其中通讯由一组参数描述隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中处理机之间实行隐式同步，即硬件同步算法描述、设计和分析困难模型参数L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量1.3并行计算模型1.3.4层次存储的并行计算模型1.串行计算系统的层次存储模型（P.34-35）HMM（层次存储）模型和HMM-BT（块传输的层次存储）模型UMH（均匀存储层次）模型RAM(h)模型——h层随机存储模型2.并行计算系统的层次存储模型（P.36-37）Memory-LogP模型（共享存储-分布存储模型）DRAM（h）模型——分布式h层随机存储模型本地结点模型为RAM(h)模型——h层随机存储模型。

p个本地处理机结点通过互连网络连接起来。处理机结点之间采用点到点消息传递方式交换信息。将消息传递看成是另一层的存储层次访问；集合消息传递看成是另一层并发存储访问方便分析并行算法复杂度DRAM(h)模型=RAM(h)模型+LogP远程存储访问模型。

SMP-Cluster，多核处理器机群系统就属于DRAM（h）模型的实例。HPM模型——层次并行和存储模型1.3并行计算模型1.3.5其他并行计算模型MIMD-AC模型——异步通信分布式计算模型比较器网络心动阵列和波前阵列判定树有向五环图量子计算模型

量子物理，量子信息，量子位（Qubit），量子寄存器，n位的量子寄存器可表述2n种状态，可并行地对量子寄存器中2n种状态进行操作。量子计算机具有海量存储和天然并行性的特征。分子计算模型

用分子表示“处理（计算）单元”，分子状态表示数据（信息）值，并行地对分子操作，所有分子同时产生反应、改变分子状态（改变数据值）。空间并行性。1.4并行算法的基础知识1.4.1并行算法的定义与分类

1.定义

并行算法：一组可同时执行且可互相协作的诸进程的集合。

2.分类

VLSI并行算法：在VLSI计算模型上开发的并行算法

1.4并行算法的基础知识1.4.2并行算法的表述1.dostepitostepjinparallel——强调stepi,…,stepj

要并行执行

stepi

…stepjenddo2.forallpar-do语句——强调n个进程（线程）并行执行，每个进程（线程）均执行语句S1,S2,..Sk,，但每个进程计算处理的数据对象不同

fori=1tonpar-do或

fori=1tondoinparallelS1S1

…...SkSk

endforendfor3.forallpar-do语句——强调p个处理器并行执行，每个处理器均执行语句S1,S2,..Sk,，但每个处理器计算处理的数据对象不同

forallPi,where0≤i≤p-1par-do或

forallPi,where0≤i≤p-1doinparallelS1S1

…...SkSk

endforendfor

1.4并行算法的基础知识1.4.3并行算法复杂性的度量1、串行算法复杂性的度量算法复杂性用关于输入数据规模n的函数f(n)来度量，特别是用当n充分大时f(n)的渐近度增长函数来度量一些记号f(n)=O(g(n))当n充分大时，f(n)

≤c×g(n),c常数

f(n)=Omega(g(n))当n充分大时，f(n)≥c×g(n),c常数f(n)=Qita(g(n))当n充分大时，c1

×g(n)

≤f(n)

≤c2

×g(n),c1

，c2常数平均情形复杂度、最坏情形复杂度1.4并行算法的基础知识1.4.3并行算法复杂性的度量

2.并行算法复杂性的度量运行时间t(n):t(n)=tc(n)+tr(n)

计算时间tc(n)和选路(路由，通信)时间tr(n)处理器数目p(n)，p(n)=n1-e,0<e<1执行代价（成本）c(n)：c(n)=t(n)×p(n)成本（代价）最优性：若求解问题的并行算法的成本c(n)等于在最坏情形下串行算法求解问题所需的最少时间，则称该并行算法是成本最优的。

例如：若某个并行排序算法用log2n个处理器在O(n)时间内完成了对n个数据的排序，则该并行排序算法的成本c(n)=log2nO(n)=O(nlog2n),因此它是成本（代价）最优的。1.4并行算法的基础知识1.4.3并行算法复杂性的度量

2.并行算法复杂性的度量加速比Sp(n)：Sp(n)=ts(n)/tp(n)，1≤

Sp(n)≤p(n)

其中ts(n)为求解问题的最快的串行算法在最坏情形下所需的运行时间，tp(n)为求解同一问题的并行算法在最坏情形下的运行时间。加速比Sp(n)反映算法的并行性对运行时间的改进程度。工程实践中达到对数加速以上认为该并行算法可行。若Sp(n)=p(n)，则达到线性加速；若Sp(n)>p(n)，则为超线性加速(一般出现在某些特殊的应用中，如人工智能中的并行搜索等)并行效率Ep(n)：Ep(n)=Sp(n)/p(n)，0<Ep(n)≤1

Ep(n)反映了并行系统中处理器的利用程度。工作量(或运算量)W(n)：并行算法所执行的总的基本操作（运算）步次数。(与处理器的数目无关)

例如：矩阵乘积算法的基本操作（运算）是“乘法”；数据排序算法的基本操作（运算）是“比较”。1.4.3并行算法复杂性的度量3.并行算法的可扩展性（Scalability）度量并行算法的可扩展性是指度量并行系统、并行算法、并行程序能否有效利用不断增加的处理器的能力增加处理器数目和扩大问题规模有可能提高加速比

影响加速的因素:

求解问题中串行执行部分比例并行处理引起额外开销(通信、等待、竞争、同步、冗余操作）增加的处理器数目超过了算法中的并发程度增加问题规模有利于提高加速

较大的问题规模可提供较高的并发度额外开销的增加可能慢于有效计算的增加算法中串行执行部分的比例可能随着问题规模的增加而缩小3.并行算法的可扩展性度量并行算法的等效率函数

令tc(i)和tO(i)分别为第i个处理器的有用计算时间和额外开销时间，Tc=tc(0)+tc(1)+…+tc(p-1)，TO=to(0)+to(1)+…+to(p-1)。令Tp为p个处理器运行并行算法所需的时间，则Tp=

tc(i)+tO(i)并且pTp=Tc+TO

设W为最佳串行算法完成的工作量，则W=TcSp=Tc/Tp=Tc/((Tc+To)/p)=p/(1+To/Tc)=p/(1+To/W)Ep=Sp/p=1/(1+To/Tc)=1/(1+To/W)

为维持效率Ep不变，当p增大(TO增大)时，必须增加计算量W(Tc)。等效率函数fE(p)：问题工作量(规模)W随处理器数目p变化的函数。并行算法可扩展性判断标准

为了维持效率不变，当p增大时，若仅需增加较小的工作量（问题规模）W——W随p增大而线性/亚线性增长，则称并行算法具有良好的可扩展性；否则，称为不可扩放的。1.4.4并行算法的WT表示Brent定理：令W(n)是并行算法A在运行时间T(n)内执行的运算量（工作量，即串行算法运行时间），则A使用p台处理器可在时间t(n)=O(W(n)/p+T(n))内执行完成。

证明：设时刻i

并行算法A做的工作量为Wi(即在(i-1,i]时段内的工作量),1≤

i≤

T(n)==>用p台处理器去完成并行算法A的第i时刻工作量，需时间

==>用p台处理器模拟并行算法A的总时间为

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

//数据A[1..n],n=2kBegin(1)fori=1tondoinparallel//时间O(1),工作量nB[i]=A[i];//A为原始数组

endfor(2)forh=1tolog2ndo//h为逻辑二叉树的层号

//h层上n/2h个结点（进程）并行执行

fori=1ton/2hdoinparallel//时间O(1

),工作量n/2hB[i]=B[2i-1]+B[2i];endforendif(3)S=B[1];//时间O(1),工作量1

endforEnd.时间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.1SIMD-SM模型上并行求和算法（高层描述）示意图：

B[1](S)—————

B[1]B[2]B[1]B[2]B[3]B[4]逐层并行

………………

由底向上

B[1]B[2]……..B[n/2-1]B[n/2]

B[1]B[2]B[3]B[4]……..B[n-3]B[n-2]B[n-1]B[n]—A[1]A[2]A[3]A[4]……..A[n-3]A[n-2]A[n-1]A[n]算法1.2SIMD-SM模型上并行求和算法（低层描述——考虑处理器数目及其分配）

//数据A[1..n],n=2k,处理器数p=2q；

//处理器Ps求A[m(s-1)+1..m*s]的子和,m=n/p=2k-q,s=1~p

Begin(1)fors=1topdoinparallel(1.1)forj=1tom=n/pdo//时间O(n/p)B[m(s-1)+j]=A[m(s-1)+j];//O(1)时间，A为原始数组

endfor(1.2)forh=1tolog2ndo//h为逻辑二叉树的层号

(1.2.1)if(k-q-h)>=0then//h层上并行工作量（结点数）大于等于处理器数

fori=2k-h-q(s-1)+1to2k-h-q*s

do//时间O(2k-h-q)=O(n/(p*2h))B[i]=B[2i-1]+B[2i];endforendif(1.2.2)ifs<=2k-hthen

//时间O(1),当前第s个子树的和B[s]B[s]=B[2s-1]+B[2s];endifendfor(1.3)Ifs=1theS=B[1]

endif

endforEnd.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+log2n)1.5并行算法的同步与通信1、并行算法的同步同步是在时间上强使各执行进程在某一点必须互相等待，确保各进程的正常顺序和对共享可写数据的正确访问。可用软件、硬件和固件的办法来实现同步：SIMD-SM(PRAM)/SIMD-IN上并行算法由硬件实现同步。MIMD-SM(APRAM)上并行算法由软件（算法）实现同步：例如，使用lock和unlock等同步语句显式设置临界区实现多个并发进程（线程）对共享变量的互斥访问。算法复杂度还包括进程生成时间、进程结束同步时间。同步示例

MIMD-SM(APRAM)上的异步并行求和算法输入：A=(a0,…,an-1),处理器数p输出：S=Σai

Begin(1)S=0；//S共享全局变量（总和）

(2.3)lock(S)//同步

(2)forallPiwhere0≤i≤p-1para-do//异步并行//S=S+L；

(2.1)L=0；//L局部变量（子和）

(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+aj

；End

endfor

|<---------------并发（并行）执行

---------------->|P0P1……Pp-2Pp-1(主）进程0进程1……进程p-2进程p-1i=0i=1……i=p-2i=p-1||……||S=0||……||L=0L=0……L=0L=0||……||forj=itonsteppdo

forj=itonsteppdo

……forj=itonsteppdoforj=itonsteppdoL=L+ajL=L+aj

……L=L+ajL=L+aj

||……||lock(S)lock(S)……lock(S)lock(S)S=S+L

S=S+L……S=S+LS=S+Lunlock(S)unlock(S)……unlock(S)unlock(S)2、并行算法的通信SIMD-SM/MIMD-SM算法的通信

通过读/写共享存储器实现处理器（并行进程）之间的通信：

globalread(X,Y)//将SM中的X读入处理器LM中的Yglobalwrite(U,V)//将LM中的U写入SM中的VSIMD-IN/MIMD-DM算法的通信通过发送/接收数据（消息）实现处理机（并行进程）之间的通信：

send(X,i)//本地处理机通过网络发送（写）X给处理机Pireceive(Y,j)//从处理机Pj通过网络接收（读）数据到本地处理机LM中的Y分布存储多计算机MIMD-DM上矩阵向量乘法并行算法通信示例输入：处理机数p,将矩阵A划分为p个子矩阵Ai=A[1..n,(i-1)r+1..ir],向量X划分为p个子向量X