Antes de mirar implementaciones individuales, es útil limitar la búsqueda identificando algunas características esenciales de los marcos de procesamiento de gráficos distribuidos. Aquí hay tres importantes:
- Eficiente cálculo iterativo. Los algoritmos gráficos tienden a involucrar múltiples iteraciones sobre los mismos datos. Es posible expresarlos como una serie de trabajos de MapReduce, pero la única forma de comunicarse entre dos iteraciones sucesivas es escribir el estado del gráfico en un almacenamiento estable, como HDFS. Esto incurre en gastos generales de E / S de disco y serialización. Un marco gráfico no debería tener que pagar esta penalidad.
- Tolerancia a fallos. Las aplicaciones a gran escala deben ser tolerantes a fallas, pero los marcos que incluyen Parallel BGL y CGMgraph (y GraphLab) no manejan las fallas automáticamente. La forma estándar de implementar la tolerancia a fallas es verificar periódicamente el estado mutable del punto de control, y la mayoría de los marcos siguientes utilizan esta técnica.
- Modelo de programación orientada a gráficos. Hay muchos marcos de uso general para la informática distribuida, pero escribir algoritmos gráficos en ellos introduce una complejidad innecesaria. Los marcos de gráficos deben ofrecer abstracciones específicas que faciliten el trabajo con gráficos.
A continuación, presentamos algunos marcos de procesamiento de gráficos de código abierto que ofrecen estas características. La mayoría de ellos siguen el modelo paralelo sincrónico masivo, donde los vértices se envían mensajes entre sí en una serie de iteraciones llamadas superpasos.
- Giraph [1], una implementación de Java BSP que se ejecuta en clústeres Hadoop existentes y proporciona tolerancia a fallas tanto para los trabajadores como para el maestro que usa ZooKeeper. Giraph salió de Yahoo! y ahora es un proyecto de Apache Incubator.
- GraphLab [2, 3], un modelo de programación asíncrono en C ++ de Carnegie Mellon.
- Phoebus [4], una implementación de Erlang BSP que puede usar HDFS para el almacenamiento.
- Golden Orb [5], otra implementación de Java BSP en Hadoop.
- Signal / Collect [6], una implementación de Scala BSP de la Universidad de Zurich. Signal / Collect también admite extensiones, incluido un modo asíncrono.
- Actualización: GraphX [16] es un nuevo marco de procesamiento de gráficos integrado en Spark que permite ver los mismos datos como un gráfico y como tablas. Viene incluido con Spark 0.9. (Estoy en el equipo GraphX).
Finalmente, aquí hay algunos sistemas de propósito general que podrían ser una buena opción para el procesamiento de gráficos:
- ¿Por qué es que cuando se requiere que los estudiantes universitarios (CS, IT o IS) realicen investigaciones / proyectos / tesis, siempre se trata del diseño y desarrollo de sistemas?
- ¿Cómo puedo aprender la teoría del lenguaje de programación?
- ¿Sobre qué temas puede investigar un estudiante de informática?
- Cómo escribir un trabajo de investigación en algoritmos
- ¿Cuáles son las áreas de investigación actuales en informática?
- Spark [7], un marco Scala de UC Berkeley que tiene como objetivo equilibrar la eficiencia y la tolerancia a fallas al proporcionar colecciones inmutables, distribuidas y en memoria que recuerdan cómo se crearon y pueden repararse automáticamente. Bagel [8] fue una implementación temprana de BSP además de Spark, y GraphX [16] ahora es la forma canónica de hacer procesamiento gráfico en Spark.
- Piccolo [9], un sistema C ++ de NYU que proporciona una tabla compartida en memoria con puntos de verificación para tolerancia a fallas y acumulación para concurrencia. Hay un ejemplo de implementación de PageRank en Piccolo [10].
- HaLoop [11], una versión de Hadoop de la Universidad de Washington que se ha modificado y optimizado para admitir la iteración. Aquí está el PageRank en HaLoop [12].
- Twister [13], otro tiempo de ejecución iterativo de MapReduce de la Universidad de Indiana. Aquí está el PageRank en Twister [14].
- Ciel [15], un sistema Python que, junto con el lenguaje Skywriting, proporciona una variedad de operadores de flujo de datos y maneja la tolerancia a fallas de manera similar a como lo hace Spark, aunque sin la ventaja de rendimiento de mantener los datos en la memoria en todos los trabajos.
[1] Giraph: http://incubator.apache.org/giraph/
[2] GraphLab: http://graphlab.org/
[3] Modelo de programación GraphLab: http://graphlab.org/abstractiono…
[4] Febo: https://github.com/xslogic/phoebus
[5] Golden Orb: http://www.goldenorbos.org/
[6] Señal / Recopilar: http://code.google.com/p/signal-…
[7] Spark: http://spark-project.org/
[8] Bagel (BSP en Spark): https://github.com/mesos/spark/w…
[9] Piccolo: http://piccolo.news.cs.nyu.edu/
[10] PageRank en Piccolo: http://kermit.news.cs.nyu.edu/br…
[11] HaLoop: http://code.google.com/p/haloop/
[12] PageRank en HaLoop: http://code.google.com/p/haloop/…
[13] Twister: http://www.iterativemapreduce.org/
[14] PageRank en Twister: http: //www.iterativemapreduce.or…
[15] Ciel: http://www.cl.cam.ac.uk/research…
[16] GraphX: Guía de programación GraphX
