并行计算共享存储并行程序设计.ppt

第八章 共享存储并行程序设计,共享存储多处理机系统：存储器任一单元均可被任一处理器访问到。 单地址空间是指存储器中每一个位置在整个的存储器地址范围内有一个唯一的地址。 通常，共享存储程序设计比消息传递程序设计更加容易、方便，因为进程间的数据交换可利用共享存储器来实现。 但共享存储程序设计需要程序设计者使用特殊的机制（如临界段等）来协调各个进程对共享数据的访问。,主要内容,共享存储多处理机系统的程序设计方法 共享数据的创建和访问 并行程序设计语言和并行结构的描述 OpenMP-利用编译制导实现的并行程序设计 Pthread-基于多线程的并行程序设计,一、共享存储多处理机系统的程序设计方法,常用的程序设计方法 并发进程的创建 并发线程的创建,使用单总线相连的共享存储多处理机,这种体系结构只适应于较少处理器的系统 总线的带宽限制了其上的处理器的通信效率,使用交叉开关网的共享存储多处理机,该体系结构极大地增加了处理器与存储器通信的带宽 但这种结构的系统造价昂贵 共享存储器系统分UMA和NUMA访问模式,1. 共享存储系统中常用的程序设计方法,使用全新的并行程序设计语言 扩充现有的顺序程序设计语言的语法，以构成新的并行程序设计语言 对现有的顺序程序设计语言使用例程库 使用带有并行编译制导预处理器的顺序程序设计语言这种编译制导用来说明共享变量和程序中可并行的部分 使用重量级进程 使用线程,2. 并发进程的创建,操作系统常常是基于进程概念的 处理机时间被多进程共享时，进程往往分时占用处理机时间； 当进程由于某些原因（如等待一个I/O操作）被阻塞时，操作系统会提供将其调出的运行机制； 并发进程概念用于并行程序设计，而它实现了真正的进程的并发。,2. 并发进程的创建,在UNIX操作系统中，使用FORK-JOIN结构描述并发进程的结构 在FORK-JOIN结构中： FORK语句用来创建新进程 JOIN语句用来等待指定进程的终止,FORK-JOIN结构,FORK-JOIN结构与消息传递系统中的spawn/exit相同,UNIX系统调用,UNIX系统利用fork() 创建新进程，对于join的实现则是利用wait()和exit()来实现的。 SPMD模式： ： 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创建的进程是一个重量级进程，它是一个完全独立的程序，有自己的变量栈、堆栈和存储器空间; 所有线程共享进程的同一存储器空间和进程的全局变量。,进程与线程的差别,从静态角度看，进程对应一个独立的程序；而线程对应一个程序中不同的、可并行执行的过程。 进程在时间和空间上的开销都很昂贵 进程除拥有自己的存储器空间、变量和堆栈外，要从其父进程进行的完全拷贝；而所有线程共享进程的同一存储器空间和进程的全部变量 线程的创建时间比进程少3个数量级 线程的同步比进程更高效：进程同步需要系统操作的支持；而线程的同步只需通过访问共享变量来实现,主要内容,共享存储多处理机系统的程序设计方法 共享数据的创建和访问 并行程序设计语言和并行结构的描述 OpenMP-利用编译制导实现的并行程序设计 Pthread-基于多线程的并行程序设计,二、共享数据的创建和访问,共享存储程序设计的主要特征是使各个处理器能够直接访问共享存储器来实现数据交换和其它通信及同步操作 共享数据的创建 在基于共享存储的并发进程系统中，系统为实现共享数据往往提供一批系统调用（系统例程） 在多线程模型中，则不需要显式地创建共享数据，在主程序（主线程）的顶部声明的变量是全局变量，可被所有线程使用,二、共享数据的创建和访问,共享数据的访问 如果进程（线程）要重写共享数据，则需认真考虑。 假设两个进程要将共享数据项x的值增1。,对应低级语言代码为： 读x单元的内容 计算x+1 将结果写回x单元,高级语言代码为： x+; 或 x=x+1;,进程1 read x compute x+1 write to x,进程2 read x compute x+1 write to x,若两进程执行每一步操作的时间关系不同，则有可能使操作的结果不相同。 进程同时执行与不同时执行 访问共享数据可归结为共享资源的访问的问题,共享资源的访问,临界区、临界段(critical section) 临界区是一种能够保证每次仅允许一个进程访问某个特定的共享资源的代码段。即：在任何时刻最多只有一个进程执行临界段代码。 要求访问临界区的进程必须实现互斥(mutual exclusion)。,在共享存储结构中的同步通常用于： 确定进程间正确的执行次序； 保证各进程对共享变量正确的读写次序； 它们实际上实现了进程间的通信和同步。 有以下几种常用的同步机制： 锁 信号量 监控程序 条件变量 使用障碍同步,1）锁机制 锁(lock)是实现临界段的互斥访问最简单的机制。 通常，一个锁用1个二进制位变量来表示，该变量为 1 表示已经有一个进程进入临界段；变量为 0表示没有进程在临界段内。 当一个进程执行到临界段“门口”，并发现临界段的“门”是打开的时候，该进程就可以进入临界段，并把“门”锁上，以防止其它进程进入。一旦进程执行完临界段代码，它就打开锁并离开。,通过忙等待控制临界段,进程 1 while (lock=1) do_nothing; lock = 1; lock =0;,临界段,进程 2 while (lock=1) do_nothing;,lock = 1; lock =0;,临界段,是不可分的,高性能程序应当尽可能少地使用临界段，因为多个进程使用临界段必须被串行化。 假设所有进程都同时达到临界段，它们将一个跟着一个地进入临界段。这种情况中的执行时间几乎与一个处理机的执行时间相同。,等待,等待,时间,死锁问题 当一个进程 A 需要另一个进程 B 拥有的资源，而进程 B 也需要进程 A 拥有的资源时，这两个进程就会因为等待彼此拥有的资源而发生死锁。 死锁还可能以环的形式发生在几个进程之间。,对于访问多个资源的两个进程，如果它们都以相同的顺序先请求某个资源，然后再请求另一个资源，就可避免死锁。,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) 临界段 V(s) ： ： 非临界段,进程 3 非临界段 ： ： P(s) 临界段 V(s) ： ： 非临界段,3）监控程序 利用信号量处理临界段问题，P操作和V操作的不匹配或对错误的信号量进行操作，都会产生严重后果。 监控程序、管程 (monitor)是一个把表示共享资源的状态变量、对资源的操作过程和初始化代码封装在一起的结构。,监控程序将所有的数据和对该数据（或其它资源）的操作都被封装在一个结构里。对数据的读和写只能由监控程序中的过程来完成，且在任何时间只能由一个进程使用监控程序的过程。 在一个监控程序中，采用永久性变量来记录共享资源的状态。这些状态变量只能在监控程序内被访问。 监控程序中任一过程被调用之前，先要对共享资源变量进行必要的初始化。 在同一监控程序内的各个过程的执行必须是互斥的。除此限制外，监控程序中的过程与一般程序设计语言中的过程一样： 所以，监控程序是实现互斥执行的结构化方法。,x_mon: monitor var /全局变量 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_being_written = T; write x; x_being_written = F; signal; /叫醒挂起进程 end write_x; end x_mon;,4）条件变量同步机制 条件变量(condition variable)同步机制用来实现在临界段中需要特定的全局条件满足了之后才可以执行的情况。 如果利用锁机制实现，需要频繁地考察全局变量（互斥变量）的值，显然这样是非常费时的。 如，线程 1 等待某个全局变量 x 到达了一个特定的值0 时，才采取行动。其他线程负责改变 x 的值。,5）障碍(barrier)同步 在使用软件实现的障碍同步机制之前，要做初始化，即给定一个需要障碍同步的处理机（或进程）数cpnu， 然后置同步计数器 barn 为 0。 每个处理机到达障碍点后，调用下面的例程去同步： barrier lock (S); barn = barn + 1; unlock (S); while (cpnu barn) do nothing ,对barn互斥操作,主要内容,共享存储多处理机系统的程序设计方法 共享数据的创建和访问 并行程序设计语言和并行结构的描述 OpenMP-利用编译制导实现的并行程序设计 Pthread-基于多线程的并行程序设计,三、并行程序设计语言和并行结构的描述,并行程序设计语言 尽管在过去的十几年里，有很多并行程序设计语言出世，但迄今为止，还没有一个能被普遍接受。 但基于共享存储的并行程序设计语言应有的并行语言要素却基本上被认同和接受： 共享数据的表示 功能域并行的表示 数据并行的表示,并行语言结构,共享数据的表示 在基于共享存储的并行程序设计语言中，变量可以定义为共享的： 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 的第一个实例有效; i = 1 时，对 body 的第二个实例有效; ,相关性分析,并行程序设计中一个关键问题是识别哪些子任务（进程）可同时执行，而哪些任务不能并行执行。 如果进程之间存在着相关性，则这些进程就不能同时执行。 如： forall (i = 0; i 5; i+) ai = 0; 很明显它们可并行执行。 但有些代码间的关系却很难一目了然。,相关性分析,我们需要一个算法来识别实例（代码）间的相关性。 并行化编译器是能够将顺序代码转换为并行代码的编译器，它可利用Bernstein条件来识别两个（或多个）进程是否可以并行执行。,相关性分析,Bernstein条件：一组足以决定两个进程是否可以同时执行的条件。 假设给定： Ii是被进程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=,不满足bernstein条件,主要内容,共享存储多处理机系统的程序设计方法 共享数据的创建和访问 并行程序设计语言和并行结构的描述 OpenMP-利用编译制导实现的并行程序设计 Pthread-基于多线程的并行程序设计,四、OpenMP,OpenMP- 1997年, DEC, IBM, Intel, SGI, 和 Kuch & Associates 等公司的代表们制定的一种适用于多种硬件平台的共享存储编程的新的工业应用标准 OpenMP-由一组编译制导语句和可调用的运行(run-time)库函数和使用Fortran和C/C+基本语言的环境变量组成的，使扩充后的语言可以表达程序中的并行性,/wp/,The 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 model 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编译制导命令,#pragma omp parallel structured_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()返回在该编译制导命令下被使用的线程个数； 库例程 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个结构： sections for single 在这些结构的末尾都隐含着一个障碍同步，除非有nowait 子句存在。 注意：这些结构不启动一组新线程，线程的启动在引入parallel结构时就完成了。,Sections结构 #pragma omp sections #pragma omp section structured_block #pragma omp section structured_block ： ： 该结构表示由#pragma omp section引出的每个structured_block可并行执行，它对应于 par 结构。,For循环结构 #pragma omp for for_loop 若线程个数与循环次数相同，则这种结构对应于forall结构。 若线程个数与循环次数不相同，则for循环被分为若干部分，使线程组中各线程负责其中的一部分； 也可以通过“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 表示在任何时刻只允许一个线程执行临界区代码structured_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 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 stop end,说明： x为局部变量 w为共享变量,为每个线程创建归约变量 sum的私有拷贝。并按归约操作符 + 初始化每个私有拷贝 sum 为 0。,对每个线程的私有结果 sum 用操作符 + 进行归约,4. OpenMP的优点与缺点,优点 提供了一个可用的编程标准 可移植性, 简单, 可扩展性 灵活支持多线程, 具有负载平衡的潜在能力 支持Orphan Scope, 使程序更具有模块化 缺点 只适用于硬件共享存储型的机器 动态可变的线程数使得支持起来困难,主要内容,共享存储多处理机系统的程序设计方法 共享数据的创建和访问 并行程序设计语言和并行结构的描述 OpenMP-利用编译制导实现的并行程序设计 Pthread-基于多线程的并行程序设计,POSIX (Portable Operating System Interface) 线程 (thread) ，即Pthreads，代表正式的 IEEE POSIX 1003.1c-1995 线程标准。 该标准可用于很多多处理机的平台，也可用于单个的工作站上。 线程管理 线程的同步 Pthreads提供了多种实现互斥、同步机制：互斥变量、条件变量、障碍同步、信号量。,五、POSIX线程模型,在Pthreads规范中，主程序本身也是一个线程。 一个单独的线程可以用下列例程来创建和终止：,当一个被创建的线程终止时，可以不用通知它的创建线程，即创建线程无需调用join例程。 这种不需要 join 的线程称为分离线程(detached thread),当一分离线程终止时，它就被撤消并释放它拥有的资源,（主）线程 : : pthread_create( ); : pthread_create( ); : 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) 功能：等待指定线程 thread 的终止。 4、pthread_t pthread_self ( void ) 功能：返回调用线程的 ID 值。,线程安全的例程,如果一个系统调用（或库例程）同时被多个线程调用总能得到正确的结果，则称该系统调用为线程安全的。 标准 I/O 操作就是