A new distributed diffusion algorithm for dynamic load-balancing in parallel systems
Ana Cortés Fité · TDX (Tesis Doctorals en Xarxa) · 2000
Uno de los problemas centrales a resolver en computadores paralelos/distribuidos es conseguir una distribucion equitativa de la carga para evitar que un desbalanceo de la misma pueda provocar periodos de inactividad en los procesadores, Los alforitmos de balanceo dinamico de la carga permiten distribuir eficientemente la carga en tiempo de ejecuccion y son utiles para resolver aplicaciones que tienen unos requerimientos computacionales no conocidos a priori o patrones de comunicacion irregulares. Recientemente se han propuesto estrategias para balancear la carga dinamicamente que operan de un modo distribuido, es decir, cada procesador del sistema utiliza informacion de la carga de sus vecinos inmediatos (dominio del procesador) para decidir como distribuir su exceso de carga. Uno de las estratgias conceptualmente mas simple es el balanceo de carga mediante difusion. La idea subyacente es que un procesador pueda difundir fracciones de su exceso de carga a uno o mas de sus vecinos poco cargados con el objetivo de equilibrar la carga con todos sus vecinos. Puesto que este enfoque, en general, no producira una solucion blanceada de forma inmediata, este proceso de difusion se itera hasta que la diferencia de carga entre cualquier para de procesadores ea menor que un valor especificado (en el caso ideal, el estado de balanceo perfecto se alcanza cuando todos los procesadores tienen la misma carga). El problema de estas estrategias de difusion es que consideran la carga (proceso, datos, threads) como cantidades reales asumiendo que pueden dividirse en fracciones arbirarias. Esta suposicion es poco realista en los entornos de programacion paralela actuales en los cuales las cargas deben ser consideradas como cantiddes enteras. Si estas estrategias se adaptan a un modelo de carga discrteo (efectuando operaciones de redondeo) entonces producen situaciones en las cuales un blanceo de carga global no se puede garantizar cuando