CoNECEx 2013

CoNecEXIEl fin de semana pasado tuve el honor de participar en el primer Congreso Nacional de Estudiantes de Ciencias Exactas de Argentina que se llevó a cabo en la facultad de Informática de la Universidad Nacional de La Plata.

Allí charlamos sobre paralelismo y algorítmos genéticos con alumnos de todo el país en un ambiente sumamente agradable.

CoNECExEspero que los asistentes hayan disfrutado de la exposición tanto como yo disfruté preparándola.

Cabe destacar que la organización fue impecable, tanto para los disertantes como para los participantes. Se percibía un ambiente cómodo, que es quizás uno de los mayores méritos que puede tener un organizador. Valga entonces el agradecimiento por la invitación a los organizadores, en especial a Gastón Menvielle que le tocó pasar por momentos difíciles la semana pasada.

Anuncios

Conclusiones de Paralelizar GA con MPI

Habiendo implementado un algoritmo genético simple (en particular una minimización de la función valle de Rosenbrock) con el fin de utilizarlo como benchmark, puedo destacar ciertas conclusiones.

El método de paralelización utilizado fue el básico para estos casos, es decir, el monolítico en términos de algoritmos genéticos, o sea, es decir existirá una sola población global que evoluciona. Este mecanismo no es el mejor desde el punto de vista del paralelismo, pero la intención es utilizarlo como benchmark, por lo que pude relajar la exigencia.

Las operaciones que se paralelizaron fueron:

  • Evaluación del Fitness
  • Crossover y Mutación

Mientras que las operaciones que quedaron seriales fueron:

  • Inicialización
  • Selección

No se utilizó una condición de optimalidad, ya que la idea fue implementar algo comparativo, por lo que se forzó siempre la ejecución de 100.000 generaciones, aunque en la mayoría de los casos, antes de las 2.000 generaciones se había alcanzado un valor más que aceptable.

Por otro lado, dado que la representación para los cromosomas fue la clásica tira de bits, no se representó un contínuo, sino una discretización del mismo, quedando excluido el punto en donde se halla el mínimo global de la función (1,1). De esta manera el algoritmo explora una franja con forma de banana que se da en la representación tridimensional de la función donde se encuentran los valores mínimos de la misma.

Por tanto debe quedar claro que el objetivo no fue optimizar la función de Rosenbrock, sino implementar un algoritmo genético paralelo comparable con fines de benchmark.

La parametrización de las corridas ha sido la siguiente:

POBLACION_SIZE 200
MAX_GENERACIONES 100000
CROSSOVER_PROBABILITY 0,65
MUTATION_PROBABILITY 0,035

El resultado arrojado por la versión serial en un dual core (2Ghz) con 2Gb RAM fue:

Operación Tiempo en ms %
Inicializacion 0 0,00%
Computo del Fitness 728085 78,69%
Operaciones Geneticas (Cross+Mut+Reempl) 191311 20,68%
Seleccion 5880 0,64%
925276

Cabe destacar que una corrida serial en un procesador i7 con 8Gb de RAM toma 70 segundos (aproximadamente el 8% respecto a la corrida descripta).

Las corridas paralelas han arrojado los siguientes resultados:

Nodos Workers Tiempo Total Inicializacion Computo del Fitness Operaciones Geneticas Seleccion
1 0 925276 0 728085 191311 5880
2 1 457484 0,077 347019 104263 6085
3 2 548708 0,082 349236 192929 6432
4 3 502676 0,082 318536 177568 6458
5 4 489597 0,081 288175 194847 6445
6 5 494720 0,116 281966 206180 6464
7 6 349025 0,082 206147 136326 6432
8 7 349025 0,082 206147 136326 6432
9 8 294204 0,077 171204 116748 6137
10 9 286247 0,077 162048 117613 6471
11 10 407975 0,078 236078 165234 6494
12 11 468207 0,078 267160 194435 6449
13 12 582009 0,078 340445 234938 6439

TiemposPorWorker

Con respecto a los tiempos de las operaciones genéticas en paralelo vemos que no se evidencia un incremento en la performance que sea beneficioso en términos reales. Esto puede deberse a que las operaciones genéticas, en este caso, son operaciones a nivel de bits, que suelen ser sumamente eficientes a nivel de procesamiento; y que, por otro lado, implican una transferencia de datos importantes: se envían 2 individuos (en este caso cabe recordar que cada individuo consiste en un arreglo de 13 bytes) y se devuelven 2 individuos, por tanto cada operación implica una transferencia de 52 bytes entre master y worker. Por tanto, la mejora en términos de procesamiento no compite con el consumo de recursos de red provocado por esta estrategia.

En cambio, en la evaluación del fitness se da otro escenario, favorable al paralelismo. En este caso, por cada individuo se envían 13 bytes y se reciben 4 bytes. En esta operación, el consumo de CPU tiene un peso más significativo que el overhead provocado por la utilización de la red (hasta cierto punto). Con la presente configuración, se encontró un mínimo tiempo de procesamiento con 10 nodos (9 workers) para la evaluación del fitness, como para el tiempo global, de una magnitud de 4,5 y 3,23 veces respectivamente.

Como conclusión general se puede extraer:

  • En GA simples, las operaciones genéticas consumen poco procesador respecto al consumo de red de enviar 2 individuos y recibir otros dos individuos.
  • La operación que más fácilmente se paraleliza es el cálculo del fitness.
  • La paralelización es muy sensible a los parámetros: Cambiará mucho si el tamaño del individuo se multiplica por 100 (vuelva totalmente inviable la paralelización de las operaciones genéticas), o si el tamaño de la población se multiplica, podríamos empezar a obtener buenos resultados paralelizando las operaciones genéticas. Otro dato sensible es el consumo de procesador durante la evaluación del fitness. Si este consumo se multiplica por 100, el rendimiento del paralelismo incrementará, dado que es la función más fácilmente paralelizable.
  • El ancho de banda es un impedimento para la escalabilidad de la solución en paralelo con MPI (GA simple y monolítico). Más aún si el GA consume o genera datos centralizados.

Algunas notas sobre “Scaling Genetic Algorithms using MapReduce”

En esta publicación, los autores (Abhishek Verma, Xavier Llor`, David E. Goldberg y Roy H. Campbell) porponen la utilización del framework MapReduce (en particular con la implementación de Hadoop) para implementar GA paralelos. Fijan posición en que la implementación tradicional basada en MPI requiere mucho conocimiento sobre la máquina donde se monta, y que, por el contrario, MapReduce permite un nivel de escalabilidad que no introduce ningún cuello de botella.

En particular, se enfocan en las variantes tradicionales y sencilla de los GA para brindar una implementación de referencia.

De los pasos del algoritmo clásico genético, la evaluación de los fitness tiene una analogía directa con la función Map, la cuál evaluará el fitness del individuo y guardará track (en un counter) del mejor individuo, finalmente persistiéndolo en el HDFS, el proceso cliente (el que inició la tarea MapReduce) chequea recurrentemente en este archivo si se ha alcanzado el criterio de convergencia.

Para poder implementar la selección distribuida, hay que tener control o mantener estado global, lo cual es un tanto complejo en MapReduce, por lo que el único componente que puede realizar este tipo de tarea es el Partitioner. El problema puntual por el cual no conviene utilizar la implementación por defecto es que durante la etapa de Shuffling (el momento en el que el framework reparte, mezcla y distribuye las emisiones de los mappers a los reducers) es porque utiliza una función de hash sobre la key (módulo la cantidad de reducers) para distribuir la carga, generando inconvenientes de convergencia del GA. Por otro lado, mientras el algoritmo genético pogrese, muchos individuos serán iguales, por lo que serán tratados por el mismo reducer, con la reducción de performance que esto implicaría. Es por eso que los autores utilizaron un partitioner especial que en vez de utilizar un hash, utiliza un número pseudoaleatorio cuya semilla es (mapperId * time).

El mecanismo de selección que han utilizado es el de torneo, ya que es el único que puede implementarse con facilidad en MapReduce, ya que la ruleta implicaría el mantenimiento de un estado global y un par de iteraciones más. Para esto han decidido tomar individuos al azar y ver quien es el ganador n veces (n es el tamaño de la población) del torneo para someterlo a la cruza. La operación de crossover se realiza en conjunto con la selección de dos individuos.

El tipo de crossover que utilizaron es el uniforme.

Cuando las poblaciones son muy grandes, la inicialización serial de los individuos tomó mucho tiempo, por lo que decidieron agregar una tanda de procesamiento map reduce en el que el map genera un individuo al azar y el reduce es trivial.

Las medidas de performance que realizaron fueron hechas con la implementación de un problema trivial utilizado para benchmark llamado OneMax Problem que consiste en encontrar la máxima cantidad de 1’s en los cromosomas de los individuos, es decir, un individuo tal que todos sus alelos sean 1’s. El análisis realizado arrojó que:

  • Análisis de convergencia: Para 104 variables, converge en 220 iteraciones con un promedio de 149 segundos por iteración.
  • Escalabilidad con carga constante por nodo: Incrementando la cantidad de recursos, no cambia el tiempo de procesamiento por iteración.
  • Escalabilidad con carga constante general: Fijaron la cantidad de variables en 50.000 e incrementaron el número de mappers, logrando una reducción del tiempo de iteración. Aunque el speed-up general queda limitado por la ley de Amdahl (“la mejora obtenida en el rendimiento de un sistema debido a la alteración de uno de sus componentes está limitada por la fracción de tiempo que se utiliza dicho componente”) dado el overhead de Hadoop (unos 10 segundos para iniciar y terminar un job).
  • Escalabilidad con incrementos en el tamaño del problema: Utilizaron el máximo de recursos y fueron incrementando el número de variables, logrando un incremento razonable con incrementos de población superlineales (n log n).

El gran inconveniente de trabajar con MPI en clústers standard es la poca tolerancia a fallos del framework. MapReduce no tiene este inconveniente. Introducen ciertas críticas a la implementación llamada MRPGA respecto a la escalabilidad.

Otros enfoques han tratado de modificar MapReduce para que se parezca a algo más consumible desde los GA, lo interesante de este trabajo es que no han intentado martillar MapReduce, sino todo lo contrario.

Como línea de investigación proponen comparar rendimientos con MPI y demostrar la importancia de GA escalables en las aplicaciones prácticas.

Por otro lado cabe destacar que no se proveen detalles de la implementación a bajo nivel, de modo que mucho se puede conjeturar sobre la implementación específica que han realizado, y que no se han aventurado a explorar alternativas un poco más complejas que el GA básico.

Algunas notas sobre “A Survey of Parallel Genetic Algorithms”

En esta publicación de 1998, Erick Cantú-Paz hace hincapié en la facilidad de implementar GA paralelos y en sus ganancias en rendimiento. Para eso intenta colectar, organizar y presentar las publicaciones más representativas en este aspecto. Sin embargo se va a centrar en las investigaciones en donde los GA tengan múltiples poblaciones independientes.

Haciendo un paneo por la historia de los enfoques paralelos en GA, destaca el trabajo de Betke de 1976, en donde describió una implementación paralela de GA convencionales. Otro estudio interesante fue el de Grefenstette de 1981 que propuso mapear las arquitecturas paralelas existentes con GA, trabajando en 4 prototipos distintos, siendo uno de ellos el primer prototipo del enfoque de poblaciones múltiples, siendo el prototipo que más tardíamente se implementó (1987).

Luego de una breve introducción describiendo someramente el mecanismo de los GA, pasa a clasificar los GA paralelos:

    1. Global single-population master-slave GA: Donde existe una única población, pero el procesamiento de la evaluación del fitness es altamente distribuida. Cada individuo puede competir y cruzarse con cualquier otro. Se dice que el algoritmos es sincrónico si debe esperar la evaluación de todos los fitness (procesados en paralelo). Hay posibilidades de implementación asincrónica, pero en esos casos el mecanismo de GA no funciona de manera tradicional. La mayoría de las implementaciones son sincrónicas y reducen la velocidad de evaluación al tiempo de evaluación más lento de cada generación. Pueden ser implementados en modelos de memoria compartida, como de memoria distribuida. Cabe destacar que para paralelizar el proceso de selección habrá obstáculos por el overhead de comunicación, aunque Branke en 1997 paralelizó distintos tipos de selección global en una grilla 2D de procesadores mostrando que sus algoritmos eran óptimos para la topología utilizada (O(\sqrt{n}) en una grilla de \sqrt{n} x \sqrt{n}). La cruza y la mutación pueden ser fácilmente paralelizables utilizando la misma idea que para la evaluación del fitness. En conclusión, son fácilmente implementables y pueden ser un método eficiente y se puede aplicar la teoría disponible para los GA tradicionales.
    2. Single-population fine-grained GA: Consiste en una población espacialmente estructurada, en donde la selección y cuza se restringen a una pequeña vecindad del individuo. Manderick y Spiessens (1989) observaron que el rendimiento se degradaba a medida que el tamaño de la vecindad aumentaba. También pudieron demostrar que para un tamaño de subpoblaciones s y un largo de cromosoma l, la complejidad de tiempo del algoritmo es O(s+l) u O(s(log s)+l) pasos dependiendo del esquema de selección utilizado. Una conclusión interesante es que no se puede determinar una regla general para comparar el método fine-grained con el coarse-grained, aunque en 1992 Gordon, Whitley y Böhm demostraron que el camino crítico de un GA fine-grained es más corto que el de GA de población múltiple, aunque no incluyeron consideraciones de comunicaciones.
    3. Multiple-population (multiple-deme) coarse-grained GA: Son los más sofisticados, dado que consisten en varias subpoblaciones que intercambian individuos entre si eventualmente (migración). Cabe destacar que los efectos de la migración todavía no han sido comprendidos enteramente. Introduce cambios en el esquema de funcionamiento de los GA tradicionales. Tienen una analogía con el enfoque llamado “modelo de isla” de la genética de poblaciones. Una observación interesante sobre los estudios realizados en este ambiente relevan ciertas preguntas de interés: ¿Cuál es el ancho de banda de comunicaciones necesario para hacer que se comporten como GA global?¿Cuál es el costo de estas comunicaciones?¿Es el costo de las comunicaciones lo suficientemente pequeño como para hacer de esta una alternativa viable para el diseño de GA paralelos? Otro de los parámetros estudiados (particulamente en la investigación de Tanese en donde comparaba el rendimiento de un GA serial con respecto a la implementación paralela con y sin costo de comunicación) es el de la frecuencia de migración de individuos. En la misma investigación encontró que una implementación de múltiple población (r poblaciones de n individuos, sin costo de comunicación) encontraba soluciones de la misma calidad que la implementación serial con una población de r.n individuos. Los parámetros que controlan la migración de individuos son:
  • La topología que define las conexiones entre las subpoblaciones.
  • Una tasa de migración que controla cuántos individuos deben migrar
  • Un intervalo de migración que afecta a la frecuencia de las migraciones

Una de las conclusiones tiene una implicancia biológica notable: hay cambios favorables en los cromosomas que se extienden más rápido en poblaciones más pequeñas que en las más grandes.

  1. GA Paralelos Jerárquicos: Es una combinación de múltiples poblaciones y procesamiento maestro-esclavo. Dentro de esta rama hay investigadores que han combinado métodos. Este enfoque puede reducir el tiempo de ejecución más que cualquiera de las otras técnicas por si sola.

Probablemente el primer intento de fundamentar teóricamente el rendimiento de un GA paralelo fue una publicación de Pettey y Leuze de 1989, en donde se describe una derivación del teorema de los esquemas para GA paralelos. Una cuestión teórica muy importante es poder determinar si (y bajo qué condiciones) un GA paralelo puede encontrar una mejor solución que un GA serial. Hay dos observaciones en el trabajo de Starkweather (et al.):

  • Las subpoblaciones relativamente aisladas pueden converger a diferentes soluciones, y la migración y recombinación pueden combinar soluciones parciales. Se especula que por esto los GA paralelos con baja tasas de migración pueden encontrar mejores soluciones para funciones separables.
  • Si la recombinación de soluciones parciales resulta en individuos con fitness más pobre (quizás porque la función no sea separable), entonces los GA seriales pueden tener una ventaja.

La migración se considera sincrónica cuando en un determinado momento migran todos los individuos que se esperaba que migren. Hay un enfoque asincrónico. Hay enfoques que utilizan la migración asincrónica tanto cuando las subpoblaciones tienden a converger como cuando convergen totalmente. De esta manera surge una pregunta muy interesante: ¿Cuál es el mejor momento para migrar?

Topología de las comunicaciones: Es un factor fundamental en los GA paralelos. Si la topología tiene una conectividad densa, se supone que las buenas soluciones se expandirán más rápido a lo largo de las poblaciones. Por otro lado, si la topología es más rala, lo harán más lento, permitiendo la aparición de diferentes soluciones. La línea general de implementación dice que la topología de comunicación debe ser estática a lo largo de toda la ejecución. El enfoque de topología dinámica es utilizado cuando puede determinarse a qué subpoblación conviene más que migre un individuo.

Entre los avances más recientes para la fecha de publicación, el autor señala:

  • Se concluyo que la cantidad óptima de workers para el enfoque GA paralelo Global es S*=\sqrt{\dfrac{nT_{f}}{T_{c}}} donde n es el tamaño de la población, Tf es el tiempo que toma hacer una evaluación de fitness y Tc es el tiempo de comunicación. El speed-up óptimo es 0.5 S*.
  • Cuando las subpoblaciones están aisladas, el speed-up no es tan significante.
  • El speed-up es mucho mejor cuando las subpoblaciones están comunicadas.
  • Se puede determinar un número óptimo de subpoblaciones (asociado al tamaño de las mismas) que maximiza el speed-up.
  • Hay varios problemas que todavía no han sido resueltos, entre ello:
      • Determinar la tasa de migración que hace que las subpoblaciones distribuidas se comporten como una única población global.
      • Determinar la topología de comunicaciones adecuada que permita la combinación de buenas soluciones, pero que no resulte en un costo excesivo de comunicación.
      • Encontrar si hay un número óptimo de subpoblaciones que maximice la confiabilidad del GA.