国家高性能计算中心（合肥）
第十四章 分布存储系统并行编程国家高性能计算中心（合肥）
分布存储系统并行编程
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
基于消息传递的并行编程
1 消息传递库
2 消息传递方式国家高性能计算中心（合肥）
1 消息传递库 (Message-Passing Libraries)
表 1,1 一些最流行的消息传递软件的例子
N a m e O r i g i n a l C r e a t o r D i s t i n c t F e a t u r e s
C M M D T h i n k i n g M a c h i n e s U s e A c t i v e M e s s a g e s f o r l o w l a t e n c y
E x p r e s s P a r a s o f t C o l l e c t i v e c o m m u n i c a t i o n a n d I / O
F o r t r a n - M A r g o n n e N a t i o n a l L a b M o d u l a r i t y a n d D e t e r m i n a c y
M P I M P I F o r u m A w i d e l y a d o p t e d s t a n d a r d
NX I n t e l O r i g i n a t e d f r o m t h e I n t e l h y p e r c u b e M P P s
P4 A r g o n n e N a t i o n a l L a b I n t e g r a t e s h a r e d m e m o r y a n d m e s s a g e p a s s i n g
P A R M A C S A N L / G M D M a i n l y u s e d i n E u r o p e
PVM O a k R i d g e N a t i o n a l L a b A w i d e l y u s e d,s t a n d - a l o n e s y s t e m
U N I F Y M i s s i s s i p p i S t a t e A s y s t e m a l l o w i n g b o t h M P I a n d P V M c a l l s
Z i p c o d e L i v e m o r e N a t i o n a l L a b C o n t r i b u t e d t o t h e c o n t e x t c o n c e p t
建议,一个终端用户在开发新的消息传递应用时使用 MPI或 PVM,原因是,
MPI和 PVM都是 公用软件,易于得到
多数厂家支持国家高性能计算中心（合肥）
CMMD,是一个用于 Thinking Machines CM-5系统的消息传递库,其特点是基于主动消息 (Active Message)机制在用户空间实现通信以减少通信延迟 ;
Express,是一个支持点到点和群集通信以及并行 I/O的程序设计环境 ;
Nx,是为 Intel MPP(例如,Hypercubes和 Paragon)开发的微核系统,现在已由用于 Intel/Sandia ASCI TFLOPS 系统中的新的微核系统 PUMA代替,
Fortran-M:是对 Fortran77的扩展,它在设计上既支持共享存储也支持消息传递,但当前只实现了对消息传递的支持,该语言提供了许多机制用于支持开发行为确定、模块化的并行程序,
P4(Parallel Programs for Parallel Processors),是一组宏和子程序,用于支持共享存储和消息传递系统中的程序设计,它可以移植到许多体系结构上,
其它的消息传递软件系统 还有 Vertex,PARMACS,Zipcode,UNIFY和 PICL
等,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
在当前所有的消息传递软件中,最重要最流行的是 MPI和
PVM,它们能运行在所有的并行平台上,包括 SMP和 PVP,
二者 已经在 Windows NT 和 Windows 95这样的非 Unix平台上实现,程序设计语言支持 C,Fortran和 Java.
在国产的三大并行机系列神威、银河和曙光上都实现了对 MPI和 PVM和支持,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
1.1 MPI(Message Passing Interface) 简介
1 消息传递库 (Message-Passing Libraries)
1992 年 4 月 组建了一个制定消息传递接口标准的工作组
1992 年 10 月 初稿形成，主要定义了点对点通信接口
1993 年 1 月 第一届 MPI 会议在 Da l l a s 举行
1993 年 2 月 公布了 MPI - 1 修定版本
1993 年 11 月 MPI 的草稿和概述发表在 S upe r c o m put i ng? 93 的会议论文集中
1994 年 5 月 MPI 标准正式发布
1994 年 7 月 发布了 MPI 标准的勘误表
1997 年 MPI 论坛发布了一个修订的标准,叫做 MPI - 2,同时,原来的 MPI 更名为 MPI - 1
目标,是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准,MPI以语言独立的形式来定义这个接口库,
并提供了与 C,Fortran和 Java语言的绑定,这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性,由于这个原因,MPI在并行计算界被广泛地接受,
国家高性能计算中心（合肥）
MPI的实现
建立在厂家专用的环境之上
IBM SP2的 POE/MPL,
Intel Paragon的 OSF/Nx
公共的 MPI环境,
CHIMP Edinburg 大学
LAN(Local Area Multicomputer) Ohio超级计算中心
MPICH Argonne国家实验室与 Mississippi州立大学
MPICH是 MPI在各种机器上的可移植实现,可以安装在几乎所有的平台上,
PC
工作站
SMP
MPP
COW
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
1.2 PVM(Parallel Virtual Machine) 简介开发时间,始于 1989年开发单位,美国 Tennessee大学,Oak Ridge国家实验室和
Emory大学联合研制特点,具有较好的适应性、可扩展性、可移植性和易使用性等特点,源代码可以免费获取,现已被用户广泛采纳,
现状,目前对它的研究和开发工作仍在各大学和研究机构进行,
尽管已经有越来越多的人开始使用 MPI,但 PVM仍然是做并行处理最流行的软件之一,随着它的不断流行,已经被移植到
PVP,SMP,MPP,工作站和 PC组成的机群系统,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
PVM和 MPI间的主要差别,
(1)PVM是一个自包含的系统,而 MPI不是,MPI依赖于支持它的平台提供对进程的管理和 I/O功能,而 PVM本身就包含这些功能,
(2) MPI对消息传递提供了更强大的支持,
(3) PVM不是一个标准,这就意味着 PVM可以更方便、更频繁地进行版本更新,
MPI和 PVM在功能上现在正趋于相互包含,例如,MPI-2增加了进程管理功能,而现在的 PVM也提供了更多的群集通信函数,与 MPI不同的是,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
1.2 Message-Passing Modes
关于通信模式,用户需要理解的有三个方面,
共有多少个进程?
进程间如何同步?
如何管理通信缓冲区?
现在的消息传递系统多使用三种通信模式,
同步的消息传递 (Synchronous Message Passing)
阻塞的消息传递 (Blocking Message Passing)
非阻塞的消息传递 (Nonblocking Message Passing)
2 消息传递方式国家高性能计算中心（合肥）
发送例程接收例程进程 Q
接收返回点开始接收点
R_syn1 S_Block2S_Non_Block3
进程 P
开始发送点 发送返回点
S_syn1 R_block2 R_Non_Block3
系统进程等待发送点
2 消息传递方式国家高性能计算中心（合肥）
Process P:
M=10;
L1,send M to Q;
L2,M=20;
goto L1;
Process Q:
L1,S= -100;
L2,receive S from P;
X=S+1;
例 2.1 消息传递中的发送和接收缓冲
M 称为发送消息缓冲 (send message buffer,or send buffer)
S 称为接收消息缓冲 (receive message buffer,or receive buffer)
2 消息传递方式国家高性能计算中心（合肥）
三种通信模式的比较通信事件 同步通信 阻塞的通信 非阻塞的通信发送开始的条件 双方都到达了发送和接收点 发送方到达发送点 发送方到达发送点发送返回意味着 消息已被收到 消息已被发送完 通知完系统某个消息要被发送接收开始的条件 双方都到达了发送和接收点 接收方到达发送点 接收方到达发送点接收返回意味着 消息已被收到 消息已被收到 通知完系统某个消息要被接收语义 明确 二者之间 需做错误探测是否需要系统提供临时的消息缓冲区不需要 需要 需要状态检查 不需要 不需要 需要等待的时间开销 最高 二者之间 最低通信与计算,通信与通信的重迭不重迭 重迭 重迭
X
11 11 1 1,21,- 99
2 消息传递方式国家高性能计算中心（合肥）
Process P:
M=10;
send M to Q;
do some computation which
does not change M;
wait for M to be sent;
M=20;
Process Q:
S=-100;
receive S from P;
do some computation which
does not use S;
wait for S to be received;
X=S+1;
例 2.2 非阻塞模式下,强制进程等待直到安全时再继续执行非阻塞模式本身也会带来一些额外开销,
作为临时缓冲区用的内存空间
分配缓冲区的操作
将消息拷入和拷出临时缓冲区
执行一个额外的检测和等待函数
2 消息传递方式国家高性能计算中心（合肥）
消息传递的特点,
在消息传递模型中,一个并行应用由一组进程组成,每个进程的代码是本地的,只能访问私有数据,进程之间通过传递消息实现数据共享和进程同步,
优点,用户可以对并行性的开发、数据分布和通信实现完全控制,
缺点,
(1) 要求程序员显式地处理通信问题,如,消息传递调用的位置,数据移动,数据复制,数据操作,数据的一致性等等,
(2) 对大多数科学计算程序来说,消息传递模型的真正困难还在于显式的域分解,也就是说,将对相应数据的操作限定在指定的处理器上进行,
在每个处理器上只能看见整个分布数据的一部分,
(3) 无法以渐进的方式、通过逐步将串行代码转换成并行代码而开发出来,
大量的散布在程序各处的域分解要求整个程序由串行到并行的转换一次性实现,而共享存储方法允许在现有的串行代码中插入并行说明从而实现逐步转换,与之相比,这是消息传递的一个明显的缺点,
2 消息传递方式国家高性能计算中心（合肥）
分布存储系统并行编程
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
MPI并行编程
1 MPI中的消息
2 MPI中的消息信封
3 MPI中的四种通信模式
4 点对点的通信
5 群集通信
6 MPI扩展
7 例子,计算 Pi的 MPI程序国家高性能计算中心（合肥）
1 MPI中的消息第五讲#include "mpi.h"
int foo(i)
int i;
{...}
main(argc,argv)
int argc;
char* argv[]
{
int i,tmp,sum=0,group_size,my_rank,N;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&group_size);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
if (my_rank==0) {
printf("Enter N:");
scanf("%d",&N);
for (i=1;i<group_size;i++)
MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD);
for (i=my_rank;i<N;i=i+group_size) sum=sum+tmp;
for (i=1;i<group_size;i++) {
MPI_Recv(&tmp,1,MPI_INT,i,i,MPI_COMM_WORLD,&status);
sum=sum+tmp;
}
printf("\n The result = %d",sum);
}
else {
MPI_Recv(&N,1,MPI_INT,i,i,MPI_COMM_WORLD,&status);
for (i-my_rank;i<N;i=i+group_size) sum=sum+foo(i);
MPI_Send(&sum,1,MPI_INT,0,i,MPI_COMM_WORLD);
}
MPI_Finalize();
}
例 1.1 一个计算 ∑foo(i)的 MPI SPMD消息传递程序,存放在文件,myprog.c”中初始化 MPI环境得到缺省的进程组大小得到每个进程在组中的编号发送消息接收消息终止 MPI环境国家高性能计算中心（合肥）
这个程序用以下并行 C编译器 mpcc来编译,
执行下列命令将可执行程序 myprog加载到 n个节点上,
mpcc myprog.c –o myprog
MPIRUN myprog –np n
MPI进程是重型的单线进程,它们拥有不同的地址空间,因此,
一个进程不能直接访问另一个进程地址空间的中的变量,进程间的通信用消息传递来实现,
1 MPI中的消息国家高性能计算中心（合肥）
为什么 MPI中的发送和接收操作要做得这么复杂呢?
MPI消息的组成,
消息的内容 (即,信的内容 ),称为消息缓冲 (message buffer)
消息的接收者 (即,写在信封上面的东西 ),称为消息信封 (message envelop)
MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD)
MPI_Recv(&N,1,MPI_INT,0,i,MPI_COMM_WORLD,&status)
send M to Q;
receive S from P
1 MPI中的消息国家高性能计算中心（合肥）
考虑一个用 C语言声明的由 N个复数组成的数组 double A[100]
假定进程 P要把这个数组发送给进程 Q:
例 1 用 MPI发送一个数据数组
1 MPI中的消息国家高性能计算中心（合肥）
要发送的消息 可用的消息传递系统 说 明
( 1) 发送整个数组 A
理论的消息传递
se nd A t o Q
消息缓冲由数组 A 标识,信封就是进程名 Q,
( 2) 发送数组 A
的头两个元素,
即,
A [ 0] 和 A [ 1]
商用的消息传递
( 假定在一台计算机上,一个双精度数是 64 位,
即 8 个字节,)
se nd(A,16,Q,t ag )
使用的发送例程形式如下,
se nd ( addr e ss,l e ng t h,de st i nat i o n,t ag )
( addr e ss,l e ng t h ) 定义消息缓冲,
( de st i na t i o n,t ag ) 定义消息信封,
( 3) 发送数组 A
中所有偶数编号的元素,即,
A [ 0 ],A [ 2 ],A [ 4 ],
..,
MP I 的消息传递
do ubl e A [ 100] ;
MPI _D at a_t y pe E v e nE l e m e nt s;
...,.,
MPI _T y pe _v e ct o r
( 50,1,2,MPI _D O U B L E,& E v e nE l e m e nt s) ;
MPI _T y pe _co m m i t ( & E v e nE l e m e nt s) ;
MPI _Se nd ( A,1,E v e nE l e m e nt s,de st i nat i o n,.,,) ;
( 1) 需要定义 导出数据类型
( 2) 使用发送例程形式如下,
MPI _S e nd
( buff e r,co unt,dat at y p e,de s t i na t i on,t ag,
co m m uni cat o r )
( buff e r,co unt,dat at y pe ) 定义了消息缓冲,
( dest i nat i o n,t ag,co m m un i cat or ) 构成消息信封,
1 MPI中的消息国家高性能计算中心（合肥）
MPI_Send (&N,1,MPI_INT,i,i,MPI_COMM_WORLD)
子程序名消息地址消息长度消息数据类型接收进程标识号消息标签通信子
MPI_Send (buffer,count,datatype,destination,tag,communicator)
(buffer,count,datatype) 消息缓冲
(destination,tag,communicator) 消息信封
1 MPI中的消息国家高性能计算中心（合肥）
消息数据类型 (message data types)
通信子 (communicators)
通信操作 (communication operations)
虚拟拓扑 (virtual topology)
MPI的 四个重要概念,
1 MPI中的消息国家高性能计算中心（合肥）
理由有两个,
一是支持异构计算
另一是允许非连续,非均匀内存区中的消息,
异构计算 (heterogeneous computing ),指的是在由不同计算机,
如工作站网络,组成的系统上运行应用程序,系统中的每台计算机可能由不同的厂商生产、使用不同的处理器和操作系统当这些计算机使用不同的数据表示时如何保证互操作性,
为什么需要定义消息数据类型?
1 MPI中的消息国家高性能计算中心（合肥）
表 1 M P I 中预定义的数据类型
MP I ( C 语言绑定 ) C MP I ( F o r t r a n 语言绑定 ) F o r t r a n
M P I _ B Y T E M P I _ B Y T E
M P I _ C H A R s i g n e d c h a r M P I _ C H A R A C T E R C H A R A C T E R
M P I _ C O M P L E X C O M P L E X
M P I _ D O U B L E d o u b l e M P I _ D O U B L E _ P R E C I S I O N D O U B L E _ P R E C I S I O N
M P I _ F L O A T f l o a t M P I _ R E A L R E A L
M P I _ I N T i n t M P I _ I N T E G E R I N T E G E R
M P I _ L O G I C A L L O G I C A L
M P I _ L O N G l o n g
M P I _ L O N G _ D O U B L E l o n g d o u b l e
M P I _ P A C K E D M P I _ P A C K E D
M P I _ S H O R T s h o r t
M P I _ U N S I G N E D _ C H A R u n s i g n e d c h a r
M P I _ U N S I G N E D u n s i g n e d i n t
M P I _ U N S I G N E D _ L O N G u n s i g n e d l o n g
M P I _ U N S I G N E D _ S H O R T u n s i g n e d s h o r t
1 MPI中的消息国家高性能计算中心（合肥）
例 2 发送非连续数据项例 程 说 明
MP I _ P a c k _ s i z e 决定需要一个多大的临时缓冲区来存放 50 个 MP I _ DO UB L E
数据项
m a l l o c (B u f f e r S i z e ) 为缓冲区 T e m p B u f f e r 动态分配内存
f o r 循环 将数组 A 的 50 个偶序数元素打成一个包,放在 T e m p B u f f e r
中
MP I _ P a c k
( A+i* j,1,MP I _ DO UB L E,
T e m p B u f f e,B u f f e r S i z e,
&P o s i t i o n,com m ) ;
第一个参数是被打包的数组元素的地址,
第三个参数是被打包的数组元素的数 据类型,
p o s i t i o n 用于跟踪已经有多少个数据项被打包,p o s i t i o n 的最后值在接下来的 MP I _ S e n d 中被用作消息计数,
double A[100];
MPI_Pack_size (50,MPI_DOUBLE,comm,&BufferSize);
TempBuffer = malloc(BufferSize);
j = sizeof(MPI_DOUBLE);
Position = 0;
for (i=0;i<50;i++)
MPI_Pack(A+i*j,1,MPI_DOUBLE,TempBuffer,BufferSize,&Position,comm);
MPI_Send(TempBuffer,Position,MPI_PACKED,destination,tag,comm);
国家高性能计算中心（合肥）
在下面的消息中,假定每个双精度数有 8字节长,一个字符是 1字节,一个整型数是 4字节,
序号 要发送的消息 消息的性质与定义方法
( 1 ) 由数组 A 的所有元素组成的消息,A 有 100 个元素,每个元素是一个双精度数,
这个消息由 100 项组成,每项有一个 d o u b l e 数据类型,决定了每一项的大小是 8 字节,第 i 项的起始地址是 A +8 ( i - 1 ),
( 2 ) 由数组 A 的第 3 和第 4 项组成消息,
这个消息由两项 A [ 2 ] 和 A [ 3 ] 组成,每项是一个 d o u b l e 数据类型,第一项始于 A +1 6,第二项始于 A +2 4,
这两个消息有两个性质,
数据项的存放是连续的 ;
所有的数据项具有相同的数据类型,
这类消息可以方便地用三元组
( a d d r e s s,c o u n t,d a t a t y p e )
来定义,
第 ( 1 ) 个消息可以用 ( A,1 0 0,M P I _ D O U B L E ) 来定义,
第 ( 2 ) 个消息可以用 ( A +1 6,2,M P I _ D O U B L E ) 来定义,
( 3 ) 由数组 A 的所有偶序数项组成的消息,
这个消息由 50 项 A [ 0 ],A [ 2 ],A [ 4 ],.,,,A [ 9 8 ] 组成,每一项有一个 d o u b l e 数据类型,第 i 项的起始地址是 A +1 6 ( i - 1 ),
( 4 )
由数组 A 的第 3 项,后跟一个字符 c,再跟一个整型数 k.
这个消息由三个不同类型的数据组成,假定它是一个数据结构,
s t r u c t { d o u b l e A [ 1 0 0 ] ; c h a r b,c ; i n t j,k ; } S
的一部分,那么第一项 A [ 2 ] 的地址是 S + 1 6,第二项 c 的地址是 S + 8 0 1,第三项 k 的地址是 S + 8 0 6,
第 ( 3 ) 个消息的性质,
数据项没有放在一个连续的存储区中,
第 ( 4 ) 个消息的性质,
数据不仅没有连续存放,而且是混合数据类型,
上述简单的方法不能处理第 ( 3 ) 和第 ( 4 ) 个消息,
MP I 引入导出数据类型 ( d e r i v e d d a t a t y p e ) 的概念,允许定义可能是由混合 数据类型,非连续存放的数据项组成的消息,导出数据类型由用户的应用程序在运行时从基本的数据类型构造,M P I 提供了强大而全面的构造复杂数据类型的子例程,
例 3 在消息传递中发送一个混合数据类型国家高性能计算中心（合肥）
例 4 发送一数组的 所有偶序数元素例 程 说 明
M P I _D a t a _t y pe 声明一个新的数据类型 E v e nEl e m e nt s,
M P I _T y pe _v e c t o r ( 50,1,2,M P I _ DOUBL E,& E
v e nEl e m e nt s)
产生一个导出数据类型 Ev e nEl e m e nt s,它由 50 个块组成,
每个块的组成是一个双精度数,后跟一个 8 字节的间隔,
接在后面的是下一块,st r i d e 是两个双精度数的大小,即
16 字节,8 字节的间隔用于跳过数组 A 的奇序数元素,
M P I _T y pe _c o m m i t ( & Ev e nEl e m e nt s) 这个 新类型必须在被发送例程使用前交付使用,
M P I _S e nd(A,1,Ev e nEl e m e nt s,dest i na t i o n,...) 注意,E v e nEl e m e nt s 的一个元素包含 A 的所有 50 个偶序数元素,因此,M P I _S e nd 的 c o unt 域值为 1,
double A[100];
MPI_Data_type EvenElements;
...,..
MPI_Type_vector(50,1,2,MPI_DOUBLE,&EvenElements);
MPI_Type_commit(&EvenElements);
MPI_Send(A,1,EvenElements,destination,...);
国家高性能计算中心（合肥）
说明,
MPI_Type_vector(count,blocklength,stride,oldtype,&newtype)
是构造导出数据类型的 MPI例程,
导出类型 newtype由 blocks的拷贝 count份组成,每块 (blocks)由已有的数据类型
oldtype的 blocklength份连续项的拷贝组成,
stride定义每两个连续的块之间的 oldtype元素个数,因此,(stride-blocklength)即是两个块之间的间隔,
1 MPI中的消息国家高性能计算中心（合肥）
消息缓冲 (message buffer,简称 buffer),在不同的消息传递使用场合有不同的含义,下面给出一些例子,
消息缓冲指的是由程序员定义的应用程序的存储区域,用于存放消息的数据值,
例如,在 Send(A,16,Q,tag)中,缓冲 A是在用户应用程序中声明的变量,
该缓冲的起始地址在消息例程中被使用,
消息缓冲也可以指由消息传递系统 (而非用户 )创建和管理的一些内存区,它用于发送消息时暂存消息,这种缓冲不在用户的应用程序中出现,有时被称为系统消息缓冲 (或系统缓冲 ).
MPI允许第三种可能的定义,用户可以划出一定大小的内存区,作为出现在其应用中的任意消息的中间缓冲,
消息缓冲
1 MPI中的消息国家高性能计算中心（合肥）
考虑下列代码,由进程 P传送一个存放在数组 A中的消息 M,到进程 Q的数组 B中,
例 5 在一对进程间发送消息
1 MPI中的消息国家高性能计算中心（合肥）
Process P
A
M
Process Q
B
Process P
A
M
Process Q
B
S
Process P
A
M
Process Q
B
T
(a) 只使用用户缓冲
(b) 使用系统缓冲 S
(c) 使用了用户级的临时缓冲 T
Process P:
double A[2000000];
send(A,32,Q,tag);
Process Q:
double B[32];
recv(B,32,P,tag)
国家高性能计算中心（合肥）
用户如何来定义消息的接收者呢? 在下面列出的 MPI发送例程中,消息信封由三项组成,
MPI_Send (address,count,datatype,destination,tag,communicator)
destination 域是一个整数,标识消息的接收进程,
消息标签 (message tag),也称为消息类型 (message type),是程序员用于标识不同类型消息、限制消息接收者的一个整数,
2 MPI中的消息信封国家高性能计算中心（合肥）
为什么要使用消息标签 (Tag)?
P r o ces s P,
s en d (A,3 2,Q )
s en d (B,1 6,Q )
P r o ces s Q,
r ecv (X,3 2,P)
r ecv (Y,1 6,P)
未使用标签
P r o ce s s P,
s en d (A,3 2,Q,ta g 1 )
s en d (B,1 6,Q,ta g 2 )
P r o ce s s Q,
r ec v (X,3 2,P,ta g 1 )
r ec v (Y,1 6,P,ta g 2 )
使用了标签为了说明为什么要用标签,我们先来看右面一段没有使用标签的代码,
这段代码打算传送 A的前 32
个字节进入 X,传送 B的前 16个字节进入 Y,但是,如果消息 B尽管后发送但先到达进程 Q,就会被第 一 个 r e c v ( ) 接收在 X 中,
使用标签可以避免这个错误,
2 MPI中的消息信封国家高性能计算中心（合肥）
使用标签的另一个原因是可以简化对下列情形的处理,
假定有两个客户进程 P
和 R,每个发送一个服务请求消息给服务进程 Q,
例 6 在消息传递中使用标签
P r oc e ss P,
sen d ( r e q u e st1,32,Q )
P r oc e ss R,
sen d ( r e q u e st2,32,Q )
P r oc e ss Q,
w h i l e ( t r u e ) {
r e c v ( r e c e i v e d _r e q u e st,32,An y _P r oc e ss ) ;
p r oc e ss r e c e i v e d _r e q u e st;
}
P r oce s s P,
s e n d ( r e q u e s t 1,32,Q,t ag 1)
P r oce s s R,
s e n d ( r e q u e s t 2,32,Q,t ag 2)
P r oce s s Q,
w h i l e ( t r u e ) {
r e c v ( r e c e i v e d _r e q u e s t,32,An y _P r oce s s,An y _T ag,S t atu s ) ;
i f ( S t atu s,T ag == t ag 1) p r oce s s r e c e i v e d _r e q u e s t i n on e w ay ;
i f ( S t atu s,T ag == t ag 2) p r oce s s r e c e i v e d _r e q u e s t i n an oth e r w ay ;
}
未使用标签使用了标签国家高性能计算中心（合肥）
通信子 (communicator):
一个进程组 (process group)+上下文 (context),
进程组,是进程的有限有序集,有限意味着,在一个进程组中,
进程的个数 n是有限的,这里的 n称为进程组的大小 (group
size),有序意味着 n 个进程是按整数 0,1,...,n-1进行编号的,
一个进程在一个通信子 (组 )中用它的编号进行标识,组的大小和进程编号可以通过调用以下的 MPI例程获得,
MPI_Comm_size(communicator,&group_size)
MPI_Comm_rank(communicator,&my_rank)
什么是通信子?
2 MPI中的消息信封
MPI_Send (address,count,datatype,destination,tag,communicator)
国家高性能计算中心（合肥）
例 7 通信子的使用
2 MPI中的消息信封
Process 0:
MPI_Send(msg1,count1,MPI_INT,1,tag1,comm1);
parallel_fft(...);
Process 1:
MPI_Recv(msg1,count1,MPI_INT,0,tag1,comm1);
parallel_fft(...);
if (my_rank==0) MPI_Send(msg2,count1,MPI_INT,1,tag2,comm2);
含代码含代码国家高性能计算中心（合肥）
存在问题,不可能保证 tag1 和 tag2一定取了不同的值,
标签是由用户定义的整数值,用户可能会出错,
即使用户不会弄错,也难以或不可能保证 tag1 和 tag2有不同的值,函数 parallel_fft( )可能是由其它用户写的,或者它是一个库例程,这样,用户可能不知道 tag2的值,
即使用户总能知道 tag2的值,仍然可能出错,因为 MPI_Recv
例程可能决定使用一个通配的 (wildcard)标签 MPI_Any_tag.
解决办法,在 parallel_fft( )中的通信使用不同的通信子,它可能包含相同的进程组 (如,进程 0和 1),但每个通信子有系统指定的不同的上下文,与 comm1的不同,因此,MPI_Recv 不再有偶然会从 parallel_fft( )的 MPI_Send中接收 msg2的危险了,
2 MPI中的消息信封国家高性能计算中心（合肥）
考虑如下由 10个进程执行的代码,
例 8 MPI中的新通信子
2 MPI中的消息信封
MPI_Comm MyWorld,SplitWorld;
int my_rank,group_size,Color,Key;
MPI_Init(&argc,&argv);
MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld);
MPI_Comm_rank(MyWorld,&my_rank);
MPI_Comm_size(MyWorld,&group_size);
Color=my_rank%3;
Key=my_rank/3;
MPI_Comm_split(MyWorld,Color,Key,&SplitWorld);
国家高性能计算中心（合肥）
MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld)
将创建一个新的通信子 MyWorld,它是包含与原始的 MPI_COMM_WORLD相同的 10个进程的进程组,但有不同的上下文,
表 分裂一个通信子 M y W or l d
R an k in My W orld 0 1 2 3 4 5 6 7 8 9
C olor 0 1 2 0 1 2 0 1 2 0
Key 0 0 0 1 1 1 2 2 2 3
R an k in Sp li tW orld(C olor=0) 0 1 2 3
R an k in Sp li tW orld(C olor=1) 0 1 2
R an k in Sp li tW orld(C olor=2) 0 1 2
2 MPI中的消息信封国家高性能计算中心（合肥）
MPI-1被设计成使不同通信子中的通信是相互分开的,以及任何群集通信是与任何点对点通信分开的,即使它们是在相同的通信子内,通信子概念尤其方便了并行库的开发,
MPI-1只支持组内通信 (intra-communication)
MPI-2支持组间通信 (inter-communication)
2 MPI中的消息信封国家高性能计算中心（合肥）
MPI消息特性的总结发送者进程总结如下例子,
MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD);
第一个参数指明消息缓存的起始地址,即存放要发送的数据信息,
第二个参数指明消息中给定的数据类型有多少项,这个数据类型由第三个参数给定,
数据类型要么是基本数据类型,要么是导出数据类型,后者由用户生成指定一个可能是由混合数据类型组成的非连续数据项,
第四个参数是目的进程的标识符 (进程编号 )
第五个是消息标签
第六个参数标识进程组和上下文,即,通信子,通常,消息只在同组的进程间传送,但是,MPI允许通过 intercommunicators在组间通信,
MPI_Send(buffer,count,datatype,destination,tag,communicator)
国家高性能计算中心（合肥）
发送者进程总结如下例,
MPI_Recv(&tmp,1,MPI_INT,i,i,MPI_COMM_WORLD,&Status)
第一个参数指明接收消息缓冲的起始地址,即存放接收消息的内存地址第二个参数指明给定数据类型的最大项数,它存放在第三个参数内,可以被接收,接收到的实际项数可能少一些第四个参数是源进程标识符 (编号 )
第五个是消息标签第六个参数标识一个通信子第七个参数是一个指针,指向一个结构
MPI_Status Status
存放了各种有关接收消息的各种信息,
Status.MPI_SOURCE 实际的源进程编号
Status.MPI_TAG 实际的消息标签实际接收到的数据项数由 MPI例程
MPI_Get_count(&Status,MPI_INT,&C)
读出,这个例程使用 Status中的信息来决定给定数据类型 (在这里是
MPI_INT)中的实际项数,将这个数放在变量 C中,
这两个域可以是 wildcard
MPI_Any_source和
MPI_Any_tag.
}
MPI_Recv(address,count,datatype,source,tag,communicator,status)
国家高性能计算中心（合肥）
当一个接收者能从不同进程接收不同大小和标签的信息时,状态信息就很有用,
例 9 消息传递中的状态 (Status)字
2 MPI中的消息信封
while (true){
MPI_Recv(received_request,100,MPI_BYTE,MPI_Any_source,
MPI_Any_tag,comm,&Status);
switch (Status.MPI_Tag) {
case tag_0,perform service type0;
case tag_1,perform service type1;
case tag_2,perform service type2;
}
}
国家高性能计算中心（合肥）
用在 MPI中的通信模式 (communication mode)
同步的 (synchronous)
直到相应的接收已经启动发送才返回,因此接收端要有存放到达消息的应用缓冲,
注意,在 MPI中可以有非阻塞的同步发送,它的返回不意味着消息已经被发出 ! 它的实现不需要在接收端有附加的缓冲,但需要在发送端有一个系统缓冲,为了消除额外的消息拷贝,应使用阻塞的同步发送,
3 MPI中的四种通信模式
S RSynchronous
1
2
3
国家高性能计算中心（合肥）
缓冲的 (buffered)
缓冲的发送假定能得到一定大小的缓冲空间,它必须事先由用户程序通过调用子例程 MPI_Buffer_attch(buffer,size)
来定义,由它来分配大小为 size的用户缓冲,这个缓冲可以用
MPI_Buffer_detach(*buffer,*size )来实现,
S RBuffer
1 2
3 MPI中的四种通信模式国家高性能计算中心（合肥）
Standard S R1
S RReady
1
2
标准的 (standard)
发送可以是同步的或缓冲的,取决于实现,
就绪的 (ready)
在肯定相应的接收已经开始才进行发送,它不像在同步模式中那样需要等待,这就允许在相同的情况下实际使用一个更有效的通信协议,
3 MPI中的四种通信模式国家高性能计算中心（合肥）
表 M P I 中不同的发送和接收操作
M P I P rim it ive B loc k ing N o n - B loc k ing
S tan d a rd S en d M P I_ S en d M P I_ Ise n d
S y n ch r o n o u s Se n d M P I_ S sen d M P I_ Iss en d
B u ffer ed S en d M P I_ B sen d M P I_ Ib sen d
R ea d y S en d M P I_ R sen d M P I_ Irs en d
R ec eiv e M P I_ R ec v M P I_ Ir ec v
C o m p leti o n C h ec k M P I_ W a it M P I_ T est
4 点对点的通信国家高性能计算中心（合肥）
例 10 使用消息传递的进程流水线
X=P(W)
W
Y=Q(X)
X
Z=R(Y)
Y Z
进程流水线中的数据流图中是一条三进程的流水线,一个进程连续地从左边接收一个输入数据流,计算一个新的值,将它发送给右边,下面的代码示出了基本思想,
进程 Q的一段代码
while (Not_Done){
MPI_Irevc(NextX,...);
MPI_Isend(PreviousY,...);
CurrentY=Q(CurrentX);
}
4 点对点的通信国家高性能计算中心（合肥）
进程 Q的代码
while (Not_Done){
if (X==Xbuf0) {X=Xbuf1; Y=Ybuf1; Xin=Xbuf0; Yout=Ybuf0;}
else {X=Xbuf0; Y=Ybuf0; Xin=Xbuf1; Yout=Ybuf1;}
MPI_Irevc(Xin,...,recv_handle);
MPI_Isend(Yout,...,send_handle);
Y=Q(X); /* 重迭计算 */
MPI_Wait(recv_handle,recv_status);
MPI_Wait(send_handle,send_status);
}
Xbuf 0
Receive X
Y=Q(X)
YBuf0
Send Y
Xbuf 1 Ybuf1
进程流水线中的双缓冲
4 点对点的通信国家高性能计算中心（合肥）
例 11 发送和接收中的死锁这是一段错误代码,可能会有下列结果,
死锁,例程 MPI_Issend是非阻塞的、同步的发送,它直到相应的
MPI_Irecv 已经启动执行才返回,如果条件 Y==5不为真,则 MPI_Irecv就不会被执行,
Y为 0.假定当 if语句被执行后 Y==5为真,则 MPI_Irecv会从进程 P接收 X
的值 (为 0)到它的变量 Y,并打印它,
Y为 5.另一个可能的情况是当 Y==5为真时,打印会在接收到 X的值并存入 Y之前执行 (因为 MPI_Irecv是非阻塞的接收 ),因此打印出的是 Y的旧值,
Process P:
...,..
X=0;
MPI_Issend(&X,...,Q,...);
Process Q
...,..
if (Y==5)MPI_Irecv(&Y,...,P,...);
printf(“Y is %d”,Y);
4 点对点的通信国家高性能计算中心（合肥）
广播 (Broadcast)
d a t a
b r o a d c a s t
( a )
A 0
A 0
A 0
A 0
A 0
A 0
A 0
p
r
o
c
e
s
s
e
sMPI_Bcast(Address,Count,Datatype,Root,Comm)
在下列 broadcast操作中,
标号为 Root的进程发送相同的消息给标记为 Comm
的通信子中的所有进程,
消息的内容如同点对点通 信 一 样 由 三 元 组
(Address,Count,Datatype)
标识,对 Root进程来说,这个三元组既定义了发送缓冲也定义了接收缓冲,对其它进程来说,这个三元组只定义了接收缓冲,
5 群集通信国家高性能计算中心（合肥）
聚集 (Gather)
MPI_Gather (SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Root,Comm)
5 群集通信播撒 (Scatter)
MPI_Scatter (SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Root,Comm)
国家高性能计算中心（合肥）
MPI_Scatter
Scatter只执行与 Gather相反的操作,Root
进程发送给所有 n个进程发送一个不同的消息,包括它自已,这 n个消息在 Root进程的发送缓冲区中按标号的顺序有序地存放,每个接收缓冲由三元组 (RecvAddress,
RecvCount,RecvDatatype)标识,所有的非 Root进程忽略发送缓冲,对 Root进程,
发送缓冲由三元组 (SendAddress,
SendCount,SendDatatype)标识,
5 群集通信
MPI_ Gather
Root进程从 n个进程的每一个接收各个进程 (包括它自已 )的消息,这 n个消息的连接按序号 rank进行,存放在 Root进程的接收缓冲中,每个发送缓冲由三元组
(SendAddress,SendCount,SendDatatype)
标识,所有非 Root进程忽略接收缓冲,对
Root进程,发送缓冲由三元组
(RecvAddress,RecvCount,RecvDatatype)
标识,
A 1
A 4
A 0
A 5
A 2
A 3
s c a t t e r
g a t he r
( b)
A 1 A 4A 0 A 5A 2 A 3
国家高性能计算中心（合肥）
扩展的聚集和播撒操作 Allgather
MPI_Allgather ( SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Comm )
5 群集通信
a l l g a t he r
( c )
B 0
E 0
A 0
F 0
C 0
D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
国家高性能计算中心（合肥）
全局交换 (Tatal Exchange)
A 1
A 4
A 0
A 5
A 2
A 3
a l l t o a l l
( d )
A 1 A 4A 0 A 5A 2 A 3
B 1 B 4B 0 B 5B 2 B 3
C 1 C 4C 0 C 5C 2 C 3
D 1 D 4D 0 D 5D 2 D 3
E 1 E 4E 0 E 5E 2 E 3
F 1 F 4F 0 D 5F 2 F 3
B 1
B 4
B 0
B 5
B 2
B 3
C 1
C 4
C 0
C 5
C 2
C 3
D 1
D 4
D 0
D 5
D 2
D 3
E 1
E 4
E 0
E 5
E 2
E 3
F 1
F 4
F 0
D 5
F 2
F 3
每个进程发送一个消息给所有 n
个进程,包括它自已,这 n个消息在它的发送缓冲中以标号的顺序有序地存放,从另一个角度来看这个通信,每个进程都从 n个进程接收一个消息,这 n个消息以标号的顺序被连接起来,存放在接收缓冲中,注意,全局交换等于由 n
个不同进程做的 n次 Gather操作,
因此,不再需要 Root参数,所有对所有,在一次全局交换中共有 n2
个消息进行通信,
MPI_Alltoall(SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Comm)
5 群集通信国家高性能计算中心（合肥）
MPI提供了两种类型的聚合操作,归约 (reduction)和扫描
(scan),
归约 (reduction)
MPI_Reduce(SendAddress,RecvAddress,Count,Datatype,
Op,Root,Comm)
这里每个进程的部分值存放在 SendAddress中,所有进程将这些值归约为最终结果并将它存入 Root进程的 RecvAddress,数据项的数据类型在 Datatype域中定义,归约操作由 Op域定义,
聚合 (Aggregation)
5 群集通信国家高性能计算中心（合肥）
扫描 (scan)
MPI_scan(SendAddress,RecvAddress,Count,Datatype,
Op,Comm)
scan操作省去了 Root域,因为 scan是将部分值组合成 n个最终值,并存放在 n个进程的 RecvAddress,scan操作由 Op域定义,
MPI的 reduction和 scan操作允许每个进程贡献向量值,而不只是标量值,向量的长度由 Count定义,MPI支持用户自定义的 reduction和 scan操作
5 群集通信国家高性能计算中心（合肥）
在路障操作中,通信子 Comm中的所有进程相互同步,即,它们相互等待,直到所有进程都执行了他们各自的
MPI_Barrier函数,
路障 (Barrier)
MPI_Barrier(Comm)
5 群集通信国家高性能计算中心（合肥）
表 MPI 中的群集通信
T ype Routin e Function ality
MPI_Bcast 一对多播送相同的信息
MPI_Gather 多对一收集个人信息
MPI_Gatherv 通用的 MPI_Gather
MPI_All gather 全局收集操作
MPI_All gatherv 通用的 MPI_All gather
MPI_Scatter 一对多播撒个人信息
MPI_Scatterv 通用的 MPI_Scatter
MPI_All toall 多 对多全交换个人信息
Data m ovem ent
MPI_All toall v 通用的 MPI_All toall
MPI_Reduce 多对一归约
MPI_All r educe 通用的 MPI_Reduce
MPI_Reduce_scatter 通用的 MPI_Reduce
Aggr egation
MPI_Scan 多对多并行 pr efix
Synchr onizati on MPI_Barrier 路障同步
5 群集通信国家高性能计算中心（合肥）
通信子中的所有进程必须调用群集通信例程,如果代码中只有通信子中的一部分成员调用了一个群集例程而其它没有调用,则是错误的,一个错误代码的行为是不确定的,意味着它可能发生任何事情,包括死锁或产生错误的结果,
一个进程一旦结束了它所参与的群集操作就从群集例程中返回,
除了 MPI_Barrier以外,每个群集例程使用类似于点对点通信中的标准
(standard)、阻塞的通信模式,
例如,当 Root进程从 MPI_Bcast中返回时,它就意味着发送缓冲的 Address
可以被安全地再次使用,其它进程可能还没有启动它们相应的 MPI_Bcast!
一个群集例程也许是也许不是同步的,取决于实现,MPI要求用户负责保证他的代码无论实现是否是同步的都是正确的,
Count 和 Datatype在所包含的所有进程中必须是一致的,
在群集例程中没有 tag参数,消息信封由通信子参数和源 /目的进程定义,
例如,在 MPI_Bcast中,消息的源是 Root,目的是所有进程 (包括 Root).
在 MPI-1 中,只支持阻塞和通信子内 (intra-communicator)群集通信,
群集例程的共同特点
5 群集通信国家高性能计算中心（合肥）
6 MPI扩展
MPI-2对 MPI-1的扩展
动态进程
单边通信
非阻塞群集通信模式和通信子间群集通信模式,
对可扩展的 I/O的支持,叫做 MPI-IO,在 MPI-1中,I/O问题全部忽略,
MPI-1只定义对 Fortran77和 C语言的绑定,MPI-2将语言绑定扩展到 Fortran90和 C++.
对实时处理的支持,
扩展了 MPI-1的外部接口,以便使环境工具的开发者更易于访问 MPI对象,这将有助于开发剖析 (profiling),监视
(monitoring)和调试 (debugging)工具,
国家高性能计算中心（合肥）
动态进程
MPI-2决定支持动态进程,这带来了以下好处,
MPI-1不定义如何创建进程和如何建立通信,因此,MPI-
1需要支撑平台提供这种能力,像 SP2中的 POE和工作站网络中的 rsh,MPI-2中的动态进程机制 以可移植的方式 (平台独立 )提供了这种能力
动态进程 有利于将 PVM程序移植到 MPI上,并且还可能支持一些重要的应用类型,如,Client/Server和 Process farm.
动态进程 允许更有效地使用资源和负载平衡,例如,所用节点数可以按需要减少和增加
支持容错,当一个结点失效,运行在其上的进程能在另一个结点上创建一个新进程完成其工作,
6 MPI扩展国家高性能计算中心（合肥）
int MPI_Spawn (
char* command_line,
int minprocs,
int maxprocs,
char* info,
int root,
MPI_Comm comm,
MPI_Comm* intercomm
int* array_of_errcodes
)
/* 可执行程序和参数 */
/* 最少要派生的进程数 */
/* 最多要派生的进程数 */
/* 在何处何时启动该进程 */
/* 根进程的编号 */
/* 根进程的通信子 */
/* comm与新派生的进程组间的互连通信子 */
/* 每个派生进程一个出错代码 */
这个函数试图派生 maxprocs个子进程,每个子进程执行相同代码,这个代码在 command_line中定义,如果 MPI不能派生 maxprocs个进程,它可以按
minprocs指定的数目派生进程,如果它连 minprocs个进程都派生不了,
MPI_Spawn就返回一个出错代码,info 必须是一个空串,允许运行时系统决定何地、如何启动该进程,
6 MPI扩展国家高性能计算中心（合肥）
MPI_Spawn是一个群集操作,也就是说,通信子 comm中的所有成员必须调用它派生进程,但是,只有 root进程中的参数
command_line,minprocs,maxprocs,和 info是有意义的,而忽略其它进程上的这些参数值,这样,尽管派生的进程可以看成
comm中所有进程的子进程,但只有 root进程是真正的父进程,
子进程是 MPI进程意味着它们必须调用 MPI_Initialize,它与父进程中的 MPI_Spawn同是群集操作,子进程和父进程可以通过 intercommunicator intercomm 进行通信,它从父进程中的
MPI_Spawn返回,子进程通过调用 MPI_parent函数能获得
intercommunicator的句柄,MPI_parent函数的形式如下,
int MPI_Parent(MPI_Comm* intercomm)
6 MPI扩展国家高性能计算中心（合肥）
单边通信
MPI-2包括一个新的点对点通信模式,叫做远程存储访问 (remote memory access,RMA),它允许一个进程执行单边通信,即,一个进程可以发送一个数据值到一个目的地,
也可以从一个数据源取一个数据值,无需另一边的参与,
在 MPI-1中,所有的点对点通信都是双边的,发送者和接收者都必需参与,
6 MPI扩展国家高性能计算中心（合肥）
int MPI_Get (
void* dest_addr,
MPI_Init dest_count,
MPI_Datatype dest_datatype,
int source_rank,
int source_disp,
int source_count,
MPI_Datatype source_datatype,
MPI_Comm comm
)
单边接收 (MPI_get)
6 MPI扩展国家高性能计算中心（合肥）
int MPI_Put (
void* source_addr,
MPI_Init source_count,
MPI_Datatype source_datatype,
int dest_rank,
int dest_disp,
int dest_count,
MPI_Datatype dest_datatype,
MPI_Comm comm
)
单边发送 (MPI_Put)
6 MPI扩展国家高性能计算中心（合肥）
7 例子,计算 Pi的 MPI程序
#include <stdio.h>
#include <mpi.h>
#include <math.h>
long n,/*number of slices */
i; /* slice counter */
double sum,/* running sum */
pi,/* approximate value of pi */
mypi,
x,/* independent var,*/
h; /* base of slice */
int group_size,my_rank;
main(argc,argv)
int argc;
char* argv[];
国家高性能计算中心（合肥）
{ int group_size,my_rank;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_rank( MPI_COMM_WORLD,&my_rank);
MPI_Comm_size( MPI_COMM_WORLD,&group_size);
n=2000;
/* Broadcast n to all other nodes */
MPI_Bcast(&n,1,MPI_LONG,0,MPI_COMM_WORLD);
h = 1.0/(double) n;
sum = 0.0;
for (i = my_rank+1; i <= n; i += group_size) {
x = h*(i-0.5);
sum = sum +4.0/(1.0+x*x);
}
mypi = h*sum;
/*Global sum */
MPI_Reduce(&mypi,&pi,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_W
ORLD);
if(my_rank==0) { /* Node 0 handles output */
printf("pi is approximately,%.16lf\n",pi);
}
MPI_Finalize();
}
国家高性能计算中心（合肥）
编译：
mpicc -o pi pi.c
运行：
mpirun -np 2 pi
7 例子,计算 Pi的 MPI程序国家高性能计算中心（合肥）
提纲
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
并行虚拟机 (PVM)
1 并行虚拟机的构造
2 PVM中的进程管理
3 PVM中的通信
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
1 并行虚拟机的构造
PVM系统的组成 (两部分 )
PVM监控进程 (daemon),称为 pvmd,它常驻在虚拟机的每个计算机上
用户可调用的库,称为 libpvm3.a,它与用户的应用程序链接,用于进程管理,消息传递和虚拟机管理,
在 PVM中,节点 (a node)称为 主机 (a host),进程 (a process)
称为 任务 (a task),
并行虚拟机的组成
1~多台主机 (硬件 )
唯一 1个 master pvmd(系统软件 ),运行在称为控制台的主机上
0~多个 slave pvmd(系统软件 )
国家高性能计算中心（合肥）
PVM 控制台 (Console)
安装了 PVM后,用户在任何一台主机上键入以下命令创建 PVM控制台,
pvm host_file
这个命令执行成功后将在调用它的主机和 host_file文件中所列的每台主机上启动一个 pvmd监控进程,并在调用它的主机上显示下列提示符,
pvm>
它指示主机当前处于 PVM控制台模式,
pvmd 的启动方法
master pvmd,必须手工启动
slave pvmds,只能由 master pvmd依次启动
master pvmd启动 slave pvmd的方法用 rsh,rexec(),或其它方法启动一个 slave
1 并行虚拟机的构造国家高性能计算中心（合肥）
表 主要的 PVM 控制命令命 令 含 义
pv m > ad d a ppl e 将主机,app le” 加入到虚拟机中
pv m > de let e a ppl e 从虚拟机中删除主机,app le”
pv m > co nf 列出虚拟机的配置
pv m > sp aw n – co unt 4 ap p 在虚拟机上启动 4 个任务运行,app,
pv m > job s 列出运行在虚拟机上的作业
pv m > ha lt 中止所有 PVM 进程,关闭 PVM
主要的 PVM命令
1 并行虚拟机的构造国家高性能计算中心（合肥）
启动文件,host_file
并行虚拟机的硬件配置在主机表 (host table)文件中说明,
它常驻在虚拟机的每台主机上,主机表中有一项叫做主机描述子 (host descriptor),对应于虚拟机中的每台主机,主机描述子中保存有主机配置信息,以及 packet queues 和通信信息缓冲,
最初,主机表只有 master host一项,当一个新的 slave加入到虚拟机后,master host的主机表被修改,添加一个与新加入的 slave对应的新项,然后,修改后的主机表的信息被播送到整个虚拟机,包括新加入的 slave hosts,这样,虚拟机中所有主机的主机表被同步,并且保持一致,除非哪台机器不转了或网络失效,
1 并行虚拟机的构造国家高性能计算中心（合肥）
虚拟机的动态配置用户可以调用 PVM库函数来动态配置虚拟机,
pvm_addhosts函数,向虚拟机中加入一至多台主机
pvm_delhosts 函数,从虚拟机中删除一至多台主机例子
int info,nhost=2,infos[2];
char *host[]={“apple”,“orange.cs.ustc.edu.cn”}
info=pvm_addhosts(hosts,nhost,infos);
info=pvm_delhosts(hosts,nhost,infos);
1 并行虚拟机的构造国家高性能计算中心（合肥）
task T(用户进程 ) pvmd2(系统进程 )
pvm_addhosts()
Blocked
finished
dm_addhost()
dm_htupd()
dm_htcommit()
dm_addhostack()
pvmd1(系统进程 )
dm_addhost()
dm_startack()
dm_htupdack()
pvmd3(系统进程 )
slave_config()
dm_htupd()
dm_htcommit()
host H2(slave) host H1(master) host H3(new slave)
图 动态加入一个主机 H3
国家高性能计算中心（合肥）
PVM支持实现静态和动态的并行性静态并行程序例子,foo为一个 SPMD程序,在控制台上执行命令
pvm>spawn –count 4 foo
将创建一个 4个任务 (或进程 )的并行应用,运行在虚拟机上,每个任务执行同一个代码 foo,如果 foo不调用动态任务创建函数 pvm_spawn(),这个应用将有一个静态的 DOP(并发度 )为 4.
2 PVM中的进程管理国家高性能计算中心（合肥）
程序到主机的映射
缺省,由 PVM提供的应用算法将任务映射到主机上,每台主机上可映射多个任务,
用户自定义,由用户为每个任务显式地定义一个特定的主机或体系结构类型例子,在控制台上执行命令,
pvm> spawn –(apple) foo
将在主机 apple上启动一个任务执行代码 foo
pvm> spawn –(RS6K) foo
将在任意的 RS/6000节点上使用 AIX操作系统启动一个任务执行代码 foo
2 PVM中的进程管理国家高性能计算中心（合肥）
动态并行程序与进程管理
PVM支持开发 MPMD并行程序和动态进程管理,最重要的函数是 pvm_spawn(),
int numt // 实际被启动的任务数
=pvm_spawn(
char *progm,// 可执行文件名
char **argv,// 指向参数数组的指针
int flag,// 选项
char *where,// 与 flag配合使用
int ntask,// 可执行文件启动的拷贝数
int *tid // 保存派生任务的 tid
)
2 PVM中的进程管理国家高性能计算中心（合肥）
表 pvm _spaw n 中的 f lag 参数选项符号
(O ption Sym bol )
选项值
( Option V alu e )
含义
P vm T askDe f aul t 0 主机由 P V M 选择
P vm T askHost 1 主机由某处定义
P vm T askAr c h 2 体系结构由某处定义
P vm T askDe bu g 4 在调试状态下启动进程
P vm T askT r ac e 8 将生成 P V M 跟踪数据
P vm M pp F r ont 16 在 M P P 前端启动进程
P vm Host C om pl 32 使用 c om pl e m e nt 主机集合
2 PVM中的进程管理国家高性能计算中心（合肥）
表 PVM 进程管理函数
PVM 函数调用 含义
tid= pvm _m ytid (); 获取调用任务的任务标识号
tid= pvm _pa r ent() ; 获取父任务的任务标识号
info = pvm _ex it(); 正在调用的任务退出 P VM,继续作为 UN IX 进程运行,
Num t= pvm _sp aw n(..,); 派生一个 PVM 任务
info = pvm _k ill(tid) ; 终止一个 PVM 任务
tsta t= pvm _ps tat( tid); 获取一个 PVM 任务的状态
info = pvm _ta sk s(.,,); 获取运行 在虚拟机上的所有任务的信息
Msta t= pvm _m stat (ho st); 获取一个主机的状态
info = pvm _con fig(..,); 获取整个虚拟机的配置信息
2 PVM中的进程管理国家高性能计算中心（合肥）
PVM支持动态分组,任何任务都可以在任意时候加入或离开一个组,
PVM 的分组功能由一个叫做 group server的 daemon完成,当第一个组函数被调用时自动地启动这个 daemon.
PVM动态分组概念是很灵活的,可以有多个组,一个任务在任何时候可以属于不同的组,一个任务可以在任何时候加入和离开一个组,无需通知组内的其它成员 (不像 MPI,一个任务在一组内总有一个唯一的编号 ),
一个任务可以播送一个消息给一个组,即使它不是这个组的成员,
动态分组带来程序行为的非确定性,
例如,
一个播送操作可以有不同的结果,如果一个任务加入或离开一个组,任务可能会也可能不会得到这个广播的消息,
如果成员任务离开一个组,路障同步操作可能会死锁,
2 PVM中的进程管理国家高性能计算中心（合肥）
表 PVM 组函数
PVM 函数调用 含义
inu m = pvm _jo ing r oup (,w orld,); 调用任务加入 W orld 组并被分配一个成员
inu m,
inf o= pvm _lv gr oup (,w orld,); 调用任务离开 W orld 组
tid = pvm _get tid (,w orld,,inu m ); 从成员号中获取任务的标识号
inu m = pvm _get ins t(,w orld,,tid ); 从任务的标识号获取成员号
gsi ze= pvm _gs ize(,w orld,); 获取组的大小
inf o= pvm _ba rrier(,w orld,,10) ; 调用任务阻塞 ( 等待 ) 直到 W orld 的 10 个成员调用了 pvm _ba rrier
inf o= pvm _bca st(,w orld,,tag ); 播送一个由标签标识的消息给所 W orld 的有成员
inf o= pvm _r educe(,,,); 类似于 MPI 的 r educt ion
2 PVM中的进程管理国家高性能计算中心（合肥）
S G H L
31 30 29 18 17 0
图 PVM通用的任务标识符 TID格式表 任务标识符的解释
S G H L 含义
0 0 1.,40 95 1.,26 21 43 任务标识符
0 1 1.,40 95 不关心 M ul tic as t 地址
1 0 0 0 本地 pv m d
1 0 1.,40 95 0 pvm 标识
1 1 S m al l neg at iv e num be r 错误代码
2 PVM中的进程管理国家高性能计算中心（合肥）
task1
pvmd1
task2
pvmd2UDP
TCP TCP
TCP
图 通用的 PVM中所用的通信协议
PVM有三种类型的通信,
pvmd间通信
pvmd与其任务间的通信
以及两个任务间的通信
3 PVM中的通信国家高性能计算中心（合肥）
int bufid =pvm_initsend(int encoding)
int info=pvm_pkint(int * p,int nitem,int stride)
int info=pvm_send(int tid,int tag)
int info=pvm_mcast(int *tids,int ntasks,int tag)
int bufid=pvm_recv(int tid,int tag)
int bufid=pvm_nrecv(int tid,int tag)
int bufid=pvm_trecv(int tid,int tag,struct timeval *tmout)
int bufid=pvm_probe(int tid,int tag)
int bufid=pvm_bufinfo(int bufid,int *bytes,int *tag,int *tid)
int info=pvm_upkint(int *p,int nitem,int stride)
3 PVM中的通信
PVM通信函数实例国家高性能计算中心（合肥）
#define n 16 /* number of tasks */
#include,pvm3.h”
main(int argc,char **argv)
{
int mytid,tids[n],me,i,N,rc,parent;
double mypi,h,sum=0.0,x;
me=pvm_joingroup(,PI”);
parent=pvm_parent( );
if (me= =0) {
pvm_spawn(,pi”,(char**)0,0,“”,n-1,tids);
printf(“Enter the number of regions:”);
scanf(,%d”,&N);
pvm_initsend(PvmDataRaw);
pvm_pkint(&N,1,1);
pvm_mcast(tids,n-1,5);
}
else {
pvm_recv(parent,5);
pvm_upkint(&N,1,1);
}
pvm_barrier(,PI”,n); /* optional */
h=1.0/(double) N;
for (i=me+1;i<=N; i+=n){
x=h*((double)i-0.5);
sum+=4.0/(1.0+x*x);
}
mypi=h*sum;
pvm_reduce(PvmSum,&mypi,1,PVM_DOUBLE,6,“PI”,0);
if (me==0) printf(,pi is approximately %.16f\n”,mypi);
pvm_lvgroup(,PI”);
pvm_exit();
}
4 例子,计算 π的 PVM程序这个 SPMD程序划分间隔 [0,1]
进入 N个区域,并启用 n个任务,每个任务负责由 N/n区域计算一个部分和 mypi,然后这 n个部分和由归约 (reduction)操作聚积成一个总和,
国家高性能计算中心（合肥）
假定源码包含在文件 pi.c中,可执行文件 pi用以下命令得到,
cc –I/pvm3/include pi.c libgpvm3.a libpvm3.a –o pi
用户调用第一个任务,它派生出其它 n-1个任务,每个任务首先用以下语句,
me=pvm_joingroup(,PI”);
加入一个组 PI,变量 me将包含组内任务的编号 (实例号 ),初始任务的编号为 0,
下一条语句
parent= pvm_parent();
找出父任务的 ID,初始任务没有父亲,这个函数调用返回 0,
对其它任务,这个函数调用返回初始任务的 ID,
4 例子,计算 π的 PVM程序国家高性能计算中心（合肥）
初始任务执行
pvm_spawn(,pi”,(char**)0,0,“”,n-1,tids);
派生 n-1个子任务,执行文件,pi”中的代码和他们的任务 ID在数组 tids中返回,其它三个参数为 null(0),这是许多
PVM程序的典型情况,
初始任务执行下面的代码提示用户键入变量 N中的区域数,
printf(,Enter the number of regions:”);
scanf(“%d”,&N);
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
然后,它执行下列代码将这个值播送给所有子任务,
pvm_initsend(PvmDataRaw);
pvm_pkint(&N,1,1);
pvm_mcast(tids,n-1,5);
这里,5是一个任意的消息标签,
同时,每个子任务将执行下列代码匹配这个播送,
pvm_recv(parent,5); /* 5是与 pvm_mcast中的标签相匹配的标签 */
pvm_upkint(&N,1,1);
然后所有的任务执行一个路障同步,
pvm_barrier(,PI”,n); /* 在组 PI中的 n个任务应在此同步 */
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
接下来的几行只是正常的计算,
h=1.0/(double) N;
for (i=me+1;i<=N; i+=n){
x=h*((double)i-0.5);
sum+=4.0/(1.0+x*x);
}
mypi=h*sum;
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
接下来做归约操作,
pvm_reduce(PvmSum,&mypi,1,PVM_DOUBLE,6,“PI”,0);
这是一个组 PI中所有的任务的求和归约,每个任务从本地 mypi
贡献一个类型为 PVM_DOUBLE数据项,最终的结果存放在初始任务 (编号为 0)的 mypi中,数 6也是一个任意的消息标签,
一般地,一个 PVM归约具有以下函数原型
pvm_reduce(void(*func)(),void *buffer,int nitem,int datatype,
int tag,char *group,int root);
打印出这个结果后,程序调用以下函数清理环境
pvm_lvgroup(“PI”) and pvm_exit(),
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
编译：
pvmcc -o pi pi.c
运行：
$>pvmd –d7 host_file&
$>pvm
pvm>span –4 pi
pvm>halt
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
提纲
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
数据并行模型的特点
单线程
在密集的数据结构上的并行操作
全局命名空间
隐式的同步和通信
隐式的计算和数据分布
具有很好的可移植性,包括 SIMD,MIMD,共享和分布存储机器数据并行模型的目的是要在分布存储的机器上实现在全局名空间进行并行程序设计,以屏蔽显式的数据分布和通信问题,
是一种细粒度的并行,
与消息传递模型相比,数据并行程序设计能在一定程度上减轻程序员的负担,但是完全依赖于程序员能否确定一个好的数据分布,
数据并行程序设计国家高性能计算中心（合肥）
数据并行语言的发展
在 SIMD机器 ILLIAC IV开发的语言 IVTRAN,是最早的允许用户控制数据布局的语言
Kali
Fortran D/Vienna Fortran
Fortran 90/ Fortran 95
Thinking Machines公司的 C*/CM Fortran /*Lisp
HPF/HPF+/F--/HPC++/HPJava
数据并行程序设计国家高性能计算中心（合肥）
提纲
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
1 高性能 Fortran(HPF)简介
2 HPF的数据并行机制
3 例子,高斯消去法的 HPF程序
HPF并行编程国家高性能计算中心（合肥）
1 高性能 Fortran(HPF)简介发展历史
1991年,DEC的 D.Lovman和 Rice大学的 K.Kennedy在
Supercomputing’91大会上提出了他们的高性能 Fortran版本,
以统一在分布存储机器上的编程方法
1992年 1月,在 Rice大学召开了第一次 HPF会议,一致通过组织 HPF论坛
1992年 3月,该论坛正式成立
1993年 5 月,发布了 HPF 1.0版 基于 Fortran90
1994年 11月发布了 HPF 1.1版
1997年 1月,论坛发布了 HPF 2.0 基于 Fortran 95
国家高性能计算中心（合肥）
对 HPF的批评主要有三个方面,
认为 HPF是一个太高层的语言,不如 MPI风格的语言适用 ;
认为 HPF是一个太低层的语言,通过改进语言编译技术和体系结构完全可以避开 HPF风格的语言所要求的编译制导 ;
认为 HPF尽管抽象层次适当,但还要作一些扩充才能满足在某些将来的体系结构上处理某些应用的需要,
1 高性能 Fortran(HPF)简介国家高性能计算中心（合肥）
HPF主要的设计目标如下,
(1) 支持数据并行程序设计 ;
(2) 最大限度地发挥非均匀存储访问的 MIMD和 SIMD计算机的性能 ;
(3) 能够调整代码适应各种体系结构的计算机,
HPF2.0语言的组成包括三个部分,
(1) 语言的基本部分,包括任何 HPF编译器必须支持的特性 ;
(2) 已经核准的扩展部分,包括满足某些特殊需要的高级结构,早期的编译器可能不支持这部分 ;
(3) 已被承认的外部接口,是 HPF论坛批准的一组接口,但是由他人设计并为 HPF用户提供具体的服务内容,
1 高性能 Fortran(HPF)简介国家高性能计算中心（合肥）
HPF2.0的一些基本特性如下,
(1) 数据并行说明 (Data parallel directives):达到第一个目标
INDEPENDENT：声明一个循环没有依赖,可以并行执行
REDUCTION：标识被不同迭代使用结合的和可交换的运算修改的变量
(2) 数据映射说明 (Data mapping directives):达到第二个目标
ALIGN：数据对准
DISTRIBUTE：数据分布（映射）
声明如何在处理器间分配数据,使得通信开销最小,负载平衡,
(3) 新的内部函数和库函数 (New intrinsic and library functions):
用于实现第三个目标,允许用户利用特定机器的低层特性,
归约 (reduction)函数／组合分散 (Combining-Scatter)函数,
前缀 (Prefix)/后缀 (Suffix)函数
分类 (Sorting)函数 /位操作 (Bit-Manipulation)函数
(4) 外部过程 (Extrinsic procedures),用于匹配其它的编程方法，
支持混合语言编程国家高性能计算中心（合肥）
3.1 FORALL结构 (FORALL construct)
例 1 简单的 FORALL语句
FORALL (K=1,M―1) X (K+1)=X(K)
注释,语句执行后,X(I―1) 的值送入 X ( I )中,
FORALL (I=1:N,J=1,N) X(I,J) = Y (J,I)
注释,语句执行后,Y的转置矩阵被送入 X,
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 2 带限制的 FORALL语句
FORALL (i=2:5,X(i)>0) X(i)=X(i―1)+X(i+1)
注释,
i是索引变量,i=2:5称为 for-三元组,等价于 i=2:5:1,表示 i
的变化范围下界是 2,上界是 5,缺省步长为 1,即 i的有效值取
{2,3,4,5},
假设在上述 FORALL语句中,初始 X={1,―1,2,―2,3,―3},
在 i的有效值范围内,满足 X(i)>0 的索引 i的活动集合为 {3,
5},求出这个活动索引值集合后,所有赋值表达式同时计算,
X(3) <= X(3-1)+X(3+1)= ―3
X(5) <= X(5-1)+X(5+1)= ―5
FORALL语句结束后,X={1,―1,―3,―2,―5,―3}.
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 3
FORALL (K=1:M,Y(K).NE.0.0) X (K)=1.0/Y(K)
注释,对 Y(K)的值不为 0的 K,把 Y(K)的倒数送入 X(K).
例 4 在 FORALL语句中,可能有不止一个 for-三元组,则用的是联合索引,
FORALL(i=1:2,j=1:3,Y(i,j)>0) Z(i,j)=1/Y(i,j)
注释,该语句等价于 Fortran90语句
where (Y(1:2,1:3)>0) Z(1:2,1:3)= 1/ Y(1:2,1:3)
则联合索引的有效值取集合
{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)},联合索引的活动值取上述集合中使 Y(i,j)>0的子集,
2 HPF的数据并行机制国家高性能计算中心（合肥）
有时,用户希望在一个 FORALL语句中包含几个赋值,这可用 FORALL结构来实现,FORALL结构是对 FORALL语句的进一步扩充,即在 FORALL和 ENDFORALL之间,可以写多条语句,但限制 FORALL结构中只能使用赋值语句,FORALL语句、
FORALL结构,WHERE语句及 WHILE结构,
例 5
FORALL (I=2,9)
A(I) = A(I―1) + A(I+1)
B(I) = A(I)
ENDFORALL
注释,首先,对从 2到 9的各 I,求值 A(I―1)+A(I+1),然后,将其结果送入 A(2)到 A(9)中,再将求得的 A(2)到 A(9)的值送入 B(2)到
B(9)中,
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 6
FORALL(i=1:n)
A (i) = sin (B(i));
C (i) = sqrt (A(i)* A(i))
D (i) = B (i)+2
ENDFORALL
2 HPF的数据并行机制国家高性能计算中心（合肥）
3.2 数据映射 (Data mapping)
数据映射,指的是将数据分布到处理器上,要在分布存储系统上实现并行处理,首先要对数据 (主要是数组 )进行划分,然后分配给各个处理机,再在各个处理器上进行计算,
数据映射要达到以下目的,
(1) 使处理器间的通信开销最小 ;
(2) 负载在可用的处理器间均匀分布,
HPF编译器可以利用 owner-compute 规则分布负载,在数据所在的处理器上执行与该数据有关的计算,因此数据映射直接决定负载分布,HPF提供了许多说明语句用于指示编译器如何最佳地分布数据到计算节点上去,
2 HPF的数据并行机制国家高性能计算中心（合肥）
一些重要的说明语句的例子
(1) 伪指令 PROCESSORS,用于描述虚拟的处理机结构例 7
!HPF$ PROCESSOR P4 (4)
注释,描述由 4个处理机组成的虚结构
!HPF$ PROCESSOR P22 (2,2)
注释,描述两行两列共 4个处理器组成的二维虚结构
2 HPF的数据并行机制国家高性能计算中心（合肥）
(2) 伪指令 ALIGN,用于描述数据对准例 8 同维数组间的对准
!HPF$ ALIGN A(I) WITH B(I)
注释,表示把 A的第 I个元素与 B的第 I个元素分配到同一个处理器上,
!HPF$ ALIGN A(I) WITH B(I+1)
注释,表示把 A的第 I个元素与 B的第 I+1个元素分配到同一个处理器上,
!HPF$ ALIGN A(I,J) WITH B(J,I)
注释,表示把 A的第 (I,J)个元素与 B的第 (J,I)个元素分配到同一个处理器上,
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 9 不同维数组间的对准
!HPF$ ALIGN A(I,*) WITH B(I)
注释,表示把 A的第 I行的所有元素与 B的第 I个元素分配到同一个处理器上,
!HPF$ ALIGN A(I) WITH B(I,*)
注释,表示把 A的第 I个元素重复分配到 B的第 I行各元素所在的处理器上,
2 HPF的数据并行机制国家高性能计算中心（合肥）
(3) 伪指令 DISTRIBUTE,用于描述数据映射 (分布 )
有分块 (BLOCK(n))和循环 (CYCLIC(n)) 两种分布方式,
例 10 以分块方式进行数据分布
!HPF$ DISTRIBUTE A (BLOCK) ONTO P4
注释,表示将 A分成每块有 25个元素组成的 4个块,分给 4个处理器,
!HPF$ DISTRIBUTE A (BLOCK(30)) ONTO P4
注释,表示将 A分成每块有 30,30,30,10个元素组成的 4
个块,分给 4个处理器,
2 HPF的数据并行机制国家高性能计算中心（合肥）
!HPF$ DISTRIBUTE B (BLOCK,BLOCK) ONTO P22
注释,表示数组 B在行列两个方向被分成 4个块,分给 4个处理器,
!HPF$ DISTRIBUTE B (*,BLOCK) ONTO P4
注释,表示数组 B在列方向分成 4个块,行方向不分布
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 11 以循环方式进行数据分配
!HPF$ DISTRIBUTE A (CYCLIC) ONTO P4
注释,表示从 A(1)开始,把各元素循环分配给从第 1到第 n (这里 n=4)个处理器,如,第 1个处理器分到了 A(1),A(5),A(9)等,
!HPF$ DISTRIBUTE A (CYCLIC (2)) ONTO P4
注释,表示把数组元素从前往后,每两个分为一组,循环分给从第 1至第 n (=4) 个处理器,如,处理机 1分到了 A(1),A(2),A(9),
A(10),处理器 2分到了 A(3),A(4),A(11),A(12)等等,
2 HPF的数据并行机制国家高性能计算中心（合肥）
(4) 一个数据映射的 HPF程序段例 12 考虑如下代码段,
integer A(100),B(100),C(101),i
!HPF$ ALIGN A(i) WITH B(i-1)
!HPF$ PROCESSOR N(4)
!HPF$ DISTRIBUTE A(BLOCK) ONTO N
!HPF$ DISTRIBUTE C(CYCLIC) ONTO N
FORALL (i=2,100)
A(i) = A(i)+B(i―1)
C(i) = C(i―1) + C(i) +C(i+1)
ENDFORALL
2 HPF的数据并行机制国家高性能计算中心（合肥）
Logical Mapping
ALIGN
DISTRIBUTE
A(1:25)
B(1:24)
C(1:101:4)
A(26:50)
B(25:49)
C(2:101:4)
A(51:75)
B(50:74)
C(3:101:4)
A(76:100)
B(75:99)
C(4:101:4)
N1 N2 N3 N4
N1
N2
N3
N4
N1,N2
N3,N4
N1,N2 N3,N4
High Performance Switch
.,,
A Paragon Mesh
A Uniprocessor
An IBM SP2
Physical Mapping
C(1) C(2) C(3),,,C(101)
B(1) B(2),,,B(99) B(100)
A(1) A(2) A(3),,,A(100)
A(1) A(2) A(3),,,A(100)
B(1) B(2),,,B(99) B(100)
C(1) C(2) C(3),,,C(101)
国家高性能计算中心（合肥）
例 13
!HPF$ PROCESSOR N(4,5)
注释,定义 20个节点组成的 4× 5网格,
!HPF$ PROCESSOR N(4,5,6)
注释,定义 120个节点组成的 4× 5× 6网格,
2 HPF的数据并行机制国家高性能计算中心（合肥）
parameter n=32
real A(n,n+1),x(n)
integer i,pivot_location(1)
!HPF$ PROCESSOR Nodes(4)
!HPF$ ALIGN x(i) WITH A(i,j)
!HPF$ DISTRIBUTE A(BLOCK,*) ONTO Nodes
do i=1,n-1
! pivoting(选主元 )
pivot_location=MAXLOC(ABS(A(i:n,i)))
swap(A(i,i:n+1),A(i-1+pivot_location(1),i:n+1))
! triangularization(三角化 )
A(i,i:n+1)=A(i,i:n+1)/A(i,i)
FORALL (j=i+1:n,k=i+1:n+1) A(j,k)=A(j,k)-A(j,i)*A(i,k)
end do
3 高斯消去法的 HPF程序国家高性能计算中心（合肥）
!back substitution(反向替换 )
do i=n,1,-1
x(i)=A(i,n+1)
A(1:i-1,n+1)=A(1:i-1,n+1)-A(1:i-1,i)*x(i)
end do
3 高斯消去法的 HPF程序国家高性能计算中心（合肥）
DISTRIBUTED 命令指出 A的第一维应是成块分布,A的第二维中的 *号说明第二维已被折叠,意味着部分数组 A(I,1:n)被映射到同一结点,
假设有四个虚拟结点 N1,N2,N3,N4,且 N可为 4整除,那么,数据分布便为如下,
N1,A(1:n/4,1:n),b(1:n/4),Temp(1:n/4),X(1:n)
N2,A(n/4+1:2*n/4,1:n),b(n/4+1:2*n/4),Temp(n/4+1:2*n/4),
X(1:n)
N3,A(2*n/4+1:3*n/4,1:n),b(2*n/4+1:n),Temp(2*n/4:3*n/4)
N4,A(3*n/4+1:n,1:n),b(3*n/4+1:n),Temp(3*n/4+1:n),X(1:n)
3 高斯消去法的 HPF程序国家高性能计算中心（合肥）
在四个结点中的数据分布结点 1 A(1:8;1:33),X(1:8)
结点 2 A(9:16,1:33),X(9:16)
结点 3 A(17:24,1:33),X(17:24)
结点 4 A(25:32,1:33),X(25:32)
3 高斯消去法的 HPF程序
第十四章 分布存储系统并行编程国家高性能计算中心（合肥）
分布存储系统并行编程
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
基于消息传递的并行编程
1 消息传递库
2 消息传递方式国家高性能计算中心（合肥）
1 消息传递库 (Message-Passing Libraries)
表 1,1 一些最流行的消息传递软件的例子
N a m e O r i g i n a l C r e a t o r D i s t i n c t F e a t u r e s
C M M D T h i n k i n g M a c h i n e s U s e A c t i v e M e s s a g e s f o r l o w l a t e n c y
E x p r e s s P a r a s o f t C o l l e c t i v e c o m m u n i c a t i o n a n d I / O
F o r t r a n - M A r g o n n e N a t i o n a l L a b M o d u l a r i t y a n d D e t e r m i n a c y
M P I M P I F o r u m A w i d e l y a d o p t e d s t a n d a r d
NX I n t e l O r i g i n a t e d f r o m t h e I n t e l h y p e r c u b e M P P s
P4 A r g o n n e N a t i o n a l L a b I n t e g r a t e s h a r e d m e m o r y a n d m e s s a g e p a s s i n g
P A R M A C S A N L / G M D M a i n l y u s e d i n E u r o p e
PVM O a k R i d g e N a t i o n a l L a b A w i d e l y u s e d,s t a n d - a l o n e s y s t e m
U N I F Y M i s s i s s i p p i S t a t e A s y s t e m a l l o w i n g b o t h M P I a n d P V M c a l l s
Z i p c o d e L i v e m o r e N a t i o n a l L a b C o n t r i b u t e d t o t h e c o n t e x t c o n c e p t
建议,一个终端用户在开发新的消息传递应用时使用 MPI或 PVM,原因是,
MPI和 PVM都是 公用软件,易于得到
多数厂家支持国家高性能计算中心（合肥）
CMMD,是一个用于 Thinking Machines CM-5系统的消息传递库,其特点是基于主动消息 (Active Message)机制在用户空间实现通信以减少通信延迟 ;
Express,是一个支持点到点和群集通信以及并行 I/O的程序设计环境 ;
Nx,是为 Intel MPP(例如,Hypercubes和 Paragon)开发的微核系统,现在已由用于 Intel/Sandia ASCI TFLOPS 系统中的新的微核系统 PUMA代替,
Fortran-M:是对 Fortran77的扩展,它在设计上既支持共享存储也支持消息传递,但当前只实现了对消息传递的支持,该语言提供了许多机制用于支持开发行为确定、模块化的并行程序,
P4(Parallel Programs for Parallel Processors),是一组宏和子程序,用于支持共享存储和消息传递系统中的程序设计,它可以移植到许多体系结构上,
其它的消息传递软件系统 还有 Vertex,PARMACS,Zipcode,UNIFY和 PICL
等,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
在当前所有的消息传递软件中,最重要最流行的是 MPI和
PVM,它们能运行在所有的并行平台上,包括 SMP和 PVP,
二者 已经在 Windows NT 和 Windows 95这样的非 Unix平台上实现,程序设计语言支持 C,Fortran和 Java.
在国产的三大并行机系列神威、银河和曙光上都实现了对 MPI和 PVM和支持,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
1.1 MPI(Message Passing Interface) 简介
1 消息传递库 (Message-Passing Libraries)
1992 年 4 月 组建了一个制定消息传递接口标准的工作组
1992 年 10 月 初稿形成，主要定义了点对点通信接口
1993 年 1 月 第一届 MPI 会议在 Da l l a s 举行
1993 年 2 月 公布了 MPI - 1 修定版本
1993 年 11 月 MPI 的草稿和概述发表在 S upe r c o m put i ng? 93 的会议论文集中
1994 年 5 月 MPI 标准正式发布
1994 年 7 月 发布了 MPI 标准的勘误表
1997 年 MPI 论坛发布了一个修订的标准,叫做 MPI - 2,同时,原来的 MPI 更名为 MPI - 1
目标,是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准,MPI以语言独立的形式来定义这个接口库,
并提供了与 C,Fortran和 Java语言的绑定,这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性,由于这个原因,MPI在并行计算界被广泛地接受,
国家高性能计算中心（合肥）
MPI的实现
建立在厂家专用的环境之上
IBM SP2的 POE/MPL,
Intel Paragon的 OSF/Nx
公共的 MPI环境,
CHIMP Edinburg 大学
LAN(Local Area Multicomputer) Ohio超级计算中心
MPICH Argonne国家实验室与 Mississippi州立大学
MPICH是 MPI在各种机器上的可移植实现,可以安装在几乎所有的平台上,
PC
工作站
SMP
MPP
COW
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
1.2 PVM(Parallel Virtual Machine) 简介开发时间,始于 1989年开发单位,美国 Tennessee大学,Oak Ridge国家实验室和
Emory大学联合研制特点,具有较好的适应性、可扩展性、可移植性和易使用性等特点,源代码可以免费获取,现已被用户广泛采纳,
现状,目前对它的研究和开发工作仍在各大学和研究机构进行,
尽管已经有越来越多的人开始使用 MPI,但 PVM仍然是做并行处理最流行的软件之一,随着它的不断流行,已经被移植到
PVP,SMP,MPP,工作站和 PC组成的机群系统,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
PVM和 MPI间的主要差别,
(1)PVM是一个自包含的系统,而 MPI不是,MPI依赖于支持它的平台提供对进程的管理和 I/O功能,而 PVM本身就包含这些功能,
(2) MPI对消息传递提供了更强大的支持,
(3) PVM不是一个标准,这就意味着 PVM可以更方便、更频繁地进行版本更新,
MPI和 PVM在功能上现在正趋于相互包含,例如,MPI-2增加了进程管理功能,而现在的 PVM也提供了更多的群集通信函数,与 MPI不同的是,
1 消息传递库 (Message-Passing Libraries)
国家高性能计算中心（合肥）
1.2 Message-Passing Modes
关于通信模式,用户需要理解的有三个方面,
共有多少个进程?
进程间如何同步?
如何管理通信缓冲区?
现在的消息传递系统多使用三种通信模式,
同步的消息传递 (Synchronous Message Passing)
阻塞的消息传递 (Blocking Message Passing)
非阻塞的消息传递 (Nonblocking Message Passing)
2 消息传递方式国家高性能计算中心（合肥）
发送例程接收例程进程 Q
接收返回点开始接收点
R_syn1 S_Block2S_Non_Block3
进程 P
开始发送点 发送返回点
S_syn1 R_block2 R_Non_Block3
系统进程等待发送点
2 消息传递方式国家高性能计算中心（合肥）
Process P:
M=10;
L1,send M to Q;
L2,M=20;
goto L1;
Process Q:
L1,S= -100;
L2,receive S from P;
X=S+1;
例 2.1 消息传递中的发送和接收缓冲
M 称为发送消息缓冲 (send message buffer,or send buffer)
S 称为接收消息缓冲 (receive message buffer,or receive buffer)
2 消息传递方式国家高性能计算中心（合肥）
三种通信模式的比较通信事件 同步通信 阻塞的通信 非阻塞的通信发送开始的条件 双方都到达了发送和接收点 发送方到达发送点 发送方到达发送点发送返回意味着 消息已被收到 消息已被发送完 通知完系统某个消息要被发送接收开始的条件 双方都到达了发送和接收点 接收方到达发送点 接收方到达发送点接收返回意味着 消息已被收到 消息已被收到 通知完系统某个消息要被接收语义 明确 二者之间 需做错误探测是否需要系统提供临时的消息缓冲区不需要 需要 需要状态检查 不需要 不需要 需要等待的时间开销 最高 二者之间 最低通信与计算,通信与通信的重迭不重迭 重迭 重迭
X
11 11 1 1,21,- 99
2 消息传递方式国家高性能计算中心（合肥）
Process P:
M=10;
send M to Q;
do some computation which
does not change M;
wait for M to be sent;
M=20;
Process Q:
S=-100;
receive S from P;
do some computation which
does not use S;
wait for S to be received;
X=S+1;
例 2.2 非阻塞模式下,强制进程等待直到安全时再继续执行非阻塞模式本身也会带来一些额外开销,
作为临时缓冲区用的内存空间
分配缓冲区的操作
将消息拷入和拷出临时缓冲区
执行一个额外的检测和等待函数
2 消息传递方式国家高性能计算中心（合肥）
消息传递的特点,
在消息传递模型中,一个并行应用由一组进程组成,每个进程的代码是本地的,只能访问私有数据,进程之间通过传递消息实现数据共享和进程同步,
优点,用户可以对并行性的开发、数据分布和通信实现完全控制,
缺点,
(1) 要求程序员显式地处理通信问题,如,消息传递调用的位置,数据移动,数据复制,数据操作,数据的一致性等等,
(2) 对大多数科学计算程序来说,消息传递模型的真正困难还在于显式的域分解,也就是说,将对相应数据的操作限定在指定的处理器上进行,
在每个处理器上只能看见整个分布数据的一部分,
(3) 无法以渐进的方式、通过逐步将串行代码转换成并行代码而开发出来,
大量的散布在程序各处的域分解要求整个程序由串行到并行的转换一次性实现,而共享存储方法允许在现有的串行代码中插入并行说明从而实现逐步转换,与之相比,这是消息传递的一个明显的缺点,
2 消息传递方式国家高性能计算中心（合肥）
分布存储系统并行编程
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
MPI并行编程
1 MPI中的消息
2 MPI中的消息信封
3 MPI中的四种通信模式
4 点对点的通信
5 群集通信
6 MPI扩展
7 例子,计算 Pi的 MPI程序国家高性能计算中心（合肥）
1 MPI中的消息第五讲#include "mpi.h"
int foo(i)
int i;
{...}
main(argc,argv)
int argc;
char* argv[]
{
int i,tmp,sum=0,group_size,my_rank,N;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&group_size);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
if (my_rank==0) {
printf("Enter N:");
scanf("%d",&N);
for (i=1;i<group_size;i++)
MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD);
for (i=my_rank;i<N;i=i+group_size) sum=sum+tmp;
for (i=1;i<group_size;i++) {
MPI_Recv(&tmp,1,MPI_INT,i,i,MPI_COMM_WORLD,&status);
sum=sum+tmp;
}
printf("\n The result = %d",sum);
}
else {
MPI_Recv(&N,1,MPI_INT,i,i,MPI_COMM_WORLD,&status);
for (i-my_rank;i<N;i=i+group_size) sum=sum+foo(i);
MPI_Send(&sum,1,MPI_INT,0,i,MPI_COMM_WORLD);
}
MPI_Finalize();
}
例 1.1 一个计算 ∑foo(i)的 MPI SPMD消息传递程序,存放在文件,myprog.c”中初始化 MPI环境得到缺省的进程组大小得到每个进程在组中的编号发送消息接收消息终止 MPI环境国家高性能计算中心（合肥）
这个程序用以下并行 C编译器 mpcc来编译,
执行下列命令将可执行程序 myprog加载到 n个节点上,
mpcc myprog.c –o myprog
MPIRUN myprog –np n
MPI进程是重型的单线进程,它们拥有不同的地址空间,因此,
一个进程不能直接访问另一个进程地址空间的中的变量,进程间的通信用消息传递来实现,
1 MPI中的消息国家高性能计算中心（合肥）
为什么 MPI中的发送和接收操作要做得这么复杂呢?
MPI消息的组成,
消息的内容 (即,信的内容 ),称为消息缓冲 (message buffer)
消息的接收者 (即,写在信封上面的东西 ),称为消息信封 (message envelop)
MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD)
MPI_Recv(&N,1,MPI_INT,0,i,MPI_COMM_WORLD,&status)
send M to Q;
receive S from P
1 MPI中的消息国家高性能计算中心（合肥）
考虑一个用 C语言声明的由 N个复数组成的数组 double A[100]
假定进程 P要把这个数组发送给进程 Q:
例 1 用 MPI发送一个数据数组
1 MPI中的消息国家高性能计算中心（合肥）
要发送的消息 可用的消息传递系统 说 明
( 1) 发送整个数组 A
理论的消息传递
se nd A t o Q
消息缓冲由数组 A 标识,信封就是进程名 Q,
( 2) 发送数组 A
的头两个元素,
即,
A [ 0] 和 A [ 1]
商用的消息传递
( 假定在一台计算机上,一个双精度数是 64 位,
即 8 个字节,)
se nd(A,16,Q,t ag )
使用的发送例程形式如下,
se nd ( addr e ss,l e ng t h,de st i nat i o n,t ag )
( addr e ss,l e ng t h ) 定义消息缓冲,
( de st i na t i o n,t ag ) 定义消息信封,
( 3) 发送数组 A
中所有偶数编号的元素,即,
A [ 0 ],A [ 2 ],A [ 4 ],
..,
MP I 的消息传递
do ubl e A [ 100] ;
MPI _D at a_t y pe E v e nE l e m e nt s;
...,.,
MPI _T y pe _v e ct o r
( 50,1,2,MPI _D O U B L E,& E v e nE l e m e nt s) ;
MPI _T y pe _co m m i t ( & E v e nE l e m e nt s) ;
MPI _Se nd ( A,1,E v e nE l e m e nt s,de st i nat i o n,.,,) ;
( 1) 需要定义 导出数据类型
( 2) 使用发送例程形式如下,
MPI _S e nd
( buff e r,co unt,dat at y p e,de s t i na t i on,t ag,
co m m uni cat o r )
( buff e r,co unt,dat at y pe ) 定义了消息缓冲,
( dest i nat i o n,t ag,co m m un i cat or ) 构成消息信封,
1 MPI中的消息国家高性能计算中心（合肥）
MPI_Send (&N,1,MPI_INT,i,i,MPI_COMM_WORLD)
子程序名消息地址消息长度消息数据类型接收进程标识号消息标签通信子
MPI_Send (buffer,count,datatype,destination,tag,communicator)
(buffer,count,datatype) 消息缓冲
(destination,tag,communicator) 消息信封
1 MPI中的消息国家高性能计算中心（合肥）
消息数据类型 (message data types)
通信子 (communicators)
通信操作 (communication operations)
虚拟拓扑 (virtual topology)
MPI的 四个重要概念,
1 MPI中的消息国家高性能计算中心（合肥）
理由有两个,
一是支持异构计算
另一是允许非连续,非均匀内存区中的消息,
异构计算 (heterogeneous computing ),指的是在由不同计算机,
如工作站网络,组成的系统上运行应用程序,系统中的每台计算机可能由不同的厂商生产、使用不同的处理器和操作系统当这些计算机使用不同的数据表示时如何保证互操作性,
为什么需要定义消息数据类型?
1 MPI中的消息国家高性能计算中心（合肥）
表 1 M P I 中预定义的数据类型
MP I ( C 语言绑定 ) C MP I ( F o r t r a n 语言绑定 ) F o r t r a n
M P I _ B Y T E M P I _ B Y T E
M P I _ C H A R s i g n e d c h a r M P I _ C H A R A C T E R C H A R A C T E R
M P I _ C O M P L E X C O M P L E X
M P I _ D O U B L E d o u b l e M P I _ D O U B L E _ P R E C I S I O N D O U B L E _ P R E C I S I O N
M P I _ F L O A T f l o a t M P I _ R E A L R E A L
M P I _ I N T i n t M P I _ I N T E G E R I N T E G E R
M P I _ L O G I C A L L O G I C A L
M P I _ L O N G l o n g
M P I _ L O N G _ D O U B L E l o n g d o u b l e
M P I _ P A C K E D M P I _ P A C K E D
M P I _ S H O R T s h o r t
M P I _ U N S I G N E D _ C H A R u n s i g n e d c h a r
M P I _ U N S I G N E D u n s i g n e d i n t
M P I _ U N S I G N E D _ L O N G u n s i g n e d l o n g
M P I _ U N S I G N E D _ S H O R T u n s i g n e d s h o r t
1 MPI中的消息国家高性能计算中心（合肥）
例 2 发送非连续数据项例 程 说 明
MP I _ P a c k _ s i z e 决定需要一个多大的临时缓冲区来存放 50 个 MP I _ DO UB L E
数据项
m a l l o c (B u f f e r S i z e ) 为缓冲区 T e m p B u f f e r 动态分配内存
f o r 循环 将数组 A 的 50 个偶序数元素打成一个包,放在 T e m p B u f f e r
中
MP I _ P a c k
( A+i* j,1,MP I _ DO UB L E,
T e m p B u f f e,B u f f e r S i z e,
&P o s i t i o n,com m ) ;
第一个参数是被打包的数组元素的地址,
第三个参数是被打包的数组元素的数 据类型,
p o s i t i o n 用于跟踪已经有多少个数据项被打包,p o s i t i o n 的最后值在接下来的 MP I _ S e n d 中被用作消息计数,
double A[100];
MPI_Pack_size (50,MPI_DOUBLE,comm,&BufferSize);
TempBuffer = malloc(BufferSize);
j = sizeof(MPI_DOUBLE);
Position = 0;
for (i=0;i<50;i++)
MPI_Pack(A+i*j,1,MPI_DOUBLE,TempBuffer,BufferSize,&Position,comm);
MPI_Send(TempBuffer,Position,MPI_PACKED,destination,tag,comm);
国家高性能计算中心（合肥）
在下面的消息中,假定每个双精度数有 8字节长,一个字符是 1字节,一个整型数是 4字节,
序号 要发送的消息 消息的性质与定义方法
( 1 ) 由数组 A 的所有元素组成的消息,A 有 100 个元素,每个元素是一个双精度数,
这个消息由 100 项组成,每项有一个 d o u b l e 数据类型,决定了每一项的大小是 8 字节,第 i 项的起始地址是 A +8 ( i - 1 ),
( 2 ) 由数组 A 的第 3 和第 4 项组成消息,
这个消息由两项 A [ 2 ] 和 A [ 3 ] 组成,每项是一个 d o u b l e 数据类型,第一项始于 A +1 6,第二项始于 A +2 4,
这两个消息有两个性质,
数据项的存放是连续的 ;
所有的数据项具有相同的数据类型,
这类消息可以方便地用三元组
( a d d r e s s,c o u n t,d a t a t y p e )
来定义,
第 ( 1 ) 个消息可以用 ( A,1 0 0,M P I _ D O U B L E ) 来定义,
第 ( 2 ) 个消息可以用 ( A +1 6,2,M P I _ D O U B L E ) 来定义,
( 3 ) 由数组 A 的所有偶序数项组成的消息,
这个消息由 50 项 A [ 0 ],A [ 2 ],A [ 4 ],.,,,A [ 9 8 ] 组成,每一项有一个 d o u b l e 数据类型,第 i 项的起始地址是 A +1 6 ( i - 1 ),
( 4 )
由数组 A 的第 3 项,后跟一个字符 c,再跟一个整型数 k.
这个消息由三个不同类型的数据组成,假定它是一个数据结构,
s t r u c t { d o u b l e A [ 1 0 0 ] ; c h a r b,c ; i n t j,k ; } S
的一部分,那么第一项 A [ 2 ] 的地址是 S + 1 6,第二项 c 的地址是 S + 8 0 1,第三项 k 的地址是 S + 8 0 6,
第 ( 3 ) 个消息的性质,
数据项没有放在一个连续的存储区中,
第 ( 4 ) 个消息的性质,
数据不仅没有连续存放,而且是混合数据类型,
上述简单的方法不能处理第 ( 3 ) 和第 ( 4 ) 个消息,
MP I 引入导出数据类型 ( d e r i v e d d a t a t y p e ) 的概念,允许定义可能是由混合 数据类型,非连续存放的数据项组成的消息,导出数据类型由用户的应用程序在运行时从基本的数据类型构造,M P I 提供了强大而全面的构造复杂数据类型的子例程,
例 3 在消息传递中发送一个混合数据类型国家高性能计算中心（合肥）
例 4 发送一数组的 所有偶序数元素例 程 说 明
M P I _D a t a _t y pe 声明一个新的数据类型 E v e nEl e m e nt s,
M P I _T y pe _v e c t o r ( 50,1,2,M P I _ DOUBL E,& E
v e nEl e m e nt s)
产生一个导出数据类型 Ev e nEl e m e nt s,它由 50 个块组成,
每个块的组成是一个双精度数,后跟一个 8 字节的间隔,
接在后面的是下一块,st r i d e 是两个双精度数的大小,即
16 字节,8 字节的间隔用于跳过数组 A 的奇序数元素,
M P I _T y pe _c o m m i t ( & Ev e nEl e m e nt s) 这个 新类型必须在被发送例程使用前交付使用,
M P I _S e nd(A,1,Ev e nEl e m e nt s,dest i na t i o n,...) 注意,E v e nEl e m e nt s 的一个元素包含 A 的所有 50 个偶序数元素,因此,M P I _S e nd 的 c o unt 域值为 1,
double A[100];
MPI_Data_type EvenElements;
...,..
MPI_Type_vector(50,1,2,MPI_DOUBLE,&EvenElements);
MPI_Type_commit(&EvenElements);
MPI_Send(A,1,EvenElements,destination,...);
国家高性能计算中心（合肥）
说明,
MPI_Type_vector(count,blocklength,stride,oldtype,&newtype)
是构造导出数据类型的 MPI例程,
导出类型 newtype由 blocks的拷贝 count份组成,每块 (blocks)由已有的数据类型
oldtype的 blocklength份连续项的拷贝组成,
stride定义每两个连续的块之间的 oldtype元素个数,因此,(stride-blocklength)即是两个块之间的间隔,
1 MPI中的消息国家高性能计算中心（合肥）
消息缓冲 (message buffer,简称 buffer),在不同的消息传递使用场合有不同的含义,下面给出一些例子,
消息缓冲指的是由程序员定义的应用程序的存储区域,用于存放消息的数据值,
例如,在 Send(A,16,Q,tag)中,缓冲 A是在用户应用程序中声明的变量,
该缓冲的起始地址在消息例程中被使用,
消息缓冲也可以指由消息传递系统 (而非用户 )创建和管理的一些内存区,它用于发送消息时暂存消息,这种缓冲不在用户的应用程序中出现,有时被称为系统消息缓冲 (或系统缓冲 ).
MPI允许第三种可能的定义,用户可以划出一定大小的内存区,作为出现在其应用中的任意消息的中间缓冲,
消息缓冲
1 MPI中的消息国家高性能计算中心（合肥）
考虑下列代码,由进程 P传送一个存放在数组 A中的消息 M,到进程 Q的数组 B中,
例 5 在一对进程间发送消息
1 MPI中的消息国家高性能计算中心（合肥）
Process P
A
M
Process Q
B
Process P
A
M
Process Q
B
S
Process P
A
M
Process Q
B
T
(a) 只使用用户缓冲
(b) 使用系统缓冲 S
(c) 使用了用户级的临时缓冲 T
Process P:
double A[2000000];
send(A,32,Q,tag);
Process Q:
double B[32];
recv(B,32,P,tag)
国家高性能计算中心（合肥）
用户如何来定义消息的接收者呢? 在下面列出的 MPI发送例程中,消息信封由三项组成,
MPI_Send (address,count,datatype,destination,tag,communicator)
destination 域是一个整数,标识消息的接收进程,
消息标签 (message tag),也称为消息类型 (message type),是程序员用于标识不同类型消息、限制消息接收者的一个整数,
2 MPI中的消息信封国家高性能计算中心（合肥）
为什么要使用消息标签 (Tag)?
P r o ces s P,
s en d (A,3 2,Q )
s en d (B,1 6,Q )
P r o ces s Q,
r ecv (X,3 2,P)
r ecv (Y,1 6,P)
未使用标签
P r o ce s s P,
s en d (A,3 2,Q,ta g 1 )
s en d (B,1 6,Q,ta g 2 )
P r o ce s s Q,
r ec v (X,3 2,P,ta g 1 )
r ec v (Y,1 6,P,ta g 2 )
使用了标签为了说明为什么要用标签,我们先来看右面一段没有使用标签的代码,
这段代码打算传送 A的前 32
个字节进入 X,传送 B的前 16个字节进入 Y,但是,如果消息 B尽管后发送但先到达进程 Q,就会被第 一 个 r e c v ( ) 接收在 X 中,
使用标签可以避免这个错误,
2 MPI中的消息信封国家高性能计算中心（合肥）
使用标签的另一个原因是可以简化对下列情形的处理,
假定有两个客户进程 P
和 R,每个发送一个服务请求消息给服务进程 Q,
例 6 在消息传递中使用标签
P r oc e ss P,
sen d ( r e q u e st1,32,Q )
P r oc e ss R,
sen d ( r e q u e st2,32,Q )
P r oc e ss Q,
w h i l e ( t r u e ) {
r e c v ( r e c e i v e d _r e q u e st,32,An y _P r oc e ss ) ;
p r oc e ss r e c e i v e d _r e q u e st;
}
P r oce s s P,
s e n d ( r e q u e s t 1,32,Q,t ag 1)
P r oce s s R,
s e n d ( r e q u e s t 2,32,Q,t ag 2)
P r oce s s Q,
w h i l e ( t r u e ) {
r e c v ( r e c e i v e d _r e q u e s t,32,An y _P r oce s s,An y _T ag,S t atu s ) ;
i f ( S t atu s,T ag == t ag 1) p r oce s s r e c e i v e d _r e q u e s t i n on e w ay ;
i f ( S t atu s,T ag == t ag 2) p r oce s s r e c e i v e d _r e q u e s t i n an oth e r w ay ;
}
未使用标签使用了标签国家高性能计算中心（合肥）
通信子 (communicator):
一个进程组 (process group)+上下文 (context),
进程组,是进程的有限有序集,有限意味着,在一个进程组中,
进程的个数 n是有限的,这里的 n称为进程组的大小 (group
size),有序意味着 n 个进程是按整数 0,1,...,n-1进行编号的,
一个进程在一个通信子 (组 )中用它的编号进行标识,组的大小和进程编号可以通过调用以下的 MPI例程获得,
MPI_Comm_size(communicator,&group_size)
MPI_Comm_rank(communicator,&my_rank)
什么是通信子?
2 MPI中的消息信封
MPI_Send (address,count,datatype,destination,tag,communicator)
国家高性能计算中心（合肥）
例 7 通信子的使用
2 MPI中的消息信封
Process 0:
MPI_Send(msg1,count1,MPI_INT,1,tag1,comm1);
parallel_fft(...);
Process 1:
MPI_Recv(msg1,count1,MPI_INT,0,tag1,comm1);
parallel_fft(...);
if (my_rank==0) MPI_Send(msg2,count1,MPI_INT,1,tag2,comm2);
含代码含代码国家高性能计算中心（合肥）
存在问题,不可能保证 tag1 和 tag2一定取了不同的值,
标签是由用户定义的整数值,用户可能会出错,
即使用户不会弄错,也难以或不可能保证 tag1 和 tag2有不同的值,函数 parallel_fft( )可能是由其它用户写的,或者它是一个库例程,这样,用户可能不知道 tag2的值,
即使用户总能知道 tag2的值,仍然可能出错,因为 MPI_Recv
例程可能决定使用一个通配的 (wildcard)标签 MPI_Any_tag.
解决办法,在 parallel_fft( )中的通信使用不同的通信子,它可能包含相同的进程组 (如,进程 0和 1),但每个通信子有系统指定的不同的上下文,与 comm1的不同,因此,MPI_Recv 不再有偶然会从 parallel_fft( )的 MPI_Send中接收 msg2的危险了,
2 MPI中的消息信封国家高性能计算中心（合肥）
考虑如下由 10个进程执行的代码,
例 8 MPI中的新通信子
2 MPI中的消息信封
MPI_Comm MyWorld,SplitWorld;
int my_rank,group_size,Color,Key;
MPI_Init(&argc,&argv);
MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld);
MPI_Comm_rank(MyWorld,&my_rank);
MPI_Comm_size(MyWorld,&group_size);
Color=my_rank%3;
Key=my_rank/3;
MPI_Comm_split(MyWorld,Color,Key,&SplitWorld);
国家高性能计算中心（合肥）
MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld)
将创建一个新的通信子 MyWorld,它是包含与原始的 MPI_COMM_WORLD相同的 10个进程的进程组,但有不同的上下文,
表 分裂一个通信子 M y W or l d
R an k in My W orld 0 1 2 3 4 5 6 7 8 9
C olor 0 1 2 0 1 2 0 1 2 0
Key 0 0 0 1 1 1 2 2 2 3
R an k in Sp li tW orld(C olor=0) 0 1 2 3
R an k in Sp li tW orld(C olor=1) 0 1 2
R an k in Sp li tW orld(C olor=2) 0 1 2
2 MPI中的消息信封国家高性能计算中心（合肥）
MPI-1被设计成使不同通信子中的通信是相互分开的,以及任何群集通信是与任何点对点通信分开的,即使它们是在相同的通信子内,通信子概念尤其方便了并行库的开发,
MPI-1只支持组内通信 (intra-communication)
MPI-2支持组间通信 (inter-communication)
2 MPI中的消息信封国家高性能计算中心（合肥）
MPI消息特性的总结发送者进程总结如下例子,
MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD);
第一个参数指明消息缓存的起始地址,即存放要发送的数据信息,
第二个参数指明消息中给定的数据类型有多少项,这个数据类型由第三个参数给定,
数据类型要么是基本数据类型,要么是导出数据类型,后者由用户生成指定一个可能是由混合数据类型组成的非连续数据项,
第四个参数是目的进程的标识符 (进程编号 )
第五个是消息标签
第六个参数标识进程组和上下文,即,通信子,通常,消息只在同组的进程间传送,但是,MPI允许通过 intercommunicators在组间通信,
MPI_Send(buffer,count,datatype,destination,tag,communicator)
国家高性能计算中心（合肥）
发送者进程总结如下例,
MPI_Recv(&tmp,1,MPI_INT,i,i,MPI_COMM_WORLD,&Status)
第一个参数指明接收消息缓冲的起始地址,即存放接收消息的内存地址第二个参数指明给定数据类型的最大项数,它存放在第三个参数内,可以被接收,接收到的实际项数可能少一些第四个参数是源进程标识符 (编号 )
第五个是消息标签第六个参数标识一个通信子第七个参数是一个指针,指向一个结构
MPI_Status Status
存放了各种有关接收消息的各种信息,
Status.MPI_SOURCE 实际的源进程编号
Status.MPI_TAG 实际的消息标签实际接收到的数据项数由 MPI例程
MPI_Get_count(&Status,MPI_INT,&C)
读出,这个例程使用 Status中的信息来决定给定数据类型 (在这里是
MPI_INT)中的实际项数,将这个数放在变量 C中,
这两个域可以是 wildcard
MPI_Any_source和
MPI_Any_tag.
}
MPI_Recv(address,count,datatype,source,tag,communicator,status)
国家高性能计算中心（合肥）
当一个接收者能从不同进程接收不同大小和标签的信息时,状态信息就很有用,
例 9 消息传递中的状态 (Status)字
2 MPI中的消息信封
while (true){
MPI_Recv(received_request,100,MPI_BYTE,MPI_Any_source,
MPI_Any_tag,comm,&Status);
switch (Status.MPI_Tag) {
case tag_0,perform service type0;
case tag_1,perform service type1;
case tag_2,perform service type2;
}
}
国家高性能计算中心（合肥）
用在 MPI中的通信模式 (communication mode)
同步的 (synchronous)
直到相应的接收已经启动发送才返回,因此接收端要有存放到达消息的应用缓冲,
注意,在 MPI中可以有非阻塞的同步发送,它的返回不意味着消息已经被发出 ! 它的实现不需要在接收端有附加的缓冲,但需要在发送端有一个系统缓冲,为了消除额外的消息拷贝,应使用阻塞的同步发送,
3 MPI中的四种通信模式
S RSynchronous
1
2
3
国家高性能计算中心（合肥）
缓冲的 (buffered)
缓冲的发送假定能得到一定大小的缓冲空间,它必须事先由用户程序通过调用子例程 MPI_Buffer_attch(buffer,size)
来定义,由它来分配大小为 size的用户缓冲,这个缓冲可以用
MPI_Buffer_detach(*buffer,*size )来实现,
S RBuffer
1 2
3 MPI中的四种通信模式国家高性能计算中心（合肥）
Standard S R1
S RReady
1
2
标准的 (standard)
发送可以是同步的或缓冲的,取决于实现,
就绪的 (ready)
在肯定相应的接收已经开始才进行发送,它不像在同步模式中那样需要等待,这就允许在相同的情况下实际使用一个更有效的通信协议,
3 MPI中的四种通信模式国家高性能计算中心（合肥）
表 M P I 中不同的发送和接收操作
M P I P rim it ive B loc k ing N o n - B loc k ing
S tan d a rd S en d M P I_ S en d M P I_ Ise n d
S y n ch r o n o u s Se n d M P I_ S sen d M P I_ Iss en d
B u ffer ed S en d M P I_ B sen d M P I_ Ib sen d
R ea d y S en d M P I_ R sen d M P I_ Irs en d
R ec eiv e M P I_ R ec v M P I_ Ir ec v
C o m p leti o n C h ec k M P I_ W a it M P I_ T est
4 点对点的通信国家高性能计算中心（合肥）
例 10 使用消息传递的进程流水线
X=P(W)
W
Y=Q(X)
X
Z=R(Y)
Y Z
进程流水线中的数据流图中是一条三进程的流水线,一个进程连续地从左边接收一个输入数据流,计算一个新的值,将它发送给右边,下面的代码示出了基本思想,
进程 Q的一段代码
while (Not_Done){
MPI_Irevc(NextX,...);
MPI_Isend(PreviousY,...);
CurrentY=Q(CurrentX);
}
4 点对点的通信国家高性能计算中心（合肥）
进程 Q的代码
while (Not_Done){
if (X==Xbuf0) {X=Xbuf1; Y=Ybuf1; Xin=Xbuf0; Yout=Ybuf0;}
else {X=Xbuf0; Y=Ybuf0; Xin=Xbuf1; Yout=Ybuf1;}
MPI_Irevc(Xin,...,recv_handle);
MPI_Isend(Yout,...,send_handle);
Y=Q(X); /* 重迭计算 */
MPI_Wait(recv_handle,recv_status);
MPI_Wait(send_handle,send_status);
}
Xbuf 0
Receive X
Y=Q(X)
YBuf0
Send Y
Xbuf 1 Ybuf1
进程流水线中的双缓冲
4 点对点的通信国家高性能计算中心（合肥）
例 11 发送和接收中的死锁这是一段错误代码,可能会有下列结果,
死锁,例程 MPI_Issend是非阻塞的、同步的发送,它直到相应的
MPI_Irecv 已经启动执行才返回,如果条件 Y==5不为真,则 MPI_Irecv就不会被执行,
Y为 0.假定当 if语句被执行后 Y==5为真,则 MPI_Irecv会从进程 P接收 X
的值 (为 0)到它的变量 Y,并打印它,
Y为 5.另一个可能的情况是当 Y==5为真时,打印会在接收到 X的值并存入 Y之前执行 (因为 MPI_Irecv是非阻塞的接收 ),因此打印出的是 Y的旧值,
Process P:
...,..
X=0;
MPI_Issend(&X,...,Q,...);
Process Q
...,..
if (Y==5)MPI_Irecv(&Y,...,P,...);
printf(“Y is %d”,Y);
4 点对点的通信国家高性能计算中心（合肥）
广播 (Broadcast)
d a t a
b r o a d c a s t
( a )
A 0
A 0
A 0
A 0
A 0
A 0
A 0
p
r
o
c
e
s
s
e
sMPI_Bcast(Address,Count,Datatype,Root,Comm)
在下列 broadcast操作中,
标号为 Root的进程发送相同的消息给标记为 Comm
的通信子中的所有进程,
消息的内容如同点对点通 信 一 样 由 三 元 组
(Address,Count,Datatype)
标识,对 Root进程来说,这个三元组既定义了发送缓冲也定义了接收缓冲,对其它进程来说,这个三元组只定义了接收缓冲,
5 群集通信国家高性能计算中心（合肥）
聚集 (Gather)
MPI_Gather (SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Root,Comm)
5 群集通信播撒 (Scatter)
MPI_Scatter (SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Root,Comm)
国家高性能计算中心（合肥）
MPI_Scatter
Scatter只执行与 Gather相反的操作,Root
进程发送给所有 n个进程发送一个不同的消息,包括它自已,这 n个消息在 Root进程的发送缓冲区中按标号的顺序有序地存放,每个接收缓冲由三元组 (RecvAddress,
RecvCount,RecvDatatype)标识,所有的非 Root进程忽略发送缓冲,对 Root进程,
发送缓冲由三元组 (SendAddress,
SendCount,SendDatatype)标识,
5 群集通信
MPI_ Gather
Root进程从 n个进程的每一个接收各个进程 (包括它自已 )的消息,这 n个消息的连接按序号 rank进行,存放在 Root进程的接收缓冲中,每个发送缓冲由三元组
(SendAddress,SendCount,SendDatatype)
标识,所有非 Root进程忽略接收缓冲,对
Root进程,发送缓冲由三元组
(RecvAddress,RecvCount,RecvDatatype)
标识,
A 1
A 4
A 0
A 5
A 2
A 3
s c a t t e r
g a t he r
( b)
A 1 A 4A 0 A 5A 2 A 3
国家高性能计算中心（合肥）
扩展的聚集和播撒操作 Allgather
MPI_Allgather ( SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Comm )
5 群集通信
a l l g a t he r
( c )
B 0
E 0
A 0
F 0
C 0
D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
B 0 E 0A 0 F 0C 0 D 0
国家高性能计算中心（合肥）
全局交换 (Tatal Exchange)
A 1
A 4
A 0
A 5
A 2
A 3
a l l t o a l l
( d )
A 1 A 4A 0 A 5A 2 A 3
B 1 B 4B 0 B 5B 2 B 3
C 1 C 4C 0 C 5C 2 C 3
D 1 D 4D 0 D 5D 2 D 3
E 1 E 4E 0 E 5E 2 E 3
F 1 F 4F 0 D 5F 2 F 3
B 1
B 4
B 0
B 5
B 2
B 3
C 1
C 4
C 0
C 5
C 2
C 3
D 1
D 4
D 0
D 5
D 2
D 3
E 1
E 4
E 0
E 5
E 2
E 3
F 1
F 4
F 0
D 5
F 2
F 3
每个进程发送一个消息给所有 n
个进程,包括它自已,这 n个消息在它的发送缓冲中以标号的顺序有序地存放,从另一个角度来看这个通信,每个进程都从 n个进程接收一个消息,这 n个消息以标号的顺序被连接起来,存放在接收缓冲中,注意,全局交换等于由 n
个不同进程做的 n次 Gather操作,
因此,不再需要 Root参数,所有对所有,在一次全局交换中共有 n2
个消息进行通信,
MPI_Alltoall(SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Comm)
5 群集通信国家高性能计算中心（合肥）
MPI提供了两种类型的聚合操作,归约 (reduction)和扫描
(scan),
归约 (reduction)
MPI_Reduce(SendAddress,RecvAddress,Count,Datatype,
Op,Root,Comm)
这里每个进程的部分值存放在 SendAddress中,所有进程将这些值归约为最终结果并将它存入 Root进程的 RecvAddress,数据项的数据类型在 Datatype域中定义,归约操作由 Op域定义,
聚合 (Aggregation)
5 群集通信国家高性能计算中心（合肥）
扫描 (scan)
MPI_scan(SendAddress,RecvAddress,Count,Datatype,
Op,Comm)
scan操作省去了 Root域,因为 scan是将部分值组合成 n个最终值,并存放在 n个进程的 RecvAddress,scan操作由 Op域定义,
MPI的 reduction和 scan操作允许每个进程贡献向量值,而不只是标量值,向量的长度由 Count定义,MPI支持用户自定义的 reduction和 scan操作
5 群集通信国家高性能计算中心（合肥）
在路障操作中,通信子 Comm中的所有进程相互同步,即,它们相互等待,直到所有进程都执行了他们各自的
MPI_Barrier函数,
路障 (Barrier)
MPI_Barrier(Comm)
5 群集通信国家高性能计算中心（合肥）
表 MPI 中的群集通信
T ype Routin e Function ality
MPI_Bcast 一对多播送相同的信息
MPI_Gather 多对一收集个人信息
MPI_Gatherv 通用的 MPI_Gather
MPI_All gather 全局收集操作
MPI_All gatherv 通用的 MPI_All gather
MPI_Scatter 一对多播撒个人信息
MPI_Scatterv 通用的 MPI_Scatter
MPI_All toall 多 对多全交换个人信息
Data m ovem ent
MPI_All toall v 通用的 MPI_All toall
MPI_Reduce 多对一归约
MPI_All r educe 通用的 MPI_Reduce
MPI_Reduce_scatter 通用的 MPI_Reduce
Aggr egation
MPI_Scan 多对多并行 pr efix
Synchr onizati on MPI_Barrier 路障同步
5 群集通信国家高性能计算中心（合肥）
通信子中的所有进程必须调用群集通信例程,如果代码中只有通信子中的一部分成员调用了一个群集例程而其它没有调用,则是错误的,一个错误代码的行为是不确定的,意味着它可能发生任何事情,包括死锁或产生错误的结果,
一个进程一旦结束了它所参与的群集操作就从群集例程中返回,
除了 MPI_Barrier以外,每个群集例程使用类似于点对点通信中的标准
(standard)、阻塞的通信模式,
例如,当 Root进程从 MPI_Bcast中返回时,它就意味着发送缓冲的 Address
可以被安全地再次使用,其它进程可能还没有启动它们相应的 MPI_Bcast!
一个群集例程也许是也许不是同步的,取决于实现,MPI要求用户负责保证他的代码无论实现是否是同步的都是正确的,
Count 和 Datatype在所包含的所有进程中必须是一致的,
在群集例程中没有 tag参数,消息信封由通信子参数和源 /目的进程定义,
例如,在 MPI_Bcast中,消息的源是 Root,目的是所有进程 (包括 Root).
在 MPI-1 中,只支持阻塞和通信子内 (intra-communicator)群集通信,
群集例程的共同特点
5 群集通信国家高性能计算中心（合肥）
6 MPI扩展
MPI-2对 MPI-1的扩展
动态进程
单边通信
非阻塞群集通信模式和通信子间群集通信模式,
对可扩展的 I/O的支持,叫做 MPI-IO,在 MPI-1中,I/O问题全部忽略,
MPI-1只定义对 Fortran77和 C语言的绑定,MPI-2将语言绑定扩展到 Fortran90和 C++.
对实时处理的支持,
扩展了 MPI-1的外部接口,以便使环境工具的开发者更易于访问 MPI对象,这将有助于开发剖析 (profiling),监视
(monitoring)和调试 (debugging)工具,
国家高性能计算中心（合肥）
动态进程
MPI-2决定支持动态进程,这带来了以下好处,
MPI-1不定义如何创建进程和如何建立通信,因此,MPI-
1需要支撑平台提供这种能力,像 SP2中的 POE和工作站网络中的 rsh,MPI-2中的动态进程机制 以可移植的方式 (平台独立 )提供了这种能力
动态进程 有利于将 PVM程序移植到 MPI上,并且还可能支持一些重要的应用类型,如,Client/Server和 Process farm.
动态进程 允许更有效地使用资源和负载平衡,例如,所用节点数可以按需要减少和增加
支持容错,当一个结点失效,运行在其上的进程能在另一个结点上创建一个新进程完成其工作,
6 MPI扩展国家高性能计算中心（合肥）
int MPI_Spawn (
char* command_line,
int minprocs,
int maxprocs,
char* info,
int root,
MPI_Comm comm,
MPI_Comm* intercomm
int* array_of_errcodes
)
/* 可执行程序和参数 */
/* 最少要派生的进程数 */
/* 最多要派生的进程数 */
/* 在何处何时启动该进程 */
/* 根进程的编号 */
/* 根进程的通信子 */
/* comm与新派生的进程组间的互连通信子 */
/* 每个派生进程一个出错代码 */
这个函数试图派生 maxprocs个子进程,每个子进程执行相同代码,这个代码在 command_line中定义,如果 MPI不能派生 maxprocs个进程,它可以按
minprocs指定的数目派生进程,如果它连 minprocs个进程都派生不了,
MPI_Spawn就返回一个出错代码,info 必须是一个空串,允许运行时系统决定何地、如何启动该进程,
6 MPI扩展国家高性能计算中心（合肥）
MPI_Spawn是一个群集操作,也就是说,通信子 comm中的所有成员必须调用它派生进程,但是,只有 root进程中的参数
command_line,minprocs,maxprocs,和 info是有意义的,而忽略其它进程上的这些参数值,这样,尽管派生的进程可以看成
comm中所有进程的子进程,但只有 root进程是真正的父进程,
子进程是 MPI进程意味着它们必须调用 MPI_Initialize,它与父进程中的 MPI_Spawn同是群集操作,子进程和父进程可以通过 intercommunicator intercomm 进行通信,它从父进程中的
MPI_Spawn返回,子进程通过调用 MPI_parent函数能获得
intercommunicator的句柄,MPI_parent函数的形式如下,
int MPI_Parent(MPI_Comm* intercomm)
6 MPI扩展国家高性能计算中心（合肥）
单边通信
MPI-2包括一个新的点对点通信模式,叫做远程存储访问 (remote memory access,RMA),它允许一个进程执行单边通信,即,一个进程可以发送一个数据值到一个目的地,
也可以从一个数据源取一个数据值,无需另一边的参与,
在 MPI-1中,所有的点对点通信都是双边的,发送者和接收者都必需参与,
6 MPI扩展国家高性能计算中心（合肥）
int MPI_Get (
void* dest_addr,
MPI_Init dest_count,
MPI_Datatype dest_datatype,
int source_rank,
int source_disp,
int source_count,
MPI_Datatype source_datatype,
MPI_Comm comm
)
单边接收 (MPI_get)
6 MPI扩展国家高性能计算中心（合肥）
int MPI_Put (
void* source_addr,
MPI_Init source_count,
MPI_Datatype source_datatype,
int dest_rank,
int dest_disp,
int dest_count,
MPI_Datatype dest_datatype,
MPI_Comm comm
)
单边发送 (MPI_Put)
6 MPI扩展国家高性能计算中心（合肥）
7 例子,计算 Pi的 MPI程序
#include <stdio.h>
#include <mpi.h>
#include <math.h>
long n,/*number of slices */
i; /* slice counter */
double sum,/* running sum */
pi,/* approximate value of pi */
mypi,
x,/* independent var,*/
h; /* base of slice */
int group_size,my_rank;
main(argc,argv)
int argc;
char* argv[];
国家高性能计算中心（合肥）
{ int group_size,my_rank;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_rank( MPI_COMM_WORLD,&my_rank);
MPI_Comm_size( MPI_COMM_WORLD,&group_size);
n=2000;
/* Broadcast n to all other nodes */
MPI_Bcast(&n,1,MPI_LONG,0,MPI_COMM_WORLD);
h = 1.0/(double) n;
sum = 0.0;
for (i = my_rank+1; i <= n; i += group_size) {
x = h*(i-0.5);
sum = sum +4.0/(1.0+x*x);
}
mypi = h*sum;
/*Global sum */
MPI_Reduce(&mypi,&pi,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_W
ORLD);
if(my_rank==0) { /* Node 0 handles output */
printf("pi is approximately,%.16lf\n",pi);
}
MPI_Finalize();
}
国家高性能计算中心（合肥）
编译：
mpicc -o pi pi.c
运行：
mpirun -np 2 pi
7 例子,计算 Pi的 MPI程序国家高性能计算中心（合肥）
提纲
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
并行虚拟机 (PVM)
1 并行虚拟机的构造
2 PVM中的进程管理
3 PVM中的通信
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
1 并行虚拟机的构造
PVM系统的组成 (两部分 )
PVM监控进程 (daemon),称为 pvmd,它常驻在虚拟机的每个计算机上
用户可调用的库,称为 libpvm3.a,它与用户的应用程序链接,用于进程管理,消息传递和虚拟机管理,
在 PVM中,节点 (a node)称为 主机 (a host),进程 (a process)
称为 任务 (a task),
并行虚拟机的组成
1~多台主机 (硬件 )
唯一 1个 master pvmd(系统软件 ),运行在称为控制台的主机上
0~多个 slave pvmd(系统软件 )
国家高性能计算中心（合肥）
PVM 控制台 (Console)
安装了 PVM后,用户在任何一台主机上键入以下命令创建 PVM控制台,
pvm host_file
这个命令执行成功后将在调用它的主机和 host_file文件中所列的每台主机上启动一个 pvmd监控进程,并在调用它的主机上显示下列提示符,
pvm>
它指示主机当前处于 PVM控制台模式,
pvmd 的启动方法
master pvmd,必须手工启动
slave pvmds,只能由 master pvmd依次启动
master pvmd启动 slave pvmd的方法用 rsh,rexec(),或其它方法启动一个 slave
1 并行虚拟机的构造国家高性能计算中心（合肥）
表 主要的 PVM 控制命令命 令 含 义
pv m > ad d a ppl e 将主机,app le” 加入到虚拟机中
pv m > de let e a ppl e 从虚拟机中删除主机,app le”
pv m > co nf 列出虚拟机的配置
pv m > sp aw n – co unt 4 ap p 在虚拟机上启动 4 个任务运行,app,
pv m > job s 列出运行在虚拟机上的作业
pv m > ha lt 中止所有 PVM 进程,关闭 PVM
主要的 PVM命令
1 并行虚拟机的构造国家高性能计算中心（合肥）
启动文件,host_file
并行虚拟机的硬件配置在主机表 (host table)文件中说明,
它常驻在虚拟机的每台主机上,主机表中有一项叫做主机描述子 (host descriptor),对应于虚拟机中的每台主机,主机描述子中保存有主机配置信息,以及 packet queues 和通信信息缓冲,
最初,主机表只有 master host一项,当一个新的 slave加入到虚拟机后,master host的主机表被修改,添加一个与新加入的 slave对应的新项,然后,修改后的主机表的信息被播送到整个虚拟机,包括新加入的 slave hosts,这样,虚拟机中所有主机的主机表被同步,并且保持一致,除非哪台机器不转了或网络失效,
1 并行虚拟机的构造国家高性能计算中心（合肥）
虚拟机的动态配置用户可以调用 PVM库函数来动态配置虚拟机,
pvm_addhosts函数,向虚拟机中加入一至多台主机
pvm_delhosts 函数,从虚拟机中删除一至多台主机例子
int info,nhost=2,infos[2];
char *host[]={“apple”,“orange.cs.ustc.edu.cn”}
info=pvm_addhosts(hosts,nhost,infos);
info=pvm_delhosts(hosts,nhost,infos);
1 并行虚拟机的构造国家高性能计算中心（合肥）
task T(用户进程 ) pvmd2(系统进程 )
pvm_addhosts()
Blocked
finished
dm_addhost()
dm_htupd()
dm_htcommit()
dm_addhostack()
pvmd1(系统进程 )
dm_addhost()
dm_startack()
dm_htupdack()
pvmd3(系统进程 )
slave_config()
dm_htupd()
dm_htcommit()
host H2(slave) host H1(master) host H3(new slave)
图 动态加入一个主机 H3
国家高性能计算中心（合肥）
PVM支持实现静态和动态的并行性静态并行程序例子,foo为一个 SPMD程序,在控制台上执行命令
pvm>spawn –count 4 foo
将创建一个 4个任务 (或进程 )的并行应用,运行在虚拟机上,每个任务执行同一个代码 foo,如果 foo不调用动态任务创建函数 pvm_spawn(),这个应用将有一个静态的 DOP(并发度 )为 4.
2 PVM中的进程管理国家高性能计算中心（合肥）
程序到主机的映射
缺省,由 PVM提供的应用算法将任务映射到主机上,每台主机上可映射多个任务,
用户自定义,由用户为每个任务显式地定义一个特定的主机或体系结构类型例子,在控制台上执行命令,
pvm> spawn –(apple) foo
将在主机 apple上启动一个任务执行代码 foo
pvm> spawn –(RS6K) foo
将在任意的 RS/6000节点上使用 AIX操作系统启动一个任务执行代码 foo
2 PVM中的进程管理国家高性能计算中心（合肥）
动态并行程序与进程管理
PVM支持开发 MPMD并行程序和动态进程管理,最重要的函数是 pvm_spawn(),
int numt // 实际被启动的任务数
=pvm_spawn(
char *progm,// 可执行文件名
char **argv,// 指向参数数组的指针
int flag,// 选项
char *where,// 与 flag配合使用
int ntask,// 可执行文件启动的拷贝数
int *tid // 保存派生任务的 tid
)
2 PVM中的进程管理国家高性能计算中心（合肥）
表 pvm _spaw n 中的 f lag 参数选项符号
(O ption Sym bol )
选项值
( Option V alu e )
含义
P vm T askDe f aul t 0 主机由 P V M 选择
P vm T askHost 1 主机由某处定义
P vm T askAr c h 2 体系结构由某处定义
P vm T askDe bu g 4 在调试状态下启动进程
P vm T askT r ac e 8 将生成 P V M 跟踪数据
P vm M pp F r ont 16 在 M P P 前端启动进程
P vm Host C om pl 32 使用 c om pl e m e nt 主机集合
2 PVM中的进程管理国家高性能计算中心（合肥）
表 PVM 进程管理函数
PVM 函数调用 含义
tid= pvm _m ytid (); 获取调用任务的任务标识号
tid= pvm _pa r ent() ; 获取父任务的任务标识号
info = pvm _ex it(); 正在调用的任务退出 P VM,继续作为 UN IX 进程运行,
Num t= pvm _sp aw n(..,); 派生一个 PVM 任务
info = pvm _k ill(tid) ; 终止一个 PVM 任务
tsta t= pvm _ps tat( tid); 获取一个 PVM 任务的状态
info = pvm _ta sk s(.,,); 获取运行 在虚拟机上的所有任务的信息
Msta t= pvm _m stat (ho st); 获取一个主机的状态
info = pvm _con fig(..,); 获取整个虚拟机的配置信息
2 PVM中的进程管理国家高性能计算中心（合肥）
PVM支持动态分组,任何任务都可以在任意时候加入或离开一个组,
PVM 的分组功能由一个叫做 group server的 daemon完成,当第一个组函数被调用时自动地启动这个 daemon.
PVM动态分组概念是很灵活的,可以有多个组,一个任务在任何时候可以属于不同的组,一个任务可以在任何时候加入和离开一个组,无需通知组内的其它成员 (不像 MPI,一个任务在一组内总有一个唯一的编号 ),
一个任务可以播送一个消息给一个组,即使它不是这个组的成员,
动态分组带来程序行为的非确定性,
例如,
一个播送操作可以有不同的结果,如果一个任务加入或离开一个组,任务可能会也可能不会得到这个广播的消息,
如果成员任务离开一个组,路障同步操作可能会死锁,
2 PVM中的进程管理国家高性能计算中心（合肥）
表 PVM 组函数
PVM 函数调用 含义
inu m = pvm _jo ing r oup (,w orld,); 调用任务加入 W orld 组并被分配一个成员
inu m,
inf o= pvm _lv gr oup (,w orld,); 调用任务离开 W orld 组
tid = pvm _get tid (,w orld,,inu m ); 从成员号中获取任务的标识号
inu m = pvm _get ins t(,w orld,,tid ); 从任务的标识号获取成员号
gsi ze= pvm _gs ize(,w orld,); 获取组的大小
inf o= pvm _ba rrier(,w orld,,10) ; 调用任务阻塞 ( 等待 ) 直到 W orld 的 10 个成员调用了 pvm _ba rrier
inf o= pvm _bca st(,w orld,,tag ); 播送一个由标签标识的消息给所 W orld 的有成员
inf o= pvm _r educe(,,,); 类似于 MPI 的 r educt ion
2 PVM中的进程管理国家高性能计算中心（合肥）
S G H L
31 30 29 18 17 0
图 PVM通用的任务标识符 TID格式表 任务标识符的解释
S G H L 含义
0 0 1.,40 95 1.,26 21 43 任务标识符
0 1 1.,40 95 不关心 M ul tic as t 地址
1 0 0 0 本地 pv m d
1 0 1.,40 95 0 pvm 标识
1 1 S m al l neg at iv e num be r 错误代码
2 PVM中的进程管理国家高性能计算中心（合肥）
task1
pvmd1
task2
pvmd2UDP
TCP TCP
TCP
图 通用的 PVM中所用的通信协议
PVM有三种类型的通信,
pvmd间通信
pvmd与其任务间的通信
以及两个任务间的通信
3 PVM中的通信国家高性能计算中心（合肥）
int bufid =pvm_initsend(int encoding)
int info=pvm_pkint(int * p,int nitem,int stride)
int info=pvm_send(int tid,int tag)
int info=pvm_mcast(int *tids,int ntasks,int tag)
int bufid=pvm_recv(int tid,int tag)
int bufid=pvm_nrecv(int tid,int tag)
int bufid=pvm_trecv(int tid,int tag,struct timeval *tmout)
int bufid=pvm_probe(int tid,int tag)
int bufid=pvm_bufinfo(int bufid,int *bytes,int *tag,int *tid)
int info=pvm_upkint(int *p,int nitem,int stride)
3 PVM中的通信
PVM通信函数实例国家高性能计算中心（合肥）
#define n 16 /* number of tasks */
#include,pvm3.h”
main(int argc,char **argv)
{
int mytid,tids[n],me,i,N,rc,parent;
double mypi,h,sum=0.0,x;
me=pvm_joingroup(,PI”);
parent=pvm_parent( );
if (me= =0) {
pvm_spawn(,pi”,(char**)0,0,“”,n-1,tids);
printf(“Enter the number of regions:”);
scanf(,%d”,&N);
pvm_initsend(PvmDataRaw);
pvm_pkint(&N,1,1);
pvm_mcast(tids,n-1,5);
}
else {
pvm_recv(parent,5);
pvm_upkint(&N,1,1);
}
pvm_barrier(,PI”,n); /* optional */
h=1.0/(double) N;
for (i=me+1;i<=N; i+=n){
x=h*((double)i-0.5);
sum+=4.0/(1.0+x*x);
}
mypi=h*sum;
pvm_reduce(PvmSum,&mypi,1,PVM_DOUBLE,6,“PI”,0);
if (me==0) printf(,pi is approximately %.16f\n”,mypi);
pvm_lvgroup(,PI”);
pvm_exit();
}
4 例子,计算 π的 PVM程序这个 SPMD程序划分间隔 [0,1]
进入 N个区域,并启用 n个任务,每个任务负责由 N/n区域计算一个部分和 mypi,然后这 n个部分和由归约 (reduction)操作聚积成一个总和,
国家高性能计算中心（合肥）
假定源码包含在文件 pi.c中,可执行文件 pi用以下命令得到,
cc –I/pvm3/include pi.c libgpvm3.a libpvm3.a –o pi
用户调用第一个任务,它派生出其它 n-1个任务,每个任务首先用以下语句,
me=pvm_joingroup(,PI”);
加入一个组 PI,变量 me将包含组内任务的编号 (实例号 ),初始任务的编号为 0,
下一条语句
parent= pvm_parent();
找出父任务的 ID,初始任务没有父亲,这个函数调用返回 0,
对其它任务,这个函数调用返回初始任务的 ID,
4 例子,计算 π的 PVM程序国家高性能计算中心（合肥）
初始任务执行
pvm_spawn(,pi”,(char**)0,0,“”,n-1,tids);
派生 n-1个子任务,执行文件,pi”中的代码和他们的任务 ID在数组 tids中返回,其它三个参数为 null(0),这是许多
PVM程序的典型情况,
初始任务执行下面的代码提示用户键入变量 N中的区域数,
printf(,Enter the number of regions:”);
scanf(“%d”,&N);
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
然后,它执行下列代码将这个值播送给所有子任务,
pvm_initsend(PvmDataRaw);
pvm_pkint(&N,1,1);
pvm_mcast(tids,n-1,5);
这里,5是一个任意的消息标签,
同时,每个子任务将执行下列代码匹配这个播送,
pvm_recv(parent,5); /* 5是与 pvm_mcast中的标签相匹配的标签 */
pvm_upkint(&N,1,1);
然后所有的任务执行一个路障同步,
pvm_barrier(,PI”,n); /* 在组 PI中的 n个任务应在此同步 */
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
接下来的几行只是正常的计算,
h=1.0/(double) N;
for (i=me+1;i<=N; i+=n){
x=h*((double)i-0.5);
sum+=4.0/(1.0+x*x);
}
mypi=h*sum;
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
接下来做归约操作,
pvm_reduce(PvmSum,&mypi,1,PVM_DOUBLE,6,“PI”,0);
这是一个组 PI中所有的任务的求和归约,每个任务从本地 mypi
贡献一个类型为 PVM_DOUBLE数据项,最终的结果存放在初始任务 (编号为 0)的 mypi中,数 6也是一个任意的消息标签,
一般地,一个 PVM归约具有以下函数原型
pvm_reduce(void(*func)(),void *buffer,int nitem,int datatype,
int tag,char *group,int root);
打印出这个结果后,程序调用以下函数清理环境
pvm_lvgroup(“PI”) and pvm_exit(),
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
编译：
pvmcc -o pi pi.c
运行：
$>pvmd –d7 host_file&
$>pvm
pvm>span –4 pi
pvm>halt
4 例子,计算 Pi的 PVM程序国家高性能计算中心（合肥）
提纲
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
数据并行模型的特点
单线程
在密集的数据结构上的并行操作
全局命名空间
隐式的同步和通信
隐式的计算和数据分布
具有很好的可移植性,包括 SIMD,MIMD,共享和分布存储机器数据并行模型的目的是要在分布存储的机器上实现在全局名空间进行并行程序设计,以屏蔽显式的数据分布和通信问题,
是一种细粒度的并行,
与消息传递模型相比,数据并行程序设计能在一定程度上减轻程序员的负担,但是完全依赖于程序员能否确定一个好的数据分布,
数据并行程序设计国家高性能计算中心（合肥）
数据并行语言的发展
在 SIMD机器 ILLIAC IV开发的语言 IVTRAN,是最早的允许用户控制数据布局的语言
Kali
Fortran D/Vienna Fortran
Fortran 90/ Fortran 95
Thinking Machines公司的 C*/CM Fortran /*Lisp
HPF/HPF+/F--/HPC++/HPJava
数据并行程序设计国家高性能计算中心（合肥）
提纲
14.1 基于消息传递的编程
14.2 MPI并行编程
14.3 PVM并行编程
14.4 基于数据并行的并行编程
14.5 HPF并行编程国家高性能计算中心（合肥）
1 高性能 Fortran(HPF)简介
2 HPF的数据并行机制
3 例子,高斯消去法的 HPF程序
HPF并行编程国家高性能计算中心（合肥）
1 高性能 Fortran(HPF)简介发展历史
1991年,DEC的 D.Lovman和 Rice大学的 K.Kennedy在
Supercomputing’91大会上提出了他们的高性能 Fortran版本,
以统一在分布存储机器上的编程方法
1992年 1月,在 Rice大学召开了第一次 HPF会议,一致通过组织 HPF论坛
1992年 3月,该论坛正式成立
1993年 5 月,发布了 HPF 1.0版 基于 Fortran90
1994年 11月发布了 HPF 1.1版
1997年 1月,论坛发布了 HPF 2.0 基于 Fortran 95
国家高性能计算中心（合肥）
对 HPF的批评主要有三个方面,
认为 HPF是一个太高层的语言,不如 MPI风格的语言适用 ;
认为 HPF是一个太低层的语言,通过改进语言编译技术和体系结构完全可以避开 HPF风格的语言所要求的编译制导 ;
认为 HPF尽管抽象层次适当,但还要作一些扩充才能满足在某些将来的体系结构上处理某些应用的需要,
1 高性能 Fortran(HPF)简介国家高性能计算中心（合肥）
HPF主要的设计目标如下,
(1) 支持数据并行程序设计 ;
(2) 最大限度地发挥非均匀存储访问的 MIMD和 SIMD计算机的性能 ;
(3) 能够调整代码适应各种体系结构的计算机,
HPF2.0语言的组成包括三个部分,
(1) 语言的基本部分,包括任何 HPF编译器必须支持的特性 ;
(2) 已经核准的扩展部分,包括满足某些特殊需要的高级结构,早期的编译器可能不支持这部分 ;
(3) 已被承认的外部接口,是 HPF论坛批准的一组接口,但是由他人设计并为 HPF用户提供具体的服务内容,
1 高性能 Fortran(HPF)简介国家高性能计算中心（合肥）
HPF2.0的一些基本特性如下,
(1) 数据并行说明 (Data parallel directives):达到第一个目标
INDEPENDENT：声明一个循环没有依赖,可以并行执行
REDUCTION：标识被不同迭代使用结合的和可交换的运算修改的变量
(2) 数据映射说明 (Data mapping directives):达到第二个目标
ALIGN：数据对准
DISTRIBUTE：数据分布（映射）
声明如何在处理器间分配数据,使得通信开销最小,负载平衡,
(3) 新的内部函数和库函数 (New intrinsic and library functions):
用于实现第三个目标,允许用户利用特定机器的低层特性,
归约 (reduction)函数／组合分散 (Combining-Scatter)函数,
前缀 (Prefix)/后缀 (Suffix)函数
分类 (Sorting)函数 /位操作 (Bit-Manipulation)函数
(4) 外部过程 (Extrinsic procedures),用于匹配其它的编程方法，
支持混合语言编程国家高性能计算中心（合肥）
3.1 FORALL结构 (FORALL construct)
例 1 简单的 FORALL语句
FORALL (K=1,M―1) X (K+1)=X(K)
注释,语句执行后,X(I―1) 的值送入 X ( I )中,
FORALL (I=1:N,J=1,N) X(I,J) = Y (J,I)
注释,语句执行后,Y的转置矩阵被送入 X,
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 2 带限制的 FORALL语句
FORALL (i=2:5,X(i)>0) X(i)=X(i―1)+X(i+1)
注释,
i是索引变量,i=2:5称为 for-三元组,等价于 i=2:5:1,表示 i
的变化范围下界是 2,上界是 5,缺省步长为 1,即 i的有效值取
{2,3,4,5},
假设在上述 FORALL语句中,初始 X={1,―1,2,―2,3,―3},
在 i的有效值范围内,满足 X(i)>0 的索引 i的活动集合为 {3,
5},求出这个活动索引值集合后,所有赋值表达式同时计算,
X(3) <= X(3-1)+X(3+1)= ―3
X(5) <= X(5-1)+X(5+1)= ―5
FORALL语句结束后,X={1,―1,―3,―2,―5,―3}.
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 3
FORALL (K=1:M,Y(K).NE.0.0) X (K)=1.0/Y(K)
注释,对 Y(K)的值不为 0的 K,把 Y(K)的倒数送入 X(K).
例 4 在 FORALL语句中,可能有不止一个 for-三元组,则用的是联合索引,
FORALL(i=1:2,j=1:3,Y(i,j)>0) Z(i,j)=1/Y(i,j)
注释,该语句等价于 Fortran90语句
where (Y(1:2,1:3)>0) Z(1:2,1:3)= 1/ Y(1:2,1:3)
则联合索引的有效值取集合
{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)},联合索引的活动值取上述集合中使 Y(i,j)>0的子集,
2 HPF的数据并行机制国家高性能计算中心（合肥）
有时,用户希望在一个 FORALL语句中包含几个赋值,这可用 FORALL结构来实现,FORALL结构是对 FORALL语句的进一步扩充,即在 FORALL和 ENDFORALL之间,可以写多条语句,但限制 FORALL结构中只能使用赋值语句,FORALL语句、
FORALL结构,WHERE语句及 WHILE结构,
例 5
FORALL (I=2,9)
A(I) = A(I―1) + A(I+1)
B(I) = A(I)
ENDFORALL
注释,首先,对从 2到 9的各 I,求值 A(I―1)+A(I+1),然后,将其结果送入 A(2)到 A(9)中,再将求得的 A(2)到 A(9)的值送入 B(2)到
B(9)中,
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 6
FORALL(i=1:n)
A (i) = sin (B(i));
C (i) = sqrt (A(i)* A(i))
D (i) = B (i)+2
ENDFORALL
2 HPF的数据并行机制国家高性能计算中心（合肥）
3.2 数据映射 (Data mapping)
数据映射,指的是将数据分布到处理器上,要在分布存储系统上实现并行处理,首先要对数据 (主要是数组 )进行划分,然后分配给各个处理机,再在各个处理器上进行计算,
数据映射要达到以下目的,
(1) 使处理器间的通信开销最小 ;
(2) 负载在可用的处理器间均匀分布,
HPF编译器可以利用 owner-compute 规则分布负载,在数据所在的处理器上执行与该数据有关的计算,因此数据映射直接决定负载分布,HPF提供了许多说明语句用于指示编译器如何最佳地分布数据到计算节点上去,
2 HPF的数据并行机制国家高性能计算中心（合肥）
一些重要的说明语句的例子
(1) 伪指令 PROCESSORS,用于描述虚拟的处理机结构例 7
!HPF$ PROCESSOR P4 (4)
注释,描述由 4个处理机组成的虚结构
!HPF$ PROCESSOR P22 (2,2)
注释,描述两行两列共 4个处理器组成的二维虚结构
2 HPF的数据并行机制国家高性能计算中心（合肥）
(2) 伪指令 ALIGN,用于描述数据对准例 8 同维数组间的对准
!HPF$ ALIGN A(I) WITH B(I)
注释,表示把 A的第 I个元素与 B的第 I个元素分配到同一个处理器上,
!HPF$ ALIGN A(I) WITH B(I+1)
注释,表示把 A的第 I个元素与 B的第 I+1个元素分配到同一个处理器上,
!HPF$ ALIGN A(I,J) WITH B(J,I)
注释,表示把 A的第 (I,J)个元素与 B的第 (J,I)个元素分配到同一个处理器上,
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 9 不同维数组间的对准
!HPF$ ALIGN A(I,*) WITH B(I)
注释,表示把 A的第 I行的所有元素与 B的第 I个元素分配到同一个处理器上,
!HPF$ ALIGN A(I) WITH B(I,*)
注释,表示把 A的第 I个元素重复分配到 B的第 I行各元素所在的处理器上,
2 HPF的数据并行机制国家高性能计算中心（合肥）
(3) 伪指令 DISTRIBUTE,用于描述数据映射 (分布 )
有分块 (BLOCK(n))和循环 (CYCLIC(n)) 两种分布方式,
例 10 以分块方式进行数据分布
!HPF$ DISTRIBUTE A (BLOCK) ONTO P4
注释,表示将 A分成每块有 25个元素组成的 4个块,分给 4个处理器,
!HPF$ DISTRIBUTE A (BLOCK(30)) ONTO P4
注释,表示将 A分成每块有 30,30,30,10个元素组成的 4
个块,分给 4个处理器,
2 HPF的数据并行机制国家高性能计算中心（合肥）
!HPF$ DISTRIBUTE B (BLOCK,BLOCK) ONTO P22
注释,表示数组 B在行列两个方向被分成 4个块,分给 4个处理器,
!HPF$ DISTRIBUTE B (*,BLOCK) ONTO P4
注释,表示数组 B在列方向分成 4个块,行方向不分布
2 HPF的数据并行机制国家高性能计算中心（合肥）
例 11 以循环方式进行数据分配
!HPF$ DISTRIBUTE A (CYCLIC) ONTO P4
注释,表示从 A(1)开始,把各元素循环分配给从第 1到第 n (这里 n=4)个处理器,如,第 1个处理器分到了 A(1),A(5),A(9)等,
!HPF$ DISTRIBUTE A (CYCLIC (2)) ONTO P4
注释,表示把数组元素从前往后,每两个分为一组,循环分给从第 1至第 n (=4) 个处理器,如,处理机 1分到了 A(1),A(2),A(9),
A(10),处理器 2分到了 A(3),A(4),A(11),A(12)等等,
2 HPF的数据并行机制国家高性能计算中心（合肥）
(4) 一个数据映射的 HPF程序段例 12 考虑如下代码段,
integer A(100),B(100),C(101),i
!HPF$ ALIGN A(i) WITH B(i-1)
!HPF$ PROCESSOR N(4)
!HPF$ DISTRIBUTE A(BLOCK) ONTO N
!HPF$ DISTRIBUTE C(CYCLIC) ONTO N
FORALL (i=2,100)
A(i) = A(i)+B(i―1)
C(i) = C(i―1) + C(i) +C(i+1)
ENDFORALL
2 HPF的数据并行机制国家高性能计算中心（合肥）
Logical Mapping
ALIGN
DISTRIBUTE
A(1:25)
B(1:24)
C(1:101:4)
A(26:50)
B(25:49)
C(2:101:4)
A(51:75)
B(50:74)
C(3:101:4)
A(76:100)
B(75:99)
C(4:101:4)
N1 N2 N3 N4
N1
N2
N3
N4
N1,N2
N3,N4
N1,N2 N3,N4
High Performance Switch
.,,
A Paragon Mesh
A Uniprocessor
An IBM SP2
Physical Mapping
C(1) C(2) C(3),,,C(101)
B(1) B(2),,,B(99) B(100)
A(1) A(2) A(3),,,A(100)
A(1) A(2) A(3),,,A(100)
B(1) B(2),,,B(99) B(100)
C(1) C(2) C(3),,,C(101)
国家高性能计算中心（合肥）
例 13
!HPF$ PROCESSOR N(4,5)
注释,定义 20个节点组成的 4× 5网格,
!HPF$ PROCESSOR N(4,5,6)
注释,定义 120个节点组成的 4× 5× 6网格,
2 HPF的数据并行机制国家高性能计算中心（合肥）
parameter n=32
real A(n,n+1),x(n)
integer i,pivot_location(1)
!HPF$ PROCESSOR Nodes(4)
!HPF$ ALIGN x(i) WITH A(i,j)
!HPF$ DISTRIBUTE A(BLOCK,*) ONTO Nodes
do i=1,n-1
! pivoting(选主元 )
pivot_location=MAXLOC(ABS(A(i:n,i)))
swap(A(i,i:n+1),A(i-1+pivot_location(1),i:n+1))
! triangularization(三角化 )
A(i,i:n+1)=A(i,i:n+1)/A(i,i)
FORALL (j=i+1:n,k=i+1:n+1) A(j,k)=A(j,k)-A(j,i)*A(i,k)
end do
3 高斯消去法的 HPF程序国家高性能计算中心（合肥）
!back substitution(反向替换 )
do i=n,1,-1
x(i)=A(i,n+1)
A(1:i-1,n+1)=A(1:i-1,n+1)-A(1:i-1,i)*x(i)
end do
3 高斯消去法的 HPF程序国家高性能计算中心（合肥）
DISTRIBUTED 命令指出 A的第一维应是成块分布,A的第二维中的 *号说明第二维已被折叠,意味着部分数组 A(I,1:n)被映射到同一结点,
假设有四个虚拟结点 N1,N2,N3,N4,且 N可为 4整除,那么,数据分布便为如下,
N1,A(1:n/4,1:n),b(1:n/4),Temp(1:n/4),X(1:n)
N2,A(n/4+1:2*n/4,1:n),b(n/4+1:2*n/4),Temp(n/4+1:2*n/4),
X(1:n)
N3,A(2*n/4+1:3*n/4,1:n),b(2*n/4+1:n),Temp(2*n/4:3*n/4)
N4,A(3*n/4+1:n,1:n),b(3*n/4+1:n),Temp(3*n/4+1:n),X(1:n)
3 高斯消去法的 HPF程序国家高性能计算中心（合肥）
在四个结点中的数据分布结点 1 A(1:8;1:33),X(1:8)
结点 2 A(9:16,1:33),X(9:16)
结点 3 A(17:24,1:33),X(17:24)
结点 4 A(25:32,1:33),X(25:32)
3 高斯消去法的 HPF程序
