Low-power-driven synthesis algorithms for sequential and combinational circuits
Sumit Roy · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1998
As the use of portable devices spread and feature sizes shrink, allowing more devices in a chip, power consumption takes on increased importance. Even for high-performance nonportable systems, the increasing cost of packaging and cooling poses stringent requirements on the maximum allowable power consumption. In this thesis, we propose logic synthesis algorithms to minimize power of sequential and combinational circuits under a given timing constraint. The proposed power optimization techniques are suitable for reducing power consumption in an industrial synthesis framework. 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.