Computing with Time
When extremely low-energy processing is required, the choice of data representation makes a tremendous difference and we have much to learn from nature in this regard. For example the brain seems to use some form of “time-based” representations — encodings where the temporal relationship between spike arrivals carries useful information. This research asks the seemingly simple question: what happens if we try to do computation with values encoded only as times?
While we don’t know how to fully answer to that question yet, our early results are encouraging and point to radically more energy efficient forms of computing. Under “race logic” information is represented as a timing delay, and a set of basic operations: MIN, MAX, ADD-CONSTANT, and INHIBIT describe the basic set of “temporal operators” replacing the AND, OR, NOT, we know and love from digital logic.
MAX: Given two inputs events arriving at time T1 and T2, output at event at time max(T1, T2)
MIN: Given two inputs events arriving at time T1 and T2, output at event at time min(T1, T2)
ADD-CONSTANT: Given one input event arriving at time T, output at event at time T+K for some constant K
INHIBIT: Given an data input arriving at Td and a control input arriving at Tc, output an event at time Td if and only if Td < Tc
The core idea of race logic is to deliberately engineer “race conditions” using these operators where the time it takes to complete a task tell you the answer you are looking for. For example, we have constructed systems where the time it takes for a signal to reach the output tells you how closely related two sequences of DNA are to one another, or how to classify an image from a collection of digits.
Edges as a Proxy for Spikes
An Practical Analog Implementation of Race Logic
Georgios Tzimpragos, Advait Madhavan, Dilip Vasudevan, Dmitri Strukov, and Timothy Sherwood. Boosted Race Trees for Low Energy Classification Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (best paper award) April 2019. Providence, RI
Advait Madhavan, Timothy Sherwood, and Dmitri Strukov. A 4-mm2 180-nm-CMOS 15-Giga-Cell-Updates-per-Second DNA Sequence Alignment Engine Based on Asynchronous Race Conditions IEEE Custom Integrated Circuits Conference (CICC) April 2017. Austin, Tx.
Advait Madhavan, Timothy Sherwood, and Dmitri Strukov. Energy efficient computation with asynchronous races Proceedings of the 53rd Design Automation Conference (DAC) June 2016. Austin, Tx.
Advait Madhavan, Timothy Sherwood, and Dmitri Strukov. Race Logic: Abusing Hardware Race Conditions to Perform Useful Computation, IEEE Micro: Micro's Top Picks from Computer Architecture Conferences (IEEE Micro - top pick), May-June 2015.
Advait Madhavan, Timothy Sherwood, and Dmitri Strukov. Race Logic: A Hardware Acceleration for Dynamic Programming Algorithms Proceedings of the International Symposium of Computer Architecture. (ISCA) June 2014. Minneapolis, Minnesota