|
Introducción La principal virtud que ofrece la utilización de la computación heterogénea es la posibilidad de contar con un entorno de maquinas (entorno HC) con distintas capacidades de computo, esto es maquinas que están mejor preparadas para ejecutar tareas con cierto tipo de paralelismo. Es importante lograr que las tareas se asignen a las maquinas de una manera adecuada, para medir esto se pueden utilizar distintas métricas. El problema de despacho de tareas en redes heterogéneas consiste en determinar la asignación de las tareas a las maquinas presentes en el entorno HC, de modo de optimizar alguna métrica. En la mayoría de los casos estudiados en la literatura se proponen varias métricas a optimizar, por lo tanto nos encontramos ante un problema de optimización multiobjetivo. En el caso de los problemas de optimización multiobjetivo se busca encontrar un conjunto de soluciones que logren balancear los criterios de optimización que se esta intentando optimizar. Luego de obtener el conjunto de soluciones óptimas se puede elegir la solución más adecuada según la prioridad que se le establezcan a los objetivos. Es muy poco frecuente obtener una única solución que optimice a todas las funciones objetivo a la vez. El problema de despacho de tareas en redes heterogéneas en un problema NP-difícil, por lo tanto no es posible resolverlo utilizando técnicas deterministas, como por ejemplo backtracking. En estos casos surge la necesidad de utilizar técnicas que obtengan buenas soluciones rápidamente, aunque las mismas no sean las soluciones óptimas globales. Estas técnicas son conocidas como heurísticas. Dentro de las que se encuentran una familia de heurísticas llamadas algoritmos evolutivos, que están basadas en la teoría de la evolución, que operan sobre un conjunto de soluciones, que es evolucionado a partir de la aplicación de distintos operadores evolutivos, hasta que se cumple una condición de parada. |
|
Paralelismo El paralelismo es una forma de resolver problemas con necesidades de cómputo muy grandes, cuando no se cuenta con un procesador con el suficiente poder de cómputo para resolver dicho problema en un tiempo razonable. Esta técnica consiste en hacer que varios procesos se ejecuten en distintos procesadores de forma colaborativa, para resolver un problema común. El funcionamiento de los algoritmos evolutivos permite que sean fácilmente paralelizables. La aplicación del paralelismo a la computación evolutiva hace que se puedan resolver problemas de gran complejidad utilizando un conjunto de equipos con poder de cómputo relativamente pequeño. Este trabajo se centrará en particular en la utilización de dos algoritmos evolutivos multiobjetivo (SPEA2 y NSGA-II) paralelos para la resolución del problema planteado.
|
|
MOEAs para despacho de tareas en redes heterogéneas |
|
|
