Почему цикл 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,
Что я не понимаю?
Решение
Согласно комментариям, проблема была в отсутствии cilk_sync. Я остановлюсь на этом, чтобы указать, как именно соотношение времени может быть предсказано с удивительной точностью.
В системе с аппаратными потоками P (обычно 8 на i7) код / cilk_spawn будет выполняться следующим образом:
- Начальный поток выполнит итерацию для i = 0 и оставит продолжение, украденное каким-либо другим потоком.
- Каждый вор украдет итерацию и оставит продолжение для следующей итерации.
- Когда каждый вор заканчивает итерацию, он возвращается к шагу 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. В этом случае, если забыть о синхронизации, это приведет к гораздо более драматическому соотношению времени.
Другие решения