12.3  Inside a Logic Synthesizer

The logic synthesizer parses the Verilog of Figure 12.1 and builds an internal data structure (usually a graph represented by linked lists). Such an abstract representation is not easy to visualize, so we shall use pictures instead. The first Karnaugh map in Figure 12.5 (a) is a picture that represents the sel signal (labeled as the input to the three MUXes in the schematic of Figure 12.1 ) for the case when the inputs are such that a[2]b[2] = 00 . The signal sel is responsible for steering the smallest input, a or b , to the output of the comparator/MUX. We insert a '1' in the Karnaugh map (which will select the input b to be the output) whenever b is smaller than a . When a = b we do not care whether we select a or b (since a and b are equal), so we insert an 'x' , a don’t care logic value, in the Karnaugh map of Figure 12.5 (a). There are four Karnaugh maps for the signal sel , one each for the values a[2]b[2] = 00 , a[2]b[2] = 01 , a[2]b[2] = 10 , and a[2]b[2] = 11 .

Next, logic minimization tries to find a minimum cover for the Karnaugh maps—the smallest number of the largest possible circles to cover all the '1' s. One possible cover is shown in Figure 12.5 (b).

In order to understand the steps that follow we shall use some notation from the Berkeley Logic Interchange Format ( BLIF ) and from the Berkeley tools misII and sis . We shall use the logic operators (in decreasing order of their precedence): '!' (negation), '*' (AND), '+' (OR). We shall also abbreviate Verilog signal names; writing a[2] as a2 , for example. We can write equations for sel and the output signals of the comparator/MUX in the format that is produced by sis , as follows (this is the same format as input file for the Berkeley tool eqntott ):

sel = a1*!b1*!b2 + a0*!b1*!b2 + a0*a1*!b2 + a1*!b1*a2 + a0*!b1*a2 + a0*a1*a2 + a2*!b2;[12.1]

outp2 = !sel*a2 + sel*b2;[12.2]

outp1 = !sel*a1 + sel*b1;[12.3]

outp0 = !sel*a0 + sel*b0;[12.4]

Equations 12.1 – 12.4 describe the synthesized network . There are seven product terms in Eq.  12.1 —the logic equation for sel (numbered and labeled in the drawing of the cover for sel in Figure 12.5 ). We shall keep track of the sel signal separately even though this is not exactly the way the logic synthesizer works—the synthesizer looks at all the signals at once.

Logic optimization uses a series of factoring, substitution, and elimination steps to simplify the equations that represent the synthesized network. A simple analogy would be the simplification of arithmetic expressions. Thus, for example, we can simplify 189 / 315 to 0.6 by factoring the top and bottom lines and eliminating common factors as follows: (3 ¥ 7 ¥ 9) / (5 ¥ 7 ¥ 9) = 3 / 5. Boolean algebra is more complicated than ordinary algebra. To make logic optimization tractable, most tools use algorithms based on algebraic factors rather than Boolean factors.

Logic optimization attempts to simplify the equations in the hope that this will also minimize area and maximize speed. In the synthesis results presented in Table 12.3 , we accepted the default optimization settings without setting any constraints. Thus only a minimum amount of logic optimization is attempted that did not alter the synthesized network in this case.

The technology-decomposition step builds a generic network from the optimized logic network. The generic network is usually simple NAND gates ( sis uses either AND, or NOR gates, or both). This generic network is in a technology-independent form. To build this generic network involves creating intermediate nodes. The program sis labels these intermediate nodes [n] , starting at n = 100 .

sel = [100] * [101] * [102] ;[12.5]

[100] = !( !a2 * [103] );

[101] = !( b2 * [103] );

[102] = !( !a2 * b2 );

[103] = !( [104] * [105] * [106] );

[104] = !( !a1 * b1 );

[105] = !( b0 * [107] );

[106] = !( a0' * [107] );

[107] = !( a1 * !b1 );

outp2 = !( [108] * [109] );[12.6]

[108] = !( a2 * !sel );

[109] = !( sel * b2 );

There are two other sets of equations, similar to Eq.  12.6 , for outp1 and outp0 . Notice the polarity of the sel signal in Eq.  12.5 is correct and represents an AND gate (a consequence of labeling sel as the MUX select input in Table 12.1 ).

Next, the technology-mapping step (or logic-mapping step) implements the technology-independent network by matching pieces of the network with the logic cells that are available in a technology-dependent cell library (an FPGA or standard-cell library, for example). While performing the logic mapping, the algorithms attempt to minimize area (the default constraint) while meeting any other user constraints (timing or power constraints, for example).

Working backward from the outputs the logic mapper recognizes that each of the three output nodes ( outp2 , outp1 , and outp0 ) may be mapped to a MUX. (We are using the term “node mapping to a logic cell” rather loosely here—an exact parallel is a compiler mapping patterns of source code to object code.) Here is the equation that shows the mapping for outp2 :

outp2 = MUX(a, b, c) = ac + b!c[12.7]

a = b2 ; b = a2 ; c = sel

The equations for outp1 and outp0 are similar.

The node sel can be mapped to the three-input majority function as follows:

sel = MAJ3(w, x, y) = !(wx + wy + xy) [12.8]

w = !a2 ; x = b2 ; y = [103] ;

Next node [103] is mapped to an OAI22 cell,

[103] = OAI22(w, x, y, z) = ! ((w + x)(y + z)) = (!w!x + !y!z) [12.9]

w = a0 ; x = a1 ; y = !b1 z = [107] ;

Finally, node [107] is mapped to a two-input NOR with one inverted input,

[107] = !(b1 + !a1) ; [12.10]

Putting Equations 12.7 – 12.10 together describes the following optimized logic network (corresponding to the structural netlist and schematic shown in Figure 12.3 ):

sel = !((( !a0 * !(a1&!b1) | (b1*!a1) ) * (!a2|b2) ) | (!a2*b2)) ;[12.11]

outp2 = !sel * a2 | sel * b2;

outp1 = !sel * a1 | sel * b1;

outp0 = !sel * a0 | sel * b0;

The comparator/MUX example illustrates how logic synthesis takes the behavioral model (the HDL input) and, in a series of steps, converts this to a structural model describing the connections of logic cells from a cell library.

When we write a C program we almost never think of the object code that will result. When we write HDL it is always necessary to consider the hardware. In C there is not much difference between i*j and i/j . In an HDL, if i and j are 32-bit numbers, i*j will take up a large amount of silicon. If j is a constant, equal to 2, then i*j take up hardly any space at all. Most logic synthesizers cannot even produce logic to implement i/j . In the following sections we shall examine the Verilog and VHDL languages as a way to communicate with a logic synthesizer. Using one of these HDLs we have to tell the logic synthesizer what hardware we want—we imply A. The logic synthesizer then has to figure out what we want—it has to infer B. The problem is making sure that we write the HDL code such that A = B. As will become apparent, the more clearly we imply what we mean, the easier the logic synthesizer can infer what we want.

[ Chapter start ] [ Previous page ] [ Next page ]