Logic Synthesizer with Optimizations in Two Phases.

Logic networks and then their corresponding transistor circuits to be laid out on integrated chips have been traditionally designed manually, spending long time and repeatedly making mistakes and correcting them. As the cost and size of transistor circuits continue to decline, logic networks that are realized by transistor circuits have been designed with an increasingly large number of logic gates. Manual design of such large logic networks is becoming too time-consuming and prone to design mistakes, thus necessitating automated design. Logic synthesizers are automated logic synthesis systems used for this purpose and transform the given logic functions into technology-dependent logic circuits that can be easily realized as transistor circuits. The quality of technology-dependent logic circuits derived by logic synthesizers is not necessarily better than manually designed ones, at least for those with a small number of logic gates, but technology-dependent logic circuits for those with millions of logic gates cannot be designed manually for reasonably short times.

Automated design of logic networks has been attempted since the early 1960s [3]. Since the beginning of the 1960s, IBM has pushed research of design automation in logic design. In the 1970s, a different type of algorithm, called the Transduction method, was devised for automated design of logic networks, as described in Chapter 37. Since the beginning of the 1980s, the integration size of integrated chips has tremendously increased, research and development of automated logic synthesis has become very active at several places [1,2,4,9] and powerful logic synthesizers have become commercially available [6].

There are different types of logic synthesizers. But here, let us describe a logic synthesizer that derives a technology-dependent logic circuit in two phases [7], although there are logic synthesizers where, unlike the following synthesizer in two phases, only technology-dependent optimization is used throughout the transformation of the given logic functions into technology-dependent logic circuits that are easily realizable as transistor circuits:

In the first phase, an optimum logic network that is not necessarily realizable as a transistor circuit is designed by Boolean algebraic approaches which are easy to use. This phase is called technology- independent optimization.

In the second phase, the logic network derived in the first phase is converted into a technology- dependent logic circuit that is easily realizable as a transistor circuit. (Note that all logic synthe- sizers, including the logic synthesizer in two phases, must eventually have technology-dependent logic circuits that are easily realizable, as transistor circuits.) This phase is called technology- dependent optimization.

The logic synthesizer in two phases has variations, depending on what optimization algorithms are used, and some of them have the advantage of short processing time.

Suppose a logic network is designed for the given functions by some means, including design methods described in the previous chapters. Figure 36.1 is an example of such logic networks. Then the logic network is to be processed by many logic optimization algorithms in sequence, as shown in Figure 36.2. As illustrated in Figure 36.1, a subnetwork (i.e., several logic gates that constitute a small logic network by themselves) that has a single output logic function is called a node, and its output function is

expressed as a sum-of-products form. Thus, the entire logic network is expressed as a network of the nodes. During the first phase of technology-independent optimization, each node does not correspond to a transistor circuit. But the second phase of technology dependent-optimization, as illustrated in Figure 36.3, converts the logic network derived by the first phase into technology-dependent circuits, in which each node corresponds to a cell [i.e., a small transistor circuit (shown in each dot-lined loop in Figure 36.3)] in a library of cells. The cell library consists of a few hundred cells where a cell is a small transistor circuit with good layout. These cells are designed beforehand and can be repeatedly used for logic synthesis.

A typical flow of logic optimization in the logic synthesis in two phases works as follows and is illustrated in Figure 36.2, although there may be variations:

1. Sweep, illustrated in Figure 36.4: Nodes that do not have any fan-outs are deleted. A node that consists of only a buffer or an inverter node is merged into next nodes. The following rules optimize nodes that have inputs of constant values, 0 or 1:

A ⋅ 1 = A, A ⋅ 0 = 0, A ∨ 1 = 1, A ∨ 0 = A

2. Collapsing (also often called flattening), illustrated in the upper part of Figure 36.5: More than one node is merged into one node, so that it has a more complicated logic function than before.

3. Two-level logic minimization: Two-level logic minimization [2] is carried out at each node, as illustrated in the lower part of Figure 36.5. (PLA minimization programs to be described in Chapter 45 can be used for this purpose.)

4. Decomposition, illustrated in Figure 36.6: Decomposition [4] extracts common expressions from the sum-of-products forms of nodes, adds intermediate nodes whose logic functions are the same as the common expressions, and re-expresses the sum-of-products form at the original nodes, using the intermediate nodes. This transformation, called weak division (described in Chapter 32), reduces the area of the circuit.

5. Technology mapping [5], illustrated in Figure 36.7: Technology mapping finds an appropriate map- ping of the network of the nodes onto the set of cells in the target cell library. Technology mapping works as follows:

a. Select a tree structure: a tree structure where all nodes have one fan-out node is extracted from the circuit.

b. Decompose it to two-input NANDs and inverters: a selected tree is decomposed to two-input NANDs and inverters. The result of this decomposition is called a subject tree.

c. Matching: all cells in the target cell library are also decomposed to two-input NANDs and inverters, as shown in Figure 36.8. Pattern matching between the subject tree and the cells in the cell library is carried out to get the best circuit.

Timing or power optimization, that is, minimization of delay time or power consumption under other conditions (e.g., minimization of delay time without excessively increasing power consumption, or minimization of power consumption without sacrificing speed too much) is also carried out by changing the structure of the nodes and their corresponding cells in the library.

6. Fanout optimization, illustrated in Figure 36.9: Fanout optimization attempts to reduce delay time by the following transformations.

a. Buffering: inserting buffers and inverters in order to reduce load capacitance of logic gates that have many fanouts. In particular, a critical path that is important for performance is separated from other fanouts [8].

b. Repowering: replacing a logic gate that has many fanouts, by another cell in the cell library that has greater output power (its cell is larger) and the same logic function as the original one. This does not change the structure of the circuit [8].

c. Cloning: creating a clone node for a logic gate that has many fanouts and distributing the fanouts among these nodes to reduce the load capacitance.

This is a typical logic optimization flow. Many other optimization algorithms can be incorporated within this flow to synthesize better circuits.