¿A qué se refiere Big Data?

El concepto de “Big Data” está relacionado con las tecnologías que permiten el procesamiento1 de grandes volúmenes de información, entendiéndose como grandes los volúmenes que por su tamaño o complejidad están por fuera del alcance de las herramientas de procesamiento de datos tradicionales.

A mediados de 2013 se ha hecho de público conocimiento el análisis de las comunicaciones masivo que realizaron agencias asociadas al gobierno de los Estados Unidos con el fin de monitorear o espiar actividades de habitantes de dicho país o de otros países del mundo. Fue entonces cuando el concepto de “Big Data” tomó un estado público que no tenía anteriormente, dado que este tipo de análisis fue realizado con herramientas relacionadas con dicho paradigma. Por lo tanto, es muy difícil, a partir de dicho hallazgo, darle el tinte únicamente tecnológico (o tecnocrático si se desea) que “Big Data” acarrea (cuyos principales elementos son objetivamente tecnológicos).

Si generalizamos este último razonamiento al ámbito de la tecnología como un todo, encontraremos que no se trata de un caso nuevo, ya que como se afirma en [Feenberg, 2002] en su teoría crítica, la tecnología no es una “cosa” (en el sentido más ordinario de dicho término), sino un proceso ambivalente de desarrollo suspendido entre diferentes posibilidades. Esta ambivalencia puede ser distinguida de la neutralidad tecnológica por el rol que esta atribuye a los valores sociales en el diseño de los sistemas técnicos (y no meramente en su uso o consumo).

Académicamente los principales impulsores de las tecnologías de procesamiento masivo de datos son Universidades, e Institutos. Comercialmente, corporaciones como Google, Yahoo, Amazon y Microsoft han dedicado recursos a la investigación en esta área. Usuarios de privilegio de estas tecnologías son las redes sociales: Facebook, Linkedin y Twitter (cuya existencia sería muy difícil sin las tecnologías Big Data), institutos científicos (investigación farmacológica, genética o aceleradores de partículas) o empresas con procesamiento masivo de datos o documentos como China Mobile o The New York Post.

Antecedentes

En principio fueron las actividades de investigación científica (relacionadas, por ejemplo, con biología molecular, telescopios, aceleradores de partículas, meteorología, etc.) las que han requerido de un nivel de procesamiento en volumen de datos fuera de la escala habitual (en el ámbito comercial) de su época.

El incremento en el tamaño de las bases de datos que es factible procesar tiene una explicación tanto en el aumento de la capacidad de cómputo, así como, en el incremento de la posibilidad de almacenamiento y acceso (dispositivos de almacenamiento). Justamente, el sentido de almacenar información relativa a determinados eventos o sucesos de una organización tiene un correlato con el costo o posibilidad de procesamiento disponible. Vale decir que muchas disciplinas (sobre todo en la minería de datos) han surgido por el hecho de que se “hizo” factible el tratamiento de determinada información. Gran parte de esta “información nueva” puede deberse a una necesidad concreta, pero otra parte debe su existencia a la generación de una necesidad artificialmente creada por la disponibilidad de tecnología para su procesamiento.

A mediados del siglo XX [Rider, 1944] se estimó que el crecimiento de las bibliotecas de las universidades de los Estados Unidos se doblaban en tamaño cada 16 años, con lo que se concluyó que en en el año 2040, la Universidad de Yale podría contrar con una biblioteca de 200.000.000 de volúmenes. Lo que requeriría un plantel de 6.000 personas para su mantenimiento. Este tipo de crecimiento viene aparejado con un cambio de paradigma tecnológico.

Paradigma y cambio

El foco de los sistemas tradicionales de procesamiento distribuido ha sido puesto sobre la computación de los problemas (lo que resulta obvio, ya que vinieron a resolver problemas de computabilidad), pero en un marco de gran complejidad de datos (tanto por cantidad, como por relaciones), es necesario enfocarse más sobre los datos.

El paradigma de procesamiento de información clásico instalado por la industria a partir de 1970 fue el modelo relacional de bases de datos, fuertemente sustentado en la teoría de conjuntos y en los predicados de primer orden de la lógica.

Las implementaciones físicas de dicho paradigma, con algunas diferencias con el modelo relacional teórico2, comenzaron a presentar complicaciones en el procesamiento de grandes volúmenes de datos. El escalamiento en este tipo de productos consiste en la implementación de un servidor de mayor potencia. La paralelización de las operaciones se ve afectada por varios de los mecanismos que implementan estos sistemas gestores de bases de datos relacionales para garantizar lo que se conoce como las propiedades ACID3. Esto último constituye un desafío de escalamiento que los motores de bases de datos relacionales no han podido sortear. Incluso las soluciones comerciales que mejoran el rendimiento en este aspecto se basan en la potenciación de un único núcleo de procesamiento (una especie de mainframe) que evitan buscar una solución computacional al problema de la merma del speed up en soluciones realmente paralelas. Cabe destacar que una máquina de 8 veces las capacidades de una PC standard de escritorio cuesta mucho más que 8 Pcs (de hecho, mucho más que 16 Pcs) y es lo que ocurre con este tipo de soluciones.

Es por eso que muchas veces se puede considerar a estas herramientas tradicionales como inadecuadas para tamaños o complejidades tan grandes. Hay modelos de programación que encajan mejor con determinados problemas. Hay, también, modelos de bases de datos que encajan mejor con el entorno y el ciclo de vida del proyecto en cuestión, como por ejemplo las bases de datos orientadas a objetos. Dichas bases de datos se llevan mucho mejor con el paradigma de orientación a objetos4 que las bases de datos relacionales.

Existe un movimiento desde fines de la década de 1990 llamado No SQL5 que principalmente se centró en los problemas de escalabilidad horizontal de las bases relacionales. Los desarrollos dentro de esta iniciativa tienen la particularidad de no cumplir con alguna de las cuatro propiedades ACID6 que sí cumplen las bases de datos relacionales con creces, además de que muchos de los proyectos se originó en el ámbito de la computación distribuida, por lo que no es casual que en el año 2002 se haya presentado una demostración formal del teorema de Brewer7.

El éxito de muchas de estas herramientas en el procesamiento de grandes volúmenes o complejidades de datos no sólo radica en la forma alternativa de modelarlos, sino en el alto nivel de paralelismo que pueden ofrecer. Para poder implementar este nivel de paralelismo se han acuñado una serie de propiedades paralelas a las ACID que permiten este crecimiento.

Referencias

[Feenberg, 2002] “Transforming technology – A critical theory revisited” – Andrew Feenberg – Oxford University Press

[Rider, 1944] “The scholar and the future of the research library” – Freemont Rider

Notas

1Tanto sea la captura, homogeneización, almacenamiento, búsqueda, compartimiento, transferencia o visualización de la información.

2Las diferencias tienen que ver a veces con imposibilidades de implementación física de determinados procedimientos como por ejemplo la utilización de multiconjuntos en lugar de conjuntos; otras veces, con la diferencia en el lenguaje de operación, que en el modelo relacional puede tratarse del álgebra o cálculo relacional y en la implementaciones físicas, con el lenguaje SQL (estándar de facto de la industria)

3Atomicidad: La ejecución de cada transacción debe ser atómica, es decir, o todas las acciones (dentro de la transacción en cuestión) se completan exitosamente o ninguna de ellas se completa, pero nunca puede quedar un estado intermedio, de modo que el usuairo no debe preocuparse por el efecto de transacciones incompletas. La base de datos garantiza ninguna transacción puede quedar “por la mitad”, aunque sea removiendo o volviendo atrás los cambios que quedaron “a medio hacer”. Consistencia: cada transacción debe preservar la consistencia de la base de datos, su integridad. Es la propiedad por la cuál una transacción siempre comienza en una instancia de base de datos consistente, por más que se encuentre (el DBMS) en “el medio” de la ejecución de otra transacción. Aislamiento: el usuario entiende que una transacción corre “sola” sin considerar el ruido que pueda hacer otra transacción ejecutándose en el mismo momento, es decir, las transacciones corren aisladas, o protegidas de los efectos de modificaciones concurrentes. Durabilidad: una vez que el DBMS le confirma al usuario que su transacción ha sido exitosa, sus efectos han sido persistidos (incluso si hay una falla del sistema).

4 Cabe destacar que la industria impuso las bases de datos relacionales, por lo que en los últimos 15 años han surgidos especificaciones de ORM (JPA de Java) y herramientas Open Source como Hibernate (la más popular) que pueden disimular las diferencias de modelos.

5 Que a veces es interpretado como Not Only SQL y que a veces se sugiere que debiera ser No Rel. Y que según sus integrantes vino a compartir como ellos habían logrado derrocar la tiranía de las lentas y caras bases de datos transaccionales a favor de una manera más eficiente y barata de manejar datos.

6 Atomicidad, Consistencia (Integridad), Aislamiento y Durabilidad.

7 También conocido como Teorema CAP, establece que es imposible que un sistema distribuido pueda dar simultáneamente estas tres garantías: Consistencia (todos los nodos ven la misma información), Disponibilidad (la falta de un nodo no impide al resto seguir funcionando) y Tolerancia a Fallos (Partition Tolerance, el sistema sigue funcionando a pesar de pérdidas arbitrarias de información o fallas parciales del sistema). Según el teorema sólo se pueden satisfacer dos simultáneamente de las tres.

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.

MPI & Eclipse

La configuración de MPI dentro del entorno eclipse puede ser confusa, aunque encontré todo lo necesario (aunque apenitas desactualizado) aquí. Si bien puedo correr cualquier programa escrito con MPI (instalando cualquier entorno de desarrollo MPI en linux) no logro que Eclipse interprete los comandos propios de MPI y los marca como error…. Pero a la hora de compilar, debugear y ejecutar, se trabaja lo más bien… Cuestión de seguir investigando…