¿Work Stealing es siempre el algoritmo de programación de hilos a nivel de usuario más apropiado?

Question

He estado investigando diferentes algoritmos de programación para un grupo de subprocesos que estoy implementando. Debido a la naturaleza del problema que estoy resolviendo, puedo suponer que las tareas que se ejecutan en paralelo son independientes y no generan nuevas tareas. Las tareas pueden ser de diferentes tamaños.

Fui de inmediato para el algoritmo de programación más popular "robo de trabajo" utilizando deques sin bloqueo para las colas de trabajos locales, y estoy relativamente satisfecho con este enfoque. Sin embargo, me pregunto si hay casos comunes en los que el robo de trabajo no sea el mejor enfoque.

Para este problema en particular, tengo una buena estimación del tamaño de cada tarea individual. El robo de trabajo no hace uso de esta información y me pregunto si hay algún planificador que proporcione un mejor equilibrio de carga que el robo de trabajo con esta información (obviamente con la misma eficacia).

NB. Esta pregunta se relaciona con un question anterior.

Answer 1

Distribuiría las tareas por adelantado. Con la información de su tiempo estimado de ejecución, puede distribuirlos en colas individuales, para cada hilo uno.

Distribuir las tareas es básicamente el knapsack problem, cada cola debe tomar la misma cantidad de tiempo.

Debe agregar algo de lógica para modificar las colas mientras se ejecutan. Por ejemplo, debe producirse una redistribución después de que el tiempo estimado de ejecución difiera en una cierta cantidad del tiempo de ejecución real.

Answer 2

Es cierto que el planificador de robo de trabajo no utiliza esa información, pero es porque no depende de ella para proporcionar los límites teóricos (por ejemplo, la memoria que utiliza, la comunicación total esperada entre los trabajadores y también el tiempo esperado para ejecutar un cálculo totalmente estricta como se puede leer aquí: http://supertech.csail.mit.edu/papers/steal.pdf)

un interesante documento (que espero que se puede acceder a: http://dl.acm.org/citation.cfm?id=2442538) utiliza realmente tiempo de ejecución acotado para proporcionar pruebas formales (que tratan de ser tan cerca de los límites originales de robo de trabajo como sea posible).

Y sí, hay casos en los que el robo de trabajo no funciona de manera óptima (por ejemplo, búsquedas de árbol no balanceadas y otros casos particulares). Pero para esos casos, se han optimizado (por ejemplo, permitiendo robar la mitad del deque de la víctima, en lugar de tomar solo una tarea: http://dl.acm.org/citation.cfm?id=571876).