Logic synthesis systems are c omplex systems and algorithmic research in synthesis has become highly specialized.This creates a gap where it is often not clear how an advance i n a p articular algorithm translates into a better synthesis system.This tutorial starts by describing a set of constraints which synthesis algorithms must satisfy to be useful.A small set of established t e chniques are r eviewed r elative to these criteria to understand their applicability and the potential for further research in these areas.

Retiming has been proposed as an optimization step for sequential circuits represented at the net-list level.Retiming moves the latches across the logic gates and in doing so changes the number of latches and the longest path delay between the latches.In this paper we show by example that retiming a design may lead to differing simulation results when the retimed design replaces the original design.We also show, by example, that retiming may not preserve the testability of a sequential test sequence for a given stuck-at fault as measured by a simulator.We identify the cause of the problem as forward retiming moves across multiple-fanout points in the circuit.The primary contribution of this paper is to show that, while an accurate logic simulation may distinguish the retimed circuit from the original circuit, a conservative three-valued simulator cannot do so.Hence, retiming is a safe operation when used in a design methodology based on conservative three-valued simulation starting each latch with the unknown value.

Efficient manipulation of Boolean functions is an important component of many computer-aided design tasks. This paper describes a package for manipulating Boolean functions based on the reduced, ordered, binary decision diagram (ROBDD) representation. The package is based on an efficient implementation of the if-then-else (ITE) operator. A hash table is used to maintain a strong canonical form in the ROBDD, and memory use is improved by merging the hash table and the ROBDD into a hybrid data structure. A memory function for the recursive ITE algorithm is implemented using a hash-based cache to decrease memory use. Memory function efficiency is improved by using rules that detect when equivalent functions are computed. The usefulness of the package is enhanced by an automatic and low-cost scheme for recycling memory. Experimental results are given to demonstrate why various implementation trade-offs were made. These results indicate that the package described here is significantly faster and more memory-efficient than other ROBDD implementations described in the literature.

An approach is described for the minimization of multilevel logic circuits. A multilevel representation of a block of combinational logic is defined, called a Boolean network. A procedure is then proposed, called ESPRESSOMLD, to transform a given Boolean network into a prime, irredundant, and R-minimal form. This procedure rests on the extension of the notions of primality and irredundancy, previously used only for two-level logic minimization, to combinational multilevel logic circuits. The authors introduce the concept of R-minimality, which implies minimality with respect to cube reshaping, and demonstrate the crucial role played by this concept in multilevel minimization. Theorems are given that prove the correctness of the proposed procedure. Finally, it is shown that prime and irredundant multilevel logic circuits are 100% testable for input and output single-stuck faults, and that these tests are provided as a byproduct of the minimization.>

MIS is both an interactive and a batch-oriented multilevel logic synthesis and minimization system. MIS starts from the combinational logic extracted, typically, from a high-level description of a macrocell. It produces a multilevel set of optimized logic equations preserving the input-output behavior. The system includes both fast and slower (but more optimal) versions of algorithms for minimizing the area, and global timing optimization algorithms to meet system-level timing constraints. This paper provides an overview of the system and a description of the algorithms used. Included are some examples illustrating an input language used for specifying logic and don't-cares. Parts on an industrial chip have been re-synthesized using MIS with favorable results as compared to equivalent manual designs.

This paper describes both a heuristic algorithm, Espresso-MV, and an exact algorithm, Espresso-EXACT, for minimization of multiple-valued input, binary-valued output logic functions. Minimization of these functions is an important step in the optimization of programmable logic arrays (PLA's). In particular, the problems of two-level multiple-output minimization, minimization of PLA's with input decoders and solutions to the input encoding problem rely on efficient solutions to the multiple-valued minimization problem. Results are presented for a large class of PLA's taken from actual chip designs. These results show that the heuristic algorithm Espresso-MV comes very close to producing optimum solutions for most of the examples. Also, results from a chip design in progress at Berkeley show how important multiple-valued minimization can be for PLA optimization.