英特尔Cilk 语言。英特尔C++ 编译器的新功能 Cilk 语言扩展技术（以下简称 “Cilk 技术”）为 C/C++ 语言增加了细粒度任务支持，使其为新的和现有的软件增加并行性来充分发掘多处理器能力变得更加容易。

Cilk 技术主要用途

使用 Cilk 技术

Cilk 技术应用实例

Cilk 中的 Reducer 视图

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 函数的冲突。例中的一些语句行被删除，但是保留了相应的行号。

9 #include <algorithm>

10

11 #include <iostream>

12 #include <iterator>

13 #include <functional>

14

15 // Sort the range between begin and end.

16 // "end" is one past the final element in the range.

19 // This is pure C++ code before Cilk conversion.

20

21 void sample_qsort(int * begin, int * end)

22 {

23 if (begin != end) {

24 --end; // Exclude last element (pivot)

25 int * middle = std::partition(begin, end,

26 std::bind2nd(std::less<int>(),*end));

28 std::swap(*end, *middle); // pivot to middle

29 sample_qsort(begin, middle);

30 sample_qsort(++middle, ++end); // Exclude pivot

31 }

32 }

33

34 // A simple test harness

35 int qmain(int n)

36 {

37 int *a = new int[n];

38

39 for (int i = 0; i < n; ++i)

40 a[i] = i;

41

42 std::random_shuffle(a, a + n);

43 std::cout << "Sorting " << n << " integers"

<< std::endl;

44

45 sample_qsort(a, a + n);

48

49 // Confirm that a is sorted and that each element

// contains the index.

50 for (int i = 0; i < n-1; ++i) {

51 if ( a[i] >= a[i+1] || a[i] != i ) {

52 std::cout << "Sort failed at location i="

<< i << " a[i] = "

53 << a[i] << " a[i+1] = " << a[i+1]

<< std::endl;

54 delete[] a;

55 return 1;

56 }

57 }

58 std::cout << "Sort succeeded." << std::endl;

59 delete[] a;

60 return 0;

61 }

62

63 int main(int argc, char* argv[])

64 {

65 int n = 10*1000*1000;

66 if (argc > 1)

67 n = std::atoi(argv[1]);

68

69 return qmain(n);

70 }

现在，可以开始在 qsort 程序中引入并行。

Cilk_spawn 关键字表示一个函数（“子”）可以和其后语句（“父”）并行执行。关键字允许但不要求并行操作。当系统有多个处理器可用时 Cilk 技术会动态地决定哪些操作会被并行执行。

_Cilk_sync 语句表示它将等待同一函数中的所有_Cilk_spawn请求被处理完成后，该函数才能继续执行。_Cilk_sync 语句不会影响在其他函数中衍生的并行 strand（strand 是一串没有任何并行控制的串行指令序列）。

21 void sample_qsort(int * begin, int * end)

22 {

23 if (begin != end) {

24 --end; // Exclude last element (pivot)

25 int * middle = std::partition(begin, end,

26 std::bind2nd(std::less<int>(),*end));

28 std::swap(*end, *middle); // pivot to middle

29 _Cilk_spawn sample_qsort(begin, middle);

30 sample_qsort(++middle, ++end); // Exclude pivot

31 _Cilk_sync;

32 }

33 }

通过在程序中包含头文件 <cilk.h>，前面的用例可以用简化的 Cilk 关键字形式来重新编写。新的宏提供了没有下划线的小写方式的命名。下面的程序行显示了用简化命名的 cilk_spawn 和 cilk_sync。

19 include <cilk.h>

21 void sample_qsort(int * begin, int * end)

22 {

23 if (begin != end) {

24 --end; // Exclude last element (pivot)

25 int * middle = std::partition(begin, end,

26 std::bind2nd(std::less<int>(),*end));

28 std::swap(*end, *middle); // pivot to middle

29 cilk_spawn sample_qsort(begin, middle);

30 sample_qsort(++middle, ++end); // Exclude pivot

31 cilk_sync;

32 }

33 }

在上述两例中，第 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点与先前的视图进行合并。 如果没有新的视图生成， 合并是不必要的。