《并行计算共享存储并行程序设计.ppt》由会员分享，可在线阅读，更多相关《并行计算共享存储并行程序设计.ppt（76页珍藏版）》请在三一办公上搜索。
1、第八章 共享存储并行程序设计,共享存储多处理机系统：存储器任一单元均可被任一处理器访问到。单地址空间是指存储器中每一个位置在整个的存储器地址范围内有一个唯一的地址。通常，共享存储程序设计比消息传递程序设计更加容易、方便，因为进程间的数据交换可利用共享存储器来实现。但共享存储程序设计需要程序设计者使用特殊的机制（如临界段等）来协调各个进程对共享数据的访问。,主要内容,共享存储多处理机系统的程序设计方法共享数据的创建和访问并行程序设计语言和并行结构的描述OpenMP-利用编译制导实现的并行程序设计Pthread-基于多线程的并行程序设计,一、共享存储多处理机系统的程序设计方法,常用的程序设计方法并
2、发进程的创建并发线程的创建,使用单总线相连的共享存储多处理机,这种体系结构只适应于较少处理器的系统总线的带宽限制了其上的处理器的通信效率,使用交叉开关网的共享存储多处理机,该体系结构极大地增加了处理器与存储器通信的带宽但这种结构的系统造价昂贵共享存储器系统分UMA和NUMA访问模式,1.共享存储系统中常用的程序设计方法,使用全新的并行程序设计语言扩充现有的顺序程序设计语言的语法，以构成新的并行程序设计语言对现有的顺序程序设计语言使用例程库使用带有并行编译制导预处理器的顺序程序设计语言这种编译制导用来说明共享变量和程序中可并行的部分使用重量级进程使用线程,2.并发进程的创建,操作系统常常是基于进
3、程概念的处理机时间被多进程共享时，进程往往分时占用处理机时间；当进程由于某些原因（如等待一个I/O操作）被阻塞时，操作系统会提供将其调出的运行机制；并发进程概念用于并行程序设计，而它实现了真正的进程的并发。,2.并发进程的创建,在UNIX操作系统中，使用FORK-JOIN结构描述并发进程的结构在FORK-JOIN结构中：FORK语句用来创建新进程JOIN语句用来等待指定进程的终止,FORK-JOIN结构,FORK-JOIN结构与消息传递系统中的spawn/exit相同,UNIX系统调用,UNIX系统利用fork()创建新进程，对于join的实现则是利用wait()和exit()来实现的。SPM
4、D模式：pid=fork();/fork()创建一个新进程子进程和父进程执行的代码段if(pid=0)exit(0);/exit()终止一个进程else wait(0);/wait()挂起进程直到收到:/其子进程终止的信号,UNIX系统调用,主、从进程执行代码不同的情况下的SPMD模式：pid=fork();/fork()创建一个新进程if(pid=0)从进程执行的代码段 else 主进程执行的代码段 if(pid=0)exit(0);/exit()终止一个进程else wait(0);/wait()挂起进程直到收到:/其子进程终止的信号,3.并发线程的创建,利用fork创建的进程是一个重量级
5、进程，它是一个完全独立的程序，有自己的变量栈、堆栈和存储器空间;所有线程共享进程的同一存储器空间和进程的全局变量。,进程与线程的差别,从静态角度看，进程对应一个独立的程序；而线程对应一个程序中不同的、可并行执行的过程。进程在时间和空间上的开销都很昂贵进程除拥有自己的存储器空间、变量和堆栈外，要从其父进程进行的完全拷贝；而所有线程共享进程的同一存储器空间和进程的全部变量线程的创建时间比进程少3个数量级线程的同步比进程更高效：进程同步需要系统操作的支持；而线程的同步只需通过访问共享变量来实现,主要内容,共享存储多处理机系统的程序设计方法共享数据的创建和访问并行程序设计语言和并行结构的描述OpenM
6、P-利用编译制导实现的并行程序设计Pthread-基于多线程的并行程序设计,二、共享数据的创建和访问,共享存储程序设计的主要特征是使各个处理器能够直接访问共享存储器来实现数据交换和其它通信及同步操作共享数据的创建在基于共享存储的并发进程系统中，系统为实现共享数据往往提供一批系统调用（系统例程）在多线程模型中，则不需要显式地创建共享数据，在主程序（主线程）的顶部声明的变量是全局变量，可被所有线程使用,二、共享数据的创建和访问,共享数据的访问如果进程（线程）要重写共享数据，则需认真考虑。假设两个进程要将共享数据项x的值增1。,对应低级语言代码为：读x单元的内容计算x+1将结果写回x单元,高级语言代
7、码为：x+;或 x=x+1;,进程1read xcompute x+1write to x,进程2read xcompute x+1write to x,若两进程执行每一步操作的时间关系不同，则有可能使操作的结果不相同。进程同时执行与不同时执行访问共享数据可归结为共享资源的访问的问题,共享资源的访问,临界区、临界段(critical section)临界区是一种能够保证每次仅允许一个进程访问某个特定的共享资源的代码段。即：在任何时刻最多只有一个进程执行临界段代码。要求访问临界区的进程必须实现互斥(mutual exclusion)。,在共享存储结构中的同步通常用于：确定进程间正确的执行次序；保
8、证各进程对共享变量正确的读写次序；它们实际上实现了进程间的通信和同步。有以下几种常用的同步机制：锁信号量监控程序条件变量使用障碍同步,1）锁机制锁(lock)是实现临界段的互斥访问最简单的机制。通常，一个锁用1个二进制位变量来表示，该变量为 1 表示已经有一个进程进入临界段；变量为 0表示没有进程在临界段内。当一个进程执行到临界段“门口”，并发现临界段的“门”是打开的时候，该进程就可以进入临界段，并把“门”锁上，以防止其它进程进入。一旦进程执行完临界段代码，它就打开锁并离开。,通过忙等待控制临界段,进程 1while(lock=1)do_nothing;lock=1;lock=0;,临界段,进
9、程 2while(lock=1)do_nothing;,lock=1;lock=0;,临界段,是不可分的,高性能程序应当尽可能少地使用临界段，因为多个进程使用临界段必须被串行化。假设所有进程都同时达到临界段，它们将一个跟着一个地进入临界段。这种情况中的执行时间几乎与一个处理机的执行时间相同。,等待,等待,时间,死锁问题当一个进程 A 需要另一个进程 B 拥有的资源，而进程 B 也需要进程 A 拥有的资源时，这两个进程就会因为等待彼此拥有的资源而发生死锁。死锁还可能以环的形式发生在几个进程之间。,对于访问多个资源的两个进程，如果它们都以相同的顺序先请求某个资源，然后再请求另一个资源，就可避免死锁
10、。,2）信号量信号量(semaphore)是一个非负整数变量 s，基本操作原语：P(s)和 V(s)，它们通过对信号量 s进行操作而实现进程间的同步。对信号量 s 执行 P 操作相当于请求分配一个单位资源，使 s 减 1。若在执行P操作前s 已为0，则表示无资源可分配，于是阻塞请求该资源的进程，将其排在 s 的等待队列中；对信号量 s 执行 V 操作相当于归还一个单位资源，使 s 加 1。二元信号量(其值0或1)与锁的执行效果相同。,信号量的初始值表示与该信号量相关的资源总数，如：系统中有两台打印机可被用户交替使用。,进程 1非临界段：P(s)临界段V(s)：非临界段,进程 2非临界段：P(s
11、)临界段V(s)：非临界段,进程 3非临界段：P(s)临界段V(s)：非临界段,3）监控程序利用信号量处理临界段问题，P操作和V操作的不匹配或对错误的信号量进行操作，都会产生严重后果。监控程序、管程(monitor)是一个把表示共享资源的状态变量、对资源的操作过程和初始化代码封装在一起的结构。,监控程序将所有的数据和对该数据（或其它资源）的操作都被封装在一个结构里。对数据的读和写只能由监控程序中的过程来完成，且在任何时间只能由一个进程使用监控程序的过程。在一个监控程序中，采用永久性变量来记录共享资源的状态。这些状态变量只能在监控程序内被访问。监控程序中任一过程被调用之前，先要对共享资源变量进行
12、必要的初始化。在同一监控程序内的各个过程的执行必须是互斥的。除此限制外，监控程序中的过程与一般程序设计语言中的过程一样：所以，监控程序是实现互斥执行的结构化方法。,x_mon:monitorvar/全局变量x_being_written:boolean;/对共享变量的读操作procedure read_x/若x正在被修改，则挂起if(x_being_written)then wait;read x;end read_x;,例：一个用来控制对共享变量 x 的互斥写的管程,/对共享变量的写操作procedure write_x if(x_being_written)then wait;x_bein
13、g_written=T;write x;x_being_written=F;signal;/叫醒挂起进程end write_x;end x_mon;,4）条件变量同步机制条件变量(condition variable)同步机制用来实现在临界段中需要特定的全局条件满足了之后才可以执行的情况。如果利用锁机制实现，需要频繁地考察全局变量（互斥变量）的值，显然这样是非常费时的。如，线程 1 等待某个全局变量 x 到达了一个特定的值0 时，才采取行动。其他线程负责改变 x 的值。,5）障碍(barrier)同步在使用软件实现的障碍同步机制之前，要做初始化，即给定一个需要障碍同步的处理机（或进程）数cpn
14、u，然后置同步计数器 barn 为 0。每个处理机到达障碍点后，调用下面的例程去同步：barrier lock(S);barn=barn+1;unlock(S);while(cpnu barn)do nothing,对barn互斥操作,主要内容,共享存储多处理机系统的程序设计方法共享数据的创建和访问并行程序设计语言和并行结构的描述OpenMP-利用编译制导实现的并行程序设计Pthread-基于多线程的并行程序设计,三、并行程序设计语言和并行结构的描述,并行程序设计语言尽管在过去的十几年里，有很多并行程序设计语言出世，但迄今为止，还没有一个能被普遍接受。但基于共享存储的并行程序设计语言应有的并行
15、语言要素却基本上被认同和接受：共享数据的表示功能域并行的表示数据并行的表示,并行语言结构,共享数据的表示在基于共享存储的并行程序设计语言中，变量可以定义为共享的：shared int x;,并行语言结构,功能域并行的表示实现多个代码段可同时执行的情况par S1;S2;：Sn;表示par结构中各语句S1,S2,Sn可同时执行,并行语言结构,数据并行的表示我们曾在同步计算中介绍过描述数据并行的 forall 语句语法：forall(i=0;i p;i+)body 语义：body 中的语句序列的 p 个实例可以同时执行。循环变量 i 的每一个值仅对一个实例有效，即：i=0 时，对 body 的第一
16、个实例有效;i=1 时，对 body 的第二个实例有效;,相关性分析,并行程序设计中一个关键问题是识别哪些子任务（进程）可同时执行，而哪些任务不能并行执行。如果进程之间存在着相关性，则这些进程就不能同时执行。如：forall(i=0;i 5;i+)ai=0;很明显它们可并行执行。但有些代码间的关系却很难一目了然。,相关性分析,我们需要一个算法来识别实例（代码）间的相关性。并行化编译器是能够将顺序代码转换为并行代码的编译器，它可利用Bernstein条件来识别两个（或多个）进程是否可以并行执行。,相关性分析,Bernstein条件：一组足以决定两个进程是否可以同时执行的条件。假设给定：Ii是被进
17、程Pi读取的所有存储单元的集合（即Pi的输入集）Oj是被进程Pj重写（改变）的所有存储单元的集合（即Pj的输出集）对于两个进程Pi 和Pj若要同时执行，它们必须满足:Pi 的输入一定不能是Pj的输出的一部分，即Ii Oj=Pj 的输入一定不能是Pi的输出的一部分，即Oi Ij=这两个进程的输出集合不相交，即Oi Oj=,例子,a=x+y;b=x+z;,I1=x,y,O1=a I2=x,z,O2=b,I1 O2=I2 O1=O1 O2=,满足bernstein条件,a=x+y;b=a+b;,I1=x,y,O1=a I2=a,b,O2=b,I1 O2=I2 O1=a O1 O2=,不满足berns
18、tein条件,主要内容,共享存储多处理机系统的程序设计方法共享数据的创建和访问并行程序设计语言和并行结构的描述OpenMP-利用编译制导实现的并行程序设计Pthread-基于多线程的并行程序设计,四、OpenMP,OpenMP-1997年,DEC,IBM,Intel,SGI,和 Kuch&Associates 等公司的代表们制定的一种适用于多种硬件平台的共享存储编程的新的工业应用标准OpenMP-由一组编译制导语句和可调用的运行(run-time)库函数和使用Fortran和C/C+基本语言的环境变量组成的，使扩充后的语言可以表达程序中的并行性,http:/openmp.org/wp/,The
19、 OpenMP Application Program Interface(API)supports multi-platform shared-memory parallel programming in C/C+and Fortran on all architectures,including Unix platforms and Windows NT platforms.Jointly defined by a group of major computer hardware and software vendors,OpenMP is a portable,scalable mode
20、l that gives shared-memory parallel programmers a simple and flexible interface for developing parallel applications for platforms ranging from the desktop to the supercomputer.,1.主要的OpenMP编译制导命令,并行编译制导命令用来建立一组并行执行的线程，这些线程执行给定的代码段。线程的个数可通过多种途径说明或设置。编译制导命令还可用于说明各种并行执行结构，如：循环结构的并行化等。,1.主要的OpenMP编译制导命令
21、,#pragma omp parallelstructured_block建立多个线程，每个线程执行structured_block代码段。structured_block可以是一个语句，也可以是一个具有单一入口和单一出口的复合语句。在该结构的末尾有一个隐含障碍同步，这种结构对应于forall结构。,#pragma omp parallel private(x,num_threads)x=omp_get_thread_num();num_threads=omp_get_num_threads();ax=10*num_threads;,库例程omp_get_num_threads()返回在该编译
22、制导命令下被使用的线程个数；库例程 omp_get_thread_num()返回线程编号（0.omp_get_num_threads()-1的一个整数），其中0号线程表示主线程。数组a 是一个全局变量，x和num_threads 被说明为私有变量。,线程组中线程的个数的设定方法：在parallel编译制导命令后用num_threads 子句调用库例程omp_set_num_threads()用环境变量OMP_NUM_THREADS定义,2.工作共享,工作共享编译制导命令有3个结构：sectionsforsingle在这些结构的末尾都隐含着一个障碍同步，除非有nowait 子句存在。注意：这些结
23、构不启动一组新线程，线程的启动在引入parallel结构时就完成了。,Sections结构#pragma omp sections#pragma omp section structured_block#pragma omp section structured_block：该结构表示由#pragma omp section引出的每个structured_block可并行执行，它对应于 par 结构。,For循环结构#pragma omp forfor_loop若线程个数与循环次数相同，则这种结构对应于forall结构。若线程个数与循环次数不相同，则for循环被分为若干部分，使线程组中各线程负
24、责其中的一部分；也可以通过“schedule”子句来分配for循环任务；还可以以轮转的方式分配for循环任务。,Single结构#pragma omp single structured block使structured block由单一线程来执行。工作共享结构的组合在parallel 制导命令后跟着 for 结构，构成一个组合结构:#pragma omp parallel for for_loop表示每个线程执行相同的 for 循环。,3.同步结构,临界区#pragma omp critical name structured_block表示在任何时刻只允许一个线程执行临界区代码struct
25、ured_block，若有多个线程同时到达name指定的临界区时，只允许一个线程进入，其它线程挂起。,3.同步结构,障碍同步#pragma omp barrier原子操作#pragma omp atomic expression_statement等等,用OpenMP 标准+Fortran编写的求 程序program Compute-pi integer n,i real w,x,sum,pi,f,a C function to integrate f(a)=4.d0/(1.d0+a*a)print*,Enter number of intervals:read*,n C calculate
26、the interval size w=1.0d0/n sum=0.0d0,用OpenMP 标准+Fortran编写的求 程序（续）!$OMP PARALLEL DO PRIVATE(x),SHARED(w),REDUCTION(+,sum)do i=1,n x=w*(i+0.5d0)sum=sum+f(x)enddo!$OMP END PARALLEL DO pi=w*sum print*,compute pi=,pi stopend,说明：x为局部变量 w为共享变量,为每个线程创建归约变量 sum的私有拷贝。并按归约操作符+初始化每个私有拷贝 sum 为 0。,对每个线程的私有结果 sum
27、 用操作符+进行归约,4.OpenMP的优点与缺点,优点提供了一个可用的编程标准 可移植性,简单,可扩展性灵活支持多线程,具有负载平衡的潜在能力支持Orphan Scope,使程序更具有模块化缺点只适用于硬件共享存储型的机器动态可变的线程数使得支持起来困难,主要内容,共享存储多处理机系统的程序设计方法共享数据的创建和访问并行程序设计语言和并行结构的描述OpenMP-利用编译制导实现的并行程序设计Pthread-基于多线程的并行程序设计,POSIX(Portable Operating System Interface)线程(thread)，即Pthreads，代表正式的 IEEE POSIX
28、1003.1c-1995 线程标准。该标准可用于很多多处理机的平台，也可用于单个的工作站上。线程管理线程的同步Pthreads提供了多种实现互斥、同步机制：互斥变量、条件变量、障碍同步、信号量。,五、POSIX线程模型,在Pthreads规范中，主程序本身也是一个线程。一个单独的线程可以用下列例程来创建和终止：,当一个被创建的线程终止时，可以不用通知它的创建线程，即创建线程无需调用join例程。这种不需要 join 的线程称为分离线程(detached thread),当一分离线程终止时，它就被撤消并释放它拥有的资源,（主）线程:pthread_create();:pthread_create
29、();:pthread_create();:,说明一个分离线程的参数,Pthreads 中的基本线程管理原语：1、int pthread_create(pthread_t*thread,pthread_attr_t*attr,void*(*routine)(void*),void*arg)功能：创建一个属性为 attr，参数为 arg 的新线程 thread，新线程执行例程 routine。2、void pthread_exit(void*status)功能：终止并退出当前线程。3、int pthread_join(pthread_t thread,void*status)功能：等待指定线程
30、thread 的终止。4、pthread_t pthread_self(void)功能：返回调用线程的 ID 值。,线程安全的例程,如果一个系统调用（或库例程）同时被多个线程调用总能得到正确的结果，则称该系统调用为线程安全的。标准 I/O 操作就是线程安全的。如：当存在着多个打印线程时，不会因此使被打印的内容交错在一起。当某个系统调用不是线程安全的时候，则需要特殊的处理来保证线程的安全性。如：对共享数据的访问需使用临界段。,Pthreads中对线程间的同步和共享数据的访问提供了很多方法：互斥锁信号量条件变量,跳过此部分,Pthreads实现锁机制的例程,在Pthreads中是利用互斥锁变量来实
31、现锁机制的。pthread_mutex_lock(如果一个线程到达互斥锁处，并且发现它被锁住，则该线程等待互斥锁打开。若有多于一个的线程等待锁打开，当锁打开时系统将选择一个线程进入临界段。系统仅允许对互斥锁上锁的线程进行开锁操作。,Pthreads 中的互斥锁例程,Pthreads提供了一个例程来检测一个锁是否真的被锁住：int pthread_mutex_trylock(pthread_mutex_t*mutex)该例程是一个非阻塞操作。当锁未被锁住时，该例程锁住锁，并返回 0；若锁已被锁住，该例程返回 EBUSY。对于前面涉及的死锁问题，当进程需要一个资源时可调用该例程来检查所需的资源是否
32、处于空闲状态，从而解决了进程强行等待所需资源可能造成的死锁问题。,Pthreads 中的条件变量同步机制,用Pthreads 中的条件变量同步例程实现前面的例子：pthread_cond_t cond1;pthread_mutex_t s;pthread_cond_init(,共享存储程序设计的基本宗旨,通过使用临界段、锁、信号量等保证共享数据的正确访问 使用障碍同步机制同步各个进程使用 Pthreads 计算 的并行程序见计算的Pthreads代码.doc相应的程序比前面看到的其他计算算法就要复杂些。,打开计算Pi的Pthreads代码,Pthreads相关网站,75,http:/sourceware.org/pthreads-win32/,Pthread模型的缺点：其目的是低端 Unix SMP,其并行程序没有良好的可扩展性；它使用了库方法，是低层次的，不是编译制导的，排斥了编译器优化；用户很难用 Pthreads 实现串行程序的并行化，用户不得不考虑很多低层细节；它只支持线程并行性，不支持细粒度的数据并行。从例子程序可以看出它很难实现数据并行程序。,
