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.
Original language | English |
---|---|
Title of host publication | ICONS 2021 - Proceedings of International Conference on Neuromorphic Systems 2021 |
Publisher | Association for Computing Machinery |
ISBN (Electronic) | 9781450386913 |
DOIs | |
State | Published - Jul 27 2021 |
Event | 2021 International Conference on Neuromorphic Systems, ICONS 2021 - Virtual, Onlie, United States Duration: Jul 27 2021 → Jul 29 2021 |
Publication series
Name | ACM International Conference Proceeding Series |
---|
Conference
Conference | 2021 International Conference on Neuromorphic Systems, ICONS 2021 |
---|---|
Country/Territory | United States |
City | Virtual, Onlie |
Period | 07/27/21 → 07/29/21 |
Funding
This manuscript has been authored in part by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, under contract number DE-AC05-00OR22725.
Keywords
- Computability and Complexity
- Computational Complexity
- Neuromorphic Algorithms
- Neuromorphic Computing