什么是正确的方法来计算斐波那契使用cilk

Question

当我学习cilk时，我用两个相反的例子来反驳:

从英特尔

2. 来自wiki(或网络上的其他示例):

相反的在这两行:

x = spawn fib (n-1);
y = spawn fib (n-2);

第一个站点说:

您不需要向第二个递归添加cilk_spawn属性调用fib()，因为这会创建一个空的continuation

我不明白为什么?
1. 什么是正确的方式?(使用2个刷出命令还是一个?)

Answer 1

来自英特尔文档"int x = cilk_spawn fib(n-1);"的代码请求在另一个威胁中运行它的许可，而下一行"int y = fib(n-2);"将在与主程序相同的威胁中运行。维基代码还要求一个新的威胁来计算fib(n-2)，这样如果有三个以上的处理器来运行主程序(fib(n))， fib(n- 1)和fib(n-2)都在单独的威胁上。

如果只有两个处理器，两个代码将执行相同的操作。以下内容来自维基页面:

…处理器没有义务在其他地方分配派生过程;如果机器只有两个处理器和，当执行fib(2)的处理器到达过程调用时，第二个处理器仍然忙于fib(1)，第一个处理器将暂停fib(2)并执行fib(0)本身，就像它是唯一的处理器一样。当然，如果另一个处理器可用，那么它将被调用到服务中，所有三个处理器将同时执行单独的帧。

Answer 2

你所指的维基百科中的例子来自MIT Cilk，它要求生成对Cilk函数的所有调用。这一要求在cilk++中被删除，并演变为英特尔的Cilk Plus实现。

请记住，被窃取的是continuation，而不是派生函数。在派生函数之前执行代码的worker将执行派生函数。cilk_spawn将continuation推送到worker的队列中，使得空闲的worker可以窃取它。

考虑在Cilk Plus中fib的完整实现:

int fib(int n) {
    if (n < 2)
        return n;
    int x = cilk_spawn fib(n-1);
    int y = fib(n-2);
    cilk_sync;
    return x+y;
}

如果你在第二次递归调用fib时设置了cilk_spawn，那么你就允许一个空闲的worker在该调用之后窃取continuation。但是这条链立即在cilk_sync处结束，所以这是浪费时间。