Power optimization of technology-dependent circuits based on symbolic computation of logic implications.
This paper presents a novel approach to the problem of optimizing combinational circuits for low power. The method is inspired by the fact that power analysis performed on a technology mapped network gives more realistic estimates than it would at the technology-independent level. After each node's switching activity in the circuit is determined, high-power nodes are eliminated through redundancy addition and removal. To do so, the nodes are sorted according to their switching activity, they are considered one at a time, and learning is used to identify direct and indirect logic implications inside the network. These logic implications are exploited to add gates and connections to the circuit; this may help in eliminating high-power dissipating nodes, thus reducing the total switching  activity and power dissipation of the entire circuit. The process is iterative; each iteration starts with a different target node. The end result is a circuit with a decreased switching power. Besides the general optimization algorithm, we propose a new BDD-based method for computing satisfiability and observability implications in a logic network; futhermore, we present heuristic techniques to add and remove redundancy at the technology-dependent level, that is, restructure the logic in selected places without destroying the topology of the mapped circuit. Experimental results show the effectiveness of the proposed technique. On average, power is reduced by 34%, and up to a 64% reduction of power is possible, with a negligible increase in the circuit delay.
INTRODUCTION
Excessive power dissipation in electronic circuits reduces reliability and battery
life. The severity of the problem increases with the level of transistor integra-
tion. Therefore, much work has been done on power optimization techniques at
all stages of the design process. During high-level design, power dissipation can
be reduced through algorithmic transformations [Chandrakasan et al. 1995], architectural
choices [Chandrakasan and Brodersen 1995], and proper selection of the
high-level synthesis tools [Macii et al. 1997]. At the logic level-the focus of this
paper-the main objective of low-power synthesis algorithms is the reduction of
the switching activity of the logic, weighted by the capacitive load. Logic optimization
may occur at both the technology-independent and the technology-dependent
stages of the synthesis flow. At the technology-independent stage, combinational
circuits are optimized by two-level minimization [Bahar and Somenzi 1995; Iman
and Pedram 1995b], don't care based minimization [Shen et al. 1992; Iman and
Pedram 1994], logic extraction [Roy and Prasad 1992; Iman and Pedram 1995a],
and selective collapsing [Shen et al. 1992]. At the technology-dependent stage, technology
decomposition [Tsui et al. 1993] and technology mapping [Tsui et al. 1993;
Tiwari et al. 1993; Lin and de Man 1993] methods have been proposed. Finally,
after an implementation of the circuit is available, power can still be reduced by
applying technology re-mapping [Vuillod et al. 1997] and gate resizing [Bahar et al.
1994; Coudert et al. 1996].
It is difficult to measure the power dissipation of technology-independent circuits
with a dependable level of accuracy. Therefore, we propose a method that can be
applied to technology mapped circuits, and that is based on the idea of reducing the
total switching activity of the network through redundancy addition and removal.
Previous work on this subject includes the methods proposed in [Cheng and
Entrena 1993; Entrena and Cheng 1993; Chang and Marek-Sadowska 1994], in
which a set of mandatory assignments is generated for a given target wire. A set of
candidate connections is then identified. Each candidate connection, when added
to the circuit, causes the target fault to become untestable and therefore the faulty
connection to become redundant. However, since the additional connection may
change the circuit's behavior, a redundancy check is needed to verify that the new
connection itself is redundant before it may be added to the circuit.
Another ATPG-based approach was proposed in [Rohfleish et al. 1996]. That
technique uses an analysis tool introduced in [Rohfleish et al. 1995] to identify permissible
transformations on the network that may reduce power dissipation. The
method for finding permissible transformations is simulation-based; implications
are classified into C1-, C2-, and C3-clauses and bit-parallel fault simulation is performed
to eliminate most of the clauses that are invalid. The remaining potentially
valid clauses are combined to create different clause combinations, each of which
is checked for validity using ATPG. As more complex clauses are included, the
number of combinations to consider can increase dramatically.
Other work in the area of redundancy addition and removal uses recursive learning
to guide in the process. For instance, the work proposed in [Kunz and Menon
1994] introduces an ATPG-based method for identifying indirect implications, which
may indicate useful transformations of a circuit. Once an implication is identified,
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 3
it may be used to add a redundant connection, which is guaranteed not to change
the behavior of the circuit. An additional redundancy elimination step is required
to identify what other redundant connections, if any, have been created by adding
this new connection.
In our method, we start from a circuit that is already implemented in gates from
a technology library, and we perform power analysis on it, so as to identify its
high and low-power dissipating nodes. We use a sophisticated learning mechanism
(related to those of [Trevillyan et al. 1986; Kunz and Pradhan 1992; Kunz 1993;
Jain et al. 1995]) to find satisfiability and observability implications in the circuit
in the neighborhood of the target nodes. Such implications are used to identify
network transformations that add and remove connections in the circuit (as done
in [Kunz and Menon 1994]), with the objective of eliminating the high-power nodes
or connections from them. The method is innovative in two main aspects; first,
it uses a powerful learning procedure based on symbolic calculations rather than
ATPG-based methods. This approach allows the identification of very general
forms of logic implications; second, it operates at the technology-dependent level;
this allows more accurate power estimates to drive the overall re-synthesis process.
Experimental results, obtained on a sample of the Mcnc'91 benchmarks [Yang 1991],
show the viability and the effectiveness of the proposed approach.
The rest of this manuscript is organized as follows. Section 2 gives definitions for
subsequent usage. In Section 3 we propose a symbolic procedure to compute logic
implications using learning. Section 4 describes the power optimization procedure
based on redundancy addition and removal. Section 5 is dedicated to experimental
results, and finally, Section 6 gives conclusions and directions for future work.
2. BACKGROUND
In this section we provide definitions of terms and introduce concepts to be used
in the rest of the paper. We first define characteristic functions and relations;
next, we discuss the concept of untestable faults and show how these faults may be
eliminated through redundancy removal. Finally, we show how logic implications
may be used to create new untestable faults in a circuit that may be subsequently
removed to create an overall better optimized circuit.
2.1 Characteristic Functions and Relations
Given a set of points S in the Boolean space, is possible to define
a function called the characteristic function of S, that evaluates to
1 exactly for the points of B n that belong to S. Formally:
This definition can be extended to arbitrary finite sets, provided that the objects
in the set are properly encoded with binary symbols.
Since characteristic functions are Boolean functions, they can be represented
and manipulated very efficiently through binary decision diagrams (BDDs) [Bryant
1986]. As a consequence, it is usually possible to handle much larger sets if the
BDDs of their characteristic functions are used instead of an explicit enumeration
of all the elements in the sets.
In this paper, we restrict our attention to relations, that is, to sets which are
subsets of some Cartesian product. Let S and Q be two sets, and let R ' S \Theta Q
be a binary relation (i.e., the elements of R are pairs of elements from S and Q).
Using different sets of variables,
the elements of S and Q, we can represent this relation through its characteristic
As an example, consider sets greeng and
GREY; RED; ORANGEg, and relation lower case(q)g. Let us
encode the elements of S using variables
Similarly, the elements of Q are encoded using variables
as:
of relation R is then:
R
That is, RED)g. Obviously, the definition of binary relation given
above can be easily extended to the case of n-ary relations, that is, relations which
are subsets of Cartesian products of order n.
2.2 Circuits and Faults
A combinational circuit, C, is an acyclic network of combinational logic gates. If
the output of a gate, g i , is connected to an input of a gate, g j , then g i is a fanin of
j and gate g j is a fanout of gate g i .
A combinational circuit may have a failure due to a wire being shorted to the
power source or ground. Such a failure may be observed as a stuck-at fault. That
is, under the failure, the circuit behaves as if the wire were permanently stuck-at-1
or stuck-at-0. We assume that single stuck-at faults are used to model failures in a
circuit. Let C be a combinational circuit, and let C f be the same circuit in which
fault f is present. Fault f is untestable if and only if the output behaviors of C
and C f are identical for any input vector applied to both C and C f .
2.3 Redundancy Addition and Removal
Any automatic test pattern generation program may be used to detect untestable
faults (e.g., [Sentovich et al. 1992]). The computed information may be used
to simplify the network by propagating the constant values (zero or one), due to
untestable stuck-at connections, throughout the circuit.
Redundancy removal is one of the most successful approaches to logic optimization
(e.g., [Cho et al. 1993]). However, its effectiveness greatly depends on the
number of redundancies: For circuits that are 100% testable, redundancy removal
does not help. For this reason, techniques based on redundancy addition and removal
have been proposed.
The concept of redundancy addition and removal is best explained through an
example. In Figure 1(a) all stuck-at faults are testable. Therefore, no simplification
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 5
through redundancy removal is possible on the network as is. If gate G10 is transformed
into a 2-input NOR gate and the additional input is connected from the
inverted output of gate G6 (see shaded logic in Figure 1(b)), then the behavior of
the circuit at its primary outputs will remain unaltered; however, three previously
testable faults (shown with X's in Figure 1(b)) now become untestable. Through
redundancy removal, gate simplification, inverter chain collapsing, and DeMorgan
transformations, the circuit can be simplified as shown in Figure 1(e).
a
c
e
G6
G4 G8 G9 G10
d
x
y
a
c
d
e
G6
G4 G8 G9 G10
x
y
a
c
e
G6
d
x
y
G6
a
c
e
G6
G4
d
x
y
(a) (b)
(c)
(d)
a
c
d
e
x
y
Fig. 1. Example of Redundancy Addition and Removal.
Adding redundant gates and connections to a circuit may increase area, delay,
and power consumption by an amount that may not be recoverable by the subsequent
step of redundancy removal. Furthermore, not all redundancies in a network
are necessarily due to sub-optimal design; automatic synthesis and technology mapping
tools sometimes resort to redundant gates insertion to increase the speed of
a digital design [Keutzer et al. 1991]. As a consequence, redundancy addition and
removal are delicate operations that should be performed within the constraints of
the objective function being minimized.
6 \Delta R. I. Bahar, E. T. Lampe, and E. Macii
2.4 Logic Implications
In general, there may be a large variety of choices available in selecting the new
connections (and logic gates) that may be added to the original circuit so as to
introduce redundancies. Kunz and Menon have proposed an effective solution for
selecting these connections through a method derived from recursive learning [Kunz
and Menon 1994]. Recursive learning is the process of determining all value assignments
necessary for detection of a single stuck-at fault in a combinational circuit.
This process is equivalent to finding direct and indirect implications in the circuit,
that is, finding all the value assignments necessary for a given signal to take on
a specific value (satisfiability implications) or to make a given signal observable
(observability implications).
2.4.1 Direct Implications. If a value assignment can be determined by simple
propagation of other signal values through a circuit, then this is known as a direct
satisfiability implication. For example, consider the circuit in Figure 2, where the
signal assignment been made. This assignment directly implies the
value assignments as these are the only assignments for G7
and G8 that will justify the output of gate G9 to a value of 1.
a
c
d
e
G6
G4 G8 G9 G10
x
y
Fig. 2. Example Circuit with Satisfiability Implications.
Similarly, if a value assignment such that a given node is observable can be
determined by simple propagation of other signal values through a circuit, then
this is known as a direct observability implication. For example, consider the circuit
in

Figure

3. For G2 to be observable, are the only assignments
for G1 and G6 that will make gate G2 observable. That is, the observability of G2
directly implies
a
c
e
d G3
G4
G6
y
Fig. 3. Example Circuit with Observability Implications.
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 7
2.4.2 Indirect Implications. It has been shown in [Kunz and Menon 1994] that
only resorting to direct implications to perform redundancy addition and removal
may not provide enough options to achieve significant improvements on the circuit
being optimized. It is thus of interested to look at another type of implications,
namely indirect implications.
To illustrate the concept of indirect implication, consider again the circuit of

Figure

2, and suppose that the signal assignment has been made. We may
optionally assign either to justify this assignment; however,
neither assignment is essential. We therefore conclude that there are no essential
direct implications we can make from this assignment. However, upon closer in-
spection, we can determine that the value assignment indirectly implies
the value assignment 1. If we temporarily assign
are both essential to satisfy G7 = 1. Likewise, by temporarily assigning
we find that are essential assignments.
In either case, is an essential assignment; we can conclude that
an essential assignment for, and is indirectly implied by,
The indirect implication shown in the previous example falls in the category of
satisfiability implications. As an example of an indirect observability implication,
consider again the circuit in Figure 3. For G3 to be observable, must be
true (and vice versa). Therefore, the observability of G3 indirectly implies
Satisfiability implications have a bi-directional property, which does not apply
to observability implications. For example, for the circuit shown in Figure 2 it
can be shown that the satisfiability implication can be
reversed and complemented so that
is a general property of satisfiability implications. However, this property does not
hold for observability implications. Referring to the previous example of Figure 3,
although the observability of G2 (that is, both
the observability of G1 does imply does not
imply This is because it cannot be assumed that G1 and G2 are always
observable under the same conditions. This lack of bi-directionality makes adding
redundant logic to the circuit more constrained when observability rather than
satisfiability implications are used. For this reason, implications of the two types
must be handled separately when applying optimizations based on redundancy
addition and removal.
In [Kunz and Menon 1994], Kunz and Menon have observed that the presence
of indirect implications is a good indication of sub-optimality of a circuit. This is
especially true for satisfiability implications. We have taken inspiration from this
approach to implement the power optimization algorithm we propose in this paper.
However, certain implications should not be eliminated from consideration simply
because they were found through direct propagation of logic values. In fact, most
observability implications are found "directly", since they are determined primarily
through forward propagation of implications. In the next section we discuss how
direct, as well as indirect implications can be computed symbolically using BDD-based
data structures. Then, in Section 4, we outline the overall optimization
procedure.
8 \Delta R. I. Bahar, E. T. Lampe, and E. Macii
3. COMPUTING IMPLICATIONS SYMBOLICALLY
In this section, we introduce our symbolic procedure to compute logic implications
through recursive learning. In what follows, a literal is either a variable or its
complement; a cube is a product of literals.
We start with a set of relations T
a universe of n Boolean variables. Each T j can be thought of as a characteristic
function y for the gate j describing its functional behavior. For example,
if j is a NAND gate with inputs y i and
j is a NOR gate, then T If the Boolean variables
are assigned in such a way that T j evaluates to 0, then the variable
assignments violate the required behavior of the gate and are invalid. In this way,
an entire network may be described within this set fT j g.
may also be used to express the observability relation for a gate. For instance,
consider gate G4 in Figure 2. For the signal at the output of gate G4 to be observable
at either primary output x or y,
and T sat
ce +G4(ce) 0 .
Now, if we are given an initial assignment (i.e., assertion A(y)), we may compute
its implications by applying A(y) to the set fT j g:
Y
Furthermore, we may wish to extract only the necessary, or essential, literals from
the implication I(y):
For example, if the assertion applied to the characteristic function
3 ), the resulting implication becomes I = y 3 (y 1 +y 2 ).
However, in order to satisfy the characteristic function given this assertion, only
strictly necessary). Therefore,
the implication y stored separately in c(y).
In this way, given an initial assertion A(y), c(y) is a list of essential gate assignments
over the entire network. Implemented using BDDs, c(y) is represented as a
single cube. As it will be shown later, essential literals require simple redundant
logic to be added to the network, and therefore it may be beneficial to store them
separately.
3.1 Direct Satisfiability Implications
Given a set of characteristic functions, T
g, and an initial assertion, A,
we compute all direct satisfiability implications using the procedure impSatDirect
shown in Figure 4. Recall that a direct implication is one that can be found by propagating
the immediate effects of the logic assertion forward and backward through
the specified set of relations T , without case analysis. The essential implications
are returned separately in the cube imp. In our implementation, T Sat , A, and imp
are all represented as BDDs.
The direct implications are computed as follows. First, we initialize the list of
implications to be the cube-free, or essential, part of A. Next, we consider all
possible direct implications, one at a time, on the gates from the set Q (line 2).
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 9
procedure impSatDirect(A,T
Sat
1.
2.
k is fanout of some x
3. while (Q 6=
4. select and remove one(Q);
5. T Sat
Sat
6. if (T Sat
7.
8. if (t j one) continue;
9.
is a fanout of some x
return(imp,T Sat );
Fig. 4. Procedure impSatDirect.
The set Q contains all fanouts of variables in the support of the cube imp, plus all
the variables in imp itself.
The first step of the while loop selects one gate from Q, and removes it from
the set. Inside the loop (lines 4 to 10), procedure Essential is called, according to
Equation 4, to discover any new essential implication. We exit the loop and return
(line
k reduces to zero, implying that the assertion A is logically
inconsistent with one of the relations in the set of sub-relations fT Sat
g.
The literal function t (line 7) represents newly discovered essential implications.
On each pass through the while loop, these new implications are added to the
global implications cube imp (line 9), thereby accumulating all the implications of
the original assertion A. As these implication variables are found, they are also
appended to the set Q (line 10) in order to evaluate their effect on the rest of the
network.
In addition to the cube imp, the procedure impSatDirect also returns T Sat ,
which has now become a reduced set of relations comprised of the cofactor of each
original relation with respect to the essential implications imp (that is, T Sat j imp ).
Notice that T Sat j imp is itself a set of implications, albeit non-essential ones. These
more general implications may also be useful for optimizing a network, though they
are not as straight-forward to apply to the network. This will be discussed in more
detail later in the paper.
3.2 Direct Observability Implications
If observability implications are also to be used in the evaluation of direct im-
plications, procedure impSatDirect may be expanded such that relation T obs
j is
evaluated along with T Sat whenever signal j is on the observability frontier. The
procedure is now renamed impDirect and shown in Figure 5.
Lines 1 to 10 are almost identical to those of procedure impSatDirect. The
observability implications are computed beginning on line 12. If the gate k is on
the frontier, we find new implications in the same way as in impSatDirect, only
this time using the observability characteristic functions, T Obs . What makes the
procedure impDirect(A,T Sat ,T Obs
1.
2.
3.
fkjxk is on frontier and has same fanout as x j 2 impg;
4. while (Q 6=
5. select and remove one(Q);
Sat
7. if (T Sat
8.
9. if (t j one) continue;
11. is a fanout of some x
fkjxk is on frontier and has same fanout as x
/* Begin Observability Calculations. */
12. if (k is on frontier) f
13. T Obs
14. if (T Obs
15.
17. else f
19.
21. if (T Obs
/* Frontier is pushed forward */
22. foreach (s 2
is observable from s) f
26. if
27.
return(imp,T Sat ,T Obs );
Fig. 5. Procedure impDirect.
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 11
code more complicated is in updating the frontier.
If the reduced observability relation T Obs
k evaluates to 1, then the fault is observable
through at least one fanout of k and the frontier should be pushed forward to
include these fanout gates (line 24). Furthermore, if all the fanouts of gate k have
been implied, then k is removed from the frontier (line 27). Finally, if the frontier
ever becomes 0 (i.e., empty), then the assertion is not observable, and never will
be. This case is checked in line 16.
3.3 Indirect (Recursively Learned) Implications
Using the symbolic direct implications procedure from the previous section, we can
find indirect, or recursively learned, implications by setting temporary orthogonal
constraints on the initial assertion, finding implications based on these constraints,
and extracting the common implication as the full set of implications. We define
orthogonal constraints as a set of functions ff
Although we may use any orthogonal set of functions, to simplify the recursive
implication procedure, we use the orthogonal constraints f(y) and f 0 (y).
Say that we extract a function f(y) from the network, and add it to the original
assertion A(y) such that:
We apply each assertion A 1 (y) and A 0 (y) separately to the network using Equation
3 to get two different sets of implications, I 1 (y) and I 0 (y), respectively. For
each variable y j we combine these implications such that:
Y
to obtain the new set of implications (both direct and indirect). That is, we retain
only the implications that are common to both I 1 (y) and I 0 (y). In addition, we may
choose to save the essential implications separately by applying Equation 4 to the
new set of implications. Notice that we may recursively apply new orthogonal constraints
to the set of transition relations to potentially find even more implications.
This is handled easily within the BDD environment, as shown in the pseudo-code
of

Figure

6.
The procedure indirectImps takes, as inputs, the assertion A and the relation
sets T Sat and T Obs . In addition, it takes an input, level, representing the
recursion level of the recursive call, initially set to 0. When level exceeds a specified
limit maxlevel, the search for further implications is abandoned. Procedure
indirectImps returns a cube, impCube, representing the set of all variables (direct
and indirect) that are implied to constant values.
It should be noted that an indirect implication discovered by propagating implications
backwards is often found to be a direct implication by propagating implications
forward. For example, the indirect satisfiability implication found in Figure 2,
can be found as a direct implication 1). This
procedure indirectImps(A,T Sat ,T Obs ,level) f
1. (directImps,T Sat ,T Obs
2. if (8i;(T Sat
3. if (level  maxlevel) return(directImps);
4. y
5.
7.
8.
Fig. 6. Procedure indirectImps.
is the same implication by the law of contrapositum. As previously mentioned,
we make the distinction between indirect and direct implications only because it is
often a good way of sorting out the more promising implications. Indeed, we may
not want to eliminate an implication simply because it is not "indirectly obtained".
If implications are found only by backward propagation, this may be a reasonable
filter to use. However, if we are interested in observability-based implications as
well, these can only be found in the forward direction, so using such a filter may
not be a good solution. This point is discussed further in Section 5.
Using BDDs to compute and store indirect implications may seem inefficient
compared to doing a simple analysis of the topology of a circuit. This may in
fact be true if all we are interested in are single-variable implications derived from
satisfiability assignments for single-literal assertions (for example, (y
b) for a; b 2 f0; 1g.) However, by computing the implications symbolically, we
are better suited for finding more general implications. That is, our procedure
can store, manipulate, and compute general (i.e., more complex) expressions with
similar complexity than if expressions were restricted to simple cubes (in fact, by
separating the essential implications from the non-essential ones, we have available
both).
4. POWER OPTIMIZATION PROCEDURE
We now describe our implication-based optimization procedure for reducing power
dissipation. The procedure consists of four main steps, described in detail in the
following Sections 4.1 to 4.4.
4.1 Selecting an Assertion Function and Finding Its Implications
Computing all the indirect implications of a large network, as shown in Section 3,
can be computationally expensive. Therefore, it is important to prune the search
for implications by limiting the recursion level and carefully selecting the assertion
function A(y) upon which the implications are found. To reduce the cost even
farther, in [Bahar et al. 1996] we have proposed to extract a sub-network and find
the implications only within the confines of this sub-network. Note that, although
the implications can be found only within the boundaries of the sub-network, all
implications must hold in the context of the entire network.
Indirect implications are often present specifically in circuits containing recon-
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 13
vergent fanout. Reconvergent fanout is the presence of two or more distinct paths
with a common input gate (or fanout stem), leading to a common output gate,
and with no other gate in common. The gate where the paths reconnect is called
the reconvergence gate. An example of a sub-network with reconvergent fanout is
shown in Figure 7. Two distinct paths from inputs c and d reconverge at gate G9.
The experiments in [Bahar et al. 1996] suggested that, in order to invest the time
finding implications only where it is most useful, the search for indirect implications
should be limited to sub-networks containing reconvergent fanout, where the
reconvergence gate itself is used as the initial assertion A(y). In this way, implications
may be found through (predominantly) backward propagation of signal values
toward the primary inputs.
a
c
d
e
G6
G4 G8 G9 G10
x
y
Reconvergence gate
Fig. 7. A Network of Gates with an Extracted Sub-Network (Shown in Grey).
While the above approach may work well if one is concerned only with satisfiability
implications, it may be too limiting if observability implications are also
to be exploited. Furthermore, as mentioned in Section 3.3, distinguishing between
indirect and direct implications becomes a less useful filter in sorting out the more
promising implications, since many of the observability ones are found through
direct forward propagation of signal values.
Instead of asserting the reconvergent gate, our new strategy selects a gate with
relatively low power dissipation (due to either low switching activity, low capacitive
load, or both). Once a suitable implication is found, the low-power assertion gate
is included in the added redundant logic. Using a low-power assertion gate has
a minimal impact on potentially increasing its own power dissipation (switching
activity and capacitive load are already low). In addition, using this signal as an
input to other gates may have a dampening effect on the switching activity of other
gates. For example, if an AND gate has a high switching activity, then connecting
a signal which tends toward a 0 value most of the time (and switches infrequently)
may prevent the output of the AND gate from switching as frequently. Moreover,
these additions may allow the removal of other high-power connections or gates.
Therefore, although the assertion gate's power is increased, the net result is an
overall decrease in power consumption.
Once an assertion gate is selected, its output value is alternately set to both 0
and 1, and the implication procedure finds any relation which exists given one of
the assertions. Since the assertion gate may exist anywhere within the network (or
14 \Delta R. I. Bahar, E. T. Lampe, and E. Macii
sub-network), values will be propagated both "backward" and "forward" through
the logic.
4.2 Finding the Right Addition
Once we have found the implications for the given assertions on the selected gate,
we can use this information to add gates and/or connections to the circuit while
retaining the behavior of the original one at the primary outputs. We use a method
similar to data flow analysis [Trevillyan et al. 1986] to determine what these modifications
are for a given assertion its implication
where the implication gate y is in the transitive fanin of the assertion gate x.
Consider first the case where This implication can also
be expressed as x 0 Given the function F the implication can be
expressed as the don't care condition, F (x) DC , for F (x). That is, x
We may transform F to ~
F by adding this don't care term to the output of F without
changing the behavior at the primary outputs of the circuit:
~
In other words, the original circuit is modified by ORing the don't care term (i.e.,
the implicant gate y) with the output of gate x. Similarly:
~
For the case instead of using the don't care expression
we use the analogous expression x
transform F to ~
F as:
~
In other words, the circuit is modified by ANDing the implicant gate y with the
output of gate x.
As an example of how this method is applied, refer back to the circuit in Figures
1(a) and (b). We show the additional connection added due to the implication
1). According to the implication, we can modify the function
at the output of gate G9 without changing the behavior of the circuit by inserting
the
in the circuit. Notice that this OR gate added
to the network is "absorbed" by the inverter G11 which now becomes a 2-input
gate. Note that it is essential that the assertion gate not be in the transitive
fanin of the implication, since replacing the function F (x) with ~
F (x) would create
a cyclic network.
4.3 Finding and Removing the Redundancies
Once the redundant circuitry is added, we use the automatic test pattern generation
procedure implemented in SIS [Sentovich et al. 1992] to find the new
redundancies created in the network. Whether implications are found using the
entire network or only within the boundaries of a sub-network, finding and removing
redundancies should be done on the entire network.
We generate a list of possibly redundant connections. Since the newly added gates
are themselves redundant, we need to make sure that they are not included in the
list. The result of redundancy removal is order dependent; removing a redundant
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 15
connection from a network may create new redundancies, and/or make existing ones
no longer redundant. Since our primary objective is reducing power dissipation, we
sort the redundant connections in order of decreasing power dissipation and remove
them starting from the top of the list.
After ATPG, the identified redundant faults can be removed with the ultimate
goal of eliminating fanout connections from the targeted high power dissipating
node. Redundancy removal procedures such as the one implemented in SIS cannot
be used for this purpose for two main reasons. First, optimization occurs through
restructuring of the Boolean network. As a consequence, even if redundancy removal
operates on a technology mapped design, the end result of the optimization
is a technology independent description that requires re-mapping onto the target
gate library. This may lead to significant changes in the structure of the original
network. This is undesirable in the context of low-power re-synthesis, since the
network transformations made during re-synthesis are based on the original circuit
implementation. Second, redundancy removal usually targets area minimization,
and this may obviously affect circuit performance.
We have implemented our own redundancy removal algorithm, which resembles
the Sweep procedure implemented in SIS, but operates on the gates of a circuit
rather than on the nodes of a Boolean network. In addition, it performs a limited
number of transformations. Namely, the procedure (a) simplifies gates whose inputs
are constant, and (b) collapses inverter chains only when the original circuit
structure and performance are preserved.
Gate Simplification:. Three simplifications are applicable to a given gate, G,
when one of its inputs is constant:
(1) If the constant value is a controlling value for G, then G is replaced by a
connection to either V dd or Ground, depending on the function of the gate.
(2) If the constant value is a non-controlling value for G, and G has more than two
inputs, then G is replaced by a gate, ~
G, taken from the library and implementing
the same logic function as G but with one less input.
(3) If the constant value is a non-controlling value for G, and G is a two-input gate,
then G is replaced by an inverter or buffer.
Usually, cell libraries contain several gates implementing the same function, but
differing by their sizes and, therefore, by their delays, loads, and driving capabilities.
We select, as replacement gate ~
G, the gate that has approximately the same driving
strength as the original gate G.
Inverter Chain Collapsing:. Inverter chains are commonly encountered in cir-
cuits, especially in the cases where speed is critical. Collapsing inverters belonging
to these "speed-up" chains, though advantageous from the point of view of area
and, possibly, power, may have a detrimental effect on the performance of the cir-
cuit. On the other hand, the simplification of gates due to redundancy removal may
produce inverter chains that may be easily eliminated without slowing down the
network. We eliminate inverter chains only in the cases where the transformation
does not increase the critical delay of the original circuit. For each inverter, ~
G,
obtained through simplification of a more complex gate, we first check if ~
G belongs
to a chain which can be eliminated. If certain constraints are satisfied, both the
G and the companion inverter in the chain (i.e., the inverter feeding ~
G or
the inverter fed by ~
are removed. In particular, in order to safely remove the
inverter chain:
(1) The first inverter cannot have multiple fanouts.
(2) The load at the output of the inverter chain must not be greater than the load
currently seen on the gate preceding the inverter chain.
The first restriction may be unnecessarily conservative; however, removing it implies
that sometimes extra inverters need to be inserted on some of the fanout branches of
the first inverter, thereby possibly introducing area, power, and delay degradation.
4.4 Choosing the Best Network
Adding redundant gates and connections to a circuit may increase area, delay, and
power consumption by an amount that may not be recoverable by the subsequent
step of redundancy removal. Given an assertion, a network is created for each literal
in the implication cube that we elected to save while running the implication
procedure. (We may choose to eliminate an implication from the list of possible
candidates because it will create a cyclic network or may add connections to an
already high-dissipating node.) This new network is obtained by adding the appropriate
redundant logic according to the chosen implication (Section 4.2) and
finding and removing the newly created redundancies (Section 4.3). Power and
delay estimations are then run on each new network. The best network is selected
from them, and used to replace the existing network. The criteria we have used
to carry out the network selection are based on a combination of delay and power
consumption and are discussed in detail in Section 5.
5. EXPERIMENTAL RESULTS
In this section we present the results obtained by applying our optimization procedure
to some combinational circuits from the Mcnc'91 benchmark suite. Experiments
were run within the SIS environment on a SUN UltraSparc 170 workstation
with 300 MB of memory.
The circuits are initially optimized using the SIS script script.rugged and
mapped for either area (using map) or for delay (using map -n 1 -AFG). The library
used to map the circuits contains NAND, NOR, and inverter gates, each of
which allows up to 4 inputs and 5 drive options. In general, gates with larger drive
strength have larger cell area, however these two values do not increase at the same
rate. After mapping, the method of [Bahar et al. 1994] is used to resize gates with
smaller gates where no circuit delay penalty is incurred. This ensures that any gain
made during the experiment is the result of our optimization procedure and not of
an improperly sized gate. The statistics for these circuits are reported in Table 1.
In particular, the number of gates, the area (in m 2 ), the delay (in nsec), and the
power consumption (in W ) are shown. Power dissipation is estimated using the
simulation method of [Ghosh et al. 1992].
For each set of experiments our optimization procedure was iteratively applied
to the circuits to find implications to be used for redundancy addition and removal.
After this step, gates in the circuit are again resized without increasing the critical
delay.
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 17

Table

1. Circuit Statistics Before Optimization.
Circuit Initial Statistics (Mapping for Area) Initial Statistics (Mapping for Speed)
Gates Area Delay Power Gates Area Delay Power
9sym 159 236176 17.79 629 276 404840 10.95 1743
clip 104 146624 17.43 427 167 249632 12.29 1205
inc
misex1 50 66352 13.79 192 76 111244 9.94 525
alu4 169 234784 19.93 628 247 344056 14.06 1391
cordic 67 90944 11.64 280 85 123192 9.53 474
cps 897 1286208 40.09 1932 1272 1694412 13.68 2772
5.1 Setting Delay and Power Constraints
The first set of experiments were run to determine how to choose a new network
among a choice of several. That is, how to choose the best implication to apply
to the network. As it was done in [Bahar et al. 1996], network choices may be
based solely on which one has the lowest power dissipation with the constraint that
the delay of the new network has not increased by more than a fixed percentage
(usually 5%). A more robust approach may use a combination of delay and power
to select the best network, or may temporarily allow power to increase so that more
powerful implications may be subsequently applied, thus having a greater impact
on reducing power dissipation. These experiments are discussed in the following
sections.
5.1.1 Power Threshold. One optimization already mentioned in Section 4.4 is the
addition of a power threshold. The basis of a power threshold is the observation
that if the difference in power of two networks is small, better results are obtained
by choosing the network with the smaller delay. Then, as a fall back, if the delays
of the two networks are equal, the difference in power (no matter how small) is
used to make the determination. This heuristic takes advantage of the fact that
the final network will be resized based on the delay of the original network. A large
improvement in the delay gives the resizing algorithm the ability to make significant
additional power gains in the layout of the transistors. It also allows transformations
which may not have been accepted previously because they increased the delay too
much.
A set of experiments was done to determine the value of an optimal threshold
value. Tests were done with values of 1.0 to 2.75W at intervals of 0.25W on all
tested circuits for an area mapping. A run was also done at a threshold of 0, which
is a run based on power alone. Figure 8 shows an optimal threshold value of 2W .
This result is reasonable because, as discussed earlier in the paper, the final power
is affected by two variables, power and delay. Also, allowing the power to increase
slightly may create new implications that lead to even greater decreases in power
dissipation.
Total Power vs. Threshold6730677068100.00 1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75
Threshold
Total
Power
Fig. 8. Power Dissipation for Given Threshold Value.
5.1.2 Delay Tolerance. Another parameter that can be varied is the delay tol-
erance, which is defined as the allowable percent increase in the delay of the final
circuit from the original circuit. The interesting observation is that raising the delay
tolerance does not always result in a slower final network. This is because there
are often many transformation choices made before the final network is obtained.
Transformations that increase the delay are often offset by other transformations
that decrease it. Yet, the increase in the delay tolerance increases the number of
networks to choose from. In other words, like the power threshold, increasing the
delay tolerance increases the probability that a power saving implication will be
found.
There are several observations which can be made from the data. First, increasing
the delay tolerance does, on average, have the effect of increasing the delay. How-
ever, depending on the circuit, allowing more flexibility with delay per iteration
can allow one to obtain a final circuit that is both lower in power and faster than
the original circuit. Second, greater success was found when testing delay-mapped
circuits compared to the area-mapped circuits. This is reasonable, since the delay
mapped circuits are by definition designed to achieve a minimum delay. From this
extreme, a small sacrifice in delay produces a relatively large power savings over
area mapped circuits.
The results of the experiments are shown in Figures 9 and 10. It can be seen
that for an increase in delay tolerance, the average delay does go up. Also, after
a certain delay tolerance level, it can be seen that further decreases in power are
small to insignificant (on the graphs a delay tolerance of 200 can be interpreted as
infinite.)
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 19
Delay Tolerance Effects630065006700690071007300
Delay Tolerance
Power
and
Normalized
Delay
Total Power
Normalized Delay
Fig. 9. Power/Delay Tradeoff Curves for Varying Delay Tolerance (Circuits Mapped for Area).
Total Power vs. Delay Tolerance105001150012500135001450015500100 105 110 115 120 125 130 135 140 145 150 155 160 165 170 175 180 185 190 195 200
Delay Tolerance
Total
Power
Normalized
Delay
Total Power
Normalized Delay
Fig. 10. Power/Delay Tradeoff Curves for Varying Delay Tolerance (Circuits Mapped for Speed).

Table

2. Statistics After Redundancy Addition and Removal (Circuits Mapped for Area).
Gates Area Delay Power Imps Obs \DeltaP \DeltaD \DeltaA
9sym 178 241744 18.34 483 98 48 0.77 1.03 1.02
clip 88 117392 15.48 274 43 14 0.64 0.89 0.80
inc 97 127136 22.06 259 67 24 0.73 0.92 1.08
alu4 126 163792 19.38 354 74 28 0.56 0.97 0.70
cordic
Average 0.72 0.96 0.93

Table

3. Statistics After Resizing Gates from Table 2. Changes in power, delay, and area are
given relative to those shown in Table 1, columns 2-5.
Area Delay Power \DeltaP \DeltaD \DeltaA
9sym 241744 18.06 470 0.75 1.02 1.02
clip 117392 15.44 255 0.60 0.89 0.80
inc 127136 22.32 236 0.66 0.93 1.08
rd53 40832 10.93 111 0.74 1.04 0.93
cordic 79344 12.12 197 0.70 1.04 0.87
Average 0.68 0.96 0.93
5.2 Individual Experiments
From the results obtained in the first set of experiments, we now show the individual
power, delay, and area characteristics for each circuit after redundancy addition and
removal and resizing is complete. For all these experiments, the recursion level for
finding implications was limited to 1 (i.e., maxlevel = 1 in Figure 6). Implications
were applied using a power threshold of 2W and a delay tolerance of 5% above
the original circuit delay. As before, after redundancy addition and removal, gates
in the circuit are resized without increasing the critical delay. That is, the critical
delay of the final circuits was never greater than 5% above that reported in Table 1.

Tables

give the final statistics for the circuits. In Tables 2 and 4 we report the
results after applying the redundancy addition and removal (Table 2 starts with
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 21

Table

4. Statistics After Redundancy Addition and Removal (Circuits Mapped for Speed).
Gates Area Delay Power Imps Obs \DeltaP \DeltaD \DeltaA
clip 134 195692 12.50 828 71 24 0.69 1.02 0.78
inc 115 158224 16.09 450 71
misex1 68 94656 10.38 370 43 19 0.70 1.04 0.85
cordic
Average 0.73 1.03 0.83

Table

5. Statistics After Resizing Gates from Table 4. Changes in power, delay, and area are
given relative to those shown in Table 1, columns 6-9.
Area Delay Power \DeltaP \DeltaD \DeltaA
9sym 354844 11.48 1351 0.78 1.05 0.88
clip 170752 12.21 496 0.41 0.99 0.68
inc 146160 16.37 295 0.46 1.00 0.82
misex1 92336 10.27 331 0.63 1.03 0.83
alu4 228288 13.99 690 0.50 1.00 0.66
cordic 109040 9.89 420 0.89 1.04 0.89
Average 0.64 1.02 0.80
circuits mapped for area and Table 4 starts with circuits mapped for speed). The
number of accepted implications is shown in the column labeled Imps. Of these, the
shows how many of them are observability implications. The relative
changes in power, delay, and area are shown in the columns labeled \DeltaP , \DeltaD, and
(e.g., a 0.75 in the \DeltaP column indicates a 25% reduction in power compared
to that given in Table 1). The results after the final step of gate resizing are shown
in

Tables

3 and 5 respectively. Changes in power, delay, and area are given relative
to those shown in Table 1.
Notice that for circuits shown in Tables 2 and 3, the change in area remains
the same before and after gate resizing. Since these circuits are originally mapped
for area optimization, most of the gates were already at or near minimum size.
22 \Delta R. I. Bahar, E. T. Lampe, and E. Macii
Therefore, even after resizing, no additional saving in area is possible, However, a
slight improvement in power and delay is still possible with resizing since, in our
library, cell area for some gates are the same for different drive strengths.
The effectiveness of our method is shown by the presented results. For example,
in the case of mapping for area, a 49% power reduction was obtained for circuit
rd84. On the other hand, in the case of circuits mapped for speed, a 64% power
savings was obtained for benchmark bw; on average a power savings of 34% was
obtained for area and speed mapped circuits combined.
It is interesting to point out the relationship between power reduction and circuit
delay and area. While the circuits averaged a 36% reduction in power, delay increased
by only 2% for speed mapped circuits and decreased by 4% for area mapped
circuits. However, for a few examples, delay decreased significantly. For instance,
in

Table

3, circuit bw mapped for area showed a 31% decrease in power along with a
22% decrease in delay. These results help emphasizing that low power does not need
always to come at the expense of reduced performance. In addition, it is not always
the case that smaller devices must be used to obtain lower-power dissipation. For
example, for circuit C432 in Table 3, area increased by 1%, but power dissipation
decreased by 37%. This result emphasizes the need to consider switching activity
when optimizing for power.
6. CONCLUSIONS AND FUTURE WORK
To be successful, power optimization needs to be driven by power analysis. By
performing power analysis directly on a technology-mapped circuit, we can selectively
target the search for implications to areas (i.e., assertion functions) that
indicate promise in reducing power dissipation. Starting from an appropriate assertion
gate, low-power minimization is achieved through network transformations,
which are based on implications obtained using symbolic, BDD-based computation.
Our method has been shown to obtain up to a 64% decrease in power dissipation
and an average of 34% power reduction for all circuits.
Although all circuits presented in the results were of small to moderate size,
this method can be expanded to larger circuits as well. With larger sized circuits,
however, execution time may increase significantly. The execution bottleneck is not
the BDD-based algorithm to find the implications, but rather the ATPG algorithm
within SIS used to identify redundant connections. Other redundancy identification
and removal techniques, such as those presented in [Iyer and Abramovici 1994] may
be used to alleviate this bottleneck.
As future work, we would like to take advantage of the more general implications
mentioned in our symbolic algorithm. This enhancement should allow us to reduce
power dissipation further. In addition, we are working on identifying more powerful
transformations (other than simple inverter chain collapsing) which may be applied
to the circuit in order to further reduce area and power at no delay cost. These
transformations may include application of DeMorgan's Law or expanding the types
of gates included in our library. For instance, it may be advantageous to collapse,
say, a NAND and an inverter into an AND, or, NAND/inverter clusters into complex
gates. Finally, we are working on refining our method of selecting an assertion gate
and finding a suitable sub-network over which to search for implications.
Power Optimization Based on Symbolic Computation of Logic Implications \Delta 23

ACKNOWLEDGMENTS

We would like to thank Fabio Somenzi and Gary Hachtel for their many helpful
comments and suggestions made on the first draft.



--R


Symbolic computation of logic implications for technology-dependent low-power synthesis
In IEEE International Symposium on Low Power Electronics and Design (August
A symbolic method to reduce power consumption of circuits containing false paths.
Boolean techniques for low-power driven re-synthesis
In IEEE/ACM International Conference on Computer Aided Design (November

Minimizing power consumption in digital cmos circuits.

Optimizing power using transformations.
Perturb and simplify: Multi-level boolean network optimizer

Redundancy identification/removal and test generation for sequential circuits using implicit state enumeration.
New algorithms for gate sizing: A comparative study.
Sequential logic optimization by redundancy addition and removal.
Estimation of average switching activity in combinational and sequential circuits.

Logic extraction and factorization for low power.


Advanced verification techniques based on learning.
Is redundancy necessary to reduce
Hannibal: An efficient tool for logic verification based on recursive learning.
In IEEE/ACM International Conference on Computer Aided Design (November

In IEEE/ACM International Conference on Computer Aided Design (November
Recursive learning: An attractive alternative to the decision tree for test generation in digital circuits.


Reducing power dissipation after technology mapping by structural transformations.
Logic clause analysis for delay opti- mization
Syclop: Synthesis of CMOS logic for low power ap- plications

Sequential circuits design using synthesis and optimization.
On average power dissipation and random pattern testability of cmos combinational logic networks.
Technology mapping for low power.
Global flow analysis in automatic logic design.
Technology decomposition and mapping targeting low power dissipation.

Logic synthesis and optimization benchmarks user guide version 3.0.
--TR
Graph-based algorithms for Boolean function manipulation
Is redundancy necessary to reduce delay
Estimation of average switching activity in combinational and sequential circuits
Technology decomposition and mapping targeting low power dissipation
Technology mapping for lower power
Perturb and simplify
Multi-level logic optimization by implication analysis
A symbolic method to reduce power consumption of circuits containing false paths
Multi-level network optimization for low power
Logic extraction and factorization for low power
Advanced verification techniques based on learning
Logic clause analysis for delay optimization
Boolean techniques for low power driven re-synthesis
Two-level logic minimization for low power
New algorithms for gate sizing
Reducing power dissipation after technology mapping by structural transformations
Symbolic computation of logic implications for technology-dependent low-power synthesis
Sequential logic optimization by redundancy addition and removal
Re-mapping for low power under tight timing constraints
High-level power modeling, estimation, and optimization
On average power dissipation and random pattern testability of CMOS combinational logic networks
Sequential Circuit Design Using Synthesis and Optimization
Recursive Learning

--CTR
Luca Benini , Giovanni De Micheli, Logic synthesis for low power, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
L. E. M. Brackenbury , W. Shao, Lowering power in an experimental RISC processor, Microprocessors & Microsystems, v.31 n.5, p.360-368, August, 2007
automation;logic design;design synthesis