Un algoritmo para balancear dinámicamente las tareas de un programa en sistemas paralelos

Abstract

DASUD ("Diffusion Algorithm Searching Unbalanced Domains'') es un algoritmo totalmente distribuido que se ha desarrollado para realizar el balanceo dinámico de carga y resolver los problemas de desequilibrio de carga que se producen cuando se suponen tareas indivisibles. Dichos problemas los encontramos en los algoritmos de tipo "nearest-neighbour'' (vecinos inmediatos) ya que, dada la naturaleza local de la información que manejan, pueden obtener situaciones localmente balanceadas que, sin embargo, muestren un elevado desbalanceo global. DASUD se ha comparado con dos de las estrategias más conocidas en la literatura dentro de la familia de los algoritmos de vecinos inmediatos: GDE ("Generalised Dimension Exchange'') y SID ("Sender Initiated Diffusion''). Para realizar la comparación, se ha utilizado un extenso conjunto de distribuciones de carga iniciales que cubren, por una parte, un amplio rango en el desequilibrio inicial de las cargas, y por otra, diferentes formas de distribución de dichas cargas en los procesadores. Las topologías que se han utilizado son las de tipo anillo, hipercubos y toros, y el número de procesadores varió desde 8 hasta 128. Del análisis de los resultados obtenidos, se concluye que DASUD supera a las otras estrategias ya que ofrece el mejor compromiso entre el grado de balanceo final y el tiempo necesario para alcanzarlo.