第十一章 同步与OpenMP内存模型
内存一致性模型
OpenMP线程在共享内存中执行,共享内存是组中所有线程都可以访问的地址空间,其中存储着变量.使共享内存系统高效运行的唯一方法是允许线程保持一个临时的内存视图,该视图驻留在处理器和内存RAM之间的内存结构中.
当线程通过共享内存中的变量进行交互时,线程必须使它们对内存的临时试图与共享视图一致.线程通过 flush构造 来实现这点.
冲刷集(flush-set) 是应用于冲刷的共享变量的集合.默认情况下,冲刷集是线程可用的所有共享变量.
- 进行显式冲刷的构造:
#pragma omp flush [(flush-set)]
除了解决内存一致性的问题,冲刷还和管理编译器何时可以重新排序指令的规则进行交互.如果指令使用了冲刷集的变量,编译器是不允许围绕冲刷来重新排序指令的.
- sequenced-before关系:
单个线程执行的事件之间的偏序.A排序在B之前,则A sequenced-before B.
顺序点(sequenced point): 程序执行中的点,在此处所涉及的有关语句以及与语句相关的任何附带后果均已完成.如果A的评估(包括A所隐含的任何附带后果)在B的执行之前完成,那么我们说A被排序在B之前.
常见的顺序点:
- 一个完整表达式的结束.包括if,while,for和return等.
- 在逻辑运算符,条件运算符以及逗号运算符处.
- 在函数调用时,所有参数的评估之后,但在调用前.
- 在函数返回之前.
事实上对于程序中顺序点的排序,我们有三种情况:
- sequenced-before:顺序点之间的关系是一个顺序点接着另一个顺序点.举例:
int a=1,b=2;
//由于赋值操作和逗号运算符为顺序点,所以该式为顺序点
//由于逗号运算符有顺序,因而两个顺序点之间有sequenced-before关系
- indeterminately sequenced:顺序点之间的关系是,它们以某种顺序执行,但这个顺序没有被定义.例如:
c = func(a)+func(b);
//由于函数调用与赋值为顺序点,但是加法不为顺序点,所以func(a)与func(b)之间顺序不确定
//所以在func(a)+func(b)中,两个顺序点之间顺序不确定,存在indeterminately sequenced关系
- unsequenced:当顺序点发生冲突并导致未定义的结果时,该情况成立.例如:
a=a++;
//由于赋值为顺序点,完整的表达式为一个顺序点,对a的增量操作与加法却不是
//子表达式是无序的,对a的赋值与增量操作可能冲突,存在unsequenced关系
而对于单个线程,有一种happens-before关系直接沿用了sequenced-before关系的概念.
- happens-before:如果事件A是排序在事件B之前的.那么就说:A happens-befor B.
为了定义多个线程之间的happens-before关系,我们必须同步线程,于是我们将同步视为两个或多个线程之间的特定事件.我们通过一个synchronized-with关系来实现.
- synchronized-with:当线程围绕一个事件协调执行,以定义其执行的顺序约束时,synchronized-with关系在线程之间成立.可以将线程的执行看作是一个事件序列,将每个事件看作是一个顺序点.
线程中事件的同步用$\leftrightarrow$表示.
成对同步
在前面的第八章中,我们注意到OpenMP通用核心中并不支持成对的或点对点(point-to-point)的同步.我们将考虑通过 生产者-消费者模式 来推动这一讨论,这是并行计算中常用的模式.
在该模式下,生产者进行一些工作以产生一些结果;消费者等待生产者完成工作,然后消费结果.将这两个步骤之间的处理序列化在流水线中十分常见.
流水线并行 中,将生产者与消费者步骤显示为两个线性序列:一个线程用于运行生产者任务,另一个线程用于运行消费者任务,只要流水线阶段的数量足够大,这些流水线并行程序的性能就会不错.
先观察下面这样的一个生产者-消费者模式程序:
bool flag=false;
#pragma omp parallel shared(A,B,flag)
{
int id = omp_get_thread_num();
int nthrds = omp_get_num_threads();
if((id==0)&&(nthrds<2))
exit(-1);
if(id==0){//生产者
produce(A);
flag=true;
}
if(id==1){//消费者
while(!flag)
//自旋锁(spin mutex)结构
consume(A);
}
}
该程序逻辑上是正确的,但是实际上却是错误的.
在并行中,同步 有两个方面: 数据同步 和 线程同步.
对于 数据同步 ,我们需要两个线程在内存中看到同一个变量的一致值.我们通过 完全冲刷 实现.
在OpenMP通用核心中,以下几点都隐含了冲刷:
- 当一个新的线程组被parallel构造fork时.
- 当一个critical构造被线程加入时.
- 当一个线程完成一个critical构造并退出临界区时.
- 进入task区域时.
- 从task区域退出时.
- 在退出taskwait时.
- 在退出显式barrier构造时.
- 在退出隐式栅栏构造时.(无nowait)
对于 线程同步 ,我们需要在两个线程之间建立synchronized-with关系.我们通过 自旋锁 实现.
于是,在调整后,我们得到了下面的又一个逻辑上似乎没有错误的程序:
int flag=0;
omp_set_num_threads(2);
#pragma omp parallel shared(A,flag)
{
int id = omp_get_thread_num();
int nthrds = omp_get_num_threads();
if((id==0)&&(nthrds<2))
exit(-1);
if(id==0){
produce(A);
#pragma omp flush
flag = 1;
#pragma omp flush(flag);
}
if(id==1){
#pragma omp flush(flag)
while(flag==0)
#pragma omp flush(flag)
#pragma omp flush
consume(A);
}
}
然而这个程序实际上仍然是错误的.
与现代程序设计语言一致, 只有通过原子操作才能建立synchronized-with关系 .而将flag设置为1及将其加载到内存中都不是原子操作,存在数据竞争.
于是为了使得这个程序真正正确,关键是需要修改自旋锁,以便通过原子加载和存储操作建立synchronized-with关系.
首先,对于生产者,将flag变量的赋值放在一个atomic write构造中.
然后,对于消费者,先把while循环变成一个无限循环,再为了避免变量flag上的任何读写冲突,将值存储到一个临时的flag变量中,并测试该变量的值来决定何时脱离循环.
最终,我们得到一个如下的程序:
int flag=0;
omp_set_num_threads(2);
#pragma omp parallel shared(A,flag)
{
int id = omp_get_thread_num();
int nthrds = omp_get_num_threads();
if((id==0)&&(nthrds<2))
exit(-1);
if(id==0){
produce(A);
#pragma omp flush
#pragma atomic write
flag = 1;
}
if(id==1){
while(1){
#pragma omp atomic read
flag_temp=flag;
if(flag_temp!=0)
break;
}
#pragma omp flush
consume(A);
}
}
锁(mutex)及其使用
OpenMP的锁与pthreads的锁功能基本相同,它是用来围绕互斥建立同步协议的.
与critical构造不同,OpenMP的锁是作为库例程来实现的. 在使用锁之前必须对其进行初始化.
- 使用锁来保证互斥:
omp_lock_t lck;
omp_init_lock(&lck);
#pragma parallel shared(lck)
{
omp_set_lock(&lck);
//...do somethine
omp_unset_lock(&lck);
}
omp_destroy_lock(&lck);
锁的设置和解除设置意味着一次冲刷,它们隐含着所需的内存移动,用相互排斥功能来支持内存一致性.
当设置锁时,意味着一次冲刷,这样线程更新的值与内存中的值一致;当解锁时,值会被冲刷,所以当下一个线程抓取锁更新值时,它将看到正确的值.
C++内存模型与OpenMP
C++11定义了原子操作,用于定义synchronized-with关系.
C++中最常用的内存顺序包括以下几种:
- seq_cst:对所有线程来说,内存的加载和存储将以相同的顺序发生.这个顺序将是所有线程上执行的任何语义上有效的指令交叉.
- release:在释放操作R之前顺序的存储操作不得重新排序为出现R之后.
- acquire:在获取A之后顺序的加载操作不得重新排序,使得其看起来发生在A后.
- acquire_release:围绕一个acquire_release操作,加载和存储操作不能重新排序.