Logic minimization algorithms for VLSI synthesis. (English) Zbl 0565.94020

Brayton, Robert K.; Hachtel, Gary D.; McMullen, Curtis T.; Sangiovanni- Vincentelli, Alberto L.

The Kluwer International Series in Engineering and Computer Science. Boston - The Hague - Dordrecht - Lancaster: Kluwer Academic Publishers. IX, 193 p. Dfl. 119.00; $ 32.50; £24.75 (1984).

The object of this book is the area of logic (function) minimization and the presentation of new algorithms appropriate for VLSI applications. The automated synthesis of a combinational circuit system can be partitioned into several tasks: functional design, logic design and physical design. The functional description of the VLSI circuits can be effectively done within a special language, Programmable Logic Arrays (PLA), whose macros are largely used to describe the physical implementation of logic functions. The technological advantage of PLA relies on the straight- forward mapping between the symbolic representation and the physical implementation.
The functional description is transformed into a logic description in terms of Boolean variables (functions). Optimal logic design, the major topic of this book, transforms the logic representation to obtain a convenient implementation.
Among the important programs created for automated logic minimization should be mentioned: MINI (developed at IBM in the middle of the 70s), PRESTO (D. W. Brown, 1981), SHRINK (J. P. Roth, 1980), SPAM - a version of MINI (S. Kang, 1981). PRESTO differs from MINI in the way the expansion process is carried out. MINI generates the complement of the logic function to check if the expansion of an implicant does not change the coverage of the function. PRESTO does not compute the complement but the expansion process requires a check on whether all the minterms covered by the expanded implicant are covered by some other implicant of the cover, which, in general, costs more computation time.
ESPRESSO-I (1981), created by the authors of the present book, uses the MINI’s technique of computing the complement of the PLA representation since it proved to be superior: on the average, the initial cost involved by the complement computing (reduced also by the discovery of better complementation algorithms) was offset by the more efficient expansion procedure that is allowed. Iteration as used by MINI is generally worthwhile for VLSI design. The initial investment in computing the complement is then amortized over the additional steps required by the iterations.
ESPRESSO-II (1982) basically follows the sequence of top-level transformations of iterated expansion-reduction pioneered by MINI. In January 1984 a new version of ESPRESSO-II was implemented in C (by Richard Rudell). The algorithms of ESPRESSO-II achieve a high level of efficiency, mainly through the use of a common theme, the ”unate recursive paradigm”. This means, roughly, that a logic function is recursively divided until each part becomes unate (monotone). The required operation (e.g. complement, reduction, irredundant cover) is then performed on the unate function in a highly efficient way. Finally, the results are merged appropriately to obtain the required result.
The book is organized as follows: Chapter 1 is an efficient introduction to the problem. Chapters 2 and 3 provide the theoretical foundations (notations, basic definitions) for logic and logic function manipulation. In particular, chapter 3 introduces the unate (monotone) functions and basic results concerning them. The unate recursive paradigm is presented and illustrated with the SIMPLIFY algorithm. All algorithms are based on a single fundamental strategy: a recursive divide and conquer. The decomposition is based on the Shannon expansion. The definition is given for matrix representation of logic functions and the corresponding algorithms are described. The authors use, for the algorithm description, a pseudo-computer language which allows to a competent reader to implement the algorithms directly.
Chapter 4 is the technical heart of the book. Each of the algorithms of ESPRESSO-II is described in detail along with the supporting theorems and proofs. The algorithms are outlined as structured procedures. COMPLEMENT, EXPAND, ESSENTIAL-PRIMES, IRREDUNDANT-COVER, REDUCE, LAST-GASP, MAKE- SPARSE are the basic routines. Many of them rely heavily on the TAUTOLOGY algorithm. The way these routines fit together to form ESPRESSO-II is also described. Chapter 5 presents a new method for using any two-valued logic minimizer for functions with multiple-valued inputs: it involves a particular encoding of the multiple-valued inputs and the creation of a don’t care set before the use of the two-valued logic minimizer. In this way, ESPRESSO-II can be effectively used to minimize multiple-valued logic functions. The method is efficient and practical as far as the number of possible values for a given input is not very large.
Chapter 6 reports the results of testing ESPRESSO-IIAPL and ESPRESSO-IIC on different PLAs. The final size, the sparsity and the amount of computation time expanded to achieve the result were the most important parameters of the experiments. The correlations among these parameters make the reader acquainted with the degree of optimization that can be achieved by the two versions of ESPRESSO-II, in APL and C.
Chapter 7 summarizes the new ideas incorporated in ESPRESSO-II and documents their effectiveness in comparison with other logic minimizers: MINI, POP, PRESTO. Some modifications introduced in the C-language version of ESPRESSO-II are also discussed. Other applications of logic minimization and directions for further research are presented and an updated bibliography of 164 titles is provided.
The book is of great interest for all those working in or being related to the new computer technologies: from the theoretical computer scientist to the hardware design engineer. It offers a concrete description of the logic minimization algorithms for VLSI design and an effective possibility, by ESPRESSO-II procedures, to work with them. In short, a quite remarkable realization in the field.

Reviewer: N.Curteanu

MSC:

94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
94-04	Software, source code, etc. for problems pertaining to information and communication theory

Keywords:

minimization algorithms; VLSI optimization programs; minimization of logic functions; combinational circuit; VLSI circuits; Programmable Logic Arrays; PLA; logic design; automated logic minimization; VLSI design; ESPRESSO-II; multiple-valued logic functions