Information Technology Reference
In-Depth Information
over real power numbers. Probabilistic activity factor ignores local surges and
observability, and simulation based estimation is limited due to long-simulation
times and input vector combinations. Recently, more exact methods have been
proposed to generate worst-case switching scenarios [1] [2] [3].
The method we have proposed here is vector-based approach that considers
level-accurate toggling activity in a combination circuit. Our method generates
exact pair of input vectors that can result in maximum toggling, at any level of
a given circuit.
The rest of the paper is organized as follows. Section 2 gives an overview
of previous approaches in power estimation. In Section 3 level-accurate power
estimation methodology is elaborated. Section 4 presents a back ground idea
on the formulation of BILP problem. We have presented the detail formulation
of level based BILP, called Level-BILP problem, in Section 5. In Section 6 the
experimental data on ISCAS-85 benchmark circuits and analysis of results is
presented. Finally, the paper is concluded with future work in Section 7.
2 Previous Work
Accuracy and computational eciency are the two motivations for research on
power estimation methodology. Two directions has been explored:
Input vector
based simulation
and
Vector less probabilistic method
. The simulation based ap-
proach generally look for a suitable input vector pair or a set of pairs to trigger
the circuit activity to maximum possible value. This kind of approach is moti-
vated by accuracy of the estimation, however such technique suffer from solving
an NP-Complete SAT problem to generate input patterns. On the other hand
probabilistic approach perform static analysis of circuit based on toggle prob-
ability at each node. Such approach are time ecient since static analysis of
circuit is a liner time problem. However the accuracy is more pessimistic, which
leads to power expensive design[4].
A vector based approach proposed by S Devadas et al.[5], formulated as
weighted max-satisfiability(SAT)
problem, is one of the early attempts. The
circuit was represented as
max-satisfiability(max-SAT)
problem and then was
solved using exact and approximation SAT solver. The SAT formulation was
modified as weighted SAT problem to consider load capacitance. One diculty
with SAT problem is computation time.
The idea of formulating the problem as
Pseudo-Boolean SAT
is explored re-
cently in [6] [3]. H Mangassarian et al.[6] and Sagahyroon et al. [7] have for-
mulated the problem as Pseudo-SAT problem to estimate worst case power and
worst case power-up current. The reported results show that the Pseudo-SAT
based technique is ecient when the problem is solved using commercial SAT
solver like CPLEX[8]. Motivated by the eciency of CPLEX solver and trade-off
between ILP and Pseudo-SAT [9], we have in our previous work [10] explored an
alternative idea of formulating the problem as ILP and solving it using CPLEX-a
dedicated ILP solver.
Some what different idea, brought from ATPG(Automatic Test Pattern Gen-
eration) technique, is proposed by Chuan- Yu Wang et al. [11] [1] in 1996. Two
