Почему цикл for cilk_spawn работает лучше, чем цикл cilk_for?

я имею

cilk_for (int i = 0; i < 100; i++)
x = fib(35);

вышеуказанное занимает 6,151 секунды

а также

for (int i = 0; i < 100; i++)
x = cilk_spawn fib(35);

занимает 5,703 секунды

fib(x) это ужасная рекурсивная функция числа Фибоначчи. Если я наберу вниз функцию фиби cilk_for лучше чем cilk_spawn, но мне кажется, что независимо от того, сколько времени требуется, чтобы сделать fib(x) cilk_for должно быть лучше, чем cilk_spawn,

Что я не понимаю?

1

Решение

Согласно комментариям, проблема была в отсутствии cilk_sync. Я остановлюсь на этом, чтобы указать, как именно соотношение времени может быть предсказано с удивительной точностью.

В системе с аппаратными потоками P (обычно 8 на i7) код / ​​cilk_spawn будет выполняться следующим образом:

  1. Начальный поток выполнит итерацию для i = 0 и оставит продолжение, украденное каким-либо другим потоком.
  2. Каждый вор украдет итерацию и оставит продолжение для следующей итерации.
  3. Когда каждый вор заканчивает итерацию, он возвращается к шагу 2, если нет больше итераций для кражи.

Таким образом, потоки выполнят передачу цикла вручную, и цикл завершится в точке, где потоки P-1 все еще работают над итерациями. Таким образом, можно ожидать, что цикл завершится после оценки только (100-P-1) итераций.

Таким образом, для 8 аппаратных потоков for / cilk_spawn с отсутствующим cilk_sync должно занять около 93/100 времени для cilk_for, что довольно близко к наблюдаемому отношению около 5,703 / 6,151 = 0,927.

Напротив, в системе «дочернего кражи», такой как TBB или PPL task_group, цикл будет стремительно завершаться, генерируя 100 задач, а затем продолжит работу до вызова метода task_group :: wait. В этом случае, если забыть о синхронизации, это приведет к гораздо более драматическому соотношению времени.

2

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