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

El 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 programador Profesor Min-Soo Kim de la Escuela de Computación en KAIST, puede procesar un gráfico de un billón de bordes con una sola computadora.

Los gráficos se utilizan ampliamente para representar y analizar objetos del mundo real en muchos campos, como las redes sociales, la inteligencia empresarial, la biología y la neurociencia. A medida que el número de aplicaciones de gráficos crece 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 gráficos algoritmo para procesar un gráfico a gran escala (por ejemplo, un billón de bordes). Por lo tanto, al desarrollar y probar algoritmos de gráficos, como un gráfico a gran escala, generalmente se usa un gráfico sintético en lugar del gráfico real. Esto se debe a que el uso compartido y el uso a gran escala de gráficos reales es muy limitado, ya que son propietarios o 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 el gráfico y ejecutar el algoritmo en el gráfico mediante el motor de procesamiento de gráficos.

El primer paso genera un gráfico sintético y lo guarda en los discos. Un gráfico sintético generalmente se genera mediante la generación basada en parámetros o métodos de escalado de gráficos. El primero extrae una pequeña cantidad de parámetros que pueden capturar algunas propiedades de una parcela real dada y genera una parcela sintética con los parámetros. Este último escala la parcela real dada a una más grande para preservar las propiedades de la parcela real original tanto como sea posible.

El segundo paso carga el gráfico guardado en la memoria principal de un motor de procesamiento de gráficos, como Apache GraphX, y ejecuta el algoritmo de gráfico dado 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 decenas o cientos de computadoras. Por lo tanto, el costo del enfoque tradicional 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. A continuación, el T-GPS procesa el algoritmo de la trama en la trama real pequeña como si la trama sintética a gran escala que se debe generar a partir de la trama real existiera en memoria principal. Después de ejecutar el algoritmo, T-GPS devuelve exactamente el mismo resultado que el enfoque convencional de dos pasos.

La idea principal detrás de T-GPS es generar solo la parte de la trama sintetizada a la que el algoritmo necesita acceder sobre la marcha y modificar el motor de procesamiento de la trama para reconocer la parte generada en vuelo como parte de la trama sintetizada realmente generada.

El equipo de investigación demostró que T-GPS puede procesar una gráfica de borde de 1 billón con una sola ordenadormientras que el enfoque convencional de dos pasos solo puede procesar un gráfico de borde de mil millones utilizando un grupo de once computadoras de la misma especificación. De esta manera, T-GPS supera el enfoque convencional 10,000 veces en términos de recursos informáticos. El equipo también demostró que la velocidad de procesamiento del algoritmo en T-GPS es hasta 43 veces más rápida que con el enfoque convencional. Esto se debe a que T-GPS no tiene la sobrecarga de la comunicación de red, mientras que el enfoque convencional implica una gran sobrecarga de comunicación entre computadoras.

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