Analysis and optimization of digital circuit dynamic behavior

Wan, Lu

Permalink

https://hdl.handle.net/2142/31027 Copy

Description

Title

Analysis and optimization of digital circuit dynamic behavior

Author(s)

Wan, Lu

Issue Date

2012-05-22T00:22:36Z

Director of Research (if dissertation) or Advisor (if thesis)

Chen, Deming

Doctoral Committee Chair(s)

Chen, Deming

Committee Member(s)

• Torrellas, Josep
• Wong, Martin D.F.
• Kumar, Rakesh

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Better-than-worst-case design
• Throughput optimization
• Dynamic behavior
• Decision diagrams
• Common-case optimization
• Probability
• Digital circuit
• Timed ternary decision diagrams
• Timed characteristic function
• High throughput
• Processor
• 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.

Graduation Semester

2012-05

Permalink

http://hdl.handle.net/2142/31027

Copyright and License Information

Copyright 2012 Lu Wan

Owning Collections