文档介绍：并行程序设计基础
第1页，本讲稿共45页
并行程序设计基础
并行程序设计概述
进程
线程
同步
通信
并行程序设计模型
*
*
第2页，本讲稿共45页
并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 并行性问题
*
*
第10页，本讲稿共45页
静态和动态并行性
程序的结构: 由它的组成部分构成程序的方法
静态并行性的例子:
parbegin P, Q, R parend
其中P,Q,R是静态的
动态并行性的例子:
while (C>0) begin
fork (foo(C));
C:=boo(C);
end
3 并行性问题
静态并行性: 程序的结构以及进程的个数在运行之前(如编译时, 连接时或加载时)就可确定, 就认为该程序具有静态并行性.
动态并行性: 否则就认为该程序具有动态并行性. 即意味着进程要在运行时创建和终止
*
*
第11页，本讲稿共45页
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: 强制父进程等待子进程
*
*
第12页，本讲稿共45页
进程编组
目的:支持进程间的交互,常把需要交互的进程调度在同一组中
一个进程组成员由：组标识符+ 成员序号唯一确定.
划分与分配
原则: 使系统大部分时间忙于计算, 而不是闲置或忙于交互; 同时不牺牲并行性(度).
划分: 切割数据和工作负载
分配：将划分好的数据和工作负载映射到计算结点(处理器)上
分配方式
显式分配: 由用户指定数据和负载如何加载
隐式分配：由编译器和运行时支持系统决定
就近分配原则：进程所需的数据靠近使用它的进程代码
3 并行性问题
*
*
第13页，本讲稿共45页
并行度(Degree of Parallelism, DOP):同时执行的分进程数.
并行粒度(Granularity): 两次并行或交互操作之间所执行的计算负载.
指令级并行
块级并行
进程级并行
任务级并行
并行度与并行粒度大小常互为倒数: 增大粒度会减小并行度.
增加并行度会增加系统(同步)开销
3 并行性问题
*
*
第14页，本讲稿共45页
4 交互／通信问题
交互：进程间的相互影响
交互的类型
通信：两个或多个进程间传送数的操作
通信方式：
共享变量
父进程传给子进程(参数传递方式)
消息传递
*
*
第15页，本讲稿共45页
同步：导致进程间相互等待或继续执行的操作
同步方式:
原子同步
控制同步(路障,临界区)
数据同步(锁,条件临界区,监控程序,事件)
例子:
原子同步
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 交互／通信问题
*
*
第16页，本讲稿共45页
聚集(aggregation)：用一串超步将各分进程计算所得的部分结果合并为一个完整的结果, 每个超步包含一个短的计算和一个简单的通信或/和同步.