5.2.3 线程同步 在 OpenMP 应用程序中, 由于是多线程执行, 必须要有必要的线程同步机制以保证程序在出现数据竞争的时候能够得出正确的结果, 并且在适当的时候控制线程的执行顺序, 以保证执行结果的确定性 OpenMP 支持两种不同类型的线程同步机制, 一种是互斥锁的机制, 可以用来保护一块共享的存储空间, 使得每一次访问这块共享内存空间的线程最多一个, 保证了数据的完整性 ; 另外一种同步机制是事件通知机制, 这种机制保证了多个线程之间的执行顺序 互斥的操作针对需要保护的数据而言, 在产生了数据竞争的内存区域加入互斥, 包括 critical,atomic 等语句以及由函数库中的互斥函数构成的标准例程 而事件机制则在控制规定线程执行顺序时所需要的同步屏障 (barrier), 定序区段 (ordered sections), 主线程执行 (master) 等 OpenMP 也对用户自主构成的同步操作提供了一定的支持 数据竞争 我们看一个简单的数据竞争的例子, 即通过下述的算法来寻找一个正整数数组中最大的元 素 串行的算法如下所示, 假设数组为 ar, 数组元素的数目为 n int i; int max_num=-1; for(i=0;i<n;i++) if(ar[i]>max_num) max_num=ar[i]; 对于这样一段简单的代码, 我们可以直接在 for 循环前面加入循环并行化的编译制导语句使 得整个程序代码段可以并行执行 int i; int max_num=-1; #pragma omp parallel for for(i=0;i<n;i++) if(ar[i]>max_num) max_num=ar[i]; 但是由于是多线程执行, 这样的并行执行代码是不正确的, 有可能产生错误的结果 下面是一个可能的执行结果, 假设数组有两个元素, 分别为 2 和 3, 系统中有两个线程在执行, 则每个线程只需对一个元素进行判断即可 线程 1 在执行的过程中, 发现 0 号元素比 max_num 要大, 需要将 2 赋值给 max_num 恰在此时, 系统将线程 1 挂起 线程 2 继续执行, 发现 1 号元素也比 max_num 大, 执行的结果就是 max_num=3 线程 2 执行完自己的任务后, 会同步在一个隐含的屏障上 (barrier) 线程 1 被唤醒, 由于它已经过了整数判断的阶段, 因此它直接将 0 号元素赋值给 max_num, 使得 max_num=2 执行的结果与串行结果完全不同 产生结果出现错误的主要原因就是我们有超过两个线程同时访问一个内存区域, 并且至少有一个线程的操作是写操作, 这样就产生了数据竞争 如果不对数据竞争进行处理的话, 就会产生执行结果出错 互斥锁机制 在 OpenMP 中, 提供了三种不同的互斥锁机制用来对一块内存进行保护, 它们分别是临界区
(critical), 原子操作 (atomic) 以及由库函数来提供同步操作 临界区 临界区通过编译制导语句对产生数据竞争的内存变量进行保护 在程序需要访问可能产生竞 争的内存数据的时候, 都需要插入相应的临界区代码 临界区编译制导语句的格式如下所示 : #pragma omp critical [(name)] block 如此, 在执行上述的程序块 block 之前, 必须首先要获得临界区的控制权 在线程组执行的时候, 运行时库会保证每次最多只有一个线程执行临界区 name 是一个临界区的属性, 给临界区一个命名 在对不同的内存区域进行保护的时候, 如果两个线程实际上访问的并不是同一块内存区域, 这是不会产生冲突的, 没有必要对它们之间进行互斥锁的操作 因此, 在 OpenMP 中就提供对临界区的命名操作 可以将不同命名的临界区保护不同的内存区域, 如此就可以在访问不同内存区域的时候使用不同命名的临界区 运行时库是不会在不同命名的临界区之间进行互斥锁同步操作的 因此, 修改上述寻找正整数数组最大的元素的代码就可以修改成如下的形式 代码 5.19 正整数数组最大的元素的临界区版本 int i; int max_num_x=max_num_y=-1; #pragma omp parallel for for(i=0;i<n;i++) #pragma omp critical (max_arx) if(arx[i]>max_num_x) max_num_x=arx[i]; #pragma omp critical (max_ary) if(ary[i]>max_num_y) max_num_y=ary[i]; 在这里稍微修改了上述的代码, 用来寻找两个数组各自的最大元素 通过两个不同的命名临界区 max_arx 与 max_ary 进行互斥操作因为两个数组之间并不存在数据相关性, 也不存在数据竞争 但是上述的代码效率并不高, 对于两个数组来说实际上分别进行了线性的操作, 在循环内部进行的同步过多, 在后续的内容中我们将提供如何提高效率的方法 原子操作原子操作是 OpenMP 编程方式给同步编程带来的特殊的编程功能, 通过编译制导语句的方式直接获取了现在多处理器计算机体系结构的功能 我们知道, 现代体系结构的多处理计算机提供了原子更新一个单一内存单元的方法, 即通过单一一条指令就能够完成数据的读取与更新操作, 例如在英特尔平台上的 CMPXCHG 的指令能够同时完成数据比较和交换功能 所有这
些功能可以被成为原子操作, 即操作在执行的过程中是不会被打断的 因此, 通过这种方式就能够完成对单一内存单元的更新, 提供了一种更高效率的互斥锁机制 在 OpenMP 的程序中, 这样一种先进的功能被通过 #pragma omp atomic 编译制导语句提供 值得注意的是, 上面讲述的临界区操作能够作用在任意的代码块上, 而原子操作只能作用在语言内建的基本数据结构 在 C/C++ 语言中, 原子操作的语法格式如下所示 #pragma omp atomic x <binop>=expr 或者 #pragma omp atomic x++//or x--, --x, ++x 明显的, 能够使用原子语句的前提条件是相应的语句块能够转化成一条机器指令, 使得相应 的功能能够一次执行完毕而不会被打断 下面是在 C/C++ 语言中可能的原子操作 + * - / & ^ << >> 值得注意的是, 当对一个数据进行原子操作保护的时候, 就不能对数据进行临界区的保护, 因为这是两种完全不同的保护机制,OpenMP 运行时并不能在这两种保护机制之间建立配合机制 因此, 用户在针对同一个内存单元使用原子操作的时候需要在程序的所有涉及到的部位都加入原子操作的支持 代码 5.20 原子操作 int counter=0; #pragma omp parallel for(int i=0;i<10000;i++) #pragma omp atomic //atomic operation counter++; printf("counter = %d\n",counter); 注意上述程序中的黑体的语句, 当黑体语句有效的时候, 即使用 atomic 语句, 则最后的执 行结果都是一致的, 执行结果总是为下面的形式 ( 使用两个线程执行 ): counter = 20000 而当这一行语句被从源程序中删除时, 由于有了数据的相关性, 最后的执行结果是不确定的, 下面是一个可能的执行结果 : counter = 12014 运行时库函数的互斥锁支持
除了上述的 critical 与 atomic 编译制导语句,OpenMP 还通过一系列的库函数支持更加细 致的互斥锁操作, 方便使用者满足特定的同步要求 下面的表格列出了由 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 *) 表 5. 1 OpenMP 库函数提供的互斥锁函数 描述初始化一个互斥锁结束一个互斥锁的使用并释放内存获得一个互斥锁释放一个互斥锁试图获得一个互斥锁, 并在成功时返回真 (true), 失败时返回假 (false) 上述库函数的使用比一般的编译制导语句更加灵活 编译制导语句进行的互斥锁支持只能放置在一段代码之前, 作用在这段代码之上 使用运行库函数的互斥锁支持例程则可以将函数置于程序员所需的任意位置 程序员必须自己保证在调用相应锁操作之后释放相应的锁, 否则就会造成多线程程序的死锁 另外, 运行库函数还支持嵌套的锁机制 需要支持嵌套锁机制的原因是由于在某些情况下, 例如进行递归函数调用的时候, 同一个线程需要获得一个互斥锁多次 如果互斥锁不支持嵌套调用的话, 在同一个互斥锁上调用两次获得锁的操作而中间没有释放锁的操作, 将会造成线程死锁 因此, 在 OpenMP 里支持同一个线程对锁的嵌套调用 嵌套调用同一个锁必须使用如下特殊的嵌套锁操作, 嵌套锁操作的库函数与上述锁操作类似, 不同的地方是在每一个函数都包含了 nest 函数名称 描述 void omp_init_nest_lock(omp_lock_t *) 初始化一个嵌套互斥锁 void omp_destroy_nest_lock 结束一个嵌套互斥锁的使用并释放内存 (omp_lock_t*) void omp_set_nest_lock(omp_lock_t *) 获得一个嵌套互斥锁 void omp_unset_nest_lock(omp_lock_t *) 释放一个嵌套互斥锁 int omp_test_nest_lock(omp_lock_t *) 试图获得一个嵌套互斥锁, 并在成功是返回 真 (true), 失败是返回假 (false) 表 5. 2 OpenMP 库函数提供的内嵌的互斥锁函数 下面一个简单的例子说明了如何使用锁机制来控制对一个计数器的访问 : 代码 5.21 使用锁机制来控制对一个计数器的访问 omp_lock_t lock; int counter=0; void inc_counter() printf("thread id=%d\n",omp_get_thread_num()) ; for(int i=0;i<1000;i++)
omp_set_nest_lock(&lock); counter++; omp_unset_nest_lock(&lock); void dec_counter() printf("thread id=%d\n",omp_get_thread_num()) ; for(int i=0;i<1000;i++) omp_set_nest_lock(&lock); counter--; omp_unset_nest_lock(&lock); int _tmain(int argc, _TCHAR * argv[]) omp_init_nest_lock(&lock); #pragma omp parallel sections #pragma omp section inc_counter(); #pragma omp section dec_counter(); omp_destroy_nest_lock(&lock); printf("counter=%d\n",counter); 可以看到, 这里有一个线程不断地增加计数器的值, 而另外一个线程不断地减少计数器的值, 因此需要同步的操作 这里演示如何使用嵌套型的锁函数, 改成普通的锁函数的效果是一样 的 但是在某些情况下, 如果一个线程必须要同时加锁两次, 则只能使用嵌套型的锁函数 事件同步机制 事件同步机制与上述的锁机制不同, 锁机制是为了维护一块代码或者一块内存的一致性, 使 得所有在其上的操作串行化 ; 而事件同步机制则用来控制代码的执行顺序, 使得某一部分代 码必须在其它的代码执行完毕之后才能执行 隐含的同步屏障 (barrier) 在每一个并行区域都会有一个隐含的同步屏障 ( barrier), 执行此并行区域的线程组在执行 完毕本区域代码之前, 都需要同步并行区域的所有线程 一个同步屏障要求所有的线程执行
到此屏障, 然后才能够继续执行下面的代码 #pragmaomp for,#pragmaompsingle,#pragma omp sections 程序块都包含自己的隐含的同步屏障 为了避免在循环过程中不必要的同步 屏障, 可以增加 nowait 子句到相应的编译制导语句中 例如在如下的代码中 : 代码 5.22 隐含的同步屏障 #pragma omp parallel #pragma omp for nowait for(int i = 1; i < size; ++i) x[i] = (y[i] + z[i])/2; printf( finished\n ); 在工作共享的 for 循环结束后, 并不需要等待其它线程的同步操作, 而可以继续执行下面的 打印操作 但是, 在并行区域的结束还是会有一个隐含的同步屏障, 这是所有的线程需要同 步的地方 明确的同步屏障语句在并行执行的时候, 在有些情况下, 隐含的同步屏障并不能提供有效的同步措施, 程序员可以在需要的地方插入明确的同步屏障语句 #pragma omp barrier 此时, 在并行区域的执行过程中, 所有的执行线程都会在同步屏障语句上进行同步 #pragma omp parallel initialization(); #pragma omp barrier process(); 上述例子中, 只有等所有的线程都完成初始化操作以后, 才能够进行下一步的处理动作, 因 此, 在此处插入一个明确的同步屏障操作以完成线程之间的同步 下面的程序是对上述程序 的扩展, 是一个实际可运行的例子 代码 5.23 明确的同步屏障语句 void initialization() int counter=0; printf("thread %d start initialization\n",omp_get_thread_num()) ; for(int i=0;i<100000;i++) counter++; printf("thread %d finish initialization\n",omp_get_thread_num()) ;
void process() int counter=0; printf("thread %d start process\n",omp_get_thread_num()) ; for(int i=0;i<100000;i++) counter+=i; printf("thread %d finish process\n",omp_get_thread_num()) ; int main(int argc, char * argv[]) #pragma omp parallel initialization(); #pragma omp barrier process(); 为了演示实际的屏障效果, 我们将运行的线程数目增加到 5 个 (OMP_NUM_THREADS=5), 下面 是某一次执行的结果 : thread 2 start initialization thread 1 start initialization thread 2 finish initialization thread 3 start initialization thread 4 start initialization thread 0 start initialization thread 0 finish initialization thread 3 finish initialization thread 4 finish initialization thread 1 finish initialization thread 2 start process thread 1 start process thread 4 start process thread 3 start process thread 4 finish process thread 2 finish process thread 1 finish process thread 0 start process thread 3 finish process
thread 0 finish process 可以看到, 在并行区域的内部, 由于加入了明确的屏障语句, 直到等到所有的线程执行初始 化完毕之后, 才真正进入处理的操作 循环并行化中的顺序语句 (ordered) 在某些情况下, 我们对于循环并行化中的某些处理需要规定执行的顺序, 典型的情况是在一次循环的过程中, 一大部分的工作是可以并行执行的, 而其余的工作需要等到前面的工作全部完成之后才能够执行 在循环并行化的过程中, 可以使用 ordered 子句使得顺序执行的语句直到前面的循环都执行完毕之后再执行 下面的例子说明了 ordered 子句是如何对结果产生影响的 代码 5.24 循环并行化中的顺序语句 void work(int k) printf("thread id =%d k=%d\n",omp_get_thread_num(),k); #pragma omp ordered printf(" %d\n", k); void ordered_func(int lb, int ub, int stride) int i; #pragma omp parallel for ordered schedule(dynamic) for (i=lb; i<ub; i+=stride) work(i); int main(int argc, char ** argv) ordered_func(0, 50, 5); return 0; 这个程序根据步长为 5 的等差数列进行工作, 下面是一次执行的结果 (OMP_NUM_THREADS=5): thread id =4 k=0 0 thread id =4 k=25 thread id =0 k=15 thread id =2 k=20 thread id =1 k=5 5 thread id =1 k=30 thread id =3 k=10
10 thread id =3 k=35 15 thread id =0 k=40 20 thread id =2 k=45 25 30 35 40 45 从结果我们可以看出, 虽然在 ordered 子句之前的工作是并行执行的, 但是在遇到 ordered 子句的时候, 只有前面的循环都执行完毕之后, 才能够进行下一步的执行 在使用事件进行执行顺序处理的同步操作时候,OpenMP 还提供了 master 子句 ( 只能在主线程中执行 ) 以及 flush 子句 ( 用于程序员自己构造执行顺序 ) 等, 限于篇幅, 就不再赘述 循环调度与分块在多线程程序中, 要实现较好的负载平衡而获得最优的性能, 就必须对循环进行高效的调度与分块 这样做的最终目的是保证执行核尽可能地在大部分时间内保持忙碌状态, 同时将调度开销 上下文切换开销和同步开销降到最低 如果负载平衡做的很差, 那么某些线程可能很早就完成了自己的工作, 从而导致处理器资源闲置, 损失了性能 为了提供一种简单的方法能够在多个处理器核之间调节工作负载,OpenMP 给出了四种调度方案, 可以适用于很多情况 :static dynamic runtime 和 guided 英特尔 C++ 和 Fortran 编译器都支持这四种调度方案 负载平衡很差通常是由循环迭代计算时间的不确定性引起的 一般来说, 通过检查源代码的方法来确定循环迭代计算时间并不是太难 在多数情况下, 循环迭代总是耗费一定数量的时间 即便不是这样, 也可以找到耗时相近的一组迭代 例如, 有时候所有的偶数迭代集合和所有奇数迭代集合所耗费的时间几乎相等, 或者循环前半部分迭代和后半部分迭代所耗费的时间几乎相等 另一方面, 要找出耗时相同的迭代集合几乎是不可能的 然而不管怎样, 都可以通过使用 schedule(kind [, chunksize]) 子句来提供循环调度信息, 使编译器和运行时库能够更好的划分迭代并将迭代分布到各个线程 ( 也就是处理器核 ), 从而实现更好的负载平衡 默认情况下,OpenMP 的 parallel for 循环或任务分配 for 循环都会采用静态负载平衡调度策略 (static-even) 这就意味着该循环的迭代将以近乎平均的方式分布到各个线程上 如果有 m 次迭代, 线程组中有 N 个线程, 那么每个线程就执行 m/n 次迭代 编译器和运行时库将正确处理 m 不能整除 N 的情况 使用静态平衡调度, 能够尽可能地降低当多个处理器同时访问同一片内存区域时发生访存冲突的几率 这种方案之所以可行, 是因为循环一般是顺序访存的, 所以将循环分割为较大的块就可以减少重叠访存的几率, 提高处理器 cache 的使用效率 考虑下面这个简单的循环使用静态平衡策略在两个线程上执行的情形
#pragma omp parallel for for (k = 0; k < 1000; k++) do_work(k); OpenMP 将在一个线程上执行迭代 0 到 499, 在另一个线程上执行迭代 500 到 999 虽然这种划分方式对于内存的利用来说可能是比较好的, 但对于负载平衡可能是不利的 而更不幸的是, 这句话反过来也成立 : 有利于负载平衡的策略也有可能对访存的性能不利 因此, 进行性能优化时, 就必须在优化内存利用和优化负载平衡之间进行折中, 通过对性能的测量找出能够得到最佳结果的方法 在 OpenMP 的 for 结构中, 使用 schedule 子句将循环调度和分块信息传达给编译器和运行时 库 #pragma omp for schedule(kind [, chunksize]) 表 5.4 总结了 OpenMP 规范中所指定的四种调度方案 如果指定了可选参数 chunksize( 块 大小 ), 则该参数必须是不随循环变化的正常数常量或整数表达式 在调整块大小时要特别注意, 因为它可能会对性能带来负面影响 随着块的大小的减小, 线 程用于从任务队列中获得任务的时间会增加, 结果使访问任务队列的开销增加, 而降低性能, 并有可能抵消负载平衡带来的性能提升 调度类型描述 static ( 默认将所有循环迭代划分成相等大小的块, 或在循环迭代次数不能整除线程数不指定块大与块大小的乘积时划分成尽可能大小相等的块 如果没有指定块大小, 迭小 ) 代的划分将尽可能的平均, 使每个线程分到一块 将块大小设置成 1 就可以交错分配各个迭代 dynamic 使用一个内部任务队列, 当某个线程可用时, 为其分配由块大小所指定的一定数量的循环迭代 线程完成其当前分配的块后, 将从任务队列头部取出下一组迭代 在默认情况下, 块大小是 1 使用这种调度类型时要小心, 因为这种调度策略需要额外的开销 guided 与 dynamic 策略类似, 但块大小刚开始比较大, 后来逐渐减小, 从而减少了线程用于访问任务队列的时间 可选的 chunk 参数可以指定所使用的块大小的最小值, 默认是 1 runtime 在运行时使用 OMP_SCHEDULE 环境变量来确定使用上述调度策略中的某一种 OMP_SCHEDULE 是一个字符串, 其格式和 parallel 结构中所给出的调度策略参数格式相同表 5.3 OpenMP 中的四种调度方案 对于 dynamic 调度来说, 块是以先来先服务的方式进行处理的, 默认的块大小是 1 每一次取得的迭代次数和 schedule 子句中所指定的块大小相等, 但最后一个块例外 当一个线程执行完分配给它的迭代后, 它将请求另一组迭代, 其数量由块大小指定 这个过程不断重复, 直至所有的迭代都被完成 最后一组迭代的个数可能小于块大小 例如, 如果使用 schedule(dynamic, 16) 子句将块大小定义为 16, 而总的迭代次数是 100, 那么划分的情况
就是 16,16,16,16,16,16,4, 共分成 7 个块 对于 guided 策略来说, 一个循环的划分是基于下列公式来完成的, 其中初值 β0 = 迭代次数 π k βk = 2N 其中 N 是线程个数, π 代表第 k 块的大小, 从第 0 块开始, 在计算第 k 块的大小时, β 代 表剩下的未调度的循环迭代次数 k k 如果 π 的值太小, 那么该值就会被块大小 S 所取代, 而 S 是由 schedule(guided,chunk-size) k 子句指定的 如果在 schedule 子句中没有指定块大小的值, 则取默认值 1 因此, 对于 guided 调度策略来说, 循环分块的方法取决于线程个数 ( N ) 迭代次数( β 0 ) 和块大小 ( S ) 例如, 给定一个循环, β 0 =800, N =2, S =80, 循环划分为 200, 150, 113, 85, 80, 80, 80, 12 当 π 4 小于 80 时, 它就取值为 80 当剩余未调度迭代个数小于 S 时, 最后一个块 大小的上界会根据需要进行调整 英特尔 C++ 和 Fortran 编译器所支持的 guided 调度策略 是遵从 OpenMP 2.5 标准来实现的 通过使用 dynamic 和 guided 调度机制, 开发人员可以对应用程序进行调整, 以应对循环的 各个迭代工作量不统一或某些处理核 ( 或处理器 ) 比其它的核 ( 或处理器 ) 运行的快的情形 在一般的情况下,guided 调度策略比 dynamic 调度策略的性能好, 因为它的开销要少一些 runtime 调度方案本质上不是一种调度方案 如果在 schedule 子句中指定 runtime 作为调 度策略,OpenMP 运行时环境就对当前的 for 循环使用由 OMP_SCHEDULE 环境变量所指定的调 度方案 OMP_SCHEDULE 环境变量的格式是 schedule-type [, chunk-size] 例如 : export OMP_SCHEDULE=dynamic, 16 使用 runtime 调度策略可以为终端用户提供一定的灵活性, 使其能够通过使用 OMP_SCHEDULE 环境变量在前面所提及的三种调度机制中进行动态选择 OMP_SCHEDULE 的默认值是 static 此外, 了解循环调度与分块方案将极大的帮助程序员选择正确的调度策略, 有助于避免应用 程序在运行时出现的伪共享 (false-sharing), 从而实现较好的负载平衡 考虑如下示例 : float x[1000], y[1000]; #pragma omp parallel for schedule(dynamic, 8)
for (k = 0; k < 1000; k++) x[k] = cos(k) * x[k] + sin(k) * y[k]; 假设有一个双核处理器系统, 其 cache 线大小是 64 字节 对于上面给出的示范代码, 在一个 cache 线中可以放两个迭代块 ( 或两个部分数组 ), 因为块大小在 schedule 子句中被设置为 8 这样的话, 数组 x 的每个迭代块都用去 cache 线中的 32 字节, 两个迭代块数据可以放在同一个 cache 线中 因为这两个块有可能被两个线程同时读写, 所以即使两个线程不会读 / 写同一数据, 也可能会导致一些 cache 线被作废 这就称为伪共享, 也就是说实际上没有必要在两个线程间共享这个 cache 线 有一种比较简单的解决方法, 就是使用 schedule(dynamic, 16), 这样一个块就能占据整个 cache 线, 从而消除伪共享 通过使用与 cache 线大小相适应的块大小设置来消除伪共享可以极大的改善应用程序的性能