Производительность кражи Cilk работы

Question

Я читаю статьи, в которых описывается работа Килка по краже графиков.

1) Насколько я понимаю, планировщик не знает задач критического пути, а просто пытается поддерживать его выполнение в любом случае, крадя задачи, которые не являются "глубокими" в графе задач. Это верно?

2) Кроме того, предполагает ли Cilk планировщик кражи работ, что все задачи имеют одинаковую сложность? Если задачи не одинаковы по сложности, не является ли планировщик менее гибким в достижении наилучшей производительности, то есть наилучшей балансировки нагрузки?

Answer 1

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

Ответ на (2) заключается в том, что планировщик задач Cilk не замечает сложности задач.

Ключевым принципом для понимания является "Лемма Брента" (обнаруженная ранее Грэмом). Лемма показывает, что (согласно предположениям PRAM), если задан жадный планировщик (тот, который никогда не позволяет работнику бездействовать, если есть работа), то абсолютный наилучший возможный график не более чем в 2 раза быстрее худшего возможного расписания, независимо от того, какова сложность задач.

Интуиция, лежащая в основе 2x, является пределом, заключающимся в том, что во время выполнения, если ни один работник не работает над задачей на критическом пути (жует на критическом пути), то каждый работник занят (жует на общей работе). Критический путь плюс общая работа не могут превышать вдвое общей работы алгоритма.

Предположение PRAM, вероятно, является самым слабым звеном на реальных машинах, где потеря кэша может занимать в 100 раз больше времени, чем попадание в кэш. Поэтому беспокойство о сложности задач менее важно, чем рассмотрение кеша. В зависимости от того, как используется Cilk, он очень хорошо работает с кешем (рекурсивные программы) или плохо (петли cilk_for подряд).