research-article

Computational Complexity of Neuromorphic Algorithms

Authors:

Catherine Schuman,

Thomas PotokAuthors Info & Claims

ICONS 2021: International Conference on Neuromorphic Systems 2021

Article No.: 8, Pages 1 - 7

https://doi.org/10.1145/3477145.3477154

Published: 13 October 2021 Publication History

Abstract

Neuromorphic computing has several characteristics that make it an extremely compelling computing paradigm for post Moore computation. Some of these characteristics include intrinsic parallelism, inherent scalability, collocated processing and memory, and event-driven computation. While these characteristics impart energy efficiency to neuromorphic systems, they do come with their own set of challenges. One of the biggest challenges in neuromorphic computing is to establish the theoretical underpinnings of the computational complexity of neuromorphic algorithms. In this paper, we take the first steps towards defining the space and time complexity of neuromorphic algorithms. Specifically, we describe a model of neuromorphic computation and state the assumptions that govern the computational complexity of neuromorphic algorithms. Next, we present a theoretical framework to define the computational complexity of a neuromorphic algorithm. We explicitly define what space and time complexities mean in the context of neuromorphic algorithms based on our model of neuromorphic computation. Finally, we leverage our approach and define the computational complexities of six neuromorphic algorithms: constant function, successor function, predecessor function, projection function, neuromorphic sorting algorithm and neighborhood subgraph extraction algorithm.

References

[1]

Larry F Abbott. 1999. Lapicque’s introduction of the integrate-and-fire model neuron (1907). Brain research bulletin 50, 5-6 (1999), 303–304.

[2]

James B Aimone, Kathleen E Hamilton, Susan Mniszewski, Leah Reeder, Catherine D Schuman, and William M Severa. 2018. Non-neural network applications for spiking neuromorphic hardware. In Proceedings of the Third International Workshop on Post Moores Era Supercomputing. 24–26.

[3]

James B Aimone, Yang Ho, Ojas Parekh, Cynthia A Phillips, Ali Pinar, William Severa, and Yipu Wang. 2020. Provable Neuromorphic Advantages for Computing Shortest Paths. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 497–499.

Digital Library

[4]

Jérémie Cabessa. 2019. Turing complete neural computation based on synaptic plasticity. PloS one 14, 10 (2019), e0223451.

[5]

Jeremie Cabessa and Hava T Siegelmann. 2014. The super-Turing computational power of plastic recurrent neural networks. International journal of neural systems 24, 08 (2014), 1450029.

[6]

Prasanna Date. 2019. Combinatorial neural network training algorithm for neuromorphic computing. Rensselaer Polytechnic Institute.

[7]

Prasanna Date, Christopher D Carothers, James A Hendler, and Malik Magdon-Ismail. 2018. Efficient classification of supercomputer failures using neuromorphic computing. In 2018 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 242–249.

[8]

Prasanna Date, Christopher D Carothers, John E Mitchell, James A Hendler, and Malik Magdon-Ismail. 2020. Training Deep Neural Networks with Constrained Learning Parameters. In 2020 International Conference on Rebooting Computing (ICRC). IEEE, 107–115.

[9]

Prasanna Date, Catherine Schuman, Bill Kay, and Thomas Potok. 2021. Neuromorphic computing is Turing-complete. arXiv preprint arXiv:2104.13983(2021).

[10]

Gabriel A Fonseca Guerra and Steve B Furber. 2017. Using stochastic spiking neural networks on spinnaker to solve constraint satisfaction problems. Frontiers in neuroscience 11 (2017), 714.

[11]

E Paxon Frady, Garrick Orchard, David Florey, Nabil Imam, Ruokun Liu, Joyesh Mishra, Jonathan Tse, Andreas Wild, Friedrich T Sommer, and Mike Davies. 2020. Neuromorphic Nearest Neighbor Search Using Intel’s Pohoiki Springs. In Proceedings of the Neuro-inspired Computational Elements Workshop. 1–10.

Digital Library

[12]

Kurt Gödel. 1934. On undecidable propositions of formal mathematics systems. Institute for Advanced Study.

[13]

Seonggil Ham, Minji Kang, Seonghoon Jang, Jingon Jang, Sanghyeon Choi, Tae-Wook Kim, and Gunuk Wang. 2020. One-dimensional organic artificial multi-synapses enabling electronic textile neural network for wearable neuromorphic applications. Science Advances 6, 28 (2020), eaba1178.

[14]

Kathleen Hamilton, Prasanna Date, Bill Kay, and Catherine Schuman D. 2020. Modeling epidemic spread with spike-based models. In International Conference on Neuromorphic Systems 2020. 1–5.

Digital Library

[15]

Kathleen Hamilton, Tiffany Mintz, Prasanna Date, and Catherine D Schuman. 2020. Spike-based graph centrality measures. In International Conference on Neuromorphic Systems 2020. 1–8.

Digital Library

[16]

Bill Kay, Prasanna Date, and Catherine Schuman. 2020. Neuromorphic graph algorithms: Extracting longest shortest paths and minimum spanning trees. In Proceedings of the Neuro-inspired Computational Elements Workshop. 1–6.

Digital Library

[17]

Mikhail Kiselev. 2016. Rate coding vs. temporal coding-is optimum between?. In 2016 International Joint Conference on Neural Networks (IJCNN). IEEE, 1355–1359.

[18]

Donald Ervin Knuth. 1997. The art of computer programming. Vol. 3. Pearson Education.

[19]

Johan Kwisthout and Nils Donselaar. 2020. On the computational power and complexity of Spiking Neural Networks. In Proceedings of the Neuro-inspired Computational Elements Workshop. 1–7.

Digital Library

[20]

Louis Lapique. 1907. Recherches quantitatives sur l’excitation electrique des nerfs traitee comme une polarization.Journal of Physiology and Pathololgy 9 (1907), 620–635.

[21]

Qing-Xuan Li, Tian-Yu Wang, Xiao-Lin Wang, Lin Chen, Hao Zhu, Xiao-Han Wu, Qing-Qing Sun, and David Wei Zhang. 2020. Flexible organic field-effect transistor arrays for wearable neuromorphic device applications. Nanoscale 12, 45 (2020), 23150–23158.

[22]

Moritz B Milde, Hermann Blum, Alexander Dietmüller, Dora Sumislawska, Jörg Conradt, Giacomo Indiveri, and Yulia Sandamirskaya. 2017. Obstacle avoidance and target acquisition for robot navigation using a mixed signal analog/digital neuromorphic processing system. Frontiers in neurorobotics 11 (2017), 28.

[23]

J Parker Mitchell, Grant Bruer, Mark E Dean, James S Plank, Garrett S Rose, and Catherine D Schuman. 2017. NeoN: Neuromorphic control for autonomous robotic navigation. In 2017 IEEE International Symposium on Robotics and Intelligent Sensors (IRIS). IEEE, 136–142.

[24]

Zihan Pan, Jibin Wu, Malu Zhang, Haizhou Li, and Yansong Chua. 2019. Neural population coding for effective temporal classification. In 2019 International Joint Conference on Neural Networks (IJCNN). IEEE, 1–8.

[25]

Kicheol Park, Yena Lee, Jiman Hong, Jae-Hoon An, and Bongjae Kim. 2020. Selecting a Proper Neuromorphic Platform for the Intelligent IoT. In Proceedings of the International Conference on Research in Adaptive and Convergent Systems. 255–260.

Digital Library

[26]

Catherine D Schuman, Kathleen Hamilton, Tiffany Mintz, Md Musabbir Adnan, Bon Woong Ku, Sung-Kyu Lim, and Garrett S Rose. 2019. Shortest path and neighborhood subgraph extraction on a spiking memristive neuromorphic implementation. In Proceedings of the 7th Annual Neuro-inspired Computational Elements Workshop. 1–6.

Digital Library

[27]

Catherine D Schuman, J Parker Mitchell, Robert M Patton, Thomas E Potok, and James S Plank. 2020. Evolutionary optimization for neuromorphic systems. In Proceedings of the Neuro-inspired Computational Elements Workshop. 1–9.

Digital Library

[28]

Catherine D Schuman, James S Plank, Grant Bruer, and Jeremy Anantharaj. 2019. Non-traditional input encoding schemes for spiking neuromorphic systems. In 2019 International Joint Conference on Neural Networks (IJCNN). IEEE, 1–10.

[29]

Hava T Siegelmann. 2003. Neural and super-Turing computing. Minds and Machines 13, 1 (2003), 103–114.

Digital Library

[30]

J Darby Smith, William Severa, Aaron J Hill, Leah Reeder, Brian Franke, Richard B Lehoucq, Ojas D Parekh, and James B Aimone. 2020. Solving a steady-state PDE using spiking networks and neuromorphic hardware. In International Conference on Neuromorphic Systems 2020. 1–8.

Digital Library

[31]

Peter Smith. 2013. An introduction to Gödel’s theorems. Cambridge University Press.

[32]

Jeffrey S Vetter, Erik P DeBenedictis, and Thomas M Conte. 2017. Architectures for the post-Moore era. IEEE Annals of the History of Computing 37, 04 (2017), 6–8.

[33]

Chris Yakopcic, Nayim Rahman, Tanvir Atahary, Tarek M Taha, and Scott Douglass. 2020. Solving constraint satisfaction problems using the loihi spiking neuromorphic processor. In 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 1079–1084.

Cited By

Raikar AAndrew JDessai PPrabhu SJathar SPrabhu ANaik MRaikar G(2024)Neuromorphic computing for modeling neurological and psychiatric disorders: implications for drug developmentArtificial Intelligence Review10.1007/s10462-024-10948-357:12Online publication date: 10-Oct-2024
https://doi.org/10.1007/s10462-024-10948-3
Vetter JDate PFahim FKulkarni SMaksymovych PTalin ATallada MVanna-iampikul PYoung ABrooks DCao YGu-Yeon WLim SLiu FMarinella MSumpter BMiniskar N(2023)Abisko: Deep codesign of an architecture for spiking neural networks using novel neuromorphic materialsThe International Journal of High Performance Computing Applications10.1177/1094342023117853737:3-4(351-379)Online publication date: 22-Jun-2023
https://doi.org/10.1177/10943420231178537
Maheshwari DYoung ADate PKulkarni SWitherspoon BMiniskar N(2023)An FPGA-Based Neuromorphic Processor with All-to-All Connectivity2023 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC60800.2023.10386808(1-5)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICRC60800.2023.10386808
Show More Cited By

Recommendations

Neuromorphic Computing is Turing-Complete
ICONS '22: Proceedings of the International Conference on Neuromorphic Systems 2022

Neuromorphic computing is a non-von Neumann computing paradigm that performs computation by emulating the human brain. Neuromorphic systems are extremely energy-efficient and known to consume thousands of times less power than CPUs and GPUs. They have ...
Effects of Noise on Leaky Integrate-and-Fire Neuron Models for Neuromorphic Computing Applications
Computational Science and Its Applications – ICCSA 2022
Abstract
Artificial neural networks (ANNs) have been extensively used for the description of problems arising from biological systems and for constructing neuromorphic computing models. The third generation of ANNs, namely, spiking neural networks (SNNs), ...
Introducing Astrocytes on a Neuromorphic Processor: Synchronization, Local Plasticity and Edge of Chaos
NICE '19: Proceedings of the 7th Annual Neuro-inspired Computational Elements Workshop

While there is still a lot to learn about astrocytes and their neuromodulatory role in the spatial and temporal integration of neuronal activity, their introduction to neuromorphic hardware is timely, facilitating their computational exploration in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICONS 2021: International Conference on Neuromorphic Systems 2021

July 2021

198 pages

ISBN:9781450386913

DOI:10.1145/3477145

Editors:
Thomas E. Potok
Oak Ridge National Laboratory
,
Melika Payvand
ETH Zurich
,
Catherine Schuman
Oak Ridge National Laboratory
,
Prasanna Date
Oak Ridge National Laboratory
,
Mutsumi Kimura
Nara Institute of Science and Technology
,
Cory Merkel
Rochester Institute of Technology
,
Brad Aimone
Sandia National Laboratories
,
Sonia Buckley
National Institute of Standards and Technology
,
Yiran Chen
Duke University
,
Gregory Cohen
Western Sydney University
,
Todd Hylton
University of California, San Diego
,
Mutsumi Kimura
Ryukoku University, Japan
,
Robert Patton
Oak Ridge National Laboratory
,
Melika Payvand
ETH Zurich
,
Robinson Pino
U.S. Department of Energy
,
Thomas Potok
Oak Ridge National Laboratory
,
Garrett Rose
University of Tennessee, Knoxville

Copyright © 2021 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 October 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICONS 2021

ICONS 2021: International Conference on Neuromorphic Systems 2021

July 27 - 29, 2021

TN, Knoxville, USA

Acceptance Rates

Overall Acceptance Rate 13 of 22 submissions, 59%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)13

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Raikar AAndrew JDessai PPrabhu SJathar SPrabhu ANaik MRaikar G(2024)Neuromorphic computing for modeling neurological and psychiatric disorders: implications for drug developmentArtificial Intelligence Review10.1007/s10462-024-10948-357:12Online publication date: 10-Oct-2024
https://doi.org/10.1007/s10462-024-10948-3
Vetter JDate PFahim FKulkarni SMaksymovych PTalin ATallada MVanna-iampikul PYoung ABrooks DCao YGu-Yeon WLim SLiu FMarinella MSumpter BMiniskar N(2023)Abisko: Deep codesign of an architecture for spiking neural networks using novel neuromorphic materialsThe International Journal of High Performance Computing Applications10.1177/1094342023117853737:3-4(351-379)Online publication date: 22-Jun-2023
https://doi.org/10.1177/10943420231178537
Maheshwari DYoung ADate PKulkarni SWitherspoon BMiniskar N(2023)An FPGA-Based Neuromorphic Processor with All-to-All Connectivity2023 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC60800.2023.10386808(1-5)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICRC60800.2023.10386808
Wurm ASeay RDate PKulkarni SYoung AVetter J(2023)Arithmetic Primitives for Efficient Neuromorphic Computing2023 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC60800.2023.10386397(1-5)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICRC60800.2023.10386397
Date PKulkarni SYoung ASchuman CPotok TVetter J(2023)Encoding integers and rationals on neuromorphic computers using virtual neuronScientific Reports10.1038/s41598-023-35005-x13:1Online publication date: 6-Jul-2023
https://doi.org/10.1038/s41598-023-35005-x
Patton RDate PKulkarni SGunaratne CLim SCong GYoung SColetti MPotok TSchuman C(2022)Neuromorphic Computing for Scientific Applications2022 IEEE/ACM Redefining Scalability for Diversely Heterogeneous Architectures Workshop (RSDHA)10.1109/RSDHA56811.2022.00008(22-28)Online publication date: Nov-2022
https://doi.org/10.1109/RSDHA56811.2022.00008
Date PKulkarni SYoung ASchuman CPotok TVetter J(2022)Virtual Neuron: A Neuromorphic Approach for Encoding Numbers2022 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC57508.2022.00017(100-105)Online publication date: Dec-2022
https://doi.org/10.1109/ICRC57508.2022.00017

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents