Low-Power-Driven Synthesis Algorithms for Sequential and Combinational Circuits

Roy, Sumit

Permalink

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

Description

Title

Low-Power-Driven Synthesis Algorithms for Sequential and Combinational Circuits

Author(s)

Roy, Sumit

Issue Date

1998

Doctoral Committee Chair(s)

Banerjee, Prithviraj

Department of Study

Electrical Engineering

Discipline

Electrical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Computer Science

Language

eng

Abstract

In the first part of the work, we propose an algorithm to decompose a given finite state machine (FSM) into smaller interacting FSMs such that by themselves they have plenty of self-loops, although the original FSM may not have any self-loops. We power down these decomposed FSM during the transitions corresponding to the self-loops to save power consumption. Second, we extend the above work to resynthesize sequential machines. We propose a symbolic simulation-based algorithm to extract the self-loops of the underlying FSM. We partition the sequential machine and apply the above clockgating technique. Third, we propose a synthesis methodology that uses algebraic techniques like kernel extraction, cube extraction, and collapsing to minimize power consumption of a logic function. A unique power cost function based on a fast mapping of a Boolean expression to a generic library is used to steer the above algebraic transformations to reduce its power consumption. Fourth, in order to guide the proposed synthesis tool, we developed a probability-based power estimation algorithm, by specifically solving the problem of identifying a desirable intermediate support-set. We proposed an exact polynomial time algorithm and also developed a heuristic solution for solving the above problem. Our heuristic solution is canonical and of constant complexity, a very desirable quality for a power metric guiding synthesis tool. Finally, we present a technology mapping algorithm which minimizing power consumption under strict timing constraint derived from industrial delay models. We introduced a novel concept of a delay-cost curve to store only important design trade-offs on the delay versus cost spectrum at each node of the circuit. We prove that our approach requires exponentially lesser storage compared to previous approaches and that it has bounded error. We report experimental results on each of our algorithm on a variety of combinational and sequential benchmark circuits.

Graduation Semester

1998

Type of Resource

text

Permalink

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

Owning Collections