Всегда ли Work Stealing является наиболее подходящим алгоритмом планирования потоков на уровне пользователя?

Question

Я исследовал различные алгоритмы планирования для пула потоков, которые я реализую. Из-за характера проблемы, которую я решаю, я могу предположить, что задачи, выполняемые параллельно, независимы и не порождают никаких новых задач. Задачи могут быть разных размеров.

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

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

NB. Этот вопрос связан с предыдущим вопросом.

Answer 1

Я бы распределял задачи заранее. С информацией об их предполагаемом времени выполнения вы можете распределить их по отдельным очередям для каждого потока.

Распределение задач по сути является проблемой ранца, каждая очередь должна занимать одинаковое количество времени.

Вы должны добавить логику для изменения очередей во время их работы. Например, перераспределение должно происходить после того, как расчетное время работы на определенную величину отличается от реального времени работы.

Answer 2

Это правда, что планировщик кражи работы не использует эту информацию, но это потому, что он не зависит от нее, чтобы обеспечить теоретические ограничения, которые он делает (например, память, которую он использует, ожидаемый общий обмен данными между работниками, а также ожидаемый время для выполнения полностью строгих вычислений, как вы можете прочитать здесь: http://supertech.csail.mit.edu/papers/steal.pdf)

В одном интересном документе (который, я надеюсь, вы можете найти по адресу: http://dl.acm.org/citation.cfm?id=2442538) фактически используется ограниченное время выполнения для предоставления формальных доказательств (которые пытаются быть как можно ближе к исходной работе). кража границ как можно).

И да, есть случаи, когда кража работы не работает оптимально (например, несбалансированный поиск по дереву и другие частные случаи). Но для этих случаев была проведена оптимизация (например, позволяя украсть половину палубы жертвы вместо выполнения только одной задачи: http://dl.acm.org/citation.cfm?id=571876).