| Título: | Balance dinámico de carga en sorting paralelo |
| Autores: |
Naiouf, Marcelo De Giusti, Laura Cristina Chichizola, Franco De Giusti, Armando Eduardo |
| Fecha: |
2012-10-16 2004 |
| Publicador: | Unversidad Nacional de La Plata |
| Fuente: |
 |
| Tipo: |
Objeto de conferencia Objeto de conferencia |
| Tema: |
Ordenación de Datos Paralelización de Algoritmos Predicción de perfomance Balance de carga Redistribución dinámica Parallel processing Parallel algorithms Distributed Ciencias Informáticas |
| Descripción: |
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. Eje: IV - Workshop de procesamiento distribuido y paralelo |
| Idioma: | Español |
1 Ajuste de las variables que gobiernan los modelos de comportamiento de HDM-4 para vías no pavimentadas de la región de Antofagasta (Chile) por Rojas Cazaluade, Oscar Orlando | 6 Alternativas para el fraccionamiento de un Parque Industrial por Borrego, Juan Antonio |
2 La Agrimensura como base de investigaciones arqueológicas por Alfageme, Marcelo O.,Papagni, Jorge H. | 7 La propiedad horizontal por López, María Inés |
3 Anteproyecto de saneamiento y loteo por Antolín, Ricardo Gabriel,Williams, Enrique Oliver | 8 Laguna "San Antonio" por Milone, Ricardo Raúl |
4 Balneario Municipal de la ciudad de Diamante por Battistessa, Gustavo J.,Palomeque, José F. | 9 Estudio catastral de tierras en el partido de San Fernando por Miquelarena, Carlos Alberto |
5 | 10 |