With the shrink of technology to the nanometer scale, network-on-chip (NOC) has become a reasonable solution for connecting many cores on a single chip. It suffers however from increasingly serious interconnect crosstalk effects, which constrain the overall performance of NOC systems. In this paper, a crosstalk tolerance method is proposed for reducing bus delay on NOC interconnects. Crosstalk-induced latency is predicted by analyzing the possible crosstalk effects of adjacent patterns stored in an NOC router. Transition times of selected bits are then adjusted to relieve these predicted crosstalk-induced effects. Experimental results on interconnects show that the proposed method can achieve the same bus delay reduction as the insertion of extra shielding wires into two adjacent wires, while the proposed method requires no extra wires. Compared with previous methods using a dual rail code, a crosstalk avoidance code, and/or a variable clock, the proposed approach provides a larger reduction of bus delay with less area overhead.

Abstract Domain testing is designed to detect domain errors that result from a small boundary shift in a path domain. Although many researchers have studied domain testing, automatic domain test data generation for string predicates has seldom been explored. This paper presents a novel approach for the automatic generation ofON–OFFtest points for string predicate borders, and describes a corresponding test data generator. Our empirical work is conducted on a set of programs with string predicates, where extensive trials have been done for each string predicate, and the results are analysed using the SPSS tool. Conclusions are drawn that: (i) the approach is promising and effective; (ii) there is a strong linear relationship between the performance of the test generator and the length of target string in the predicate tested; and (iii) initial inputs, no shorter than the target string and with characters generated randomly, may enhance the performance in the test data generation for string predicates. Copyright © 2009 John Wiley & Sons, Ltd.

Hazards ubiquitously exist in combinational circuits, and then should be taken into account for delay testing. This paper analyzes the impact of hazards on small-delay defect (SDD) detection, and presents a new test pattern selection method considering hazards. The concept of arrival time window is introduced and the concept of output deviation is redefined to accurately reflect the pattern capability on SDD detection. A new signal transition probability calculation method is presented to calculate output deviation more practical than that without considering hazards. Patterns from an N-detect test set for transition faults are then selected according to their output deviations. Experimental results show that, for the same pattern count, the patterns selected by the proposed method excite more long paths, and are capable of detecting more small delay defects at the early stage of delay testing compared to the method without considering hazards.

Traffic metrics at application level are critical for protocol research, abnormity detection, accounting and network operation. There are great challenges to identify packets at application level since dynamic protocol ports and packet encryption are deployed popularly. There are several different methods of traffic identification being proposed in recently research for corresponding applications. It is impossible to identify traffic with any one method alone. A methodology of online traffic identification at application level named multi-phases identification (MPI) based on packet and flow is proposed in this paper. There are two stages in the methodology. The traffic classification is based on packet characteristic in the first stage and based on flow feature in the second stage to correct the results in the first stage. There are several advantages in MPI: (1) these existing traffic identification methods can be easily integrated into MPI to improve the identification accuracy, (2) the corresponding new identification method for the new application can be inserted into MPI feasibly with scripts of the identification rule, and (3) efficiency of identification can be improved with the mechanism of adaptive justification for the sequence of methods and implemented on multi-CPUs platform. MPI has been implemented a general purpose CPU platform with OC-48 POS and 10 GE network interface. Experiment on an OC-48 POS backbone link shows MPI is accurate and effective for traffic identification.

There is an increasing demand for test and diagnosis expertise in the global semiconductor industry, in sectors ranging from foundries to test houses, to IDM companies, and from fabless design houses to EDA companies. Test education, however remains a niche, highly specialized subject area in the graduate curriculum and is seldom covered in undergraduate classes. In this panel, we evaluate the current health of academic test education and debate the role and goals of future test education, as well as those changes that need to be made to meet the global market demands.

Bloom filters allow membership queries over sets with allowable errors. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. However, the false positive errors are unavoidable, and the false positive rate increases intolerantly along with the date set expanding. To solve the scalability problem of Bloom filters, this paper presents a new design of a scalable Bloom filter (SBF) for an expanding data set. The SBF keeps a low false positive rate by adding Bloom filter vectors with double length when necessary. The paper proposes algorithms for element insertion and query operation of SBF by employing the H3class of universal hash functions. Theoretical and experimental results demonstrate that the new SBF provides false positive rate as low as 21.3% of the dynamic Bloom filter presented before and the querying CPU time increasing with logarithmic rather than linear. Therefore, the proposed SBF outperforms other current scalable Bloom filters significantly.

To provide efficient rollback-recovery for fault-tolerance in distributed systems, it is significant to reduce the number of checkpoints under the existence of consistent global checkpoints in index-based distributed checkpointing algorithms. A new checkpointing scheme, IBQSC, is presented in this paper for index-based checkpointing. It reduces the number of forced-checkpoints when multiple processes transfer data almost equally frequently. It also keeps synchronous in case of some process with less opportunity to transfer data for them to avoid too much amount of overhead of rollback-recovery due to useful computation losing in case of failure. Simulation results show that the proposed IBQSC scheme can reduce the number of induced forced-checkpoints per message 25-30% on an average comparing to the traditional strategies.

We propose a new coding method of limited global fault information in an n-cube. First, each node collects precise fault information within distance-d, and then fault information about nodes that are more than distance-d away is coded in a special way. Specifically, in our approach, each node in a cube-based multicomputer of dimension n is associated with an extended safety vector of n bits. In the extended safety vector model, each node knows fault information within distance-2; fault information outside distance-2 is coded in a special way based on the coded information of its neighbors. The extended safety vector of each node can be easily calculated through n-1 rounds of information exchanges among neighboring nodes. Therefore, each extended safety vector is an approximated measure of the number & distribution of faults in the neighborhood. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source & destination nodes. In addition, the extended safety vector can be used as a navigation tool to direct a message to its destination through a minimal path. A simulation study has been conducted based on different selections of d, and results have shown a significant improvement under the proposed model over the safety vector model in handling link faults, even for a small value of d as in the extended safety vector model where d=2.

This paper proposes a scheme of at-speed current testing by applying two alternative vectors to circuits under test for a fault, to enable a slow measurement under a high frequency operation. The paper presents test generation of the two alternative vectors at gate level by means of counting only logical up-transitions based on a Boolean process, and employing the Bayesian optimization algorithm. SPICE simulation shows that the responses of tests generated by the algorithm can be observed either by a low-cost ATE or a waveform sensor.

Domain testing is a well-known software testing technique. Although research tasks have been initiated in domain testing, automatic test data generation based on character string predicates has not yet been reported. This paper presents a novel approach to automatically generate ON-OFF test points for character string predicate borders associated with program paths, and describes a corresponding test data generator control flow based testing Slices with respect to predicates on paths are constructed to calculate the current values of variables in the predicates via program slicing techniques. Each character element of variables in a character string predicate is dynamically determined in turn by function minimization so that the ON-OFF test points for the predicate border can be automatically generated. The preliminary experimental results show that this approach is promising and effective.

Partition testing is a well-known software testing technique. This paper shows that partition testing strategies are relatively ineffective in detecting faults related to small shifts in input domain boundary. We present an innovative software testing approach based on input domain analysis of specifications and programs, and propose the principle and procedure of boundary test case selection in functional domain and operational domain. The differences of the two domains are examined by analyzing the set of their boundary test cases. To automatically determine the operational domain of a program, the ADSOD system is prototyped. The system supports not only the determination of input domain of integer and real data types, but also non-numeric data types such as characters and enumerated types. It consists of several modules in finding illegal values of input variables with respect to specific expressions. We apply the new testing approach to some example studies. A preliminary evaluation on fault detection effectiveness and code coverage illustrates that the approach is highly effective in detecting faults due to small shifts in the input domain boundary, and is more economical in test case generation than the partition testing strategies.

Three efficient test power optimization algorithms for CMOS circuits are studied in this paper. First, for delay-fault test pattern sets of ISCAS89 benchmarks, this algorithm can cut down 37.5% or more test power than the simulation-based annealing algorithm. Second, because approaches which use the Hamming distance between two input test patterns, to optimize the test power, cannot reduce as much power for ISCAS85 benchmarks as expected, a novel optimization approach that uses the power of an ideal circuit without delay, to optimize the test power is presented. Experimental results demonstrate that our approach can cut down 70.8% more test power than present approaches. Third, the influence of undetermined test bits on test power optimization is studied by changing the number of undetermined bits in test patterns. Experimental results demonstrate that with the increase of undetermined test bits, the un-optimized test power markedly decreases.

This paper presents a new level of description between behavioral and state descriptions of a finite-state machine (FSM). The description is termed behavioral phase clustering description. New concepts of behavioral phase and clustering of behavioral phases in an FSM are introduced. The new description simplifies functional analysis, verification and test of FSM designs. If an FSM is described at low level, some states can be clustered into behavioral phases directly. If it is described at behavioral level, behavioral phases can be extracted from the behavioral description, and clustering of behavioral phases can be performed through easy functional analysis. As one application of behavioral phase clustering descriptions, a new technique employed in a test generation system, ATCLUB, at Register Transfer (RT)-level based on a behavioral phase transition fault model is introduced in this paper. In ATCLUB, test generation process is accelerated through clustering of behavioral phases. Experimental results show that ATCLUB generates test sequence efficiently, with a sharp decrease in vector count at the penalty of a slightly decrease in fault coverage comparing to other ATPG tools.

The authors theoretically describe the monotonic increasing relationship between average powers of a CMOS VLSI circuit with and without delay. The power of an ideal circuit without delay, which can be fast computed, has been used as the evaluation criterion for the power of a practical circuit with delay, which needs more computing time, in such fields as fast estimation for the average power and the maximum power, and fast optimization for the low test power. The authors propose a novel simulation approach that uses delay-free power to compact a long input vector pair sequence into a short sequence and then, uses the compacted one to fast simulate the average (or maximum) power for a CMOS circuit. In comparison with the traditional simulation approach that uses an un-compacted input sequence to simulate the average (or maximum) power, experiment results demonstrate that in the field of fast estimation for the average power, the present approach can be 6–10 times faster without significant loss in accuracy (less than 3.5% on average), and in the field of fast estimation for the maximum power, this approach can be 6–8 times faster without significant loss in accuracy (less than 5% on average). In the field of fast optimization for the test power, the authors propose a novel delay-free power optimization approach for the test power. Experiment results demonstrate that, in comparison with the approach of direct optimization and the approach of Hamming distance optimization, this approach is of the highest optimization efficiency because it needs shorter time (16.84%) to obtain a better optimization effect (reducing 35.11% test power).

This paper introduces a new technique employed in a test generation system, ATCLUB, at RT-level, based on clustering of circuit states. States or some sets of states in a low-level description are mapped to high levels in terms of a particular variable in a behavioral description, and termed behavioral phases. Further clustering of behavioral phases is performed to represent the function of a circuit more explicitly and refinedly. Such a refined representation is then used in the test generation algorithm to simplify and speed up search process of test sequences. Experimental results demonstrate the computational efficiency of the clustering process and test pattern generation.

The paper presents an approach to fault extraction and test generation at RTL (register transfer level). The proposed ATPG (automatic test pattern generation) is targeting to cover all the extracted faults rather than a specific fault, and based on simulation with unspecified inputs. It uses a request-echo strategy called X-Pulling to greatly reduce the unnecessary backtrack and implication, which makes the algorithm very efficient. Experimental results demonstrate that our approach is better than ARTIST in three aspects: on average, the CPU time is shorter by three orders of magnitude, the test length is shorter by 52% and the fault coverage is higher by 0.89%.

Built-in self-test (BIST) is considered to be one of the most promising approaches to testing modern ICs. This paper proposes an efficient BIST design using LFSR-ROM architecture. It takes advantage of don't-care bits that remain during the process of test pattern generation. It determines the target fault set with an ATPG tool to achieve predefined fault coverage. It compresses the size of ROM in two dimensions to reduce the number of test patterns and ROM outputs as well. Experimental results demonstrate that the proposed scheme is able to reduce hardware overhead several-fold.

High operation frequency and strict timing behavior are characteristics of modern high performance integrated circuits, which require a digital system simulator to accurately simulate not only the logic function but also the timing behavior of a circuit. This paper presents some experimental results by SPICE to validate the analytical approach of Boolean process, and extract some data for a numerical waveform simulation. The paper also presents a waveform simulator and its results of experiments, which is very different from traditional logic simulator.

Reliable communication in cube-based multicomputers using the extended safety vector concept is studied. Each node in a cube-based multicomputer of dimension n is assorted with an extended safety vector of n bits, which is an approximated measure of the number and distribution of faults in the neighborhood. In the extended safety vector model, each node knows fault information within distance-2 and fault information outside distance-2 is coded in a special way based on the coded information of its neighbors. The extended safety vector of each node can be easily calculated through n-1 rounds of information exchanges among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source and destination nodes. In addition, the extended safety vector can be used as a navigation tool to direct a message to its destination through a minimal path. Simulation results show a significant improvement in terms of optimal routing capability in a hypercube with faulty links using the proposed model, compared with the one using the original safety vector model.

This paper proposes a novel N-modular redundancy (NMR) structure with concurrent output error location (COEL) capability. The concurrent output error locatable NMR structure consists of a conventional NMR structure and a totally self-checking (TSC) extra circuit with N+1 two-rail code outputs. This extra circuit is used for locating the output error produced by any replicated module or the voter, and the internal fault produced by the extra circuit itself. Such a self-checking extra circuit is called the output error locator (OEL). It is constructed by conventional TSC two-rail code checkers (TRCs) and self-testing multi-input comparators. Each comparator is made by adding one extra two-rail code input to the cascaded multi-input comparator. The error handling capabilities, hardware complexity and propagation delay are analyzed for the proposed OEL. The performance of the proposed scheme and that of the Gaitanis's scheme are compared for a triple modular redundancy (TMR) structure.

Delay testing is important for high speed ICs. The main difficulty for delay testing comes from the huge number of paths and the large percentage of delay untestable paths. This paper presents an approach to delay testing with double observations, which provides a high path delay fault coverage by testing a small number of paths. But, for each test pair, it is necessary to sample the primary output twice, one before and another after the transition. The paper explains how to select the very limited number of paths, termed sample paths, and how to generate the test pair and the observation times for the sample paths. Furthermore, the number of sample paths is linear to the number of gates in the circuit under test, despite exponential growth in the number of single paths. Based on the analytical delay model, most of the paths are delay testable which makes the delay test generation easier than that based on single path sensitization.

In many designs a large portion of path delay faults is non-robustly untestable. This paper presents a new low-cost method for identifying non-robustly untestable path delay faults. Using an implication-based procedure, our method starts with a small number of path segments, called maximum fanout-free segments, to quickly locate lines which cannot construct non-robustly testable paths with them. After a large portion of faults is marked as untestable, only a small subset of faults remains for the ATPG procedure, which can effectively alleviate the problem of handling a huge number of path delay faults and reduce test generation time. Experimental results for ISCAS'85 benchmark circuits demonstrate that a significant portion of non-robustly untestable path delay faults was identified efficiently using our method. For most of these circuits, 90%-95% of non-robustly untestable path delay faults can be identified within a small amount of CPU time.

A memory efficient test pattern generator for path delay faults, DTPG, is presented in this paper, which uses the efficient path identifier to represent a path. A compact bit table, path information table, is proposed to store test information efficiently. Furthermore, DTPG is capable of identifying functional sensitizable paths, which account for large percent of paths in many circuits. The experimental results show that DTPG is memory efficient. It generates tests for C3540 with 57 million paths and preserves the testability information for all paths. Experimental results show the influence of stepwise mandatory sensitization, multiple backtrace, and backtracking limits on the cpu time consumed by delay test generation process.

The industry has accepted I/sub DDQ/ testing to detect CMOS IC defects. While I/sub DDT/ testing needs more research to be applicable in practice. However, it is noticed that observing the average transient current can lead to improvements in real defect coverage. This paper presents a formal procedure to identify I/sub DDT/ testable faults, and to generate input vector pairs to detect the faults based on Boolean process. It is interesting to note that those faults may not be detected by I/sub DDQ/ or other test methods, which shows the significance of I/sub DDT/ testing.

Correct operation of logic circuits requires not only the functional correctness, but also the correctness of temporal behavior. This paper deals with the problem of delay testability of two-level circuits through adding extra inputs. A design of delay-verifiable combinational logic by adding extra inputs is proposed, and a synthesis procedure is given. Experimental results show that the hardware overhead is about 1/3 of that of the methods proposed previously (1987, 1991), which aim at robust testable or VNR testable circuits. In fact, it is good enough to guarantee delay verifiability to satisfy the requirement of temporal correctness.

The paper presents an extension to OBDDs with timing information, called timed binary decision diagrams (TBDDs). TBDDs are also canonical and allow the symbolic manipulation of Boolean functions with timing information. A TBDD software package is implemented based on the existing CMU BDD package. Experimental results demonstrate the efficiency of the TBDDs in representing circuits with both functional and timing information.

This paper presents an efficient implication-based approach for identifying non-robustly untestable path delay faults. It starts from possible conflicts to find untestable faults by performing static implication. It is neither path-oriented nor space-search based. Experimental results for ISCAS'85 benchmark circuits demonstrate that a significant portion of non-robustly non-robustly untestable path delay faults is identified efficiently. The method can be combined easily with ATPG-based approaches for path delay testing to yield cost effective methods for path delay faults in large circuits.

A waveform polynomial for a digital circuit integrates both logic and timing information. It is applicable to design verification and test. This paper introduces a compact and manageable form, BPBDD, to represent and manipulate Boolean process based on BDDs, and shows how to construct a BPBDD representing a waveform polynomial for a given circuit. Experimental results show that BPBDD is capable of handling circuits of middle size efficiently. Although it is more complicated than OBDDs, more information about a circuit is available.

For pt. I see ibid. (1994). Incorporating performance factors in the physical and logical design of VLSI circuits is necessary for performance enhancement. Boolean process provides an analytical approach to circuit representation to precisely describe logical and timing behavior simultaneously. It allows input and output of circuits be described by waveform functions, which is consistant with common used intuitive waveforms. Waveform functions can be manipulated formally by using mathematical tools. This paper defines distance, difference and limit of waveform polynomials, and demonstrates that the concepts of sensitization and hazard should be redefined precisely when duration between input transitions is comparable to circuit delay. Based on these observations, many interesting results are driven.

Many ATPG algorithms are proposed every year. Evaluation of ATPG algorithms not only provides possibility to compare algorithms, but also predicts required computation resources for design and test of extra large circuits. The evaluation includes aspects of fault coverage, computation efficiency, and test set size. ISCAS 85 and ISCAS 89 benchmark circuits are available common examples for the evaluation. This paper presents a general methodology for the evaluation in spite of the difference of the computing environments that the algorithms run in. Eleven ATPG algorithms are evaluated, as a case study, based on the data of their experimental results published in the literature to show the feasibility and validation of the methodology presented.>

A rigorous mathematical analysis is presented to identify error conditions under which aliasing can occur for several common types of serial signature analyzers (SSAs) and parallel signature analyzers (PSAs). The PSAs are faster and require less hardware than the SSAs; however, for PSAs some double errors are a special cause of concern. Such aliasing errors are analyzed and it is shown that PSA pairs can be identified for which these errors are disjoint. Novel reconfigurable PSA designs are presented which use a two-signature scheme to detect all double errors.>

A general approach is presented to the design of totally self-checking (TSC) programmable logic arrays (PLAs). A strongly fault secure (SFS) implementation is suggested for the functional PLA, which is shown to be SFS whenever the output is encoded by two-rail code. K-unit TSC checker (TSCC) element are defined to construct TSC checkers. The TSCC is very appropriate for the companion of the SLF PLA since a given input codeword set is sufficient for testing the TSCC. The minimum number of tests needed for a type-m two-rail code K-unit TSCC is 12/sup m/. This is a generalization of the fact that four test patterns are sufficient for testing an XOB parity checker tree. As an application, a novel design of a TSC comparator with an arbitrary number of inputs is presented.>

Functional testing has become increasingly important due to the advent of VLSI technology. This paper presents a systematic procedure for generating tests for detecting functional faults in digital systems described by the register transfer language. Procedures for testing register decoding, instruction decoding, data transfer, data storage and data manipulation function faults in microprocessors are described step-by-step. Examples are given to illustrate the procedures.