In this paper, a novel logic BIST (built-in self test) scheme with complementary weights is proposed. The BIST implementation combines random patterns with complementary-weight weighted patterns. A heuristic algorithm based on deterministic test set is developed to compute weight set with complementary weights. Hardware similar to bit-flipping is used to produce complementary weights. For random resistant ISCAS circuits, complete fault coverage can be achieved with very low hardware overhead. Experiments show that two complementary weights are sufficient for weighted random pattern testing and it presents a novel direction for exploiting weighted patterns.

This work presents a novel BIST (built-in self test) scheme with scan chain segmentation. In the scheme, a combination of pseudo random patterns and single-weight patterns have been applied to CUT (circuit under test). Scan chain is partitioned into multiple segments delimited by inverters. When a single weighted pattern is applied to a segmented scan chain, successive segments receive bit patterns with complementary weights. Several segment configurations may be required to achieve full fault coverage. In this scheme the control logic is inside the scan path and built-in self test can be implemented without compromising timing performance of CUT. Experiments show that our scheme can obtain very good fault coverage. Hardware implementation is simple and straightforward.

This paper presents a novel scan cell based control point insertion technique which eliminates timing degradation of conventional control points in built-in self test (BIST) applications. In this approach, control points are encoded into scan chains. Observation points are applied to enhance fault coverage. At each phase, a set of control points are activated to detect a set of target faults. Compared to conventional test point insertion, scan cell based control points improve controllability of the core logic without compromising timing performance of circuit under test (CUT). Experimental results show that close to stuck-at fault coverage by automatic test pattern generation (ATPG) can be achieved by our BIST method.

In this paper we analyze the coverage of distributed delay defects, on untested but functionally sensitizable paths, achieved by robustly testing a subset of paths in the circuit. This is measured by translating the information gained from robust testing into a set of linear constraints on edge delays and then using these to bound the circuit delay. Surprisingly, the results of our experiments on ISCAS benchmark circuits show that robust testing of a subset of paths in the circuit, may not cover distributed delay defects on the remaining paths very well at all.

Partial scan design is divided into two stages: 1) critical cycle breaking and 2) partial scan flip-flop selection with respect to conflict resolution. A multiple phase partial scan design method is introduced by combining circuit state information and conflict analysis. Critical cycles are broken using a combination of valid circuit state information and conflict analysis. It is quite cost-effective to obtain circuit state information via logic simulation, therefore, circuit state information is iteratively updated after a given number of partial scan flip-flops have been selected. The valid-state-based testability measure may become ineffective to select scan flip-flops when cycles remaining in the circuit are not so influential to testability. The method turns to the conflict resolution process using an intensive conflict-analysis-based testability measure conflict. Sufficient experimental results are presented.

This paper addresses the problem of compacting test responses in the presence of unknowns at the input of the compactor by exploiting the capabilities of well-known error detection and correction codes. The technique, called i-Compact, uses Saluja-Karpovsky Space Compactors, but permits detection and location of errors in the presence of unknown logic (X) values with help from the ATE. The advantages of i-Compact are: 1. Small number of output pins front the compactors for a required error detection capability; 2. Small tester memory for storing expected responses; 3. Flexibility of choosing several different combinations of number of X values and number of bit errors for error detection without altering the hardware compactor; 4. Same hardware capable of identifying the line that produced an error in presence of unknowns; 5. Use of non-proprietary codes found in the literature of 1950s; and 6. Independent of the circuit and the test generator.

Localized delay defects, like resistive shorts, resistive opens, etc., can be effectively detected by testing the longest testable path through each wire (or gate) in the circuit. Such a delay test set is referred to as a longest-path-per-wire test set. In this paper we study test data volume and test application time reduction techniques for such tests based on the Illinois scan architecture. We present a novel ATPG flow to quickly determine longest-path-per-wire test sets under constraints imposed by the Illinois scan architecture. Results of experiments on ISCAS sequential circuits are presented. On an average we achieve a test data volume reduction of 2.79X and number of test cycles reduction of 3.28X for robust path delay, tests (as compared to the case without Illinois scan). The corresponding numbers for non-robust tests are 3.58X and 4.24X.

As the complexity of VLSI circuits is increasing due to the exponential rise in transistor count per chip, testing cost is becoming an important factor in the overall integrated circuit (IC) manufacturing cost. This paper addresses the issue of decreasing test cost by lowering the test data bits and the number of clock cycles required to test a chip. We propose a new incremental algorithm for generating tests for Illinois Scan Architecture (ILS) based designs and provide analysis of test data and test time reduction. This algorithm is very efficient in generating tests for a number of ILS-designs in order to find the most optimal configuration.

Testing the longest path passing through each gate is important to detect small localized delay defects at a gate, e.g. resistive opens or resistive shorts. In this paper we present ATPG techniques to automatically determine the longest testable path passing through a gate or wire in the circuit without first listing all long paths passing through it. This technique is based on a graph traversal algorithm that can traverse all paths of a given length in a weighted directed acyclic graph. Experimental results for ISCAS benchmarks are also presented.

As the complexity of VLSI circuits is increasing due to the exponential rise in transistor count per chip, testing cost is becoming an important factor in the overall integrated circuit (IC) manufacturing cost. This paper addresses the issue of decreasing test cost by lowering the test data bits and the number of clock cycles required to test a chip. We propose a technique based on the reconfiguration of scan chains to reduce test time and test data volume for Illinois Scan Architecture (ILS) based designs. This technique is presented with details of hardware implementation as well as the test generation and test application procedures. The reduction in test time and test data volume achieved using this technique is quite significant in most circuits.

Scan based test techniques offer a very efficient alternative to achieve high fault coverage when compared to functional pattern testing. As circuit sizes grow ever larger, test data volume and test application time grow unwieldy even in the very efficient scan based designs. The Illinois Scan Architecture is a low cost alternative to conventional scan. In this paper, we present the first ever reported case study of the effectiveness of the Illinois Scan Architecture on an industrial circuit.

Testing the critical paths in a circuit is essential to cover distributed delay and small delay defects in a manufactured circuit. However, in most circuits, only a small percentage of functionally irredundant critical paths (which can affect the cycle time) are robustly testable. We propose the covering of defects on untestable critical paths by robustly testing the longest testable segments lying on those paths. This method is scalable to large circuits since the task of segment delay fault test generation has complexity similar to path delay fault test generation. Experimental results have been given to demonstrate that significant additional coverage of defects on critical paths can be achieved using this technique.

This article describes a diagnostic fault simulator for stuck-at faults in sequential circuits that is both time and space efficient. The simulator represents indistinguishable classes of faults as memory efficient lists. The use of lists reduces the number of output response comparisons between faults and hence speeds up the simulation process. The lists also make it easy to drop faults when they are fully distinguished from other faults. Experimental results on the ISCAS89 circuits show that the simulator runs significantly faster than an earlier work based on distinguishability matrices, and for large circuits is faster and more memory efficient than a recent method based on lists of indistinguishable faults. The paper provides the first reports on pessimistic and optimistic diagnostic measures for all faults of the large ISCAS circuits with known deterministic tests. The diagnostic fault simulator has also been modified to diagnose defects, given the output responses of failing devices. Results on simulated bridging defects show that the diagnosis time is comparable to the time for fault simulation with fault dropping.

This paper presents new test generation techniques for improving the average-case performance of the iterative logic array based deterministic sequential circuit test generation algorithms. To be able to assess the effectiveness of the proposed techniques, we have developed a new ATPG system for sequential circuits, called ATOMS, and we have incorporated these techniques into the test generator ATOMS achieved very high fault coverages in a short amount of time for the ISCAS89 sequential benchmark circuits, demonstrating the effectiveness of these techniques on the test generation performance.

The number of robustly testable paths is very low for typical circuits, hence the delay defect coverage of a robust path fault test set can be very small. Robustly testing path-segments which are not covered by any robustly testable paths can enhance the defect coverage of a path test set, however the existence of such uncovered path-segments in benchmark circuits has not been proven so far. In this paper we experimentally prove the existence of robustly testable path-segments not covered by any robustly testable paths in the ISCAS benchmark circuits. A highly effective delay fault test generator using some novel techniques, has been implemented for this purpose and is also described in the paper.

This paper presents a new technique, called C-compatibility, for reducing the test application time of the counter-based exhaustive built-in-self-test (BIST) test pattern generators. This technique reduces the test application time by reducing the size of the binary counter used in the test pattern generators. We have incorporated the synthesis algorithm for synthesizing BIST test pattern generators using the C-compatibility technique into ATOM, an advanced ATPG system for combinational circuits. The experimental results showed that the test pattern generators synthesized using this technique for the ISCAS 85 and full scan versions of the ISCAS 89 benchmark circuits achieve 100% stuck-at fault coverage in much smaller test application time than the previously published counter-based exhaustive BIST pattern generators.

Paths in a circuit share many lines and gates and hence, under specific assumptions, path delays are linearly related to each other. The delays of all the paths in a circuit can be expressed as a linear combination of the delays of a small subset of paths called the basis path set. In this paper we present a testing methodology and efficient algorithms to establish an upper bound (in most cases greater than the circuit clock period) on the circuit delay by testing only the paths in the basis path set. Since the size of the basis path set has been shown to be at most linear in the size of the circuit, this technique has the potential of drastically reducing the number of paths that have to be tested. Experimental results for benchmark circuits are given.

This paper presents a new algorithm, essential fault reduction, for generating compact test sets for combinational circuits under the single stuck-at fault model, and a new heuristic for estimating the minimum single stuck-at fault test set size. These algorithms together with the dynamic compaction algorithm are incorporated into an advanced automatic test pattern generation system for combinational circuits, called MinTest. MinTest found better lower bounds and generated smaller test sets than the previously published results for the ISCAS85 and full scan versions of the ISCAS89 benchmark circuits.

A new method for state justification is proposed for sequential circuit test generation. The linear list of states dynamically obtained during the derivation of test vectors is used to guide the search during state justification. State-transfer sequences that drive the circuit from the current state to the target state may already be known. Otherwise, genetic engineering of existing state-transfer sequences is required. In both cases, genetic-algorithm-based techniques are used to generate valid state justification sequences for the circuit in the presence of the target fault. This approach achieves extremely high fault coverages, and thus outperforms previous deterministic and simulation-based techniques.

New measures of peak power are proposed in the context of sequential circuits, and an efficient automatic procedure is presented to obtain very good lower bounds on these measures, as well as providing the actual input vectors that attain such bounds. Automatic generation of a functional vector loop for near-worst case power consumption is also attained. Experiments show that vector sequences generated give much more accurate estimates of peak power dissipation and are generated in significantly shorter execution times than estimates made from randomly generated sequences for four delay models.

Two fast algorithms for static test sequence compaction are proposed for sequential circuits. The algorithms are based on the observation that test sequences traverse through a small set of states and some states are frequently revisited throughout the application of a test set. Subsequences that start and end on the same states may be removed if necessary and if sufficient conditions are met for them. Contrary to the previously proposed methods, where multitudes of fault simulations are required, the techniques described in this paper require only two fault simulation passes and are applied to test sequences generated by various test generators, resulting in significant compactions very quickly for circuits that have many revisited states.

Dynamic test sequence compaction is an effective means of reducing test application time and often results in higher fault coverages and reduced test generation time as well. Three simulation-based techniques for dynamic compaction of test sequences are described. The first technique uses a fault simulator to remove test vectors from the test sequence generated by a test generator if the vectors are not needed to detect the target fault, considering that the circuit state may be known. The second technique uses genetic algorithms to fill the unspecified bits in a partially-specified test sequence in order to increase the number of faults detected by the sequence. The third technique uses test sequences provided by the test generator as seeds in a genetic algorithm, and better sequences are evolved that detect more faults. Significant improvements in test set size, fault coverage, and test generation time have been obtained over previous approaches using combinations of the three techniques.

Thispaperpresents two new algorithms, Redundant Vec-torElimination (RVE) and Essential Fault Reduction (EFR), for generating compact test sets for combinational circuits under the single stuck at fault model, and a new heuristic for estimating ihe minimum single stuck at fault test set size.7hese algon.thmstogether with the dynamic compaction algorithm are incorporated into an advancedATPG systemfor combinational circuits, called MinTest.MinTestfound better lower bounds and generated smaller test sets than the previ-OUSIJY published resultsfor the ISCAS85 andfill scan version of the ISCAS89 benchmark circuits.I

In this paper, we propose a high-level vatiable selection jor patiial-smn approach to improue the testability oj digital systems.The testability oj a design is evaluated at the high level based on previously pToposed contTol[abi!ity and observability mwuTes.A testability gruding technique is utilized to measure the Telative testability improvement in a design as the result oj making a subset of the variables jully controllable and observable.The variables that cause the gTeatest testability improvement aTe selected, and the selection pTocess is perjormed incrementally until no fiTtheT testability improvement can be achieved.Then the TegisteTs that correspond to the selected variables aTe placed in the scan-chain jor partial-scan implementation.The qerimentul Tesults shows that the vatiable selection approach.produces partial-scan implementations that cun achieve high jault coveTage, while the logic oveTheads are jairly low.

This paper proposes a method to enhance topological ATPG algorithms by exploiting some information computed through symbolic techniques. Since symbolic techniques can only be applied to small circuits, suitable circuit portions (named macros) are first selected, and then symbolic techniques are used to analyze their state graphs. The topological ATPG algorithm benefits from this analysis to bound its search tree. Experimental results show that the proposed approach is effective in reducing the required CPU time and increasing both the Fault Coverage and the Fault Efficiency. When high-level information about the circuit behavior and structure is available, it can be fruitfully exploited for macro selection.

One of the common misconceptions about a stuck-at fault model is that it does not model a physical defect accurately and therefore is not adequate for testing defects in advancing technologies. Stuck-at fault model can be described as anything but a physical defect model. You can call it abstract, logical, Boolean, symbolic, functional or behavioral model, but don't call it a physical defect model! But that is not a weakness of the stuck-at fault model. To the contrary, abstraction is the main strength of this model and the reason for its longevity. Abstraction is also the reason that it will be the model of choice in the next millenium. By staying away from physical details stuck-at fault model remains effective with changing technologies and design styles. Stuck-at fault model operates in the logic domain while most physical level models operate in analog domain or even in the electromagnetic domain. With the rapidly growing number of transistors on a chip, abstraction is a necessity to manage complexity. So if anything the trend for the next millenium is likely to be a higher level of abstraction. Does the abstraction come at a cost in loss of defect detection? To answer this let us consider two major classes of defects: defects internal to a gate and defects external to a gate.

This paper presents two algorithms for generating compact test sets for combinational and full scan circuits under the transition and CMOS stuck-open fault models; Redundant Vector Elimination (RVE) and Essential Fault Reduction (EFR). These algorithms together with the dynamic compaction algorithm are incorporated into an advanced ATPG system for combinational circuits, called MinTest. The test sets generated by MinTest are 30% smaller than the previously published two-pattern test set compaction results for the ISCAS85 and full scan version of the ISCAS89 benchmark circuits.

This paper presents new techniques for speeding up deterministic test pattern generation for VLSI circuits. These techniques improve the PODEM algorithm by reducing number of backtracks with a low computational cost. This is achieved by finding more necessary signal line assignments, by detecting conflicts earlier, and by avoiding unnecessary work during test generation. We have incorporated these techniques into an ATPG system for combinational circuits, called ATOM. The performance results for the ISCAS85 and full scan version of the ISCAS89 benchmark circuits demonstrated the effectiveness of these techniques on the test generation performance.

New methods for fault-effect propagation and state justification that use finite-state-machine sequences are proposed for sequential circuit test generation. Distinguishing sequences are used to propagate the fault effects from the flip-flops to the primary outputs by distinguishing the faulty machine state from the fault-free machine state. Set, clear, and pseudoregister justification sequences are used for state justification via a combination of partial state justification solutions. Reengineering of existing finite-state machine sequences may be needed for specific target faults. Moreover, conflicts imposed by the use of multiple sequences may need to be resolved. Genetic-algorithm-based techniques are used to perform these tasks. Very high fault coverages have been obtained as a result of this technique.

The authors propose a novel algorithm to rapidly identify untestable delay faults using pre-computed static logic implications. The fault-independent analysis identifies large sets of untestable faults, if any, without enumerating them. The cardinalities of these sets are obtained by using a counting algorithm that has quadratic complexity in the number of lines. Since the method is based on an incomplete set of logic implications, it gives only a lower bound on the number of untestable faults. A post-processing step can list the untestable faults, if desired. Targeting untestable delay faults for test generation by an automatic test pattern generation (ATPG) tool can be avoided. The method works for the segment delay fault model and its special case, the path delay fault model, and identifies robustly untestable, non-robustly untestable, and functionally unsensitizable delay faults. Results on benchmark circuits show that many delay faults are identified as untestable in a very short time. For the benchmark circuit c6288, the algorithm identified 1.978/spl times/10/sup 20/ functionally unsensitizable path faults in 3 CPU seconds.

Previous work has shown that maximum switching density at a given node is extremely sensitive to a slight change in the delay at that node. However, when estimating the peak power for the entire circuit, the powers estimated must not be as sensitive to a slight variation or inaccuracy in the assumed gate delays because computing the exact gate delays for every gate in the circuit during simulation is expensive. Thus, we would like to use the simplest delay model possible to reduce the execution time for estimating power, while making sure that it provides an accurate estimate, i.e., that the peak powers estimated will not vary due to a variation in the gate delays. Results for four delay models are reported for the ISCAS85 combinational benchmark circuits, ISCAS89 sequential benchmark circuits, and several synthesized circuits.

New measures of peak power in the context of sequential circuits are proposed.This paper presents an automatic procedure to obtain very good lower bounds on these measures as well as the actual input vectors that attain such bounds.The initial state of the circuit is an important factor in determining the amount of switching activity in sequential circuits and is taken into account.A peak power estimator tool K2 was developed using genetic techniques.Experiments show that vector sequences generated by K.2 give much more accurate estimates for peak power dissipation than the estimates made from randomly generated sequences.

The need for test generation tools which target bridging faults in addition to stuck-at faults is growing. This work introduces BART, a new bridging-fault-targeted test; generator based upon HITEC and E-PROOFS, and gauges its performance against that of other techniques for bridging fault testing. A new circuit modification is proposed which allows a single bridging fault to be represented as a collection of four stuck-at faults. This modification is refined so that lines can be justified so as to maximize the probability that the voltage on one of the bridged nodes is corrupted enough to represent an incorrect logic value. This refinement uses the concept of "strong" and "weak" logic values, which gauge the resistance of the path between a gate output and the driving rail. BART was able to produce test sets which gave reasonable coverage for sequential circuits as well as combinational circuits.

Dynamic test sequence compaction is an effective means of reducing test application time and often results in higher fault coverages and reduced test generation time as well. A new algorithm for dynamic test sequence compaction is presented that uses genetic techniques to evolve test sequences. Test sequences provided by a test generator and previously evolved sequences already included in the test set are used as seeds in the genetic population. Significant improvements in test set size, fault coverage, and test generation time have been obtained over previous approaches.

A method to perform diagnostic test generation in sequential circuits by modifying a conventional test generator is presented. The method utilizes circuit netlist modification along with a forced value at primary input in the modified circuit techniques to reduce the computational effort for diagnostic test pattern generation in sequential circuits. Speed-up of the diagnostic ATPG process is achieved by the identification of states that are impossible to justify with three-valued logic.

Two fast algorithms for static test sequence compaction are proposed for sequential circuits. The algorithms are based on the observation that test sequences traverse through a small set of states, and some states are frequently re-visited throughout the application of a test set. Subsequences that start and end on the same states may be removed if necessary and sufficient conditions are met for them. The techniques require only two fault simulation passes and are applied to test sequences generated by various test generators, resulting in significant compactions very quickly for circuits that have many revisited states.

We propose three synchronous parallel algorithms for scalable parallel test set partitioned fault simulation. The algorithms are based on a new two-stage approach to parallelizing fault simulation for sequential VLSI circuits in which the test set is partitioned among the available processors, The test set partitioning inherent in the algorithms overcomes the good circuit logic simulation bottleneck that exists in traditional fault partitioned approaches to parallel fault simulation. The implementations were done on a shared memory multiprocessor and on a network of workstations. Two of the algorithms show a small degree of pessimism in a few cases, with respect to the fault coverage as compared with a uniprocessor run, while the third algorithm provides the same results as in a uniprocessor run. All algorithms provide excellent speedups and perform much better than a traditional fault partitioned approach, on both shared and distributed memory parallel platforms.

This paper presents a new static logic implication algorithm. An improved implication procedure that fully takes advantage of the special context of static implication, the iterative method, and set algebra is described. The algorithm discovers at low cost many indirect implications which are not discovered by dynamic learning without tremendous time cost. The experimental results show that a very large number of indirect implications are found by our algorithm. The static implication procedure has many useful applications, one of which is static redundancy identification. Use of the static implications obtained from the algorithm in static redundancy identification for ISCAS85 combinational circuits resulted in a larger number of redundant faults identified than in previous methods.

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.

Test generation using deterministic fault-oriented algorithms is highly complex and time consuming. New approaches are needed to augment the existing techniques, both to reduce execution time and to improve fault coverage. Genetic algorithms (GA's) have been effective in solving many search and optimization problems. Since test generation is a search process over a large vector space, it is an ideal candidate for GA's. In this work, we describe a GA framework for sequential circuit test generation. The GA evolves candidate test vectors and sequences, using a fault simulator to compute the fitness of each candidate test. Various GA parameters are studied, including alphabet size, fitness function, generation gap, population size, and mutation rate, as well as selection and crossover schemes. High fault coverages were obtained for most of the ISCAS'89 sequential benchmark circuits, and execution times were significantly lower than in a deterministic test generator in most cases.

We present two algorithms, called list-based scheme and tree-based scheme, to compute bridging fault (BF) coverage ofIDDQtests. These algorithms use the novel ideal of “indistinguishable pairs,” which makes it more efficient and versatile than known fault simulation algorithms. Unlike known algorithms, the two algorithms can be used for combinational as well as sequential circuits and for arbitrary sets of BFs. Experiments show that the tree-based scheme is, in general, better than the list-based scheme. But the list-based scheme is better for some classes of faults.

State information of a sequential circuit can be used to evaluate the complexity of test generation.The ratio of valid states to all the states of the circuit is an important indicator of test generation complexity.Using valid states obtained via logic simulation, a testability measure based on the density of encoding is proposed for scan flip flop selection.A second testability measure based on the test generation state information is also presented and used to select scan flip flops.Cycles are broken selectively on the basis of the circuit state information.Good fault coverage and test efficiency are obtained when fewer scan flip flops than the minimum cut set are selected.Experimental results are presented to demonstrate the effectiveness of the method.

We define a new delay fault model, called the double transition fault model. Under this model, a fault is associated with a pair of lines and a pair of transitions on these lines. The model captures the effects of defects that increase the delays of two (or more) individual lines by an amount that causes the circuit to fail when signals are propagated through both lines. It thus provides a simplification of the path delay fault model, that does not suffer from the exponential behavior of this model. We propose a test generation procedure for double transition faults, based on reordering of a given test set for stuck-at faults. The procedure does not require enumeration of all double transition faults, and is thus applicable to circuits with large numbers of lines. We present experimental results of this procedure for several benchmark circuits.

We propose an efficient combinational circuit simulation technique for the recently proposed segment delay fault model. After simulation of a vector pair, activated segments are traced using a depth-first search. A segment numbering scheme finds the number of faults to be simulated. A labeling technique generates edge labels to compute a unique label for each segment fault. The use of labels avoids explicit storing of fault lists and allows efficient access to previously detected segment faults. Experimental results demonstrate several advantages of the segment delay fault model. First, the total number of faults remains manageable for small segment lengths. Second, many segments, not included in any robustly testable path fault, may have robust segment delay fault tests. Generating tests for such segments may increase the delay defect coverage.

In this study, we present a controllability measure for high-level circuit descriptions and a high-level synthesis-for-testability technique. Unlike many studies in the area of high-level synthesis for testability that focus on improving the testability of data paths, the objective of our approach is to improve the testability of synthesized circuits by enhancing the controllability of the control flow. Experimental results on several high-level synthesis benchmarks show that when this approach is used prior to logic synthesis, a shorter ATPG time, a smaller test set, and better fault coverage and ATPG efficiency are often achieved. Implementation of this technique requires minimal logic and performance overheads and allows test vectors to be applied at clock-speed.

Simulation-based techniques for dynamic compaction of test sequences are proposed. The first technique uses a fault simulator to remove test vectors from the partially-specified test sequence generated by a deterministic test generator if the vectors are not needed to detect the target fault, considering that the circuit state may be known. The second technique uses genetic algorithms to fill the unspecified bits in the partially-specified test sequence in order to increase the number of faults detected by the sequence. Significant reductions in test set sizes were observed for all benchmark circuits studied. Fault coverages improved for many of the circuits, and execution times often dropped as well, since fewer faults had to be targeted by the computation-intensive deterministic test generator.

During fault simulation, an approximation frequently used in practice is to declare a fault to be detected after it has been potentially detected a predetermined number of times. This approximation may lead to declaring a fault detected when in fact the fault will not be detected during a standard test application process. We propose an alternative measure of fault detection for potentially detected faults, that is easy to compute, yet its accuracy is significantly higher than the measure based on the number of times a fault is potentially detected. Experimental results are shown to support the accuracy of the new measure.

A global partial scan design algorithm based on circuit state information is proposed. Valid states obtained via logic simulation are used to evaluate testability of the circuit. A testability measure based on the density of encoding is used to select scan flip flops, and the problem is formulated into an optimization problem. An algorithm is presented to obtain an initial partial scan design solution, and a variety of techniques are used to subsequently derive an optimal solution. The most significant technique used in the global algorithm is that a dynamic testability measure is adopted, which can greatly reduce the size of the search space and enhance the effectiveness of the search problem. The partial scan design method can greatly reduce potential backtracks during test generation. Experimental results demonstrate 100% test efficiency can be obtained for most circuits selecting fewer scan flip flops than other methods.

We propose a segment delay fault model to represent any general delay defect ranging from a spot defect to a distributed defect. The segment length, L, is a parameter that can be chosen based on available statistics about the types of manufacturing defects. Once L is chosen, the fault list contains all segments of length L and paths whose entire lengths are less than L. Both rising and falling transitions at the origin of segments are considered. Choosing segments of a small length can prevent an explosion of the number of faults considered. At the same time, a defect over a segment may be large enough to affect any path passing through it. We present an efficient algorithm to compute the number of segments of any possible length in a circuit. We define various classes of segment delay fault tests-robust, transition, and non-robust-that offer a trade-off between fault coverage and quality.

A fault-oriented sequential circuit test generator is described in which various types of distinguishing sequences are derived, both statically and dynamically, to aid the test generation process. A two-phase algorithm is used during test generation. The first phase activates the target fault, and the second phase propagates the fault effects (FE's) from the flip-flops with assistance from the distinguishing sequences. This strategy improves the propagation of FE's to the primary outputs, and the overall fault coverage is greatly increased. In our new test generator, DIGATE, genetic algorithms are used to derive both activating and distinguishing sequences during test generation. Our results show very high fault coverages for the ISCAS89 sequential benchmark circuits and several synthesized circuits.

An efficient automatic test pattern generator for I/sub DDQ/ current testing of CMOS digital circuits is presented. The complete two-line bridging fault set is considered. An adaptive genetic algorithm (GA) is used to generate compact test sets. Experimental results for ISCAS85 and ISCAS89 benchmark circuits are presented. The results show that GA-based test generators are very well suited for generating compact test sets for I/sub DDQ/ testing of bridging faults.

Mixed analog and digital mode simulators have been available for accurate /spl alpha/-particle-induced transient fault simulation. However, they are not fast enough to simulate a large number of transient faults on a relatively large circuit in a reasonable amount of time. In this paper, we describe a gate-level transient fault simulation environment which has been developed based on realistic fault models. Although the environment was developed for /spl alpha/-particle-induced transient faults, the methodology can be used for any transient fault which can be modeled as a transient pulse of some width. The simulation environment uses a gate level timing fault simulator as well as a zero-delay parallel fault simulator. The timing fault simulator uses logic level models of the actual transient fault phenomenon and latch operation to accurately propagate the fault effects to the latch outputs, after which point the zero-delay parallel fault simulator is used to speed up the simulation without any loss in accuracy. The environment is demonstrated on a set of ISCAS-89 sequential benchmark circuits.

In hierarchical test generation, the test vectors for the low level structure of the module under test are computed and then justified at a high level. In the module test computation procedure, a low level ATPG tool is conventionally applied to the complete structure of that particular module without adding extra information. Due to the architectural level functional constraints applied to the inputs of that module, many of the test vectors being computed are not justifiable at the high level. Therefore, high efficiency cannot be achieved without managing the functional constraint problem in the hierarchical ATPG process. In this paper, both top-down and bottom-up approaches are addressed. It is shown that the valid control code abstraction and test cube justification techniques are very effective to overcome the architectural level functional constraint problem and to achieve high efficiency in test computation. The proposed algorithms have been implemented in our hierarchical ATPG package and promising experimental results have been derived. We conclude that architectural level functional constraints can be efficiently avoided through these techniques.

Overhead reduction techniques for hierarchical fault simulation are presented which reduce simulation overhead for the concurrent method and its expanded version, the Multi-List-Traversal method. The techniques include a one-pass fault simulation strategy, characteristic vectors, and contiguous concurrent machines. The cost of each process for the conventional and new methods is formulated for comparison. The methods were implemented in C, and experiments were conducted using ISCAS benchmark circuits. The results show that the new techniques make conventional concurrent fault simulators up to 4.9 times faster and also that the performance can be improved by fault ordering.

Abstract|A hybrid sequential circuit test generator is described which combines deterministic algorithms for fault excitation and propagation with genetic algorithms for state justi cation.Deterministic procedures for state justi cation are used if the genetic approach is unsuccessful, to allow for identi cation of untestable faults and to improve the fault coverage.High fault coverages were obtained for the ISCAS89 benchmark circuits and several additional circuits, and in many cases the results are better than those for purely deterministic approaches.

This paper describes a diagnostic fault simulator for stuck-at faults in sequential circuits that is both time and space efficient. The simulator represents indistinguishable classes of faults as memory efficient lists. The use of lists reduces the number of output response comparisons between faults and hence speeds up the simulation process. The lists also make it easy to drop faults when they are fully distinguished from other faults. Experimental results on the ISCAS89 circuits show that the simulator runs significantly faster than an earlier work based on distinguishability matrices and is faster and more memory efficient than a recent method based on lists of indistinguishable faults. The paper provides the first reports on pessimistic and optimistic diagnostic measures for all faults of the large ISCAS circuits. 1 Introduction The aim of fault location or diagnosis is to locate device failures. Diagnosis may be intended for identification and replacement of a faulty sub-circui...

A new technique is proposed to handle fault simulation at the architectural level. The technique bypasses the need for complete gate level structure and efficiently uses the architectural information. Symbolic data representing groups of stuck at faults, known as fault effects, are propagated across the circuit with intelligent propagation prediction. Fault effects may combine and form new groups in the process. Automated behavioral simulation using only three data types is used to propagate fault effects at the architectural level by propagation prediction; no additional high level constraints or precomputation of faulty behavior are needed for simulation. Although not a fully deterministic algorithm, the results of ALFSIM, Architectural Level Fault Simulation, show high accuracy when compared with the gate level fault simulation.

Fault simulation for sequential circuits numbers among the highly compute intensive tasks in the integrated circuit design process. In the quest for rapid design turn around, parallelization has been proposed to speed fault simulation. We introduce ProperPROOFS, a parallel extension of the PROOFS fault simulation package. ProperPROOFS exploits parallelism based on fault partitioning, incorporating static and dynamic partitioning schemes and a new asynchronous and distributed method of fault redistribution. We present results for circuits in the ISCAS-89 benchmark set across several parallel architectures. A detailed evaluation of results provides new insight into the use of fault partitioning to parallelize high performance serial fault simulation applications.

To ensure the production of reliable circuits and fully testable unpackaged dies for MCMs burn-in, both dynamic and monitored, remains a feasible option. During this burn-in process the circuit needs to be stressed for an extended period of time. This requires computation of cyclic input sequences to stress the circuit. A taxonomy of stress related problems for full scan circuits is presented. It is shown that there are efficient ways to compute the sequences for many variations of monitored burn-in problems. Preliminary experimental results on ISCAS89 benchmark circuits are presented.

The average distance between states is proposed as a new testability measure for finite state machines (FSMs). Also proposed is the concept of center state to reduce distances in FSMs. This test function embedding technique has been shown to improve the testability of sequential circuits with minimal overhead. An overview of several design for testability (DFT) and synthesis for testability (SFT) methods for sequential circuits is also given in this paper. Experimental results have shown that DFT approach is more advantageous than SFT approach to implement our test function. The contribution of this paper is to analyze the trade-offs between several aspects of DFT and SFT techniques.

Recent studies show that a stuck-at test applied at the operational speed of the circuit identifies more defective chips than a test having the same fault coverage but applied at a lower speed. Design-for-testability approaches based on full scan, partial scan, or silicon-based solutions such as CrossCheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed. In this work, we investigate various design-for-testability (DFT) techniques for sequential circuits that permit at-speed application of tests while providing for very high fault coverage. The method involves parallel loading of flip-flops in test mode for enhanced controllability combined with probe point insertion for enhanced observability. Fault coverage and ATG effectiveness improved to greater than 96% and 99.7%, respectively, for the ISCAS89 sequential benchmark circuits studied when these nonscan DFT techniques were used. The average area overhead for the nonscan DFT enhancements was 9.9% for standard cell implementations of three circuits synthesized from high-level descriptions, compared to 20.2% for full scan. ATG effectiveness improved to greater than 99.3% for all three circuits with the nonscan DFT enhancements.>

No abstract available.

Automatic test pattern generation (ATPG) for sequential circuits remains one of the most compute-intensive tasks in the integrated circuit design process. Although numerous attempts have been made to speed the ATPG process via parallelization, these attempts have often proved disappointing when compared against the best available serial algorithms using metrics of resultant quality and performance. In this paper we introduce ProperHITEC, a parallel extension of the HITEC/PROOFS sequential test generation package. ProperHITEC embodies a new approach to parallel ATPG; it is incrementally derived from one of the best-performing serial algorithms and this incremental derivation is implemented via the mechanisms of object-oriented programming. Results of running ProperHITEC on three parallel architectures, the Sun 4/600MP, the INTEL iPSC/860, and the Encore Multimax are presented. These results show that ProperHITEC achieves results virtually identical in quality to HITEC while achieving significant multiprocessor utilization.

Abstract|T est generation using deterministic faultoriented algorithms is highly complex and time-consuming.New approaches are needed to augment the existing techniques, both to reduce execution time and to improve fault coverage.In this work, we describe a genetic algorithm (GA) framew ork for sequential circuit test generation.The GA evolves candidate test vectors and sequences, using a fault simulator to compute the tness of each candidate test.Various GA parameters are studied, including alphabet size, tness function, generation gap, population size, and mutation rate, as well as selection and crossover schemes.High fault coverages were obtained for most of the IS-CAS89 sequential benchmark circuits, and execution times were signi cantly lower than in a deterministic test generator in most cases.

Previous work on radiation hardening has focused on designing memory elements to tolerate direct hits by high energy particles. The study of latch designs to tolerate high energy particle induced transient pulses arising in the combinational part of the circuit and traveling to the inputs of DFFs has been, ignored. In this work, we look at ways to slow down the input stage of latches by inserting resistances to tolerate transient pulses. Fault injection experiments indicates that most of the transient pulses can be tolerated with 7.5 ns penalty in performance, at least for the ISCAS-89 benchmark circuits. In circuits for critical systems, this penalty may be acceptable. Furthermore, this is not the best case penalty since the DFF can be individually optimized for the circuit and the transient pulse width can be somewhat shortened through redesign. Therefore, this is a viable approach for tolerating transient pulses in VLSI circuits used in critical systems.>

The increasing use of hardware description languages (HDL's) in VLSI design and the emergence of high-level test generation programs has led to an interesting problem. There is a need for design for testability (DFT) techniques that can be applied early in the design phase to improve the effectiveness of ATPG programs on hard-to-test circuits. By an early identification of hard-to-test areas of a circuit, testability can be inserted prior to logic synthesis. In this paper, we first present a comparative study of a gate-level test generator and a high-level test generator by benchmarking them on a common suite of circuits. Based on an evaluation of the results, we propose techniques to automatically extract information from the high-level circuit description that could improve the performance of both ATPG tools. An automatic DFT tool that utilizes VHDL descriptions of the circuit to make an intelligent selection of flip-flops for partial scan is then described. Results on six hard-to-test circuits show that very high fault coverages can be obtained by both a gate-level and a high-level test generator on these circuits after scan. With this detailed study we demonstrate that a DFT tool can make a more efficient and effective selection of partial scan flip-flops by exploiting the high-level circuit information. It can accurately predict the hard-to-test areas of a circuit. Significant improvements in fault coverage and ATPG efficiency, and speedups in ATPG time, can be obtained by a gate-level and a high-level test generator after high-level scan selection.>

Hierarchically designed microprocessor-like VLSI circuits have complex data paths and embedded control machines to execute instructions. When a test pattern has to be applied to the input of an embedded module, determination of a sequence of instructions, which will apply this pattern and propagate the fault effects, is extremely difficult. After the instruction sequence is derived, to assign values at all interior lines without conflicts is also very difficult. In this paper, we propose a separation of test generation process into two phases: path analysis and value analysis. In the phase of path analysis, a new methodology for automatic assembly of a sequence of instructions is proposed to satisfy the internal test goals. In the phase of value analysis, an equation-solving algorithm is used to compute an exact value solution for all interior lines. This new ATPG methodology containing techniques for both path and value analysis forms a complete solution for a variety of microprocessor-like circuits. This new approach has been implemented and experimented on six high-level circuits. The results show that our approach is very effective in achieving complete automation for high-level test generation.>

Some recent studies show that an at-speed sequential or functional test is better than a test executed at lower speed. Design-for-testability approaches based on full scan, partial scan or silicon-based solutions such as Crosscheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed of the circuit. In this paper, a design-for-test method that permits at-speed testing is introduced. The method is based on probe point insertion for improved observability, and it requires enhancements to an existing sequential circuit fault simulator. Faults that can be activated but not detected at existing primary outputs are targeted. A minimal set of probe points is selected to detect these faults, and the probe points are compressed to one or two output pins using exclusive-OR trees. The issue of aliasing of fault effects is addressed. Improvements in fault coverage were made for all 17 of the ISCAS89 sequential benchmark circuits studied. Fault coverages between 99% and 100% were obtained for seven circuits, and 100% ATG effectiveness was achieved on all but two circuits.>

Article Free Access Share on Non-scan design-for-testability techniques for sequential circuits Authors: Vivek Chickermane View Profile , Elizabeth M. Rudnick View Profile , Prithviraj Banerjee View Profile , Janak H. Patel View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 236–241https://doi.org/10.1145/157485.164686Published:01 July 1993Publication History 49citation329DownloadsMetricsTotal Citations49Total Downloads329Last 12 Months43Last 6 weeks19 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Systems designed for reliability must be validated through simulations. However, traditional SPICE like simulators or even mixed-mode simulators are too slow for the task of simulating the effects of /spl alpha/-particle hits on relatively large circuits. Gate-level simulators offer tremendous speedup over these electrical level simulators, but they are only as good as the model which captures the /spl alpha/-particle effect at the logic level. The goal of this research is to develop a computationally efficient model which captures the behavior of the /spl alpha/-particle at the logic level. This model can then be used in a gate-level timing simulator to propagate the /spl alpha/-particle effects to the latches and the outputs of the circuit under simulation. We have developed a closed form solution to approximate the logic pulse waveform resulting from /spl alpha/-particle hits. As is presented in the paper, the model tracks the data from SPICE simulations remarkably well.>

High speed architectures usually employ some form of parallelism or concurrency. Parallel or concurrent execution of a program not only increases the rate at which references are issued to the memory system but also changes the behavior of these references, relative to its serial-scalar execution. This paper reports the variations in program memory reference behavior when automatically transformed by a compiler and executed on parallel and vector archirectures. Using traces of the PERFECT benchmark set, executed on on Aliiant FX180 in a single scalar processor, single vector processor, scalar multiprocessor and vector multiprocessor modes, measurements are reported for issue rates, reference locality and data sharing.

This paper identifies the two key factors involved in obtaining accurate bridging fault simulation results and presents a hybrid technique that maximizes both the speed and accuracy of bridging fault simulation for gate-level standard cell designs. Both combinational and sequential circuits are studied and the results are compared with several other bridging fault simulators.>

When a logic module is embedded in a large circuit, the architectural level functional constraints usually cause don't cares at the interface of this module. If the logic of the module is not synthesized using these don't cares, then redundancy may exist making the circuit very hard to test. In this paper, architectural level circuit structural and instruction behavioral information is exploited to analyze functional constraints and extract don't cares. The don't cares are used to optimize the logic of the module and to remove many redundant faults.>

When VLSI circuits such as microprocessors are designed hierarchically, testability issues have to be considered simultaneously with functional specifications to reduce the testing complexity early in the design phase. Accurate testability measures are required to indicate the hard-to-test areas and can be used as a guidance for ATPG. This paper presents a new testability analysis technique operating at a high level using both circuit structural information and assembly-level instruction behavioral information. This testability analysis targets at the popular functional test generation and a modern high level ATPG methodology published in recent literature. The experimental results of testability measures as well as high level ATPG are presented to verify the effectiveness.>

Computer vision is regarded as one of the most complex and computationally intensive problems. In general, a Computer Vision System (CVS) attempts to relate scene(s) in terms of model(s). A typical CVS employs algorithms from a very broad spectrum such as numerical, image processing, graph algorithms, symbolic processing, and artificial intelligence. The authors present a multiprocessor architecture, called "NETRA," for computer vision systems. NETRA is a highly flexible architecture. The topology of NETRA is recursively defined, and hence, is easily scalable from small to large systems. It is a hierarchical architecture with a tree-type control hierarchy. Its leaf nodes consists of a cluster of processors connected with a programmable crossbar with selective broadcast capability to provide the desired flexibility. The processors in clusters can operate in SIMD-, MIMD- or Systolic-like modes. Other features of the architecture include integration of limited data-driven computation within a primarily control flow mechanism, block-level control and data flow, decentralization of memory management functions, and hierarchical load balancing and scheduling capabilities. The paper also presents a qualitative evaluation and preliminary performance results of a cluster of NETRA.>

A comparative study of a gate-level test generator and a high-level test generator by benchmarking them on a common suite of circuits is presented. Based on the examination of the results DFT techniques that use high-level circuit information are proposed. The results obtained after partial scan selection by a high-level DFT tool are compared with results obtained by a gate-level partial scan tool. This detailed comparative study demonstrates that a DFT tool can make a more effective selection of partial scan flip-flops by exploiting the high-level circuit information, and by accurately predicting the hard-to-test areas of a circuit.>

The problem of bridging fault simulation under the conventional voltage testing environment is considered. A method to provide electrical-level simulation accuracy, without paying the associated performance penalties, is proposed. A three-level simulation model is used, balancing the tradeoffs among gate-level, switch-level, and electrical-level simulation. Large memory overheads are avoided by localizing the fault, and by performing electrical-level simulation only in the area around the fault. This approach is sufficiently flexible to model feedback faults, BiCMOS circuits, stuck-open faults, and any fault that can be described with a circuit netlist. Tests were run on several ISCAS combinational and sequential benchmark circuits, using realistic cells and transistor parameters; results show that accurate simulations can be performed in reasonable time.>

A hierarchial testing approach for linear state variable digital systems based on matrix manipulation and constrained low-level test generation is reported. FEAST (functional extractor and sequential test generator) operates at the high level, where the circuit is described as an interconnection of arithmetic modules. CREST (constrained sequential test generator) operates at the low level description of the individual modules, and generates test sets satisfying constraints imposed by the high-level modules and their interconnection structure. The approach was found to perform better than automatic test generation at the gate level using existing algorithms for several large circuits.>

This paper presents techniques to utilize high-level structural, functional and register-transjer information to perform design-for-testability (DFT}. An automatic tool which utilizes VHDL descriptions of the datapath and control unit of sequential circuits to make an intelligent selection of scan pip-pops is described. This DFT tool ADEPT can make design enhancements early in the design phase. Results on four hard-to-test circuits show that very high fault coverages can be achieved by both a gate-level and a high-level test generator on these circuits after scan selection. Fewer scan jlip-flops were chosen as compared to a gate-level partial scan selection.

Hierarchically designed microprocessor-like VLSI circuits have complex data paths and complex embedded control machines to execute instructions. When a test pattern has to be applied to the input of an embedded module, determination of a sequence of instructions, which will apply this pattern and propagate the fault effects, is extremely diflcult. In this paper, we present a new methodology for automatic assembly of a sequence of instructions to satisfy the internal test goals. Combined with the previous equation-solving approach, this new high level ATPG methodology forms a complete solution for a variety of microprocessor-like circuits. This new approach has been implemented and experimented on three high level circuits. The results show that our approach is very effective in achieving complete automation for high level test generation.

In this work we describe a diagnostic fault simulator for sequential circuits which evaluates the effectiveness of a given test set in distinguishing between faults. Diagnostic fault simulation is performed on several ISCAS89 sequential benchmark circuits using two different deterministic test sets for each circuit. Several diagnostic measures are reported, including the diagnostic resolution, the diagnostic power, and the sizes of the indistinguishable fault classes. In addition, lists of indistinguishable faults are generated. Use of the diagnostic fault simulator to diagnose faults, given the output responses of failing devices, is also described.

Some recent studies show that an at-speed sequential or functional test is better than a test executed at lower speed. Design-for-testability approaches based on full scan, partial scan, or silicon-based solutions like Crosscheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed. In this paper, a design-for-test method which permits at-speed testing is introduced. The method is based on probe point insertion for improved observability. Improvements in fault coverage were made for all 16 of the ISCAS-80 benchmark circuits studied. Fault coverages between 99% and 100% were obtained for six circuits, and 100% ATG efficiency achieved on all but two circuits.>

The authors describe PROOFS, a fast fault simulator for synchronous sequential circuits, PROOFS achieves high performance by combining all the advantages of differential fault simulation, single fault propagation, and parallel fault simulation, while minimizing their individual disadvantages. The fault simulator minimizes the memory requirements, reduces the number of gate evaluations, and simplifies the complexity of the software implementation. PROOFS requires an average of one fifth the memory required for concurrent fault simulation and runs six to 67 times faster on the ISCAS-89 sequential benchmark circuits.>

The authors describe a number of heuristic algorithms to compact a set of test sequences generated by a sequential circuit automatic test pattern generator (ATPG). A model has been developed and analyzed which shows that finding the optimal solution has an exponential worst-case complexity. To achieve an acceptable run time, some heuristics have been developed that yield good suboptimal solutions in a very short time. Three heuristic algorithms were developed. These algorithms were implemented in C and lex and applied to several of the ISCAS-89 benchmark sequential circuits. They reduce the test length by 17%-63% with a very small time overhead, while having little effect on the original fault overage.>

Article Free Access Share on Parallel test generation for sequential circuits on general-purpose multiprocessors Authors: Srinivas Patil IBM Corporation P.O. Box 950, Poughkeepsie, NY IBM Corporation P.O. Box 950, Poughkeepsie, NYView Profile , Prithviraj Banerjee Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, ILView Profile , Janak H. Patel Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 155–159https://doi.org/10.1145/127601.127651Published:01 June 1991Publication History 27citation177DownloadsMetricsTotal Citations27Total Downloads177Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors propose a fault oriented partial scan design methodology to be performed as a sequel to test generation. Given the cost of converting each flip-flop to a scanned flip-flop and an overall bound on the cost of the scan design, the program OPUS-2 selects a set of flip-flops which are most likely to improve the quality of test generation. The expected improvement in testability is modeled by profit functions quantifying the reduction in weighted cycles, or the reduction in SCOAP values at hard-to-detect fault sites. Experiments performed on ISCAS89 sequential benchmark circuits show that, by analytically selecting only 10-20% of the flip-flops, the circuits can be tested to the same level of quality as a fully scanned circuit. The advantages of the proposed method are that the highest possible fault coverage can be achieved while limiting the cost of scan to a user-specified limit.>

A novel architectural level test generation methodology is proposed to solve both data flow path conflicts and data flow value conflicts. For each pattern to be justified at a high level, an instruction sequence and the underdetermined system of nonlinear equations are derived based on preprocessing information. The solution of the system of equations is calculated by a signal-driven discrete relaxation algorithm without making any high-level decisions. The test generation is performed by recursively assembling the instruction sequence and solving the system of equations. This test generation approach has been implemented, and the tests of several microprocessors have been generated successfully. The results show that this approach is effective and promising.>

Methods are investigated for reducing events in sequential circuit fault simulation by reducing the number of faults simulated for each test vector. Inactive faults, which are guaranteed to have no effect on the output or the next state, are identified using local information from the fault-free circuit in one technique. In a second technique, the Star-algorithm is extended to handle sequential circuits and provides global information about inactive faults, based on the fault-free circuit state. Both techniques are integrated into the PROOFS synchronous sequential circuit fault simulator. An average 28% reduction in faulty circuit gate evaluations is obtained for the 19 ISCAS-89 benchmark circuits studied using the first technique, and 33% reduction for the two techniques combined. Execution times decrease by an average of 17% when the first technique is used. For the largest circuits, further improvements in execution time are made when the Star-algorithm is included.>

This paper reports the cache performance of a set of vectorized numerical program from the Perfect Club benchmarks. Using a low cost trace driven simularion technique we show how a non-prefetching vector cache can result in unpredictable performance and how rhis unpredictability makes it difficult to find a good block size. We describe two simple prefetch schemes to reduce the influence of long stride vector accesses and misses due IO block invalidations in mulliprocessor vector caches. These two schemes are shown to have better performance than a non-prefetching cache.

In this paper, an ATF’G methodology working at an architectural level is proposed. For the data path portion, the hierarchy of the design is exploited and the dependence on the gate level information is relieved. For the conb’oi faults, gate level algorithms are incorporated with high level approaches to excite the fault and differentiate the fault effect to primary outputs. Due to the fault collapsing effect arid the fault differentiation process, several data types have been defined for the manipulation alf all possible fault e€fects. A functional equivalent model is used for sequential modules, which makes this technique extendable beyond the register-transfer level. The backtracking mechanism used in the control unit has been carefully modified to ensure a complete finite space searching. Some experimerrtal results are presented to show the effectiveness of this approach.

This paper describes PROOFS, a super fast fault simulator for synchronous sequential circuits. PROOFS achieves high performance by combining all the advantages of differential fault simulation, single fault propagation, and parallel fault simulation, while minimizing their individual disadvantages. PROOFS minimizes the memory requirements, reduces the number of events that need to be evaluated, and simplifies the complexity of the software implementation. PROOFS requires an average of one fifth the memory required for concurrent fault simulation and runs 6 to 67 times faster on the ISCAS sequential benchmarks.

A multiprocessor architecture called NETRA is discussed. It is highly reconfigurable and does not involve the use of complex interconnection schemes. The topology of this multiprocessor is recursively defined and is therefore easily scalable from small to large systems. It has a tree-type hierarchical architecture featuring leaf nodes that consist of a cluster of small but powerful processors connected via a programmable crossbar with selective broadcast capability. The architecture is simulated on a hypercube multiprocessor and the performance of one processor cluster is evaluated for stereo-vision tasks. The particular stereo algorithm selected for implementation requires computation of the two-dimensional fast Fourier transform (2-D FFT), template matching, histogram computation, and least-squares surface fitting. Static partitioning of data is used for the data-independent tasks such as 2-D FFT and dynamic scheduling, and load balancing is used for the data-dependent tasks of feature matching and disambiguation.>

Several techniques to perform static and dynamic load balancing for vision systems are presented. These techniques capture the computational requirements of a task by examining the data when it is produced. They can be applied to many vision systems because many algorithms in different systems are either the same or have similar computational characteristics. These techniques are evaluated by applying them on a parallel implementation of the algorithms in a motion estimation system on a hypercube multiprocessor system. It is shown that the performance gains when these data decomposition and load balancing techniques are used are significant and that the overhead of using these techniques is minimal.>

The problem of selecting flip-flops for inclusion into a partial scan path is formulated as an optimization problem. Scan flip-flops result in layout and delay overheads. Hence, scan flip-flops have to be chosen such that the net cost associated with these overheads is bounded by some user-specified limit. The problem then reduces to choosing a set of flip-flops which gives the best improvement in testability, while keeping the cost bounded. Cost functions are proposed for a standard cell design approach to model the effects of the overheads. Profit functions for three different testability criteria are proposed, and the optimization methodology for each is discussed. The optimization process is modeled on the lines of the 0/1 knapsack problem. Results for some medium-sized sequential circuits which show a very large improvement in fault coverage obtained by optimally selecting a small fraction of the flip-flops in the circuit are presented.>

The problem of recovering from processor transient faults in shared memory multiprocessor systems is examined. A user-transparent checkpointing and recovery scheme using private caches is presented. Processes can recover from errors due to faulty processors by restarting from the checkpointed computation state. Implementation techniques using checkpoint identifiers and recovery stacks are examined as a means of reducing performance degradation in processor utilization during normal execution. This cache-based checkpointing technique prevents rollback propagation, provides rapid recovery, and can be integrated into standard cache coherence protocols. An analytical model is used to estimate the relative performance of the scheme during normal execution. Extensions to take error latency into account are presented.>

This paper proposes the use of a functional-level testing methodology based on the generation of test vectors from the functional descriptions of combinational circuits under test. The approach that is adopted involves the generation of a two-level AND-OR, or OR-AND implementation from a circuit's functional description, the generation of test vectors by way of a PODEM based algorithm for the two-level implementation, and the application of the generated tests on a specific implementation(s) of the circuit under test. This approach is experimentally evaluated on various combinational circuits, and is shown to be successful in achieving very high fault-coverages without relying on implementation details of the circuits that are tested.

The authors address the problem of accurate logic simulation in the presence of unknowns. Algorithms to perform exact simulation using high-level descriptions are presented. The complexity of these algorithms is shown to be considerably less than that of existing algorithms. An analysis of realistic programmable logic arrays (PLAs) and some random functions is used to compare the complexity of the two algorithms presented. Data on the SN74181 ALU suggest that function blocks of similar size can be easily dealt with. The feasibility of the approach is demonstrated by a programmed implementation of the algorithms as part of a high-level test generation system.>

Integrated vision systems employ a sequence of image understanding algorithms in which the output of an algorithm is the input of the next algorithm in the sequence. Algorithms that constitute an integrated vision systems exhibit different characteristics, and therefore, require different data decomposition techniques and efficient load balancing techniques for parallel implementation. However, since input data of a task is produced as output of the previous task, this information can be exploited to perform knowledge based data decomposition and load balancing. This paper presents several techniques to perform static and dynamic load balancing schemes for integrated vision systems. These techniques are novel in the sense that they capture the computational requirements of a task by examining the data when it is produced. Furthermore, they can be applied to many integrated vision systems because many algorithms in different systems are either same or have similar computational characteristics. These techniques are evaluated by applying them to the algorithms in a motion estimation system. It is shown that the performance gains when these techniques are used are significant and the overhead of using these techniques is minimal. The performance is evaluated by implementing the algorithms using the presented techniques on a hypercube multiprocessor system.

The problem of diagnosis and spare allocation for random-access memory (RAM) with coupling faults is addressed. A number of spare allocation algorithms for RAM with row and column redundancy have recently been proposed. These procedures, however, have been restricted to repair stuck-at faults. The authors examine both diagnosis and repair of coupling faults in RAMs utilizing spare rows and columns. It is shown that a coupling fault is repaired if its coupling cell is replaced by utilizing a spare row or its coupled cell is replaced by utilizing a spare row or column. By specifying both the coupled cell and coupling cell, the amount of redundancy required to repair a given set of faults may be reduced. A diagnosis procedure for RAM is provided to locate stuck-at faults as well as coupling faults. A graph model is used to describe the repair of coupling faults. A repair procedure has been implemented to allocate rows and columns for repair.>

A design strategy is presented for efficient and comprehensive parallel testing of high-density, MOS random-access memories (RAMs). Parallel test algorithms for RAMs have been developed on the basis of this design-for-testability approach for a broad class of pattern-sensitive faults. Two algorithms which are significantly more efficient than previous approaches are examined. The first algorithm detects the static and dynamic pattern-sensitive faults over a neighborhood of five cells. The second algorithm tests the symmetric pattern-sensitive faults over a neighborhood of nine cells. It tests an n-bit RAM organized as a square root n* square root n array in 97 square root n memory cycles. The design-for-testability approach modifies the existing RAM architecture very little, so that it can be implemented very easily. The additional overhead is only about 2 square root n transistors. The low overhead allows high reliability, and the additional circuit for each bit line can fit within the 3 lambda -to-6 lambda pitch width in a high-density, single-transistor dynamic RAM. Although the algorithm is designed to detect pattern-sensitive faults, the modified architecture can be readily used to speed up other conventional algorithms of linear complexity by a factor of O( square root n).>

The results of an extensive study of five existing testability measures when used to aid heuristics for automatic test pattern generation algorithms are presented. Each measure was evaluated using over 60000 faults in circuits of varying size and complexity. The performance of these measures was rated using several different criteria. Based on these results the performance of a composite test generation strategy that uses multiple guidance heuristics was evaluated. The results indicate that this strategy not only provides better fault coverage but also reduces the average time taken to generate a test or determine that a given fault is undetectable.>

The problem of diagnosis and spare allocation for a random access memory (RAM) with coupling faults, utilizing spare rows and columns, is examined. It is shown that a coupling fault is repaired if its coupling cell is replaced by a spare row or its coupled cell is replaced by a spare row or column. By specifying both the coupled cell and coupling cell the amount of redundancy required to repair a given set of faults can be reduced. A diagnosis procedure is provided to locate stuck-at faults as well as coupling faults. A graph model is used to describe the repair of coupling faults, and a repair procedure is implemented to allocate rows and columns for repair.>

Currently available automatic test pattern generators (ATPGs) generate test sets that are nonoptimal in length. The authors describe novel heuristic techniques to reduce the length of the test set for a sequential circuit by compaction of the automatically generated patterns. Based on these techniques, a program has been written in C that achieved a 56%-73% reduction in the test length of a highly sequential circuit obtained from industry.>

The availability of low-cost, high-performance, general-purpose parallel machines has made parallel processing viable for the development of CAD (computer-aided design) applications. The authors identify the key issues that surface when an attempt is made to parallelize the test-generation process. They illustrate how different test-generation strategies can be mapped onto different classes of parallel machines, including loosely coupled distributed systems, distributed-memory systems with message-passing architectures, and tightly coupled multiprocessor systems with shared global memory. Parallel test generation using a single heuristic and using multiple heuristics is considered. The performance of these mapping strategies is predicted by using uniprocessor turnaround times and an estimate of the communication delays.>

Several different local memory organizations applicable for single-chip processors are compared. Several cache types-instruction, data, split, unified, stack, and top-of-stack-are considered. These are compared to multiple-register-set architectures to which various caches can also be added. The performance metric of interest is effective access time, since a wide variety of register and cache organizations are used. A model for access time and a model for chip area required for each organization form the basis for comparison. Extensive simulations of several register-memory organizations are presented. Address traces from a VAX-11/780 running systems programs were used in the simulation. The data indicate that for small area (600 bytes), split or unified instruction and data caches are best. Context switch effects were measured and found to be negligible for small- and medium-size caches.>

Trace-driven simulation is a simple way of evaluating cache memory systems with varying hardware parameters. But to evaluate realistic workloads, simulating even a few million addresses is not adequate and such large scale simulation is impractical from the consideration of space and time requirements. New methods of simulation based on statistical techniques are proposed for decreasing the need for large trace measurements and for predicting true program behavior. In the method, sampling techniques are applied while collecting the address trace from a workload. This drastically reduces the space and time needed to collect the trace. New simulation techniques are developed to use the sample data not only to predict the mean miss rate of the cache, but also to provide an empirical estimate of its actual distribution. Finally, a new concept of primed cache is introduced to simulate large caches by the sampling-based method.>

A design strategy is presented for efficient and comprehensive testing when the address, data, and bit lines are not externally controllable or observable. Three algorithms are developed for testing common functional faults in content-addressable memories. One provides a novel method for detecting pattern-sensitive faults over a neighborhood size of nine and thereby tests a w-word content addressable memory in 33w+2b+64 operations, where b is the number of bits in a word. The algorithm is significantly more efficient than other embedded procedures for testing pattern-sensitive faults. Two additional simple algorithms are given for testing embedded content-addressable memories for stuck-at and adjacent-cell coupling faults.>

Given a combinational network and a specific stuck-at fault to be detected, there are several approaches to generating a test vector. However, most of these approaches fail to exploit the hierarchy inherent in any complex digital design. This paper presents a hierarchical approach to test vector generation. HIPODEM: A test generation system based on this approach is presented. General procedures to perform forward implication and backtracing in a hierarchical framework are discussed in detail. Experimental results obtained from test runs on both flat-level and hierarchical circuits are compared. For the circuits tried, generating tests from a hierarchical description proved to be faster than doing it from a flat level description of the circuit.

This paper presents a design strategy for efficient and comprehensive parallel testing of both Random Access Memory (RAM) and Content Addressable Memory (CAM). Based on this design for testability approach, parallel testing algorithms for CAMs and RAMs are developed for a broad class of pattern sensitive faults. The resulting test procedures are significantly more efficient than previous approaches. For example, the design for testability strategy allows an entire w word CAM to be read in just one operation with a resulting speed up in testing as high as w. In the case of an n bit RAM, the improvement in test efficiency is by a factor of Ο(√n). The overall reduction in testing time is considerable for large size memories.

In this paper a DEC VAX with multiple register sets is evaluated under many differently sized register sets. Both the number of register sets and the number of registers per set were varied. Performance, measured in terms of memory traffic, is compared to that of a standard VAX. Memory traffic is measured from many real program traces on the standard processor and from transformations of the trace for the multiple register set processors. Results are presented for each program; an empirical formula is derived which describes the average program's behavior. A decrease in memory references of approximately 16% can be expected using multiple register sets.

Previous papers have shown that a ripple carry adder composed of several full adder cells can be completely tested by a minimum test set of size 8 independent of the number of cells in the ripple carry adder under single faulty cell assumption. The fault model assumed is that faults in a cell can change the cell behavior in any arbitrary way, as long as the cell remains a combinational circuit. In this paper, we assume that any number of cells can be faulty at any time. A minimum test set of size 11 which can detect arbitrary length ripple carry adders under this fault model is presented. For general (N, p) adders in which each cell is a p-bit adder, a minimum test set of size 3 × 22P − 1 is also presented.

The PODEM (path-oriented decision making) algorithm generates tests for single stuck-at faults in combinational circuits described at the gate level. Controllability and observability (C/O) values were used as heuristic measures in PODEM. The PODEM algorithm and five different methods of determining controllability and observability were implemented. An experiment was conducted to study the effectiveness of different controllability and observability measures for PODEM. Based on the experimental data a new strategy for test generation is discussed.

This paper presents empirical results on the performance of CD, a compiler directed memory management policy, and the Working Set policy in a multiprogramming system. A description of the multiprogramming model used in the experiments is also presented. The results show that CD outperforms WS in terms of fault rate, space time cost, and throughput characteristics. Moreover, WS is shown to lack controllability. Two anomaly types are reported in this paper, both of which are exhibited by WS but not by CD.

Incremental and parallel garbage collection schemes implemented via time-slicing on a serial processor incur substantial overhead which is directly translated as reduced execution efficiency for the user and which might even be aggravated due to context switching.It is useful, therefore, to examine the possibility of implementing a parallel garbage collection algorithm using a separate processor operating asynchronously with the main list processor.The overhead in such a scheme arises from the synchronization necessary to manage the two processors, maintaining memory consistency.In this paper, we present an architecture and supporting parallel garbage collection algorithms designed for a virtual memory system wlth separate processors for list processing and for garbage collection.Each processor has its own primary memory; in addition, there is a small common memory which both processors may access.Individual memories swap off a common secondary memory, but no locking mechanism is required.In particular, a page may reside in both memories simultaneously, and indeed may be accessed and modified freely by each proce~.or.A secondary memory controller ensures consistency without necessitating numerous lockouts on the pages.

article Free Access Share on An efficient LISP-execution architecture with a new representation for list structures Authors: Gurindar S. Sohi Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, ILView Profile , Edward S. Davidson Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, ILView Profile , Janak H. Patel Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, ILView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 91–98https://doi.org/10.1145/327070.327136Published:01 June 1985Publication History 7citation319DownloadsMetricsTotal Citations7Total Downloads319Last 12 Months17Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A Compiler Directed Memory Management Policy for numerical programs is described in this paper.The high level source codes of numerical programs contain useful information which can be used by a compiler to determine the memory requirements of a program.Using this information, the compiler can insert some directives into the operating system for effective management of the memory hierarchy.During the program's execution the operating system dynamically allocates to a program the space it requires as specified by the received directive.The new policy is compared with LRU and WS policies.Empirical results presented in this paper sliow that the CD policy can out-perform LRU and WS by a wide margin.

This paper presents a cache coherence solution for multiprocessors organized around a single time-shared bus. The solution aims at reducing bus traffic and hence bus wait time. This in turn increases the overall processor utilization. Unlike most traditional high-performance coherence solutions, this solution does not use any global tables. Furthermore, this coherence scheme is modular and easily extensible, requiring no modification of cache modules to add more processors to a system. The performance of this scheme is evaluated by using an approximate analysis method. It is shown that the performance of this scheme is closely tied with the miss ratio and the amount of sharing between processors.

Shared-cache memory organizations for parallel-pipelined multiple instruction stream processors avoid the cache coherence problem of private caches by sharing single copies of common blocks. A shared cache may have a higher hit ratio, but suffers performance degradation due to access conflicts.

A method proposed for concurrent error detection in ALU's is used in the design of multiplier and divider arrays. This method, called recomputing with shifted operands (RESO), can detect all errors caused by failures confined to a cell of the cellular array. The assumption that the failures are confined to a small area of an integrated circuit and the precise nature of the failures is not known is very applicable to VLSI circuits. RESO uses time redundancy for error detection and requires only a small increase in the hardware of a multiply and divide array.

Cache memory organization for parallel-pipelined multiprocessor systems is evaluated. Private caches have a cache coherence problem. A shared cache avoids this problem and can attain a higher hit ratio due to sharing of single copies of common blocks and dynamic allocation of cache space among the processes. However, a shared cache suffers performance degradation due to access conflicts.

This paper presents an approximate analytical model for the performance of multiprocessors with private cache memories and a single shared main memory. The accuracy of the model is compared with simulation results and is found to be very good over a broad range of parameters. The parameters of the model are the size of the multiprocessor, the size and type of the interconnection network, the cache miss-ratio, and the cache block transfer time. The analysis is extended to include several different read/write policies such as write-through, load-through, and buffered write-back. The analytical technique presented is also applicable to the performance of interconnection networks under block transfer mode.

A new method of concurrent error detection in the Arithmetic and Logic Units (ALU's) is proposed. This method, called "Recomputing with Shifted Operands" (RESO), can detect errors in both the arithmetic and logic operations. RESO uses the principle of time redundancy in detecting the errors and achieves its error detection capability through the use of the already existing replicated hardware in the form of identical bit slices. It is shown that for most practical ALU implementations, including the carry-lookahead adders, the RESO technique will detect all errors caused by faults in a bit-slice or a specific subcircuit of the bit slice. The fault model used is more general than the commonly assumed stuck-at fault model. Our fault model assumes that the faults are confined to a small area of the circuit and that the precise nature of the faults is not known. This model is very appropriate for the VLSI circuits.

Synchronous N-processor systems with M shared memories are considered. Memory interference is modeled for processor request rates between 0 and 1 per memory cycle. Two probability-based models and one queueing-based model are summarized from prior literature. A new steady-state flow model is introduced. This steady-state model is most accurate overall. The queueing model is somewhat more accurate when request rate is near 1, and M and N are large. Accuracy is established with respect to probabilistic simulation. Additional related models are described.

A class of interconnection networks based on some existing permutation networks is described with applications to processor to memory communication in multiprocessing systems. These networks, termed delta networks, allow a direct link between any processor to any memory module. The delta networks and full crossbars are analyzed with respect to their effective bandwidth and cost. The analysis shows that delta networks have a far better performance per cost than crossbars in large multiprocessing systems.

An alternative multiple processor organization to the distributed pipeline (DP) [1] is presented. It is shown that the proposed organization is superior to the DP in every respect.

A new class of interconnection networks is proposed for processor to memory communication in multiprocessing systems. These networks allow a direct link between any processor to any memory module. The cost of these networks is considerably less than that of full crossbars. Moreover, the design and control of these networks is simple. The proposed networks and the full crossbars are analyzed with respect to the bandwidth and the cost.

Concurrent or overlapped processing of more than one task is a common technique used in many computer architectures to increase the throughput. A pipeline is one such form consisting of a set of hardware segments which can be operated in an overlapped fashion. The existing and many proposed pipelines assume that a task must flow synchronously, without wait or preemption, from segment to segment for its execution. In this paper we propose a pipeline model in which priority buffers are provided at every segment to control the flow of tasks. Several different priority implementations are analyzed assuming periodic arrivals of tasks. The characteristics studied are, queue size, wait time and throughput. It is shown that the theoretical maximum throughput of a pipeline is attainable with the use of internal buffers. Moreover, it is shown that a substantial degree of freedom in scheduling of tasks is achieved by these methods.

A pipeline is defined to be a collection of resources, called segments which can be kept busy simultaneously. A task once initiated, flows from segment to segment for its execution. A collision occurs if two or more tasks attempt to use the same segment at the same time.