Highlight

Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees

Achievement

A team of researchers at Oak Ridge National Laboratory (ORNL) had a paper accepted to the Neuro-Inspired Computational Elements (NICE) conference in Heidelberg, Germany.  The work demonstrates how graph algorithms are deployable on neuromorphic systems, which allows for a low energy, highly resilient implementation of graph algorithms. As proof of concept, two classical algorithms for extracting the longest shortest path and a minimum spanning tree. Notably, the algorithms improve on previous results by introducing fractional offsets to spiking thresholds to ensure that no two neurons spike at the same time. The presentation of this work has been delayed due to the COVID-19 pandemic, but the work was accepted for both a presentation and a poster at NICE 2020.

Significance and Impact

This work demonstrates an alternative use case for neuromorphic computing. Given the underlying graph infrastructure, neuromorphic systems are ideal for implementing and executing graph algorithms. This work provides another example of the robustness and diversity of applications of neuromorphic computing beyond the scope of deep learning.

Research Details

  • Researchers demonstrate how fractional offsets can be applied to spiking neural networks to prevent pairs of neurons from firing simultaneously. 
  • Given the set of distinct firing times, several graph algorithms (Longest Shortest Path extraction and Prim’s algorithm for extracting minimum spanning tree) become possible.
  • Researchers demonstrate that neuromorphic architecture can be used to implement classical graph algorithms with low energy output in an intrinsically parallel setting.

Citation and DOI

Bill Kay, Prasanna Date, Catherine D. Schuman "Neuromorphic Graph Algorithms: Extracting Longest Shortest Path and Minimum Spanning Tree." Neuromorphic-Inspired Computational Elements (NICE) Workshop 2020.

Overview

Neuromorphic architectures provide a low energy and highly parallelized framework for many tasks. In this document we demonstrate that neuromorphic computing systems can be used to deploy classical algorithms when one introduces a fractional firing time offset to prevent neurons from spiking simultaneously. Previously, simultaneous firing times proved to be an obstruction from implementation of many algorithms.

Last Updated: May 28, 2020 - 4:01 pm