¿T-GPS procesa un gráfico con billones de bordes en una sola computadora?

T-GPS procesa un gráfico con un billón de bordes en una sola computadora

Tecnología de simulación de procesamiento de gráficos a escala de billones (T-GPS). Crédito: KAIST

Un equipo de investigación de KAIST ha desarrollado una nueva tecnología que permite el procesamiento de un algoritmo gráfico a gran escala sin almacenar el gráfico en la memoria principal o en el disco. Nombrado como T-GPS (Trillion-scale Graph Processing Simulation) por el desarrollador Profesor Min-Soo Kim de la Escuela de Computación en KAIST, puede procesar un gráfico con un billón de bordes usando una sola computadora.

Los gráficos se utilizan ampliamente para representar y analizar objetos del mundo real en muchos dominios, como las redes sociales, la inteligencia empresarial, la biología y la neurociencia. A medida que el número de aplicaciones de gráficos aumenta rápidamente, desarrollar y probar nuevos algoritmos de gráficos se vuelve más importante que nunca. Hoy en día, muchas aplicaciones industriales requieren un algoritmo de gráfico para procesar un gráfico a gran escala (por ejemplo, un billón de aristas). Por lo tanto, al desarrollar y probar algoritmos de gráficos como para un gráfico a gran escala, generalmente se usa un gráfico sintético en lugar de un gráfico real. Esto se debe a que compartir y utilizar gráficos reales a gran escala es muy limitado debido a que son propietarios o son prácticamente imposibles de recopilar.

De manera convencional, el desarrollo y la prueba de algoritmos de gráficos se realizan mediante el siguiente enfoque de dos pasos: generar y almacenar un gráfico y ejecutar un algoritmo en el gráfico utilizando un motor de procesamiento de gráficos.

El primer paso genera un gráfico sintético y lo almacena en discos. El gráfico sintético generalmente se genera mediante métodos de generación basados ​​en parámetros o métodos de ampliación de gráficos. El primero extrae una pequeña cantidad de parámetros que pueden capturar algunas propiedades de un gráfico real dado y genera el gráfico sintético con los parámetros. Este último escala un gráfico real dado a uno más grande para preservar las propiedades del gráfico real original tanto como sea posible.

El segundo paso carga el gráfico almacenado en la memoria principal del motor de procesamiento de gráficos, como Apache GraphX, y ejecuta un algoritmo de gráfico determinado en el motor. Dado que el tamaño del gráfico es demasiado grande para caber en la memoria principal de una sola computadora, el motor de gráficos generalmente se ejecuta en un grupo de varias decenas o cientos de computadoras. Por lo tanto, el costo del enfoque convencional de dos pasos es muy alto.

El equipo de investigación resolvió el problema del enfoque convencional de dos pasos. No genera ni almacena un gráfico sintético a gran escala. En cambio, simplemente carga el pequeño gráfico real inicial en la memoria principal. Luego, T-GPS procesa un algoritmo de gráfico en el gráfico real pequeño como si el gráfico sintético a gran escala que se debe generar a partir del gráfico real existiera en la memoria principal. Una vez finalizado el algoritmo, T-GPS devuelve exactamente el mismo resultado que el método convencional de dos pasos.

La idea clave de T-GPS es generar solo la parte del gráfico sintético a la que el algoritmo necesita acceder sobre la marcha y modificar el motor de procesamiento de gráficos para reconocer la parte generada sobre la marcha como la parte del gráfico sintético realmente generado.

El equipo de investigación demostró que T-GPS puede procesar un gráfico de 1 billón de bordes usando una sola computadora, mientras que el enfoque convencional de dos pasos solo puede procesar un gráfico de mil millones de bordes usando un grupo de once computadoras de la misma especificación. Por lo tanto, T-GPS supera el enfoque convencional en 10,000 veces en términos de recursos informáticos. El equipo también demostró que la velocidad de procesamiento de un algoritmo en T-GPS es hasta 43 veces más rápida que el enfoque convencional. Esto se debe a que T-GPS no tiene sobrecarga de comunicación de red, mientras que el enfoque convencional tiene mucha sobrecarga de comunicación entre computadoras.

El profesor Kim cree que este trabajo tendrá un gran impacto en la industria de TI, donde casi todas las áreas utilizan datos de gráficos, y agregó: “T-GPS puede aumentar significativamente tanto la escala como la eficiencia del desarrollo de un nuevo algoritmo de gráficos”.


Similar Posts

Leave a Reply