Prasanna Date, Bill Kay, Catherine Schuman, Robert Patton and Thomas Potok

July, 2021

ICONS: International Conference on Neuromorphic Systems

https://doi.org/10.1145/3477145.3477154

PDF not available yet, or is only available from the conference/journal publisher.

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.

Citation Information

Text

author       P. Date and B. Kay and C. D. Schuman and R. Patton and T. Potok
title        Computational Complexity of Neuromorphic Algorithms
booktitle    International Conference on Neuromorphic Computing Systems (ICONS)
publisher    ACM
pages        1-7
year         2021
url          https://doi.org/10.1145/3477145.3477154
doi          10.1145/3477145.3477154

Bibtex

@INPROCEEDINGS{dks:21:ccn,
    author = "P. Date and B. Kay and C. D. Schuman and R. Patton and T. Potok",
    title = "Computational Complexity of Neuromorphic Algorithms",
    booktitle = "International Conference on Neuromorphic Computing Systems (ICONS)",
    publisher = "ACM",
    pages = "1-7",
    year = "2021",
    url = "https://doi.org/10.1145/3477145.3477154",
    doi = "10.1145/3477145.3477154"
}