We propose a new complementary metal-oxide semiconductor (CMOS) gate design that has different delays along various input to output paths within the gate. The delays are accomplished by inserting selectively sized ldquopermanently onrdquo series transistors at the inputs of a logic gate. We demonstrate the use of the variable input delay CMOS gates for a totally glitch-free minimum dynamic power implementations of digital circuits. Applying a linear programming method to the c7552 benchmark circuit and using the gates described in this paper, we obtained a power saving of 58% over an unoptimized design. This power consumption was 18% lower than that for an alternative low power design using conventional CMOS gates. The optimized circuits had the same critical path delays as their original unoptimized versions. Since the overall delay was not allowed to increase, the glitch elimination with conventional gates required insertion of delay buffers on noncritical paths. The use of the variable input delay gates drastically reduced the required number of delay buffers.

This paper presents a new fault node for implication graph that represents the Boolean detectability status of a fault in the circuit. An implication graph with fault nodes is termed functional fault graph (FFG) because such a graph stores both the functional information and the fault information of the circuit. By computing the transitive closure and graph condensation of the FFG of a circuit, we show that we can collapse faults, and identify untestable faults and independent fault pairs in the circuit. Compared to prior fault independent-based approaches for fault collapsing, our technique gives the best result by reducing the fault-set size by 66%. Additional advantages of our technique compared to previous techniques are: a) It can also identify independent fault pairs in the circuit, and b) It can be extended for other fault models and has a variety of applications. Our experiment with c7552 also found more than 268 K independent fault pairs. This work also introduces the first fault-independent polynomial-time approach for identifying untestable transition delay faults.

Dynamic power cutoff technique (DPCT) (Baozhen Yu and Bushnell, 2006) is a novel active leakage power reduction technique. It works by partitioning the circuit into different groups based on the minimal switching window of each gate and turning on the power of each group only during a small timing window within each clock cycle, which results in significant active leakage power savings. But this high frequency on-off operation on the power connections may cause power grid integrity issues. In this paper, the authors analyze DPCT's effect on the power grid. Experimental results on ISCAS '85 circuits using 70 nm Berkeley predictive models (Cao et al., 2000) show that DPCT reduces the maximal voltage drop on the power grid by up to 49%. However, it also introduces some high frequency harmonic noise. Extra decoupling capacitors can be added to reduce this high frequency noise to the required level.

We propose a new partial-scan algorithm, the first to use toggling rates of the flip-flops (analyzed using DSP methods) and Shannon entropy measures of flip-flops to select flip-flops for scan. This improves the testability of the circuit-under-test (CUT). Entropy is maximized throughout the circuit to maximize the information flow (the principle of maximum entropy), which improves testability. We propose using partial-scan for testing, to maximize fault coverage (FC), reduce test volume (TV), reduce test application time (TAT), and reduce test power (TP) but we allow for full-scan during silicon debug. Full-scan is commonly used for testing, to reduce sequential automatic test-pattern generation (ATPG) to the complexity of combinational ATPG, but comes with serious TV, TAT, and TP overheads. Partial-scan significantly reduces circuit delay, when compared to full-scan, because critical flip-flops in the circuit data path do not have the extra hardware for full-scan, and therefore are roughly 5% faster, and use 10% less area. This is particularly critical for microprocessors. The HITEC ATPG program generated results for this new partial-scan algorithm.

We propose a new IDDQtesting signature, the graphical IDDQsignature. We discovered that noise, in the entire set of current measurements for a chip, is a vastly superior feature for classifying chips as good or bad, compared to present methods. The measured IDDQcurrent as a function of vectors is defined here as the signature. We examine the shape of the waveform defined by the total set of the IDDQmeasurements, to extract the number of bands that all of the current measurements cluster into, the width and separation of the bands and current glitches or noise among all IDDQmeasurements. We examined the IDDQsignatures of all SEMATECH experiment chips that were classified as good or bad by a combination of functional, delay, and scan voltage tests. A single IDDQthreshold, whether absolute or differential, cannot separate good/bad chips reliably. Good chip signatures contain discrete levels (or bands) of varying widths and separations. A faulty chip almost always displays noise and glitches in the band structure. The graphical IDDQclassifier shows very high accuracy for SEMATECH test data with a test escape rate of 5.97%, compared with 7.5% for the single threshold method, 7.6% for current differences and 7.5% for the DeltaIDDQmethod. The graphical IDDQmethod had a 1.2% test overkill, compared with 2.3% for the single threshold method, 6.1% for current differences and 7.0% for DeltaIDDQ.

Since structured application specific integrated chip (ASIC) products require very short turn around time, long automatic test pattern generation (ATPG) run time is undesirable. Large structured ASICs often require a large number of test patterns to achieve the desired fault coverage. This paper presents the first test point insertion technique for structured ASICs that can reduce test set sizes and ATPG run time. Only unused flip-flops in the structured ASIC design are used to implement test points, so the proposed technique does not incur any hardware overhead. Since test points are inserted during a post-layout step, considering both timing and layout information, hence test points can be inserted without changing the existing layout or routing. Novel gain functions are defined that specifically quantify the reduction in test volume and test time to select the best signal lines for inserting test points. The gain function described in this paper is also applicable to regular cell based ASICs. The proposed test point insertion technique can be used in conjunction with any compression technique (Jas et al., 2003) to further reduce the test volume. Experimental results clearly demonstrate the effectiveness and scalability of the proposed technique. Using less than 1% of extra flip-flops and very little run time for test point insertion, test generation time was reduced by up 42.9% and test data volume by up to 25.9% while also achieving a near 100% fault efficiency for very large industrial (400K-5M signal lines) designs

Due to the exponential increase in subthreshold leakage and gate leakage with technology scaling, leakage power is becoming a major fraction of total VLSI chip power in active mode. We present a novel active leakage power reduction technique, called the dynamic power cutoff technique (DPCT). First, the switching window for each gate, during which a gate makes its transitions, is identified by static timing analysis. Then, the circuit is optimally partitioned into different groups based on the minimal switching window (MSW) of each gate. Finally, power cutoff transistors are inserted into each group to control the power connections of that group. Each group is turned on only long enough for a wavefront of changing signals to propagate through that group. Since each gate is only turned on during a small timing window within each clock cycle, this significantly reduces active leakage power. This technique can also save standby leakage and dynamic power. Results on ISCAS '85 benchmark circuits modeled using 70 nm Berkeley Predictive Models [1] show up to 90% active leakage, 99% standby leakage, 54% dynamic power, and 72% total power savings.

Spectral generation of patterns, to excite the natural frequencies of a digital circuit, is highly effective in testing sequential circuits. We have created a hardware embodiment of the spectral test-pattern generator for built-in self-test (BIST). We present five new spectral response compactors SRC1-5 for BIST. Each analyzes the spectral content of circuit output responses, and accumulates their spectrum in one or more counters. The method has astonishing results. SRC1 never aliased for any faults in the ISC AS '89 benchmarks. SRC2, a low-overhead version of SRC1, aliased slightly more than the multiple-input signature register (MISR), but used less hardware than the MISR. This new spectral BIST system has a 91.26% shorter test sequence than for a conventional LFSR pattern generator and MISR system, with at least 8.42% higher fault coverage. The benefits of this are drastically shorter test sequences, the elimination of scan-shifting sequences, much lower test power dissipation, and higher fault coverage.

A selfish gene (SG) algorithm differs from the genetic algorithm (GA) because it evolves genes (characteristics) that provide higher fitness rather than evolving individuals with higher fitness. We enhance the spectral method of sequential circuit test generation by using a SG algorithm. The objects of evolution are the Hadamard spectral matrix, non-linear digital signal processing (DSP) filtering cutoff values, vector holding time, and relative input phase shifts, which are all modeled as genes. These characteristics, extracted from compacted test vectors, are used to create new vector sequences to be further compacted with higher fault coverage. Alternatively, new vectors were generated by holding randomly selected vectors and then randomly perturbing some bits in 8-bit chunks of bit streams. Both the SG algorithm and holding with bit-perturbation can outperform the previously-published spectral method in either fault coverage, or shorter vector length, or both. The SG algorithm is often superior to random bit-perturbation but it requires more CPU time.

Proposes a new analog coupling delay fault model and analog macromodeling technique to generate tests for these faults. To our knowledge, this is the first time that analog macromodeling, along with multiple-delay sequential digital fault simulation, using differing rise and fall times for digital logic gates, effectively detected coupling timing faults. We propose a new crosstalk candidate reduction (CCR) algorithm, which looks at the entire set of possible signal line couplings and eliminates impossible and uninteresting couplings from the final list. On various circuits, CCR reduced the coupling candidates by 98.1%, on average. The analog macromodels eliminate errors and uncertainty about whether signals actually couple, and also avoid complete analog simulation during fault simulation, as all analog macromodels are precomputed. The analog macromodel is independent of the circuit-under-test, because it models generalized interconnect. The method efficiently handles large circuits with more than 10,000 coupling faults, while obtaining coupling fault coverages in the range of 4 to 10% on sequential circuits, and up to 33% on combinational circuits. These are the first coupling fault results for sequential circuits.

A differential algorithm for concurrent simulation of path delay faults in sequential circuits is presented. The simulator analyzes all three conditions, namely, initialization, signal transition propagation through the path, and fault effect observation at a primary output for vector pairs and considers the hazard states occurring between vectors. The main contribution is in methods of propagating signals between time frames. An optimistic method assumes that all nondestination flip-flops are not affected by delays. The pessimistic method converts all nondestination flip-flops with nonsteady values to the unknown state before these values are propagated beyond the time frame in which a path is activated. A 13-valued algebra is shown to improve the efficiency of fault simulation.

We analyze the causes of low path delay fault coverage in synchronous sequential circuits and propose a method to improve testability. The three main reasons for low path delay fault coverage are found to be: (A) combinationally false (nonactivatable) paths; (B) sequentially nonactivatable paths; and (C) unobservable fault effects. Accordingly, we classify undetected faults in Groups A, B, and C. Combinationally false paths ran be made testable by modifying the circuit or resynthesizing the combinational logic as discussed by other researchers. A majority of the untestable faults are, however found in Group B, where a signal transition cannot be functionally propagated through a combinational path. A test requires two successive states necessary to create a signal transition and propagate it through the target path embedded in the sequential circuit. We study a partial scan technique in which flip-flops are scanned to break cycles and shun that a substantial increase in the coverage of path delay faults is possible.

VLSI Designers know so little about testing that the large, multi-national corporations frequently higher test experts to advise their designers on test problems. The companies even pay a higher salary to the testing experts than to their VLSI Designers. The author's position is that three lectures in every VLSI Design course should be devoted to test. The first lecture would touch briefly on Test Economics, in order to motivate the students to take an interest in testing problems and costs. This lecture would also include introductory Fault Modeling for stuck-faults, delay-faults (transition and path), bridging faults, MOS Transistor Faults, and IDDQ Faults. Industry uses all of these faults in production testing. The second lecture would cover Fault Simulation, as well as Combinational and Sequential automatic test-pattern generation (ATPG) and the reason for redundancy removal (to avoid masking of testable faults). The focus of this lecture should not be on the various algorithms, but rather on the test generation and fault simulation process. This will train the students in redundancy removal techniques, and teach them how to facilitate test generation by removing testability problems from their designs. The final lecture should be on design for testability (DFT). This would cover Full and Partial Scan, as well as the JTAG 1149 Boundary Scan Standard. Scan is included because a very high percentage of designs will employ some form of scan. In addition, built-in self-testing (BIST) should be introduced in this lecture, but details would be omitted. BIST is important, because industry and leading academics project that BIST may appear in 90% of the chips in 11 years. If additional time is available, I would suggest a fourth lecture on Testability Measures, and how they can be used by the designer, to eliminate test generation problems, predict fault coverages, and accelerate ATPG programs.

Some false paths are caused by redundant stuck-at faults. Removal of those stuck-at faults automatically eliminates such false paths from the circuit. However, there are other false paths that are not associated with any redundant stuck-at fault. All links of such a false path are shared with other testable paths. We focus on the elimination of this type of false paths. We use a nonenumerative path delay fault simulator, which duplicates selected gates to separate the detected and undetected path delay faults. The expanded circuit may contain new redundant stuck-at faults, corresponding to those undetected paths that are false. This happens because in the expanded circuit some new links have only false paths passing through them. Such links become the sites for redundant stuck-at faults. Removal of these redundant faults eliminates false paths. The quality of the result may depend on the coverage of testable paths by the vectors that are simulated. Since a non-enumerative path delay simulation and an implication-based redundancy removal technique are used, the present procedure of false-path elimination can be applied to very large circuits.

We extend the path status graph (PSG) method of delay fault simulation to sequential circuits. By devising a layered PSG and restricting the number of time-frames over which a fault must be detected, we preserve the non-enumerative nature of the simulation algorithm. The program is capable of simulating a wide variety of circuits (synchronous, asynchronous, multiple-clock and tri-state logic.) Both rated and variable clock modes, as well as robust, non-robust or functional sensitization detection options, are available. The simulation can be stopped and restarted through a check pointing facility. The program can target any given list of paths. This path list can also be generated by the program based on user-selectable criteria (all paths, longest paths, paths between certain I/O pairs, etc.) User reports include a histogram of path coverage versus path length. Detected and undetected path data remain implicit in the PSG and can be retrieved through post-processing commands. Due to its non-enumerative stature, the program can process most production level digital logic circuits.

The effect of test environment noise (tester noise) on test waveforms is considered. Methods such as retrofitting of analog test equipment or performing multiple fast Fourier transforms (FFTs) on measured waveforms for repeatability and noise suppression are costly. We propose a simulation environment in which the tester noise characteristics along with wide-band measurement can be used to grade environment test waveforms and recommend noise-robust test waveforms. We use time averaged second order statistics such as the power spectrum density (PSD) and root mean square (RMS) values to characterize any noise considered. We then determine circuit primary output (PO) noise characteristics and use them to make decisions about the test waveforms and recommend more noise-robust tests. Results of experiments on an instrumentation amplifier, biquadratic filter and a Gilbert multiplier are presented.

We explore non-robust untestability of paths based on redundant stuck-at faults. Such untestability classification is necessary for a path to be ignored in timing verification and delay testing. A recent result states that redundant stuck-at-0 (s-a-0) and stuck-at-1 (s-a-1) faults of a line imply untestability of rising and falling delay faults, respectively, for all paths through that line. We find that this result only establishes robust untestability of paths. Starting with known examples, where a non-robust test can exist for some paths that pass through the site of a redundant stuck-at fault, we examine various classes of stuck-at fault redundancies. We prove that: (1) an unexcitable or undrivable redundant s-a-0 (s-a-1) fault will make all paths through the fault site non-robustly delay-untestable for rising (falling) transition, and (2) an unobservable fault site (causing both s-a-0 and s-a-1 faults to be redundant) can only classify the passing paths as robustly delay-untestable, Finally, we show that two singly-untestable paths, passing through the sites of separate redundant single stuck-at faults, may form a multiply-testable pair of paths provided the two redundant single stuck-at faults have a multi-fault test.

We propose a novel hardware model to reconfigure a sequential ULSI circuit for partial-scanned delay-fault built-in self-test (BIST). We modify the standard stuck-fault BIST model to ensure highly robust delay tests by inserting hardware to avoid circuit hazards that invalidate delay tests. The model treats un-scanned flip-flops and latches as inverters or buffers. We propose a novel minimum feedback vertex set (FVS) algorithm based on quadratic 0-1 programming (which has O(n/sup 2/) complexity) for partial-scan flip-flop selection. We obtain a pipelined sequential circuit and insert parity-flippers to remove hazards during testing. We avoid placing hardware on time-critical paths. We find the FVS and insert deglitching hardware for all of the 1989 ISCAS circuits.

We present an efficient path-delay fault (PDF) simulator that does not involve the enumeration of paths. Our method calculates the exact fault coverage, and identifies all tested faults in any circuit with a large number of paths. We present a new data structure, called the path-status graph (PSG), to efficiently hold the status of each PDF in the circuit, i.e., whether or not the PDF is tested. The keg to this efficiency is in breaking the information into pieces and distributing it over the data structure, and in retaining all or part of the reconverging fan-out structure of the circuit in the PSG. Thus, an exponential number of PDF's can share the same piece of information. Using 1000 random tests, we simulated all of the approximately 10/sup 20/ PDF's in the circuit c6288, and determined that 4.4 billion faults were detected. This number is larger by over three orders of magnitude compared to what was possible with previously reported methods.

A new simulation-based method uses single-input change (SIC) vectors to derive tests efficiently for singly testable (ST) path-delay faults (PDFs). A PDF is ST if there exists a delay test that guarantees its detection when it is the only PDF in the circuit. It is known that an ST PDF must have a single-input change test. We utilize this result and present a fault simulator that is specifically tuned to simulate single-input change vectors efficiently. We assign random values to all inputs, and then propagate rising and falling transitions from each input while all other inputs are held steady. We present a 16-valued algebra with which rising and falling PDF's from all inputs are concurrently simulated. Using a suitable encoding for signal values, gates are evaluated directly through Boolean operations, and all computation stages use machine word parallelism. Results on the ISCAS'85 and '89 benchmarks show that the approach is superior to another published method in terms of both fault coverage and execution time.

We propose a delay test methodology for general sequential circuits. To test a combinational path between two flip-flops, the source flip-flop is initialized to the appropriate value, followed by creation of a transition, which is propagated through the path. An incorrect logic value is captured in the destination flip-flop if the path delay exceeds the clock period. The state of the destination flip-flop is observed at a primary output through path sensitization. Only one vector that propagates the transition through the path is applied with the rated clock period. All other vectors use a slow speed clock to ensure fault-free initialization and fault effect observation. The test generation method uses a 13-value algebra that represents the relevant transition and hazard states of signals. Since several path delay faults can be activated by the vector applied at the rated clock, only the flip-flops with hazard-free steady values are assumed to have deterministic states. This allows us to generate sequentially robust tests. We present the results of the test generation method on ISCAS benchmark circuits.

A recently proposed method obtains path delay fault coverages by estimating the count of the number of tested faults instead of actually enumerating them. The estimate becomes pessimistic when several paths share a set of lines. In this communication, we present a continuum of improved approximations for the counting method, approaching exact fault simulation, to allow tradeoffs between accuracy and complexity. Higher accuracy is obtained at the expense of CPU time. We propose the use of flags corresponding to fixed-length path segments. A flag indicates whether or not the segment has been included in a previously detected path fault. A path fault, detected by a pair of vectors, is counted as a new detection only if it includes at least one segment not included in any previously tested path fault. The results show that as the length of segments is increased, the accuracy becomes close to that of the exact fault simulation, even with small segment lengths.

We analyze all signals of a combinational circuit simultaneously for redundancy. The state of a signal is represented by two binary variables. The first variable is the logic value of the signal. The second variable is the observability status of the signal with respect to all primary outputs. Boolean equations specify local relationships of these variables in a manner similar to the neural network or Boolean satisfiability method. All pairwise terms appearing in these Boolean equations are used to construct an implication graph, for which the transitive closure graph is obtained. Any signal assignments or relations found from the transitive closure are substituted into higher-order terms of the Boolean equations, some of which reduce to pairwise terms. Such cases are iteratively included in the transitive closure until no more reductions are possible. In the final transitive closure, all signals are examined for the following conditions of redundancy: (1) If a signal and its complement imply each other (contradiction) then both stuck-at faults on that signal are redundant; (2) If one value implies the other value (fixation) then one of the stuck-at faults on that signal is redundant; (3) If the true observability status of a signal implies its own false observability status, then both stuck-at faults of that signal are redundant; (4) If a certain value of a signal implies the false observability status, then the corresponding stuck-at fault is redundant. We give ISCAS '85 benchmark results. For c6288, we could identify 31 out of 33 redundancies. The percentage of identified redundancies was not always that high, but the algorithm has polynomial complexity and we discuss its limitations.

The present an efficient path-delay fault (PDF) simulator that does not involve enumeration of paths. Our method calculates the exact fault coverage, and identifies all tested faults in any circuit with a large number of paths. We present a new data structure, called the Path-Status Graph (PSG), to efficiently hold the status of each PDP in the circuit, i.e., whether or not the PDF is tested. The key to this efficiency is in breaking the information into pieces and distributing it over the data structure and in retaining all or part of the reconverging fanout structure of the circuit in the PSG. Thus, an exponential number of PDFs can share the same piece of information. Using one thousand random tests, we simulated all of the approximately 10/sup 20/ PDFs in the circuit c6288 and determined that 4.4 billion faults were detected. This number is larger by over three orders of magnitude compared to what was possible with previously reported methods.

We present a novel test generation technique for path delay faults, based on the growth (G) and disappearance (D) faults of programmable logic arrays (PLA). The circuit is modeled as a PLA that is prime and irredundant with respect to every output. Certain tests for G faults, generated by using known efficient methods are transformed into tests for path delay faults. Our algorithm generates tests for all robustly detectable path delay faults in the two-level circuit and its multilevel implementation synthesized using algebraic transformations. Experimental results confirm that the generated vectors, beside robustly covering all path delay faults, also cover most stuck faults in the algebraically factored multilevel circuit. We present some of the best known timings and robust path delay fault coverages for the scan/hold versions of several ISCAS89 circuits, for which the PLA description could be obtained.

In this paper, we classify path-delay faults into three categories: singly-testable (ST), multiply-testable (MT), and singly-testable dependent (ST-dependent). All ST faults are guaranteed detection in the case of a single fault, and some may be guaranteed detection through robust and validatable non-robust tests even in the case of multiple faults. An ST-dependent fault can affect the circuit speed only if certain ST faults are present. Thus, if the ST faults are tested, the ST-dependent faults need not be tested. MT faults cannot be guaranteed detection, but affect the speed only if delay faults simultaneously exist on a set of paths none of which is ST. We classify all path-delay faults into the three categories by a procedure using any unaltered single stuck fault test generation tool. We use only two runs of this tool on a network derived from the original network. As a by-product of this process, we generate single and multiple input change delay tests for all testable faults. With these tests, we expect that most defective circuits are identified. Examples and results on ISCAS'89 benchmarks are presented.

We propose a quadratic 0-1 approach to redesign a circuit in order to test it for excessive delays using a new robust delay-fault Built-In Self Testing (BIST) model. This approach models the problem as a weighted signed graph balancing problem. The algorithm has O(n/sup 2/) complexity, where n is the number of circuit nodes. We drop hardware from false timing paths to lower the delay fault BIST hardware overhead to 17% in large circuits (measured overhead in addition to stuck-fault BIST overhead). Results show that the computation is rapid for the 1985 ISCAS benchmarks.

We have developed a new statistical technique for estimating delay fault coverage in combinational circuits. True value simulation is performed for a sample of vector pairs chosen randomly from the test set. Transition probabilities and observabilities are estimated from the simulation data. These allow us to estimate fault detection probabilities per vector pair. Fault models considered are the transition faults, path delay faults, and the longest path delay faults. We analyze the vector sampling error and find a high-confidence lower bound for the detection probability that is used to compute the fault coverage for the entire vector set. Experimental results show that vector sampling can provide a close approximation to other methods. It requires reduced computing resources compared to other statistical methods. The savings over fault simulation is even greater.>

Abstract|W e propose a linear complexity method to estimate robust path dela y fault coverage in digital circuits.W e adopt a path counting scheme for a true-value simulator that uses ags for each signal line.These ags determine the new path delay faults detected by the simulated vector pair.Experimental results are presented to show the eectiveness of the method in estimating path delay fault coverage.

We derive new neural network models for n and pFET transistors for use in switch-level test generation. Special characteristics included in the model are bidirectionality and an explicit representation of the substrate. We prove the optimality of these models. The results for an example CMOS circuit indicate that modeling circuit portions at the switch-level allows more accurate tests for transistor stuck-open faults without giving up the speed of gate-level ATPG.>

We propose a new statistical technique for estimating fault coverage in combinational circuits. Our method requires fault-free simulation of a random sample of vectors from the test vector set. Fault coverage is computed from controlabilities and observabilities both defined as probabilities and the method is applicable to any fault model like stuck-at-faults or delay faults. Experimental results are presented for path and transition delay faults.>

We experimentally study the reasons for low coverage of path delay faults in several sequential benchmark circuits. Causes for undetected faults are classified into three categories: (A) Combinationally nonactivated paths, (B) Sequentially nonactivated paths, and (C) Unobservable fault effect. The type A faults can only be made detectable by modifying or resynthesizing the combinational logic as has been discussed by others. We find that almost 80% of sequentially untested faults are in category B. Most are not activated because the two successive states necessary to create a transition and to propagate it through the path cannot be produced in the sequential circuit. We study the partial scan technique in which flipflops are scanned to break cycles and show that a substantial increase in the coverage of path delay faults is possible.

We present new extensions to the EST' algoritlm, which accelerates combinational circuit Redundancy Identification and Automatic Test Pattern Generation (ATPG) algorithms, in particular SOCRATES. EST detects equivalent search states, which are saved. for all faults during ATPG. The search space is reduced by using learned Search State equiualences to detect previously-encountered search states (possibly from prior faults) and to make internal node assignments. We present two extensions to EST. The first ensures that each portion of the ATPG search space is explored only once. The second applies headline objectives in parallel, rather than serially. For the 1965 ISCAS combinational benchmarks, EST accelerates S 0 CRATES by 6.53 times, when all faults are targeted, and by 5.51 times, when used with random pattern generation, f,iult simulation and fault dropping. This acceleration was achieved with minimal memory overhead.

Timing-driven placement is essential for full-custom VLSI, Gallium Arsenide, and ECL circuits to meet wire timing constraints. A new macro/custom cell floorplanner and global router, called MHERTZ, meets wire timing constraints by using force-directed cost functions in multi-start and simulated annealing (SA) optimization algorithms. MHERTZ also prevents wire coupling, meets specified chip aspect ratios, and produces smaller floorplans than TIMBERWOLFMC.

We recently proposed an unconventional digital circuit modeling technique and formulated test generation as an energy minimization problem [7]. Although energy minimization is as hard as test generation, the new approach has two advantages. Since the circuit function is mathematically expressed, operations research techniques like linear and non-linear programming can be applied to test generation. The non-causal form of the model makes parallel processing possible. The energy function E, a quadratic 0-1 function, is split into two sub-functions, a homogeneous posiform and an inhomogeneous posiform. The minimum of E is the sum of the minima of the two sub-functions, each having a minimum value of 0. We obtain a minimizing point of the homogeneous posiform, in time complexity that is linear in the number of sub-function terms, and check if the other sub-function becomes 0. When both become 0, we have a test vector. We discuss several easily parallelizable speedup techniques using the transitive closure and other graph properties. Preliminary results on combinational circuits confirm the feasibility of this technique.

We present a new algorithm, EST, that accelerates any combinatorial circuit Automatic Test-Pattern Generation algorithm. EST detects equivalent search states, which are saved for all faults during ATPG. The search space is reduced by using Binary Decision Diagram fragments to detect previously-encountered search states (possibly from prior faults). Search terminates earlier than before. Redundant fault analysis further accelerates ATPG. ATPG is accelerated 1347 times for hard-to-test faults in the ISCAS '85 benchmarks.

A new automatic test pattern generation (ATPG) methodology that has the potential to exploit fine-grain parallel computing and relaxation techniques is described. This approach is radically different from the conventional methods used to generate tests for circuits from their gate level description. The digital circuit is represented as a bidirectional network of neurons. The circuit function is coded in the firing thresholds of neurons and the weights of interconnection links. This neural network is suitably reconfigured for solving the ATPG problem. A fault is injected into the neural network and an energy function is constructed with global minima at test vectors. The authors simulated the neural network on a serial computer, and determined the global minima of the energy function using a directed search technique augmented by probabilistic relaxation. Preliminary results on combinational circuits confirm the feasibility of this technique.>

Ulysses is a VLSI computer-aided-design (CAD) environment that effectively addresses the problems associated with CAD tool integration. Specifically, Ulysses allows for the integration of a collection of individual CAD tools into a design automation (DA) system that will execute a codified design methodology. Ulysses can track the multiple partial designs that result during a complete design cycle. Furthermore, Ulysses allows the designer to interrupt the design process at any time and take control. An example involving a silicon compilation task is presented to illustrate the ability of Ulysses to execute a sequence of CAD tools automatically to generate a viable layout for an IC. This example also illustrates Ulysses' ability to recover from CAD tool failures that may result if a layout cannot be completed due to routing channel congestion or overconstrained leaf-cell boundary conditions.>

An automatic test pattern generation (ATPG) methodology that has the potential to exploit fine-grain parallel computing and relaxation techniques is described. The approach is radically different from the conventional methods used to generate tests for circuits from their gate-level descriptions. A digital circuit is represented as a bidirectional network of neurons. The circuit function is coded in the firing thresholds of neurons and the weights of interconnection links. This neural network is suitably reconfigured for solving the ATPG problem. A fault is injected into the neural network and an energy function is constructed with global minima at test vectors. Global minima are determined by a probabilistic relaxation technique augmented by a directed search. Preliminary results on combinational circuits confirm the feasibility of the technique.>

Ulysses is a VLSI CAD environment which effectively addresses the problems associated with CAD tool integration. Specifically, Ulysses allows the integration of CAD tools into a design automation system, the codification of a design methodology, and the representation of a design space. Ulysses keeps track of the progress of a design and allows exploration of the design space. The environment employs artificial intelligence techniques, functions as an interactive expert system, and interprets descriptions of design tasks encoded in the scripts language. An example of an integrated circuit layout design task is provided. The use of Ulysses in performing this task is discussed in detail.