Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs.
In this paper we study structural gate decomposition in general, simple gate networks for depth-optimal technology mapping using K-input Lookup-Tables (K-LUTs). We show that (1) structural gate decomposition in any K-bounded network results in an optimal mapping depth smaller than or equal to that of the original network, regardless of the decomposition method used; and (2) the problem of structural gate decomposition for depth-optimal technology mapping is NP-hard for K-unbounded networks when K3 and remains NP-hard for K-boundeds networks when K5. Based on these results, we propose two new structural gate decomposition algorithms, named DOGMA and DOGMA-m, which combine the level-driven node-packing technique (used in FlowMap) and the network flow-based labeling technique (used in Chortle-d) for depth-optimal technology mapping. Experimental results show that (1) among five structural gate decompostion algorithms, DOGMA-m results in the best mapping solutions; and (2) compared with speed_up(an algebraic algorithm) and TOS (a Boolean approach), DOGMA-m completes, decomposition of all tested benchmarks in a short time while speed_up and TOS fail in several cases. However, speed_up results in the smallest depth and area in the following technology mapping steps.
Introduction
The field programmable gate arrays (FPGAs) have been widely used in circuit design
implementation and system prototyping for the advantages of short design cycles and low non-recurring
engineering cost. An important class of FPGAs use lookup-tables (LUTs) as the basic logic elements. A
K-input LUT (K-LUT) which consists of 2 K SRAM cells can store the truth table of arbitrary Boolean
function of up to K variables. By connecting LUTs into a network, LUT-based FPGAs can be used to
implement circuit designs in a short time.
Logic synthesis for LUT-based FPGAs transforms networks of logic gates into functionally
equivalent LUT networks. The process is usually divided into two tasks: logic optimization and
technology mapping. Logic optimization extracts common subfunctions to reduce the circuit size and/or
resynthesizes critical paths to reduce the circuit delay. Technology mapping consists of two subtasks:
gate decomposition and LUT mapping. In gate decomposition, large gates are decomposed into gates of
at most K inputs (that is, K-bounded). The resulting K-bounded network is then mapped onto (i.e.,
covered by) K-LUTs in the LUT mapping step. The separation of optimization and mapping tasks is
artificial. Some LUT synthesis algorithms (e.g. [LaPP94] and [WuEA95]) decompose collapsed networks
into LUT networks directly. The objectives of these tasks include area or delay minimization, routability
maximization, or a combination of them. A comprehensive survey of gate decomposition, LUT mapping,
and logic synthesis algorithms for LUT-based FPGAs can be found in [CoDi96].
The delay of an LUT network can be measured by the number of levels (or depth) in the network
under the unit delay model. A number of algorithms were proposed in the past for delay-oriented LUT
mapping. We classify them into two classes. The first class of algorithms, such as Chortle-d [FrRV91b],
DAG-Map [ChCD92], and FlowMap [CoDi94a], perform LUT mapping without logic resynthesis.
Among these algorithms, Chortle-d guarantees depth-optimal technology mapping for simple-gate tree
networks and FlowMap guarantees depth-optimal LUT mapping for general K-bounded networks.
Following FlowMap, FlowMap-r [CoDi94b] and CutMap [CoHw95] further reduce the mapping area,
and FlowMap-d [CoDi94c] and Edge-Map [YaWo94] minimize delay under a more accurate net delay
model. Another class of LUT mapping algorithms, such as MIS-pga-delay [MuSB91], TechMap-D
[SaTh93], FlowSyn [CoDi93], and ALTO [HuJS96] collapse critical paths followed by delay-oriented
logic resynthesis. Due to resynthesis, this class of algorithms could obtain mapping depth smaller than
the optimal depth computed by FlowMap, but usually with longer computation time.
Gate decomposition may affect significantly the network depth obtained by the algorithms in the
first LUT mapping class. For example, the network in Figure 1(a) is not a K-bounded network for
When node v is decomposed as shown in Figure 1(b), any mapping algorithm will result in a depth of 3 or
larger. But if node v is decomposed in the way shown in Figure 1(c), a mapping solution with a depth of
2 can be obtained. In addition, when a K-bounded network is further decomposed, the mapping depth
could be reduced. Figure 2(a) shows a 3-bounded network. For produces a 3-level
mapping solution of five LUTs. (Every shaded square represents an LUT in the figure.) But if node v is
further decomposed, FlowMap produces a 2-level network of four LUTs (Figure 2(b)). The two
examples demonstrate that gate decomposition affects the depth obtained by LUT mapping algorithms.
We classify gate decomposition methods into structural, algebraic, or Boolean approaches.
Structural gate decomposition can only be applied to simple gates (e.g., AND gates, OR gates, XOR
gates). Complex gates need to be transformed into simple gates (e.g., via AND-OR decomposition)
before any structural decomposition. The tech_decomp algorithm in SIS [SeSL92], the dmig algorithm
[Wa89, ChCD92], and the Chortle family of mapping algorithms [FrRC90, FrRV91a, FrRV91b] all
perform structural gate decomposition. In algebraic gate decomposition approaches, networks are
(a) (b) (c)

Figure

1 Impact of gate decomposition on mapping depth for
(a) Initial network. (b) A decomposition resulting in a mapping depth of 3.
(c) A decomposition resulting in a mapping depth of 2.
(a) Before Decomposition (b) After Decomposition

Figure

Gate decomposition in a K-bounded network Initial K-bounded network
with a mapping depth of 3. (b) Decomposed network with a mapping depth of 2.
usually partially collapsed and gates are represented in the sum-of-product (SOP) form. Common logic
subfunctions are then extracted with algebraic divisions [Ru89, De94]. The speed_up algorithm in SIS
[SeSL92] is an algebraic approach which collapses critical paths followed by network resynthesis for
delay minimization. In Boolean gate decomposition approaches, logic gates are decomposed via
functional operations. Shannon expansion, if-then-else (ITE) decomposition, and AND-OR
decomposition are very common Boolean gate decomposition operations. Recently, functional
decomposition techniques [AS59, Cu61, RoKa62] are used in a number of LUT network synthesis
algorithms [LaPP94, WuEA95, LeWE96]. In these algorithms, networks are completely collapsed
whenever possible for the outputs to be represented as functions of the network inputs directly. The
output functions are then decomposed into composed K-input subfunctions for implementation using K-
LUTs. Optional LUT mapping steps may follow to improve the synthesis results. The FGSyn algorithm
[LaPP94] and the BoolMap-D algorithm [LeWE96] take this approach for delay-oriented LUT network
synthesis. Generally speaking, algebraic approaches and Boolean approaches are more effective for both
area and delay minimization in technology mapping while structural approaches are usually faster.
Hybrid approaches such as algebraic decompositions followed by structural decompositions are used in
many logic synthesis approaches.
In this paper, we study structural gate decomposition for delay minimization in general networks
with the following motivations. First, we have shown that how gates are decomposed can affect the
mapping depth computed by FlowMap. A good gate decomposition step allows mapping algorithms to
obtain the smallest mapping depth. Second, structural gate decomposition allows arbitrary grouping of
gate inputs for our optimization objective while algebraic or Boolean approaches do not have this
advantage. Third, structural gate decomposition is computationally efficient. This is an important factor
for mapping large designs and estimating the mapping delay or area. Nowadays, the IC process
technology has advanced to 0.25 -m and below. Million-gate FPGAs have become a reality. Structural
gate decomposition algorithms can be employed in the technology mapping approaches along with this
technology trend.
Several delay-oriented structural gate decomposition algorithms were proposed in the past. The
tech_decomp algorithm [SeSL92] decomposes each simple gate into a balanced fanin tree to minimize
the number of levels locally. The dmig algorithm [Wa89, ChCD92] is based on the Huffman coding
algorithm and guarantees the minimum depth in the decomposed network. However, the mapping depth
might not be the minimum. The network in Figure 1(b) is actually decomposed using dmig and results in
a suboptimal mapping depth. The Chortle-d algorithm [FrRV91b] employs bin packing heuristics to
achieve depth minimization, but is optimal for trees only. In this paper, we go one step further. We shall
develop structural gate decomposition algorithms for depth-optimal technology mapping on general
networks.
The rest of this paper is organized as follows. Section 2 defines the terminology, presents general
properties and formulates the structural gate decomposition problems. Section 3 addresses the NP-completeness
of the problems. Section 4 presents two new algorithms, named DOGMA and DOGMA-
m, for structural gate decomposition. Experimental results are presented in Section 5 and Section 6
concludes the paper. A preliminary version of this work was published in DAC'96 [CoHw96] without
the proofs of theorems and considered only single-gate decompositions.
2. Problem Formulation
2.1. Definitions and Preliminaries
A combinational Boolean network N can be represented by a directed acyclic graph
where each node v -V represents a logic gate and each directed edge (u,v) -E represents a connection
from the output of node u to the input of node v. A node v is a simple gate if v implements one of the
following functions: AND, OR, XOR, or their inversions. Primary inputs (PIs) are nodes of in-degree
zero. Other nodes are internal nodes among which some are designated as primary outputs (POs). A
node v is a predecessor of a node u if there is a directed path from v to u in N. The depth of a node v is
the number of edges on the longest path from any PI to v. Each PI has a depth of zero. The depth of a
network is the largest depth for nodes in the network. Let input (v) and fanout (v) represent the set of
fanins and the set of fanouts of node v, respectively. Given a subgraph H of N, let input (H) denote the set
of distinct nodes outside H that supply inputs to nodes in H. A fanin cone C v rooted at v is a connected
subnetwork consisting of v and its predecessors. Node v is the root node of C v , and is denoted as
root K be the LUT input size. A node v is K-bounded if | input (v) | -K. Otherwise, v is K-
unbounded. A network N is K-bounded if it contains only K-bounded nodes.
Given a K-bounded network N, a set { of subnetworks is a K-LUT mapping
solution of N if
(C1) for every L i -M, L i is a fanin cone in N and | input (L i ) | -K,
(C2) for every L i -M, input (L i ) contains only PIs or root nodes of other subnetworks in M,
(C3) for every L i -M, root (L i ) is either a PO or belongs to input (L j ) for some L j -M, and
(C4) for every PO v of N,
A mapping solution M is duplication free if L i -L j =- for all L i -L j in M. By implementing every
subnetwork in M using a K-LUT, we obtain a K-LUT network which is functionally equivalent to N. The
mapping area and the mapping depth of M is the LUT count (i.e., | M | ) and the depth in the K-LUT
network that implements M, respectively.
Given a K-bounded network N, let S K (N) represent the set of K-LUT networks that implement all
mapping solutions of N. The minimum mapping depth of N, denoted as MMD (N), is the minimum
network depth for all K-LUT networks in S K (N). Let N v represent the largest fanin cone rooted at v in N.
The minimum mapping depth of a node v -N, denoted as MMD N (v), is MMD (N v ). The mapping depth
of any PI is 0. Given a K-bounded network N, the FlowMap algorithm [CoDi94a] computes MMD N (v)
for every node v -N in polynomial time. A cut in N v is a partition (X v , X
v ) of N v such that X
v is a fanin
cone rooted at v and X v is N v -X
v . The cutset of the cut, denoted as n (X v , X
v ), is defined as input (X
The cut is K-feasible if | n (X v , X
-K. The height of the cut, denoted as height (X v , X
v ), is
v )}. FlowMap computes a min-height K-feasible cut in the fanin cone of
each node v to obtain MMD N (v).
The following two lemmas are on the minimum mapping depth in general networks. Lemma 1
states the monotone property of minimum mapping depth and Lemma 2 gives a way to compute
MMD N (v).
be a K-bounded network and let node v -V. Then
MMD N (u) -MMD N (v) for every fanin u - input (v).
be a K-bounded network, node v -V, and let
there exists a K-feasible cut of height p - 1 in
N v . Otherwise, MMD N
2.2. Properties of Structural Gate Decomposition
Simple gates allow arbitrary grouping of their fanins in decomposition. However, the grouping and
the resulting gate size in decomposition can affect significantly the depth and area in the final mapping
solution. In this subsection, we shall show that the best mapping results can only be obtained from
completely decomposed networks.
Let node v be a simple gate in a network N and let | input (v) | - 3. Given a structural gate
decomposition algorithm D, a decomposition step D v on node v (i) chooses two fanins u 1 and u 2 of v, (ii)
removes edges introduces a node w and three edges
to re-connect u 1 , u 2 and v. Because v is a simple gate, D v can always be applied. Node w has the same
gate type as node v. For any subnetwork N- = (V-,E-) of N and a decomposition step D v , we define
{ w}, E- {
if v -V-, and D v (N-) =N- if v -/ N-. A network is completely decomposed when it becomes 2-bounded. In

Figure

3(a), N- contains nodes u 1 and v with input { a,b,u 2 , c,d}. Figure 3(b) shows D v (N-) after
one decomposition step D v . The subnetwork is completely decomposed in Figure 3(c). We have the
following theorem.
Theorem 1 Let be a K-bounded network, node v -V be a simple gate, and
| input (v) | - 3. Then S K (N) - S K (D v (N)) for any structural gate decomposition algorithm D.
(a) (c)
(b)
a
b c d
a
b c d a u 2
b c d
e

Figure

3 Decomposition of node v. (a) Before decomposition.
(b) D v (N) after one decomposition step D v . (c) Complete decomposition of v.
Proof Let w be the node introduced by D v . Let { be an arbitrary mapping
solution of N. We claim { D v (L 1 ),D v (L 2 ), . , D v (L m )} is a mapping solution of D v (N). First, N
and D v (N) have the same set of PIs and POs. From Figure 3, it should be clear that L i and D v (L i ) have
the same set of inputs as well as the same output node. As a result, M- satisfies conditions (C1) to (C4)
for being a mapping solution of D v (N). The K-LUT that implements L i also implements D v (L i ). Hence
the K-LUT network that implements M also implements M-. Therefore, S K (N) - S K (D v (N)). However, a
mapping solution M- of D v (N) can not be a mapping solution of N if w is the root node of some
subnetwork in M- (due to w -/ N). There exists at least one such mapping solution which is D v (N) itself.
As a result, S K (N) - S K (D v (N)). #
Corollary 1.1 Let be a K-bounded network, node v -V be a simple gate, and
| input (v) | - 3. Then MMD (D v (N)) -MMD (N) for any structural gate decomposition algorithm D.
Proof Since S K (N) - S K (D v (N)) for any decomposition algorithm D, by definition,
MMD (D v (N)) -MMD (N). #
Note that Theorem 1 and Corollary 1.1 hold as long as the decomposition step at v (structural,
algebraic, or Boolean) can be carried out regardless v is a simple gate or not. However, the algebraic or
functional decomposition for a complex gate may not always be possible.
Since the set of all possible functionally equivalent K-LUT networks expands whenever a simple
gate is decomposed (Theorem 1), it is always beneficial to decompose simple-gate networks into 2-
bounded networks for LUT mapping algorithms to exploit the larger mapping solution space. The
experimental results reported in [CoDi94a] confirm this conclusion. In their experiments, the input
networks were first transformed into simple gate networks and then decomposed structurally into 5-
bounded, 4-bounded, 3-bounded, or 2-bounded networks before for LUT mapping. The resulting
mapping depth decreases monotonically along with the decrease of gate sizes in decomposition. An
interesting contrast comes from the results reported in [LeEW96] where networks were first collapsed
completely and then decomposed functionally into 5-bounded, 4-bounded, or 3-bounded networks for
LUT mapping. The best mapping solutions in terms of area and depth are mostly from the 5-bounded
networks. The two experiments show an important difference between structural and functional
decompositions: logic signals are preserved in structural decompositions while new gates are synthesized
during functional decompositions. In [LeEW96], the 5-bounded, 4-bounded, and 3-bounded networks
contain totally different sets of internal gates which are synthesized independently in three functional
decomposition processes. In fact, according to Corollary 1.1, if the 5-bounded networks in [LeEW96]
were further decomposed for LUT mapping, even smaller mapping depth could be obtained in their
experiments.
The following lemma specifies a condition where the structural gate decomposition will not cause
further mapping depth reduction.
be a K-bounded network, node v -V be a simple gate, and | input (v) | - 3.
Assume that nodes u 1, Figure 4(a)). Let D v be the
decomposition step which merges u 1 , u 2 into an intermediate node w (see Figure 4(b)). Then
MMD (N) =MMD (D v (N)).
Proof Assume MMD N
)). Next,
assures that p-MMD D v (N) (w) -MMD D v (N) (v). Then, according to
Corollary 1.1, we have MMD D v (N) (v) -MMD N

Figure

4(b)). Now we show MMD (D v (N)) =MMD (N). Suppose this is not the case. Then
MMD (D v (N)) <MMD (N) and there exists a mapping solution { (N) such that
M has a depth smaller than MMD (N). Let x i represent the output node of each K-feasible subnetwork L i
in M. First, would be a mapping solution of N (by collapsing w into v)
and MMD (D v (N)) would not be smaller than MMD (N). Next, there must exist some x i such that
We call node x i a depth-reduced node. There are two cases for any depth-
reduced node x i . (i) w -/ input (L i ). Then we can find another node x j - input (L i ) such that
won't be a depth-reduced node. We continue to trace
depth-reduced nodes towards PIs. This tracing, however, won't reach PIs since PIs have a depth of 0. At
certain depth, the second case must happen. (ii) w - input (L i ). Then (N- x -L i , L i ) is a cut in the fanin
cone N- x i
in D v (N) (see Figure 4(c)). But we can move node v from L i to N- x -L i and obtain another K-
feasible cut of height p in N- x i
(see

Figure

4(d)), since w is fanout-free and w and v have the same
mapping depth p. This implies MMD D v (N) As a result, x i is not a depth-reduced node.
Contradiction. So we proved MMD (D v (N)) =MMD (N). #
Lemma 4 Let be a K-bounded network, node v -V be a simple gate, and | input (v) | - 3.
If MMD N (D v (N)) for any structural
gate decomposition algorithm D.
Proof Since the intermediate node w has the same depth as node v, this lemma is true according to
Lemma 3. #
(a) (b)
(c) (d)

Figure

4 (a) Before D v . (b) After D v . (c) w - input (L i ). (d) v is moved out of L i .
2.3. Integrated versus Two-step Technology Mapping
Gate decomposition and LUT mapping can be performed in two different ways. In an integrated
mapping approach, the input network is decomposed and covered by LUTs simultaneously, while in a
two-step mapping approach, the input network is decomposed into a K-bounded network before LUT
mapping is performed. For example, Chortle-d is an integrated mapping approach while FlowMap fits
only into a two-step mapping approach. The separation of gate decomposition and LUT mapping is a
restriction in general since integrated approaches allow more informative gate decomposition and LUT
mapping decisions while two-step approaches do not have this advantage. It may appear that the
minimum mapping depth for all integrated mapping approaches will be smaller than the minimum
mapping depth for all two-step mapping approaches. However, we show that this is not the case for
structural gate decomposition.
Theorem 2 Given a K-bounded network N, if only structural gate decomposition is allowed, the
minimum mapping depth for all integrated mapping approaches equals to the minimum mapping depth
for all two-step mapping approaches.
Proof Given an arbitrary K-bounded network N, assume some integrated approach results in the
optimal depth MMD (N) in a mapping solution M N . Then M N is a mapping solution of some K-bounded
network N- decomposed structurally from N. A depth-optimal mapper (e.g. FlowMap) can take N- as
input and generate a mapping solution M N- . Since M N- is depth-optimal with respect to N-, we have
MMD (N-MMD (N). But M N is depth optimal with respect to N, As a result, MMD (N) -MMD (N-).
Therefore, MMD (N) =MMD (N-). #
Our mapping algorithms to be presented in Section 4 should be considered a hybrid approach. On
one hand, depth minimization is achieved in structural gate decomposition (by DOGMA or DOGMA-m)
to return a network topology of the minimum mapping depth; On the other hand, the LUT mapping
solution is computed in depth-optimal LUT mapping with area minimization as a second objective. As a
result, the depth and the area are optimized separately in the two steps of technology mapping. Therefore,
we consider our algorithm as a hybrid approach.
2.4. The SGD/K and K-SGD/K Problems
In this paper, we study structural gate decomposition of K-bounded or K-unbounded simple-gate
networks into 2-bounded networks such that LUT mapping algorithms (e.g., FlowMap) can obtain the
smallest mapping depth. We formulate the following two problems.
Structural Gate Decomposition for K-LUT Mapping (SGD/K) Given a simple-gate K-
unbounded network N - , decompose N - into a 2-bounded network N 2 such that MMD (N 2
for any other 2-bounded decomposed network N- 2 of N - .
Structural Gate Decomposition in K-bounded Network for K-LUT Mapping (K-SGD/K)
Given a simple-gate K-bounded network N K , decompose N K into a 2-bounded network N 2 such that
other 2-bounded decomposed network N- 2 of N K .
3. Complexity of SGD/K and K-SGD/K Problems
We shall show the following results: (1) The SGD/K problem is NP-hard for K - 3; and (2) the K-
SGD/K problem is NP-hard for K - 5. We shall present the construction for the NP-Complete reduction,
the lemmas and theorems, and the proofs for theorems. Proofs for lemmas can be found in the Appendix.
Our results are based on polynomial-time transformations from the 3SAT problem to the decision
version of the SGD/K and the K-SGD/K problems. The 3SAT problem, which is a well-known NP-Complete
problem [GaJo79], is defined as follows.
Problem: 3-Satisfiability (3SAT)
Instance: A set of Boolean variables collection of m clauses
each clause is the disjunction (OR) of 3 literals of the variables and
(ii) each clause contains at most one of x i and x #
i for any variable x i .
Question: Is there a truth assignment for the variables in X such that C
We shall transform an arbitrary instance of 3SAT to an instance of SGD/K in polynomial time. The
idea is to relate the truth assignment of variables in 3SAT to the decision of gate decomposition in
SGD/K. Since determining the truth assignment is difficult, the decision of gate decomposition is also
difficult. We define the decision version of the SGD/K problem as follows.
Problem: Structural Gate Decomposition for K-LUT Mapping (SGD/K-D)
Instance: A constant K - 3, a depth bound B, and a simple-gate K-unbounded network N - .
Question: Is there a way to structurally decompose N - into a 2-bounded network N 2 such that the
depth-optimal K-LUT mapping solution of N 2 has a depth no more than B?
Given an instance F of 3SAT with n variables x 1 , x 2 , . , x n and m clauses C i , C 2 , . , C m , we
construct an K-unbounded network N (F) corresponding to the instance F as follows.
First, for each variable x i , we construct a subnetwork N which consists of the following nodes:
(a) two output nodes denoted as x i and x
nodes in which two of them are denoted as
1 and PI i
nodes, denoted as v i
respectively; The nodes are connected as shown in Figure 5. Each node of w i
2 has K - 1 PI fanins.
Node s i has 4 fanins from w i
1 and PI i
. Every other internal node has K PI fanins. Note that
well-defined for K - 3 and is K-bounded for
Next, for each clause C j with 3 literals l j
3 , we construct a subnetwork N (C j ) which consists of
the following nodes: (a) one output node denoted as C j ; (b) three literal nodes denoted as l j
2K-5 , each of them being the root of a complete 2-level K-ary tree with
PI nodes as leaves; (d) (K - 2) internal nodes r j
K-2 , each of them being the root of a complete 3-
level K-ary tree with PI nodes as leaves. The connections are shown in Figure 6(a). The output node C j
has all internal nodes as its fanins in N (C j ). Note that N (C j ) is well-defined for K - 3. However, the
output node C j is not K-bounded.
K PI's
K PI's
K-1 PI's K-1 PI's
K PI's K PI's
K-3
K-2
Figure

5 Construction of network N
r j3
K-2
l j
r j3
K-2
l j
(a) (b)

Figure

6 (a) Construction of network N (C j ) for each clause C j .
(b) Exact 2K nodes of depth 2 appear when MMD (l j
2.
Finally, we connect the subnetworks N (C j with the subnetworks N
as follows to form the network N (F). Let literal l j
k be a literal in clause C j . If l j
x i is a variable, we connect node x i in N as the single fanin of node l j
k in N (C j ). Similarly, if l j
we connect node x #
i in N as the single fanin of node l j
k in N (C j ). Note that every literal node has
exactly one fanin. This fanin node is called the variable node of the corresponding literal node. Network
N primary outputs: nodes C 1 , . , C m . We illustrate the construction of N (F) by an example.
Assume
The network N (F) is shown in Figure 7. Because
clause
as fanins to nodes l 1
3 in N (C 1 ), respectively.
is the variable node of node l 1
1 . We have the following lemma.
Lemma 5 The 3SAT instance F is satisfiable if and only if N (F) can be decomposed into D (N
such that MMD (D (N
Theorem 3 The SGD/K problem is NP-hard for K - 3.
Proof The transformation from an instance F of 3SAT to the network N (F) takes O (K 3 (n +m))
time. If the SGD/K-D problem can be solved in polynomial time, we can set solve 3SAT in
polynomial time. So the SGD/K-D problem is NP-hard. For a given decomposed network D (N (F)) of
takes polynomial time to compute its mapping depth d and verify whether d -B (e.g. by
FlowMap). So the SGD/K-D problem is NP-Complete. Since N are well-defined forl 1l 1 3
l 1l 2l 2l 2l 3l 3l 3

Figure

7 The network N (F) for
the SGD/K-D problem is NP-Complete for K - 3. Hence the SGD/K problem is NP-hard for K - 3.
We now show the complexity of the K-SGD/K problem. In this construction of reduction, we must
have every node K-bounded (note that N (C j ) is not K-bounded in the previous construction). Given an
instance F of the 3SAT with n variables x 1 , x 2 , . , x n and m clauses C i , C 2 , . , C m , we construct a
corresponding K-bounded network N K (F) as follows. For each variable x i , construct subnetwork N
before (shown in Figure 5). However, for each clause C j , construct subnetwork N K (C consisting of (a)
one output node denoted C j ; (b) three literal nodes denoted as l j
K-5 , each of them is the root of a complete 2-level K-ary tree with PI nodes as leaves. The
subnetwork N K (C j ) is shown in Figure 8(a). Note that N K (C j ) is well defined and K-bounded for K - 5.
We connect subnetworks N according to the formula F as before to obtain the network
N K (F). We have the following lemma.
Lemma 6 The 3SAT instance F is satisfiable if and only if N K (F) can be decomposed into
D (N K (F)) such that MMD (D (N K
Theorem 4 The K-SGD/K problem is NP-hard for K - 5.
Proof The subnetwork N K-bounded for 4. The subnetwork N K (C j ) is K-bounded for
5. Based on similar arguments in the proof of Theorem 3, it is easy to see the K-SGD/K problem is
NP-hard for K - 5. #
4. Gate Decomposition Algorithms for Depth-Optimal Mapping
In this section, we combine the node packing technique in Chortle-d with the min-height K-feasible
cut technique in FlowMap in structural gate decomposition of simple-gate networks. Our objective is to
minimize the depth in the final mapping solution. We propose two algorithms. The first algorithm
decomposes logic gates independently as in most previous approaches; while the second algorithm
decomposes multiple gates simultaneously to exploit common fanins. The advantage of multi-gate
(a) (b)
l jl jl j3 C j2
l j
K-5
K-5
Figure

8 Construction of K-bounded subnetwork N K (C j ) for each clause C j .
decomposition can be seen in one example. Nodes a, b, . , f in Figure 9 are primary inputs. If nodes u
and v in Figure 9(a) are decomposed independently, we might obtain a network in Figure 9(b). For
the best mapping solution in this case will be a 3-level network of 6 LUTs. However, if nodes u and v are
decomposed together to exploit their common fanins c and d as shown in Figure 9(c), a 2-level network
of 4 LUTs can be obtained. Both the depth and the area are reduced in the mapping solution.
(a)
a b c d e
f
x
(b)
a b c d e
f
x
(c)
a b c d e
f
x

Figure

9 Multi-gate decomposition. (a) Initial network. (b) Single gate decomposition result.
(c) Multi-gate decomposition result. (Shaded nodes are LUT outputs.)
4.1. Single Gate Decomposition
We present our single gate decomposition algorithm DOGMA (Depth-Optimal Gate decomposition
for MApping) in this subsection. Given a simple-gate network N, DOGMA decomposes nodes in
topological order from PIs to POs. At each node v, DOGMA shall decompose and label v with the
number l (v) =MMD N (v) (v) where N (v) denotes the decomposed network. The set of fanins of label q in
input (v), denoted S q , is called a stratum of depth q. A K-feasible cut of height q - 1 exist for every node
in S q . A K-feasible cut of height q - 1 exists for a set B of nodes if such a cut exists for a node s created
with input (s) =B. DOGMA groups input (v) into strata according to their labels, and processes each
stratum in two steps.
(1) Starting from the stratum S q of the smallest depth, DOGMA partitions S q into a minimum number
of subsets such that there exists a K-feasible cut of height q - 1 for each subset of nodes. The
process is similar to packing objects into bins. Each bin has a size of K. The size of a node (also
called an object) is the size of its min-cut of height q - 1. A set of nodes can be packed into one bin
if their overall size is no larger than K. Such a bin is called a min-height K-feasible bin which
corresponds to a partitioned subset of S q . Note that the overall cut size for nodes in a set could be
smaller than the sum of their individual cut sizes.
(2) After partitioning S q into subsets (or min-height K-feasible bins), an intermediate node (also called
bin node) w i is created for each bin B i with input (w i ) =B i and is labeled l (w
is then created for each w i with input (b i { w i } and a label l (b buffer nodes are put
into the set S q +1 . Note that if some bin B i contains more than 2 nodes, bin node w i needs to be
further decomposed. However, according to Lemma 4, no matter how w i is decomposed, the
minimum mapping depth of the network does not change. DOGMA arbitrarily decomposes w i into
an unbalanced tree.
DOGMA repeats steps (1) and (2) for stratum S q +1 and so on until all strata have been processed.
The last bin node corresponds to node v. Note that buffer nodes are introduced only for the packing
process and will be removed when the decomposition is complete.
To determine if there exists a K-feasible cut of height q - 1 for a bin B i - S q of nodes, we compute a
max-flow in the flow network constructed as follows [CoDi94a]. (i) Create a sink node t with
input (t) =B i . (ii) Create a source node s that fanouts to all PIs in N t . (iii) Assign every edge in N t an
infinite flow capacity. (iv) Replace every node u -N t , except s and t, by a subgraph (V u
{
an infinite flow capacity if l otherwise, a unit flow capacity is assigned. (v) Finally,
compute a max-flow in the constructed flow network. The amount of flow f corresponds to the min-cut
size in the flow network. If f -K, there exists a min-cut of height q - 1 for the bin B i of nodes.
We illustrate DOGMA for 3. The output node v in Figure 10(a) is under decomposition.
Among the five fanins of v, b,c,d have labels l As
a result, S { b,c,d} and S { a,e}. According to DOGMA, b,c will be packed into one bin since a K-
feasible cut of height 1 exists for them, and d into another bin for a total of two (which is the minimum)
min-height K-feasible bins. Then bin nodes f and g with labels l (f buffer nodes h and i
with labels l are created for the two bins, respectively (see Figure 10(b)). DOGMA proceeds
to the stratum of depth 3. Two K-feasible cuts of height 2 are found for { a,h} and { i,e} respectively.
Again, bin nodes j and k with labels l nodes m and n with labels l
are created for the two bins, respectively. Nodes m and n are then packed into a bin which corresponds to
v (see

Figure

10(c)). Finally, nodes g, h, i, m and n are removed and node v is completely decomposed
with a label l
The following problem needs to be solved in DOGMA.
a
c d
e
a
c d
e
a
c d
e
(a) (b)
(c)
Figure

Decomposition of gate v by the DOGMA algorithm. (a) Before decomposition.
(b) b and c, d are packed into f and g. (c) a and h, i and e are packed into j and k.
Min-Height K-Feasible Bin Packing Problem Given a stratum S q of depth q, pack nodes in S q
into a minimum number of min-height K-feasible bins.
In our study, we developed three heuristics to solve the problem. The first-fit-decreasing (FFD) and
best-fit-decreasing (BFD) are two heuristics for the bin packing problem [HoSa78]. The FFD heuristic
sorts objects into a list of objects of decreasing sizes, indexes the bins 1,2,3,., then removes the object
from the list (in order) and puts it into the first bin that can accommodate it. The initial conditions on the
bins and objects in the BFD heuristic are the same as in the FFD heuristic. But BFD puts the object into
the bin that leaves the smallest empty space. For the min-height K-feasible bin packing problem, we
proposed two min-cut based heuristics, MC-FFD and MC-BFD, which are analogous to FFD and BFD
except that every object is a node whose size is defined to be the size of its min-cut of height q - 1. A set
of nodes can be packed into a K-feasible bin as long as their combined cut size is no larger than K. The
third heuristic is called maximal-sharing-decreasing (MC-MSD) which encourages sharing during
packing, i.e., the size of the min-cut for the packed nodes is smaller than the sum of their individual min-cut
sizes. The packing that produces the maximum sharing is considered the best-fit packing when MC-
MSD calls MC-BFD for a packing result.
Experimental results (Table 1) show very little difference between the three heuristics on the
mapping results (DOGMA followed by CutMap) for MCNC benchmarks. It indicates that the same
number of bins were obtained by the three heuristics in most cases. This could be due to the small bin
size in the experiment. We choose MC-FFD for its efficiency. The FFD heuristic is also used in
Chortle-d for packing nodes into bins. However, MC-FFD packs nodes according to the size of their
min-height K-feasible cut for better performance. With reconvergent fanouts in general networks, one
can not decide locally whether a set of nodes can be packed into one bin or not. For example, it is not
obvious that nodes e and i in Figure 10(b) can be packed into one bin. The MC-FFD heuristic employs
max-flow computation and can decide the packing feasibility correctly.
The time complexity of DOGMA is computed as follows. For every node v in the input network
create | input (v) | - 2 nodes. In total, there are
( | input (v) | - created. The min-height K-feasible cut
computation has a time complexity of O (K . | E | ) [CoDi94a] where K is the LUT input size, and is carried
out O ( | input (v) | 2 ) times in the worst case at each node v in the MC-FFD heuristic. Let d max be the
maximal fanin size for nodes in N. Then the time complexity of DOGMA is O (K . d max
. | E | 2 ). We can
reduce the time complexity of min-height cut computation to O (K . | constructing partial flow
networks only to a certain depth, where E p is the edge set of the partial flow network. Let E p_max
represent the edge set of the largest partial flow network constructed during decomposition. Then the
time complexity of DOGMA is reduced to O (K . d max
Bin packing heuristics in DOGMA
MC-FFD MC-BFD MC-MSD
Circuits D A D A D A
count 5
rot 7 267 7 267 7 267
too_large 5
C6288 22 724 22 724 22 724
des 5 965 5 965 5 965
total 171 7674 171 7674 171 7677

Table

1 Comparison of packing heuristics MC-FFD, MC-BFD, and MC-MSD in DOGMA.
4.2. Multiple Gate Decomposition
We present our multiple gate decomposition algorithm, named DOGMA-m, and illustrate the
procedure on the network shown in Figure 11(a) for 3. DOGMA-m is outlined in Figure 12.
We call the stratum of each node a local stratum. The union of all local strata of depth q is called
the global stratum of depth q. For each depth q, a node v is under decomposition if | input (v) | > 2 (i.e.,
not yet completely decomposed) and input (v) intersets with the global stratum of depth q. Starting from
the depth the nodes of the same gate type and also under decomposition will be decomposed
simultaneously. In Figure 11(a), nodes a, b, ., h all have a label of 1. Nodes x, y, and z are under
decomposition for 1. The local stratum of depth 1 is { a,b,c} for node x, { b,c,d,e, f } for node y, and
{ e, f , g,h} for node z, respectively. The global stratum of depth 1 is { a,b,c,d,e, f , g,h}.
(a)
e
a b c g h
f
d
x y z
(c)
e
a b c g h
f
d
z
(b)
e
a b c g h
f
d
y z
e
a b c g h
f
d
z

Figure

Multiple gate decomposition. (a) Initial network. (b) After one
(c) After two Completely decomposed network.
In initialization, buffers are created for PIs to supply inputs to the the rest of the network. PIs are
labeled 0 and buffers are labeled 1. In Figure 11(a), nodes a, b, . , h are buffers PI buffers. Gray
regions represent the global strata of depth 1 and 2 in Figure 11(a)-(c) and (d), respectively . The gate
decomposition proceeds as follows.
(1) For each depth q and for each gate type f, the nodes under decomposition are collected into a set
G q
f . Then the global stratum of depth q, denoted as S q , is computed by the union of local strata of
depth q for all nodes in G q
f . In

Figure

{ x,y,z} and
{ a,b,c,d,e, f , g,h}. Based on G q
f and S q , we formulate the Global Stratum Bin Packing
(GSBP) problem (to be formally defined later). By solving the GSBP problem, we achieve (i) for
each node in G q
f , its local stratum of depth q are packed into min-height K-feasible bins, and (ii)
there are a minimum number of min-height K-feasible bins in total. The second objective is
achieved by packing common fanins for the nodes in G q
f . Intermediate nodes (also called bin
nodes) are created for bins. In Figure 11(b), nodes b and c, e and f, g and h are packed into bin
nodes i, j and k, respectively.
(2) It is possible that some nodes in G q
f have been decomposed completely (e.g., nodes x and z in

Figure

while the local strata of other nodes can be further packed (e.g., node y in Figure
11(b)). Both G q
f and S q are updated and a new instance of the GSBP problem for the same q value
is formulated and solved. The process iterates until the global stratum of depth q has been
minimally packed into bins (as a result, the network does not change). In Figure 11(b), we have
l
{ v,y}, and S { i,d, j,x}. By solving the GSBP problem for the updated G 1
f
and S 1 , node d and i are packed into a bin node m. Node y is now completely decomposed with a
label l 2. The process iterates with updated G 1
{ v} and S { x}. But no further packing are
possible for Figure 11(c)).
(3) Buffer nodes are created and labeled q every fanin in the global strata S q . The
decomposition process iterates steps (1) and (2) until the network is 2-bounded. In Figure 11(d), a
buffer node n is created for node x, nodes y and z are then packed into a bin, and the decomposition
of node v is completed.
Two points are worth mentioning. First, in DOGMA, each node is decomposed only after all its
fanins have been decomposed and labeled. In DOGMA-m, however, nodes could undergo decomposition
even though some of their fanins have not been labeled. For example, node v in Figure 11(b) is under
decomposition (v -G 1
f ) while its fanin y is not labeled yet. Second, for each depth q and gate type f,
multiple instances of the GSBP problem might be solved in order to pack local strata into a minimal
number of bins. For example, two instances of the GSBP problem are solved for before the local
stratum of node y is minimally packed (from Figure 11(a) to (c)). In our experiments, we found that
solving three instances of the GSBP problem are sufficient for each q value.
The Global Stratum Bin Packing (GSBP) Problem is formally defined as follows.
Global Stratum Bin Packing (GSBP) Problem Given a set G q
f of nodes of gate type f under
decomposition and a global stratum S q of depth q that contain fanins of nodes from G q , pack the fanins in
S q into a set of bins such that (i) for each node in G q , its local stratum of depth q are packed into min-
height K-feasible bins, (ii) there is a minimum number of min-height K-feasible bins in total.
To solve the GSBP problem, we build a matrix M where rows correspond to nodes in
G q
columns correspond to fanins in S {
not. A rectangle is a subset of rows and columns, denoted by a pair
(R,C) indicating the row and column subsets, where all entries are 1. C corresponds to a bin of fanins and
R corresponds to a set of nodes that share fanins in C. A solution of the GSBP problem is a rectangle
cover for M subject to that a K-feasible cut of height q - 1 exists for fanins in each column set C. This
matrix representation is similar to the cube-literal matrix used for solving the cube extraction problem
procedure DOGMA-m ( N, K )
/* N is the input network and K is LUT input size. */
Initialization
. until N is 2-bounded do
4 while not inc_q do
5 for each gate function type f do
{ u | label
8 Solve GSBP( G q
f , S q , K ) problem
9 for each min-height K-feasible bin B i created (if any) in GSBP do
create bin node w i , label (w i
to N, update fanins of nodes in G q
f
12 if no new bin node was created then
13 for each node u i - S q do
14 create buffer node b i , label (b i
return N

Figure

Multiple gate decomposition algorithm.
[Ru89, De94]. However, the algorithms for cube extraction can not be applied directly because the C in
every rectangle (R,C) must satisfy the K-feasible cut constraint.
We use the MC-FFD packing heuristic to compute a rectangle cover for the GSBP problem as
follows. First, compute the fanout factor
and the cut size s j of min-cut of height q - 1 for
a b c d e f
x
y
(a)00
z
a b c d e f
x
y
(b)00
z
Figure

13 FFD bin packing heuristic for the GSBP problem.
(a) Initial M. (b) The M after the first run of bin packing.
every fanin u j - S q . The weight of each fanin is
. s j . Then we sort the fanins according to their weights
and follow the MC-FFD bin packing heuristic to pack fanins into bins (starting from the fanin with the
largest weight). Our strategy is to group fanins of large cut sizes for obtaining a minimum number of bins
and to group fanins of large fanout sizes for exploiting common fanins. A set of fanins can be packed
into one bin C if (i) a K-feasible cut of height q - 1 exists for the fanins in C, and (ii) the largest rectangle
satisfies | R | - r min (i.e., at least r min nodes in G q
f share these fanins) where r min is a user-specified
parameter. By performing the MC-FFD packing heuristic, we obtain a set of rectangles. Each rectangle
(R,C) that satisfies | C | - c min (another user-specified parameter) will be saved and covered with 0's in
M. The MC-FFD packing procedure is repeated until M contains only 0's. A rectangle cover for M is
then obtained, and the set C in each rectangle corresponds to a bin. In our implementation, we set
in the first pass of the MC-FFD packing procedure, and decrease both values to 1 in
subsequent iterations. The decrease of values guarantees the termination of our procedure.
We demonstrate the MC-FFD packing heuristic on the network in Figure 11(a) for solving
the GSBP problem. The initial matrix M is shown in Figure 13(a). The rows correspond to nodes in
{ x,y,z} and the columns correspond to fanins in S { a,b,c,d,e, f , g,h}. The weight of each fanin
is its fanout size (i.e., the number of 1's in each column) since every fanin is a PI buffer whose cut size is
1. Fanins are sorted into the order b,c,e, f , a,d,g,h according to their weights. Nodes b and c are packed
into the first bin, which corresponds to the rectangle (R 1 , b,c}). Although there is a 3-
feasible cut of height 0 for nodes b,c,e, they can't be packed into one bin because the rectangle for them
have | R | = | { y} | < r 2. As a result, node e is put into a separate bin and packed with node f, which
corresponds to the rectangle (R 2 , e, f }). Then the two rectangles are covered with 0's

Figure

13(b)). We reset r another run of MC-FFD packing heuristic. Three
bins are obtained but only one bin contains two fanins. Totally, three bin nodes will be created. The
network in Figure 11(a) is now decomposed into the network in Figure 11(b).
original rugged
ckt gate fanin ckt gate fanin
Circuits size 3 >3 time(s) size 3 >3
z4ml
count 111 14% 0% 1.4 79 22% 20%
9symml 153 34% 8% 20.4 96 28% 35%
cordic 73 11% 8% 1.3 36 22% 28%
i3 70 0% 6% 2.2 78 0% 26%
alu2 210 17% 53% 29.9 172 19% 16%
alu4 416 13% 47% 22.0 374 16% 9%
rot 494 21% 39% 17.1 392 21% 18%
dalu 1939 10% 4% 3.0 595 42% 7%
too_large 1038 0% 100% 7.0 137 21% 35%
des
total 18824 16% 26% 317.4 13007 16% 12%

Table

optimization using the rugged script.
5. Experimental Results
We implemented DOGMA and DOGMA-m in C language and incorporated them into the RASP
logic synthesis system for FPGAs [CoPD96]. We prepared two sets of benchmarks in our experiments.
The first set C original consists of 24 original multi-level MCNC benchmarks which all contain a large
percentage of 2-unbounded gates (i.e., 3 or more inputs). We performed the rugged script in SIS
[SeSL92] for technology independent optimization and obtained the second set C rugged of benchmarks.
Both sets of benchmarks were transformed into simple-gate networks using AND-OR decomposition.

Table

2 shows the circuit sizes and fanin distributions of the two sets of simple-gate networks. The
benchmark set C original contains 18,824 simple gates with 42% of them being 2-unbounded, while the
benchmark set C rugged contains 13,007 simple gates with 28% of them being 2-unbounded. Clearly, both
circuit size and fanin size were reduced by performing the rugged script. The total runtime is less than 6
minutes.
We compared DOGMA and DOGMA-m with three structural gate decomposition algorithms, as
well as DOGMA-m with algebraic and Boolean decomposition approaches in our experiments. The three
structural gate decomposition algorithms used for comparison were the tech_decomp algorithm
[SeSL92], the dmig algorithm [Wa89, ChCD92], and our implementation of the Chortle-d algorithm
[FrRV91b]. After gate decomposition by each of these algorithms, CutMap [CoHw95] was employed to
obtain depth-optimal mapping solutions. For a comparison across structural, algebraic, and Boolean gate
decompositions, we employed DOGMA-m, speed_up in SIS [SeSL92] and the TOS package
[EcLL96] to perform decompositions, respectively. Again, CutMap was employed to perform LUT
mapping except for TOS since it produced LUT networks directly. The objective of gate decomposition
and LUT mapping in our experiments was to minimize mapping depth. CutMap also minimizes
mapping area as the second objective. All experiments were performed on a Sun ULTRA2 workstation
with 256M of memory.
We first demonstrate the impact of further gate decomposition on depth and area in technology
mapping. According to Theorem 1, the mapping solution space expands regardless of the gate
decomposition algorithm used. We use tech_decomp to decompose benchmarks in C rugged into 5-
bounded networks, and subsequently into 2-bounded networks, followed by LUT mapping to obtain
mapping solutions. The sizes of 5-bounded networks increase substantially comparing to the 5-
unbounded networks in C rugged . However, the percentages of 2-unbounded gates are about the same. We
employed CutMap [CoHw95] and DFMap [CoDi94b] to produce depth-optimal and duplication free
5-bounded CutMap DFMap
ckt gate fanin 5-bounded 2-bounded 5-bounded 2-bounded
Circuits size 3 >3 D A D A D A D A
count 79 22 20 5 31 5 31
9symml 131 24 28 7 90 6 105
alu4 434 21 9
rot
too_large 219
des
total 16007
ratio 1.00 1.00 0.84 1.01 1.00 1.00 1.02 0.84

Table

3 Comparison of results for 5-bounded and 2-bounded networks.
area-optimal mapping solutions, respectively. In Table 3, we see that both the optimal mapping depth (by
CutMap) and the optimal duplication-free mapping area (by DFMap) are reduced by 16% when the 5-
bounded networks are further decomposed into 2-bounded networks. These results confirm the results
stated in Theorem 1.
Structural gate decomposition algorithms
tech_decomp dmig chortle-d DOGMA DOGMA-m
Circuits D A T(s) D A T(s) D A T(s) D A T(s) D A T(s)
z4ml 4
count 5
9symml 5
dalu 9 507 3.7 9 513 4.3 9 507 12.0 9 506 175.8 9 497 19.9
too_large 7 4867 26.3 7 4700 297.4 6 3913 137.6 6 3867 456.9 6 2124 1680.7
C6288 22 728 4.5 22 728 5.1 22 728 85.9 22 728 854.9 22 728 42.6
des 5
total
ratio 1.11 1.50 0.03 1.05 1.48 0.12 1.06 1.41 0.12 1.01 1.39 0.69 1.00 1.00 1.00

Table

4 Comparison of results using tech_decomp, dmig, chortle-d, DOGMA and DOGMA-m
for gate decomposition followed by CutMap for circuits in C original .
Next, we compared five structural gate decomposition algorithms (tech_decomp, dmig, Chortle-
d, DOGMA, and DOGMA-m) on benchmarks in C original and C rugged using CutMap as the mapping
engine. The depth and area of mapping solutions as well as the runtimes of the compared algorithms (not
including CutMap time) for the two sets of benchmarks are presented in Tables 4 and 5, respectively.
Comparing to DOGMA-m, we see that the other four algorithms result in up to 11% larger mapping
depth and up to 50% larger mapping area on the benchmark set C original , and up to 16% larger mapping
depth and up to 10% larger mapping area on the benchmark set C rugged . The differences in mapping
depth obtained by DOGMA-m and dmig or DOGMA are marginal, while the differences in mapping
area are more significant. Regarding the runtime, DOGMA-m runtime is comparable to DOGMA
runtime, but is 8 to 33 times slower than the runtimes of other three algorithms. However, DOGMA-m
runtime is in the same order of magnitude as the time spent in performing the rugged script or CutMap.
Structural gate decomposition algorithms
tech_decomp dmig chortle-d DOGMA DOGMA-m
Circuits D A T(s) D A T(s) D A T(s) D A T(s) D A T(s)
count 5
cordic 5
rot 9 270 1.0 7 259 1.1 8 265 2.5 7 267 6.2 7 261 5.4
too_large 6 162 0.4 5 161 0.6 5 185 1.1 5
C6288 22 727 4.3 22 690 4.9 22 690 19.4 22 724 769.2 22 723 192.0
des 6 1087 4.5 5 1058 5.3 6 1127 14.4 5 965 49.0 5 969 208.5
total 196 7857 32.0 176 7773 42.8 182 7836 103.4 171 7689 1130.9 169 7144 919.0
ratio 1.16 1.10 0.03 1.04 1.09

Table

5 Comparison of results using tech_decomp, dmig, chortle-d, DOGMA and DOGMA-m
for gate decomposition followed by CutMap for circuits in C rugged .
Comparing Tables 4 and 5, we see that the mapping area for C rugged is 30% to 50% smaller than
that for C orginal , while the mapping depth for C rugged is 1% to 7% larger than that for C original . It shows
that the rugged script, which performs logic optimization based on algebraic divisions, is very effective
for area minimization but not as effective for depth minimization. A benefit resulted from the area
reduction is the significant decrease of runtime for all decomposition algorithms. For benchmarks in
rugged , DOGMA-m results in 10% smaller area comparing to the other four algorithms under
comparison. It shows that DOGMA-m can exploit common fanins for area minimization in addition to
the rugged script.
Finally, we employed DOGMA-m, speed_up and TOS for a comparison across structural,
algebraic, and Boolean gate decomposition approaches. We configured TOS for delay-oriented synthesis
in the medium-effort mode performing both single-output (TOS-s) and multi-output (TOS-m) functional
decompositions. The input circuits to TOS were prepared as follows. First, we tried to collapse each
benchmark in C rugged into a flat logic network within 30 minutes of CPU time. If this could not be done,
we used the reduce_depth -depth d command provided in TOS to collapse benchmarks into networks
of the smallest depth d where d - 2. We allocated minutes of CPU time for each depth d starting from
Among all benchmarks after collapsing, rot and C880 have a depth of 2, C432,
C2670, C5315, and C7552 have a depth of 3, C3540 and i10 have a depth of 4, and C6288 has a
depth of 6. The remaining benchmarks are completely collapsed.

Table

6 collects the mapping results by DOGMA
TOS-m. Subtotal1, subtotal2, and subtotal3 are totals of the mapping results for benchmarks that
speed_up, TOS-s, and TOS-m succeed, respectively, and the ratios measure the relative performances
of these approaches with respect to DOGMA-m CutMap. The time T(s) reports the computation time
in seconds. In Table 6, we see that DOGMA-m + CutMap is able to map all benchmarks in 23 minutes,
while speed_up fail to map some benchmarks after 2 hours.
Comparing to DOGMA-m takes more than 5 hours (98% consumed
Technology mapping (gate decomposition and LUT mapping) algorithms
DOGMA-m speed_up TOS-TUM (medium effort)
CutMap single-output multiple-output
Circuits D A T(s) D A T(s) D A T(s) D A T(s)
count 5 31 1.0 3 52 12.2 2 42 8.4 3 38 24.7
rot 7 261 13.2 6 251 71.1 7 404 117.5 8 291 612.0
too_large 5 149 7.5 5 112 24.3 9 324 465.0 8 168 1395.4
C6288 22 723 213.0
des 5 969 263.9 - 4 704 1586.8 -
subtotal2 139 6266 1103.3 139 11294 15792.6
ratio 1.00 1.00 1.00 0.87 0.94 17.60 1.00 1.80 14.31 1.01 1.11 29.83

Table

6 Mapping results resulted from structural (DOGMA-m), algebraic (speed_up),
and Boolean (TOS) gate decomposition approaches on C rugged .
by speed_up) to map 23 benchmarks (not including des) but obtains significantly better results: 13%
smaller mapping depth and 6% smaller mapping area. The results on C432 show the largest contrast
between the performance of speed_up and the efficiency of DOGMA-m: speed_up results in a
mapping depth of 8 in more than 2 hours while DOGMA-m results in a mapping depth of 11 in 6.6
seconds. TOS-s and TOS-m do not return mapping solutions in allocated CPU times for 3 and 8
benchmarks, respectively. Comparing to the other two approaches, TOS-s obtains smaller mapping
depth on count,9sym m l,alu2,alu4 and t481, and TOS-m obtains smaller mapping area
on 9symml, cordic, x1, alu2 and t481. It is worth noting that TOS is extremely successful
for 9symml and t481. The results indicate that functional decomposition based mapping approaches
require longer computation time to obtain good results, especially on circuits of medium to large sizes.
Overall, from these experiments, we conclude that DOGMA-m can obtain the best mapping results
among five structural gate decomposition algorithms under comparison, and is much more efficient in
terms of runtime (over 17 and times faster, respectively) comparing to the algebraic decomposition
algorithm speed_up and the functional decomposition approach TOS. However, speed_up obtains the
best results among compared approaches.
6. Conclusion
In this paper, we present an in-depth study of structural gate decomposition for depth-optimal
technology mapping in LUT-based FPGA designs. We show that any structural gate decomposition in
K-bounded networks can only result in a smaller depth in K-LUT mapping solutions regardless of the
decomposition algorithm used. Therefore, it is always beneficial to decompose circuits into 2-bounded
networks for depth minimization when structural decompositions are applied. We prove that the
structural gate decomposition problem in depth-optimal technology mapping is NP-hard for K-unbounded
networks when the LUT input size K - 3 and remains NP-hard for K-bounded networks when K - 5. We
propose two new algorithms, named DOGMA and DOGMA-m, which combine the level-driven node
packing technique in Chortle-d and the network flow based labeling technique in FlowMap, for
structural gate decomposition. DOGMA-m decomposes multiple gates simultaneously to exploit
common fanins. The following experimental results have been observed. First, the optimal mapping
depth and the optimal duplication-free mapping area can be reduced by 16% if 5-bounded networks are
decomposed structurally into 2-bounded networks. Second, applying the rugged script for technology
independent logic optimization before technology mapping can result in 40% to 50% area reduction with
only marginal increase in depth, while significantly reduce the runtime of structural decomposition
algorithms. Third, DOGMA-m results in the smallest mapping depth and mapping area among five
structural gate decomposition algorithms under comparison. Finally, comparing three algorithms
DOGMA-m, speed_up, and TOS, which take structural, algebraic, and Boolean (functional
gate decomposition approaches respectively, DOGMA-m can decompose all tested
benchmarks in a short time, while speed_up and TOS fail to obtain results on some benchmarks.
However, speed_up results in 13% smaller depth and 6% smaller area in final mapping solutions
comparing to DOGMA-m.

Acknowledgement

The authors are very grateful to Mr. Legl in Professor Antreich's group in the Institute of Electronic
Design Automation, Technical University of Munich, Germany, for providing us with the TOS logic
synthesis package. The authors would like to acknowledge the supports from NSF Young Investigator
(NYI) Award MIP-9357582, grants from Xilinx, Quickturn, and Lucent Technologies under the
California MICRO programs, and software donation from Synopsys.



--R

"The Decomposition of Switching Functions,"
"DAG-Map: Graph-based FPGA Technology Mapping for Delay Optimization,"
"Beyond the Combinatorial Limit in Depth Minimization for LUT-Based FPGA Designs,"
"FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs,"
"On Area/Depth Trade-off in LUT-Based FPGA Technology Mapping,"
"On Nominal Delay Minimization in LUT-Based FPGA Technology Mapping,"
"Combinational Logic Synthesis for LUT Based Field Programmable Gate Arrays,"
"Simultaneous Depth and Area Minimization in LUT-Based FPGA Mapping,"
"Structural Gate Decomposition for Depth-Optimal Technology Mapping in LUT-based FPGA Designs,"
"RASP: A General Logic Synthesis System for SRAM-based FPGAs,"
"A Generalized Tree Circuit,"
"Synthesis and Optimization of Digital Circuits,"
"TOS-2.2 Technology Oriented Synthesis User Manual,"
"Chortle: A Technology Mapping Program for Lookup Table -Based Field Programmable Gate Arrays,"
"Chortle-crf: Fast Technology Mapping for Lookup Table -Based FPGAs,"
"Technology Mapping of Lookup Table-Based FPGAs for Performance,"
Computer and Intractability: A Guide to the Theory of NP- Completeness
Fundamentals of Computer Algorithms
"An Iterative Area/Performance Trade-Off Algorithm for LUT-based FPGA Technology Mapping,"
"FPGA Synthesis using Function Decomposition,"
"Performance-Directed Technology Mapping for LUT-Based FPGAs - What Role Do Decomposition and Covering Play?,"
"A Boolean Approach to Performance-Directed Technology Mapping for LUT-Based FPGA Designs,"
"Performance Directed Synthesis for Table Look Up Programmable Gate Arrays,"
"Minimization Over Boolean Graphs,"
"Logic Synthesis for VLSI Design,"
"Performance Directed Technology Mapping for Look-Up Table Based FPGAs,"
"SIS: A System for Sequential Circuit Synthesis,"
"Algorithms for Multi-level Logic Optimization,"
"Functional Multiple-Output Decomposition: Theory and an Implicit Algorithm,"
"Edge-Map: Optimal Performance Driven Technology Mapping for Iterative LUT Based FPGA Designs,"
--TR
Chortle-crf: Fast technology mapping for lookup table-based FPGAs
Algorithms for multilevel logic optimization
Performance directed technology mapping for look-up table based FPGAs
Edge-map
Simultaneous depth and area minimization in LUT-based FPGA mapping
On nominal delay minimization in LUT-based FPGA technology mapping
Functional multiple-output decomposition
Combinational logic synthesis for LUT based field programmable gate arrays
A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs
An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping
Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs
A Generalized Tree Circuit
Synthesis and Optimization of Digital Circuits
Computers and Intractability
DAG-Map
FPGA Synthesis Using Function Decomposition
Performance-Directed Technology-Mapping for LUT-Based FPGAs - What Role Do Decomposition and Covering Play?
simplification;technology mapping;delay minimization;system design;decomposition;logic optimization;programmable logic;computer-aided design of VSLI;synthesis;FPGA