GraphBLAST: Un marco de gráficos basado en álgebra lineal de alto rendimiento en la GPU

Las implementaciones de alto rendimiento de algoritmos de grafos son desafiantes de implementar en nuevo hardware paralelo como las GPUs debido a tres desafíos: (1) la dificultad de crear bloques de construcción de grafos, (2) el desbalance de carga en hardware paralelo, y (3) los problemas de grafos tienen baja intensidad aritmética. Para abordar algunos de estos desafíos, GraphBLAS es un esfuerzo innovador y en curso por parte de la comunidad de análisis de grafos para proponer bloques de construcción basados en álgebra lineal dispersa, lo que permite que los algoritmos de grafos se expresen de manera eficiente, sucinta, componible y portátil. En este documento, examinamos los desafíos de rendimiento de un enfoque basado en álgebra lineal para construir marcos de grafos y describimos nuevos principios de diseño para superar estos cuellos de botella. Entre los nuevos principios de diseño se encuentra la explotación de la escasez de entrada, que permite a los usuarios escribir algoritmos de grafos sin especificar la dirección de empuje y tirón. Explotar la escasez de salida permite a los usuarios indicar al backend qué valores de la salida en una sola computación vectorizada no desean que se calculen. El balanceo de carga es una característica importante para equilibrar el trabajo entre los trabajadores paralelos. Describimos las importantes características de balanceo de carga para manejar grafos con diferentes características. Los principios de diseño descritos en este documento han sido implementados en “GraphBLAST”, el primer marco de gráficos basado en álgebra lineal de alto rendimiento en GPUs NVIDIA que es de código abierto. Los resultados muestran que en una sola GPU, GraphBLAST tiene en promedio al menos un orden de magnitud de aceleración sobre las implementaciones anteriores de GraphBLAS SuiteSparse y GBTL, un rendimiento comparable a los primitivos de GPU más rápidos y los marcos de gráficos en memoria compartida Ligra y Gunrock, y un mejor rendimiento que cualquier otro marco de gráficos en GPU, mientras ofrece un modelo de programación más simple y conciso.