并 行 计 算中国科学技术大学计算机科学与技术系国家高性能计算中心 (合肥 )
2003年 9月第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程第四章 并行算法的设计基础
4.1 并行算法的基础知识
4.2 并行计算模型
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 52009-7-24
并行算法的定义和分类
并行算法的定义
算法
并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。
并行算法的分类
数值计算和非数值计算
同步算法和异步算法
分布算法
确定算法和随机算法
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 72009-7-24
并行算法的表达
描述语言
可以使用类 Algol、类 Pascal等；
在描述语言中引入并行语句。
并行语句示例
Par-do语句
for i=1 to n par-do
……
end for
for all语句
for all Pi,where 0≤i≤k
……
end for
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 92009-7-24
并行算法的复杂性度量
串行算法的复杂性度量
最坏情况下的复杂度 (Worst-CASE Complexity)
期望复杂度 (Expected Complexity)
并行算法的几个复杂性度量指标
运行时间 t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。 n为问题实例的输入规模。
处理器数 p(n)
并行算法成本 c(n),c(n)=t(n)p(n)
总运算量 W(n),并行算法求解问题时所完成的总的操作步数。
国家高性能计算中心（合肥） 102009-7-24
并行算法的复杂性度量
Brent定理令 W(n)是某并行算法 A在运行时间 T(n)内所执行的运算量，则 A使用 p台处理器可在 t(n)=O(W(n)/p+T(n))时间内执行完毕。
W(n)和 c(n)密切相关
P=O(W(n)/T(n))时,W(n)和 c(n)两者是渐进一致的
对于任意的 p,c(n)?W(n)
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 122009-7-24
并行算法的同步
同步概念
同步是在时间上强使各执行进程在某一点必须互相等待；
可用软件、硬件和固件的办法来实现。
同步语句示例
算法 4.1 共享存储多处理器上求和算法输入,A=(a0,…,an-1),处理器数 p
输出,S=Σai
Begin
(1)S=0 (2.3) lock(S)
(2)for all Pi where 0≤ i≤ p-1 do S=S+L
(2.1) L=0 (2.4) unlock(S)
(2.2) for j=i to n step p do end for
L=L+aj End
end for
end for
国家高性能计算中心（合肥） 132009-7-24
并行算法的通讯
通讯
共享存储多处理器使用,global read(X,Y)和 global write(X,Y)
分布存储多计算机使用,send(X,i)和 receive(Y,j)
通讯语句示例
算法 4.2 分布存储多计算机上矩阵向量乘算法输入：处理器数 p,A划分为 B=A[1..n,(i-1)r+1..ir],
x划分为 w=w[(i-1)r+1;ir]
输出,P1保存乘积 AX
Begin
(1) Compute z=Bw
(2) if i=1 then yi=0 else receive(y,left) endif
(3) y=y+z
(4) send(y,right)
(5) if i=1 then receive(y,left)
End
第四章 并行算法的设计基础
4.1 并行算法的基础知识
4.2 并行计算模型
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 162009-7-24
PRAM模型
基本概念
由 Fortune和 Wyllie1978年提出，又称 SIMD-SM模型。
有一个集中的共享存储器和一个指令控制器，通过 SM
的 R/W交换数据，隐式同步计算。
结构图 Control Unit
Interconnection Network
P
LM
P
LM
P
LM
P
LM
Shared Memory
国家高性能计算中心（合肥） 172009-7-24
PRAM模型
分类
(1) PRAM-CRCW并发读并发写
CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据
PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入
APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入
(2) PRAM-CREW并发读互斥写
(3) PRAM-EREW互斥读互斥写
计算能力比较
PRAM-CRCW是最强的计算模型,PRAM-EREW可 logp倍模拟
PRAM-CREW和 PRAM-CRCW
CRCWCREWEREW TTT
C R C WC R E WEREW TTT
)l o g()l o g( pTOpTOT C R C WC R E WE R E W
国家高性能计算中心（合肥） 182009-7-24
PRAM模型
优点
适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节 。
缺点
不适合 MIMD并行机，忽略了 SM的竞争、通讯延迟等因素
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 202009-7-24
异步 APRAM模型
基本概念
又称分相（ Phase） PRAM或 MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过 SM进行通讯；
处理器间依赖关系，需在并行程序中显式地加入同步路障。
指令类型
(1)全局读 (2)全局写
(3)局部操作 (4)同步国家高性能计算中心（合肥） 212009-7-24
异步 APRAM模型
计算过程由同步障分开的全局相组成国家高性能计算中心（合肥） 222009-7-24
异步 APRAM模型
计算时间设局部操作为单位时间；全局读 /写平均时间为 d,d随着处理器数目的增加而增加；同步路障时间为 B=B(p)非降函数。
满足关系 ； 或令 为全局相内各处理器执行时间最长者，则 APRAM上的计算时间为
优缺点易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合 MIMD-DM模型。
pBd2 )lo g()( pdOpBB )log/log( dpdO
pht
同步障次数BtT ph
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 242009-7-24
BSP模型
基本概念
由 Valiant(1990)提出的,,块,同步模型，是一种异步 MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。
模型参数
p：处理器数 (带有存储器 )
l：同步障时间 (Barrier synchronization time)
g：带宽因子 (time steps/packet)=1/bandwidth
国家高性能计算中心（合肥） 252009-7-24
BSP模型
计算过程由若干超级步组成，
每个超级步计算模式为左图
优缺点强调了计算和通讯的分离，
提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多 h条消息的传递等。
各 处 理 器局 部 计 算全 局 通 信路 障 同 步图 4,3
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 272009-7-24
logP模型
基本概念
由 Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，
实行隐式同步。
模型参数
L,network latency
o,communication overhead
g,gap=1/bandwidth
P,#processors
注,L和 g反映了通讯网络的容量国家高性能计算中心（合肥） 282009-7-24
logP模型
优缺点捕捉了 MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，
可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。
BSP vs,LogP
BSP?LogP,BSP块同步?BSP子集同步?BSP进程对同步＝
LogP
BSP可以常数因子模拟 LogP,LogP可以对数因子模拟 BSP
BSP＝ LogP+Barriers－ Overhead
BSP提供了更方便的程设环境,LogP更好地利用了机器资源
BSP似乎更简单、方便和符合结构化编程
2003年 9月第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程第四章 并行算法的设计基础
4.1 并行算法的基础知识
4.2 并行计算模型
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 52009-7-24
并行算法的定义和分类
并行算法的定义
算法
并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。
并行算法的分类
数值计算和非数值计算
同步算法和异步算法
分布算法
确定算法和随机算法
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 72009-7-24
并行算法的表达
描述语言
可以使用类 Algol、类 Pascal等；
在描述语言中引入并行语句。
并行语句示例
Par-do语句
for i=1 to n par-do
……
end for
for all语句
for all Pi,where 0≤i≤k
……
end for
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 92009-7-24
并行算法的复杂性度量
串行算法的复杂性度量
最坏情况下的复杂度 (Worst-CASE Complexity)
期望复杂度 (Expected Complexity)
并行算法的几个复杂性度量指标
运行时间 t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。 n为问题实例的输入规模。
处理器数 p(n)
并行算法成本 c(n),c(n)=t(n)p(n)
总运算量 W(n),并行算法求解问题时所完成的总的操作步数。
国家高性能计算中心（合肥） 102009-7-24
并行算法的复杂性度量
Brent定理令 W(n)是某并行算法 A在运行时间 T(n)内所执行的运算量，则 A使用 p台处理器可在 t(n)=O(W(n)/p+T(n))时间内执行完毕。
W(n)和 c(n)密切相关
P=O(W(n)/T(n))时,W(n)和 c(n)两者是渐进一致的
对于任意的 p,c(n)?W(n)
4.1 并行算法的基础知识
4.1.1 并行算法的定义和分类
4.1.2 并行算法的表达
4.1.3 并行算法的复杂性度量
4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥） 122009-7-24
并行算法的同步
同步概念
同步是在时间上强使各执行进程在某一点必须互相等待；
可用软件、硬件和固件的办法来实现。
同步语句示例
算法 4.1 共享存储多处理器上求和算法输入,A=(a0,…,an-1),处理器数 p
输出,S=Σai
Begin
(1)S=0 (2.3) lock(S)
(2)for all Pi where 0≤ i≤ p-1 do S=S+L
(2.1) L=0 (2.4) unlock(S)
(2.2) for j=i to n step p do end for
L=L+aj End
end for
end for
国家高性能计算中心（合肥） 132009-7-24
并行算法的通讯
通讯
共享存储多处理器使用,global read(X,Y)和 global write(X,Y)
分布存储多计算机使用,send(X,i)和 receive(Y,j)
通讯语句示例
算法 4.2 分布存储多计算机上矩阵向量乘算法输入：处理器数 p,A划分为 B=A[1..n,(i-1)r+1..ir],
x划分为 w=w[(i-1)r+1;ir]
输出,P1保存乘积 AX
Begin
(1) Compute z=Bw
(2) if i=1 then yi=0 else receive(y,left) endif
(3) y=y+z
(4) send(y,right)
(5) if i=1 then receive(y,left)
End
第四章 并行算法的设计基础
4.1 并行算法的基础知识
4.2 并行计算模型
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 162009-7-24
PRAM模型
基本概念
由 Fortune和 Wyllie1978年提出，又称 SIMD-SM模型。
有一个集中的共享存储器和一个指令控制器，通过 SM
的 R/W交换数据，隐式同步计算。
结构图 Control Unit
Interconnection Network
P
LM
P
LM
P
LM
P
LM
Shared Memory
国家高性能计算中心（合肥） 172009-7-24
PRAM模型
分类
(1) PRAM-CRCW并发读并发写
CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据
PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入
APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入
(2) PRAM-CREW并发读互斥写
(3) PRAM-EREW互斥读互斥写
计算能力比较
PRAM-CRCW是最强的计算模型,PRAM-EREW可 logp倍模拟
PRAM-CREW和 PRAM-CRCW
CRCWCREWEREW TTT
C R C WC R E WEREW TTT
)l o g()l o g( pTOpTOT C R C WC R E WE R E W
国家高性能计算中心（合肥） 182009-7-24
PRAM模型
优点
适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节 。
缺点
不适合 MIMD并行机，忽略了 SM的竞争、通讯延迟等因素
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 202009-7-24
异步 APRAM模型
基本概念
又称分相（ Phase） PRAM或 MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过 SM进行通讯；
处理器间依赖关系，需在并行程序中显式地加入同步路障。
指令类型
(1)全局读 (2)全局写
(3)局部操作 (4)同步国家高性能计算中心（合肥） 212009-7-24
异步 APRAM模型
计算过程由同步障分开的全局相组成国家高性能计算中心（合肥） 222009-7-24
异步 APRAM模型
计算时间设局部操作为单位时间；全局读 /写平均时间为 d,d随着处理器数目的增加而增加；同步路障时间为 B=B(p)非降函数。
满足关系 ； 或令 为全局相内各处理器执行时间最长者，则 APRAM上的计算时间为
优缺点易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合 MIMD-DM模型。
pBd2 )lo g()( pdOpBB )log/log( dpdO
pht
同步障次数BtT ph
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 242009-7-24
BSP模型
基本概念
由 Valiant(1990)提出的,,块,同步模型，是一种异步 MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。
模型参数
p：处理器数 (带有存储器 )
l：同步障时间 (Barrier synchronization time)
g：带宽因子 (time steps/packet)=1/bandwidth
国家高性能计算中心（合肥） 252009-7-24
BSP模型
计算过程由若干超级步组成，
每个超级步计算模式为左图
优缺点强调了计算和通讯的分离，
提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多 h条消息的传递等。
各 处 理 器局 部 计 算全 局 通 信路 障 同 步图 4,3
4.2 并行计算模型
4.2.1 PRAM模型
4.2.2 异步 APRAM模型
4.2.3 BSP模型
4.2.4 logP模型国家高性能计算中心（合肥） 272009-7-24
logP模型
基本概念
由 Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，
实行隐式同步。
模型参数
L,network latency
o,communication overhead
g,gap=1/bandwidth
P,#processors
注,L和 g反映了通讯网络的容量国家高性能计算中心（合肥） 282009-7-24
logP模型
优缺点捕捉了 MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，
可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。
BSP vs,LogP
BSP?LogP,BSP块同步?BSP子集同步?BSP进程对同步＝
LogP
BSP可以常数因子模拟 LogP,LogP可以对数因子模拟 BSP
BSP＝ LogP+Barriers－ Overhead
BSP提供了更方便的程设环境,LogP更好地利用了机器资源
BSP似乎更简单、方便和符合结构化编程
