Cilk技术主要用途

Cilk 技术的设计特别适合但不限于 “divide 和 conquer” 的算法。它将问题分解成可以独立完成的子问题（任务），然后再将这些执行结果合并起来。另外，对于那些常常使用 “divide 和 conquer” 算法的递归函数， Cilk 技术同样也支持得很好。 任务既可以在不同的函数里实现，也可以在一个迭代的循环中完成。Cilk 关键字能有效地标识可并行执行的函数调用和循环，同时，Cilk 技术的运行环境能有效率地将这些任务调度到空闲的处理器上运行。

使用Cilk技术

下面描述了使用 Cilk 技术创建一个并行程序的操作步骤：通常，要有一个已经实现了基本功能的串行 C++ 程序。要确保该串行程序是正确无误的。因为虽然在串行程序中的任何 bug 仍会在并行程序中发生，但是这些 bug 在并行程序中将更加难以辨别和调试。找出程序中可以从并行操作中获益的代码段。那些执行时间相对长，并且能独立执行的操作是首选修改目标。用三个 Cilk 关键字标明那些能并行执行的任务： _Cilk_spawn（或 cilk_spawn, 如果程序包含了 cilk.h 文件）表示对一个函数（“子”）的调用，能与调用者（“父”）一起被并行处理。 _Cilk_sync（或 cilk_sync, 如果程序包含了 cilk.h 文件）表示所有衍生的“子”函数完成后，才能继续后续代码执行。 _Cilk_for（或 cilk_for, 如果程序包含了 cilk.h 文件）表示一个循环包含的迭代可以被并行执行。编译程序： Window* 操作系统：选择使用 icl 命令行工具，或者在微软的 Visual Studio* 下进行编译。如果使用 Visual Studio* 进行开发，确保已经从英特尔® Parallel Composer 相关菜单中选择了“Use Intel C++” Linux* 操作系统：使用 icc 命令执行程序。如果没有竞争条件，并行程序将输出和串行程序相同的结果。通过使用 reducer，锁，或者重写代码解决任何由于竞争条件而产生的冲突问题。

Cilk技术应用实例

下面以 Quicksort 为例，演示如何用 Cilk 技术编写一个并行化程序。其中使用函数名 sample_qsort 以避免和标准 C 函数库中的 qsort 函数的冲突。例中的一些语句行被删除，但是保留了相应的行号。现在，可以开始在 qsort 程序中引入并行。Cilk_spawn 关键字表示一个函数（“子”）可以和其后语句（“父”）并行执行。关键字允许但不要求并行操作。当系统有多个处理器可用时 Cilk 技术会动态地决定哪些操作会被并行执行。_Cilk_sync 语句表示它将等待同一函数中的所有_Cilk_spawn请求被处理完成后，该函数才能继续执行。_Cilk_sync 语句不会影响在其他函数中衍生的并行 strand（strand 是一串没有任何并行控制的串行指令序列）。通过在程序中包含头文件 <cilk.h>，前面的用例可以用简化的 Cilk关键字形式来重新编写。新的宏提供了没有下划线的小写方式的命名。下面的程序行显示了用简化命名的 cilk_spawn 和 cilk_sync。在上述两例中，第 29 行的语句将衍生出对 sample_qsort 的一次可异步执行的递归调用。这样，当 sample_qsort 在第 30 行再次被调用时，第 29 行的语句可能还没有执行完成。在第 31 行的 cilk_sync 语句表示在同一函数里的所有 cilk_spawn 请求执行完成前，该函数不能继续执行。在每一个函数的末尾都有一个系统隐含的 cilk_sync 用来等待当前函数衍生的所有任务完成，所以第 31 行的 cilk_sync 语句是多余的，但是这里为了使代码更清晰而加入了这行。上面的改动采用了一个典型的二分法策略来实现递归算法的并行化。在每一层的递归调用中，会产生一个两路的并行；“父” strand （第29行）继续执行当前的函数；而“子” strand 执行其他递归调用。这种递归调用能产生相当多的并行运算。

Cilk中的Reducer视图

Reducer视图 (The Reducer View)这里我们来讨论一下Cilk中的Reducer视图。在Cilk中， Reducer是我们支持的一种超级对象(Hyperobject)。什么是超级对象？ 他是一种被cilk运行环境支持的构件，使多个strand能互不影响地访问共享变量和数据结构，它是通过同时提供给每个strand一个超级对象的不同视图来实现。Reducer是我们唯一支持的超级对象。 根据超级对象的概念我们可以知道， 视图(View)其实是超级对象的一个状态。视图作为输入(input)提供给strand， 不同的strand具有不同的Reducer视图， 他们根据该视图可以互不影响的访问共享变量和数据。理解了Reducer视图的概念，那么Cilk运行系统如何产生一个Reducer 视图呢？ 我们同样用一个例子来说明视图的生成。假设我们有下面这样一些任务。mywork (1);A: cilk_spawn mywork(3)mywork(2)B: cilk_sync;mywork(4)我们知道， cilk_spawn衍生出一个新的可以并行执行的任务。 这时可以分为密取发生和不发生两种情况。当密取不发生的时候， 如下图所示， 此时的程序执行是串行的， 没有新的线程来并行执行， 也就没有新的Reducer 视图被创建。当密取行为发生的时候，如下图所示， 此时在A点， 我们的主线程(I)有一个Reducer的当前执行视图(V1)， 线程(I)执行strand (3), strand(3)中使用的视图就是V1. 另一线程(II)密取工作strand (2), 这时strand(2)会得到一个新的Reducer视图(V2)。新生成的V2拥有Reducer的恒等值(identity value)， strand(2)基于该V2进行操作。 在B点进行Reducer同步的时候，新生成的V2与原来的视图V1进行合并。 合并后， V2被注销。 strand(4) 继续基于V1进行操作。理论上说， 我们可以理解为每个strand都有一个reducer的私有视图。然而基于性能的考虑， 视图的产生是延迟的(Lazy semantics)。并不是每一次的衍生调用都会有新的视图的生成。新视图的创建了必须符合下面两个条件:1. 首先，新的视图的创建必须在密取行为发生之后。 如果密取行为没有发生， 程序的执行其实是线性的。 这时就没有必要产生新的视图。2. 其次， 只有在新的strand里面首次存取reducer的时候，新的视图才会被创建。 也就是说， 当密取行为发生后， 视图也不是马上被创建出来的。 如果在新的strand里面没有基于reducer的存取操作， 那么我们是没有必要产生新的reducer视图的。如果新的strand里面有对reducer的存取操作， 那么在首次存取该reducer的时候， 系统才会在该存取点创建新的视图实例。如果新的视图被创建， 他会在cilk_sync点与先前的视图进行合并。 如果没有新的视图生成， 合并是不必要的。