Aceleración del camino más corto de origen único a gran escala en FPGA

Muchos problemas del mundo real pueden representarse como gráficos y resolverse mediante algoritmos de recorrido de gráficos. El camino más corto de origen único (SSSP) es un algoritmo fundamental en gráficos. Hoy en día, los gráficos a gran escala implican millones o incluso miles de millones de vértices, lo que hace que el procesamiento paralelo eficiente de gráficos sea un desafío. En este documento, proponemos un diseño basado en un solo FPGA para acelerar SSSP para gráficos masivos. Adoptamos el conocido algoritmo de Bellman-Ford. En el diseño propuesto, el gráfico se almacena en memoria externa, lo que es más realista para el procesamiento de gráficos a gran escala. Utilizando el ancho de banda de memoria externa disponible, nuestro diseño logra el máximo paralelismo de datos para procesar múltiples aristas en cada ciclo de reloj, independientemente de las dependencias de datos. El rendimiento de nuestro diseño también es independiente de la estructura del gráfico. Proponemos un diseño de datos optimizado para permitir una utilización eficiente del ancho de banda de memoria externa. Prototipamos nuestro diseño utilizando un FPGA de última generación. Los resultados experimentales muestran que nuestro diseño es capaz de procesar 1.6 mil millones de aristas por segundo (GTEPS) utilizando un solo FPGA, mientras que simultáneamente logra una alta frecuencia de reloj de más de 200 MHz. Esto nos situaría en la posición 131 de la lista de referencia Graph 500 de sistemas de supercomputación para aplicaciones intensivas en datos. Por lo tanto, nuestra solución proporciona un rendimiento comparable a los sistemas de última generación.