This paper introduces m-inductiveness over a set of nodes S in sequential circuits. The m-inductive property can be used for equivalence-checking or improved sequential optimization. It allows the behavior of many next state functions (not in S) to be changed while maintaining correctness at the primary outputs of a circuit. As such, it creates flexibility that can be used for sequential optimization. It is shown that the number of nodes in S is reduced as m, the parameter for the inductiveness, increases. We provide an algorithm for finding a minimal set S, as well as one for using m-inductiveness in optimization. We give examples of such optimized circuits and show that m-inductive-based optimization can result in significant area reduction when applied to industrial designs.

Sequential logic synthesis often leads to substantially easier equivalence checking problems, compared to general-case sequential equivalence checking (SEC). This paper theoretically investigates when SEC can be reduced to a combinational equivalence checking (CEC) problem. It shows how the theory can be applied when sequential transforms are used, such as sequential clock gating, retiming, and redundancy removal. The legitimacy of such transforms is typically justified intuitively, by the designer or software developer believing that the two circuits reach the same state after a finite number of cycles, and no difference is observed at the outputs due to fanin non-controllability and fanout non-observability effects.

Proposes a linear-time algorithm for post-placement scan chain optimization that works efficiently on large designs and that allows user-specified tradeoffs between runtime and solution quality. This algorithm is also efficiently applied on scan chain partitioning. Presents repartitioning algorithm that takes advantage of the linear-time scan chain optimization algorithm presented in the first part. The idea is simply to connect all the scan flipflops of all the scan chains together in a new chain. Then the algorithm optimizes this new chain and splits it in individual chains of the size of the initial chains. Later it assigns individual chains to their closest scan primary input/output pair.

We present LEOPARD, a fanout optimization algorithm based on the effort delay model for near-continuous size buffer libraries. Our algorithm minimizes area under required timing and input capacitance constraints by finding the tree topology and assigning different gains to each buffer to minimize the total buffer area. Experimental results show that the new algorithm achieves significant buffer area improvement compared to previous approaches.

A description is given of SIS, an interactive tool for synthesis and optimization of sequential circuits. Given a state transition table or a logic-level description of a sequential circuit, SIS produces an optimized net-list in the target technology while preserving the sequential input-output behavior. Many different programs and algorithms have been integrated into SIS, allowing the user to choose among a variety of techniques at each stage of the process. It is built on top of MISII and includes all (combinational) optimization techniques therein as well as many enhancements. SIS serves as both a framework within which various algorithms can be tested and compared and as a tool for automatic synthesis and optimization of sequential circuits.>

The observability relation O(x,z) or the Boolean relation provides a description of all the flexibility one has in implementing a Boolean network N. The authors represent and use this flexibility in a logic synthesis system by adding a single output node to the Boolean network N. The node function for the new node is O(x,z). The newly constructed network N' (called the observability network) has only one output and computes 1 for every input x. It is shown that the observability don't cares (ODCs) for a node y/sub i/ in N' provide the maximum flexibility for implementing y/sub i/ and subsume the flexibility obtained for y/sub i/ in N even with don't cares provided at each output. This gives rise to new methods for computing complete ODCs for N' and hence for N.>

An algorithm for computing local don't cares (in terms of immediate fanin variables) at each intermediate node of a Boolean network is presented. These don't cares can be directly used for the simplification of each node by a two-level minimizer. The simplification is relatively fast and the optimized circuits are 100% testable in most cases. The method is more powerful than previous ones developed for node simplification because it computes almost the full local don't care set at each node using image computation techniques. External don't cares are used effectively and there is no restriction on how these are represented because BDDs (binary decision diagrams) are used to translate them into local don't cares. This algorithm has been implemented in the sequential interactive logic synthesis system (SIS), and experimental results are presented that show the effectiveness of the proposed algorithm on benchmark circuits with and without external don't cares.>

The authors propose a novel technology-independent algorithm to minimize circuit delay. The algorithm works in two steps. The first step performs a partial collapse of the circuit based on a delay-driven clustering. The second step factorizes and simplifies the circuit without increasing the number of levels of logic. The computational cost of the algorithm is dominated by the simplification step. To estimate circuit delay, a state-of-the-art technology mapper is used, incorporating fanout optimization and tree covering for delay minimization. On average over a representative set of benchmarks, a delay reduction of 18% is obtained for an area increase of 11%.>

We give an algorithm for computing subsets of observability don't cares at the nodes of a multi-level Boolean network. These subsets are based on an extension of the methods introduced in [4] for computing compatible sets of permissible functions (CSPF's) at the nodes of networks composed of NOR gates. The extensions presented are in four directions; an arbitrary logic function is allowed at any node, the don't cares are expressed in terms of both primary inputs and intermediate variables, a new ordering scheme is used, and maximal CSPF's are computed. These ideas are incorporated in an algorithm designed to take full advantage of the power of two-level minimization in multi-level logic synthesis systems. This has been implemented in MIS-II and we present results that demonstrate the effectiveness of these techniques.

The authors propose a novel method based on transition relations that only requires the ability to compute the BDD (binary decision diagram) for f/sub i/ and outperforms O. Coudert's (1990) algorithm for most examples. The method offers a simple notational framework to express the basic operations used in BDD-based state enumeration algorithms in a unified way and a set of techniques that can speed up range computation dramatically, including a variable ordering heuristic and a method based on transition relations.>

SLIP (system-level interactive partitioning), a framework for algorithms that partition and implement complex VLSI-based systems as a hierarchy of electronic packages, is described. SLIP provides a policy for representing hierarchical systems on the OCT data model as well as an attribute mechanism which is used to annotate the representation and to build models of the system. Modifications to the hierarchy are made with routines which maintain the consistency of both the data representation and the attributes.>

Two methods for two-level logic minimization tuned to a multilevel network environment are discussed. Each produces results superior to ESPRESSO. The tautology-based method is very simple and can be coded in less than 700 lines of C language using the existing data structures, and some routines in ESPRESSO. The reduced offset modification is somewhat more complicated but gives the best results. This algorithm has been incorporated into MISII. The authors have demonstrated that a simple filter applied to the don't care set in this application can be extremely effective.>