十二、并行程序设计基础国家高性能计算中心（合肥） 22009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 32009-7-24
并行程序设计概述
1 并行程序设计难的原因
2 并行语言的构造方法
3 并行性问题
4 交互 /通信问题
5 五种并行编程风范
6 计算圆周率的样本程序国家高性能计算中心（合肥） 42009-7-24
1 并行程序设计难的原因
技术先行,缺乏理论指导
程序的语法 /语义复杂,需要用户自已处理
任务 /数据的划分 /分配
数据交换
同步和互斥
性能平衡
并行语言缺乏代可扩展和异构可扩展,程序移植困难,
重写代码难度太大
环境和工具缺乏较长的生长期,缺乏代可扩展和异构可扩展国家高性能计算中心（合肥） 52009-7-24
2 并行语言的构造方法串行代码段
for ( i= 0; i<N; i++ ) A[i]=b[i]*b[i+1];
for (i= 0; i<N; i++) c[i]=A[i]+A[i+1];
(a) 使用库例程构造并行程序
id=my_process_id();
p=number_of_processes();
for ( i= id; i<N; i=i+p) A[i]=b[i]*b[i+1];
barrier();
for (i= id; i<N; i=i+p) c[i]=A[i]+A[i+1];
例子,MPI,PVM,Pthreads
(b) 扩展串行语言
my_process_id,number_of_processes(),and barrier()
A(0:N-1)=b(0:N-1)*b(1:N)
c=A(0:N-1)+A(1:N)
例子,Fortran 90
(c) 加编译注释构造并行程序的方法
#pragma parallel
#pragma shared(A,b,c)
#pragma local(i)
{
# pragma pfor iterate(i=0;N;1)
for (i=0;i<N;i++) A[i]=b[i]*b[i+1];
# pragma synchronize
# pragma pfor iterate (i=0; N; 1)
for (i=0;i<N;i++)c[i]=A[i]+A[i+1];
}
例子,SGI power C
国家高性能计算中心（合肥） 62009-7-24
方法 实例 优点 缺点库例程 M P I,PVM 易于实现,不需要新编译器无 编 译 器 检查,
分析和优化扩展 F o r t r a n 9 0 允许编译器检查、分析和优化实现困难,需要新编译器编译器注释 S GI p o w e r C,HPF 介于库例程和扩展方法之间,在串行平台上不起作用,
三种并行语言构造方法比较
2 并行语言的构造方法国家高性能计算中心（合肥） 72009-7-24
3 并行性问题
3.1 进程的同构性
SIMD,所有进程在同一时间执行相同的指令
MIMD:各个进程在同一时间可以执行不同的指令
SPMD,各个进程是同构的，多个进程对不同的数据执行相同的代码 (一般是数据并行的同义语 )
常对应并行循环，数据并行结构，单代码
MPMD:各个进程是异构的,多个进程执行不同的代码
（一般是任务并行，或功能并行，或控制并行的同义语）
常对应并行块，多代码要为有 1000个处理器的计算机编写一个完全异构的并行程序是很困难的国家高性能计算中心（合肥） 82009-7-24
并行块
parbegin S1 S2 S3 …….Sn parend
S1 S2 S3 …….Sn 可以是不同的代码并行循环,当并行块中所有进程共享相同代码时
parbegin S1 S2 S3 …….Sn parend
S1 S2 S3 …….Sn 是相同代码简化为
parfor (i=1; i<=n,i++) S(i)
进程的同构性
3 并行性问题国家高性能计算中心（合肥） 92009-7-24
用单代码方法说明 SPMD
要说明以下 SPMD程序,
parfor (i=0; i<=N,i++) foo(i)
用户需写一个以下程序,
pid=my_process_id();
numproc=number_of _processes();
parfor (i=pid; i<=N,i=i+numproc) foo(i)
此程序经编译后生成可执行程序 A,用 shell
脚本将它加载到 N个处理结点上,
run A –numnodes N
SPMD程序的构造方法用数据并行程序的构造方法要说明以下 SPMD程序,
parfor (i=0; i<=N,i++) {
C[i]=A[i]+B[i];
}
用户可用一条数据赋值语句,
C=A+B
或
forall (i=1,N) C[i]=A[i]+B[i]
进程的同构性
3 并行性问题国家高性能计算中心（合肥） 102009-7-24
用 SPMD伪造 MPMD
要说明以下 MPMD程序,
parbegin S1 S2 S3 parend
可以用以下 SPMD程序,
parfor (i=0; i<3,i++) {
if (i=0) S1
if (i=1) S2
if (i=2) S3
}
因此,对于可扩展并行机来说,
只要支持 SPMD就足够了
MPMD程序的构造方法用多代码方法说明 MPMD
对不提供并行块或并行循环的语言要说明以下 MPMD程序,
parbegin S1 S2 S3 parend
用户需写 3个程序,分别编译生成 3
个可执行程序 S1 S2 S3,用 shell脚本将它们加载到 3个处理结点上,
run S1 on node1
run S2 on node1
run S3 on node1
S1,S2和 S3是顺序语言程序加上进行交互的库调用,
进程的同构性
3 并行性问题国家高性能计算中心（合肥） 112009-7-24
3.2 静态和动态并行性程序的结构,由它的组成部分构成程序的方法静态并行性的例子,
parbegin P,Q,R parend
其中 P,Q,R是静态的动态并行性的例子,
while (C>0) begin
fork (foo(C));
C:=boo(C);
end
3 并行性问题静态并行性,程序的结构以及进程的个数在运行之前 (如编译时,连接时或加载时 )就可确定,就认为该程序具有静态并行性,
动态并行性,否则就认为该程序具有动态并行性,即意味着进程要在运行时创建和终止国家高性能计算中心（合肥） 122009-7-24
Process A:
begin
Z:=1
fork(B);
T:=foo(3);
end
Process B:
begin
fork(C);
X:=foo(Z);
join(C);
output(X+Y);
end
Process C:
begin
Y:=foo(Z);
end
开发动态并行性的一般方法,Fork/Join
静态和动态并行性
3 并行性问题
Fork,派生一个子进程
Join,强制父进程等待子进程国家高性能计算中心（合肥） 132009-7-24
3.3 进程编组目的,支持进程间的交互,常把需要交互的进程调度在同一组中一个进程组成员由,组标识符 + 成员序号 唯一确定,
3.4 划分与分配原则,使系统大部分时间忙于计算,而不是闲置或忙于交互 ;
同时不牺牲并行性 (度 ).
划分,切割数据和工作负载分配,将划分好的数据和工作负载映射到计算结点 (处理器 )上分配方式显式分配,由用户指定数据和负载如何加载隐式分配：由编译器和运行时支持系统决定就近分配原则,进程所需的数据靠近使用它的进程代码
3 并行性问题国家高性能计算中心（合肥） 142009-7-24
并行度 (Degree of Parallelism,DOP):同时执行的分进程数,
并行粒度 (Granularity),两次并行或交互操作之间所执行的计算负载,
指令级并行
块级并行
进程级并行
任务级并行并行度与并行粒度大小常互为倒数,增大粒度会减小并行度,
增加并行度会增加系统 (同步 )开销
3 并行性问题国家高性能计算中心（合肥） 152009-7-24
4 交互／通信 问题交互：进程间的相互影响
4.1 交互的类型
通信,两个或多个进程间传送数的操作通信方式：
共享变量
父进程传给子进程 (参数传递方式 )
消息传递国家高性能计算中心（合肥） 162009-7-24
同步,导致进程间相互等待或继续执行的操作同步方式,
原子同步
控制同步 (路障,临界区 )
数据同步 (锁,条件临界区,
监控程序,事件 )
例子,
原子同步
parfor (i:=1; i<n; i++) {
atomic{x:=x+1; y:=y-1}
}
路障同步
parfor(i:=1; i<n; i++){
Pi
barrier
Qi
}
临界区
parfor(i:=1; i<n; i++){
critical{x:=x+1; y:=y+1}
}
数据同步 (信号量同步 )
parfor(i:=1; i<n; i++){
lock(S);
x:=x+1;
y:=y-1;
unlock(S)
}
4 交互／通信 问题国家高性能计算中心（合肥） 172009-7-24
聚集 (aggregation),用一串超步将各分进程计算所得的部分结果合并为一个完整的结果,每个超步包含一个短的计算和一个简单的通信或 /和同步,
聚集方式,
归约
扫描交互的类型
4 交互／通信 问题例子,计算两个向量的内积
parfor(i:=1; i<n; i++){
X[i]:=A[i]*B[i]
inner_product:=aggregate_sum(X[i]);
}
国家高性能计算中心（合肥） 182009-7-24
4.2 交互的方式
4 交互／通信 问题交互代码 C
…
…
P1 P2 Pn
相对于交互代码 C,可对进程 P定义如下状态,
到达 (arrived),P刚到达 C,但还未进入
在内 (in),P在代码中
完成 (finished):P刚完成执行代码 C,但还未离开
在外 (out),P不在代码中 (未到达或已离开 )
同步的交互,所有参与者同时到达并执行交互代码 C
异步的交互,进程到达 C后,不必等待其它进程到达即可执行 C
国家高性能计算中心（合肥） 192009-7-24
入口条件 出口条件当事进程状态 其它进程状态 当事进程状态 其它进程状态交互方式到达 ( a r r i v e d ) 到达 ( a r r i v e d ) 完成 ( f i ni she d ) 完成 ( f i ni she d ) 同步发送 / 接收到达 ( a r r i v e d ) × 完成 ( f i ni she d ) × 锁定发送到达 ( a r r i v e d ) × 完成 ( f i ni she d ) 完成 ( f i ni she d ) 锁定接收到达 ( a r r i v e d ) × 在内 ( in ) × 非锁定发送 / 接收到达 ( a r r i v e d ) 到达 ( a r r i v e d ) 完成 ( f i ni she d ) 在内 ( in ) 或完成 ( f i ni she d ) 路障到达 ( a r r i v e d ) 在外 ( o ut ) 完成 ( f i ni she d ) 在外 ( o ut ) 临界区交互方式与入口 /出口条件的组合
4 交互／通信 问题锁定的发送,消息已发完,但不一定已收到锁定的接收,消息已收到非锁定的发 /收,只是发出发 /收的请求国家高性能计算中心（合肥） 202009-7-24
4.3 交互的模式按交互模式是否能在编译时确定分为,
静态的
动态的按有多少发送者和接收者参与通信分为
一对一,点到点 (point to point)
一对多,广播 (broadcast),播撒 (scatter)
多对一,收集 (gather),归约 (reduce)
多对多,全交换 (Tatal Exchange),扫描 (scan),置换 /移位
(permutation/shift)
4 交互／通信 问题国家高性能计算中心（合肥） 212009-7-24
1
3
5
P1
P2
P3
1
3
5,1
P1
P2
P3
1
3
5
P1
P2
P3
1,1
3,1
5,1
P1
P2
P3
1,3,5 P1
P2
P3
1,3,5
3
5
P1
P2
P3
1
3
5
P1
P2
P3
1,3,5
3
5
P1
P2
P3
(a) 点对点 (一对一 ),P1发送一个值给 P3 (b) 广播 (一对多 ),P1发送一个值给全体
(c) 播撒 (一对多 ),P1向每个结点发送一个值 (d) 收集 (多对一 ),P1从每个结点接收一个值
4 交互／通信 问题国家高性能计算中心（合肥） 222009-7-24
1
3
5
P1
P2
P3
1,5
3,1
5,3
P1
P2
P3
1,2,3
4,5,6
7,8,9
P1
P2
P3
1,4,7
2,5,8
3,6,9
P1
P2
P3
1
3
5
P1
P2
P3
1,1
3,4
5,9
P1
P2
P3
1
3
5
P1
P2
P3
1,9
3
5
P1
P2
P3
(e) 全交换 (多对多 ),每个结点向每个结点发送一个不同的消息
(f) 移位 (置换,多对多 ),每个结点向下一个结点发送一个值并接收来自上一个结点的一个值,
(g) 归约 (多对一 ),P1得到和 1+3+5=9 (h) 扫描 (多对多 ),P1得到 1,P2得到
1+3=4,P3得到 1+3+5=9
4 交互／通信 问题国家高性能计算中心（合肥） 232009-7-24
相并行（ Phase Parallel）
分治并行（ Divide and Conquer Parallel）
流水线并行（ Pipeline Parallel）
主从并行（ Master-Slave Parallel）
工作池并行（ Work Pool Parallel）
5 五种并行编程风范国家高性能计算中心（合肥） 242009-7-24
相并行（ Phase Parallel）
一组 超级步 （相）
步内各自计算
步间通信、同步
BSP（ 4.2.3）
方便差错和性能分析
计算和通信不能重叠
C C C
Synchronous Interaction
......
C C C
Synchronous Interaction
......
国家高性能计算中心（合肥） 252009-7-24
主－从并行（ Master-Slave Parallel）
主进程：串行、协调任务
子进程：计算子任务
划分设计技术（ 6.1）
与相并行结合
主进程易成为瓶颈
Master
Slave Slave Slave
国家高性能计算中心（合肥） 262009-7-24
分治并行 （ Divide and Conquer Parallel）
父进程把负载分割并指派给子进程
递归
重点在于归并
分治设计技术（ 6.2）
难以负载平衡国家高性能计算中心（合肥） 272009-7-24
流水线并行（ Pipeline Parallel）
一组进程
流水线作业
流水线设计技术（ 6.5）
P1
P2
P3
国家高性能计算中心（合肥） 282009-7-24
工作池并行（ Work Pool Parallel）
初始状态：一件工作
进程从池中取任务执行
可产生新任务放回池中
直至任务池为空
易与负载平衡
临界区问题（尤其消息传递）
Work Pool
P1 P2 P3
国家高性能计算中心（合肥） 292009-7-24
8 计算圆周率的样本程序
1
0
0 2
2
1
)5.0(1
4
1
4
Ni N
N
i
dx
x
国家高性能计算中心（合肥） 302009-7-24
计算圆周率的 c语言代码段
#define N 1000000
main() {
double local,pi = 0.0,w;
long i;
w=1.0/N;
for (i = 0; i<N; i ++) {
local = (i + 0.5)*w;
pi = pi + 4.0/(1.0+local * local);
}
printf(“pi is %f \n”,pi *w);
}
国家高性能计算中心（合肥） 312009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 322009-7-24
进程
1 进程的基本概念
2 进程的并行执行
3 进程的相互作用国家高性能计算中心（合肥） 332009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 342009-7-24
线程
1 线程的基本概念
2 线程的管理
3 线程的同步国家高性能计算中心（合肥） 352009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 362009-7-24
同步
1 原子和互斥
2 高级同步结构
3 低级同步原语国家高性能计算中心（合肥） 372009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 382009-7-24
通信
1 影响通信系统性能的因素
2 低级通信支持
3 TCP/IP通信协议组简介国家高性能计算中心（合肥） 392009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 402009-7-24
并行程序设计模型
1 隐式并行模型
2 数据并行模型
3 消息传递模型
4 共享变量模型国家高性能计算中心（合肥） 412009-7-24
并行程序设计模型
隐式并行（ Implicit Parallel）
数据并行（ Data Parallel）
共享变量（ Shared Variable）
消息传递（ Message Passing）
国家高性能计算中心（合肥） 422009-7-24
隐式并行（ Implicit Parallel）
概况：
程序员用熟悉的串行语言编程
编译器或运行支持系统自动转化为并行代码
特点：
语义简单
可移植性好
单线程，易于调试和验证正确性
效率很低国家高性能计算中心（合肥） 432009-7-24
数据并行（ Data Parallel）
概况：
SIMD的自然模型
局部计算和数据选路操作
特点：
单线程
并行操作于聚合数据结构（数组）
松散同步
单一地址空间
隐式交互作用
显式 数据分布国家高性能计算中心（合肥） 442009-7-24
共享变量（ Shared Variable）
概况：
PVP,SMP,DSM的自然模型
特点：
多线程,SPMD,MPMD
异步
单一地址空间
显式同步
隐式数据分布
隐式通信国家高性能计算中心（合肥） 452009-7-24
消息传递（ Message Passing）
概况：
MPP,COW的自然模型
特点：
多线程
异步
多地址空间
显式同步
显式数据映射和负载分配
显式通信
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 32009-7-24
并行程序设计概述
1 并行程序设计难的原因
2 并行语言的构造方法
3 并行性问题
4 交互 /通信问题
5 五种并行编程风范
6 计算圆周率的样本程序国家高性能计算中心（合肥） 42009-7-24
1 并行程序设计难的原因
技术先行,缺乏理论指导
程序的语法 /语义复杂,需要用户自已处理
任务 /数据的划分 /分配
数据交换
同步和互斥
性能平衡
并行语言缺乏代可扩展和异构可扩展,程序移植困难,
重写代码难度太大
环境和工具缺乏较长的生长期,缺乏代可扩展和异构可扩展国家高性能计算中心（合肥） 52009-7-24
2 并行语言的构造方法串行代码段
for ( i= 0; i<N; i++ ) A[i]=b[i]*b[i+1];
for (i= 0; i<N; i++) c[i]=A[i]+A[i+1];
(a) 使用库例程构造并行程序
id=my_process_id();
p=number_of_processes();
for ( i= id; i<N; i=i+p) A[i]=b[i]*b[i+1];
barrier();
for (i= id; i<N; i=i+p) c[i]=A[i]+A[i+1];
例子,MPI,PVM,Pthreads
(b) 扩展串行语言
my_process_id,number_of_processes(),and barrier()
A(0:N-1)=b(0:N-1)*b(1:N)
c=A(0:N-1)+A(1:N)
例子,Fortran 90
(c) 加编译注释构造并行程序的方法
#pragma parallel
#pragma shared(A,b,c)
#pragma local(i)
{
# pragma pfor iterate(i=0;N;1)
for (i=0;i<N;i++) A[i]=b[i]*b[i+1];
# pragma synchronize
# pragma pfor iterate (i=0; N; 1)
for (i=0;i<N;i++)c[i]=A[i]+A[i+1];
}
例子,SGI power C
国家高性能计算中心（合肥） 62009-7-24
方法 实例 优点 缺点库例程 M P I,PVM 易于实现,不需要新编译器无 编 译 器 检查,
分析和优化扩展 F o r t r a n 9 0 允许编译器检查、分析和优化实现困难,需要新编译器编译器注释 S GI p o w e r C,HPF 介于库例程和扩展方法之间,在串行平台上不起作用,
三种并行语言构造方法比较
2 并行语言的构造方法国家高性能计算中心（合肥） 72009-7-24
3 并行性问题
3.1 进程的同构性
SIMD,所有进程在同一时间执行相同的指令
MIMD:各个进程在同一时间可以执行不同的指令
SPMD,各个进程是同构的，多个进程对不同的数据执行相同的代码 (一般是数据并行的同义语 )
常对应并行循环，数据并行结构，单代码
MPMD:各个进程是异构的,多个进程执行不同的代码
（一般是任务并行，或功能并行，或控制并行的同义语）
常对应并行块，多代码要为有 1000个处理器的计算机编写一个完全异构的并行程序是很困难的国家高性能计算中心（合肥） 82009-7-24
并行块
parbegin S1 S2 S3 …….Sn parend
S1 S2 S3 …….Sn 可以是不同的代码并行循环,当并行块中所有进程共享相同代码时
parbegin S1 S2 S3 …….Sn parend
S1 S2 S3 …….Sn 是相同代码简化为
parfor (i=1; i<=n,i++) S(i)
进程的同构性
3 并行性问题国家高性能计算中心（合肥） 92009-7-24
用单代码方法说明 SPMD
要说明以下 SPMD程序,
parfor (i=0; i<=N,i++) foo(i)
用户需写一个以下程序,
pid=my_process_id();
numproc=number_of _processes();
parfor (i=pid; i<=N,i=i+numproc) foo(i)
此程序经编译后生成可执行程序 A,用 shell
脚本将它加载到 N个处理结点上,
run A –numnodes N
SPMD程序的构造方法用数据并行程序的构造方法要说明以下 SPMD程序,
parfor (i=0; i<=N,i++) {
C[i]=A[i]+B[i];
}
用户可用一条数据赋值语句,
C=A+B
或
forall (i=1,N) C[i]=A[i]+B[i]
进程的同构性
3 并行性问题国家高性能计算中心（合肥） 102009-7-24
用 SPMD伪造 MPMD
要说明以下 MPMD程序,
parbegin S1 S2 S3 parend
可以用以下 SPMD程序,
parfor (i=0; i<3,i++) {
if (i=0) S1
if (i=1) S2
if (i=2) S3
}
因此,对于可扩展并行机来说,
只要支持 SPMD就足够了
MPMD程序的构造方法用多代码方法说明 MPMD
对不提供并行块或并行循环的语言要说明以下 MPMD程序,
parbegin S1 S2 S3 parend
用户需写 3个程序,分别编译生成 3
个可执行程序 S1 S2 S3,用 shell脚本将它们加载到 3个处理结点上,
run S1 on node1
run S2 on node1
run S3 on node1
S1,S2和 S3是顺序语言程序加上进行交互的库调用,
进程的同构性
3 并行性问题国家高性能计算中心（合肥） 112009-7-24
3.2 静态和动态并行性程序的结构,由它的组成部分构成程序的方法静态并行性的例子,
parbegin P,Q,R parend
其中 P,Q,R是静态的动态并行性的例子,
while (C>0) begin
fork (foo(C));
C:=boo(C);
end
3 并行性问题静态并行性,程序的结构以及进程的个数在运行之前 (如编译时,连接时或加载时 )就可确定,就认为该程序具有静态并行性,
动态并行性,否则就认为该程序具有动态并行性,即意味着进程要在运行时创建和终止国家高性能计算中心（合肥） 122009-7-24
Process A:
begin
Z:=1
fork(B);
T:=foo(3);
end
Process B:
begin
fork(C);
X:=foo(Z);
join(C);
output(X+Y);
end
Process C:
begin
Y:=foo(Z);
end
开发动态并行性的一般方法,Fork/Join
静态和动态并行性
3 并行性问题
Fork,派生一个子进程
Join,强制父进程等待子进程国家高性能计算中心（合肥） 132009-7-24
3.3 进程编组目的,支持进程间的交互,常把需要交互的进程调度在同一组中一个进程组成员由,组标识符 + 成员序号 唯一确定,
3.4 划分与分配原则,使系统大部分时间忙于计算,而不是闲置或忙于交互 ;
同时不牺牲并行性 (度 ).
划分,切割数据和工作负载分配,将划分好的数据和工作负载映射到计算结点 (处理器 )上分配方式显式分配,由用户指定数据和负载如何加载隐式分配：由编译器和运行时支持系统决定就近分配原则,进程所需的数据靠近使用它的进程代码
3 并行性问题国家高性能计算中心（合肥） 142009-7-24
并行度 (Degree of Parallelism,DOP):同时执行的分进程数,
并行粒度 (Granularity),两次并行或交互操作之间所执行的计算负载,
指令级并行
块级并行
进程级并行
任务级并行并行度与并行粒度大小常互为倒数,增大粒度会减小并行度,
增加并行度会增加系统 (同步 )开销
3 并行性问题国家高性能计算中心（合肥） 152009-7-24
4 交互／通信 问题交互：进程间的相互影响
4.1 交互的类型
通信,两个或多个进程间传送数的操作通信方式：
共享变量
父进程传给子进程 (参数传递方式 )
消息传递国家高性能计算中心（合肥） 162009-7-24
同步,导致进程间相互等待或继续执行的操作同步方式,
原子同步
控制同步 (路障,临界区 )
数据同步 (锁,条件临界区,
监控程序,事件 )
例子,
原子同步
parfor (i:=1; i<n; i++) {
atomic{x:=x+1; y:=y-1}
}
路障同步
parfor(i:=1; i<n; i++){
Pi
barrier
Qi
}
临界区
parfor(i:=1; i<n; i++){
critical{x:=x+1; y:=y+1}
}
数据同步 (信号量同步 )
parfor(i:=1; i<n; i++){
lock(S);
x:=x+1;
y:=y-1;
unlock(S)
}
4 交互／通信 问题国家高性能计算中心（合肥） 172009-7-24
聚集 (aggregation),用一串超步将各分进程计算所得的部分结果合并为一个完整的结果,每个超步包含一个短的计算和一个简单的通信或 /和同步,
聚集方式,
归约
扫描交互的类型
4 交互／通信 问题例子,计算两个向量的内积
parfor(i:=1; i<n; i++){
X[i]:=A[i]*B[i]
inner_product:=aggregate_sum(X[i]);
}
国家高性能计算中心（合肥） 182009-7-24
4.2 交互的方式
4 交互／通信 问题交互代码 C
…
…
P1 P2 Pn
相对于交互代码 C,可对进程 P定义如下状态,
到达 (arrived),P刚到达 C,但还未进入
在内 (in),P在代码中
完成 (finished):P刚完成执行代码 C,但还未离开
在外 (out),P不在代码中 (未到达或已离开 )
同步的交互,所有参与者同时到达并执行交互代码 C
异步的交互,进程到达 C后,不必等待其它进程到达即可执行 C
国家高性能计算中心（合肥） 192009-7-24
入口条件 出口条件当事进程状态 其它进程状态 当事进程状态 其它进程状态交互方式到达 ( a r r i v e d ) 到达 ( a r r i v e d ) 完成 ( f i ni she d ) 完成 ( f i ni she d ) 同步发送 / 接收到达 ( a r r i v e d ) × 完成 ( f i ni she d ) × 锁定发送到达 ( a r r i v e d ) × 完成 ( f i ni she d ) 完成 ( f i ni she d ) 锁定接收到达 ( a r r i v e d ) × 在内 ( in ) × 非锁定发送 / 接收到达 ( a r r i v e d ) 到达 ( a r r i v e d ) 完成 ( f i ni she d ) 在内 ( in ) 或完成 ( f i ni she d ) 路障到达 ( a r r i v e d ) 在外 ( o ut ) 完成 ( f i ni she d ) 在外 ( o ut ) 临界区交互方式与入口 /出口条件的组合
4 交互／通信 问题锁定的发送,消息已发完,但不一定已收到锁定的接收,消息已收到非锁定的发 /收,只是发出发 /收的请求国家高性能计算中心（合肥） 202009-7-24
4.3 交互的模式按交互模式是否能在编译时确定分为,
静态的
动态的按有多少发送者和接收者参与通信分为
一对一,点到点 (point to point)
一对多,广播 (broadcast),播撒 (scatter)
多对一,收集 (gather),归约 (reduce)
多对多,全交换 (Tatal Exchange),扫描 (scan),置换 /移位
(permutation/shift)
4 交互／通信 问题国家高性能计算中心（合肥） 212009-7-24
1
3
5
P1
P2
P3
1
3
5,1
P1
P2
P3
1
3
5
P1
P2
P3
1,1
3,1
5,1
P1
P2
P3
1,3,5 P1
P2
P3
1,3,5
3
5
P1
P2
P3
1
3
5
P1
P2
P3
1,3,5
3
5
P1
P2
P3
(a) 点对点 (一对一 ),P1发送一个值给 P3 (b) 广播 (一对多 ),P1发送一个值给全体
(c) 播撒 (一对多 ),P1向每个结点发送一个值 (d) 收集 (多对一 ),P1从每个结点接收一个值
4 交互／通信 问题国家高性能计算中心（合肥） 222009-7-24
1
3
5
P1
P2
P3
1,5
3,1
5,3
P1
P2
P3
1,2,3
4,5,6
7,8,9
P1
P2
P3
1,4,7
2,5,8
3,6,9
P1
P2
P3
1
3
5
P1
P2
P3
1,1
3,4
5,9
P1
P2
P3
1
3
5
P1
P2
P3
1,9
3
5
P1
P2
P3
(e) 全交换 (多对多 ),每个结点向每个结点发送一个不同的消息
(f) 移位 (置换,多对多 ),每个结点向下一个结点发送一个值并接收来自上一个结点的一个值,
(g) 归约 (多对一 ),P1得到和 1+3+5=9 (h) 扫描 (多对多 ),P1得到 1,P2得到
1+3=4,P3得到 1+3+5=9
4 交互／通信 问题国家高性能计算中心（合肥） 232009-7-24
相并行（ Phase Parallel）
分治并行（ Divide and Conquer Parallel）
流水线并行（ Pipeline Parallel）
主从并行（ Master-Slave Parallel）
工作池并行（ Work Pool Parallel）
5 五种并行编程风范国家高性能计算中心（合肥） 242009-7-24
相并行（ Phase Parallel）
一组 超级步 （相）
步内各自计算
步间通信、同步
BSP（ 4.2.3）
方便差错和性能分析
计算和通信不能重叠
C C C
Synchronous Interaction
......
C C C
Synchronous Interaction
......
国家高性能计算中心（合肥） 252009-7-24
主－从并行（ Master-Slave Parallel）
主进程：串行、协调任务
子进程：计算子任务
划分设计技术（ 6.1）
与相并行结合
主进程易成为瓶颈
Master
Slave Slave Slave
国家高性能计算中心（合肥） 262009-7-24
分治并行 （ Divide and Conquer Parallel）
父进程把负载分割并指派给子进程
递归
重点在于归并
分治设计技术（ 6.2）
难以负载平衡国家高性能计算中心（合肥） 272009-7-24
流水线并行（ Pipeline Parallel）
一组进程
流水线作业
流水线设计技术（ 6.5）
P1
P2
P3
国家高性能计算中心（合肥） 282009-7-24
工作池并行（ Work Pool Parallel）
初始状态：一件工作
进程从池中取任务执行
可产生新任务放回池中
直至任务池为空
易与负载平衡
临界区问题（尤其消息传递）
Work Pool
P1 P2 P3
国家高性能计算中心（合肥） 292009-7-24
8 计算圆周率的样本程序
1
0
0 2
2
1
)5.0(1
4
1
4
Ni N
N
i
dx
x
国家高性能计算中心（合肥） 302009-7-24
计算圆周率的 c语言代码段
#define N 1000000
main() {
double local,pi = 0.0,w;
long i;
w=1.0/N;
for (i = 0; i<N; i ++) {
local = (i + 0.5)*w;
pi = pi + 4.0/(1.0+local * local);
}
printf(“pi is %f \n”,pi *w);
}
国家高性能计算中心（合肥） 312009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 322009-7-24
进程
1 进程的基本概念
2 进程的并行执行
3 进程的相互作用国家高性能计算中心（合肥） 332009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 342009-7-24
线程
1 线程的基本概念
2 线程的管理
3 线程的同步国家高性能计算中心（合肥） 352009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 362009-7-24
同步
1 原子和互斥
2 高级同步结构
3 低级同步原语国家高性能计算中心（合肥） 372009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 382009-7-24
通信
1 影响通信系统性能的因素
2 低级通信支持
3 TCP/IP通信协议组简介国家高性能计算中心（合肥） 392009-7-24
并行程序设计基础
12.1 并行程序设计概述
12.2 进程
12.3 线程
12.4 同步
12.5 通信
12.6 并行程序设计模型国家高性能计算中心（合肥） 402009-7-24
并行程序设计模型
1 隐式并行模型
2 数据并行模型
3 消息传递模型
4 共享变量模型国家高性能计算中心（合肥） 412009-7-24
并行程序设计模型
隐式并行（ Implicit Parallel）
数据并行（ Data Parallel）
共享变量（ Shared Variable）
消息传递（ Message Passing）
国家高性能计算中心（合肥） 422009-7-24
隐式并行（ Implicit Parallel）
概况：
程序员用熟悉的串行语言编程
编译器或运行支持系统自动转化为并行代码
特点：
语义简单
可移植性好
单线程，易于调试和验证正确性
效率很低国家高性能计算中心（合肥） 432009-7-24
数据并行（ Data Parallel）
概况：
SIMD的自然模型
局部计算和数据选路操作
特点：
单线程
并行操作于聚合数据结构（数组）
松散同步
单一地址空间
隐式交互作用
显式 数据分布国家高性能计算中心（合肥） 442009-7-24
共享变量（ Shared Variable）
概况：
PVP,SMP,DSM的自然模型
特点：
多线程,SPMD,MPMD
异步
单一地址空间
显式同步
隐式数据分布
隐式通信国家高性能计算中心（合肥） 452009-7-24
消息传递（ Message Passing）
概况：
MPP,COW的自然模型
特点：
多线程
异步
多地址空间
显式同步
显式数据映射和负载分配
显式通信
