Temporal State Machines: Using temporal memory to stitch time-based graph computations

Published

May 11, 2021

Author(s)

Advait Madhavan, Matthew Daniels, Mark D. Stiles

Abstract

Race logic, an arrival-time-coded logic family, has demonstrated energy and performance improvements for a subset of applications ranging from dynamic programming to machine learning. In the absence of memory, or a mathematical framework for abstraction and composition, previous race logic demonstrations used ad hoc mappings of algorithms into hardware. These restricted architectures, assembled from stateless, spatially arranged feed-forward paths, do not lend themselves to generalization. In order to systematize the development of temporally coded architectures, we associate race logic with the mathematical field tropical algebra. This association performs two functions. It provides a mapping between the mathematical primitives of tropical algebra and generalized race logic computations, guiding the design of temporally coded tropical circuits. It also serves as a useful framework for the expression of higher order timing-based algorithms. This abstraction, when combined with a natively temporal memory, makes it possible to partition feed- forward computations into stages and organize them into a state machine. We leverage analog memristor-based temporal memories to design a such a temporal state machine that operates purely on time-coded wavefronts. We implement a version of the well-studied Dijkstra's algorithm to evaluate this temporal state machine. This demonstration shows the promise of temporal computing to deliver significant energy and throughput advantages.

Citation

ACM Journal on Emerging Technologies in Computing Systems

Volume

17

Issue

3

Pub Type

Journals

Download Paper

https://doi.org/10.1145/3451214

Local Download

Keywords

Temporal Computing, Race Logic, Tropical Algebra, Graph Processing, Neuromorphic Computing

Citation

Madhavan, A. , Daniels, M. and Stiles, M. (2021), Temporal State Machines: Using temporal memory to stitch time-based graph computations, ACM Journal on Emerging Technologies in Computing Systems, [online], https://doi.org/10.1145/3451214, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=931074 (Accessed April 19, 2024)