Cilk™ Plus并行程序的串行等价程序的执行过程

    C++社区的趋势近年来主要是通过以添加更多的库而不是语言关键字来实现增加程序的功能性,比如Threading Building Blocks以及Parallel Patterns库,但与主流发展趋势不同的是,Intel的Cilk™ Plus的实现方式则是以后者的形式——语言关键字来增加程序功能的,本文将就此给出分析。

    其中的一个主要原因是语言及其扩展主要是由编译器来实现转换,并且编译器能够提供一定程度的保证,比如串行等价语义等。

    每一个使用关键字来定义并行Cilk™ Plus的程序都有一个已在编译器实现中定义好的串行语义。 通过将每一个cilk_sync及cilk_spawn替换为空,且将每一个cilk_for以for关键字来替代,编译器由此将并行的Cilk™ Plus程序处理为一个有效的串行C/C++程序。 当两个逻辑并行的线程同时访问同一内存位置且至少一个为写内存操作时,程序行为此时出现竞态,如果一个Cilk™ Plus并行程序没有竞态发生的话,此时它将产生与其串行等价程序相同的结果。编译器是如何保证其串行等价的结果一致的?考虑以下的代码:

int foo() 
{ 
int x1 = func1(); 
int d1 = 0; 
int x2 = cilk_spawn child1(bar1(), bar2()); //产生一个输入参数为两个函数调用的子调用 
int x3 = cilk_spawn child2(&d1);            //传递一个栈变量到子调用中 
int x4 = func3();                     // func3能够与child1和child2同时运行 
cilk_sync;                            //等待两个子任务的完成以使用其计算的结果 
return x1 + x2 + x3 + x4 + d1; 
} 

程序的运行时可解释为:

1. foo函数中spawn出一个child1子任务以便它能与func1同时执行;

2. cilk_sync的声明会使程序的执行流在此等待child1和child2的返回,以便后续程序流能够使用其返回值。

在此代码的生成过程中,编译器主要做了3处转换:

1. 作为child1传入参数的两个函数bar1和bar2首先将被parent线程顺序执行,即函数foo所在的线程。

2. 在foo的return语句返回前,编译器会插入cilk_sync,这也是编译器对每一个包含cilk_spawn的函数所做的底层默认工作,这与fork-join的并行模型相一致,由此可使程序的行为更容易理解;

而且默认插入的cilk_sync也会保证foo的栈帧在整个foo函数执行期间一直为其spawn出的子任务所见。 在此例中,foo将d1的地址传给child2,这由此保证了当child2写d1内存位置处的内容时,此内存地址仍在foo的栈中。

3. 执行foo的线程执行到child1时,cilk_spawn之后的代码将被加入到工作队列中以便被之后的当前线程继续执行以及被其它spawn出的子工作线程执行,这种工作方式称为‘Parent Stealing’,且在库的实现中,‘Work Stealing’机制是用‘Child Stealing’的方式来完成,即在此例子中,child stealing意思是child1将被入队列且会被之后spawn出的worker线程们以steal的方式来完成执行。

    以下是一段并行递归代码,在此例子中的三元树中,每一个节点指向其左中右子节点且自身有颜色属性。通过对此树的一次递归遍历即可以建立一个含有所有红色节点的链表,当并行化此递归程序时,需要注意的是在将多个节点同时push入全局链表时可能会发生竞态。所以推荐的方式是用Cilk™ Plus中的hyper object机制来存取此链表,hyper object内部实现为对此全局变量/数据结构进行局部化处理,从而保证及时多线程同时存取全局地址时仍不会有竞态发生:

cilk::reducer_list_append<terntreenode *> root;
void
find_reds_par(terntreenode *p)
 {
       if (p->color == red) {
         root.push_back(p);
       }
       if (p->left) cilk_spawn find_reds_par(p->left);
       if (p->middle) cilk_spawn find_reds_par(p->middle);
       if (p->right) find_reds_par(p->right);
}  

    Cilk™ Plus的并行遍历实现可保证会跟串行遍历程序一样产生内部节点排序相同的结果一致的链表。

 

    关于更多Cilk™ Plus的规范或内部实现规定,可以访问https://software.intel.com/en-us/intel-cilk-plus.

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.
Возможность комментирования русскоязычного контента была отключена. Узнать подробнее.