资源描述
单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,OpenMP,编程简介,一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言。,一种能够被用于显示指导多线程、共享内存并行的应用程序编程接口（,API,）。,OpenMP,具有良好的可移植性，支持多种编程语言,OpenMP,能够支持多种平台，包括大多数的类,UNIX,系统以及,Windows NT,系统（,Windows 2000,，,Windows XP,，,Windows Vista,等）。,OpenMP,标准诞生于,1997,年。,www.openmp.org,OpenMP,编程简介,OpenMP,最初是为共享内存的多处理器系统设计的并行编程方法，这种计算机对程序员来说是多个处理器共享同一个内存设备，其体系结构如图所示：,OpenMP,多线程编程基础,OpenMP,的编程模型以线程为基础，通过编译指导语句来显示地指导并行化，为编程人员提供了对并行化的完整控制。,OpenMP,的执行模型采用,Fork-Join,的形式：,Fork-Join,的形式,派生线程遇到编译指导语句将派生出另外一组线程,Master,Thread,Paralll,Region,Nested,Parallel,Region,OpenMP,编程组成,OpenMP,同时支持,C/C+,语言和,Fortran,语言，可以选择任意一种语言以及支持,OpenMP,的编译器编写,OpenMP,程序。,OpenMP,的,功能由两种形式,提供：,编译指导语句,与,运行时库函数,，并通过,环境变量,的方式灵活控制程序的运行。,编译指导语句提供了将一个串行程序渐进的改造为并行程序的能力，而对于不支持,OpenMP,编译指导语句的编译器，这些编译指导语句又可以被忽略，完全和原来的串行程序兼容。,运行时库函数，则只有在必须的情况下才考虑调用。,编译指导语句,在编译器编译程序的时候，会识别特定的注释，而这些特定的注释就包含着,OpenMP,程序的一些语义。,(,#,pragma,omp,parallel,).,在一个无法识别,OpenMP,语意的普通编译器中，这些特定的注释会被当作普通的注释而被忽略。,在,C/C+,程序中，,OpenMP,的所有编译制导语句以,#,pragma,omp,开始，后面跟具体的功能指令。即具有如下的形式：,#,pragma,omp, clause , clause,其中,directive,部分就包含了具体的编译指导语句，包括,parallel, for, parallel for, section, sections, single, master, critical, flush, ordered,和,atomic,。,将串行的程序逐步地改造成一个并行程序，达到增量更新程序的目的，减少程序编写人员一定的负担。,运行时库函数,OpenMP,运行时函数库原本用以设置和获取执行环境相关的信息，它们当中也包含一系列用以同步的,API,。,支持运行时对并行环境的改变和优化，给编程人员足够的灵活性来控制运行时的程序运行状况。,环境变量（,OMP_NUM_THREADS,）,编写,OpenMP,程序,开发工具已经增加了对,OpenMP,的支持，,Visual Studio 2005,完全支持,OpemMP,。,编写,OpenMP,程序的必要步骤：,生成项目；,配置项目，支持,OpenMP,;,编写代码，加速,#include “,omp.h,”,；,编写源程序；,配置环境变量，确定线程的数目；,执行程序。,循环并行化,循环并行化编译制导语句的格式，在,C/C+,语言中，循环并行化语句的编译指导语句格式如下：,#,pragma,omp,parallel for ,clauseclause,for (index = first ;,test_expression,;,increment_expr,),body of the loop;,parallel,关键字将紧跟的程序块扩展为若干完全等同的并行区域，每个线程拥有完全相同的并行区域；,关键字,for,则将循环中的工作分配到线程组中，线程组中的每一个线程完成循环中的一部分内容。,循环并行化语句的限制,并行化语句必须是,for,循环语句并具有规范的格式，能够推测出循环的次数，有以下约束 ：,循环语句中的循环变量必须是有符号整型；,循环语句中的比较操作必须是这样的形式：,loop_variable,或,=,loop_invariant_integer,；,循环语句中的第三个表达式（,for,循环的循环步长）必须是整数加或整数减，加减的数值必须是一个循环不变量（,loop invariant value,）；,如果比较操作是,或,或,=,，那么循环变量的值在每次迭代时都必须减少；,循环必须是单入口、单出口的，循环内部不允许有能够到达循环之外的跳转语句，也不允许有外部的跳转语句到达循环内部。,简单循环并行化,两个向量相加，并将计算的结果保存到第三个向量中，向量的维数为,n,。向量相加即向量的各个分量分别相加。,for,（,int,i=0;i,n;i,+,）,zi,=,xi+yi,;,存在循环依赖性实例：,for,（,int,i=0;i,n;i,+,）,zi,=zi-1+xi+yi,对于向量加法来说，可以使用循环并行化编译指导语句直接对循环进行并行化 ：,#,pragma,omp,parallel for,for,（,int,i=0;i,n;i,+,）,zi,=,xi+yi,;,数据相关的概念,如果语句,S2,与语句,S1,存在数据相关，那么必然存在以下两种情况之一：,S1,在循环的一次迭代中访问存储单元,L,，而,S2,在随后的一次迭代中访问同一存储单元，即：循环迭代相关,;,S1,和,S2,在同一循环迭代中访问同一存储单元,L,，但,S1,的执行在,S2,之前，即：非循环迭代相关 。,实例：,x0 = 0; y0 = 1; #,pragma,omp,parallel for,private(k,) for (k = 1; k 100; k+),xk, = yk-1 + 1; /S1,yk, = xk-1 + 2; /S2 ,x0 = 0;,y0 = 1;,x49 = 74;,y49 = 74 ;,#,pragma,omp,parallel for,private(m, k),for (m = 0; m 2; m+),for (k = m*49 + 1; k m*50 + 50; k+),xk, = yk-1 + 1; /S1,yk, = xk-1 + 2; /S2,循环并行化编译指导语句的子句,循环并行化子句可以包含一个或者多个子句来控制循环并行化的实际执行,可以用来控制循环并行化编译。,数据的作用域子句用,shared,来表示一个变量是各个线程之间共享的，而用,private,来表示一个变量是每一个线程私有的，用,threadprivate,表示一个线程私有的全局变量。,循环嵌套,在一个循环体内经常会包含另外一个循环体，循环产生了嵌套 。,循环并行化编译制导语句可以加在任意一个循环之前，则对应的最近的循环语句被并行化，其它部分保持不变。,实际上并行化是作用于嵌套循环中的某一个循环，其它部分由执行到的线程负责执行。,#include ,stdafx.h,#include ,omp.h,int,_,tmain(int,argc, _TCHAR*,argv,),int,i;int,j;,#,pragma,omp,parallel for,/#,pragma,omp,parallel for,private(j,),for(i,=0;i4;i+),for(j,=6;j10;j+),printf(i=%d j=%dn,i,j);,printf(#n);,for(i,=0;i4;i+),#,pragma,omp,parallel for,for(j,=6;j10;j+),printf(i,=%d j=%,dn,i,j,);,return 0;,控制数据的共享属性,OpenMP,程序在同一个共享内存空间上执行，线程通信容易，一个线程写入一个变量，另一个线程可以读取这个变量来完成线程间的通信。,控制数据的共享属性,全局变量以及程序代码都是全局共享的；而动态分配的堆空间也是共享的。,通过,threadprivate,来明确指出的某一个数据结构属于线程范围的全局变量。,OpenMP,允许线程保留自己的私有变量不能让其它线程访问到。每一个线程会建立变量的私有拷贝，虽然变量名是相同的，实际上在共享内存空间内部的位置是不同的。,控制数据的共享属性,数据作用域子句用来确定数据的共享属性，有下面以下几个子句 ：,shared,用来指示一个变量的作用域是共享的；,private,用来指示一个变量作用域是私有的；,firstprivate,和,lastprivate,分别对私有的变量进行初始化的操作和最后终结的操作，,firstprivate,将串行的变量值拷贝到同名的私有变量中，在每一个线程开始执行的时候初始化一次。而,lastprivate,则将并行执行中的最后一次循环的私有变量值拷贝的同名的串行变量中；,default,语句用来改变变量的默认私有属性。,在使用作用域子句的时候要遵循如下的一些规则 ：,作用域子句作用的变量是已经申明的有名变量；,作用域子句在作用到类或者结构的时候，必须作用到类或者结构的整体，而不能只作用于类或者结构的一个部分；,一个编译指导语句能够包含多个数据作用域子句，但是变量只能出现在一个作用域子句中，即变量不能既是共享的，又是私有的；,在语法结构上，作用域子句只能作用在出现在编译指导语句起作用的语句变量部分。另外，可以将作用域子句作用在类的静态变量上。,OpenMP,对默认情况下，并行区中所有的变量都是共享的，但有三种例外情况：,在,parallel for,循环中，,循环索引变量,是私有的；,那些并行区中的局部变量是私有的；,所有在,private,，,firstprivate,，,lastprivate,或,reduction,子句中列出的变量都是私有的。私有化是通过为每个线程创建各个变量的独立副本来完成的。,规约操作的并行化,常见的规约操作,数组求和,#,pragma,omp,parallel for private,（,arx,ary,n,）,reduction,（,+:,a,b,）,for,（,i=0;i,n;i,+,）,a=,a+arxi,;,b=,b+aryi,;,运算符,数据类型,默认初始值,+,整数，浮点,0,*,整数，浮点,1,-,整数，浮点,0,&,整数,所有位都开启，,0,|,整数,0,整数,0,&,整数,1,|,整数,0,使用,reduction,子句进行多线程程序设计时，要记住以下三个要点：,在第一个线程到达指定了,reduction,子句的共享区域或循环末尾时，原来的规约变量的值变为不确定，并保持此不确定状态直至规约计算完成,;,如果在一个循环中使用到了,reduction,子句，同时又使用了,nowait,子句，那么在确保所有线程完成规约计算的栅栏同步操作前，原来的规约变量的值将一直保持不确定的状态,;,各个线程的私有副本值被规约的顺序是未指定的。因此，对于同一段程序的一次串行执行和一次并行执行，甚至两次并行执行来说，都无法保证得到完全相同的结果（这主要针对浮点计算而言），也无法保证计算过程中诸如浮点计算异常这样的行为会完全相同。,私有变量的初始化和终结操作,开始时访问到私有变量在主线程中的同名变量的值，也有可能需要将循环并行化最后一次循环的变量结果返回给主线程中的同名的变量。,OpenMP,编译指导语句使用,firstprivate,和,lastprivate,对这两种需求进行支持，使得循环并行开始执行的时候私有变量通过主线程中的变量初始化，同时循环并行结束的时候，将最后一次循环的相应变量赋值给主线程的变量。,程序实例：,私有变量的初始化和终结操作实例,数据相关性与并行化操作,并不是所有的循环都能够使用,#,pragma,omp,parallel for,来进行并行化。为了对一个循环进行并行化操作，我们必须要保证数据两次循环之间不存在数据相关性。,数据竞争,当两个线程对同一个变量进行操作，并且有一个操作为写操作的时候，就说明这两个线程存在数据竞争，此时，读出的数据不一定就是前一次写操作的数据，而写入的数据也可能并不是程序所需要的。,for（int i=0;i99;i+）,ai=ai+ai+1;,具有循环之间数据相关性的串行程序,for,（,int,j=1;j,N;j,+,）,for,（,int,i=0;i,N;i,+,）,ai,j,=ai,j+ai,j-1;,具有循环之间数据相关性的并行程序,for,（,int,j=1;j,N;j,+,）,#,pragma,omp,parallel for,for,（,int,i=0;i,N;i,+,）,ai,j,=ai,j+ai,j-1;,并行区域编程,并行区域就是通过循环并行化编译指导语句使得一段代码能够在多个线程内部同时执行。,并行区域编译指导语句的格式：,#,pragma,omp,parallel ,clauseclause,block,parallel,编译指导语句的执行过程,#,pragma,omp,parallel,for,（,int,i=0;i5;i+,）,printf,（,hello world i=%,dn,i,）,;,#,pragma,omp,parallel for,for,（,int,i=0;i5;i+,）,printf,（,hello world i=%,dn,i,）,;,线程私有数据与,threadprivate,，,copyin,子句,使用,threadprivate,子句用来标明某一个变量是线程私有数据，在程序运行的过程中，不能够被其他线程访问到。,使用,copyin,子句对线程私有的全局变量进行初始化。,int,counter=0;,#,pragma,omp,threadprivate(counter,),void,inc_counter,(),counter+;,int,_,tmain(int,argc, _TCHAR*,argv,),#,pragma,omp,parallel,for(int,i=0;i10000;i+),inc_counter,();,printf(counter,=%,dn,counter,);,return 0;,并行区域之间的工作共享,工作队列：基本工作过程即为维持一个工作的队列，线程在并行执行的时候，不断从这个队列中取出相应的工作完成，直到队列为空为止。,int,next_task,=0;,int,get_next_task,(),int,task;,#,pragma,omp,critical,if(next_task,8) ,task=,next_task,;,next_task,+;,else,task=-1;,return task;,void,task_queue,（）,int,my_task,;,#,pragma,omp,parallel private,（,my_task,）,my_task,=,get_next_task,（）,;,while,（,my_task,!=-1,）,get_task_done,（,my_task,）,;,my_task,=,get_next_task,（）,;,并行区域之间的工作共享,根据线程号分配任务：由于每一个线程在执行的过程中的线程标识号是不同的，可以根据这个线程标识号来分配不同的任务。,#,pragma,omp,parallel private,（,myid,）,nthreads,=,omp_get_num_threads,（）,;,myid,=,omp_get_thread_num,（）,;,get_my_work_done,（,myid,nthreads,）,;,并行区域之间的工作共享,使用循环语句分配任务,int _tmain(int argc, _TCHAR* argv),int i;,#pragma omp parallel /,开始并行执行,printf(outside loop thread=%dn,omp_get_thread_num();,#pragma omp for,for(i=0;i,max_num,，需,max_num,=ar0,。此时，系统将线程,1,挂起。线程,2,继续，发现,ar1,max_num,，结果,max_num,=3,，线程,2,完成。线程,1,被唤醒，使得,max_num,=ar0,。执行的结果与串行结果完全不同。,int,i;,int,max_num,=-1;,for,（,i=0;i,max_num,）,max_num,=,ari,;,int,i;,int,max_num,=-1;,#,pragma,omp,parallel for,for,（,i=0;i,max_num,）,max_num,=,ari,;,互斥锁机制,OpenMP,提供三种不同的互斥锁机制：,临界区（,critical,）,原子操作（,atomic,）,由库函数来提供同步操作,临界区,通过编译指导语句对产生数据竞争的内存变量进行保护。,临界区编译指导语句的格式如下所示：,#,pragma,omp,critical ,（,name,）,block,执行程序块,block,之前，首先要获得临界区的控制权。在线程组执行的时候，保证每次最多只有一个线程执行临界区。,name,是一个临界区的属性，临界区的命名操作。,互斥锁机制,修改寻找正整数数组最大的元素的代码,int,i;,int,max_num_x,=,max_num_y,=-1;,#,pragma,omp,parallel for,for,（,i=0;i,max_num_x,）,max_num_x,=,arxi,;,#,pragma,omp,critical,（,max_ary,）,if,（,aryi,max_num_y,）,max_num_y,=,aryi,;,互斥锁机制,原子操作,OpenMP,编程方式给同步编程带来的特殊的编程功能；,通过编译指导语句的方式直接获取了现在多处理器计算机体系结构的功能；,操作在执行的过程中是不会被打断的。,能够完成对单一内存单元的更新，提供一种更高效率的互斥锁机制。,通过,#,pragma,omp,atomic,编译指导语句提供；,只能作用在语言内建的基本数据结构，语法格式如下所示：,#,pragma,omp,atomic,x =,expr,#,pragma,omp,atomic,x+/or x-, -x, +x,原子操作,在,C/C+,语言中可能的原子操作 ：,“,+ * - / & | ”,注意：,当对一个数据进行原子操作保护的时候，就不能对数据进行临界区的保护；,在针对同一个内存单元使用原子操作的时候需要在程序的所有涉及到的部位都加入原子操作的支持。,互斥锁机制,运行时库函数的互斥锁支持,OpenMP,通过一系列的库函数支持更加细致的互斥锁操作 ；,编译指导语句进行的互斥锁支持只能放置在一段代码之前，作用在这段代码之上；,程序员必须自己保证在调用相应锁操作之后释放相应的锁，否则就会造成多线程程序的死锁。,函数名称,描述,void omp_init_lock,（,omp_lock_t *,）,初始化一个互斥锁,void,omp_destroy_lock,（,omp_lock_t,*,）,结束一个互斥锁的使用并释放内存,void,omp_set_lock,（,omp_lock_t,*,）,获得一个互斥锁,void omp_unset_lock,（,omp_lock_t *,）,释放一个互斥锁,int,omp_test_lock,（,omp_lock_t,*,）,试图获得一个互斥锁，并在成功是返回真（,true,），失败是返回假（,false,）,隐含的同步屏障（,barrier,）,在每一个并行区域都会有一个隐含的同步屏障（,barrier,），执行此并行区域的线程组在执行完毕本区域代码之前，都需要同步并行区域的所有线程；,一个同步屏障要求所有的线程执行到此屏障，然后才能够继续执行下面的代码；,#pragma omp for,，,#pragma omp single,，,#pragma omp sections,程序块都包含自己的隐含的同步屏障；,为了避免在循环过程中不必要的同步屏障，可以增加,nowait,子句到相应的编译指导语句中。,明确的同步屏障语句,在有些情况下，隐含的同步屏障并不能提供有效的同步措施，可以在需要的地方插入明确的同步屏障语句,#,pragma,omp,barrier,。此时，所有的执行线程都会在同步屏障语句上进行同步。,#,pragma,omp,parallel,initialization,（）,;,#,pragma,omp,barrier,process,（）,;,循环并行化中的顺序语句,在某些情况下，我们对于循环并行化中的某些处理需要规定执行的顺序，典型的情况是在一次循环的过程中，一大部分的工作是可以并行执行的，而其余的工作需要等到前面的工作全部完成之后才能够执行,;,在循环并行化的过程中，可以使用,ordered,子句使得顺序执行的语句直到前面的循环都执行完毕之后再执行,;,ordered,子句使用实例。,影响性能的主要因素,根据,Amdahl,定律，我们应当努力提高并行化代码在应用程序中的比率，这是通用的提高效率的方法。,编写,OpenMP,程序时需要考虑的程序优化的一些方面的问题：,OpenMP,本身的开销,OpenMP,多线程并行化需要一定的程序库的支持。在这些运行时库对程序并行加速的同时需要运行库的本身，因此，库中代码的运行必然会带来一定的开销。,影响性能的主要因素,编写,OpenMP,程序时需要考虑的程序优化的一些方面的问题：,负载均衡,使用,OpenMP,进行并行程序编码要非常注意使得线程之间的负载大致均衡，能够让多个线程在大致相同的时间内完成工作，从而能够提高程序运行的效率。,局部性,在程序运行过程中，高速缓存将缓存最近刚刚访问过的数据以及这些数据相邻的数据。因此，在编写程序的时候，需要考虑到高速缓存的作用，有意地运用这种局部性带来的高速缓存的效率提高。,线程同步带来的开销,多个线程在进行同步的时候必然带来一定的同步开销，在使用多线程进行开发时需要考虑同步的必要性，消除不必要的同步，或者调整同步的顺序，就有可能带来性能上的提升。,OpenMP,程序性能分析实例,并行化带来的额外负担,并行化会带来额外的负担，从效率上考虑，并不是所有的程序都应当并行化的。特别是对于小程序来说，并行化带来的效率不足以弥补并行化本身带来的运行负担，勉强进行并行化就会得不偿失。,负载均衡,同步开销,负载均衡,同步开销,1,同步开销,习题,设计一个程序，使用,OpenMP,，累加,1-100,之和。环境变量,OMP_NUM_THREADS,值为,4,，写出过程。,提示：,#,pragma,omp,parallel for,
展开阅读全文