Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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

Keywords

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

Citation

Madhavan, A. , Daniels, M. and , 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 September 22, 2021)
Created May 11, 2021, Updated May 19, 2021