Files in this item



application/pdfWAN_Lu.pdf (9MB)
(no description provided)PDF


Title:Analysis and optimization of digital circuit dynamic behavior
Author(s):Wan, Lu
Director of Research:Chen, Deming
Doctoral Committee Chair(s):Chen, Deming
Doctoral Committee Member(s):Torrellas, Josep; Wong, Martin D.F.; Kumar, Rakesh
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Better-than-worst-case design
Throughput optimization
Dynamic behavior
Decision diagrams
Common-case optimization
Digital circuit
Timed ternary decision diagrams
Timed characteristic function
High throughput
Timing speculation
Timing error analysis
Timing error resilience
Logic synthesis
Abstract:Very-large-scale-integration (VLSI) circuit design heavily relies on computer aided design (CAD) tools to synthesize and optimize the circuits targeting a cycle time tclk. To account for variations, this cycle time usually includes a conservative timing guardband to accommodate delay changes. With the shrinking of technology, the performance of VLSI circuits has reached gigahertz range. However, the traditional way of designing VLSI circuits is facing great challenges with shrinking performance gain along with the shrinking cycle time tclk. Better-than-worst-case (BTWC) designs are proposed to alleviate the problem by removing the guardband and complementing a circuit with error detection and correction mechanisms. BTWC deliberately allows timing errors for rare cases and rectifies them with error correction mechanisms. This new design methodology can operate a circuit more efficiently than the traditional way. From the performance perspective, BTWC design, especially timing speculation (TS), is a promising technique for boosting VLSI circuit throughput. In this thesis, path constraint tuning (PCT) is proposed to design high-throughput processor components. PCT leverages a commercial design flow to tightly constrain frequently exercised timing paths and relax the infrequently exercised portion of the design. PCT is our initial effort to boost processor component performance with the BTWC design methodology. Considering that commercial CAD tools are designed to work with the traditional design methodology, they are not suitable for BTWC designs. To address the limitations of the existing CAD tools, a novel concept of dynamic behavior is proposed to quantify the timing error probabilities for digital circuits. Given input static probabilities of a circuit, its error statistics can be analyzed and represented with a dynamic behavior curve. The throughput of the circuit can then be derived from this behavior curve. Timed characteristic function (TCF) is proposed as a way to derive the behavior graph analytically using binary decision diagrams (BDD). Based on this analytical timing-error-probability framework, a logic optimization algorithm is developed to utilize dual threshold voltage (dualVt) cells to optimize a circuit's throughput in such a way that the most dynamically critical gates of a circuit can be identified and optimized. To make the circuit-level dynamic behavior analysis scalable, a technique called timed ternary decision diagrams (tTDD) is developed to analyze circuit dynamic behavior. It uses a divide-and-conquer method by analyzing each partitioned sub-circuit first and then combining the analysis results. False path pruning and random variable compaction are proposed to enable the computation of stabilization probabilities. Given that dynamic behavior becomes a new optimization dimension, a dynamic behavior driven logic synthesis technique is proposed to re-structure the BTWC circuit. A BTWC design flow called common case promotion (CCP) is proposed to specifically optimize circuit dynamic behavior. Aiming at improving the circuit stabilization probability for common cases, this proposed CCP consists of (1) probability-driven re-synthesis that changes a digital circuit’s internal structure, (2) a dynamic behavior aware SAT-based redundancy remover that reduces area overhead, and (3) a TCF based circuit dynamic behavior analyzer that provides optimization convergence. Utilizing error correction capability of BTWC design methodology, CCP can improve a circuit's timing error resilience by effectively manipulating the circuit's dynamic behavior. To sum up, this thesis focus on an emerging VLSI design methodology and proposes the use of dynamic behavior as a new measure to the quality of VLSI circuits. Based on dynamic behavior analysis, various optimization techniques are proposed. This work provides a thorough treatment to this new subject.
Issue Date:2012-05-22
Rights Information:Copyright 2012 Lu Wan
Date Available in IDEALS:2012-05-22
Date Deposited:2012-05

This item appears in the following Collection(s)

Item Statistics