哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 2章 并行 编程基础
??1 并行编程综述
??2 进程任务和线程
??3 并行性问题
??4 交互和通信问题
哈尔滨工业大学计算机科学与技术学院
?3 并行性问题
?并行编程带来的许多额外问题。
?重点讨论在用户程序中由于对并
行性所作的说明而引起的问题。
哈尔滨工业大学计算机科学与技术学院
?一、进程中的同构性
? 指并行程序中各分进程的类似性。
? 有 3种可能的基本类似,
? SPMD,
? 在单程序多数据 (SPMD)程序中的分进程是同
构的。因为多个进程在不同的数据范畴内执
行相同代码。
? MPMD,
? 在多程序多数据 (MPMD)程序中的分进程
是异构的。因为多个进程可以执行不同
代码。
哈尔滨工业大学计算机科学与技术学院
?SPMD和 MPMD程序，两者都是 MIMD类
型的。
?SIMD,
?SIMD程序与 SPMD有区别,SIMD程序
是 SPMD程序的一个特例。
?将着重 MPMD程序的研究。
哈尔滨工业大学计算机科学与技术学院
? 数据并行程序 --是指 SPMD程序，尤
其是此程序只用数据并行构造 (如
Fortran90中所采用的 )时。
? 功能并行程序 (也称为任务并行或控
制并行程序 )--通常是 MPMD程序的同
义词。
? 在一个并行程序中,MPMD(功能并行 )
和 SPMD(数据并行 )风格可以混合使
用。
哈尔滨工业大学计算机科学与技术学院
?1.并行块 (parallel block)
?表达 MPMD程序的方法是,
?使用 parbegin和 parend构造。
?这种结构化的构造最初是由
DUkstra提议的，也称为 cobegin
和 coend。
哈尔滨工业大学计算机科学与技术学院
Parbegin S1,S2,…, Sn Parend
?当并行块执行时，它的 n个分进程
S1,S2,…, Sn就开始同时执行。
?它们的执行是互相独立的，以不
同速率进行。
?当所有 n个分进程终止时，并行块
也就终止。
哈尔滨工业大学计算机科学与技术学院
?2、并行循环 (Parallel loop)
?当并行块中的所有进程共享相
同代码时，用一个称为并行循
环的速记记号来标明并行块如
下,
哈尔滨工业大学计算机科学与技术学院
? Parbegin Process(1)······Process(n)
? Parend
? 可简化成如下的并行循环,
? Parfor(i=1； i<=n,i++){Process(i)}
? 并行循环常用来说明 SPMD并行程序。
哈尔滨工业大学计算机科学与技术学院
? 可以用 SPMD来仿真 MPMD。
? 例如 MPMD代码,
? Parbegin A； B； C； parend
? 表示成一个 SPMD的并行循环
? parfor(i=0； i<3； i++){
? if (i=0) A；
? If (i=1) B；
? If (i=2) C； }
哈尔滨工业大学计算机科学与技术学院
?3.多代码与单代码 (Multi-
Code versus Single Code)
?MPP和 COW上，许多编程语言不提供
并行块或并行循环构造。
哈尔滨工业大学计算机科学与技术学院
?例如,Parbegin A； B； C；
parend,
?用多代码进行说明,
?run A On node 1
?run B On node 2
?run C On node 3
?程序 A,B和 C仅是顺序程序加上进
行交互的库调用。
哈尔滨工业大学计算机科学与技术学院
? SPMD程序可用单代码方法加以说明。
例如，要说明并行循环
? parfor(i=0,i<N； i++)
? {foo(i)},
? 用户只需编写如下的一个程序,
? Pid=my_process id()；
? Numproc=number_of_processes();
? for(i,=pid； i<N； i=i+numproc)foo(i)；
哈尔滨工业大学计算机科学与技术学院
? 数据并行构造
? 在 Fortran 90和 HPF中,SPMD并行性可用数
据并行构造加以说明。
? 例如，一个并行循环,
parlor(i:=1;i<=N;++){c[i]=A[i]+B[i
];}
? 用户可用 1条数组赋值语句,C=A+B或用
以下循环来表示,
? forall (i=1,N) C[i]=A[i]+B[i]
哈尔滨工业大学计算机科学与技术学院
?二、静态和动态并行性
? 1.静态并行性
? 如果一个程序的结构以及组成进程的
个数在运行时间之前 (如在编译时间，
连接时间或装载时间 )就可确定。
? 2.动态并行性
? 这就蕴含着那些进程要在运行时间内
创建和终止。
哈尔滨工业大学计算机科学与技术学院
?3.动态并行性通常使用某些操
作,
?fork/join(派生和汇合）
?fork/join操作加以表示。它们
也可用单代码或多代码方法加以
说明。
哈尔滨工业大学计算机科学与技术学院
?一般构思。下列程序有 3个进程，
其中 A是主进程，当程序开始执行
时，它是自动被创建的,
? Process A,
? Begin
? Z:=1
? Fork(B);
? T:=foo(3)
? end
哈尔滨工业大学计算机科学与技术学院
? Process B,
? Begin
? Fork(C);
? X:=foo(3);
? Join(C);
? Output(X+Y);
? end
哈尔滨工业大学计算机科学与技术学院
? Process C,
? Begin
? Y:=boo(Z);
? end
哈尔滨工业大学计算机科学与技术学院
?三、进程编组
?一个进程组是进程的一个有序集。
进程中的成员数称为组的大小。
?每个组有一个组标识符 (ID)，它
唯一地识别并行程序中的组。
哈尔滨工业大学计算机科学与技术学院
?为支持组的概念，并行编程语
言需要提供管理进程组的功能,
?如创建和毁灭组、询问组的 ID、
组的成员以及组员的排序等。
哈尔滨工业大学计算机科学与技术学院
?四、分配问题
?任何并行程序必须在某些数据对
象上完成某些计算 (工作负载 )。
?分配是指将数据和工作负载划分
到进程中并将进程映射到结点 (处
理器 )上。
哈尔滨工业大学计算机科学与技术学院
?1.并行性
?平均并行性的量化指标,
?并行程序的并行度 (degree of
paralle lism,DOP)通常定义为
可同时执行的分进程数。
哈尔滨工业大学计算机科学与技术学院
?2.颗粒度
?是指在两次并行性操作或交互操
作之间所执行的计算负载。
?粒度大小分为细 (小 )、中、粗
(大 )3种。
?按计算的操作数大小,可粗略地估
计 。
哈尔滨工业大学计算机科学与技术学院
?3.隐式和显式分配
?显式分配
?用户需要显式说明如何分配数据和
工作负载。
?隐式分配
?此任务将由编译器和运行时间系统
来完成，可以有各种组合分配方式。
哈尔滨工业大学计算机科学与技术学院
?例：在对称式多处理机中
?通常的分配方法是让数据留驻在
一个中央共享存储器中以使所有
进程都可加以访问。
?工作负载的分配可以用静态方式
也可用动态方式。当一个进程分
得一个工作负载后，它所需的数
据可从共享存储器得到。
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 2章 并行 编程基础
??1 并行编程综述
??2 进程任务和线程
??3 并行性问题
??4 交互和通信问题
哈尔滨工业大学计算机科学与技术学院
?3 并行性问题
?并行编程带来的许多额外问题。
?重点讨论在用户程序中由于对并
行性所作的说明而引起的问题。
哈尔滨工业大学计算机科学与技术学院
?一、进程中的同构性
? 指并行程序中各分进程的类似性。
? 有 3种可能的基本类似,
? SPMD,
? 在单程序多数据 (SPMD)程序中的分进程是同
构的。因为多个进程在不同的数据范畴内执
行相同代码。
? MPMD,
? 在多程序多数据 (MPMD)程序中的分进程
是异构的。因为多个进程可以执行不同
代码。
哈尔滨工业大学计算机科学与技术学院
?SPMD和 MPMD程序，两者都是 MIMD类
型的。
?SIMD,
?SIMD程序与 SPMD有区别,SIMD程序
是 SPMD程序的一个特例。
?将着重 MPMD程序的研究。
哈尔滨工业大学计算机科学与技术学院
? 数据并行程序 --是指 SPMD程序，尤
其是此程序只用数据并行构造 (如
Fortran90中所采用的 )时。
? 功能并行程序 (也称为任务并行或控
制并行程序 )--通常是 MPMD程序的同
义词。
? 在一个并行程序中,MPMD(功能并行 )
和 SPMD(数据并行 )风格可以混合使
用。
哈尔滨工业大学计算机科学与技术学院
?1.并行块 (parallel block)
?表达 MPMD程序的方法是,
?使用 parbegin和 parend构造。
?这种结构化的构造最初是由
DUkstra提议的，也称为 cobegin
和 coend。
哈尔滨工业大学计算机科学与技术学院
Parbegin S1,S2,…, Sn Parend
?当并行块执行时，它的 n个分进程
S1,S2,…, Sn就开始同时执行。
?它们的执行是互相独立的，以不
同速率进行。
?当所有 n个分进程终止时，并行块
也就终止。
哈尔滨工业大学计算机科学与技术学院
?2、并行循环 (Parallel loop)
?当并行块中的所有进程共享相
同代码时，用一个称为并行循
环的速记记号来标明并行块如
下,
哈尔滨工业大学计算机科学与技术学院
? Parbegin Process(1)······Process(n)
? Parend
? 可简化成如下的并行循环,
? Parfor(i=1； i<=n,i++){Process(i)}
? 并行循环常用来说明 SPMD并行程序。
哈尔滨工业大学计算机科学与技术学院
? 可以用 SPMD来仿真 MPMD。
? 例如 MPMD代码,
? Parbegin A； B； C； parend
? 表示成一个 SPMD的并行循环
? parfor(i=0； i<3； i++){
? if (i=0) A；
? If (i=1) B；
? If (i=2) C； }
哈尔滨工业大学计算机科学与技术学院
?3.多代码与单代码 (Multi-
Code versus Single Code)
?MPP和 COW上，许多编程语言不提供
并行块或并行循环构造。
哈尔滨工业大学计算机科学与技术学院
?例如,Parbegin A； B； C；
parend,
?用多代码进行说明,
?run A On node 1
?run B On node 2
?run C On node 3
?程序 A,B和 C仅是顺序程序加上进
行交互的库调用。
哈尔滨工业大学计算机科学与技术学院
? SPMD程序可用单代码方法加以说明。
例如，要说明并行循环
? parfor(i=0,i<N； i++)
? {foo(i)},
? 用户只需编写如下的一个程序,
? Pid=my_process id()；
? Numproc=number_of_processes();
? for(i,=pid； i<N； i=i+numproc)foo(i)；
哈尔滨工业大学计算机科学与技术学院
? 数据并行构造
? 在 Fortran 90和 HPF中,SPMD并行性可用数
据并行构造加以说明。
? 例如，一个并行循环,
parlor(i:=1;i<=N;++){c[i]=A[i]+B[i
];}
? 用户可用 1条数组赋值语句,C=A+B或用
以下循环来表示,
? forall (i=1,N) C[i]=A[i]+B[i]
哈尔滨工业大学计算机科学与技术学院
?二、静态和动态并行性
? 1.静态并行性
? 如果一个程序的结构以及组成进程的
个数在运行时间之前 (如在编译时间，
连接时间或装载时间 )就可确定。
? 2.动态并行性
? 这就蕴含着那些进程要在运行时间内
创建和终止。
哈尔滨工业大学计算机科学与技术学院
?3.动态并行性通常使用某些操
作,
?fork/join(派生和汇合）
?fork/join操作加以表示。它们
也可用单代码或多代码方法加以
说明。
哈尔滨工业大学计算机科学与技术学院
?一般构思。下列程序有 3个进程，
其中 A是主进程，当程序开始执行
时，它是自动被创建的,
? Process A,
? Begin
? Z:=1
? Fork(B);
? T:=foo(3)
? end
哈尔滨工业大学计算机科学与技术学院
? Process B,
? Begin
? Fork(C);
? X:=foo(3);
? Join(C);
? Output(X+Y);
? end
哈尔滨工业大学计算机科学与技术学院
? Process C,
? Begin
? Y:=boo(Z);
? end
哈尔滨工业大学计算机科学与技术学院
?三、进程编组
?一个进程组是进程的一个有序集。
进程中的成员数称为组的大小。
?每个组有一个组标识符 (ID)，它
唯一地识别并行程序中的组。
哈尔滨工业大学计算机科学与技术学院
?为支持组的概念，并行编程语
言需要提供管理进程组的功能,
?如创建和毁灭组、询问组的 ID、
组的成员以及组员的排序等。
哈尔滨工业大学计算机科学与技术学院
?四、分配问题
?任何并行程序必须在某些数据对
象上完成某些计算 (工作负载 )。
?分配是指将数据和工作负载划分
到进程中并将进程映射到结点 (处
理器 )上。
哈尔滨工业大学计算机科学与技术学院
?1.并行性
?平均并行性的量化指标,
?并行程序的并行度 (degree of
paralle lism,DOP)通常定义为
可同时执行的分进程数。
哈尔滨工业大学计算机科学与技术学院
?2.颗粒度
?是指在两次并行性操作或交互操
作之间所执行的计算负载。
?粒度大小分为细 (小 )、中、粗
(大 )3种。
?按计算的操作数大小,可粗略地估
计 。
哈尔滨工业大学计算机科学与技术学院
?3.隐式和显式分配
?显式分配
?用户需要显式说明如何分配数据和
工作负载。
?隐式分配
?此任务将由编译器和运行时间系统
来完成，可以有各种组合分配方式。
哈尔滨工业大学计算机科学与技术学院
?例：在对称式多处理机中
?通常的分配方法是让数据留驻在
一个中央共享存储器中以使所有
进程都可加以访问。
?工作负载的分配可以用静态方式
也可用动态方式。当一个进程分
得一个工作负载后，它所需的数
据可从共享存储器得到。
