Как правильно вычислить Фибоначчи, используя cilk?

Question

Как правильно вычислить Фибоначчи, используя cilk?

Пока я учил Cilk, я столкнулся с двумя противоположными примерами:

Противоположность лежит в этих двух строках:

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

Первый сайт говорит:

Вам не нужно добавлять атрибут cilk_spawn ко второму рекурсиву
позвонить fib() потому что это создаст пустое продолжение

Я не понимаю почему?
Какой правильный путь? (используя 2 команды появления или только одну?)

0

c++cilk fibonacci

Решение

Другие решения

Пример в Википедии, на который вы ссылаетесь, взят из MIT Cilk, который требовал, чтобы все вызовы функций Cilk создавались. Это требование было снято с Cilk ++, который превратился в реализацию Intel Cilk Plus.

Имейте в виду, что это украденное продолжение, а не порожденная функция. Рабочий, который выполняет код до того, как порожденная функция выполнит порожденную функцию. cilk_spawnвыдвигает продолжение в рабочую деку, делая его доступным для кражи незанятым работником.

Рассмотрим полную реализацию fib в Cilk Plus:

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;
}

Если вы положите cilk_spawn при втором рекурсивном вызове fib вы позволяете незанятому работнику украсть продолжение после этого вызова. Но эта нить немедленно заканчивается на cilk_syncтак что это пустая трата времени.

1

Источник

Accepted Answer

Код из документа intel «int x = cilk_spawn fib (n-1);» запрашивает разрешение запустить его в другой угрозе, в то время как следующая строка «int y = fib (n-2);» будет работать на той же угрозе, что и основная программа. Вики-код запрашивает новую угрозу также для вычисления fib (n-2), чтобы при наличии более трех процессоров запустить основной progran (fib (n)), fib (n-1) и fib (n-2) Все на отдельные угрозы.

Оба кода будут работать одинаково, если было только два процессора. Следующее от вики-страницы:

… Процессор не обязан назначать порожденную процедуру в другом месте; если машина имеет только два процессора а также вторая все еще занята в fib (1), когда процессор, выполняющий fib (2), добирается до вызова процедуры, первый процессор приостановит работу fib (2) и сам выполнит fib (0), как было бы, если бы это был единственный процессор. Конечно, если доступен другой процессор, он будет запущен в эксплуатацию, и все три процессора будут выполнять отдельные кадры одновременно.

3