Files in this item

FilesDescriptionFormat

application/pdf

application/pdf9912360.pdf (7MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Low-Power-Driven Synthesis Algorithms for Sequential and Combinational Circuits
Author(s):Roy, Sumit
Doctoral Committee Chair(s):Banerjee, Prithviraj
Department / Program:Electrical Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
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.
Issue Date:1998
Type:Text
Language:English
Description:135 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998.
URI:http://hdl.handle.net/2142/81274
Other Identifier(s):(MiAaPQ)AAI9912360
Date Available in IDEALS:2015-09-25
Date Deposited:1998


This item appears in the following Collection(s)

Item Statistics