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 执行其他递归调用。这种递归调用能产生相当多的并行运算。

 

 

For more complete information about compiler optimizations, see our Optimization Notice.