Balance dinámico de carga en sorting paralelo

Abstract

El Sorting (ordenación) es una de las operaciones más comunes e importantes que se realizan en una computadora. Numerosos algoritmos requieren que los datos (numéricos o no numéricos) se encuentren ordenados para poder accederlos de manera más eficiente. Uno de los problemas de los algoritmos de sorting es cuando la secuencia de datos es muy grande. Los mejores algoritmos secuenciales tienen tiempos de orden O(n x Log n) donde n es el número de datos. La solución al tiempo de procesamiento creciente con n ha sido la paralelización de los algoritmos de ordenación, utilizando varios procesadores. La utilización de múltiples procesadores trabajando sobre subsecuencias del total n de datos puede alcanzar un rendimiento cercano al óptimo (speedup = n), pero alcanzar este óptimo es dificultoso en arquitecturas reales. Uno de los ejes para alcanzar una perfomance óptima en la ordenación paralela es lograr un balance en el trabajo a realizar por cada procesador. Nótese que el trabajo no depende solo de la cantidad de datos de cada subsecuencia, sino también del desorden parcial de la misma, y de la potencia de cómputo de cada procesador. Este trabajo desarrolla una técnica de redistribución dinámica de la carga de datos a partir de la predicción del trabajo a realizar por cada procesador, permitiendo así una carga balanceada del trabajo entre los diferentes procesos. Se demuestra que el método tiende a alcanzar el óptimo teórico en la performance del algoritmo paralelo.