TBB Рекурсивная цепная реакция с более порожденными задачами

Question

Что следует сделать при использовании рекурсивной цепной реакции в TBB (C ++) для определения некоторых значений?

Например, при вычислении чисел Фибоначчи мы создаем две подзадачи в перегруженном методе execute (), которыйявляются: A для вычисления n-2.th числа и B для расчета n-1.th числа.В этом примере B порождается, и A устанавливается в spawn_and_wait_for_all (что означает, что задача A ожидает задачу B).

Но если мы, например, должны определить числа Трибоначи;тогда у нас должно быть три подзадачи.Мой вопрос состоит в том, какая из этих трех задач должна быть spawn_and_wait_for_all для достижения максимального параллелизма?

Этот вопрос также может быть применен, когда у нас есть n подзадач.

Answer 1

См. этот учебник для начинающих для справки о планировании срывов против жадных задач.В случае жадного планировщика (например, Cilk) степень параллелизма не зависит от того, какая подзадача выдана последней.Для планировщика останова планирование остановок уменьшает параллелизм.Эвристика для минимизации количества остановок заключается в использовании самой большой подзадачи для spawn_and_wait_for_all.Это снижает вероятность того, что у родительского потока закончится работа, и его придется украсть из другого места, что может привести к остановке, если другие дочерние задачи завершат работу до того, как родительский поток завершит то, что украл.