Professor
Department of Computer Science
Department of Electrical Engineering
Columbia University, New York, NY, USA

 

 

Webpage

Optimization of Robust Asynchronous Threshold Networks Using Local Relaxation Techniques

Friday, 11 December 2015 at 9:40 in room BC 420

 

Abstract:

As process, temperature and voltage variations become significant in deep submicron design, timing closure becomes a critical challenge in synchronous CAD flows.  An attractive alternative is to use robust asynchronous circuits which gracefully accommodate timing discrepancies.  One promising target is the use of asynchronous threshold circuits, constructed of robust m-of-n cells, such as Null Convention Logic (NCL) style, which have been shown to provide high reliability under extreme operating temperatures (e.g. -175C to +225C), process variability, and sub-threshold operating voltage (e.g. 200 mV). However, such robust asynchronous circuits typically suffer from high area and latency overheads.

In this work, a global optimization algorithm is presented which reduces the area and delay of the circuits by relaxing their overly-restrictive style. In particular, a "relaxation" approach is proposed, which selectively replaces gates or sub-components by optimized equivalents which can perform eager evaluation, while still preserving the overall timing robustness of the entire circuit. The algorithm is formulated as a unate covering problem, and solved exactly under several cost functions.

The gate-level optimization algorithm demonstrates average improvements of 34.9% in area and 16.1% in delay.  The approach has been migrated to block-level optimization, and applied to high-performance adders (Brent-Kung, Kogge-Stone) and array multipliers, with significant benefits:  up to 49.7% area improvement and 25.5% delay improvement.

It is expected that this global optimization technique can also be applied to robust threshold networks used in a range of emerging technologies.

[This work appeared in ASPDAC-07 and Async-08.]

About the speaker:

Steven M. Nowick is a Professor of Computer Science and Electrical Engineering at Columbia University, and co-founder and former chair of the Computer Engineering Program. He received a Ph.D. in Computer Science from Stanford University in 1993, and a B.A. from Yale University.   His main research area is on design methodologies and CAD tools for synthesis and optimization of asynchronous and mixed-timing (i.e. GALS) digital systems.  His current projects include:  scalable networks-on-chip (NoC's) for shared-memory parallel processors and embedded systems, ultra-low energy digital systems, fault tolerance, and low-power and robust global communication.

Dr. Nowick is an IEEE Fellow, a recipient of an Alfred P. Sloan Research Fellowship, and NSF CAREER and RIA Awards.  He received Best Paper Awards at the IEEE International Conference on Computer Design (1991, 2012) and the IEEE Async Symposium (2000).  He co-founded the IEEE "Async" Symposia series in 1994, and was its Program Committee Co-Chair and General Co-Chair. He was Program Chair of the IEEE/ACM International Workshop on Logic and Synthesis (IWLS), and program track/subcommittee chair at DAC, DATE and ICCD conferences.  He is currently an associate editor of IEEE Design & Test magazine, ACM Journal on Emerging Technologies in Computer Systems, and IEEE Transactions on VLSI Systems, and former associate editor of IEEE Transactions on CAD.  He was the selection committee chair of the ACM/SIGDA Outstanding Dissertation in EDA (OPDA) Award, and a member of the Best Paper award selection committees of ACM/IEEE DAC and ICCAD conferences.  He is also a recipient of the Columbia Engineering School Alumni Distinguished Faculty Teaching Award.  He holds 12 issued US patents.