ternative wire technique attempts to replace a target
wire by another wire without changing the logic functionality. In
this paper, we propose two new transformations of replacing
wires. One transformation simultaneously replaces multiple
input wires of a gate by a new set of input wires and the other
performs gate decompostion during the alternative wire process.
To accomplish such complex transformations, we discuss some
theoretical foundations for replacing multiple wires. Under-
standing how wires/gates can be replaced by other wires/gates
allows us to speedup the process tremendously.
1 Introduction
In the traditional design flow, interconnect design takes a
(fixed) net list and attempts to optimize the interconnects from
the given net list which can be produced from a logic synthesis
tool. To handle the growing complexity of circuit design, design-
ers are forced to look ahead in a higher level of abstraction and
propose algorithms which combine logic synthesis and layout
synthesis. There have been several research papers
[2][4][5][7][9][11] integrating the logic and layout synthesis
algorithms. The work [9] proposes an earlier synthesis strategy
which uses wireplanning to distribute delays over the func-
tional elements and interconnects. In [11], they present an inte-
grated design flow which combines floorplanning, technology
mapping, and placement using a dynamic programming algo-
rithm.
There are also several logic synthesis techniques [1] [2] [3]
[6] [12] which may potentially be modified to consider the wiring
effect. Among those, [2] proposes a post-layout logic synthesis
technique which allows one to modify wire topology. This tech-
nique, called the alternative wire technique (Alwire) explores the
freedom in the logic domain to provide additional flexibility in
the layout area. The basic philosophy of Alwire is to remove
some wire by adding another wire to the circuit. For example in
Fig. 1 by adding wire
g
1
->g
5
, wire
c->g
2
can be removed with-
out changing the logic functionality.
The traditional techniques, though, can be quite effective in
performing single wire replacement. Due to the large searching
space required, to the best of our knowledge, there is very little
success in simultaneously replacing multiple wires/gates. In this
paper, we propose two new transformations. For the (direct)
input wires of a node, one transformation simultaneously
replaces the old set of input wires by a new set of input wires,
assuming that the old set of input wires is targeted for replace-
ment. For example, in Fig. 2, suppose the input wires (e->g
, f->g)
of node
g, are under consideration for removal. Our transforma-
tion can identify that a new set of wires
(o->g, p->g, q->g) can
replace the old set (
e->g, f->g) without changing the circuit func-
tionality. The other transformation proposed in this paper per-
forms gate decomposition during the alternative wire process. In
Fig. 5, only after decomposing the big OR gate
g
1
(Fig. 5a) into
two small OR gates,
g
6
and
g
7
(Fig. 5b), we can then replace wire
c->g
2
by wire
g
6
->g
5
.
We also would like to mention that there are several logic
optimization algorithms adding multiple wires/gates and then
removing wires/gates to reduce the size of a circuit. However,
those algorithms do not have specific target wires for removal in
mind and, therefore, are quite different from the objective of this
paper.
In order to achieve such complex transformations, we discuss
some theoretical foundations for replacing multiple wires. Under-
standing how wires/gates can be replaced by other wires/gates
allows us to speedup the process tremendously. As a result, we
can perform these complex transformations which were unfeasi-
ble in practice in [2]. Our experimental results show that these
new transformations require reasonable run time but can provide
much more flexibility than those in [2].
2 The Alternative Wire Technique
In this section, we briefly review the Alwire technique. Basi-
cally, the Alwire technique first decides some existing irredun-
dant wire that is the target to be removed. Then, the technique
searches for some non-existing wire, sometimes called a candi-
date connection, that once added can make the target wire stuck-
Fig. 1 An example for single alternative wire.
g
2
g
3
g
5
o
2
o
1
a
b
c
d
g
1
f
o
3
g
4
e
g
2
g
3
g
5
o
2
o
1
a
b
c
d
g
1
f
o
3
g
4
(b)
(a)
e
Synthesis for Multiple Input Wires Replacement of a Gate for
Wiring Consideration
Shih-Chieh Chang, Jung-Cheng Chuang, Zhong-Zhen Wu
National Chung-Cheng University, Jay-Yi, Taiwan R.O.C. - 2 -
at fault undetectable (redundant) and therefore it can be removed.
Finally, the technique checks whether a candidate connection is
redundant, i.e., whether adding the non-existing wire preserves the
circuits functionality. Only when the candidate connection is ver-
ified as redundant, the target wire can be replaced by the candidate
connection. For example, consider finding an alternative wire for
wire
c->g
2
in Fig. 1. Let us first check wire
c->g
2
s-a-1 test. To
propagate the fault effect and to activate the fault, the value
assignments {
a=1, b=1, d=0, e=1, c=0, g
1
=0, o
3
=1} must be set.
These assignments are called the
mandatory assignments (MAs)
for
c->g
2
s-a-1 test. If the (non-existing) wire
g
1
->
g
5
is added to
the circuit, the MA of
g
1
=0 will cause node
g
5
to have the MA of
0 which blocks the fault propagation and cause the fault undetect-
able. So, wire
g
1
->g
5
is identified as a candidate connection.
Finally, the technique checks whether
g
1
->g
5
s-a-1 is redundant.
Since it is redundant, wire
g
1
->g
5
is an alternative wire for
c->g
2
.
In the Alwire procedure, if there are
k candidate connections, it
requires
k times of redundancy checking to find all possible alter-
native wires. In the case of simultaneously replacing
l wires which
all have
k candidates, the complexity will be O(k
l
). In a large cir-
cuit, the value
k can be very large. Therefore, directly applying the
Alwire technique for multiple wire replacement is very costly.
3 Gate support replacement
In this section, we discuss a transformation which replaces
multiple wires at the same time. The transformation is termed the
alternative node technique (Alnode) in which we attempt to
replace the input wires of a node by a new set of input wires. The
size of a new set can be larger or smaller than the original set. For
example, in Fig. 2, the inputs of node
g, (e, f) can be replaced by
the new set of inputs
(o, p, q). In this case, after replacement,
nodes
e can be removed from the circuit. Sometimes, Alnode may
lead to area reduction or good routing results.
Before we discuss the procedure for
Alnode, we would like to
distinguish different types of MAs. We define the
observability
MAs of wire w, obvMAs(w) to be MAs assigned only for propagat-
ing a fault from wire
w to a Primary Output (PO). For example, in
Fig. 2, to propagate a fault from wire
g->i to a PO, the observabil-
ity MAs
obvMAs(g->i)={h=0, s=0, l=0, j=1} must be set. Simi-
larly, we can define the observability MAs of node
n, obvMAs(n),
so that a fault can be propagated from
n to a PO. The process of
finding the MAs of a wire
n->m s-a-1 test can be divided into two
steps. First, we set up the observability MAs for wire
n->m, obv-
MAs(n->m); then we assign the activating value of 0 at node n and
derive more MAs from MA
n=0. We define the MAs derived by
MA
n=0 (including n=0) to be the activating derived MAs, act-
DrvMAs(n=0). Therefore, the MAs of n->m s-a-1 test is equal to
obvMAs(n->m) actDrvMAs(n=0). For example in Fig. 2, the
MAs for wire
g->i s-a-1 test is equal to obvMAs(g->i) actDrv-
MAs(g=0) where obvMAs(g->i) = {h=0, s=0, l=0, j=1}. The set
actDrvMAs(g=0) can be determined from the following: Under
the observability conditions of
{h=0, s=0, l=0, j=1}, we assign
MA
g=0 which can lead to MAs {e=0, f=0}. We then show MA
e=0 can lead to MA q=0 in Fig. 3.
Due to space limitation, we do not show other derivations of MAs.
However, using the similar technique (recursive learning [8]), one
can derive {
o=0, p=0, q=0, t=0} from {e=0, f=0}. As a result, we
have
actDrvMAs(g=0) = {g=0, e=0, f=0, o=0, p=0, q=0, t=0}.
The MAs in
actDrvMAs(g=0) are MAs implied from g=0 under
the conditions of observability MAs. Intuitively, one can consider
that a node in
actDrvMAs(g=0) has some relation with node g.
Now, we present our
Alnode algorithm. This algorithm
attempts to replace node
n by a new node n whose support set is
different from those of node
n. Node n is called an alternate node
for
n. We also assume that none of the input wires of node n and
n are redundant. For ease of discussion, let us assume that node n
is a 2-input OR gate with input nodes {
u, v} and its alternative
node
n is a 3-input OR gate with input nodes {x, y, z}. Therefore,
our objective is to select three nodes from existing nodes in a cir-
cuit to replace the old set {
u, v}. For the case of AND gates or
other size of inputs, this can be easily derived. In order to replace
node
n by a new node n, the following lemma must be satisfied.
Lemma 1: Suppose the observability MAs obvMAs(n) are set
first. If node
n can replace node n, then,
MA
n=0 must imply MA n=0, and
(EQ 1)
MA
n=1 must imply MA n=1
(EQ 2)
Lemma 1 states that, if a Primary Input (PI) vector evaluates a
0 (1) at node
n, the vector must also evaluate a 0 (1) at an alterna-
tive node
n under the condition that the vector can propagate a
fault from
n to a PO. Therefore, to check whether node n with a
new se