2345381
Optimized reseeding by seed ordering and encoding
Mixed-mode logic built-in self-test (BIST) applies both pseudorandom test patterns and deterministic test patterns [from an automatic test pattern generation (ATPG) tool] to the combinational portion of the circuit under test. Each scan-test cycle consists of: 1) shifting a test pattern into the scan chains; 2) capturing the response to that pattern; and 3) shifting the captured response out of the scan chains. The shifting of the test pattern out of the scan chains is overlapped with shifting in the next test pattern. The pattern shifted into the scan chains comes from the output of the pseudorandom pattern generator (PRPG); this pattern is determined by the initial state or seed of the PRPG (the contents of the PRPG at the beginning of the shifting operation). In a pseudorandom cycle, the initial state is the final state (last PRPG contents) from the previous cycle. The initial state of a deterministic cycle is shifted into the PRPG either from an a tester or from an on-chip BIST controller. This paper describes techniques to minimize the number of deterministic seeds that must be used: the number of seeds determines the required storage either on the ATE or the chip being tested. These techniques interleave pseudorandom and deterministic cycles rather than first applying all of the pseudorandom cycles and then the deterministic cycles. The decision of when to change from a pseudorandom cycle to a deterministic cycle is made by comparing the final state of the pseudorandom cycle with previously generated ATPG patterns or by carrying out fault simulation on the final state. Which deterministic pattern is chosen for the deterministic cycle critically influences the remainder of the test. A methodology for doing this is described. In addition to interleaving test cycles, it is possible to use partial cycles in which the PRPG operates for a few clocks without loading the scan chains. This allows a new seed to be present without loading the seed from the ATE or controller. As might be suspected, this reduces the number of stored seeds at the penalty of more complexity in the control sequence. These techniques were simulated and compared with conventional reseeding for some ISCAS'89 benchmarks. Improvements varied between 25% and 85% in the required seed storage.
2705949
Logic soft errors in sub-65nm technologies design and CAD challenges
Logic soft errors are radiation induced transient errors in sequential elements (flip-flops and latches) and combinational logic. Robust enterprise platforms in sub-65nm technologies require designs with built-in logic soft error protection. Effective logic soft error protection requires solutions to the following three problems: (1) accurate soft error rate estimation for combinational logic networks; (2) automated estimation of system effects of logic soft errors, and identification of regions in a design that must be protected; and, (3) new cost-effective techniques for logic soft error protection, because classical fault-tolerance techniques are very expensive.
15807495
Application-independent testing of FPGA interconnects
We present a new automatic test-configuration-generation technique for application-independent manufacturing testing of the interconnection network of static-random-access-memory-based field programmable gate arrays (FPGAs). This technique targets detection of open and bridging faults in the wiring channels and programmable switches in the interconnects. Experimental results on Xilinx Virtex FPGAs show that very few test configurations are required to cover stuck-open, stuck-closed, open, and bridging faults in the interconnects.
2734062
A design diversity metric and reliability analysis for redundant systems
Design diversity has long been used to protect redundant systems against common-mode failures. The conventional notion of diversity relies on "independent" generation of "different" implementations. This concept is qualitative and does not provide a basis to compare the reliabilities of two diverse systems. In this paper, for the first time, we present a metric to quantify diversity among several designs. Based on this metric, we derive analytical reliability models that show a simple relationship between design diversity, system failure rate, and mission time. In addition, we present simulation results to demonstrate the effectiveness of design diversity in Duplex and Triple Modular Redundant (TMR) systems. For independent multiple-module failures, we show that, mere use of different implementations does not always guarantee higher reliability compared to redundant systems with identical implementations-it is important to analyze the reliability of redundant systems using our metric. For common-mode failures and design faults, there is a significant gain in using different implementations-however, as our analysis shows, the gain diminishes as the mission time increases. Our simulation results also demonstrate the usefulness of diversity for enhancing the self-testing properties of redundant systems.
2397835
Speed clustering of integrated circuits
Experimental data on 0.18 /spl mu/ test chips shows strong evidence of clustering of speeds of neighboring dies on a wafer. This clustering phenomenon is utilized to develop techniques for predicting the speed of a part from the speeds of three or more of its neighbors. On-chip processor monitors are used to further improve the prediction accuracy of these techniques. Experimental data demonstrates both the effectiveness of these prediction schemes and the possibility of applying of them to reduce the cost of speed binning.
900289
Techniques and algorithms for fault grading of FPGA interconnect test configurations
Conventional fault simulation techniques for field programmable gate arrays (FPGAs) are very complicated and time consuming. The alternative, FPGA fault emulation technique, is incomplete and can be used only after the FPGA chip is manufactured. In this paper, we present efficient algorithms for computing the fault coverage of a given FPGA test configuration. The faults considered are opens and shorts in FPGA interconnects. The presented technique is able to report all detectable and undetectable faults and, compared with conventional methods, is orders of magnitude faster.
2481844
Proving Atomicity: An Assertional Approach
Atomicity (or linearizability) is a commonly used consistency criterion for distributed services and objects. Although atomic object implementations are abundant, proving that algorithms achieve atomicity has turned out to be a challenging problem. In this paper, we initiate the study of systematic ways of verifying distributed implementations of atomic objects, beginning with read/write objects (registers). Our general approach is to replace the existing operational reasoning about events and partial orders with assertional reasoning about invariants and simulation relations. To this end, we define an abstract state machine that captures the atomicity property and prove correctness of the object implementations by establishing a simulation mapping between the implementation and the specification automata. We demonstrate the generality of our specification by showing that it is implemented by three different read/write register constructions: the message-passing register emulation of Attiya, Bar-Noy and Dolev, its optimized version based on real time, and the shared memory register construction of Vitanyi and Awerbuch. In addition, we show that a simplified version of our specification is implemented by a general atomic object construction based on the Lamport’s replicated state machine algorithm.
1158736
Specifying and proving properties of timed I/O automata in the TIOA toolkit
Timed I/O Automata (TIOA) is a mathematical framework for modeling and verification of distributed systems that involve discrete and continuous dynamics. TIOA can be used for example, to model a real-time software component controlling a physical process. The TIOA model is sufficiently general to subsume other models in use for timed systems. The TIOA toolkit, currently under development, is aimed at supporting system development based on TIOA specifications. The TIOA toolkit is an extension of the IOA toolkit, which provides a specification simulator, a code generator, and both model checking and theorem proving support for analyzing specifications. This paper focuses on modeling of timed systems with TIOA and the TAME-based theorem proving support provided in the toolkit, for proving system properties, including timing properties. Several examples are provided by way of illustration
15125333
Evolutionary modular design of rough knowledge-based network using fuzzy attributes
This article describes a way of integrating rough set theory with a fuzzy MLP using a modular evolutionary algorithm, for classification and rule generation in soft computing paradigm. The novelty of the method lies in applying rough set theory for extracting dependency rules directly from a real-valued attribute table consisting of fuzzy membership values. This helps in preserving all the class representative points in the dependency rules by adaptively applying a threshold that automatically takes care of the shape of membership functions. An l-class classification problem is split into l two-class problems. Crude subnetwork modules are initially encoded from the dependency rules. These subnetworks are then combined and the final network is evolved using a GA with restricted mutation operator which utilizes the knowledge of the modular structure already generated, for faster convergence. The GA tunes the fuzzification parameters, and network weight and structure simultaneously, by optimising a single fitness function. This methodology helps in imposing a structure on the weights, which results in a network more suitable for rule generation. Performance of the algorithm is compared with related techniques.
11380579
Bitmap indexes for large scientific data sets: a case study
The data used by today's scientific applications are often very high in dimensionality and staggering in size. These characteristics necessitate the use of a good multidimensional indexing strategy to provide efficient access to the data. Researchers have previously proposed the use of bitmap indexes for high-dimension scientific data as a way of overcoming the drawbacks of traditional multidimensional indexes such as R-trees and KD-trees, which are bulky and whose performance does not scale well as the number of dimensions increases. However, the techniques proposed in previous work on bitmap indexes are not sufficient to address all problems that arise in practice. In experiments with real datasets, we experienced problems with index size and query performance. To overcome these shortcomings, we propose the use of adaptive, multilevel, multi-resolution bitmap indexes, and evaluate their performance in two scientific domains. Our preliminary experiments with a parallel query processor and index creator also show that it is very easy to parallelize a bitmap index
9622081
Modular Rough Fuzzy MLP: Evolutionary Design
The article describes a way of designing a hybrid system for classification and rule generation, integrating rough set theory with a fuzzy MLP using an evolutionary algorithm. An l-class classification problem is split into l two-class problems. Crude subnetworks are initially obtained for each of these two-class problems via rough set theory. These subnetworks are then combined and the final network is evolved using a GA with restricted mutation operator which utilizes the knowledge of the modular structure already generated, for faster convergence.