Race Logic: A Hardware Acceleration for Dynamic Programming Algorithms

摘要

We propose a novel computing approach, dubbed "Race Logic", in which information, instead of being represented as logic levels, as is done in conventional logic, is represented as a timing delay. Under this new information representation, computations can be performed by observing the relative propagation times of signals injected into the circuit (i.e. the outcome of races). Race Logic is especially suited for solving problems related to the traversal of directed acyclic graphs commonly used in dynamic programming algorithms. The main advantage of this novel approach is that information processing (minmax and addition operations) can be very efficiently expressed through the manipulation of the natural delay chaining inherent to digital designs, which then results in superior latency, throughput, and energy efficiency. To verify this hypothesis, we designed several Race Logic implementations of a DNA global sequence alignment engine and compared it to the state-of-the-art conventional systolic array implementation. Our synthesized design shows that synchronous Race Logic is up to 4 x faster when both approaches are mapped to a 0.5μm CMOS standard cell technology. At the same time the throughput for sequence matching per circuit area is about 3x higher at 5× lower power density for 20-long-symbol DNA sequences.