## Maximum Instantaneous Power Estimation by Subgraph Coloring

Bao Liu
CS2005-0834
October 12, 2005

Finding maximum instantaneous power consumption helps estimation of worst-case supply voltage drop and lifetime of a VLSI system. We observe signal correlations represented by logic inversions, and present a maximum subgraph two-coloring formulation for the problem. We show the problem is NP-hard, and the complexity comes from the presence of {\em reconvergent fanouts} besides inputs signal correlations. We further develop an efficient algorithm for general VLSI designs of practical sizes. Our experimental results on the ISCAS'89 benchmark show our subgraph coloring algorithm achieves $4.31\%$ less standard deviation of maximum instantaneous power estimate than the greedy transition assignment algorithm in \cite{WangRC96}; and a $2.82\%$ standard deviation of maximum instantaneous power estimate with 2-3 orders of runtime speedups compared with pattern-dependent simulation techniques.

## How to view this document

• Display an overview of the document in one of the following formats.

• Display a selected page in one of the following formats (document has 6 pages).
• Display the whole document in one of the following formats.