Department of Computer Science & Engineering

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.

Pre-2018 CSE ID: CS2005-0834