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

A flow network
2021: Q3

Significance and Impact

With the end of Moore's Law approaching, the ever-increasing demand for more computing power is beginning to out pace our ability to keep up from a hardware point of view. Neuromorphic computing is a promising computing paradigm for future computing systems due to its extremely low power usage and inherent parallelism. While many of the most popular use-cases for neuromorphic systems involve control tasks and machine learning, we focus on one aspect of a neuromorphic processor as a co-processing unit for future HPC systems. Namely, one of the largest barriers to building larger HPC systems than we see today is power consumption. Under the hood of HPC systems are a myriad of graph and combinatorial algorithms such as sorting, routing, and communication protocols. Here, we develop neuromorphic implementations of three classical graph algorithms to lay the groundwork for more sophisticated graph computing on neuromorphic systems in coming years in hopes that many of the routine computing tasks "under the hood" of HPC systems could be offloaded to a low-power, highly parallel neuromorphic processing unit allowing for larger systems with lower energy costs. 

Research Details

A paper where the authors developed neuromorphic version of graph algorithms which, on input of a graph G will determine if the graph has any cycles (i.e., is a tree), if a graph has any odd cycles (i.e., is bipartite), and of the Ford-Fulkerson algorithm for determining the maximum flow. The first two algorithms are elementary, but the neuromorphic implementations were non-trivial. Further, the Ford-Fulkerson algorithm requires several neuromorphic runs and leans on an interplay between neuromorphic and traditional compute.

The paper concludes with a deployment of each neuromorphic algorithm on large test graphs using the NEural Simulation Tool (NEST). The spike counts for each algorithm were used as a proxy for power consumption, and shown to run with lower power consumption than a run of a 'traditional' algorithm for testing each graph property. The work is a step in the direction of developing graph algorithms which can be deployed neuromorphically to unload many of the sorting, searching, and communications algorithms under the hood of HPC in an attempt to lower the energy consumption cost for future systems. 

Last Updated: August 12, 2021 - 9:27 pm