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

Resumo Técnico: O Caminho para a Escalabilidade na Busca Eficiente em Grafos em Hardware Neuromórfico Massivamente Paralelo

Definição do Problema
O cálculo de caminhos mínimos em grafos ponderados é um problema fundamental com aplicações críticas em planejamento de rotas, roteamento de rede, planejamento de ação robótica e redução de dimensionalidade não linear (ex: Isomap). Embora algoritmos sequenciais estabelecidos como o algoritmo de Dijkstra sejam eficazes em hardware convencional, eles enfrentam desafios de escalabilidade e eficiência energética quando aplicados a grafos de grande escala ou ambientes multiusuário. As abordagens paralelas existentes para GPUs e CPUs frequentemente dependem de mecanismos de coordenação global que são dispendiosos em arquiteturas distribuídas ou baseadas em eventos. O hardware neuromórfico, caracterizado por computação e memória co-localizadas e comunicação baseada em eventos, oferece uma solução potencial, mas requer algoritmos que minimizem a sincronização global para aproveitar suas forças inerentes.

Metodologia: NEURO-MAPP
Os autores introduzem o NEURO-MAPP (Propagação Paralela de Adição Mínima Baseada em Neuromórficos), um algoritmo de caminho mínimo distribuído projetado especificamente para sistemas neuromórficos. O conceito central envolve a incorporação de um grafo ponderado em um grafo computacional onde:

• Operações Locais: Os vértices realizam a minimização local sobre os sinais de distância de entrada para selecionar a menor distância candidata.
• Operações de Aresta: As arestas propagam atualizações de distância adicionando seus pesos associados ao sinal de entrada.
• Dinâmica: Os caminhos mínimos emergem através de dinâmicas de atualização puramente locais e paralelas, sem a necessidade de coordenação global.

O algoritmo foi implementado na plataforma SpiNNaker 2, um sistema neuromórfico massivamente paralelo que apresenta 152 núcleos ARM por chip, cada um com SRAM dedicada e conectados via uma rede no chip (NoC) de baixa latência. As principais estratégias de implementação incluíram:

1. Particionamento de Vértices: Para lidar com desequilíbrios de carga causados por distribuições de graus assimétricos (ex: "hubs" em redes de proteínas), os autores desenvolveram uma estratégia de particionamento consciente do grau do vértice. Isso atribui vértices a núcleos para minimizar o grau cumulativo por núcleo, evitando gargalos. Para outros tipos de grafos, foram utilizadas atribuições aleatórias ou de minimização de largura de banda.
2. Otimização de Passagem de Mensagens: Dois métodos para codificar atualizações de distância foram comparados. Uma abordagem "baseada em predecessor", que armazena as arestas de saída diretamente no núcleo de origem e realiza buscas de tempo constante, mostrou-se significativamente superior à abordagem padrão "baseada em sucessor" (que requer busca binária em arestas de entrada) para grafos esparsos e de alta conectividade, reduzindo o tempo de busca em até um fator de 10.
3. Escalonamento de Iteração Dinâmico: Para mitigar o tempo de ociosidade causado por cargas de trabalho variáveis entre os núcleos, um coordenador global leve foi implementado. Os núcleos sinalizam a conclusão a um escalonador, que aciona a próxima iteração apenas quando todos os núcleos estão prontos, garantindo a sincronização sem etapas de tempo fixas e dispendiosas.

Resultos Principais
O desempenho do NEURO-MAPP em um único chip SpiNNaker 2 foi avaliado contra o algoritmo de Dijkstra em uma CPU moderna (M1 Pro) através de tipos de grafos sintéticos e do mundo real:

• Escalabilidade e Tempo de Execução:

  • Grafos Aleatórios e de Mundo Pequeno (Small-World): O NEURO-MAPP demonstrou uma escalabilidade superior. Enquanto o algoritmo de Dijkstra teve um desempenho melhor em grafos pequenos, o tempo de execução do NEURO-MAPP cresceu logaritmicamente com o tamanho do grafo, superando o Dijkstra para grafos excedendo ~30.000–38.000 vértices.
  • Grafos de Grade (Grid): Para grafos de grade 3D, o algoritmo de Dijkstra permaneceu mais rápido devido ao maior diâmetro desses grafos, que exige mais iterações para o NEURO-MAPP. No entanto, para grades de dimensões mais altas (ex: 5D), o NEURO-MAPP mostrou uma vantagem de tempo de execução de ~20%.
  • Aplicações do Mundo Real: Em navegação aérea 3D (ambiente urbano Manhattan), o NEURO-MAPP resolveu o problema em 6,1 ms comparado aos 6,8 ms do Dijkstra. Por outro vez, para navegação em redes rodoviárias (distritos alemães), o NEURO-MAPP foi atualmente mais lento (por uma ordem de magnitude) devido à topologia específica e ao tamanho das redes testadas, embora os autores projetem que ele superará o Dijkstra em escalas maiores.
  • Redes de Interação de Proteínas: Apesar de tempos de execução mais longos em tamanhos de rede atuais, o NEURO-MAPP mostrou tendências favoráveis para redes maiores com topologias semelhantes.

• Eficiência Energética:

  • Em todos os tipos de grafos testados, o NEURO-MAPP consumiu significativamente menos energia por consulta de caminho mínimo do que a implementação em CPU.
  • O chip SpiNNaker 2 consumiu menos de 500 mW durante a execução, comparado a aproximadamente 4 W da CPU. Mesmo nos casos em que o NEURO-MAPP teve um tempo de execução mais longo, o menor consumo de potência resultou em menor consumo de energia total (ex: 2,4 mJ vs. 25,5 mJ para a tarefa de navegação aérea).

• Integração com Isomap:

  • Os autores integraram o NEURO-MAPP ao framework de redução de dimensionalidade Isomap para calcular a matriz de todos os pares de caminhos mínimos (APSP). O NEURO-MAPP demonstrou desempenho superior para conjuntos de dados maiores e maior número de vizinhos próximos ($k$), validando sua utilidade como um componente em pipelines algorítmicos maiores.

Significância e Alegações
O artigo afirma que o NEURO-MAPP demonstra o potencial do hardware neuromórfico, que possui comunicação esparsa baseada em spikes, como uma plataforma escalável e energeticamente eficiente para busca em grafos. Os autores enfatizam que, embora comparar um algoritmo sequencial de núcleo único com um sistema massivamente paralelo possa parecer injusto, a métrica de interesse é o tempo de execução total e a energia necessária para completar uma tarefa.

As principais alegações incluem:

1. Eficiência Energética: O hardware neuromórfico pode resolver problemas de caminho mínimo com significativamente menor consumo de energia do que as CPUs convencionais, mesmo quando o algoritmo paralelo ainda não é o mais rápido em tempo de execução absoluto para todos os tamanhos de grafos.
2. Escalabilidade: O algoritmo escala favoravelmente para famílias de grafos com baixos diâmetros (aleatórios, mundo pequeno, grades de alta dimensão), sugerindo que sistemas neuromórficos de múltiplos chips poderiam resolver problemas atualmente intratáveis para aplicações com restrição de energia.
3. Agnosticismo de Hardware: Embora implementado no SpiNNaker 2, os autores observam que o algoritmo é aplicável a qualquer sistema com unidades paralelas independentes suficientes, memória local e comunicação de baixa latência, incluindo outras plataformas neuromórficas como Loihi 2 ou Graphcore IPUs.

Os autores permanecem modestos quanto às limitações atuais, reconhecendo que, para tipos específicos de grafos (como redes rodoviárias 2D) e restrições atuais de um único chip, o algoritmo de Dijkstra permanece mais rápido. No entanto, eles postulam que as vantagens energéticas e as tendências de escalabilidade logarítmica indicam um caminho claro para um desempenho superior em sistemas neuromórficos de múltiplos chips de maior escala.