Skip to main content
main-content

Über dieses Buch

The roots of the project which culminates with the writing of this book can be traced to the work on logic synthesis started in 1979 at the IBM Watson Research Center and at University of California, Berkeley. During the preliminary phases of these projects, the impor­ tance of logic minimization for the synthesis of area and performance effective circuits clearly emerged. In 1980, Richard Newton stirred our interest by pointing out new heuristic algorithms for two-level logic minimization and the potential for improving upon existing approaches. In the summer of 1981, the authors organized and participated in a seminar on logic manipulation at IBM Research. One of the goals of the seminar was to study the literature on logic minimization and to look at heuristic algorithms from a fundamental and comparative point of view. The fruits of this investigation were surprisingly abundant: it was apparent from an initial implementation of recursive logic minimiza­ tion (ESPRESSO-I) that, if we merged our new results into a two-level minimization program, an important step forward in automatic logic synthesis could result. ESPRESSO-II was born and an APL implemen­ tation was created in the summer of 1982. The results of preliminary tests on a fairly large set of industrial examples were good enough to justify the publication of our algorithms. It is hoped that the strength and speed of our minimizer warrant its Italian name, which denotes both express delivery and a specially-brewed black coffee.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Very Large Scale Integration (VLSI) plays a major role in the development of complex electronic systems. As a result of the continued progress in semiconductor technology, an increasing number of devices can be put on a single micro-electronic chip. Newly developed design methods for VLSI must be able to cope with this increased design complexity [MEA 80]. Many such methods are required for the final implementation of a chip. This book addresses one area, that of logic minimization, and provides a new set of optimization algorithms which can cope with the increased complexity of VLSI designs.
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Chapter 2. Basic Definitions

Abstract
In this section we provide a framework of concise definitions for use in the entire sequel. The definitions will be informal, with the object being defined appearing in bold type.
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Chapter 3. Decomposition and Unate Functions

Abstract
Except for the procedure EXPAND, all our algorithms are based on a single fundamental strategy: a recursive divide and conquer. Examples of the use of this strategy applied to logic function manipulation can be found in papers by Morreale [MOR 70] and by Hong and Ostapko [HON 72]. The decomposition is based on the Shannon expansion [SHA 48]. The Shannon expansion makes use of the cofactor of a logic function. Since we are dealing primarily with matrix representations and covers, we will give the definition of cofactor for representations.
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Chapter 4. The Espresso-II Minimization Loop and Algorithms

Abstract
ESPRESSO-II receives as its inputs J and D, cube covers of the on-set and the don’t-care set of an incompletely specified Boolean function ff. Optionally, it can accept input J and Rx, cube covers of the on- and off-sets. It returns as its output a “minimized” cover. As discussed in Chapter 1, the objectives of ESPRESSO-II are to minimize:
  • NPT: the number of product terms in the cover;
  • NLI: the number of literals (non-2’s) in the input parts of the cover;
  • NLO: the number of literals in the output parts.
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Chapter 5. Multiple-Valued Logic Minimization

Abstract
As discussed in Chapter 1, many multiple-valued input logic functions can be implemented very efficiently in PLA’s with two-bit input decoders. Hence multiple-valued logic minimization is of great practical importance [FLE 75]. A two-bit decoder pairs two Boolean variables, say x1 and x2, and generates four decodes
$$ \begin{array}{*{20}{c}} {{{x}_{1}}{{x}_{2}},} \\ {{{{\bar{x}}}_{1}}{{x}_{2}},} \\ {{{x}_{1}}{{{\bar{x}}}_{2}},} \\ {{{{\bar{x}}}_{1}}{{{\bar{x}}}_{2}}.} \\ \end{array} $$
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Chapter 6. Experimental Results

Abstract
In this chapter we discuss our computational experience with an APL implementation of ESPRESSO-II. We report data on 56 PLA’s given to us by various sources. Some have already been minimized by various PLA minimization programs while others consist entirely of minterms. The 56 PLA’s are a mixture of control and data flow logic. Some have don’t-care sets and there is a range in size from 4 inputs to 94 inputs, from 1 output to 109 outputs, and from an initial cover size of 10 terms to 654 terms. The computing time required by ESPRESSO-IIAPL to minimize these PLA’s ranged from less than a second to 721 seconds on an IBM/3081K machine. Most of the PLA’s represent real applications although a few are arithmetic functions which we devised for their interesting structures, or because they were known to be difficult problems.
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Chapter 7. Comparisons and Conclusions

Abstract
In this chapter we recapitulate the main features of ESPRESSO-II and compare it to other minimization algorithms. We compare its strategy with that of MINI, POP and PRESTO, and discuss some modifications introduced in the C-language version of ESPRESSO-II. We then present empirical results obtained by running these programs on the 56 test cases introduced in the preceding chapter. Finally, we discuss other applications of logic minimization and directions for further research.
Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, Alberto L. Sangiovanni-Vincentelli

Backmatter

Weitere Informationen