Production VLSI circuits typically consist of primitives like tristate buffers, bidirectional buffers, and bus configurations that assume non-Boolean values like the high-impedance state. We describe a systematic methodology for extending test generation algorithms that work on combinational circuits with only Boolean primitives to full-scan production circuits. Key features of the methodology are illustrated using the energy minimization based test generation algorithm for combinational circuits. The main features of our methodology that make the test generation algorithm practical for large production circuits are: (1) only one Boolean variable is used to represent the value on a signal and all signals assume only Boolean values during the test generation procedure; (2) the function of non-Boolean primitives is separated into Boolean and non-Boolean components with energy functions required only for the Boolean component; and (3) non-Boolean components are implicitly considered in the energy minimization procedure. In this process, no new energy functions other than the normal Boolean gate energy functions are needed. We give a method for identifying and removing redundancies in production circuits using energy minimization. The formulation is also applicable to Boolean satisfactorily and BDD methods. We first use the test generation algorithm for identifying undetectable faults and then relax specific constraints in the original test generation problem by ignoring the non-Boolean components. We show that undetectability in the relaxed formulation implies redundancy. We report redundancy removal results for production VLSI circuits, ISCAS 85, and full-scan versions of the ISCAS 89 benchmark circuits.

Production VLSI circuits typically consist of primitives like tri-state buffers, bidirectional buffers and bus configurations that assume non-Boolean values like the high-impedance state. The present work describes a systematic methodology for extending test generation algorithms to full-scan production circuits. Key features of the methodology are illustrated using the energy minimization based test generation algorithm for combinational circuits. The main features of our methodology that make the test generation algorithm practical for large production circuits are: (1) only one Boolean variable is used to represent the value on a signal and all signals assume only Boolean values during the test generation procedure, (2) function of non-Boolean primitives is separated into Boolean and non-Boolean components, and energy functions are derived only for the Boolean component, and (3) non-Boolean components are implicitly considered in the energy minimization procedure. In this process, no new energy functions other than the normal Boolean gate energy functions are needed. Further, in this paper, we report the first known method of identifying and removing redundancies in production circuits using formulations based on energy minimization, satisfiability or BDD-based methods. We first use the test generation algorithm for identifying undetectable faults and then relax specific constraints in the original test generation problem by ignoring the non-Boolean components. We show that undetectability in the relaxed formulation implies redundancy. Redundancy removal results on several production VLSI circuits, ISCAS 85 and full-scan versions of the ISCAS 89 benchmark circuits are reported.

ABSTRACT: We propose a novel sequential delay op-timization technique based on network flow methods that simultaneously exploits delays on all paths in the circuit. We view the sequential circuit as an intercon-nection of path segments with pre-specified delays. Path segments are bounded by flip-flops, primary inputs or primary outputs. Recognizing that a delay optimizer can satisfy certain delay constraints more easily than others, we first propose a measure of difficulty for the delay optimizer. Our measure is based on explicit path delays to be satisfied by the delay optimizer. Also, our measure induces a partial order on the set of possible delay constraints. We then compute a set of delay con-straints that is optimal with respect to our measure. The delay constraint set is optimal in the sense that it is the easiest constraint that can be specified to the delay optimizer. We formulate the delay constraint cal-culation problem as a minimum cost network flow prob-lem. If the delay optimizer satisfies the optimal delay constraint set, then the resynthesized circuit may have several pat hs exceeding the desired clock period. How-ever, we show that the resynthesized circuit can always be retimed to achieve the desired clock period. Exper-imental results on MCNC synthesis benchmarks show that our method improves the performance of circuits beyond what is achievable using optimal retiming and conventional combinational logic synthesis. 1.

A transitive-closure-based test generation algorithm is presented. A test is obtained by determining signal values that satisfy a Boolean equation derived from the neural network model of the circuit incorporating necessary conditions for fault activation and path sensitization. The algorithm is a sequence of two main steps that are repeatedly executed: transitive closure computation and decision-making. A key feature of the algorithm is that dependences derived from the transitive closure are used to reduce ternary relations to binary relations that in turn dynamically update the transitive closure. The signals are either determined from the transitive closure or are enumerated until the Boolean equation is satisfied. Experimental results on the ISCAS 1985 and the combinational parts of ISCAS 1989 benchmark circuits are presented to demonstrate efficient test generation and redundancy identification. Results on four state-of-the-art production VLSI circuits are also presented.>

A method to improve the effectiveness of retiming by transforming the sequential circuit is proposed. Bottlenecks which prevent retiming to achieve a desired clock period are identified. Conditions to eliminate the retiming bottlenecks are derived. These conditions are satisfied by a process of identifying subcircuits and satisfying a set of timing constraints on the subcircuits. The transformed circuit, which satisfies the timing constraints, can be retimed to achieve the desired clock period. If the original circuit has its initial state specified, the method always generates the final circuit with an equivalent initial state. Experimental results on a variety of sequential benchmark circuits demonstrate significant performance improvement.>

Mind, a module binder for the Bridge synthesis system, is described. The practical considerations for generating production-quality designs are emphasized. These considerations include the separation of single-function and multiple-function ALU (arithmetic and logic unit) generators, the extraction of constant and feedthrough control signals, as well as the incorporation of a net-list post processor to eliminate constant inputs, floating outputs, and feedthrough wires. Experimental data indicate that the application of these optimization techniques results in significant area reduction.>