哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 2章 并行 编程基础
??1 并行编程综述
??2 进程任务和线程
??3 并行性问题
??4 通信问题
哈尔滨工业大学计算机科学与技术学院
?4 通信问题
?交互操作称为通信
?这里讨论范围广一些,
?在并行系统中需支持的通信操
作
?通信方式和模式
?竞争通信和合作通信
哈尔滨工业大学计算机科学与技术学院
?一、通信操作
?分为三种,
?数据交换（通信）
?同步
?聚集操作
? 这些操作常统称为通信
? 它们对体系结构和编程的支持有着不
同的要求
哈尔滨工业大学计算机科学与技术学院
?1、通信
? 通信操作是指在两个或多个进程间传
送数据。
? 分类,
?在共享存储程序中的通信
?使用过程级并行性的多处理机程序
用派生过程
?在多计算机模型中的通信
哈尔滨工业大学计算机科学与技术学院
?2,同步操作
?将导致进程的相互等待；
?允许正在等待的进程去继续执行
哈尔滨工业大学计算机科学与技术学院
?不同类型的同步操作,
?（ 1）原子性
?进程常需要以单原子操作方式完成
一串操作,
Parfor(i,=1； i<n； i++){
Atomic {X=X+1； y=y-1； }
}
完成隐式同步
哈尔滨工业大学计算机科学与技术学院
（ 2）控制的同步
?使进程将处于等待状态,
?parfor(i,=1； i<n； i++){
?Pi
?Barrier
?Qi
?}
哈尔滨工业大学计算机科学与技术学院
?例题：另一种控制同步的构造
是临界区,
?parfor(i,=1； i<n； i++)
?{
?critical{X=X+1； y=y-1； }
?}
哈尔滨工业大学计算机科学与技术学院
?说明,
?应注意临界区是互斥的，因为每次
只允许一个进程执行这两条语句。
?与此相反，只要原子性是强制的，
多个进程就可执行它们自己的原子
区。
哈尔滨工业大学计算机科学与技术学院
?（ 3）数据同步
? 执行一个数据同步操作的进程将处
于等待状态，直至程序执行到达某
种数据状态。
? 如下面的代码段所示,
parfor(i,=1,i<n； i++)
{lock(S)； X=X+1； y=y-1；
unlock(S)； }
哈尔滨工业大学计算机科学与技术学院
?3、聚集 (aggregation)
? 由并行程序中的各分进程计算所得的
部分结果，需要用聚集操作加以合并
以得到一个完整结果。
哈尔滨工业大学计算机科学与技术学院
?聚集的主要特征是,
?它由一串超步组成
?在每个超步中，每个进程完成一
个小粒度计算
?通信一个短消息
哈尔滨工业大学计算机科学与技术学院
?例题：求部分和（递归折迭归约
操作）
? 假设有 n个进程
?P(0),P(1),…, P(n-1）
? 数组元素 a[i]初始化时分配给进程
P(i)。
a[0]+ a[1]+ …,+a[n]
? 可以用下列的求 P(i)的单代码程序加
以表示，其中 i=0到 n-1；
哈尔滨工业大学计算机科学与技术学院
? Sum=a； //每个进程有一局部变量 Sum
? For（ j=1； j<n； j=j*2){//log(n)个超步
? if(i％ j=0) {
? Get Sum Of process P(i+j) into
alocal variable tmp；
(*将进程 P(i+j)的和放到局部变量 trap
中 *)
Sum=Sum+tmp；
}
}
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?说明,
?聚集 的特点
哈尔滨工业大学计算机科学与技术学院
?二、通信方式
哈尔滨工业大学计算机科学与技术学院
?一个通信是同步的是指,
?如果代码 C必须当进程都已到达 C后
方可执行
?一个通信是异步的是指,
?如果一个进程到达 C后可不必等待
其他进程，而执行 C。
哈尔滨工业大学计算机科学与技术学院
?双进程的通信 --n=2时；
?多进程的通信 --若 n大于 2。
?点对点通信 --当一个进程向另一
进程发送消息时。
?集合通信 --多进程的通信。
哈尔滨工业大学计算机科学与技术学院
? 当一个进程 P遇到一个交互代码 C时，若
对入口和出口条件以不同方法加以设置，
就可得到多种通讯状态,
?In：进程 P在代码 C中，包括刚进入 C，
刚完成它的代码 C
?Out
?Arrived
?Finished
? 对于双进程的通信，可有 256种组合。
哈尔滨工业大学计算机科学与技术学院
入口条件 出口条件 例
自身 其他 自身 其他
到达
到达
到达
到达
到达
到达
×
×
×
到达
到达
在外
在内
完成
完成
完成
完成
完成
×
×
完成
完成
在内或完成
在外
非锁定发送／接收
锁定发送
锁定接收
同步发送／接收
路障
临界区
入口和出口条件的组合
哈尔滨工业大学计算机科学与技术学院
?广泛使用的通信方式有以下 3种,
?同步的
?锁定的
?非锁定的
哈尔滨工业大学计算机科学与技术学院
?三、通 信 模式
?是指一些进程对其他进程的影响。
?静态的通信模式
?动态通信模式
哈尔滨工业大学计算机科学与技术学院
?几种点对点的集合通信模式如下
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?四,合作 通信 和竞争 通信
?竞争通信,
?一个主要差别是进程以不同方法进
行 通信 。在并发操作系统中，进程
间的交互主要是为了竞争共享资源。
?合作通信,
?它们是要相互进行消息通信、相互
同步、或是从部分计算值生成组合
值。
哈尔滨工业大学计算机科学与技术学院
属性 竞争程序 合作程序
应用
实例
操作系统网络工具 偏微分方程，离散事
件模拟
颗粒
度
少数大粒度的异构进
程
许多小粒度的同构进
程
交互
实例
临界区，生产者 -消
费者，读者 -写者
路障同步，广播、置
换，归约、扫描递降，
工作池或队列
交互
构造
锁、信号灯、事件，
条件临界区，监控程
序
路障,Fetch-and-Add，
一致区域
性质 非终止的，非确定的 终 止 的，确定的
合作和竞争的并行程序
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 2章 并行 编程基础
??1 并行编程综述
??2 进程任务和线程
??3 并行性问题
??4 通信问题
哈尔滨工业大学计算机科学与技术学院
?4 通信问题
?交互操作称为通信
?这里讨论范围广一些,
?在并行系统中需支持的通信操
作
?通信方式和模式
?竞争通信和合作通信
哈尔滨工业大学计算机科学与技术学院
?一、通信操作
?分为三种,
?数据交换（通信）
?同步
?聚集操作
? 这些操作常统称为通信
? 它们对体系结构和编程的支持有着不
同的要求
哈尔滨工业大学计算机科学与技术学院
?1、通信
? 通信操作是指在两个或多个进程间传
送数据。
? 分类,
?在共享存储程序中的通信
?使用过程级并行性的多处理机程序
用派生过程
?在多计算机模型中的通信
哈尔滨工业大学计算机科学与技术学院
?2,同步操作
?将导致进程的相互等待；
?允许正在等待的进程去继续执行
哈尔滨工业大学计算机科学与技术学院
?不同类型的同步操作,
?（ 1）原子性
?进程常需要以单原子操作方式完成
一串操作,
Parfor(i,=1； i<n； i++){
Atomic {X=X+1； y=y-1； }
}
完成隐式同步
哈尔滨工业大学计算机科学与技术学院
（ 2）控制的同步
?使进程将处于等待状态,
?parfor(i,=1； i<n； i++){
?Pi
?Barrier
?Qi
?}
哈尔滨工业大学计算机科学与技术学院
?例题：另一种控制同步的构造
是临界区,
?parfor(i,=1； i<n； i++)
?{
?critical{X=X+1； y=y-1； }
?}
哈尔滨工业大学计算机科学与技术学院
?说明,
?应注意临界区是互斥的，因为每次
只允许一个进程执行这两条语句。
?与此相反，只要原子性是强制的，
多个进程就可执行它们自己的原子
区。
哈尔滨工业大学计算机科学与技术学院
?（ 3）数据同步
? 执行一个数据同步操作的进程将处
于等待状态，直至程序执行到达某
种数据状态。
? 如下面的代码段所示,
parfor(i,=1,i<n； i++)
{lock(S)； X=X+1； y=y-1；
unlock(S)； }
哈尔滨工业大学计算机科学与技术学院
?3、聚集 (aggregation)
? 由并行程序中的各分进程计算所得的
部分结果，需要用聚集操作加以合并
以得到一个完整结果。
哈尔滨工业大学计算机科学与技术学院
?聚集的主要特征是,
?它由一串超步组成
?在每个超步中，每个进程完成一
个小粒度计算
?通信一个短消息
哈尔滨工业大学计算机科学与技术学院
?例题：求部分和（递归折迭归约
操作）
? 假设有 n个进程
?P(0),P(1),…, P(n-1）
? 数组元素 a[i]初始化时分配给进程
P(i)。
a[0]+ a[1]+ …,+a[n]
? 可以用下列的求 P(i)的单代码程序加
以表示，其中 i=0到 n-1；
哈尔滨工业大学计算机科学与技术学院
? Sum=a； //每个进程有一局部变量 Sum
? For（ j=1； j<n； j=j*2){//log(n)个超步
? if(i％ j=0) {
? Get Sum Of process P(i+j) into
alocal variable tmp；
(*将进程 P(i+j)的和放到局部变量 trap
中 *)
Sum=Sum+tmp；
}
}
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?说明,
?聚集 的特点
哈尔滨工业大学计算机科学与技术学院
?二、通信方式
哈尔滨工业大学计算机科学与技术学院
?一个通信是同步的是指,
?如果代码 C必须当进程都已到达 C后
方可执行
?一个通信是异步的是指,
?如果一个进程到达 C后可不必等待
其他进程，而执行 C。
哈尔滨工业大学计算机科学与技术学院
?双进程的通信 --n=2时；
?多进程的通信 --若 n大于 2。
?点对点通信 --当一个进程向另一
进程发送消息时。
?集合通信 --多进程的通信。
哈尔滨工业大学计算机科学与技术学院
? 当一个进程 P遇到一个交互代码 C时，若
对入口和出口条件以不同方法加以设置，
就可得到多种通讯状态,
?In：进程 P在代码 C中，包括刚进入 C，
刚完成它的代码 C
?Out
?Arrived
?Finished
? 对于双进程的通信，可有 256种组合。
哈尔滨工业大学计算机科学与技术学院
入口条件 出口条件 例
自身 其他 自身 其他
到达
到达
到达
到达
到达
到达
×
×
×
到达
到达
在外
在内
完成
完成
完成
完成
完成
×
×
完成
完成
在内或完成
在外
非锁定发送／接收
锁定发送
锁定接收
同步发送／接收
路障
临界区
入口和出口条件的组合
哈尔滨工业大学计算机科学与技术学院
?广泛使用的通信方式有以下 3种,
?同步的
?锁定的
?非锁定的
哈尔滨工业大学计算机科学与技术学院
?三、通 信 模式
?是指一些进程对其他进程的影响。
?静态的通信模式
?动态通信模式
哈尔滨工业大学计算机科学与技术学院
?几种点对点的集合通信模式如下
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?四,合作 通信 和竞争 通信
?竞争通信,
?一个主要差别是进程以不同方法进
行 通信 。在并发操作系统中，进程
间的交互主要是为了竞争共享资源。
?合作通信,
?它们是要相互进行消息通信、相互
同步、或是从部分计算值生成组合
值。
哈尔滨工业大学计算机科学与技术学院
属性 竞争程序 合作程序
应用
实例
操作系统网络工具 偏微分方程，离散事
件模拟
颗粒
度
少数大粒度的异构进
程
许多小粒度的同构进
程
交互
实例
临界区，生产者 -消
费者，读者 -写者
路障同步，广播、置
换，归约、扫描递降，
工作池或队列
交互
构造
锁、信号灯、事件，
条件临界区，监控程
序
路障,Fetch-and-Add，
一致区域
性质 非终止的，非确定的 终 止 的，确定的
合作和竞争的并行程序
