Road to scalability for efficient graph search on massively parallel neuromorphic hardware

Resumen Técnico: Camino hacia la Escalabilidad para la Búsqueda de Grafos Eficiente en Hardware Neuromórfico Masivamente Paralelo

Planteamiento del Problema
El cálculo de rutas mínimas en grafos ponderados es un problema fundamental con aplicaciones críticas en la planificación de rutas, el enrutamiento de redes, la planificación de acciones robóticas y la reducción de dimensionalidad no lineal (por ejemplo, Isomap). Aunque los algoritmos secuenciales establecidos como el algoritmo de Dijkstra son efectivos en hardware convencional, enfrentan desafíos de escalabilidad y eficiencia energética cuando se aplican a grafos de gran escala o entornos multiusuario. Los enfoques paralelos existentes para GPUs y CPUs suelen depender de mecanismos de coordinación global que resultan costosos en arquitecturas distribuidas o basadas en eventos. El hardware neuromórfico, caracterizado por la computación y memoria co-localizadas y la comunicación basada en eventos, ofrece una solución potencial, pero requiere algoritmos que minimicen la sincronización global para aprovechar sus fortalezas inherentes.

Metodología: NEURO-MAPP
Los autores presentan NEURO-MAPP (Propagación Paralela de Min-Add basada en Neuromorfismo), un algoritmo de ruta mínima distribuido diseñado específicamente para sistemas neuromórficos. El concepto central implica embeber un grafo ponderado en un grafo computacional donde:

• Operaciones Locales: Los vértices realizan una minimización local sobre las señales de distancia entrantes para seleccionar la distancia candidata más pequeña.
• Operaciones de Aristas: Las aristas propagan las actualizaciones de distancia sumando sus pesos asociados a la señal entrante.
• Dinámica: Las rutas mínimas emergen a través de dinámicas de actualización puramente locales y paralelas sin requerir coordinación global.

El algoritmo fue implementado en la plataforma SpiNNaker 2, un sistema neuromórfico masivamente paralelo que cuenta con 152 núcleos ARM por chip, cada uno con SRAM dedicada y conectados mediante una red de interconexión (NoC) de baja latencia. Las estrategias clave de implementación incluyeron:

1. Partición de Vértices: Para abordar los desequilibrios de carga causados por distribuciones de grado sesgadas (por ejemplo, "hubs" en redes de proteínas), los autores desarrollaron una estrategia de partición consciente del grado del vértice. Esta asigna vértices a los núcleos para minimizar el grado acumulado por núcleo, evitando cuellos de botella. Para otros tipos de grafos, se utilizaron asignaciones aleatorias o de minimización de ancho de banda.
2. Optimización del Paso de Mensajes: Se compararon dos métodos para codificar las actualizaciones de distancia. Un enfoque basado en "predecesores", que almacena las aristas salientes directamente en el núcleo de origen y realiza búsquedas de tiempo constante, resultó ser significativamente superior al enfoque por defecto basado en "sucesores" (que requiere búsqueda binaria en las aristas entrantes) para grafos dispersos y de alta conectividad, reduciendo el tiempo de búsqueda hasta en un factor de 10.
3. Programación de Iteración Dinámica: Para mitigar el tiempo de inactividad causado por cargas de trabajo variables entre los núcleos, se implementó un coordinador global ligero. Los núcleos señalan la finalización a un programador, el cual dispara la siguiente iteración solo cuando todos los núcleos están listos, asegurando la sincronización sin pasos de tiempo fijos y de desperdicio.

Resultos Clave
El rendimiento de NEURO-MAPP en un solo chip SpiNNaker 2 se evaluó frente al algoritmo de Dijkstra en un CPU moderno (M1 Pro) a través de tipos de grafos sintéticos y del mundo real:

• Escalabilidad y Tiempo de Ejecución:

  • Grafos Aleatorios y de Mundo Pequeño (Small-World): NEURO-MAPP demostró una escalabilidad superior. Mientras que el algoritmo de Dijkstra funcionó mejor en grafos pequeños, el tiempo de ejecución de NEURO-MAPP creció logarítmicamente con el tamaño del grafo, superando a Dijkstra para grafos que exceden los ~30,000–38,000 vértices.
  • Grafos de Rejilla (Grid Graphs): Para grafos de rejilla 3D, el algoritmo de Dijkstra siguió siendo más rápido debido al mayor diámetro de estos grafos, lo que requiere más iteraciones para NEURO-MAPP. Sin embargo, para rejillas de mayor dimensión (por ejemplo, 5D), NEURO-MAPP mostró una ventaja de tiempo de ejecución de aproximadamente un 20%.
  • Aplicaciones del Mundo Real: En navegación aérea 3D (entorno urbano tipo Manhattan), NEURO-MAPP resolvió el problema en 6.1 ms frente a los 6.8 ms de Dijkstra. Por el contrario, para la navegación de redes viales (distritos alemanes), NEURO-MAPP fue actualmente más lento (por un orden de magnitud) debido a la topología específica y al tamaño de las redes probadas, aunque los autores proyectan que superará a Dijkstra en escalas mayores.
  • Redes de Interacción de Proteínas: A pesar de tiempos de ejecución más largos en los tamaños de red actuales, NEURO-MAPP mostró tendencias favorables para redes más grandes con topologías similares.

• Eficiencia Energética:

  • En todos los tipos de grafos probados, NEURO-MAPP consumió significativamente menos energía por consulta de ruta mínima que la implementación en CPU.
  • El chip SpiNNaker 2 consumió menos de 500 mW durante la ejecución, en comparación con los aproximadamente 4 W del CPU. Incluso en casos donde NEURO-MAPP tuvo un tiempo de ejecución más largo, la menor potencia de consumo resultó en un menor consumo de energía total (por ejemplo, 2.4 mJ frente a 25.5 mJ para la tarea de navegación aérea).

• Integración con Isomap:

  • Los autores integraron NEURO-MAPP en el marco de reducción de dimensionalidad Isomap para calcular la matriz de todos los pares de rutas mínimas (APSP). NEURO-MAPP demostró un rendimiento superior para conjuntos de datos más grandes y un mayor número de vecinos cercanos ($k$), validando su utilidad como componente en procesos algorítmicos más amplios.

Significancia y Reivindicaciones
El artículo afirma que NEURO-MAPP demuestra el potencial del hardware neuromórfico, que presenta comunicación dispersa basada en pulsos (spikes), como una plataforma escalable y eficiente energéticamente para la búsqueda de grafos. Los autores enfatizan que, aunque comparar un algoritmo secuencial de un solo núcleo con un sistema masivamente paralelo pueda parecer injusto, la métrica de interés es el tiempo de ejecución total y la energía requerida para completar una tarea.

Las principales reivindicaciones incluyen:

1. Eficiencia Energética: El hardware neuromórfico puede resolver problemas de ruta mínima con un consumo de energía significativamente menor que las implementaciones en CPU convencionales, incluso cuando el algoritmo paralelo aún no es el más rápido en tiempo de ejecución absoluto para todos los tamaños de grafos.
2. Escalabilidad: El algoritmo escala favorablemente para familias de grafos con diámetros bajos (aleatorios, de mundo pequeño, rejillas de alta dimensión), lo que sugiere que los sistemas neuromórficos de múltiples chips podrían resolver problemas actualmente intratables para aplicaciones con restricciones de energía.
3. Agnosticismo de Hardware: Aunque se implementó en SpiNNaker 2, los autores señalan que el algoritmo es aplicable a cualquier sistema con suficientes unidades paralelas independientes, memoria local y comunicación de baja latencia, incluyendo otras plataformas neuromórficas como Loihi 2 o Graphcore IPUs.

Los autores mantienen la modestia respecto a las limitaciones actuales, reconociendo que para tipos de grafos específicos (como las redes viales 2D) y las restricciones actuales de un solo chip, el algoritmo de Dijkstra sigue siendo más rápido. Sin embargo, postulan que las ventajas energéticas y las tendencias de escalabilidad logarítmica indican un camino claro hacia un rendimiento superior en sistemas neuromórficos de múltiples chips de mayor escala.