Search NASA⌕ Search

DOE OSTI · 1873836

Neuromorphic Graph Algorithms: Cycle Detection, Odd Cycle Detection, and Max Flow

Abstract

Neuromorphic computing is poised to become a promising computing paradigm in the post Moore’s law era due to its extremely low power usage and inherent parallelism. Spiking neural networks are the traditional use case for neuromorphic systems, and have proven to be highly effective at machine learning tasks such as control problems. More recently, neuromorphic systems have been applied outside of the arena of machine learning, primarily in the field of graph algorithms. Neuromorphic systems have been shown to perform graph algorithms faster and with lower power consumption than their traditional (GPU/CPU) counterparts, and are hence an attractive option for a co-processing unit in future high performance computing systems, where graph algorithms play a critical role. In this paper, we present a neuromorphic implementation of cycle detection, odd cycle detection, and the Ford-Fulkerson max-flow algorithm. We further evaluate the performance of these implementations using the NEST neuromorphic simulator by using spike counts and simulation time as proxies for energy consumption and run time. In addition to gains inherent in neuromorphic systems, we show that within the neuromorphic implementations early stopping criteria can be implemented to further improve performance.

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Kay, Bill, Schuman, Catherine, O'Connor, Jade, Date, Prasanna, Potok, Thomas. 2021-10-01. Neuromorphic Graph Algorithms: Cycle Detection, Odd Cycle Detection, and Max Flow. https://doi.org/10.1145/3477145.3477172. https://searchnasa.com/record/osti%3A1873836/neuromorphic-graph-algorithms-cycle-detection-odd-cycle-detection-and-max-flow

Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.