Maximum-length sequences of length 2 n − 1 (m-sequences) are typically obtained by starting from a primitive polynomial of degree n over G F ( 2 ) and configuring a Linear Feedback Shift Register (LFSR) based on that polynomial. In this study, we investigate the generation of long m-sequences based on a primitive polynomial of low degree. Specifically, we investigate a very simple form of an LFSR structure, referred to as Two-Multiplier Split LFSR (2M-SLFSR) , that consists of m δ -bit cells and is based on a single low-degree primitive polynomial of degree δ ≥ 2 over G F ( 2 ) and which can generate, with proper configuration, an m-sequence of length 2 m δ − 1 . For example, we show that starting from the primitive polynomial x 2 + x + 1 over G F ( 2 ) , a 2M-SLFSR with m = 599 2-bit cells can be constructed that yields an m-sequence of length 2 1198 − 1 . M-sequences of large length such as 2 512 − 1 obtained from low degree primitive polynomials via LFSR structures akin to 2M-SLFSR find current applications in stream ciphers like those used in SNOW-V and SNOW-Vi.

We propose a novel transistor-level synthesis method to minimize the number of transistors needed to implement a digital circuit. In contrast with traditional standard cell design methods or transistor-level synthesis methods based on single-input “complex” gates or “super” gates, our method considers multioutput clusters as the basic resynthesis unit. Our tool takes any gate-level circuit netlist as input and divides it into several clusters of user-controlled size. For each output of a cluster, a simplified sum of product (SOP) expression is obtained and all such expressions are jointly minimized for the cluster using the MOTO-X multioutput transistor-level synthesis tool. Then, we consider groups of clusters, referred to as “superclusters,” to collectively reduce the overall transistor count. Experimental results indicate average transistor count reductions compared to the ABC synthesis tool of 9.95%, 6.53%, 10.49%, 13.09%, and 9.76% for the ISCAS’85, LGSynth’89, LGSynth’91, EPFL’15 and ITC’99 benchmark suites, respectively. Furthermore, our proposed approach proves to be more efficient than the transistor-mapped binary decision diagram approach, highlighting the potential of our methodology for optimizing integrated circuits at the transistor-level while delivering enhancements in power efficiency and demonstrating varied improvements in delay performance.

Designing systems for optimal reliability with minimum cost represents a significant challenge. We consider a standby system that includes a main component that can be fully repaired every time it fails, with the repair taking either a fixed amount of time or an exponentially distributed amount of time, and a standby component activated only during the main component’s repair. Utilizing the Interior-Point Method for Nonlinear Optimization, we propose an optimization framework to find the optimal configuration in terms of the lifetimes of the components and the repair time, in order to minimize the cost required to achieve any desired target reliability level by any desired time. The proposed optimization framework aids also designers and decision-makers in determining the most favorable trade-off in optimal resource allocation for reliable systems.

We present a novel mathematical framework for computing the number of maintenance cycles of a system component [referred to as “noncritical” (NC)] until another reference system component [referred to as “critical” (CR)] fails for the first time. Whenever the NC component experiences a failure, it receives necessary corrective maintenance in terms of replacement or minimal repair, as long as the CR component is still in operation. The lifetime of the CR component is assumed to be independent of that of NC and the first failure of CR is assumed to mark the end of the cycle counting process. That is, the CR component is never correctively repaired but it can optionally be fully replaced in an opportunistic maintenance fashion every time the NC component fails. This study broadens the scope of existing renewal theory (whether standard or generalized) by computing the average number of renewals for the NC component within the limited lifetime of the CR component. Closed-form approximations for the proposed “bounded” renewal processes (BRPs) are also given. Simulation results on a variety of distributions for the component lifetimes, including actual distributions for components of wind turbines, show that the approximations follow closely the real processes. In addition, we demonstrate, using actual costs for replacement and repair of wind turbine components, the difference in maintenance cost estimation that the proposed BRPs make with respect to standard and generalized renewal theories, and exemplify the decision point for selecting a particular BRP to minimize maintenance cost.

Modern Chip Multiprocessors (CMPs) are integrating an increasing amount of cores to address the continually growing demand for high-application performance. The cores of a CMP share several components of the memory hierarchy, such as Last-Level Cache (LLC) and main memory. This allows for considerable gains in multithreaded applications while also helping to maintain architectural simplicity. However, sharing resources can also result in performance bottleneck due to contention among concurrently executing applications. In this work, we formulate a fine-grained application characterization methodology that leverages Performance Monitoring Counters (PMCs) and Cache Monitoring Technology (CMT) in Intel processors. We utilize this characterization methodology to develop two contention-aware scheduling policies, one static and one dynamic , that co-schedule applications based on their resource-interference profiles. Our approach focuses on minimizing contention on both the main-memory bandwidth and the LLC by monitoring the pressure that each application inflicts on these resources. We achieve performance benefits for diverse workloads, outperforming Linux and three state-of-the-art contention-aware schedulers in terms of system throughput and fairness for both single and multithreaded workloads. Compared with Linux, our policy achieves up to 16% greater throughput for single-threaded and up to 40% greater throughput for multithreaded applications. Additionally, the policies increase fairness by up to 65% for single-threaded and up to 130% for multithreaded ones.

The ideal benefit of parallelizing/multithreading a program is diminished in practice by several factors such as hardware scaling, memory bandwidth, power constraints, and synchronization due to critical sections. Several models have been proposed in the past to estimate the resulting performance and extend the traditional Amdahl’s law. In this work, we focus on the effect of synchronization, and develop a model for the execution time estimation of multithreaded programs under the presence of critical sections. The proposed model is applicable to multiple different critical sections and generalizes and improves previously proposed models. Experimental results on simulated, synthetic and benchmark examples show that the proposed model provides accurate approximations.

BACKGROUND: The Top Scoring Pair (TSP) classifier, based on the concept of relative ranking reversals in the expressions of pairs of genes, has been proposed as a simple, accurate, and easily interpretable decision rule for classification and class prediction of gene expression profiles. The idea that differences in gene expression ranking are associated with presence or absence of disease is compelling and has strong biological plausibility. Nevertheless, the TSP formulation ignores significant available information which can improve classification accuracy and is vulnerable to selecting genes which do not have differential expression in the two conditions ("pivot" genes). RESULTS: We introduce the AUCTSP classifier as an alternative rank-based estimator of the magnitude of the ranking reversals involved in the original TSP. The proposed estimator is based on the Area Under the Receiver Operating Characteristic (ROC) Curve (AUC) and as such, takes into account the separation of the entire distribution of gene expression levels in gene pairs under the conditions considered, as opposed to comparing gene rankings within individual subjects as in the original TSP formulation. Through extensive simulations and case studies involving classification in ovarian, leukemia, colon, breast and prostate cancers and diffuse large b-cell lymphoma, we show the superiority of the proposed approach in terms of improving classification accuracy, avoiding overfitting and being less prone to selecting non-informative (pivot) genes. CONCLUSIONS: The proposed AUCTSP is a simple yet reliable and robust rank-based classifier for gene expression classification. While the AUCTSP works by the same principle as TSP, its ability to determine the top scoring gene pair based on the relative rankings of two marker genes across all subjects as opposed to each individual subject results in significant performance gains in classification accuracy. In addition, the proposed method tends to avoid selection of non-informative (pivot) genes as members of the top-scoring pair.

In built-in test pattern generation and test set compression, an LFSR is usually employed as the on-chip generator with an arbitrarily selected characteristic polynomial of degree equal, according to a popular rule, to$S_\mathrm{ max}+20$, where$S_\mathrm{ max}$is the maximum number of specified bits in any test cube of the test set. By fixing the polynomial a priori a linear system only needs to be solved to compute the required LFSR initial states (seeds) to generate the target test cubes, but the disadvantage is that the polynomial degree (length of the LFSR and seed bit size) may be too large and the fault coverage cannot be guaranteed. In this paper we address the problem of computing a polynomial of small degree directly from the given test set without having to solve multiple non-linear systems and fixing a priori the polynomial degree. The proposed method uses an adaptation of the Berlekamp-Massey algorithm and the Sidorenko-Bossert theorem to perform the computation. In addition, the method guarantees (by design) that all the test cubes in the given test set are generated, thereby achieving 100% coverage, which cannot be guaranteed under the “trial-and-error”$S_\mathrm{ max}+20$rule. Experimental results verify the advantages that the proposed methodology offers in terms of reduced polynomial degree and 100% coverage.

Transistor count minimization is an important goal as very-large-scale integration technology approaches its technical and physical limits. In this paper, we present a computer-aided design synthesis tool that tries to minimize the number of transistors required to implement a given multiple-output logic function. The proposed transistor-level synthesis approach goes beyond the traditional series-parallel design style and allows for extensive bridging. It starts from a sum-of-products expression for each output, allowing also for don't care terms, and produces a transistor network with a small number of transistors to implement all outputs jointly under a user-specified bound on the number of transistors in series to avoid long charge/discharge paths. Experimental results on previously examined multioutput functions and case studies (full adder, Gray/binary counter, and seven-segment display) demonstrate the benefit of the approach.

In this paper we present a new search method for test set embedding using an accumulator driven with an additive constant C. We formulate the problem of finding the location of a test pattern in the generated sequence in terms of a linear Diophantine equation with two variables, which is known to be solved quickly in linear time. We show that only one Diophantine equation needs to be solved per test set irrespective of its size. Next we show how to find the starting state, for a given constant C and test set T, such that the generated sequence can reproduce T with minimum length. Finally, we show that the best constant Copt(in terms of shortest test length) for the embedding of T using an accumulator of size n can be found in O(2ldrn+Fldr|T|) steps, instead of O(nldr2nldr|T|) steps of a previous approach, where F depends on the particular test set and can be significantly smaller than its worst case value of 2n-2. The value of F can also be further reduced while providing a guaranteed approximation bound of the shortest test length. Experimental results show the computational improvements.

We propose a built-in scheme for generating all patterns of a given deterministic test set T. The scheme is based on grouping the columns of T, so that in each group of columns the number riof unique representatives (row subvectors) as well as their product R over all such groups is kept at a minimum. The representatives of each group (segment) are then generated by a small finite state machine (FSM) with log2riflip-flops. As all FSMs run through their states, all patterns of T are generated in time R. Experimental results show that with appropriate filling of the don't cares to reduce the number of representatives in each segment, and with the use of standard sequential synthesis tools, the scheme can offer low hardware overhead as well as low number R of test cycles.

Linear finite-state machines (LFSMs) such as linear feedback shift registers (LFSRs), cellular automata (CA), and ring generators (RGs) are used as test pattern generators in built-in self-test schemes that employ 2-D scan design. These mechanisms are usually accompanied by phase shifters (PSs) in order to avoid the degradation of the fault coverage caused by correlations/dependences in the produced test bit sequences. Given this context, we investigate in this paper the potential of generalized (or Galois) LFSRs (GLFSRs) as onboard test pattern generators. We compare GLFSRs with and without PSs against LFSMs with PSs (LFSM/PSs) for various types of LFSMs (LFSRs, CA, RGs, and dense RGs) on two accounts: channel separation and overall hardware cost. Experimental results show that GLFSRs achieve larger channel separation with lower hardware cost than LFSM/PS and attain higher fault coverage.

We propose an innovative scheme for LFSR re- seeding based on the efficient generation of the seeds of any non-primitive irreducible polynomial. The scheme has very small hardware overhead irrespective of the number of seeds and guarantees that the generation of the pattern subsequence from each seed is disjoint. Experimental results demonstrate the potential of the mechanism for pseudorandom test pattern generation in a parallel chain test-per-scan environment.

In built-in 2D test pattern generation, parallel scan chains are driven by successive stages of a TPG mechanism. The bit sequences received by the scan chains are shifted versions of one another by different numbers of bit positions known as phaseshifts. Small phaseshifts impact negatively the fault coverage, and in order to alleviate this problem, the use of additional hardware overhead in terms of multi-input XOR gates (phaseshifters) has been proposed in the literature to impose large phaseshifts. In this paper we show that by simply permuting locally the stages of a cellular automaton and adding absolutely no other logic, large phaseshifts can be attained. In particular we show that scan chain i can be driven by an appropriate CA stage j, such that |j - i| les B and the minimum phaseshift between successive chains (channel separation) is maximized. The user-defined bound B controls the routing overhead. We have obtained large channel separations even for B = 2.

Two-dimensional scan design with a linear test pattern generator is a practical built-in self-test technique, but it suffers from linear dependencies, which reduce the fault coverage. To alleviate this problem, networks of xor gates known as phase shifters can be employed. Current techniques based on the empirical criterion of imposing large phase shift differences (channel separations) between successive scan chains cannot adequately remove the dependencies. In this paper, we present a method that addresses explicitly the minimization of linear dependencies through appropriate selection of phase shift values. The method is based on the criterion of minimizing the linear dependencies in each cone of the circuit under test, and is applicable to any type of linear test pattern generator, be it linear feedback shift register of the external- xor or internal-xor type, cellular automaton, etc. Experimental results demonstrate the effect of the approach in increasing fault coverage.

The number of transistors required for the implementation of a logic function is a fundamental consideration in digital VLSI design. While the determination of a series-parallel implementation can be straightforward once a simplified Boolean expression of the function is available, this may not be an optimum solution. In this paper, a methodology is developed for minimizing the number of transistors that starts from a sum-of-products expression and utilizes non-series-parallel structures. Experimental results demonstrate the efficiency of the approach

In this paper we show first that finding the location of a test vector in the sequence generated by an accumulator driven with an odd additive constant C is equivalent to the solution of a linear Diophantine equation with two variables. The latter equation is known to be solved fast in linear time. We then show that only one Diophantine equation needs to be solved per test set irrespective of the number of patterns in it. The finding of the locations of all patterns of a given test set T in the sequence generated under a constant C is done in O(n+ | T |) steps instead of O(n middot |T|) steps of a previous approach. Next we present a method which, given a test set T, and an odd constant C, finds the seed in the sequence generated under C that can reproduce all patterns of T in minimum length. We use this optimum technique to search for the best constant C' (in terms of short test length) in a randomly generated subset. Experimental results show the potential of the approach for test set embedding

Two-dimensional scan design is a widely used BIST architecture for pseudo-random and pseudo-exhaustive testing. However, linear dependencies that arise due to the properties of the test-pattern generators in use have a negative impact on fault coverage. To alleviate this problem, networks of XOR gates known as phase shifters are often used. Existing techniques for selecting phase shifts, such as those based on large channel separations, lead to inadequate removal of linear dependencies. In this paper we present for the first time a method for the selection of appropriate channel phase shifts to explicitly minimize linear dependencies. Experimental results corroborate the effect of the approach in increasing fault coverage

A flexible test architecture for embedded cores and all interconnects in a system-on chip (SOC) is presented. It targets core testing parallelism and reduced test application time by using, as much as possible, existing core interconnects to form TAM paths. It also provides for dynamic wrapper reconfiguration. Algorithms that minimize the use of extra interconnects for the TAM path formation are presented and evaluated.

Arithmetic-function modules, which are available in many circuits, can be utilized to generate test patterns and compact test responses. An accumulator-based scheme along with a procedure to find maximum-length nonlinear sequences for bit-serial test-pattern generators is proposed. The proposed scheme achieves good fault coverage with low hardware overhead and short test sequences

Using a simulation study we analyze the throughput performance of Yao's adaptive ARQ scheme in time-varying channels. The simulation takes into account the Rayleigh amplitude and the fast or the slow fading characteristics of a wireless channel, under a representative M-FSK modulation and Reed-Solomon coding scheme. We show that, for a specific set of design parameters, Yao's adaptive procedure works well for all channel fading rates, except for moderately slow rates. By observing variations of packet error rates at a specified SNR we provide an explanation for these varied behaviors under different channel fading rates.

This paper proposes a new test pattern generator (TPG) which is an enhancement of GLFSR (Galois LFSR). This design is based on certain non-binary error detecting codes, formulated over an extension field of GF(2/sup /spl delta//), /spl delta/ > 1. The resulting generator provides a guaranteed Hamming distance between successive test patterns, resulting in shorter test lengths. As an additional advantage, the proposed TPG has the intrinsic ability to detect 1-bit errors in the TPG itself. Detailed design methodology and experimental results are presented. The results presented here also have implications in algebraic coding theory in that they may lead to new coding techniques for test pattern generation.

In this paper, we investigate the use of Galois LFSRs (GLFSRs) as test pattern generators in BIST schemes that employ multiple scan chains. Current schemes use LFSRs or cellular automata (CA) with additional phase shifters to provide guaranteed minimum phase shifts between successive scan chains and also impose an upper bound on the number of taps for the XOR gate of each phase shifter. We compare CA with phase shifters (CAPSs) and GLFSRs without phase shifters in terms of the minimum inter-channel separation that they achieve and the overall XOR cost for each construction. Experimental results for different degrees show that GLFSRs are preferable in both hardware cost and fault coverage

Phase shifters are used to shift the bit sequences produced by the successive stages of a built-in test pattern generator (TPG) based on a linear finite state machine (LFSM) by a specified amount ( phase shift ) relative to the characteristic sequence. An upper bound on the number of taps to be used for each phase shifter and a lower bound on the phase-shift value between successive stages of the TPG mechanism are the general parameters of the problem. Methods to design such phase shifters have been given in the past separately for Type-1 LFSRs, Type-2 LFSRs, and three-neighborhood cellular automata. In this article, we show how phase shifters can be synthesized uniformly and efficiently for any LFSM, including the aforementioned ones. We demonstrate the method by showing how to obtain phase shifters for two-dimensional cellular automata and for ring generators.

A flexible test access mechanism (TAM) for embedded cores and their interconnects in a System-on Chip (SOC) environment is presented. It targets core testing parallelism and reduced test application time while explicitly taking into consideration area and performance issues. The TAM primarily uses core interconnects but also allows for extra interconnects. The DFT hardware can be implemented either at the SOC or at the core level. It combines features of TAMs that have been designed for low test application time and those for SOC area and performance criteria.

In this paper, we present built-in test pattern generation (TPG) mechanisms that can enforce a prescribed exact set of phaseshifts, or channel separations, on the bit sequences produced by their successive stages, while still requiring low hardware overhead. Such mechanisms are used in controlling the amount of correlations and/or linear dependencies that are problematic for pseudorandom and pseudoexhaustive TPG in a two-dimensional TPG architecture. The reduction in hardware overhead is achieved by a new technique that merges the logic of the original TPG mechanism with that of the required phase shifter network in order to yield an improved compact structure.

Linear feedback shift registers (LFSRs) are popular mechanisms for built-in test pattern generation (TPG). They are normally used with a primitive characteristic polynomial because, in that case, only one initialization state (seed) is required. We show that if the characteristic polynomial is nonprimitive irreducible, the required seeds can still be efficiently generated. We establish a formula that shows how the seeds of any nonprimitive irreducible polynomial relate to each other. This leads to an efficient hardware implementation with small hardware overhead, irrespective of the number of seeds, and enhances the choices available for the design of appropriate TPG structures in the case of pseudoexhaustive TPG that were previously limited to primitive characteristic polynomials only.

In this paper, the linear dependencies of extended linear finite state machines (LFSMs) used as test pattern generators (TPGs) are examined. The TPG mechanism considered is a shift register whose initial portion is configured as an LFSM. This mechanism (LFSM/SR) can be used for pseudorandom and circuit-specific pseudoexhaustive test pattern generation. A formula is presented that relates the linear dependencies that can occur among the LFSM/SR cells with the characteristic polynomial of the LFSM. Previously, such an easily computable formula had only been established for Type-1 linear feedback shift registers (LFSRs). The generalization allows the fast determination of linear dependencies for any LFSM, including in particular Type-2 LFSRs and cellular automata.

The problem of determining the exact number of path delay faults that a given test set detects in a combinational circuit is shown to be intractable. This result further strengthens the importance of several recently proposed pessimistic heuristics as well as exact exponential algorithms for this nonenumerative problem. A polynomial time pessimistic algorithm which returns higher coverage than algorithms with the same order of complexity and at the same time compacts the test set is also presented.

We propose an on-chip test pattern generator that uses an one-dimensional cellular automaton (CA) to generate either a precomputed sequence of test patterns or pairs of test patterns for path delay faults. To our knowledge, this is the first approach that guarantees successful on-chip generation of a given test pattern sequence (or a given test set for path delay faults) using a finite number of CA cells. Given a pair of columns (C u , C v ) of the test matrix, the proposed method uses alternative “link procedures” P j that compute the number of extra CA cells to enable the generation of (C u , C v ) by the CA. A systematic approach uses the link procedures to minimize the total number of needed CA cells. The performance of the scheme depends on an appropriate choice of link procedures P j .

Linear Feedback Shift Registers (LFSRs) are the most efficient and popular pseudo-exhaustive test pattern generation (TPG) mechanism. The goal is to minimize the required test length with low hardware overhead while obtaining pseudo-exhaustive TPG. Primitive characteristic polynomials are widely used because they require only one seed but the candidate polynomials are few and our experiments show that often the pseudoexhaustive test length is prohibitive. In this paper, we present a novel pseudoexhaustive approach with provably low number of seeds where the characteristic polynomial is the product of a primitive and an irreducible polynomial satisfying certain conditions. Our experimental results on the ISCAS'85 benchmarks show that using the proposed method requires very low hardware overhead. The list of characteristic polynomials for pseudoexhaustive TPG is greatly enhanced and our experiments show that pseudoexhaustive TPG is more feasible.

We propose two methods for embedding on-chip a given set of pairs of test patterns that have been generated by an arbitrary ATPG tool for path delay faults. The first method uses an LFSR with multiplexers. It applies to any set of test patterns and it is experimentally verified to have reasonable hardware overhead. The second method applies to the important special case of single input pattern changes within each pair and is very hardware overhead efficient.

We present a polynomial-time algorithm that finds the maximum weighted independent set of a transitive graph. The studied problem finds applications in a variety of VLSI contexts, including path delay fault testing, scheduling in high-level synthesis, and channel routing in physical design automation. The algorithm has been implemented and incorporated in a CAD tool for path delay fault testing. We experimentally verify its impact in the latter context.

We examine the problem of transmitting in minimum time a given amount of data between a source and a destination in a network with finite channel capacities and nonzero propagation delays. In the absence of delays, the problem has been shown to be solvable in polynomial time. In this paper, we show that the general problem is NP-complete. In addition, we examine transmissions along a single path, called the quickest path, and present algorithms for general and special classes of networks that improve upon previous approaches. The first dynamic algorithm for the quickest path problem is also given. © 1999 John Wiley & Sons, Inc. Networks 33: 167–174, 1999

Counter-based mechanisms have been proposed for use in built-in test set embedding. A single counter or multiple counters may be used with one or multiple seeds. In addition, counters may be combined with ROM's. Each alternative design scenario introduces a difficult combinatorial optimization problem: minimization of the time required to reproduce the test patterns by an appropriate synthesis of the built-in test pattern generator. This paper presents fast synthesis techniques that result in almost optimal designs. For any given circuit, they efficiently determine whether counter-based schemes are applicable as built-in generators for a given circuit. The proposed techniques have been implemented and tested on the ISCAS'85 benchmarks. Comparative studies with a weighted random linear feedback shift register scheme show that counter-based designs may offer good hardware/time solutions.

We present a polynomial time algorithm that finds the maximum weighted independent set of a transitive graph. The studied problem finds applications in a variety of VLSI contexts, including path delay fault testing, scheduling in high level synthesis and channel routing in physical design automation. The algorithm has been implemented and incorporated in a CAD tool for path delay fault testing. We experimentally verify its impact in the latter context.

A recent method proposed that a lower bound on the number of path delay faults excited by a given test set can be computed using a set independent lines that form a cut. For each line in the cut a subcircuit consisting of all paths that contain the line is defined, and a lower bound to the number of excited path delay faults can be obtained by working on the respective subcircuits. A polynomial time algorithm is presented here for computing the maximum cardinality set of independent circuit lines. Experimental results show that the more the subcircuits the better the lower bound on the number of excited path delay faults is. More subcircuits may be generated only in a heuristic manner. It was proposed to consider two or more line-disjoint cuts C/sub i/. We propose a technique where only one C/sub i/ must be a cut. This scheme is based on novel algorithms, and results in more subcircuits than the previous one.

Nonenumerative path-delay fault coverage estimation for combinational circuits estimates the fault coverage of a given test set without explicit enumeration of all paths in the circuit. In a recent nonenumerative method, it was proposed that a set C of lines be located in the circuit so that the set forms a cut and no lines in the set belong to the same path. Each line in the cut defines a subcircuit consisting of all paths that contain the line. Fault coverage may be obtained by working on all the subcircuits without double-counting path-delay faults. The main result of this paper is a polynomial time algorithm for finding a maximum cardinality set C. Besides its theoretical importance, our extensive experimental results on the ISCAS'85 benchmarks show that the larger the set C (and the number of subcircuits), the better the fault coverage estimation. More subcircuits may be generated only in a heuristic manner. It was proposed to consider two or more line-disjoint cuts C/sub i/. We propose a technique where only one C/sub i/ must be a cut. This scheme is based on novel algorithms and results in more subcircuits than the previous one.

Several mechanisms based on ROMs, LFSRs, counters, cellular automata, have been proposed as built-in test pattern generators with trade-offs between hardware and time overhead. This paper presents and analyses a scheme based on a counter with multiple seeds to generate a test set with low hardware overhead. A fast CAD tool determines the number of clock cycles required for the test set generation and this number is shown to be close to the best possible. A comparison to other existing approaches on the ISCAS'85 benchmarks shows that the proposed mechanism can offer a favorable hardware/time overhead for many circuits.

We study the behavior of counter-based schemes as very low hardware overhead built-in mechanisms for reproducing unordered test patterns. We show that a small number of seeds, each defining a test pattern generation session, can result in an economical design in terms of both time and hardware. We present counter-based schemes with a trade-off on the time and hardware overhead. Experimental results on the ISCAS'85 benchmarks and comparisons with other built-in mechanisms show that the proposed schemes constitute a promising technique for effective built-in deterministic test pattern generation.

A generally effective criterion for the selection of flip-flops in the partial scan problem for sequential circuit testability is to select flip-flops that break the cyclic structure of the circuit and reduce its sequential depth. The selection of flip-flops may also be subject to a prescribed bound on the clock period of the modified circuit (timing-driven partial scan). In this paper we propose two techniques (for non-timing-driven and timing-driven partial scan) which address the above criterion based on a transformation of sequential circuits known as retiming. For non-timing-driven partial scan, we employ retiming to rearrange the flip-flops of the circuit, so that its functionality is preserved, while the number of flip-flops that are needed to break all cycles and bound the sequential depth is significantly reduced. For timing-driven partial scan, we propose a retiming-based technique that reduces the overall area overhead required to achieve the clock period bound. Experimental results on the ISCAS'89 circuits show the benefit of our approach in both timing-driven and non-timing-driven partial scan.

We propose a very simple and fast CAD tool to check whether a binary counter can reproduce a predetermined set of test patterns in a reasonable time. Given a test matrix T, the tool uses column merging, complementation, and permutation so that the distance between the starting and the finishing vector of the corresponding counter is minimized. The hardware overhead of the proposed approach is by far lower than that of any other existing approach. Although it is computationally difficult (NP-hard) to obtain the absolute minimum distance, we present an algorithm which in the absence of don't cares in the test matrix, finds an appropriate column merging, complementation, and permutation that guarantees the distance is never more than twice as large as the best possible. In the presence of don't cares, the latter algorithm forms the basis of a powerful heuristic. Experiments on various test sets on benchmark circuits show that the exact number of clock cycles needed for a binary counter to reproduce all the patterns for the hard-to-detect faults compares favorably with the expected number yielded by existing Weighted Random LFSR-based approaches which have significantly higher hardware overhead.

We present a quadratic-time algorithm for minimizing the number of modules in an FPGA with combinational and sequential modules (like the C-modules and S-modules of the ACT2 and ACT3 architectures). The constraint is that a combinational module can be combined with one flip-flop in a single sequential module, only if the combinational module drives no other combinational modules. Our algorithm uses a minimum-cost flow formulation to solve the problem with a significant time improvement over a previous approach that used a general linear program.

We address the issue of pseudo-exhaustive test pattern generation (TPG) for the built-in self-test (BIST) of sequential circuits. Let d be the sequential depth, and w be the input dependency limit. We use an LFSR/SR Test Pattern Generator and a small additional hardware overhead to automatically generate d/spl middot/2/sup w/ test patterns to test the circuit pseudo exhaustively or, alternatively, pseudo-randomly with less hardware overhead and extremely high fault coverage. Our scheme uses novel retiming algorithms and transforms the circuit to an equivalent (for test purposes) one by scanning a subset of flip-flops for breaking its cyclic structure, bounding the sequential depth, forcing the input dependency limit, balancing the circuit, and maintaining the clock period. We present the first polynomial time algorithm to bound the sequential depth of a circuit by retiming with minimum number of flip-flops and subject to a clock period bound. We also give a retiming-based polynomial time algorithm to balance a circuit by inserting a minimum number of bypass delay cells. Experimental results on the ISCAS'89 benchmarks indicate that our method outperforms a previously proposed approach, which not only does not provide for on-chip test pattern generation but also requires O(q/spl middot/f/spl middot/2/sup w/) test patterns, where q is the total number of primary or pseudo-primary outputs in the circuit and f is the total number of flip-flops.>

A very popular and established methodology for testing complex sequential circuits is to break the cyclic structure of the circuit by incorporating a minimum number of flip-flops into a partial scan register. The circuit can then be tested by applying sequences of test patterns or using techniques for testing combinational logic. In the former case, it is very important to minimize the sequential depth, i.e. the maximum number of flip-flops on any path from the inputs to the outputs. In the latter case, it is also necessary to balance the circuit, so that all paths between any pair of nodes have the same number of flip-flops. In this paper, we address the above goals using the sequential logic synthesis concept of retiming. We present polynomial-time algorithms that solve optimally the following problems: (i) minimization of the sequential depth of the circuit; (ii) minimization of the number of flip-flops in the circuit so that the sequential depth and the clock period are less than prescribed bounds; and (iii) minimization of the number of flip-flops that need to be inserted in the circuit so that it becomes balanced. These algorithms extend the areas where retiming can be successfully applied.>

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudo-exhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify a class of such polynomials which, by appropriate LFSR cell ordering, guarantees that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage.>

Test sets for built-in self-test (BIST) test pattern generation (TPG) are normally pseudorandom or truncated pseudoexhaustive. In this work, the authors propose a pseudorandom TPG scheme which is based on the idea of ordering appropriately the cells of a linear feedback shift register (LFSR) in order to control the percentage of linear dependencies in the generated patterns. The LFSR cell ordering is done prior to the circuit's layout phase, in accordance with the design for testability principles. The proposed pseudorandom scheme compares favorably with the use of truncated pseudoexhaustive test sets with or without cell reordering.>

In order for pseudo-exhaustive test pattern generation to be practical (time requirement less than 2/sup /spl omega//, /spl omega//spl les/20), two conditions must be satisfied: 1). The function of every element in the circuit must be controllable from no more than /spl omega/ inputs, and 2). The overall time to exercise all elements in the circuit must not exceed 2/sup /spl omega//. We address both these requirements by inserting a small number of bypass storage cells in the circuit under test and constructing appropriate Linear Feedback Shift Registers (LFSRs) to serve as built-in test pattern generators. Our method is applicable to both the gate-level and the module-level and achieves low hardware overhead by using a new graph model for the representation of the circuit and a metric quantity that couples requirements 1 and 2 above.>

A generally effective approach to the partial scan problem is to select flip-flops that break the cyclic structure of the circuit.A large number of techniques are based on this framework but they are all static, in the sense that the fllp-flops remain fixed on their original positions.In this paper, we present a method that rearranges the D flip-flops of a synchronous sequential circuit by retiming, so that the overhead of partial scan is minimized.Experiments on IS CAS'89 circuits show that retiming irnproves significantly both non-timing-driven and timing-driven partial scan.

We present a method that can be used to test a sequential circuit pseudoexhaustively or almost pseudoexhaustively using LFSR/SRs as ATPGs with d-2/sup w/ test patterns, where d is the sequential depth and w is the input dependency limit. Our approach is based on the following techniques: (1) Use of LFSR/SRs as ATPGs (2) Rearrangement of the flip-flops of the circuit by retiming so that the hardware overhead for breaking all cycles and bounding the sequential depth is minimized. (3) Introduction of bypass storage cells (BSCs) so that no combinational element in the circuit has input dependence greater than a user-defined constant w. (4) Introduction of bypass delay cells (BDCs) so that the graph becomes more easily balanced or approximately balanced. Comparative experimental results indicate that our method behaves better than full-scan. It also outperforms a previous approach which, not only does not provide for on-chip TPG, but also requires O(q-f-2/sup 2/) test patterns, where q is the total number of primary or pseudoprimary outputs in the circuit and f is the total number of flip-flops.>

The generation of pseudoexhaustive test sets for the built-in self-test (BIST) of combinational circuits is addressed, using as a test pattern generator a simple linear feedback register (LFSR), structure, known as LFSR/SR. It is shown that particular orderings of the LFSR cells can significantly reduce the test set size. In addition, it is shown that an LFSR/SK designed with a particular cell ordering and the allowance of a marginal number of additional cells guarantees pseudoexhaustive test sets of the minimum size 2/sup w/, where w is the maximum input dependency limit of the circuit under test. Extensive experimentation on benchmark circuits and comparisons with the hardware overhead of other methods indicate the advantage of this approach.>

A self-contained method with very low bypass storage cell (BSC) overhead is presented. The method uses a graph model to represent the circuit under test. This unifying model makes the method applicable to both the gate level and the module level. A non-necessarily-partitioning technique reduces the number of BSCs considerably.>