Multi-level logic minimization.

There are several possible design style alternatives for multilevel logic design:

• domino logic,
• Cmos static cells,
• standard cells,
• cascaded PLAs,
• Weinberger layouts,
• gate arrays,
• multilevel PLAs,
• special regular layouts (like for symmetric functions).

Currently, optimization programs are designed or are under design for most of these approaches. Structure of most of the systems is the following:

• front-end software converts the input high-level language design description (functional,behavioral,or structural) to internal representation of logic networks,
• logic optimizer minimizes network independently on technology, optimizing such criteria as number of gates, number of inputs, number of transistors,
• technology-dependent logical transformations are performed,
• topological optimizer (like folding of PLA, wire packing in Weinberger layout, etc.) is used to generate symbolic layout,

The systems that we are aware of include:

• LSS (Logic Synthesis System) of IBM [44, 45, 46, 47, 17, 19], for gate arays,
• Yorktown Silicon Compiler [20] - [25],
• Cascode Voltage Switches [74].
• MAMBO system [96],
• Domino Logic,

Three approaches currently exist to multilevel logic design:

• global optimization, (Yorktown Silicon Compiler, part of Angel [98] and FDS [72].
• local optimization (part of Angel, LSS, MAMBO).
• combination of the above.

Global optimization approaches include:

• decomposition of Boolean functions [5, 114, 147, 160, 161, 175]. An example of global optimization approach is given in [20] and was found efficient for single sided Cascade Voltage Switches. The approach of Brayton completely redesigns the network.

Algorithms used include:

1. extraction - common subexpressions are recognized and replaced with one variable,
2. collapsing - intermediate variables which do not offer savings are eliminated.
3. simplification - a two level Boolean expression is minimized by use of logic minimization algorithms,
4. decomposition - a function too large to be implemented in a target technology is factored and decomposed (FDS of Bell Labs).

The result of the first stages of compilation of high-level behavioral description program is the nonoptimized logical network. At this stage of design some transformations to optimize the network are possible, that hold true for arbitrary technology of network`s realization. These transformations consist, generally speaking, in removal of some parts of the network which do not influence its behavior (no path goes from them to an output of the network) and in the reduction of the number of inputs, according to the rules of the Boolean algebra. The parts of the network not connected to outputs can be found which is an indirect effect of some transformations executed at the previous stages of the structural implementation. The fact that such parts of network occur can be either the designer's error or rather a result of high level initial specification.

Reductions of the number of gates' inputs are also possible, as well as the number of gates in some cases. They result from constant ones and zeros on gates' inputs; it is usually an effect of applying, on some previous design stages, of the standard blocks (like registers, adders, multiplexers, comparators), with certain fixed input data. For instance application of an adder to add a variable, (like a four-bit bus), and a constant, (a four bit binary sequence), gives possibility of simplifying the adder. The adder in the resultant network will not retain its universality. The transformations applied to minimize such networks are rule-based. Each of them is very simple, however their successive usage sometimes permits for essential simplification of a network [Wiec 84a].

Next transformations optimize the network by applying a rule-based approach and this is done also independently of technology. An excellent example of this kind of system is one of GE, described in [51, 82, 87, 34]. Another system of this type was designed in IBM and its description can be found in [44] - [47], [10]. The transformational approach to NAND network design is presented in [120]. Other rule-based systems for arbitrary negative gates are described in [180, 181] and [162].

Another approach, which usually starts from a set of Boolean equations, is based on factorization [65, 20]. The basic factoring rules (like ab+ac=a(b+c)) can be usually applied in many places of the set of expressions, and applying some factorization prohibits another one. The point is to select optimum factorizations for large sets of logic equations. Factorization is strongly related to decomposition. Both the disjoint and the disjoint decompositions have been studied. The function shall be presented as a composition of some other functions, possibly operating on disjoint sets of input variables. The classical papers on decomposition of Boolean functions are [37, 39, 62] and [105]. A branch and bound algorithm to design optimum multilevel NAND networks was described by Davidson [50]. Another approach to multilevel design is presented in [118]. Approaches to design multilevel multi-output functions are discussed in [171]. A modern approach to decomposition and factoring was introduced in papers of Brayton and respective software is currently being implemented in IBM. Some other special structures of functions' realization are : three level circuits with NANDs [136], trees, cascades, and arrays of tunable gates. Problems of mapping circuits to different technologies, selecting modules, and partitioning are discussed in [83, 119, 35, 108]. A dynamic programming approach to optimal mapping of logic network to a set of modules is discussed in [158].

Interesting approaches to several partial problems in logic design are included in [8, 29, 31] and [66]. It seems that they can be used for efficient implementation of some new methods in a comprehensive global/local logic design system with various representations of logic functions.

Since EXOR gates are used in most arithmetical and many coding/telecommunication operations, design with this type of gates is important. Circuits that use many exors usually produce PLAs with large areas, research in multilevel synthesis methods with EXORs and ANDs, XNORS and ORs, or any other functional system including EXORs is very important from practical point of view. Many papers have been devoted to this topic in the past [4, 13, 189, 129, 146], but results are not widely used in industry. New research emphasizes programming efficiency and possibility of using these methods for wider categories of circuits in comprehensive general purpose global/local approaches.

In some systems logic minimization is done in conjunction with layout minimization, best examples are perhaps [163] and [149].