Information Technology Reference
In-Depth Information
Tabl e 1.
Summary of BILP as presented in [10]
Function Type Examples
I/O Constraints
NOT
1:
y
=1
− x
1
NAND
2:
y
=1
− x
1
· x
2
NOR
2:
y
=1
−
(
x
1
+
x
2
)+
x
1
· x
2
where
y,x
i
ʵ
[0
,
1]
Linearization
y
=1
− x
1
· x
2
Constraints
p
=
x
1
· x
2
y
=1
− p
s.t. p ≤ x
1
,
p ≤ x
2
,and
x
1
+
x
2
− p ≤
1
Toggle
x
n
Constraints
x
n
+1
x
n
=1
− x
n
x
n
+1
=1
− x
n
+1
x
toggle
=
x
n
· x
n
+1
+
x
n
· x
n
+1
Maximize
i
=1
x
toggle
Objective
Function
5 Formulation of Level-BILP
Formulation of BILP for each level is needed to determine the level-max peak
activity and the corresponding input vectors in a modified way. For example with
respect to Fig-1, to determine the peak activity at Level-1 the toggle variables
at out-put net of XOR and NAND gate only has to be included in the objective
function. Hence for Level-1 the objective function as given in Table 1 can be
rewritten in following way.
2
x
1
.i
toggle
Maximize
(3)
i
=1
where
x
1
.
1
toggle
and
x
1
.
2
toggle
are toggle variable corresponding to XOR and NAND
gate at Level-1.
Since here the objective is to determine the peak activity at Level-1 the rest
of the circuit i.e. Level-2 to Level-3 can be ignored. Therefor the constraint set
now will only consider the gates from Level-1.
Similarly when we consider the Level-2 the objective function will optimize
the toggle variables corresponding to Level-2. And the constraint set will include
the gates from Level-2 back to Level-1. Rest of the gates from Level-3 onwards
can be ignored.
Hence from the above demonstration we observed that during the maximiza-
tion at Level-j(j is the current level at which maximization is being performed)
the circuit from Level-[j+1] to Level-L(L is the maximum number of levels) is
in don't care state and circuit from Level-1 to Level-j is in active state or care
state. Hence the BILP can now be applied only to the part of circuit that is in
active state.
