Efficient symbolic algorithms for computing the minimum and bounded leakage states

Kaviraj Chopra, Sarma Vrudhula

Research output: Contribution to journalArticlepeer-review


Static power consumption due to subthreshold, gate, and junction leakages has become a significant component of the total power consumption. For nanoscale circuits, leakage poses one of the most important challenges to the continuation of Moore's law. The leakage of a logic gate varies by an order of magnitude over its Boolean input space. Thus, one way to minimize leakage in a circuit during standby mode is to apply an input vector for which the leakage is at its minimum. Such a set of vectors is called the minimum leakage set (MLS). In this paper, an efficient algorithm for computing the exact MLS is presented. The approach is based on implicit enumeration using integer-valued decision diagrams. Since the search space for MLS is exponential in the number of primary inputs, the enumeration is done with respect to the minimum balanced cut of the digraph representation of the circuit. Next, the problem of the increased switching power, which results from driving all inputs to a given state when entering the standby mode, is addressed. For a given upper bound B on the leakage, the MLS algorithm is extended to identify the maximal input cube with the minimum switching cost from the set of minterms whose maximum leakage is ≤ B. The switching cost associated with an input is taken to be proportional to the load capacitance of that input. The algorithms have been successfully tested on the ISCAS85 and MCNC91 benchmark circuits.

Original languageEnglish (US)
Pages (from-to)2820-2832
Number of pages13
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number12
StatePublished - Dec 2006


  • Decision diagrams
  • Leakage power analysis
  • Power minimization
  • Symbolic techniques

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient symbolic algorithms for computing the minimum and bounded leakage states'. Together they form a unique fingerprint.

Cite this