Synthesis:Optimization

Optimization

To yield the best results in optimization, it is important to give the compiler information about the real environment of the design. Constraints are declarations to define the special optimization goals for a specific circuit. Whether the design goal was met can easily be decided by checking  characteristic quantities like timing, area, or ca- pacity, or by comparing the result with previous results. During optimization there are two types of constraints in use:

• Design Rule Constraints (see table 6.1);

• Optimization Constraints (see table 6.2).

Design rule constraints are requirements depend- ing on technology. They always exist implicitly because of the selected target library. They are general rules for ensuring a correct function. For the compiler these requirements have the highest priority (table 6.1).

regarding area and speed have better chances of being taken into account for the circuit (table 6.2).

Consequence of optimization constraints

Synthesis is a complex process having many pa- rameters which can be changed. Some of them are discrete, some are continuous. Discrete parameters are the RTL architecture, logic function, as well as many switches in the synthesis tool to control the algorithm of synthesis statically. Continuous parameters describe, e.g., input or output delay times, capacitive loads, or clock periods.

To show the way a synthesis tool works in principle, it does not make sense to change all parameters at the same time. Looking at figures 6.16 . . . 6.18, mainly the area and speed of a given design are of interest. As stated in [6.4], it is assumed that the clock period obtained (which is nearly equivalent to the maximal delay in the critical path) is a measure of the operating speed, and that all other parameters related to time depend on it.

Figure 6.17 supplements the picture in fig. 6.16, where for each synthesized netlist its area depending on the constraints is displayed. The smaller the delay in the critical path, the bigger the area,  because of an increase in the degree of parallelism and the use of additional buffers.

Both results from fig. 6.16 and 6.17 combining yields the characteristic presentation in fig. 6.18. The graph connects individual points which correspond to a synthesis run (yielding a netlist) for a particular constraint. The behavior at the left side of the graph calls for some attention. In the attempt to realize the highest operating speed the results are chaotic. A minute change of a constraint causes a significant change in the area. This type of behavior can often be observed in algorithms having a randomly selected starting point.

Optimization strategies

Designs of digital circuits normally have hierar- chical levels. The top level of this hierarchy then consists only of blocks being connected with each other. Some blocks process data, others are only responsible for control. The internal structure of the blocks is different, too. Both aspects require an individual treatment during synthesis. In clearly structured components (e.g., a huge adder) it is desirable to maintain the structure and to use it during opimization. Within non-structured blocks it is the job of the synthesis tool to remove redundant logic and thus improve the structure of the circuit.

The structure of a circuit description can be recognized at a logical level as well as at the gate level. The logical level is independent of technology and is described by a set of boolean equations. The gate level of a circuit is made by a real implementation of the logical level introducing the target technology (fig. 6.19).

The purpose of an optimization on a logical level is to improve the structure of the digital design with- out changing the function. The first attempt leads to a reduction of the product terms as well as to smaller circuits and to smaller propagation delays. Because area and speed are the main criteria during a circuit’s optimization the strategy used plays an important role. The optimization strategy consists of a meaningful application of the following steps or a combination of both:

• Flattening;

• Structuring [6.7].

Flattening

Flattening identifies an optimization step which solves all expressions in boolean equations enclosed in brackets by applying the distributive law and which removes all intermediate variables. An optimization of operating speed is the primary goal.

The result of the flattening is, as is seen in the example, a sum of product terms. This does not always yield the circuit version having the highest operating speed, because some variables are present in more than one product term, which causes an increased load (fan out) by a large number of gate inputs connected to the driver involved. This aspect is shown in fig. 6.20a.

Flattening can be followed by an algorithm to minimize the boolean equations. Optimization tools can minimize each output separately, or deal with all outputs together at the same time during the process of minimization.

The first case produces an optimal result for the individual output. In the second case product terms

needed more than once are shared. Identical product terms frequently appear when many outputs are depending on nearly all inputs. Minimization in this case is very efficient when looking at the chip area. In fig. 6.20b the total size in the example has not changed, but the loads are distributed more evenly.

Structuring

The primary goal of structuring is to find things which the circuit structure has in common. Therefore a flat representation will receive a structure by introducing intermediate variables.

The intermediate variable stands for a partial function and which can be used more than once to simplify the boolean equation. As a consequence of sharing partial functions less chip area is taken, but, on the other hand, the logical depth in the critical path can be increased in some cases.

Structuring is often recommended in the first opti- c mization run. After that a detailed specification of delay times between input and output can be used to optimize the critical path without changing the uncritical regions. The attempt to satisfy additional constraints can lead to an increase in area, because run time optimization can cause an increase in parallelism. This parallelism means a duplication of one path or another (fig. 6.21 and 6.22).

Optimization of two-stage logic

The progress of logic synthesis and optimization visible in these days results from the investigation of combinatorial logic in two stages. The most popular method of this type of description is the sum product term, also known as the disjunctive function. Here, according to boolean algebra, AND terms form the product types in the first stage. These are added in a second stage using OR gates where, strictly speaking, inverters located at gate inputs form a third stage. Additional forms of combinatorial logic are OR/AND, AND/OR, NOR/NOR or NAND/NAND (fig. 6.23 and 6.24).

The practical realization of two-staged combinatorial logic can be found in components having a PAL structure (programmable array logic). Be- cause of the direct mapping of the mathematical description to the silicon area, these structures are highly suitable for an automatic logic or layout synthesis. The relatively simple structure yields short delay times and a high operating speed of the realized circuit. In this case the operating speed can be estimated very precisely in an early design stage.

However, the two-stage logic of regular operators such as addition, subtraction, parity, is growing excessively in size when the number of inputs goes up. For example, when calculating parity the EXOR operation of N signals causes 2N−1 product terms. Nevertheless, optimized two-stage forms of representation are very often the starting point of multistage logic synthesis algorithms.

The goal of an optimization of a two-stage logic is to find a boolean function equivalent to the one present at the start of optimization, that has an optimum number of product terms and literals (direct or negated variables in the boolean function). The main attention is dedicated to the problem of finding a set of product terms which completely describes the function presented at the starting point, but shows the least redundancy possible. The solution has two phases:

• Decomposition of the boolean function to be optimized to a set of product terms, in such a way that none of these terms is present in another term (prime implicants);

• The choice of a minimal set of product terms to obtain a complete description of the original function.

Quine McCluskey Algorithm

An algorithm using both of these steps is the method of Quine McCluskey [6.2]. The approach depends on a suitable combination of product terms.

Modern minimization programs are based on that method. Its mechanism will be explained best by an example: specific output values of a four bit counter abcd have to be decoded. Hence a boolean function y consisting of minterms, as in table 6.3, is examined. A minterm is a product term which contains all input values.

In the first step a comparison (pair by pair) is performed to find product terms different only in one position. This position is replaced by an ‘X’ (table 6.4).

The terms of the result of the first step are com- pared in a second iteration (table 6.5) in the same way. However, now the restrictions apply that if two terms should be combined ‘X’ must now be located at an identical position, and only one more position (which would be replaced by ‘X’) can be different. After that combination five terms showing no similarity would be left.

The five left terms are used to choose a minimal set to realize all minterms. Therefore in the last step it will be marked in table 6.6 which minterms are Choosing from the columns A–E, columns can be removed in such a way that for each line at least one mark is still present. In the example this is column C. Its marks are part of column B and column E. If there are several possibilities for removing columns the columns having the highest number of literals (or the smallest number of ‘X’) should be removed. The remaining columns finally make up the solution (table 6.6).

The solution shows a significantly smaller number of product terms:

Optimization of sequential logic

The focus of the preceding chapter has been on the optimization of combinatorial logic. Methods to optimize sequential circuits are now discussed. A model of synchronous sequential circuits is the state machine, because it contains a combinatorial part and registers typical of that type of description.

State machines can be described by states and the present input signals. The combination of input signals and the present state (fig. 6.25) determines which state the machine is going to enter when the next clock event occurs. An approved form of presentation for state machines is the state transition diagram (fig. 6.26). Because of its level of abstraction, these diagrams describe behavior in the first place; they do not reflect the chip area needed or show information about possible clock speeds.

Minimization of states

When the overall complexity of a state machine is reduced, an economic use of resources is often a consequence. Fewer states means fewer storage elements. Fewer states means; generally speaking; fewer state transitions, which is a positive step when thinking about the optimization of chip area.

Algorithms for minimizing states are discussed in detail in [6.5]. A simple example explains the procedure for obtaining, starting with a given state transition diagram a state machine which has the

The first step of a minimization of states is to search the table for states which have, for a specific input value, identical output values and identical ‘next states’. In the example this is the case for the states S1 and S2. Because of that these states can be combined into one state.

Coding of states

To find a suitable coding of states is more difficult than it seems to be at first glance. The problem is to find a binary equivalent for every state in such a way as to optimize chip area and operating speed. The binary equivalent reflects the type of storage element (e.g., D, JK, or Toggle FF) and the type of coding of the states. There are three possible types of coding states: