Boolean Circuit Rewiring: Bridging Logical and Physical Designs

By Tak-Kei Lam, Wai-Chung Tang, Xing Wei and 2 more

Demonstrates techniques which will allow rewiring rates of over 95%, enabling adoption of deep sub-micron chips for industrial applications

Logic synthesis is an essential part of the modern digital IC design process in semi-conductor industry. This book discusses a logic synthesis technique called “rewiring” and its latest technical advancement in term of rewirability. Rewiring technique has surfaced in academic research since 1993 and there is currently no book available on the market which systematically and comprehensively discusses this rewiring technology. The authors cover logic transformation techniques with concentration on rewiring. For many decades, the effect of wiring on logic structures has been ignored due to an ideal view of wires and their negligible role in the circuit performance. However in today’s semiconductor technology wiring is the major player in circuit performance degeneration and logic synthesis engines can be improved to deal with this through wire-based transformations. This book introduces the automatic test pattern generation (ATPG)-based rewiring techniques, which are recently active in the realm of logic synthesis/verification of VLSI/SOC designs.

• Unique comprehensive coverage of semiconductor rewiring techniques written by leading researchers in the field
• Provides complete coverage of rewiring from an introductory to intermediate level
• Rewiring is explained as a flexible technique for Boolean logic synthesis, introducing the concept of Boolean circuit transformation and testing, with examples
• Readers can directly apply the described techniques to real-world VLSI design issues
• Focuses on the automatic test pattern generation (ATPG) based rewiring methods although some non-ATPG based rewiring methods such as graph based alternative wiring (GBAW), and “set of pairs of functions to be distinguished” (SPFD) based rewiring are also discussed

A valuable resource for researchers and postgraduate students in VLSI and SoC design, as well as digital design engineers, EDA software developers, and design automation experts that specialize in the synthesis and optimization of logical circuits.

• Language: English
• Publisher: Wiley
• Release date: Jan 11, 2016
• ISBN: 9781118750148

Book preview

List of Figures

List of Tables

Table 1.1 Behavior of the basic Boolean operators

Table 2.1 Truth table and minterms of logical AND function

Table 2.2 SPFDs of the gates in Figure 2.16

Table 2.3 SPFDs of the gates in Figure 2.21

Table 3.1 Comparison of rewiring ability of SPFD-based rewiring algorithms for four-LUT FPGA designs

Table 3.2 Comparison of rewiring ability for different atomic SPFD assignment methods

Table 4.1 CPU time analysis for IRRA

Table 4.2 CPU time analysis for ECR

Table 4.3 Comparison on combinational benchmarks between IRRA and ECR

Table 4.4 Comparison on sequential benchmarks between IRRA and ECR

Table 4.5 Comparison on combinational benchmarks between NAR and ECR

Table 4.6 FPGA technology mapping for ILR combined with different rewiring engines on optimized benchmarks, LUT size = 4

Table 4.7 Comparison between ECR and FECR

Table 4.8 Effectiveness of different windowing sizes

Table 4.9 Comparison between ECR, FECR, and CECR

Table 4.10 Detailed statistics for CECR

Table 4.11 Effectiveness of windowing technique

Table 5.1 Experimental results of area reduction by using approaches in Plaza et al. (2007) and Chen and Wang (2010) and our approach

Table 5.2 Iterations of optimization in our approach

Table 5.3 Benchmark information

Table 5.4 Real versus estimated HPWL reduction

Table 5.5 Effectiveness of our framework for wirelength reduction of placement and global routing

Table 5.6 Effectiveness of our algorithm compared to the traditional peak-first algorithm and a recent work

Table 5.7 Comparison of our algorithm and the DCP algorithm

Table 5.8 Results of depth-ILR followed by area-ILR with FlowSYN ( c05-math-0208 )

Table 5.9 Result of area-ILR over DAOMap ( c05-math-0221 )

Table 5.10 Result of area-ILR over DAOMap ( c05-math-0222 )

Table 5.11 Result of Area-ILR over IMap ( c05-math-0227 )

Table 5.12 Result of Area-ILR over IMap ( c05-math-0228 )

Table 5.13 Result of Area-ILR over imfs c05-math-0233 lutpack in ABC( c05-math-0234 )

Table 5.14 Result of Area-ILR on Commercial Benchmarks ( c05-math-0237 )

Table 5.15 Effect of area-ILR on VPR Delay performance ( c05-math-0243 )

Table 5.16 Effect of area-ILR on delay performance in commercial FPGAs ( c05-math-0245 )

Table 5.17 Result of area-ILR on circuits synthesized by BDS-pga ( c05-math-0262 )

Table 5.18 c05-math-0422 : Number of terminals versus net weight

Table 5.19 Experimental results on rewiring-based FPGA router

Table 5.20 Experimental results on rewiring-based technology mapping and routing

Table 5.21 Postlayout optimization by SPFD-ER

Table 5.22 Total cell areas of the circuits

Table 5.23 Power dissipation statistics

Preface

Our group has been working on wire-based logic restructuring (rewiring) for over a decade. Over the years, we have published numerous conference and journal papers on rewiring. As a recent major milestone, we have developed a rewiring scheme that reaches a near-complete rewiring rate ( f01-math-0001 ). This result demonstrates the high power of this kind of logic transformation techniques and the great potential of applying them on modern electronic design automation (EDA) tools.

Because of the aggressive and continuous scaling down of transistor sizes, to 45, 22 nm, and even below 16 nm, wires have become a dominant factor affecting circuit performance. Hence, rewiring is particularly suitable for today's nanometer technologies.

We could not find a book that focuses on and discusses rewiring techniques. Since rewiring techniques have become much more practical in nanometer technologies, we felt there was a need to publish a reference book to provide readers with the key ideas.

This book is of introductory to intermediate level. We hope this book will help in popularizing science, and the readers will find this book interesting and informative.

Tak-Kei Lam, Wai-Chung Tang, Xing Wei,

Yi Diao, and David Yu-Liang Wu

Introduction

The concepts of various major rewiring techniques are explained throughout the book gradually. First, readers will be presented with the basic ideas of rewiring. Next, the technical details of each kind of rewiring technique will be discussed in detail. Finally, the applications of rewiring techniques in various electronic design automation (EDA) areas will be introduced.

Intended Audience

Students studying computer/electronic engineering, academic staff, and even EDA engineers are the intended readers of this book. The readers should have some basic knowledge of Boolean algebra, logic gates, and graph theory. For readers without the related advanced knowledge, essential concepts will be introduced and explained throughout the book.

Type Conventions

The following conventions are used in this book:

Mathematical symbols and names of circuit elements, such as f02-math-0001 and f02-math-0002 , are typeset in this font.

Codes are typeset in this font.

Acknowledgments

Many people have contributed to this book in the forms of research output, implementations of algorithms, suggestions for content, and, last but not least, simply being encouraging. This book could never have been completed without their generous effort. We are very grateful to the following people for all they have done:

The authors of RAMBO, REWIRE, RAMFIRE, GBAW, IRRA, NAR, ECR, FECR, CECR, SPFD-based and all other rewiring techniques.

The authors of the typesetting system ngr001 and the plugins.

Chapter 1

Preliminaries

1.1 Boolean Circuits

A Boolean variable is a variable whose value can only be either 0 (false) or 1 (true) or unknown. Every Boolean variable has two literals. They are the normal form and the negation/complement of the variable. The negation of a variable always evaluates to the opposite value of the variable. Suppose c01-math-0001 is a Boolean variable; then its negation is c01-math-0002 . When c01-math-0003 is 1, c01-math-0004 is 0; when c01-math-0005 is 0, c01-math-0006 is 1. The literals of variable c01-math-0007 are then c01-math-0008 and c01-math-0009 .

A function consisting of Boolean variables is known as a Boolean function. It is a mapping between Boolean spaces. For example, the function c01-math-0010 is a mapping between the input space of c01-math-0011 Boolean variables and the output space of c01-math-0012 Boolean variables. We use c01-math-0013 to indicate the input variables or input values of the Boolean function c01-math-0014 .

The mapping between Boolean spaces is achieved by Boolean operators. The basic Boolean operators (operations) AND, OR, NOT, XOR, and XNOR are denoted as c01-math-0015 , and c01-math-0016 , respectively, in this book. We may omit the symbol c01-math-0017 for clarity. The behavior of the basic operators is listed in Table 1.1. Complex Boolean operators can be derived from these basic operators. In fact, only AND and NOT, or only OR and NOT, are sufficient to derive all other Boolean operations.

Table 1.1 Behavior of the basic Boolean operators

An example of Boolean function is c01-math-0023 , which computes the logical conjunction of variables c01-math-0024 and c01-math-0025 . A Boolean function may contain literals. The Boolean function c01-math-0026 is such an example that computes the logical conjunction of variable c01-math-0027 and the negation of variable c01-math-0028 . It may be surprising for readers who are not familiar with Boolean algebra to see a function c01-math-0029 . This function is actually nothing special but is normal and valid. It just means that, among the three variables, the value of variable c01-math-0030 is don't care. That is to say, the value of c01-math-0031 can be either 0 or 1, and c01-math-0032 . For another example, the function c01-math-0033 can be expanded into c01-math-0034 .

Observability don't cares (ODCs) (Damiani and De Micheli 1990) of a Boolean variable are the conditions under which the variable is not affecting any of the primary outputs. For example, if an input c01-math-0035 of an AND gate has the controlling value 0, its set of other inputs c01-math-0036 are unobservable no matter what values they have. The ODC of c01-math-0037 is c01-math-0038 . Satisfiability don't cares (SDCs) of a circuit node represent the local input patterns at the node that cannot be generated by the node's fanins. As a trivial example of SDC, if we connect all inputs of a two-input AND gate to a common signal, the values of its inputs can never be c01-math-0039 or c01-math-0040 .

Many rules in ordinary algebra, such as commutative addition and multiplication, associative addition and multiplication, and variable distribution, can be applied into Boolean algebra. Therefore, function

c01-math-0041

. For each of the conjunction term, it can be expanded by connecting it with all combinations of the literals of the missing variables by conjunction. Some additional important rules that are obeyed in Boolean algebra only include c01-math-0042 and c01-math-0043 . Regarding our example, it can be expanded as follows:

equation

Other rules can be derived from the basic rules easily. Since Boolean algebra is a vast area of study, even the elementary topics can cover a whole book. In this book, we shall not cover every detail.

Boolean functions can be realized in hardware using logic gates. A Boolean circuit or Boolean network is composed of gates and implements some Boolean functions. We simply use circuits or networks to represent Boolean circuits when the meaning is clear in the context. Figure 1.1 illustrates the logic gates implementing the basic Boolean functions. An example circuit composed of AND, OR, and NOT gates is shown in Figure 1.2(b). For gate c01-math-0045 , its inputs are c01-math-0046 and c01-math-0047 , so it is implementing the function c01-math-0048 . Regarding gate c01-math-0049 , its function is c01-math-0050 .

c01f001

Figure 1.1 Basic logic gates

c01f002

Figure 1.2 Directed acyclic graph representation of a circuit. (a) A directed acyclic graph; (b) a Boolean circuit

A less famous Boolean operator is the cofactor. The cofactor of a Boolean function c01-math-0051 with respect to a variable c01-math-0052 is c01-math-0053 c01-math-0054 . Suppose c01-math-0055 , c01-math-0056 , and c01-math-0057 . Similarly, the cofactor of a Boolean function c01-math-0058 with respect to the complement of a variable c01-math-0059 is c01-math-0060 c01-math-0061 . Suppose c01-math-0062 , c01-math-0063 . Every Boolean function can be expressed using Shannon's expansion. For example, c01-math-0064 . An example of a function with multiple inputs is

c01-math-0065

In general, Boolean circuits can be represented by directed acyclic graphs (DAGs). A DAG is a kind of graph in which two vertices may be connected by an edge pointing to either one of the vertices, such that there are no loops in the graph. With regard to a circuit, the vertices of its corresponding graph represent its gates, and the edges of the graph represent its wires. An example of a DAG is illustrated in Figure 1.2(a). It is in fact the corresponding graph representation for the circuit in Figure 1.2(b). For instance, the node c01-math-0066 in the graph represents the OR gate c01-math-0067 , and the edge from c01-math-0068 to c01-math-0069 corresponds to the target wire indicated in the figure.

Each node in a DAG is therefore associated with a Boolean function. Edges pointing toward a node are known as the fanins of the node, and edges leaving the node are known as the fanouts of the node. The source of a wire connecting c01-math-0070 to c01-math-0071 has a fanout c01-math-0072 , and the destination of the wire c01-math-0073 has a fanin c01-math-0074 . The number of fanins of a node c01-math-0075 is called the in-degree/fanin number of the node, which is denoted by c01-math-0076 . Similarly, the number of fanouts of node c01-math-0077 is called the out-degree/fanout number and is denoted by c01-math-0078 . A special case of a DAG is the and-inverter graph (AIG) in which every node represents an AND gate. The values of the edges may be complemented to implement all Boolean functions.

In a circuit, the nodes whose fanin numbers are 0 or have no fanins are known as primary inputs (PIs), and the nodes whose fanout numbers are 0 or have no fanouts are known as primary outputs (POs).

Node c01-math-0079 is a transitive fanin (TFI) of node c01-math-0080 if there is a path from node c01-math-0081 to node c01-math-0082 . Node c01-math-0083 is said to be a transitive fanout (TFO) of node c01-math-0084 if is reachable from node c01-math-0085 . All TFIs of a node form the TFI cone of the node, and all TFOs of a node form the TFO cone of the node.

The most famous problem regarding Boolean circuits is the Boolean satisfiability problem. It is always known as the SAT problem. This problem is to determine whether there is any assignment of values to the variables of a given Boolean function such that the function can be evaluated to 1. For the Boolean function c01-math-0086 , the value assignments c01-math-0087 allows c01-math-0088 to evaluate to 1. It is a solution that satisfies this SAT problem instance.

1.2 Redundancy