Skip to main content

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

by William W Kay, Catherine D Schuman, Jade O'connor, Prasanna A Date, Thomas E Potok
Publication Type
Conference Paper
Journal Name
ICONS '21 Proceedings of the International Conference on Neuromorphic Systems
Book Title
ICONS 2021: International Conference on Neuromorphic Systems 2021
Publication Date
Page Number
Publisher Location
New York, United States of America
Conference Name
ICONS 2021: International Conference on Neuromorphic Systems 2021
Conference Location
Knoxville, Tennessee, United States of America
Conference Sponsor
Oak Ridge National Laboratory
Conference Date

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.