Temporal Computing

Summary

The human brain does some types of information processing, like speech recognition, image recognition, or video processing, much more efficiently than can be done with modern computers.  Neuromorphic computing is the field of making computing more efficient by taking inspiration from how the brain works.  There is strong evidence that parts of the brain process information based on the timing of events, like neural spikes.  Standard integrated circuits can be adapted to perform time-based computing to efficiently solve big-data processing and machine learning tasks efficiently.  We are extending time-based computing in important ways by studying new device and memory technologies, exploring new mathematical frameworks and building demonstrations of time-based computing architectures.

Description

Fig. 1. Time re-envisioned: not a by-product of computation, but the domain in which information is encoded, leading to different mathematical functions becoming energy efficient primitives.

In standard integrated circuits, information that is coded as ones and zeros is implemented by voltages on wires being high or low.  The circuits consume energy during transitions between these voltages.  Binary numbers have a voltage per bit so there are a lot of transitions each time a number changes.  In “race logic” information is not encoded in these bits but rather in the time at which a voltage changes from low to high.  This allows more than one bit of information to be encoded on a single wire. Such an approach has lower precision than the usual binary representation of the information but can operate faster, at much lower energy, and with smaller area on the integrated circuit. 

Race logic information consists of wavefronts.  A wavefront is the set of transitions in a series of wires.  The relative arrival times of the transitions can be incremented or decremented with delay elements. Simple logic gates like OR-gates or AND-gates determine which transition arrives first or last.  As the wavefront propagates through the circuit, different parts move faster or slower depending on the information being processed.  The final answer is determined by which signal wins the race, i.e., arrives first.

Fig 2. Race logic for graph traversal: (a-f) show how various simple graph traversal operations can be implemented with tropical algebra; (g-i) show how these tropical operations can be implemented in race logic with an array-based design.

The simplicity of the unit cells makes race logic especially powerful on problems that can be mapped to spatially organized data structures such as graphs or trees. We have studied both options. Decision-tree-based models are useful for making categorical decisions on image data. When accelerated with race logic, they achieve accuracy only a percent below state of the art, at a one- to two-order-of-magnitude lower energy cost.

The application of race logic to problems like graph computations is greatly enhanced because it can be described by a particular, new type of algebra – tropical algebra. Just like race logic, tropical algebra uses MIN and MAX as addition operators and SUM as a multiplicative operator, allowing the mathematic framework of this algebra to be applied to analyze race logic systems.  Simple tropical matrix operations can then be performed by a crossbar architecture of race logic primitives. We have shown that such an architecture can perform graph traversal an order of magnitude faster and with an order of magnitude less energy cost than state-of-the-art non-temporal graph accelerators. 

Fig. 3. Temporal memory with 1T1R crossbar of memristors: with appropriate write and read circuits, the difference in arrival times between various edges can be encoded in the resistance state of a memristor. 

Making race logic useful for solving an even broader class of problems requires a way to store wavefronts, that is, a temporal memory.  Creating such a memory requires transposing the time encoded information into a static, non-volatile encoding.  To achieve this we are pursuing two options.  One approach involves the same memristors that we are exploring for programmable delay elements.  As shown in figure 3, this approach involves using time differences in voltages to create corresponding changes in the resistance of the memristors.  In another approach, we are using the time differences in the voltages to move a magnetic structure in a magnetic wire. Each nanodevice has its own properties such as linearity, noise, area, efficiency and speed that need to be understood before they can be incorporated into temporal memory architectures.

Fig. 4. Experimental demonstration underway: die micrograph of a 10x10 race logic DNA sequence alignment array, with exposed vias ready for post-CMOS memristors.

Race logic not only works well with conventional integrated circuits, but also in novel low temperature computing environments based on superconductors. In such computing approaches, the physical encoding is naturally spike-based and hence lends itself well to temporal coding approaches.  While low- temperature computers are unlikely to be important in consumer electronics, they could play an important role in data centers because they can be much faster and lower energy than existing electronics. We are exploring superconducting circuits that would be needed for such applications.

Other Publications

• G. Tzimpragos, J. Volk, D. Vasudevan, N. Tsiskaridze, G. Michelogiannakis, A. Madhavan, J. Shalf, T. Sherwood, "Temporal Computing With Superconductors," IEEE Micro, vol. 41, no. 3, pp. 71-79, 1 May-June 2021, doi: 10.1109/MM.2021.3066377.
• G. Tzimpragos, D. Vasudevan, N. Tsiskaridze, G. Michelogiannakis, A. Madhavan, J. Volk, J. Shalf, T. Sherwood, "A Computational Temporal Logic for Superconducting Accelerators," ASPLOS '20: Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, March 2020, Pages 435–448, doi: 10.1145/3373376.3378517.
• G. Tzimpragos, A. Madhavan, D. Vasudevan, D. Strukov, T. Sherwood, "Boosted Race Trees for Low Energy Classification," ASPLOS '19: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, April 2019, Pages 215–228, doi: 10.1145/3297858.3304036.