OpenMP (10)

211从而也没有共享变量。编译器需要不改变OpenMP程序原来的基于共享内存的编程方式，而使得这些程序能在集群系统上正确运行。原来用于线程环境代码变换思想仍然可以用在这里，但是关于全局变量和OpenMP的数据变量的修饰（private、shared及threadprivate等）子句需要不同的处理。由于没有共享的内存空间，所以即使像前面那样使用指针的办法也不能实现数据共享。下面就对全局变量和非全局共享变量的特殊处理进行分析。12.4.1全局变量在集群计算机上利用SVM提供的共享内存区，就可以实现进程间的变量共享问题。问题是如何重新分配整个全局地址空间到SVM的共享内存中去。方法就是编译器在识别出所有的全局变量后，将它们转变为相同类型的指针。然后再调用main()函数之前，调用ort_sglvar_allocate()函数为所有的全局变量分配共享内存。各个全局变量都映射到这个共享内存区内，如果需要则将有些变量进行初始化。下面以一段代码为例来说明。1.inta=1,b=2,c;2.voidf()3.{#pragmaompparallel4.c=a+b;5.}此处变量a、b、c都是全局变量，所以都必须分配在共享内存区内。而且a、b变量还需要初始化。经过变换后的代码如下。1.int_sglini_a=1,(*a),_sglini_b=1,(*b),(*c);2.staticvoid*_thrFunc0_(void*arg)3.{/*#pragmaompparallel–bodymovedbelow*/4.(*c)=(*a)+(*b);5.return(void*)0;6.}变量a、b、c都被转换成相应的同类型指针（见第1行）。代码中所有引用这些变量的地方也都被修改成指针访问（见第4行）。对于有初始化的变量，新增了带有前缀_sglini_的变量用来保存相应的初始值（见第1行）。而原来的函数则变成如下代码所示。1.voidf()2.{ort_execute_parallel(-1,_thrFunc0_,(void*)0);3.}同时还提供了在main()函数之前就需要调用的其他函数(constructor构造函数)。1.staticvoid__attribute__((constructor))_init_shvars_0(void)2.staticvoid_init_shvars_0(void)3.{ort_sglvar_allocate((void**)&c,sizeof(int),(void*)0);4.ort_sglvar_allocate((void**)&b,sizeof(int),(void*)&_sglini_b);5.ort_sglvar_allocate((void**)&a,sizeof(int),(void*)&_sglini_a);6.}212构造函数_init_shvars_0在main()函数调用之前执行，它包含了3个ort_sglvar_allocate()函数的调用，每个调用对应一个共享全局变量。使用构造函数的原因是考虑到当一个程序有多个独立的C代码源文件编译成的模块经链接构成的可执行文件时，是无法在编译时知道全部的全局共享变量。但是通过在每个C代码源文件中定义一个构造函数，就可以保证在main()函数调用之前被调用执行。还需要注意的就是每个C代码源文件中的构造函数名字不能相同，因此OMPi的编译器将用带有“_init_shvars_”前缀不同的编号来命名这些构造函数。Omni编译器也采用了相似的方法来运行于集群系统上，而另一些编译器如NanosCompiler则采用不同的方法，Nanos中的进程利用底层的SVM系统共享全部进程内存空间，此时与普通线程模式的处理完全一样，不需做额外的努力，但是这样一来性能将非常差。12.4.2非全局共享变量非全局变量是保存在堆栈中的，但是多个线程之间虽然共享代码段、数据段，堆栈却是各自分开的。这种情况下以堆栈方式来操作则无法实现共享，所以在基于线程的技术时需要借助于指针（线程间的存储空间是共享的）而不是堆栈操作来获得这些共享变量。但是如果基于进程的技术来实现运行环境，一个进程即使使用指针也无法访问到其他进程的存储空间。OMPi的解决方法是同时结合SVM提供的共享内存和指针技术，主进程master的堆栈放置在共享内存区，所有对这些非全局的共享变量的访问都修改成指针访问，这样一来其他进程借助于指针可以访问到这个共享内存区的变量。另外一些编译器则使用下面的解决方法。每次遇到一个并行域的时候，首先开辟一个SVM共享内存区，然后将这些需要共享的堆栈变量拷贝到这个共享区，所有进程都使用指针来访问这些共享数据，最后在退出并行域的时候将这些共享取得数据拷贝回到堆栈中。主要的问题是需要增加数据拷贝的开销。12.5运行环境OpenMP是基于fork-join模型的，因此在并行域内是由多个经fork操作产生的实体来并发执行任务，这些执行任务的实体我们称为“OpenMP线程”，而这些OpenMP线程具体是由操作系统负责的进程与线程来实现，还是由用户级线程来实现都是可以的。在OMPi中将OpenMP线程抽象为“执行体”（EEs，ExecutionEntities）。由ORT（OMPiRuntime）模块来统一管理这些执行体EE并通过这些EE来并发执行任务，而EE的具体实现由相应的EELIB(ExecutionEntitiesLibrary)模块负责，系统中可以有多种EELIB模块，但是每次只有一种生效。下面对运行库的初始化、任务分担、同步、线程私有变量以及通用线程接口等问题作简单介绍。12.5.1初始化OpenMP程序运行时，ORT先调用ort_initialize()函数进行整个运行时系统的初始化，编译器将这个函数调用插入到main()中，负责下面的工作：2131.处理OpenMP的环境变量；2.初始化EELIB；3.构造主线程的EE的控制块EECB(EEControlBlock)，EECB类似于操作系统中的PCB；4.如果EELIB是基于进程技术的，则还将处理全局变量。12.5.2并行域的处理在进入并行域代码的时候，实际上是调用了运行库中的ort_execute_parallel()函数（参见12.3的代码转换部分），此时ORT将会与EELIB进行协商，请求并获得一定数量的EE（取决于用户的要求、是否启动了并行嵌套特性和动态调整特性），这些EE将首先调用ort_get_ee_work()确定自己所要执行的任务。EE获取一个以函数指针指向的任务函数，同时也将初始化自己的EECB控制快（包含组的大小、组内id、并行嵌套级数、父结点EE的指针）。在并行嵌套的情况下，所有的EE都通过父结点EE指针构成一棵动态变化的树，每当新进入到一层（级）的并行域，就会新增一个有若干EE构成的子树，而每退出某一级的并行域则会有一个子树消失。12.5.3任务分担OpenMP提供了三种任务分担的结构，分别是for、sections和single用于将任务合理的分配在多个OpenMP线程上。这些结构对应的代码区通常都是在结束处隐含有同步操作的（阻塞），除非使用了nowait子句显式地说明不需要同步，这使得OMPi需要跟踪记录这些额外的状态（某个EE组内的EE可能分别处于不同的并行域中）。每当一个并行域中有一个EE在执行任务，我们就称这个并行域使活跃的。由于在每个需要任务分担的任务中我们需要记录哪些子任务已经完成，哪些还没有完成，如果因为nowait子句使得有多个负载分担结构同时活跃，那就需要为每一个负载分担结构都提供相应的独立记录信息。考虑到在一个循环中的single语句或sections语句，上面的方法只为负载分担结构保留一个记录信息并不够用。此时可以采用动态生成这些记录信息，也可以像Omni编译器那样禁止超过一个非阻塞的负载分担结构。OMPi的方法是在某一组EE的父结点的EECB上为各个负载分担结构预先生成一组记录信息的队列，当前最大的活跃负载分担结构数量为MAXWS。每个记录里面记录有结构相关的信息（sections中剩余的section数目，for结构中的下一个需要调度的任务和步长增量，用于EE并发访问的锁等等）、以及队列相关的信息（退出此负载分担结构的EE数量等），一旦活跃的负载分担结构数量达到MAXWS时，将阻止EE进入新的负载分担结构，直到分配新的空间来满足这些记录。OMPi的ORT对这些负载分担队列的访问是经过仔细优化的。如果可以，尽量采用无锁的方式来访问这些队列信息、尽量采用原子操作、只在必要时使用非嵌套的单层锁plainlock、避免对整个队列作完整的初始化。只有当一个EE遇到为初始化的记录项时，才进行完整的初始化。在ORT看来，每次遇到负载分担结构，就需要调用两个函数，一个是进入时的ort_enter_workshare_region()，一个是退出时的ort_leave_workshare_region()。这两个函数都要修改前面提到的队列里的信息。第一个进入负载分担结构的EE将初始化当前的记录信息并214为下一个记录作准备，其他后续进入的EE则无需做什么。最后一个退出的EE在ort_leave_workshare_region()，需要清空里面的记录，而前面离开的EE只需要将notleft计数器（未退出该区线程数目）进行减1操作。一旦清空，就可以回收利用于其他的负载分担结构的记录。下面用一个例子来展示相关的过程。1.voidf()2.{intI;3.#pragmaompparallel4.#pragmaompforprivate(i)schedule(static)5.for(i=0;i100;i++)6.do_some_calculations(i);7.}经OMPi的代码变换后的代码如下。1.staticvoid*_thrFunc0_(void*arg)2.{3.{inti;4.Intfrom_=0,to_=0,step_;5.strcut_ort_getopt_gdopt_;6.step_=1;7.ort_entering_for(1,0,0,step_,&gdopt_);8.if(ort_get_static_default_chunk(0,100,step_,&from_,&to_))9.{for(i=from_;ito_;i=i+1)10.do_some_calculations(i);11.}12.ort_leaving_for();13.}14.return(void*)0;15.}第7行的ort_entering_for()函数的内部会调用ort_enter_workshare_region()函数，它通知ORT这个负载分担的类型、是否为阻塞方式（1表示非阻塞）。但是编译器可以识别出没有必要为parallel结构和for结构各自启用一个同步路障，因此它忽略了for要求的路障并告知ORT这是一个nowait的负载分担结构。第二个参数是告诉ORT是否for结合了ordered子句，第三和第四个参数指出循环的下界和步长。最后一个参数用于dynamic和guided的调度方式。ort_get_static_default_chunk()用于确定各个EE所需要负责的for循环中那一部分。最后EE退出该负载分担结构时调用ort_leaving_for()函数，该函数在进而调用ort_leave_workshared_region()告诉ORT本EE已经退出了该负载分担结构。12.5.4同步ORT将源程序中的barrier语句用ort_barrier_me()函数调用来取代。当EE执行该函数时将会把自己阻塞（利用一个共享的数组），然后等待父结点EE唤醒。等待可以使用一个标志上215的自旋锁，但是为了节约CPU资源，自旋锁并不一直自旋下去，而是在一段时间后让出CPU。父结点EE检查那个共享数组，如果发现所有EE都已经到达同步点，那么它将通过设置标志从而释放所有阻塞的EE。但