Algoritmo heurístico para equilibrar la carga entre subprocesos

Question

Estoy trabajando en un programa de subprocesos múltiples en el que tengo varios subprocesos de trabajo que realizan tareas de longitud desigual. Quiero equilibrar la carga de las tareas para garantizar que hagan aproximadamente la misma cantidad de trabajo. Para cada tarea T _i Tengo un número c _i que proporciona una buena aproximación a la cantidad de trabajo que se requiere para esa tarea.

Estoy buscando un algoritmo eficiente (O (N) N = número de tareas o mejor) que me dará "aproximadamente" un buen equilibrio de carga dados los valores de c _i. No tiene que ser óptimo, pero me gustaría poder tener algunos límites teóricos sobre cuán malas son las asignaciones resultantes.

¿Alguna idea?

Answer 1

desea implementar un algoritmo de trabajo robar. Cada subproceso de trabajo tiene una cola de doble finalización, las nuevas tareas se agregan al final de la cola más pequeña. Los trabajadores eliminan tareas de la parte superior de su propia cola (la separación superior/inferior reduce la contención), cuando un trabajador no tiene más trabajos que hacer, le roba un trabajo de la cola más grande. Es simple, y funciona bien, este es el algoritmo con el que se basa el sistema paralelo de Microsoft que viene con .net4.0, creo.

La asignación resultante es bastante bueno, subprocesos de trabajo sólo se quedan sin trabajo por hacer si no hay más puestos de trabajo disponibles en todo el sistema.

Nb. Si desea que se rompa un código de ejemplo, mi amigo escribió un sistema de robo de trabajo para C#, que puede encontrar here

Answer 2

En O (N) esto parece fácil.

Dale a cada hilo algunos "puntos". Deje p_i los puntos asignados a la secuencia T_i. Para cada tarea, elija la secuencia con el valor más alto p_i y reste el costo de la tarea desde p_i. Entonces solo necesita hacer un seguimiento de los hilos ordenados por puntaje, que es trivial en O (N) tiempo, y puede hacerse fácilmente en O (log N) con un árbol balanceado.

Para un funcionamiento continuo, no hay un mínimo en p_i. Si desea evitar que los puntajes se vuelvan deshonestos hacia -inf, solo agregue regularmente una cantidad arbitraria de P a todos los puntajes (la misma cantidad para todos los puntajes).

Edit: Me equivoqué N. Arriba, N es el número de hilos, contrario a la pregunta formulada. Con N = número de tareas, y T = número de hilos, esto lleva a un costo O (N * log T). Si T es "pequeño", está cerca de O (N).

Edición 2: Si todas las tareas son conocidos de antemano, así como el número de hilos, entonces creo que el cálculo de la programación óptima es similar a la knapsack problem y es, con toda generalidad, NP-completo (entonces obtendrás exponenciales en algún lugar). Un simple análisis basado en los costos, como de alguna manera describo más arriba, le dará una aproximación relativamente buena siempre que todas las tareas individuales tengan un pequeño costo en relación con el costo total que se asignará a cada hilo.

Answer 3

Echaré un vistazo a los algoritmos para el equilibrio de carga, p.

http://www.ieee802.org/3/trunk_study/february98/congdon.pdf

http://publib.boulder.ibm.com/infocenter/cicstg/v6r0m0/index.jsp?topic=/com.ibm.cicstg600.doc/ccllal0292.htm

Answer 4

forma más sencilla es para clasificar los trabajos que descienden por p_i (pero esto es O (n log n)) y hacer esto:

1. Para cada hilo que hemos est . run time e_n = 0.
2. Para cada tarea encuentro thread que tiene una mínima tarea e_n enque y e_n = e_n + p_i.

Este algoritmo debe darle mejores resultados, pero con el tiempo O (N M) donde N es el número de tareas y número M de hilos. El costo total de la solución es O (N log N + N M), por lo que para M < < N es O (N log N) y para M cerca de N es O (n^2).

Answer 5

Mi inclinación es no tratar de averiguar de antemano cómo asignar las tareas, sino para que se vayan todos en una cola de trabajo común. Cualquier hilo de trabajo que no tenga nada más que hacer toma la siguiente tarea de la cola hace el trabajo y verifica la cola para la siguiente tarea.

Answer 6

Si bien la sugerencia con respecto a la problema de la mochila es muy útil, usted ha dicho que usted está tratando de reducir al mínimo el tiempo neto de la ejecución. Tomar el enfoque de la mochila requeriría que siga aumentando los tamaños de su mochila hasta que obtenga una solución factible, no muy eficiente.

Si el tiempo de ejecución neto está limitado por el tiempo de finalización más largo entre todos los hilos que trabajan en paralelo, quiero asignar tareas para MINIMIZAR el tiempo de trabajo MÁXIMO en todos los hilos. Hacer esto puede dar como resultado uno o más hilos que no hacen mucho trabajo, por lo que realmente no estamos "equilibrando" el trabajo. Si desea equilibrar el trabajo, entonces esa es una función objetivo diferente. Por ejemplo, es posible que desee minimizar la varianza en el trabajo entre hilos.

Look en el área de taller de trabajo de planificación. Si sólo hace esto con poca frecuencia, me gustaría sugerir el uso de un algoritmo genético - si tiene que hacerlo con frecuencia y de manera más automatizada, sugeriría hacer un poco de búsquedas bibliográficas para los algoritmos deterministas. Espero que esto ayude.