# BDD-Based Topology Optimization for Low-Power DTIG FinFET Circuits

Authors: Haiyan Ni; Jianping Hu; Xuqiang Zhang; Haotian Zhu
Journal: Active and Passive Electronic Components
 (2019)

---

## Abstract

This paper proposed a logic synthesis method based on binary decision diagram (BDD) representation. The proposed method is optimized for dual-threshold independent-gate (DTIG) FinFET circuits. The algorithm of the BDD-based topology optimization is stated in detail. Some kinds of feature subgraph structures of a BDD are extracted by the extraction algorithm and then fed to mapping algorithm to get a final optimized circuit based on predefined DTIG FinFET logic gates. Some MCNC benchmark circuits are tested under the proposed synthesis method by comparing with ABC, DC tools. The simulations show that the proposed synthesis method can obtain performance improvement for DTIG FinFET circuits.


---

## Body

## 1. Introduction

As a 3D transistor, FinFET is more efficient than the traditional devices because it can suppress short channel effect (SCE) and drain induced barrier lowering (DIBL) [1–6]. FinFET can operate in common-gate (CG) mode, whose two gates are tied together naturally and can be used like a traditional single-gate device with improved performances, or in independent-gate (IG) mode, whose two gates can be used as two separated single-gate devices in parallel or series on special conditions [2].Today’s VLSI is usually designed by “standard cell” method [7]. Among the design flow, synthesis is an important process, which transforms the high level design to low level netlists form composed by standard cells. Currently, standard cell libraries are basically built on the basis of CMOS or CG FinFET devices. The synthesis tools, such as commercial tools like Synopsys Design Compiler (DC), public-domain tools like ABC [8], and synthesis algorithms like factorization-based methods, usually utilizing these single-gate standard cell libraries to optimize the circuit topology. However, according to our research, DTIG FinFET-based circuits have excellent performances and can be used in modern VLSI circuits [9–11]. So it has an emerging need to develop a comprehensive method based on DTIG FinFETs.As a powerful representation of logic function, binary decision diagram (BDD) is widely used in computer science to solve graph algorithms and matrix-operation, even artificial intelligence problems. It also can be applied in VLSI design to construct the topology of the circuits and detect and optimize the circuits [12–14]. The efficiency of the BDD is always determined by the variable order of the functions. Since the variable ordering problem is a NP-complete [15, 16], there are many approximation heuristic methods have been found to efficiently solve this problem [12, 17–19].The paper described a circuit topology optimization method based on BDD technology to compose the DT IG FinFET circuits by using the predefined DTIG FinFET basic logic cells. It is organized as follows. In Section2, we introduce the predefined DTIG FinFET logic gates briefly, and in Section 3 we state some theorems and an algorithm of feature modules extraction in BDD graph. The mapping algorithm is also included in Section 3. And in Section 4, we realize the algorithms and verify the effectiveness of the method by testing the MCNC benchmarks. Finally, we conclude in Section 5.


## 2. DTIG FinFET Cell Library

Compared with single-gate devices, such as CMOS or CG FinFET, DTIG FinFET can design more flexible circuits by using of the low-threshold (low-Vth) and high-threshold (high-Vth) devices [2, 3, 9, 11, 20]. We have built a mini DTIG FinFET logic cells library for further using and as shown in Figure 1 are two examples and their CG comparisons. The DTIG FinFET logic cells have more compact structures than the CG FinFET logic cells, and thus they would have more advantages in transistor count, delay, and power dissipation than CG FinFET cells, as examples shown in Table 1. All gates in the library, which are composed by low-Vth transistors and high-Vth ones with parameters extracted from TCAD simulations, have been verified by Hspice with the BSIMIMG model from UC Berkeley [21].Table 1
Performance comparison of some example cells.
Cells T.Count Delay (ps) Power (μW) CG IG CG IG CG IG  NAND 4 2 5.6 5.1 11.8 5.5  NOR 4 2 5.5 4.7 11.8 3.0  NAND3 6 4 9.2 9.7 8.5 4.9  AOI 6 4 7.7 7.3 15.6 5.9  OAI 6 4 6.6 6.4 16.8 9.5  XOR 10 8 4.0 3.4 54.3 31.7Figure 1
The basic logic cells realized by the CG FinFETs and DTIG FinFETs, respectively. (a) NAND, (b) NOR.
(a)
NAND (b)
NOR


## 3. The Algorithms of Synthesis DTIG Logic Circuits

Firstly, we give some definitions about BDD and feature structure. Next, we give some theorems related to BDD subgraph extraction and prove them. Finally, we describe the implementations of BDD-based extraction algorithm and mapping algorithm.


### 3.1. Definitions

Binary decision diagrams (BDD) is proposed by Akers [22] as a method to representation of logic function. The methods based on BDD have been widely used in the representation and design of VLSI [23]. For the convenience of further discussion, we introduce several definitions related to BDD and its subgraph extraction firstly.Definition 1 (binary decision diagram (BDD)).
BDD has been defined in [22, 24] detailed; here we briefly describe some concepts. A BDD, as an example shown in Figure 2(a), is a rooted directed acyclic graph which is used to represent a Boolean function as (1)f=v1v4+v-1v3+v-1v-4v-5+v-2v3The BDD graph can be represented in formal language as G=V,E, where V and E are the node set and edge set, respectively. V contains two types of nodes, named as nonterminal nodes (circular form in the figure), and terminal nodes (block form in the figure). Every nonterminal node, labelled with an input variable vi∈G((i=1,2,…,n), has two children,low(vi)∈V andhigh(vi)∈V, and two relative edges,else(vi)∈E andthen(vi)∈E, connecting to the two children, respectively. Here in this paper, theelse(vi) andthen(vi) edges are denoted as dotted line and solid line in the figures, respectively. A terminal node vi∈V has not any child and outgoing edges and is only labelled with a value (vi)∈{0,1}.Figure 2
(a) A BDD example representing the Boolean logic equation (1), (b)–(f) its extracted BDD subgraphs, (g) MUX realization directly from (a), (h) the AOI and OAI cells mapped by the extracted BDD subgraphs (e), and (f), (i) the optimized result.When a BDD is used to compute a logic functionf(v1,v2,…,vn), we recursively compute the function from the root node (here assuming that it is vi) to the terminal node 0 or 1:(2)fvi=v-iflowvi+vifhighviwhere v¯i is the complementary logic of vi. Because the production of 0 and any logic is 0, we can omit the paths from root to 0-terminal and reserve the computations from root to 1-terminal.The BDD mentioned in this paper actually refers to reduced ordered binary decision diagram (ROBDD) [25–27], which is a type of variant BDD with input variables specially ordered and simplified structure with distinct nodes. There are many algorithms to get the ROBDD from BDD by efficiently ordering the variables and removing the redundant variables in literatures [15–19].Definition 2 (feature structure).
A feature structure is a special subgraph in a BDD,Gs=Gi⊆G(i=1,2,3,…), which can be mapped to a DTIG FinFET basic logic gate, such as AND/NAND, OR/NOR, AOI, XOR, and MUX. Here Gi is a subgraph in G rooted by vi with its children and the descendants.From Figure2(a), we can extract some BDD subgraph, as shown in Figures 2(b)–2(f). Among them, subgraphs in Figures 2(c)–2(e) can be realized with the DTIG FinFET logic gates that are AOI, OAI, AND, and NOR, respectively. Therefore, all these structures are feature structures. For example, Figure 2(b) is an extracted subgraph from Figure 2(a) that can be realized by an AOI cell, and Figure 2(c) can be realized by an OAI, as shown in Figure 2(h). The structure in Figure 2(f) cannot be mapped to any logic cell; therefore it is not a feature structure.On the other hand, for a nonterminal node in BDD, we can always realize by a MUX cell directly [22, 28]. So, we can map the BDD shown in (1) to a MUX-based netlist directly as shown in Figure 2(g).


### 3.2. Theorems of Extraction Algorithm

Theorem 3.
For a nonterminal nodevi of a BDD, we assume that its two children are vx with node function f(vx) and vy with node function f(vy). If a nonterminal node vj with function f(vj) and one of its two outgoing edges are connecting to vi and another edge connecting to vx or vy, the nodes group (vi,vj,vx,vy) can construct as a feature structure of AND/NAND/OR/NOR.Proof.
Assuming thatvx = high(vi) = low(vj), vy = low(vi) and vi = high(vj), as shown Figure 3(a).
According to Definition1, there is a function shown in (3) and the derivations (4) and (5) from Figure 3(a).(3)fvj=v-jfvx+vjvifvx+v-ifvy=fvxvi+v-j+fvyv-ivj(4)=fvxv-ivj¯+fvyv-ivj(5)=fvxv-ivj¯+fvyv-ivj
From (4) and (5), we can map the BDD subgraph to one of four feature structures of NAND, AND, OR, and NOR as shown in Figures 3(b)–3(e).
Similarly, the other cases satisfying the condition of Theorem3 will get similar results and also can be proven easily.Figure 3
One case of Theorem3 and relative feature structures. (a) One case of BDD subgraph, (b) NAND structure, (c) AND structure, (d) OR structure, and (e) NOR structure.Theorem 4.
For a node group(vi,vx,vy,vj) satisfying the condition of Theorem 3, assuming that there exists a nonterminal node vk with function f(vk) and vx is a common child of vj and vi and vy is just a child of vi, when one outgoing edge of vk connects to node vj and the other edge connects to node vx, then the nodes vi, vx, vy, vj, vk and their relative edges construct a feature structure of three-input AND/NAND/OR/NOR logic.
Otherwise, when one outgoing edge ofvk connects to node vj and the other edge connects to node vi or vy, the nodes vi, vx, vy, vj, vk and their relative edges construct a feature structure of three-input AOI/OAI logic.Proof.
Firstly we consider the first case as shown in Figure4(a).
Assuming thatvx = high(vi) = low(vj) = low(vk) and vy = low(vi), according to (2) in Definition 1, there is (6) and its derivations as follows:(6)fvk=v-kvx+vkfvj=v-kfvx+vkfvxv-ivj¯+fvyv-ivj=fvxv-k+vi+v-j+fvyvkv-ivj(7)=fvxvkv-ivj¯+fvyvkv-ivj(8)=fvxv-k+vi+v-j+fvyv-k+vi+v-j¯
From (7) and (8), we can get the results as shown in Figures 4(b)–4(e).
Now we consider another case in Theorem4; assuming that vj = high(vk), vi = low(vk), vx = high(vi) = low(vj) = low(vk) and vy = low(vi), according to (2) in Definition 1, there is (9) and its derivations as follows:(9)fvk=vkfvj+v-kvifvx+v-ifvy=vkfvxv-ivj¯+fvyv-ivj+v-kvifvx+v-ifvy=fvxvi+vkv-j+fvyv-iv-k+vj(10)=fvxvi+vkv-j+fvyvi+vkv-j¯(11)=fvxv-iv-k+vj¯+fvyv-iv-k+vj
From (10) and (11), we can get the results of Theorem 4.Figure 4
One case of Theorem4 and relative feature structures: (a) one case of BDD subgraph, (b) AND3, (c) NAND3, (c) OR3, and (d) NOR3.Theorem 5.
For two nodesvi, vj in a BDD graph, assume that vi is thelow child and thehigh child of vj at the same time, if thelow child vi has two outgoing edges,then andelse, connecting to vx and vy, respectively, while thehigh child vi has two outgoing edges,then andelse, connecting to vy and vx, respectively. The subgraph including vj, vi, vx, vy can be construct as a feature structure of XOR/XNOR logic.Proof.
From Theorem5, we can show it in Figure 5.
According to (2) in Definition 1, we have(12)fvj=vjvifvx+v-ifvy+v-jv-ifvx+vifvy=fvxvjvi+v-jv-i+fvyvjv-i+v-jvi(13)=fvxvj⊙vi+fvyvj⊕vi
From (13), the subgraph can be constructed as XOR/XNOR logic, as shown in Figures 5(b) and 5(c).Figure 5
The case in Theorem5: (a) BDD subgraph, (b) XOR, and (c) XNOR.


### 3.3. BDD-Based Node Extraction Algorithm

According to the definitions and the theorems above mentioned, we have developed a feature structure extraction algorithm for a given BDD, which contains four subroutines to finish the extraction procedure. The subroutine 1 outputs the reduced ordering form of the BDD graph from an input logic function f. The extracted BDD subgraphs of the feature structures will be obtained through the processes from subroutines 2 to 4 successively. In each subroutine, some parts of the BDD are marked as the different feature structures. The order of the algorithm flow is carefully arranged. As shown in Table1, in the proposed DTIG FinFET cell library, NAND/NOR cells can reduce the number of transistors more than the single-gate gates, AOI/OAI/NAND3/NOR3 cells the second, and XOR cells the least. The extraction order of the feature structure is in this order to get the most improvement. When the whole algorithm procedure is finished, we will obtain the optimized BDD and the feature structures, which can be fed to the mapping algorithm to further process.In the algorithm of the subroutine 1, as shown in Algorithm1, we generate an initial reduced ordered BDD from the input logic function by using a sorting algorithm like the traditionalbubble sort algorithm. When subroutine 1 is finished, an optimal ordered BDD form will be obtained.Algorithm 1:The algorithm of subroutine 1 in the BDD-based extraction algorithm.
Algorithm of Subroutine1: Input: f=f(v1,v2…vi,…vj…vn) Output: G[]: node set of BDD form 1:G[] ← bdd_init(f) 2: sum_src← bdd_nodecount(G[]) 3:fori = 1 ton do 4:forj = i ton do 5:   bdd_swapvar(vi,vj) 6:   sum_ex← bdd_nodecount(G[]) 7:ifsum_ex ≤ sum_src then 8:    sum_src← sum_ex 9:elsesum_ex > sum_src 10:    bdd_swapvar(vi,vj) 11:end if 12:end for 13:end forThe subroutine 2, as shown in Algorithm2, searches for a father vj of each node vi in the optimal ordered BDD from subroutine 1.Algorithm 2:The algorithm of subroutine 2 in the BDD-based extraction algorithm.
Algorithm of subroutine2: Input: G[]: node set from subroutine 1 Output: Gsa[]: set of AND/NAND2 sub-graph Output:Gso[]: set of OR/NOR sub-graph 1:for eachviinG[]do 2:(vx,vy) ← children(vi) 3:for eachvjinG[]do 4:iflow(vj)=vithen 5:If high(vj) = vx OR high(vj) = vy then 6:fOR-NOR←fOR-NORmark(vi,vi,vx,vy,E(vj,vi,vx,vy)) 7:    Gso[k]←fOR-NOR 8:end if 9:else ifhigh(vj)=vithen 10:iflow(vj)=vxORlow(vj)=vythen 11:fAND-NAND ← mark(vi,vi,vx,vy,E(vj,vi,vx,vy)) 12:    Gsa[]←fAND-NAND 13:end if 14:end if 15:end for 16:end forWe markvj as a father of vi and vx, vy as two children of vi. If the node group (vi, vj, vx, vy) meets the condition of Theorem 3, i.e., both vi and vx (or vy) are the children of vj and we extract the subgraph containing the nodes vj, vi, vx, vy and their relative edges and then mark the subgraph as a feature structure of OR/NOR (fOR-NOR) or AND/NAND (fAND-NAND). When this subroutine is finished, all feature structures of OR/NOR or AND/NAND are extracted and stored in the setsGso andGsa, respectively.The algorithm of the subroutine 3, as shown in Algorithm3, searches for a node group (vi, vj, vk, vx, vy) which meets the condition of Theorem 4. First we check each subgraph in the result setGsafrom subroutine 2 and the origin BDD graph set G from subroutine 1; if a node vk exists in G which satisfies the cases of Theorem 4, we extract a new subgraph containing the node vk, and the corresponding subgraph in the setGsa and their edges, and we mark the new subgraph as a new feature structure of AND3/NAND3 or AOI. Then, we store this feature structure into the setGsa3 for AND3/NAND3 or setGsaoi for AOI, respectively. Finally, the corresponding subgraph in the setGsa should be deleted because it has been covered by the new generated feature structure.Algorithm 3:The algorithm of subroutine 3 in the BDD-based extraction algorithm.
Algorithm of Subroutine3: Input: Gsa: set of AND/NAND2 sub-graph from subroutine2; Input:G[]: node set of BDD from subroutine 1 Output: Gsaoi[]: set of AOI/OAI sub-graph Output: Gsand3[]: set of AND/NAND31 sub-graph 1:for eachgs inGsa do 2:vj ←root(gs) 3:for eachvkinBDDdo 4:iflow(vk)=vjORhigh(vk)=vjthen 5:ifvksatisfyTheorem 4 case 1then 6:fANDNAND31←mark(vi,vj,vk,vx,vy,E(vi,vj,vk,vx,vy)) 10:     Gsa3[]←fANDNAND31 11:else ifvksatifyTheorem 4 case2then 12:fAOIOAI←mark(vi,vj,vk,vx,vy,E(vi,vj,vk,vx,vy)) 13:     Gsaoi[]←fAOIOAI 14:end if 15:end if 16:end for 17:end forAccording to Theorem5, algorithm of the subroutine 4, as shown in Algorithm 4, searches for the special groups of nodes in the optimal ordered BDD from subroutine 1 and then constructs them as new feature structures. If the nodes of a group satisfy the conditions of Theorem 5, (a) a node (denoted as vk) is the same father of the other two nodes (denoted as vi and vj) of the same variable, (b) there exist two nodes that are the same children of vi and vj, and (c) low(vj) = high(vi) and low(vi) = high(vj), then we extract the group and their edges as a feature structure of XOR logic and then store it into setGsxor.Algorithm 4:The algorithm of subroutine 4 in the BDD-based extraction algorithm.
Algorithm of Subroutine 4 1:Input: G[]: node set of source BDD from subroutine 1 2:Output: Gsxor[]: set of XOR/NXOR sub-graph 3:for eachvkinG[]do 4:for eachviinG[]do 5:for eachvjinG[]do 6:iflow(vk) = viANDhigh(vk) = vjOR high(vk) = viANDlow(vk) = vjthen 7:ifvalue(vj) = value(vi)then 8:iflow(vi) = high(vj)ANDhigh(vi) = low(vj)then 9:       (vx,vy) ←children(vi,vj) 10:fXORNXOR←mark(vi,vj,vk,vx,vy,E(vi,vj,vk,vx,vy)) 11:       Gsxor[]←fXORNXOR 12:end if 13:end if 14:end if 15:end for 16:end for 17:end forWhen these subroutines are all finished, the proposed extraction algorithm generates the optimal ordered BDD form of a given logic function and obtains all the feature structures in the BDD.


### 3.4. The Mapping Algorithm

The extraction algorithms described above only aims at simplifying Boolean functions. In the next logic synthesis steps, we need to replace the logic gates with physical cells in the cell library by using a mapping algorithm. We propose the feature structure mapping algorithm with four steps. In step 1, after reading the BDD and its subgraphs from the extraction algorithm, we exclude the redundant, or covered, subgraphs. Then, in step 2, we map the source BDD to a circuit composed of MUXs completely and map the feature structures to the IG FinFET logic gates. In step 3, we give the final optimized circuit by replacing some MUXs subcircuits with logic cells. Step 1 to step 3 are shown as examples in Figures2(a)–2(h) and the result is as shown in Figure 2(i).


## 3.1. Definitions

Binary decision diagrams (BDD) is proposed by Akers [22] as a method to representation of logic function. The methods based on BDD have been widely used in the representation and design of VLSI [23]. For the convenience of further discussion, we introduce several definitions related to BDD and its subgraph extraction firstly.Definition 1 (binary decision diagram (BDD)).
BDD has been defined in [22, 24] detailed; here we briefly describe some concepts. A BDD, as an example shown in Figure 2(a), is a rooted directed acyclic graph which is used to represent a Boolean function as (1)f=v1v4+v-1v3+v-1v-4v-5+v-2v3The BDD graph can be represented in formal language as G=V,E, where V and E are the node set and edge set, respectively. V contains two types of nodes, named as nonterminal nodes (circular form in the figure), and terminal nodes (block form in the figure). Every nonterminal node, labelled with an input variable vi∈G((i=1,2,…,n), has two children,low(vi)∈V andhigh(vi)∈V, and two relative edges,else(vi)∈E andthen(vi)∈E, connecting to the two children, respectively. Here in this paper, theelse(vi) andthen(vi) edges are denoted as dotted line and solid line in the figures, respectively. A terminal node vi∈V has not any child and outgoing edges and is only labelled with a value (vi)∈{0,1}.Figure 2
(a) A BDD example representing the Boolean logic equation (1), (b)–(f) its extracted BDD subgraphs, (g) MUX realization directly from (a), (h) the AOI and OAI cells mapped by the extracted BDD subgraphs (e), and (f), (i) the optimized result.When a BDD is used to compute a logic functionf(v1,v2,…,vn), we recursively compute the function from the root node (here assuming that it is vi) to the terminal node 0 or 1:(2)fvi=v-iflowvi+vifhighviwhere v¯i is the complementary logic of vi. Because the production of 0 and any logic is 0, we can omit the paths from root to 0-terminal and reserve the computations from root to 1-terminal.The BDD mentioned in this paper actually refers to reduced ordered binary decision diagram (ROBDD) [25–27], which is a type of variant BDD with input variables specially ordered and simplified structure with distinct nodes. There are many algorithms to get the ROBDD from BDD by efficiently ordering the variables and removing the redundant variables in literatures [15–19].Definition 2 (feature structure).
A feature structure is a special subgraph in a BDD,Gs=Gi⊆G(i=1,2,3,…), which can be mapped to a DTIG FinFET basic logic gate, such as AND/NAND, OR/NOR, AOI, XOR, and MUX. Here Gi is a subgraph in G rooted by vi with its children and the descendants.From Figure2(a), we can extract some BDD subgraph, as shown in Figures 2(b)–2(f). Among them, subgraphs in Figures 2(c)–2(e) can be realized with the DTIG FinFET logic gates that are AOI, OAI, AND, and NOR, respectively. Therefore, all these structures are feature structures. For example, Figure 2(b) is an extracted subgraph from Figure 2(a) that can be realized by an AOI cell, and Figure 2(c) can be realized by an OAI, as shown in Figure 2(h). The structure in Figure 2(f) cannot be mapped to any logic cell; therefore it is not a feature structure.On the other hand, for a nonterminal node in BDD, we can always realize by a MUX cell directly [22, 28]. So, we can map the BDD shown in (1) to a MUX-based netlist directly as shown in Figure 2(g).


## 3.2. Theorems of Extraction Algorithm

Theorem 3.
For a nonterminal nodevi of a BDD, we assume that its two children are vx with node function f(vx) and vy with node function f(vy). If a nonterminal node vj with function f(vj) and one of its two outgoing edges are connecting to vi and another edge connecting to vx or vy, the nodes group (vi,vj,vx,vy) can construct as a feature structure of AND/NAND/OR/NOR.Proof.
Assuming thatvx = high(vi) = low(vj), vy = low(vi) and vi = high(vj), as shown Figure 3(a).
According to Definition1, there is a function shown in (3) and the derivations (4) and (5) from Figure 3(a).(3)fvj=v-jfvx+vjvifvx+v-ifvy=fvxvi+v-j+fvyv-ivj(4)=fvxv-ivj¯+fvyv-ivj(5)=fvxv-ivj¯+fvyv-ivj
From (4) and (5), we can map the BDD subgraph to one of four feature structures of NAND, AND, OR, and NOR as shown in Figures 3(b)–3(e).
Similarly, the other cases satisfying the condition of Theorem3 will get similar results and also can be proven easily.Figure 3
One case of Theorem3 and relative feature structures. (a) One case of BDD subgraph, (b) NAND structure, (c) AND structure, (d) OR structure, and (e) NOR structure.Theorem 4.
For a node group(vi,vx,vy,vj) satisfying the condition of Theorem 3, assuming that there exists a nonterminal node vk with function f(vk) and vx is a common child of vj and vi and vy is just a child of vi, when one outgoing edge of vk connects to node vj and the other edge connects to node vx, then the nodes vi, vx, vy, vj, vk and their relative edges construct a feature structure of three-input AND/NAND/OR/NOR logic.
Otherwise, when one outgoing edge ofvk connects to node vj and the other edge connects to node vi or vy, the nodes vi, vx, vy, vj, vk and their relative edges construct a feature structure of three-input AOI/OAI logic.Proof.
Firstly we consider the first case as shown in Figure4(a).
Assuming thatvx = high(vi) = low(vj) = low(vk) and vy = low(vi), according to (2) in Definition 1, there is (6) and its derivations as follows:(6)fvk=v-kvx+vkfvj=v-kfvx+vkfvxv-ivj¯+fvyv-ivj=fvxv-k+vi+v-j+fvyvkv-ivj(7)=fvxvkv-ivj¯+fvyvkv-ivj(8)=fvxv-k+vi+v-j+fvyv-k+vi+v-j¯
From (7) and (8), we can get the results as shown in Figures 4(b)–4(e).
Now we consider another case in Theorem4; assuming that vj = high(vk), vi = low(vk), vx = high(vi) = low(vj) = low(vk) and vy = low(vi), according to (2) in Definition 1, there is (9) and its derivations as follows:(9)fvk=vkfvj+v-kvifvx+v-ifvy=vkfvxv-ivj¯+fvyv-ivj+v-kvifvx+v-ifvy=fvxvi+vkv-j+fvyv-iv-k+vj(10)=fvxvi+vkv-j+fvyvi+vkv-j¯(11)=fvxv-iv-k+vj¯+fvyv-iv-k+vj
From (10) and (11), we can get the results of Theorem 4.Figure 4
One case of Theorem4 and relative feature structures: (a) one case of BDD subgraph, (b) AND3, (c) NAND3, (c) OR3, and (d) NOR3.Theorem 5.
For two nodesvi, vj in a BDD graph, assume that vi is thelow child and thehigh child of vj at the same time, if thelow child vi has two outgoing edges,then andelse, connecting to vx and vy, respectively, while thehigh child vi has two outgoing edges,then andelse, connecting to vy and vx, respectively. The subgraph including vj, vi, vx, vy can be construct as a feature structure of XOR/XNOR logic.Proof.
From Theorem5, we can show it in Figure 5.
According to (2) in Definition 1, we have(12)fvj=vjvifvx+v-ifvy+v-jv-ifvx+vifvy=fvxvjvi+v-jv-i+fvyvjv-i+v-jvi(13)=fvxvj⊙vi+fvyvj⊕vi
From (13), the subgraph can be constructed as XOR/XNOR logic, as shown in Figures 5(b) and 5(c).Figure 5
The case in Theorem5: (a) BDD subgraph, (b) XOR, and (c) XNOR.


## 3.3. BDD-Based Node Extraction Algorithm

According to the definitions and the theorems above mentioned, we have developed a feature structure extraction algorithm for a given BDD, which contains four subroutines to finish the extraction procedure. The subroutine 1 outputs the reduced ordering form of the BDD graph from an input logic function f. The extracted BDD subgraphs of the feature structures will be obtained through the processes from subroutines 2 to 4 successively. In each subroutine, some parts of the BDD are marked as the different feature structures. The order of the algorithm flow is carefully arranged. As shown in Table1, in the proposed DTIG FinFET cell library, NAND/NOR cells can reduce the number of transistors more than the single-gate gates, AOI/OAI/NAND3/NOR3 cells the second, and XOR cells the least. The extraction order of the feature structure is in this order to get the most improvement. When the whole algorithm procedure is finished, we will obtain the optimized BDD and the feature structures, which can be fed to the mapping algorithm to further process.In the algorithm of the subroutine 1, as shown in Algorithm1, we generate an initial reduced ordered BDD from the input logic function by using a sorting algorithm like the traditionalbubble sort algorithm. When subroutine 1 is finished, an optimal ordered BDD form will be obtained.Algorithm 1:The algorithm of subroutine 1 in the BDD-based extraction algorithm.
Algorithm of Subroutine1: Input: f=f(v1,v2…vi,…vj…vn) Output: G[]: node set of BDD form 1:G[] ← bdd_init(f) 2: sum_src← bdd_nodecount(G[]) 3:fori = 1 ton do 4:forj = i ton do 5:   bdd_swapvar(vi,vj) 6:   sum_ex← bdd_nodecount(G[]) 7:ifsum_ex ≤ sum_src then 8:    sum_src← sum_ex 9:elsesum_ex > sum_src 10:    bdd_swapvar(vi,vj) 11:end if 12:end for 13:end forThe subroutine 2, as shown in Algorithm2, searches for a father vj of each node vi in the optimal ordered BDD from subroutine 1.Algorithm 2:The algorithm of subroutine 2 in the BDD-based extraction algorithm.
Algorithm of subroutine2: Input: G[]: node set from subroutine 1 Output: Gsa[]: set of AND/NAND2 sub-graph Output:Gso[]: set of OR/NOR sub-graph 1:for eachviinG[]do 2:(vx,vy) ← children(vi) 3:for eachvjinG[]do 4:iflow(vj)=vithen 5:If high(vj) = vx OR high(vj) = vy then 6:fOR-NOR←fOR-NORmark(vi,vi,vx,vy,E(vj,vi,vx,vy)) 7:    Gso[k]←fOR-NOR 8:end if 9:else ifhigh(vj)=vithen 10:iflow(vj)=vxORlow(vj)=vythen 11:fAND-NAND ← mark(vi,vi,vx,vy,E(vj,vi,vx,vy)) 12:    Gsa[]←fAND-NAND 13:end if 14:end if 15:end for 16:end forWe markvj as a father of vi and vx, vy as two children of vi. If the node group (vi, vj, vx, vy) meets the condition of Theorem 3, i.e., both vi and vx (or vy) are the children of vj and we extract the subgraph containing the nodes vj, vi, vx, vy and their relative edges and then mark the subgraph as a feature structure of OR/NOR (fOR-NOR) or AND/NAND (fAND-NAND). When this subroutine is finished, all feature structures of OR/NOR or AND/NAND are extracted and stored in the setsGso andGsa, respectively.The algorithm of the subroutine 3, as shown in Algorithm3, searches for a node group (vi, vj, vk, vx, vy) which meets the condition of Theorem 4. First we check each subgraph in the result setGsafrom subroutine 2 and the origin BDD graph set G from subroutine 1; if a node vk exists in G which satisfies the cases of Theorem 4, we extract a new subgraph containing the node vk, and the corresponding subgraph in the setGsa and their edges, and we mark the new subgraph as a new feature structure of AND3/NAND3 or AOI. Then, we store this feature structure into the setGsa3 for AND3/NAND3 or setGsaoi for AOI, respectively. Finally, the corresponding subgraph in the setGsa should be deleted because it has been covered by the new generated feature structure.Algorithm 3:The algorithm of subroutine 3 in the BDD-based extraction algorithm.
Algorithm of Subroutine3: Input: Gsa: set of AND/NAND2 sub-graph from subroutine2; Input:G[]: node set of BDD from subroutine 1 Output: Gsaoi[]: set of AOI/OAI sub-graph Output: Gsand3[]: set of AND/NAND31 sub-graph 1:for eachgs inGsa do 2:vj ←root(gs) 3:for eachvkinBDDdo 4:iflow(vk)=vjORhigh(vk)=vjthen 5:ifvksatisfyTheorem 4 case 1then 6:fANDNAND31←mark(vi,vj,vk,vx,vy,E(vi,vj,vk,vx,vy)) 10:     Gsa3[]←fANDNAND31 11:else ifvksatifyTheorem 4 case2then 12:fAOIOAI←mark(vi,vj,vk,vx,vy,E(vi,vj,vk,vx,vy)) 13:     Gsaoi[]←fAOIOAI 14:end if 15:end if 16:end for 17:end forAccording to Theorem5, algorithm of the subroutine 4, as shown in Algorithm 4, searches for the special groups of nodes in the optimal ordered BDD from subroutine 1 and then constructs them as new feature structures. If the nodes of a group satisfy the conditions of Theorem 5, (a) a node (denoted as vk) is the same father of the other two nodes (denoted as vi and vj) of the same variable, (b) there exist two nodes that are the same children of vi and vj, and (c) low(vj) = high(vi) and low(vi) = high(vj), then we extract the group and their edges as a feature structure of XOR logic and then store it into setGsxor.Algorithm 4:The algorithm of subroutine 4 in the BDD-based extraction algorithm.
Algorithm of Subroutine 4 1:Input: G[]: node set of source BDD from subroutine 1 2:Output: Gsxor[]: set of XOR/NXOR sub-graph 3:for eachvkinG[]do 4:for eachviinG[]do 5:for eachvjinG[]do 6:iflow(vk) = viANDhigh(vk) = vjOR high(vk) = viANDlow(vk) = vjthen 7:ifvalue(vj) = value(vi)then 8:iflow(vi) = high(vj)ANDhigh(vi) = low(vj)then 9:       (vx,vy) ←children(vi,vj) 10:fXORNXOR←mark(vi,vj,vk,vx,vy,E(vi,vj,vk,vx,vy)) 11:       Gsxor[]←fXORNXOR 12:end if 13:end if 14:end if 15:end for 16:end for 17:end forWhen these subroutines are all finished, the proposed extraction algorithm generates the optimal ordered BDD form of a given logic function and obtains all the feature structures in the BDD.


## 3.4. The Mapping Algorithm

The extraction algorithms described above only aims at simplifying Boolean functions. In the next logic synthesis steps, we need to replace the logic gates with physical cells in the cell library by using a mapping algorithm. We propose the feature structure mapping algorithm with four steps. In step 1, after reading the BDD and its subgraphs from the extraction algorithm, we exclude the redundant, or covered, subgraphs. Then, in step 2, we map the source BDD to a circuit composed of MUXs completely and map the feature structures to the IG FinFET logic gates. In step 3, we give the final optimized circuit by replacing some MUXs subcircuits with logic cells. Step 1 to step 3 are shown as examples in Figures2(a)–2(h) and the result is as shown in Figure 2(i).


## 4. Algorithm Implementation

The synthesis algorithms including extraction and mapping are both implemented in MATLAB platform, and for comparison of the circuit optimization effectiveness, the ABC and DC synthesis tools are also applied to the same circuits. For a fair comparison, all methods use the same DTIG FinFET cell library we built in Section2. Finally, all the circuits from ABC, DC, and the proposed method are simulated by using Hspice with the BSIMIMG model from UC Berkeley [21]. Figure 6 presents the simulation results of the MCNC benchmark circuits.Figure 6
Comparison between the simulation results of ABC, DC, and this work.
(a) (b) (c) (d)As shown in Figure6(a), for almost all tested circuits, the count of transistors in the circuit optimized by this work is the least among the comparisons. Therefore, in most cases, the proposed method can get the most effective area since the area occupation is determined by the number of the transistors.The average power dissipation can be expressed by(14)Pav=NPav1=NplowPlow+phighPhighwhere Pav is the average power of a circuit,N is the transistor count in a circuit,Pav1 is the average power of one transistor,Plow andPhigh are the average power of one low-Vth and high-Vth IG FinFET, respectively, andplow andphigh are the possibility of low-Vth and high-Vth IG FinFET in a circuit, respectively.From (14), if the possibility of transistors in kinds of circuits is close to each other, the average power of a circuit is determined by the count of transistor in a circuit. From Figure 6(b), we can see the trend of the power dissipation is close to the transistor count trend shown in Figure 6 and still almost all the circuits synthesized by this work have the least power dissipation, and the fact fits the prediction of (14) very well. The delay analysis is more complicated than power dissipation. The maximum delay of a circuit depends on the critical path. The more transistors on the critical path are, the greater delay should be. For a DTIG FinFET circuit, the high-threshold device has more delay because it has low on-current, which further reduces the switch speed and increases the delay. So as shown in Figure 6(c), we find that the circuit synthesized by this work has no obvious advantage in terms of delay.The power delay product (PDP) can evaluate a circuit more comprehensively because it considers both delay and power consumption. As seen from Figure6(d), compared with ABC and DC, all of the circuits synthesized by this work have obvious advantage of PDP.


## 5. Conclusion

In this paper, we have presented a BDD-based synthesis method to optimize DTIG FinFET circuits. We search the BDD graph of an input logic to find feature structures and map them to DTIG FinFET basic logic gates. The algorithms are implemented in MATLAB and compared with ABC and DC by simulation of the MCNC benchmark circuits. The result shows that the proposed method can significantly improve the performances of DTIG FinFET circuits in area occupation, power consumption, and PDP.



---

*Source: 8292653-2019-07-18.xml*