Paralelismo en las operaciones en GAs

Antes de asignar roles en términos de Map-Reduce, conviene sobrevolar la noción de qué nivel de paralelismo soportan las operaciones más comunes que se dan en los GAs. Sin entrar en ningún detalle, y haciendo un análisis de nivel cero (o desde 10.000m de altura), creo que no está mal la siguiente tabla, en donde cada operación es encasillada en una de las siguientes categorías:

  • Necesariamente Serializable: La operación no puede, o no es eficiente que sea ejecutada en paralelo.
  • Serializable hasta cierto umbral: La operación para “n” bajos no muestra ninguna ventaja en ser ejecutada en paralelo. Generalmente ese “n” es el tamaño de la población.
  • Fácilmente Paralelizable: Es altamente paralelizable, la naturaleza de la operación no se riñe con el paralelismo.
  • Dificultosamente paralelizable: Si bien se puede paralelizar, implica esfuerzo de implementación y el pago de algún costo en el rendimiento (subóptimo).

Las operaciones que se tomaron como muestra, son las básicas, claramente se deberá estudiar cada posibilidad, pero no es el momento.

Necesariamente Serializable Serializable hasta cierto umbral Fácilmente paralelizable Dificultosamente paralelizable
Inicialización de la población
Azar x
Resultado de una heurística x x
Evaluación del fitness x
Selección x
Crossover x
Mutación simple x
Aceptación de individuos x
Reemplazo de Individuos x
Anuncios

Deje un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s