Всегда ли 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).