Cilk work stealing performance

Question

Я читаю статьи, которые описывают работу Килка, занимающуюся графикой исполнения.

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

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

Answer 1

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

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

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

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

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