We ascribe beauty to that which is simple; which has no superfluous parts; which exactly answers its end…
—R. W. Emerson, The Conduct of Life, on “Beauty,” 1871Logic optimization transforms a given function such that some quality of result (QoR) is improved, preserving the functional equivalence and meeting the given constraints. The QoR measure can be area, performance, power, testability, routability, and manufacturability.
We can employ logic optimization at various stages in the VLSI design flow. After register transfer level (RTL) synthesis, we obtain a netlist in terms of generic gates. For a generic gate, the function is well-defined. However, other attributes of a generic gate, such as timing, area, and power, are not well-defined. A logic optimization tool crudely estimates them and improves some QoR measures of the circuit. This task is known as technology-independent logic optimization.
Post technology-independent logic optimization, we map the netlist to the cells of the given technology libraries. This task is known as technology mapping or mapping. Post-mapping, we can apply logic optimization and improve QoR measures of the cell-instantiated netlist. This task is known as technology-dependent logic optimization.
In this chapter, we will discuss technology-independent logic optimizations. We will discuss technology-dependent logic optimizations in Chapter 17 (“Timing-driven optimizations”) and Chapter 19 (“Power-driven optimizations”).
There are two distinct types of technology-independent logic optimizations: sequential logic optimization and combinational logic optimization. In sequential logic optimization, we typically optimize the finite state machine (FSM) representation by state minimization and state encoding. In combinational logic optimization, we optimize the combinational logic elements in a circuit. We can divide combinational logic optimization techniques further into two categories: two-level logic optimization and multilevel logic optimization [1]. These two types of techniques differ in their Boolean function representation and have distinct merits and demerits. In practice, synthesis tools apply both these types of optimizations.
In this chapter, we describe logic optimization that works on a generic-gate netlist. However, estimating the cost of various implementations for a generic-gate netlist is challenging. We can use crude measures such as gate count, literal count, and number of logic levels to estimate the cost of an implementation. These measures typically work well for area estimation but are not good for timing or delay estimation. Therefore, often, the objective of technology-independent logic optimization is to minimize the area of a circuit.