Decomposition and technology mapping of speed-independent circuits using Boolean relations.
Presents a new technique for the decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed method iteratively performs Boolean decomposition of each such gate F into a two-input combinational or sequential gate G, which is available in the library, and two gates H/sub 1/ and H/sub 2/, which are simpler than F, while preserving the original behavior and speed-independence of the circuit. To extract functions for H/sub 1/ and H/sub 2/, the method uses Boolean relations, as opposed to the less powerful algebraic factorization approach used in previous methods. After logic decomposition, overall library matching and optimization is carried out. Logic resynthesis, performed after speed-independent signal insertion for H/sub 1/ and H/sub 2/, allows for the sharing of decomposed logic. Overall, this method is more general than existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping.
Introduction
Speed-independent circuits, originating from D.E. Muller's work [12], are hazard-free under the unbounded
gate delay model . With recent progress in developing efficient analysis and synthesis techniques, supported
by CAD tools, this sub-class has moved closer to practice, bearing in mind the advantages of speed-
independent designs, such as their greater temporal robustness and self-checking properties.
The basic ideas about synthesis of speed-independent circuits from event-based models, such as Signal
Transition Graphs (STGs) and Change Diagrams, are described e.g. in [4, 9, 6]. They provide general
conditions for logic implementability of specifications into complex gates . The latter are allowed to have
an arbitrary fanin and include internal feedback (their Boolean functions being self-dependent).
To achieve greater practicality, synthesis of speed-independent circuits has to rely on more realistic
assumptions about implementation logic. Thus, more recent work has been focused on the development
of logic decomposition techniques. It falls into two categories. One of them includes attempts to achieve
logic decomposition through the use of standard architectures (e.g. the standard-C architecture mentioned
below). The other group comprises work targeting the decomposition of complex gates directly, by finding
a behavior-preserving interconnection of simpler gates. In both cases, the major functional issue, in addition
to logic simplification, is that the decomposed logic must not violate the original speed-independent
specification. This criterion makes the entire body of research in logic decomposition and technology
mapping for speed-independent circuits quite specific compared to their synchronous counterparts.
This work has been partially supported by ACiD-WG (ESPRIT 21949), UK EPSRC project ASTI GR/L24038 and
CICYT TIC 95-0419
Two examples of the first category [1, 8] present initial attempts to move from complex gates to a
more structured implementation. The basic circuit architecture includes C elements (acting as latches)
and combinational logic, responsible for the computation of the excitation functions for the latches.
This logic is assumed to consist of AND gates with potentially unbounded fain and unlimited input
inversions and bounded fanin OR gates. Necessary and sufficient conditions for implementability of
circuits in such an architecture (called the standard-C architecture), have been formulated in[8, 1]. They
are called Monotonic Cover (MC) requirements. The intuitive objective of the MC conditions is to
make the first level (AND) gates work in a one-hot fashion with acknowledgment through one of the C-
elements. Following this approach, various methods for speed-independent decomposition and technology
mapping into implementable libraries have been developed,e.g. in [14] and [7]. The former method only
decomposes existing gates (e.g., a 3-input AND into two 2-input ANDs), without any further search of
the implementation space. The latter method extends the decomposition to more complex (algebraic)
divisors, but does not tackle the limitation inherent in the initial MC architecture.
The best representative of the second category appears to be the work of S. Burns [3]. It provides
general conditions for speed-independent decomposition of complex (sequential) elements into two sequential
elements (or a sequential and a combinational element). Notably, these conditions are analyzed
using the original (unexpanded) behavioral model, thus improving the efficiency of the method. This
work is, in our opinion, a big step in the right direction, but addresses mainly correctness issues. It does
not describe how to use the efficient correctness checks in an optimization loop, and does not allow the
sharing of a decomposed gate by different signal networks. The latter issues were successfully resolved in
but only within a standard architecture approach.
In [15, 13] methods for technology mapping of fundamental mode and speed-independent circuits
using complex gates were presented. These methods however only identify when a set of simple logic
gates can be implemented as a complex gate, but cannot perform a speed-independent decomposition of
a signal function in case it does not fit into a single gate. In fact, a BDD-based implementation of the
latter is used as a post-optimization step after our proposed decomposition technique.
In our present work we are considering a more general framework which allows use of arbitrary gates
and latches available in the library to decompose a complex gate function, as shown in Figure 1. In that
respect, we are effectively making progress towards the more flexible second approach. The basic idea of
this new method is as follows.
An initial complex gate is characterized by its function F . The result of decomposition is a library
component designated by G and a set of (possibly still complex) gates labeled H . The latter
are decomposed recursively until all elements are found in the library and optimized to achieve the lowest
possible cost. We thus by and large put no restrictions on the implementation architecture in this work.
However, as will be seen further, for the sake of practical efficiency, our implemented procedure deals only
with the 2-input gates and/or latches to act as G-elements in the decomposition. The second important
change of this work compared to [7] is that the new method is based on a full scale Boolean decomposition
rather than just on algebraic factorization. This allows us to widen the scope of implementable solutions
and improve on area cost (future work will tackle performance-oriented decomposition).
Our second goal in generalizing the C-element based decomposition has been to allow the designer
to use more conventional types of latches, e.g. D-latches and SR-latches, instead of C-elements that may
not exist in conventional standard-cell libraries. Furthermore, as our experimental results show (see
Section 6), in many cases the use of standard latches instead of C-elements helps improving the circuit
implementations considerably.
The power of this new method can be appreciated by looking at the example hazard.g taken from
a set of asynchronous benchmarks. The original STG specification and its state graph are shown in

Figure

2,a and b. The initial implementation using the "standard C-architecture" and its decomposition
using two input gates by the method described in [7] are shown in Figure 2,c and d. Our new method
produces a much cheaper solution with just two D-latches, shown in Figure 2,e. Despite the apparent
triviality (for an experienced human designer!) of this solution, none of the previously existing automated
tools has been able to obtain it. Also note that the D-latches are used in a speed-independent fashion,
G
F
Hn
y
y

Figure

1: General framework for speed-independent decomposition
and are thus free from meta-stability and hazard problems 1 .
a,d - inputs
outputs
d
a
z
c
c
d
c
d D
R c
z
R
R c
R c
C z
(a)
c-
z-
a-
a- d-
(b)
a-
a-
d-
d-
z-
c-1000
a-
a z
z a
c
a d
a
d c
c
z
a z
a
z
c
z
d
(c) (d)

Figure

2: An example of Signal Transition Graph (a), State Graph (b) and their implementation (c)(d)(e)
(benchmark hazard.g)
The paper is organized as follows. Section 2 introduces the main theoretical concepts and notation.
Section 3 presents an overview of the method. Section 4 describes the major aspects of our Boolean
relation-based decomposition technique in more detail. Section 5 briefly describes its algorithmic imple-
mentation. Experimental results are presented in Section 6, which is followed by conclusions and ideas
about further work.
Background
In this section we introduce theoretical concepts and notation required for our decomposition method.
Firstly, we define State Graphs , which are used for logic synthesis of speed-independent circuits. The
State Graph itself may of course be generated by a more compact, user-oriented model, such as the
Signal Transition Graph. The State Graph provides the logic synthesis procedure with all information
necessary for deriving Boolean functions for complex gates. Secondly, the State Graph is used for a
property-preserving transformation, called signal insertion. The latter is performed when a complex
gate is decomposed into smaller gates, and the thus obtained new signals must be guaranteed to be
speed-independent (hazard-free in input/output mode using the unbounded gate delay model).
1 For example, all transitions on the input must be acknowledged by the output before the clock can fall and close the
latch. E.g. there is no problem with setup and hold times as long as the propagation time from D to Q is larger than both
setup and hold times, which is generally the case.
2.1 State Graphs and Logic Implementability
A State Graph (SG) is a labeled directed graph whose nodes are called states . Each arc of an SG is
labeled with an event , that is a rising (a+) or falling (a\Gamma) transition of a signal a in the specified circuit.
We also allow notation a  if we are not specific about the direction of the signal transition. Each state
is labeled with a vector of signal values. An SG is consistent if its state labeling v is such
that: in every transition sequence from the initial state, rising and falling transitions alternate for each
signal. Figure 2,b shows the SG for the Signal Transition Graph in Figure 2,a, which is consistent. We
write s a
there is an arc from state s (to state s 0 ) labeled with a.
The set of all signals whose transitions label SG arcs are partitioned into a (possibly empty) set of
inputs, which come from the environment, and a set of outputs or state signals that must be implemented.
In addition to consistency, the following two properties of an SG are needed for their implementability in
a speed-independent logic circuit.
The first property is speed-independence. It consists of three parts: determinism, commutativity and
output-persistence. An SG is called deterministic if for each state s and each label a there can be at most
one state s 0 such that s a
An SG is called commutative if whenever two transitions can be executed
from some state in any order, then their execution always leads to the same state, regardless of the order.
An event a   is called persistent in state s if it is enabled at s and remains enabled in any other state
reachable from s by firing another event b   . An SG is called output-persistent if its output signal events
are persistent in all states and no output signal event can disable input events. Any transformation (e.g.,
insertion of new signals for decomposition), if performed at the SG level, may affect all three properties.
The second requirement, Complete State Coding (CSC), becomes necessary and sufficient for the
existence of a logic circuit implementation. A consistent SG satisfies the CSC property if for every pair of
states s; s 0 such that the set of output events enabled in both states is the same. (The SG
in

Figure

2,b is output-persistent and has CSC.) CSC does not however restrict the type of logic function
implementing each signal. It requires that each signal is cast into a single atomic gate. The complexity
of such a gate can however go beyond that provided in a concrete library or technology.
The concepts of excitation regions and quiescent regions are essential for transformation of SGs, in
particular for inserting new signals into them. A set of states is called an excitation region (ER) for event
a   (denoted by ER(a   it is the set of states such that s 2 ER(a   ) , s a
!. The quiescent region (QR)
(denoted by QR(a   )) of a transition a   , with excitation region ER(a   ), is the set of states in which a is
stable and keeps the same value, i.e. for ER(a+) (ER(a\Gamma) ), a is equal to 1(0) in QR(a+) (QR(a\Gamma)).
Examples of ER and QR are shown in Figure 2,b.
2.2 Property-preserving event insertion
Our decomposition method is essentially behavioral - the extraction of new signals at the structural
(logic) level must be matched by an insertion of their transitions at the behavioral (SG) level. Event
insertion is an operation on an SG which selects a subset of states, splits each of them into two states and
creates, on the basis of these new states, an excitation region for a new event. Figure 3 shows the chosen
insertion scheme, analogous to that used by most authors in the area [16]. We shall say that an inserted
signal a is acknowledged by a signal b, if b is one of the signals delayed by the insertion of a, (the same
terminology will be used for the corresponding transitions). For example, d acknowledges x in Figure 3.
State signal insertion must preserve the speed-independence of the original specification. The events
corresponding to an inserted signal x are denoted x , x+, x\Gamma, or, if no confusion occurs, simply by x.
Let A be a deterministic, commutative SG and let A 0 be the SG obtained from A by inserting event x.
We say that an insertion state set ER(x) in A is a speed-independence preserving set (SIP-set) iff: (1)
for each event a in A, if a is persistent in A, then it remains persistent in A 0 , and (2) A 0 is deterministic
and commutative. The formal conditions for the set of states r to be a SIP-set can be given in terms of
intersections of r with the so-called state diamonds of SG [5]. These conditions are illustrated by Figure
4, where all possible cases of illegal intersections of r with state diamonds are shown. The first (rather
(a)
d c b a
(b)
d
x

Figure

3: Event insertion scheme: (a) before insertion, (b) after insertion
inefficient) method for finding SIP-sets based on a reduction to the satisfiability problem was proposed
in [16]. An efficient method based on the theory of regions has been described in [5].
d
r
a
d
a
s3 d
d
a
r
d
a
r
d
a) b) c)

Figure

4: Possible violations of SIP conditions
Assume that the set of states S in an SG is partitioned into two subsets which are to be encoded by
means of an additional signal. This new signal can be added either in order to satisfy the CSC condition,
or to break up a complex gate into a set of smaller gates. In the latter case, a new signal represents the
output of the intermediate gate added to the circuit. Let r and r denote the blocks of such a
partition. For implementing such a partition we need to insert transitions of the new signals in the border
states between r and r.
The input border of a partition block r, denoted by IB(r), is informally a subset of states of r by which
r is entered. We call IB(r) well-formed if there are no arcs leading from states in r \Gamma IB(r) to states in
IB(r). If a new signal is inserted using an input border, which is not well-formed, then the consistency
property is violated. Therefore, if an input border is not well-formed, its well-formed speed-independent
preserving closure is constructed, as described by an algorithm presented in [7].
The insertion of a new signal can be formalized with the notion of I-partition ([16] used a similar
definition). Given an SG, A, with a set of states S, an I-partition is a partition of S into four blocks:
QR(x\Gamma)g. QR(x\Gamma)(QR(x+)) defines the states in which x will have the
stable value 0 (1). ER(x+) (ER(x\Gamma)) defines the excitation region of x in the new SG A 0 . To distinguish
between the sets of states for the excitation (quiescent) regions of the inserted signal x in an original
SG A and the new SG A 0 we will refer to them as ERA (x ) and ER A 0
respectively. If the insertion of x preserves consistency and persistency, then the only transitions crossing
boundaries of the blocks are the following: QR(x\Gamma) ! ERA
Example 2.1 Figure 5 shows three different cases of the insertion of a new signal x into the SG for
the hazard.g example. The insertion using ERA (x+) and ERA (x\Gamma) of Figure 5,a does not preserve
speed-independence as the SIP set conditions are violated for ERA (x+) (violation type in Figure 4,b).
When signal x is inserted by the excitation regions in Figure 5,b then its positive switching is acknowledged
by transitions a\Gamma, d+, while its negative switching by transition z \Gamma. The corresponding excitation
regions satisfy the SIP conditions and the new SG A 0 , obtained after insertion of signal x, is shown in

Figure

5,b. Note that the acknowledgment of x+ by transitions a\Gamma, d+ results in delaying some input
signal transitions in A 0 until x+ fires. This changes the original I/O interface for SG A, because it
requires the environment to look at a new signal before it can change a and d. This is generally incorrect
(unless we are also separately finding an implementation for the environment or we are working under
appropriate timing assumptions), and hence this insertion is rejected.
a,d - inputs
outputs a+
a-
a-
d-
d-
z-
c-1000
a-
A
A
a-
a-
d-
d-
c-
a-
a-
a-
a-
d-
d-
z-
c-1000
a-
(a)
A
A
A'
x-
x-
z-
(b)
A'
a-
a-
d-
d-
z-
c-1000
a-
A
A
(c)

Figure

5: Different cases of signal insertion for benchmark hazard.g: violating the SIP-condition (a),
changing the I/O interface (b), correct insertion (c)
The excitation regions ERA (x+) and ERA (x\Gamma) shown in Figure 5,c are SIP sets. They are well-formed
and comply with the original I/O interface because positive and negative transitions of signal x
are acknowledged only by output signal z. This insertion scheme is valid.
2.3 Basic definitions about Boolean Functions and Relations
An important part of our decomposition method is finding appropriate candidates for characterization
(by means of Boolean covers) of the sets of states ERA (x+) and ERA (x\Gamma) for the inserted signal x. For
this, we need to reference here several important concepts about Boolean functions and relations [11].
An incompletely specified (scalar) Boolean function is a functional mapping
and '\Gamma' is a don't care value. The subsets of domain B n in which F holds the 0, 1
and don't care value are respectively called the OFF-set , ON-set and DC-set . F is completely specified
if its DC-set is empty. We shall further always assume that F is a completely specified Boolean function
unless said otherwise specifically.
be a Boolean function of n Boolean variables. The set is
called the support of the function F . In this paper we shall mostly be using the notion of true support ,
which is defined as follows. A point (i.e. binary vector of values) in the domain B n of a function F is
called a minterm. A variable x 2 X is essential for function F (or F is dependent on x) if there exist at
least two minterms v1; v2 different only in the value of x, such that F (v1) 6= F (v2). The set of essential
variables for a Boolean function F is called the true support of F and is denoted by sup(F ). It is clear
that for an arbitrary Boolean function its support may not be the same as the true support. E.g., for a
c the true support of F (X) is sup(F
a subset of X .
Let F (X) be a Boolean function F (X) with support g. The cofactor of F (X) with
respect to x i defined as F x i
respectively). The well-known Shannon expansion of a Boolean function F (X) is based on its cofactors:
. The Boolean difference, or Boolean derivative, of F (X) with respect to x
defined as ffiF
do
1: foreach non-input signal x do
solutions(x):=;;
2: foreach gate G 2 flatches, and2, or2g do
endfor
3: best H(x) := Best SIP candidate from solutions(x);
endfor
4: if foreach x, best H(x) is implementable
or foreach x, best H(x) is empty then exit loop;
5: Let H be the most complex best H(x);
Insert new signal z implementing H and derive new SG;
forever
7: Library matching;

Figure

Algorithm for logic decomposition and technology mapping.
A function F
or F x i
under
ordering In the former case
it is called positive unate in x i , in the latter
case negative unate in x i . A function that is not unate in x i is called binate in x i . A function is
(positive/negative) unate if it is (positive/negative) unate in all support variables. Otherwise it is binate.
For example, the function positive unate in variable a because F a
For an incompletely specified function F (X) with a DC-set, let us define the DC function FDC :
We will say that a function e
F is an implementation of F if
Boolean relation is a relation between Boolean spaces [2, 11]; it can be seen as a generalization of a
Boolean function, where a point in the domain B n can be associated with several points in the codomain.
More formally, a Boolean relation R is R ' B n \Theta f0; 1g m . Sometimes, we shall also use the "\Gamma" symbol
as a shorthand in denoting elements in the codomain vector, e.g. 10 and 00 will be represented as one
vector \Gamma0. Boolean relations play an important role in multi-level logic synthesis [11], and we shall use
them in our decomposition method.
Consider a set of Boolean functions with the same domain. Let R '
be a Boolean relation with the same domain as functions from H. We will say that H is compatible
with R if for every point v in the domain of R the vector of values (v; H 1 is an
element of R. An example of compatible functions will be given in Section 4.
3 Overview of the method
In this section we describe our proposed method for sequential decomposition of speed-independent
circuits aimed at technology mapping. It consists of three main steps:
1. Synthesis via decomposition based on Boolean relations;
2. Signal insertion and generation of a new SG;
3. Library matching
The first two steps are iterated until all functions are decomposed into implementable gates or no
further progress can be made. Each time a new signal is inserted (step 2), resynthesis is performed for all
output signals (step 1). Finally, step 3 collapses decomposed gates and matches them with library gates.
The pseudo-code for the technology mapping algorithm is given in Figure 6.
By using a speed-independent initial SG specification, a complex gate implementation of the Boolean
function for each SG signal is guaranteed to be speed-independent. Unfortunately this gate may be too
large to be implemented in a semi-custom library or even in full custom CMOS, e.g. because it requires
too many stacked transistors. The goal of the proposed method is to break this gate starting from its
output by using sequential (if its function is self-dependent, i.e. it has internal feedback) or combinational
gates.
Given a vector X of SG signals and given one non-input signal y 2 X (in general the function F (X) for
y may be self-dependent), we try to decompose the function F (X) into (line 2 of algorithm in Figure 6):
ffl a combinational or sequential gate with function G(Z; y), where Z is a vector of newly introduced
signals,
ffl a vector of combinational 2 functions H(X) for signals Z,
so that G(H(X)) implements F (X). Moreover, we require the newly introduced signals to be speed-
independent (line 3). We are careful not to introduce any unnecessary fanouts due to non-local ac-
knowledgment, since they would hinder successive area recovery by gate merging (when allowed by the
library).
The problem of representing the flexibility in the choice of the H functions has been explored, in the
context of combinational logic minimization, by [19] among others. Here we extend its formulation to
cover also sequential gates (in Sections 4.1 and 4.3). This is essential in order to overcome the limitations
of previous methods for speed-independent circuit synthesis that were based on a specific architecture.
Now we are able to use a broad range of sequential elements, like set and reset dominant SR latches,
transparent D latches, and so on. We believe that overcoming this limitation of previous methods (that
could only use C elements and dual-rail SR-latches) is one of the major strengths of this work. Apart
from dramatically improving some experimental results, it allows one to use a "generic" standard-cell
library (that generally includes SR and D latches, but not C elements) without the need to design and
characterize any new asynchronous-specific gates.
The algorithm proceeds as follows. We start from an SG and derive a logic function for all its non-input
signals (line 1). We then perform an implementability check for each such function as a library
gate. The largest non-implementable function is selected for decomposition. In order to limit the search
space, we currently try as candidates for G (line 2):
ffl all the sequential elements in the library (assumed to have two inputs at most, again in order to
limit the search space),
ffl two-input AND, OR gates with all possible input inversions.
The flexibility in the choice of functions represented as a Boolean relation, that represents
the solution space of F described in Section 4.1.
The set of function pairs compatible with the Boolean relation is then checked for speed-
independence (line 3), as described in Section 2.2. This additional requirement has forced us to implement
a new Boolean relation minimizer, that returns all compatible functions , as outlined in Section 5.1. If
both are not speed-independent, the pair is immediately rejected.
Then, both H 1 and H 2 are checked for approximate (as discussed above) implementability in the
library, in increasing order of estimated cost. We have two cases:
1. both are speed-independent and implementable: in this case the decomposition is accepted,
2. otherwise, the most complex implementable H i is selected, and the other one is merged with G.
2 The restriction that H(X) be combinational will be partially lifted in Section4.3.
The latter is a heuristic technique aimed at keeping the decomposition balanced. Note that at this stage
we can also implement H 1 or H 2 as a sequential gate if the sufficient conditions described in Section 4.3
are met.
The procedure is iterated as long as there is progress or until everything has been decomposed (line
4). Each time a new function H i is selected to be implemented as a new signal, it is inserted into the SG
(line and resynthesis is performed in the next iteration.
The incompleteness of the method is essentially due to the greedy heuristic search that accepts
the smallest implementable or non-implementable but speed-independent solution. We believe that an
exhaustive enumeration with backtracking would be complete even for non-autonomous circuits, by a
relatively straightforward extension of the results in [17].
At the end, we perform a Boolean matching step ([10]) to recover area and delay (line 7). This step
can merge together the simple 2-input combinational gates that we have (conservatively) used in the
decomposition into a larger library gate. It is guaranteed not to introduce any hazards if the matched
gates are atomic.
4 Logic decomposition using Boolean relations
4.1 Specifying permissible decompositions with BRs
In this paper we apply BRs to the following problem.
Given an incompletely specified Boolean function F (X) for signal y, y 2 X, decompose it into two-levels
such that G(H(X); y) implements F (X) and functions G and H have a simpler
implementation than F (any such H will be called permissible).
Note that the first-level function (X)g is a multi-output logic function, specifying
the behavior of internal nodes of the decomposition,
The final goal is a function decomposition to a form that is easily mappable to a given library. Hence
only functions available in the library are selected as candidates for G. Then at each step of decomposition
a small mappable piece (function G) is cut from the potentially complex and unmappable function F .
For a selected G all permissible implementations of function H are specified with a BR and then via
minimization of BRs a few best compatible functions are obtained. All of them are verified for speed-
independence by checking SIP-sets. The one which is speed-independent and has the best estimated cost
is selected.
Since the support of function F can include the output variable y, it can specify sequential behavior.
In the most general case we perform two-level sequential decomposition such that both function G and
function H can be sequential, i.e., contain their own output variables in the supports. The second level
of the decomposition is made sequential by selecting a latch from the library as a candidate gate, G. The
technique for deriving a sequential solution for the first level H is described in Section 4.3.
We next show by example how all permissible implementations of decomposition can be expressed
with BRs.
Example 4.1 Consider the STG in Figure 7,a, whose SG appears in Figure 8,a. Signals a, c and d
are inputs and y is an output. A possible implementation of the logic function for y is F (a; c; d;
us decompose this function using as G a reset-dominant Rs-latch represented by
the equation Figure 7,b). At the first step we specify the permissible
implementations for the first level functions by using the BR specified in the table
in

Figure

8,b. Consider, for example, vector a; c; d; It is easy to check that F(0; 0; 0;
Hence, for vector 0000 the table specifies that (R; implementation
of R and S must keep for this input vector either 1 at R or 0 at S, since these are the necessary and
3 For simplicity we consider the decomposition problem for a single-output binary function F , although generalization for
the multi-output and multi-valued functions is straightforward.
y
d D
Rs
c
dc+yc
Rs
a
Rs
Rs
d-
a-
c-
a-
y
y
G
R
c
d
y
a)
c)
d) e)
R
y
d
c
a S
R
c
a d

Figure

7: Sequential decomposition for function d)
Region C-element D-latch Rs Sr AND OR
QR(y\Gamma) f0\Gamma; \Gamma0g f0\Gamma; \Gamma0g f1\Gamma; \Gamma0g 0\Gamma f0\Gamma; \Gamma0g 00
unreachable \Gamma\Gamma \Gamma\Gamma \Gamma\Gamma \Gamma\Gamma \Gamma\Gamma \Gamma\Gamma

Table

1: Boolean relations for different gates
sufficient conditions for the Rs-latch to keep the value 0 at the output y, as required by the specification.
On the other hand, only one solution possible for the input vector 1100 which corresponds
to setting the output of the Rs-latch to 1. The Boolean relation solver will find, among others, the two
solutions illustrated in Figure 7,c,d: (1) a and (2) acd. Any of these
solutions can be chosen depending on the cost function.

Table

specifies compatible values of BRs for different types of gates: a C-element, a D-latch, a
reset-dominant Rs-latch, a set-dominant Sr-latch, a two input AND gate and a two input
states of an SG are partitioned into four subsets, ER(y+); QR(y+);ER(y \Gamma); and QR(y \Gamma), with respect
to signal y with function F (X) for which decomposition is performed. All states that are not reachable
in the SG form a DC-set for the BR. E.g., for each state, s, from ER(y+) only one compatible solution,
11, is allowed for input functions H of a C-element. This is because the output of a C-element in
all states, s 2 ER(y+) is at 0 and F these conditions the combination 11 is the only
possible input combination that implies 1 at the output of a C-element. On the other hand, for each
state s 2 QR(y+), the output hence it is enough to keep at least one input of a
C-element in 1. This is expressed by values f1\Gamma; \Gamma1g in the second line of the table. Similarly all other
compatible values are derived.
4.2 Functional representation of Boolean relations
Given an SG satisfying CSC requirement, each output signal y 2 X is associated with a unique incompletely
specified function F (X), whose DC-set represents the set of unreachable states. F (X) can
be represented by three completely specified functions, denoted ON(y)(X), OFF (y)(X) and DC(y)(X)
representing the ON-, OFF-, and DC-set of F (X), such that they are pairwise disjoint and their union
is a tautology.
c-
c-
d-
a-
c-
c- d+
a-
a-
a-
ON(y)
a,c,d,y
(a)
acdy F R S
(b)

Figure

8: (a) State graph, (b) Decomposition of signal y by an RS latch
Let a generic n-input gate be represented by a Boolean equation
are the inputs of the gate, and q is its output 4 . The gate is sequential if q belongs to the true support of
G(Z; q).
We now give the characteristic function of the Boolean relation for the implementation of F (X) with
gate G. This characteristic function represents all permissible implementations of z
allow F to be decomposed by G.
Given characteristic function (1), the corresponding table describing Boolean relation can be derived
using cofactors. For each minterm m with support in X , the cofactor BR(y)m gives the characteristic
function of all compatible values for z (see example below).
Finding a decomposition of F with gate G is reduced to finding a set of n functions
Example 4.2 (Example 4.1 continued.) The SG shown in Figure 8.a corresponds to the STG in Figure
7. Let us consider how the implementation of signal y with a reset-dominant Rs latch can be expressed
using the characteristic function of BR. Recall that the table shown in Figure 8.b represents the function
F (a; c; d; and the permissible values for the inputs R and S of the Rs latch. The ON-,
OFF-, and DC-sets of function F (a; c; d; y) are defined by the following completely specified functions:
4 In the context of Boolean equations representing gates we shall liberally use the "=" sign to denote "assignment", rather
than mathematical equality. Hence q in the left-hand side of this equation stands for the next value of signal q while the
one in the right-hand side corresponds to its previous value.
The set of permissible implementations for R and S is characterized by the following characteristic
function of the BR specified in the table. It can be obtained using equation 1 by substituting expressions
for ON(y); OFF (y); DC(y), and the function of an Rs-latch, R(S
BR(y)(a; c; d; (R
This function has value 1 for all combinations represented in the table and value 0 for all combinations
that are not in the table (e.g., for (a; c; d; For example, the set of compatible values
for given by the cofactor
which correspond to the terms 1\Gamma and \Gamma0 given for the Boolean relation for that minterm.
Two possible solutions for the equation BR(y)(a; c; d; corresponding to Figure 7,c,d are:
4.3 Two-level sequential decomposition
Accurate estimation of the cost of each solution produced by the Boolean relation minimizer is essential
in order to ensure the quality of the final result. The minimizer itself can only handle combinational logic,
but often (as shown below) the best solution can be obtained by replacing a combinational gate with a
sequential one. This section discusses some heuristic techniques that can be used to identify when such a
replacement is possible without altering the asynchronous circuit behavior, and without undergoing the
cost of a full-blown sequential optimization step. Let us consider our example again.
Example 4.3 (Example 4.1 continued.) Let us assume that the considered library contains three-input
AND, OR gates and Rs-, Sr- and D-latches. Implementation (1) of signal y by an Rs-latch with
inputs R=cd and S=acd matches the library and requires two AND gates (one with two and one with
three inputs) and one Rs-latch. The implementation (2) of y by an Rs-latch with inputs R=cd+ y c and
S=a would be rejected, as it requires a complex AND-OR gate which is not in the library. However, when
input y in the function cd replaced by signal R, the output behavior of R will not change, i.e.
function R=cd+ y c can be safely replaced by R=cd+Rc. The latter equation corresponds to the function
of a D-latch and gives the valid implementation shown in Figure 7,e.
Our technique to improve the precision of the cost estimation step, by partially considering sequential
gates, is as follows:
1. Produce permissible functions z via the minimization of Boolean
relations (z 1 and z 2 are always combinational as z 1 ; z 2 62 X).
2. Estimate the complexity of H 1 and
matches the library then Complexity = cost of the gate else Complexity = literal count
3. Estimate the possible simplification of H 1 and H 2 due to adding signals z 1 and z 2 to their supports,
i.e. estimate the complexity of the new pair fH 0
2 g of permissible functions z
4. Choose the best complexity between H 1
Let us consider the task of determining H 0
2 as in step 3. Let A be an SG encoded by variables
from set V and let z = H(X; y), such that X ' V; y 2 V , be an equation for the new variable z
which is to be inserted in A. The resulting SG is denoted A 0 =Ins(A; z=H(X; y)) (sometimes we will
simply A 0 =Ins(A; z) or A 0 =Ins(A; z one signal is inserted).
A solution for Step 3 of the above procedure can be obtained by minimizing functions for signals
z 1 and z 2 in an SG A However this is rather inefficient because the creation of SG
A 0 is computationally expensive. Hence instead of looking for an exact estimation of complexity for
signals z 1 and z 2 we will rely on a heuristic solution, following the ideas on input resubstitution presented
in Example 4.3. For computational efficiency, the formal conditions on input resubstitution should be
formulated in terms of an original SG A rather than in terms of the SG A 0 obtained after the insertion of
new signals 5 .
Lemma 4.1 Let Boolean function H(X; y) implement the inserted signal z and be positive (negative)
unate in y. Let H 0 (X; z) be the function obtained from H(X; y) by replacing each literal y (or y) by
literal z. The SGs A 0 =Ins(A; z=H(X; y)) and A 00 =Ins(A; z=H 0 (X; z)) are isomorphic iff the following
condition is satisfied:
where S   is the characteristic function describing the set of states (ERA (z+) [ ERA (z \Gamma)) in A.
Informally Lemma 4.1 states that resubstitution of input y by z is permissible if in all states where
the value of function H(X; y) depends on y, the inserted signal z has a stable value.
Example 4.4 (Example 4.1 continued.) Let input R of the RS-latch be implemented as cd

Figure

7,d). The ON-set of function H=cd shown by the dashed line in Figure 8,a. The input
border of H is the set of states by which its ON-set is entered in the original SG A, i.e.
By similar consideration we have that f0100g. These input borders satisfy the SIP conditions
and hence IB(H) can be taken as ERA (R+), while ERA (R\Gamma) must be expanded beyond IB(H) by state
1100 for not to delay the input transition a+ (ERA (R\Gamma) = f0100; 1100g).
The set of states where the value of function H essentially depends on signal y is given by the function
negative unate in y and cube ac has no intersection with ERA (R+)[ERA (R\Gamma).
Therefore by the condition of Lemma 4.1 literal y can be replaced by literal R, thus producing a new
permissible function R=cd
This result can be generalized for binate functions, as follows.
Lemma 4.2 Let Boolean function H(X; y) implement the inserted signal z and be binate in y. Function
H can be represented as H(X; are Boolean functions not depending
on y. Let H 0 (X; are
isomorphic iff the following conditions are satisfied:
are characteristic Boolean functions describing sets of states ERA (z+) [ ERA (z \Gamma) and
ERA (z+) in A, respectively.
The proof is given in the Appendix.
The conditions of Lemma 4.2 can be efficiently checked within our BDD-based framework. They
require to check two tautologies involving functions defined over the states of the original SG A. This
heuristic solution is a trade-off between computational efficiency and optimality. Even though the estimation
is still not completely exact (the exact solution requires the creation of A 0 =Ins(A; z)), it allows
us to discover and possibly use the implementation of Figure 7,e.
5 Note that this heuristic estimation covers only the cases when one of the input signals for a combinational permissible
is replaced by the feedback z i
from the output of H i
itself. Other cases can also be investigated, but checking
them would be too complex.
5 Implementation aspects
The method for logic decomposition presented in the previous section has been implemented in a synthesis
tool for speed-independent circuits. The main purpose of such implementation was to evaluate the
potential improvements that could be obtained in the synthesis of speed-independent circuits by using a
Boolean-relation-based decomposition approach. Efficiency of the current implementation was considered
to be a secondary goal at this stage of the research.
5.1 Solving Boolean relations
In the overall approach, it is required to solve BRs for each output signal and for each gate and latch
used for decomposition. Furthermore, for each signal and for each gate, several solutions are desirable in
order to increase the chances to find SIP functions.
Previous approaches to solve BRs [2, 18] do not satisfy the needs of our synthesis method, since (1)
they minimize the number of terms of a multiple-output function and (2) they deliver (without significant
modifications to the algorithms and their implementation) only one solution for each BR. In our case we
need to obtain several compatible solutions with the primary goal of minimizing the complexity of each
function individually . Term sharing is not significant because two-level decomposition of a function is not
speed-independent in general, and hence each minimized function must be treated as an atomic object.
Sharing can be exploited, on the other hand, when re-synthesizing the circuit after insertion of each new
signal. For this reason we devised a heuristic approach to solve BRs. We next briefly sketch it.
Given a BR BR(y)(X; Z), each function H i for z i is individually minimized by assuming that all other
functions will be defined in such a way that H(X) will be a compatible solution for BR. In
general, an incompatible solution may be generated when combining all H i 's. Taking the example of

Figure

8, an individual minimization of R and S could generate the solution
Next, a minterm with incompatible values is selected, e.g. -
d-y for which but only the
compatible values 1\Gamma or \Gamma0 are acceptable. New BRs are derived by freezing different compatible values
for the selected minterm. In this case, two new BRs will be produced with the values 1\Gamma and \Gamma0,
respectively for the minterm - a-c -
d-y. Next, each BR is again minimized individually for each output
function and new minterms are frozen until a compatible solution is obtained.
This approach generates a tree of BRs to be solved. This provides a way of obtaining several compatible
solutions for the same BR. However, the exploration may become prohibitively expensive if the search tree
is not pruned. In our implementation, a branch-and-bound-like pruning strategy has been incorporated
for such purpose. Still, the time required by the BR solver dominates the computational cost of the
overall method in our current implementation. Ongoing research on solving BRs for our framework
is being carried out. We believe that the fact that we pursue to minimize functions individually, i.e.
without caring about term sharing among different output functions, and that we only deal with 2-output
decompositions, may be crucial to derive algorithms much more efficient than the existing approaches.
5.2 Selection of the best decomposition
Once a set of compatible solutions has been generated for each output signal, the best candidate is
selected according to the following criteria (in priority
1. At least one of the decomposed functions must be speed-independent.
2. The acknowledgment of the decomposed functions must not increase the complexity of the implementation
of other signals (see section 5.3).
3. Solutions in which all decomposable functions are implementable in the library are preferred.
4. Solutions in which the complexity of the largest non-implementable function is minimized are
preferred. This criterion helps to balance the complexity of the decomposed functions and derive
balanced tree-like structures rather than linear ones 6 .
5. The estimated savings obtained by sharing a function for the implementation of several output
signals is also considered as a second order priority criterion.
Among the best candidate solutions for all output signals, the function with the largest complexity,
i.e. the farthest from implementability, is selected to be implemented as a new output signal of the SG.
The complexity of a function is calculated as the number of literals in factored form. In case it is
a sequential function and it matches some of the latches of the gate library, the implementation cost is
directly obtained from the information provided by the library.
5.3 Signal acknowledgment and insertion
For each function delivered by the BR solver, an efficient SIP insertion must be found. This reduces
to finding a partition fERA (x+); QRA (x+); ERA (x\Gamma); QRA (x\Gamma)g of the SG A such that ERA (x+) and
ERA (x\Gamma) (that are restricted to be SIP-sets, Section 2.2) become the positive and negative ERs of the
new signal x. QRA (x+) and QRA (x\Gamma) stand for the corresponding state sets where x will be stable and
equal to 1 and 0, respectively.
In general, each function may have several ERA (x+) and ERA (x\Gamma) sets acceptable as ERs. Each one
corresponds to a signal insertion with different acknowledging outputs signals for its transitions. In our
approach, we perform a heuristic exploration seeking for different ERA (x+) and ERA (x\Gamma) sets for each
function. We finally select one according to the following criteria:
ffl Sets that are only acknowledged by the signal that is being decomposed (i.e. local acknowledgment)
are preferred.
ffl If no set with local acknowledgment is found, the one with least acknowledgment cost is selected.
The selection of the ERA (x+) and ERA (x\Gamma) sets is done independently. The cost of acknowledgment
is estimated by considering the influence of the inserted signal x on the implementability of the other
signals. The cost can be either increased or decreased depending on how ERA (x+) and ERA (x\Gamma) are
selected, and is calculated by incrementally deriving the new SG after signal insertion.
As an example consider the SG of Figure 5,c and the insertion of a new signal x for the function
d. A valid SIP set for ERA (x+) would be the set of states f1100; 0100; 1110; 0110g, where the
state f1100g is the input border for the inserted function. A valid SIP set for ERA (x\Gamma) would be the
set of states f1001; 0001g. With such insertion, ERA (x+) will be acknowledged by the transition z+ and
ERA (x\Gamma) by z \Gamma. However, this insertion is not unique. For the sake of simplicity, let us assume that a
and d are also output signals. Then an insertion with ERA would be also valid. In that
case, the transition x+ would be acknowledged by the transitions a\Gamma and d+.
5.4 Library mapping
The logic decomposition of the non-input signals is completed by a technology mapping step aimed
at recovering area and delay based on a technology-dependent library of gates. These reductions are
achieved by collapsing small fanin gates into complex gates, provided that the gates are available in the
library. The collapsing process is based on the Boolean matching techniques proposed by Mailhot et al.
[10], adapted to the existence of asynchronous memory elements and combinational feedback in speed-
independent circuits. The overall technology mapping process has been efficiently implemented based on
the utilization of BDDs.
6 Different criteria, of course, may be used when we also consider the delay of the resulting implementation, since then
keeping late arriving signals close to the output is generally useful and can require unbalanced trees.
6 Experimental results
6.1 Results in decomposition and technology mapping
The method for logic decomposition presented in the previous sections has been implemented and applied
to a set of benchmarks. The results are shown in Table 2.
Circuit signals literals/latches CPU Area non-SI Area SI
I/O old new (secs) lib 1 lib 2 best 2 inp map best
chu150 3/3 14/2 10/1
converta 2/3 12/3 16/4 252 352 312 312 338 296 296
drs
ebergen 2/3 20/3 6/2 4 184 160 160 160 144 144
hazard 2/2 12/2 0/2 1 144 120 120 104 104 104
nak-pa 4/6 20/4 18/2 441 256 248 248 250 344 250
nowick 3/3 16/1 16/1 170 248 248 248 232 256 232
sbuf-ram-write 5/7 22/6 20/2 696 296 296 296 360 338 338
trimos-send 3/6 36/8 14/10 2071 576 480 480 786 684 684
Total 252/52 180/37 4288 3984 3976 4180 4662 3982

Table

2: Experimental results.
The columns "literals/latches" report the complexity of the circuits derived after logic decomposition
into 2-input gates. The results obtained by the method presented in this paper ("new") are significantly
better than those obtained by the method presented in [7] ("old"). Note that the library used for the
"new" experiments was deliberately restricted to D, Sr and Rs latches (i.e. without C-elements, since
they are generally not part of standard cell libraries). This improvement is mainly achieved because of
two reasons:
ffl The superiority of Boolean methods versus algebraic methods for logic decomposition.
ffl The intensive use of different types of latches to implement sequential functions compared to the
C-element-based implementation in [7].
However, the improved results obtained by using Boolean methods are paid in terms of a significant
increase in terms of CPU time. This is the reason why some of the examples presented in [7] have not
been decomposed. We are currently exploring ways to alleviate this problem by finding new heuristics to
solve Boolean relations efficiently.
6.2 The cost of speed independence
The second part of Table 2 is an attempt to evaluate the cost of implementing an asynchronous specification
as a speed-independent circuit. The experiments have been done as follows. For each bench-
mark, the following script has been run in SIS, using the library asynch.genlib: astg to f; source
script.rugged; map. The resulting netlists could be considered a lower bound on the area of the circuit
regardless of its hazardous behavior (i.e. the circuit only implements the correct function for each output
signal, without regard to hazards). script.rugged is the best known general-purpose optimization script
for combinational logic. The columns labeled "lib 1" and "lib 2" refer to two different libraries, one biased
towards using latches instead of combinational feedback 7 , the other one without any such bias.
The columns labeled SI report the results obtained by the method proposed in this paper. Two
decomposition strategies have been experimented before mapping the circuit onto the library:
ffl Decompose all gates into 2-input gates (2 inp).
ffl Decompose only those gates that are not directly mappable into gates of the library (map).
In both cases, decomposition and mapping preserve speed independence, since we do not use gates (such
as MUXes) that may have a hazardous behavior when the select input changes. There is no clear evidence
that performing an aggressive decomposition into 2-input gates is always the best approach for technology
mapping. The insertion of multiple-fanout signals offers opportunities to share logic in the circuit, but
also precludes the mapper from taking advantage of the flexibility of mapping tree-like structures. This
trade-off must be better explored in forthcoming work.
Looking at the best results for non-SI/SI implementations, we can conclude that preserving speed
independence does not involve a significant overhead. In our experiments we have shown that the reported
area is similar. Some benchmarks were even more efficiently implemented by using the SI-preserving
decomposition. We impute these improvements to the efficient mapping of functions into latches by
using Boolean relations.
7 Conclusions and future work
In this paper we have shown a new solution to the problem of multi-level logic synthesis and technology
mapping for asynchronous speed-independent circuits. The method consists of three major parts. Part 1
uses Boolean relations to compute a set of candidates for logic decomposition of the initial complex gate
circuit implementation. Thus each complex gate F is iteratively split into a two-input combinational
or sequential gate G available in the library and two gates H 1 and H 2 that are simpler than F , while
preserving the original behavior and speed-independence of the circuit. The best candidates for H 1 and
are selected for the next step, providing the lowest cost in terms of implementability and new signal
insertion overhead. Part 2 of the method performs the actual insertion of new signals for H 1 and/or H 2
into the state graph specification, and re-synthesizes logic from the latter. Thus parts 1 and 2 are applied
to each complex gate that cannot be mapped into the library. Finally, Part 3 does library matching to
recover area and delay. This step can collapse into a larger library gate the simple 2-input combinational
gates (denoted above by G) that have been (conservatively) used in decomposing complex gates. No
violations of speed-independence can arise if the matched gates are atomic.
This method improves significantly over previously known techniques [1, 8, 7]. This is due to the
significantly larger optimization space exploited by using (1) Boolean relations for decomposition and (2)
a broader class of latches 8 . Furthermore, the ability to implement sequential functions with SR and D
latches significantly improves the practicality of the method. Indeed one should not completely rely, as
earlier methods did, on the availability of C-elements in a conventional library.
In the future we are planning to improve the Boolean relation solution algorithm, aimed at finding
a set of optimal functions compatible with a Boolean relation. This is essential in order to improve the
CPU times and synthesize successfully more complex specifications.



--R

Automatic gate-level synthesis of speed-independent circuits
An exact minimizer for boolean relations.
General conditions for the decomposition of state holding elements.
Synthesis of Self-timed VLSI Circuits from Graph-theoretic Specifications
Complete state encoding based on the theory of regions.
Concurrent Hardware.
Technology mapping for speed- independent circuits: decomposition and resynthesis
Basic gate implementation of speed-independent circuits
Algorithms for synthesis and testing of asynchronous circuits.
Algorithms for technology mapping based on binary decision diagrams and on boolean operations.
Synthesis and Optimization of Digital Circuits.
A theory of asynchronous circuits.
Structural methods for the synthesis of speed-independent circuits
Decomposition methods for library binding of speed-independent asynchronous designs
Automatic technology mapping for generalized fundamental mode asynchronous designs.
A generalized state assignment theory for transformations on Signal Transition Graphs.

Heuristic minimization of multiple-valued relations
Permissible functions for multioutput components in combinational logic optimization.
--TR
Automatic technology mapping for generalized fundamental-mode asynchronous designs
Decomposition methods for library binding of speed-independent asynchronous designs
Basic gate implementation of speed-independent circuits
A generalized state assignment theory for transformation on signal transition graphs
Automatic gate-level synthesis of speed-independent circuits
Synthesis and Optimization of Digital Circuits
Algorithms for Synthesis and Testing of Asynchronous Circuits
General Conditions for the Decomposition of State-Holding Elements
Complete State Encoding Based on the Theory of Regions
Technology Mapping for Speed-Independent Circuits
Structural Methods for the Synthesis of Speed-Independent Circuits

--CTR
Jordi Cortadella , Michael Kishinevsky , Alex Kondratyev , Luciano Lavagno , Alexander Taubin , Alex Yakovlev, Lazy transition systems: application to timing optimization of asynchronous circuits, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.324-331, November 08-12, 1998, San Jose, California, United States
Michael Kishinevsky , Jordi Cortadella , Alex Kondratyev, Asynchronous interface specification, analysis and synthesis, Proceedings of the 35th annual conference on Design automation, p.2-7, June 15-19, 1998, San Francisco, California, United States
technology mapping;two-input sequential gate;complex gates;decomposed logic sharing;netlist;speed-independent circuits;two-input combinational gate;signal insertion;optimization;library matching;boolean decomposition;boolean relations;circuit CAD;logic resynthesis;design library;logic decomposition