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

135 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998.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.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD