To alleviate high energy dissipation of unnecessary snooping accesses, snoop filters have been designed to reduce snoop lookups. These filters have the problem of decreasing filtering efficiency, and thus usually rely on partial or whole filter reset by detecting block evictions. Unfortunately, the reset conditions occur infrequently or unevenly (called passive filter deletion ). This work proposes the concept of revitalized snoop filter (RSF) design, which can actively renew the destination filter by employing a generation wrapping-around scheme for various reference behaviors. We further utilize a sampling mechanism for RSF to timely trigger precise filter revitalizations, so that unnecessary RSF flushing can be minimized. The proposed RSF can be integrated to various existent inclusive snoop filters with only a minor change to their designs. We evaluate our proposed design and demonstrate that RSF eliminates 58.6% of snoop energy compared to JETTY on average while inducing only 6.5% of revitalization energy overhead. In addition, RSF eliminates 45.5% of snoop energy compared to stream registers on average and only induces 2.5% of revitalization energy overhead. Overall, these RSFs reduce the total L2 cache energy consumption by 52.1% (58.6% -- 6.5%) as compared to JETTY and by 43% (45.5% -- 2.5%) as compared to stream registers. Furthermore, RSF improves the overall performance by 1% to 1.4% on average compared to JETTY and stream registers for various benchmark suites.

In a modern system-on-chip design, hundreds of cores and intellectual properties can be integrated into a single chip. To be suitable for high-performance interconnects, designers increasingly adopt advanced interconnect protocols that support novel mechanisms of parallel accessing, including outstanding transactions and out-of-order completion of transactions. To implement those novel mechanisms, a master tags an ID to each transaction to decide in-order or out-of-order properties. However, these advanced protocols may lead to transaction deadlocks that do not occur in traditional protocols. To prevent the deadlock problem, current solutions stall suspicious transactions and in certain cases, many such stalls can incur serious performance penalty. In this brief, we propose a novel ID assignment mechanism that guarantees the issued transactions to be deadlock-free and results in significant reduction in the number of transaction stalls issued by masters. Our experimental results show encouraging performance improvements compared with previous works with little hardware and power overheads.

By allowing timing errors to occur and recovering them online, resilient systems can be used to eliminate the voltage/frequency guardband to improve energy efficiency/throughput. Due to the nature of fault tolerance computing, resilient systems have a different binning strategy from traditional circuits. In this paper, we study, for the first time, the binning metrics of resilient systems. We propose a solution for resilient system binning based on structural at-speed delay testing. Then an adaptive clock configuration technique is proposed for yield improvement. Experimental results demonstrate the effectiveness of our proposed binning method, and significant yield improvement accomplished by the adaptive clock configuration technique.

Soft error has become an important reliability issue in advanced technologies. To tolerate soft errors, solutions suggested in previous works incur significant performance and power penalties, especially when a design with fault-tolerant structures is overprotected. In this paper, we present a soft-error-tolerant design methodology to tradeoff performance, power, and reliability for different applications. First, four novel detection and correction flip-flop (FF) structures are proposed to provide different levels of tolerance capability against soft errors. Second, architecture-level vulnerability and logic-level susceptibility analyses are employed to identify weak FFs that can easily cause program execution errors. Third, an optimization framework is developed to synthesize the proposed four novel FF structures into weak and highly observable storage bits with the flexibility of trading off performance, power, and reliability. A five-stage pipeline RISC core (UniRISC) is adopted to demonstrate the usefulness of our methodology. Experimental results show that the proposed method can accomplish design goals by balancing performance, power, and reliability. For example, we can not only satisfy the reliability requirement that no more than five errors occur per one billion hours in a design but also reduce up to 87% performance overhead and 91% power overhead when compared with previous works.

A macro-fault is defined as a group of signal faults such that the errors induced cannot be observed unless two or more faults (either permanent or temporary) in the group happen simultaneously. Since adding a redundant (alternative) wire for an existing (target) wire can mask some certain faults of these two wires mutually, a macro-fault can be formed by redundant wire addition. The faults that are dominated by or equivalent to the masked faults are also included in the macro-fault. As the feature size of integrated circuit technologies continue to scale down, manufacturing fault-free chips is getting more difficult and fault tolerance techniques will become more critical. In the past, redundancy has been adopted for memory for improving fault tolerance. For critical circuit components, even the costly triple modular redundancy techniques have to be applied. In this work, we study the implications of our new fault model, macro-fault, on the potential impact on fault tolerance and manufacturing yield. Based on the findings, a heuristic approach based on redundant wire addition is designed for improving fault tolerance. The approach can be incorporated with other fault tolerance techniques to form a hierarchical cross-layer fault tolerance scheme.

Region-based multi-supply voltage (MSV) design, by which circuits are partitioned into multiple "voltage islands" and each island operates at a supply voltage that meets its own performance requirement, is an effective technique to tradeoff power and performance. Different from conventional voltage island generation techniques that work in a conservative manner to guarantee "always correct" computation, in this work, we investigate the MSV design problem for timing-speculative circuits, which achieves high energy-efficiency by allowing the occurrence of infrequent timing errors and correcting them online. A novel algorithm based on dynamic programming is developed to tackle this problem. Experimental results on various benchmark circuits demonstrate the effectiveness of the proposed methodology.

By allowing the occurrence of infrequent timing errors and correcting them online, circuit-level timing speculation is one of the most promising variation-tolerant design techniques. How to effectively test timing-speculative circuits, however, has not been addressed in the literature. This is a challenging problem because conventional scan techniques cannot provide sufficient controllability and observability for such circuits. In this paper, we propose novel techniques to achieve high fault coverage for timing-speculative circuits without incurring high design-for-testability cost. Experimental results on various benchmark circuits demonstrate the effectiveness of the proposed solution.

This article presents a hybrid Automatic Test Pattern Generation (ATPG) technique using the staggered Launch-On-Shift (LOS) scheme followed by the one-hot launch-on-shift scheme for testing delay faults in a scan design containing asynchronous clock domains. Typically, the staggered scheme produces small test sets but needs long ATPG runtime, whereas the one-hot scheme takes short ATPG runtime but yields large test sets. The proposed hybrid technique is intended to reduce test pattern count with acceptable ATPG runtime for multimillion-gate scan designs. In case the scan design contains multiple synchronous clock domains, and each group of synchronous clock domains is treated as a clock group and tested using a launch-aligned or a capture-aligned LOS scheme. By combining these schemes together, we found the pattern counts for two large industrial designs were reduced by approximately 1.6X to 1.8X, while the ATPG runtime was increased by 40% to 50%, when compared to the one-hot clocking scheme alone.

This paper presents a hybrid automatic test pattern generation (ATPG) technique using the staggered launch-on capture (LOC) scheme followed by the one-hot LOC scheme for testing delay faults in a scan design containing asynchronous clock domains. Typically, the staggered scheme produces small test sets but needs long ATPG runtime, whereas the one-hot scheme takes short ATPG runtime but yields large test sets. The proposed hybrid technique is intended to reduce test pattern count with acceptable ATPG runtime for multi-million-gate scan designs. In case the scan design contains multiple synchronous clock domains, each group of synchronous clock domains is treated as a clock group and tested using a launch aligned or a capture aligned LOC scheme. By combining these schemes together, we found the pattern counts for two large industrial designs were reduced by approximately 1.1X to 2.1X, while the ATPG runtime was increased by 10% to 50%, when compared to the one-hot clocking scheme alone.

Recent research at Intel suggests that chips with hundreds of processor cores are possible in the not-so-distant future. As the number of cores grows, so does the size of the cache systems required to allow them to operate efficiently. Caches have grown to consume a significant percentage of the power utilized by a processor. In this research, we extend the concept of location cache to support chip multiprocessors (CMPs) systems in combination with low-power L2 caches based upon the gated-ground technique. The combination of these two techniques allows for reductions in both dynamic and leakage power consumption. In this paper, we will present an analysis of the power savings provided by utilizing location caches in a CMP system. The performance of the cache system is evaluated by extending the capability of CACTI and Simics using the SPLASH-2 and ALPBench benchmark suites. These simulation results demonstrate that the utilization of location caches in CMP systems is capable of saving a significant amount of power over equivalent CMP systems that lack location caches.

The increasing leakage power consumption and stringent thermal constraint necessitate more aggressive leakage control techniques. Power gating and body biasing are widely used for standby leakage control. Their large energy overhead for performing mode transition is the major obstacle for more aggressive leakage control. Temperature and process variation (TV/PV) further magnify the overhead problem, leading to so-called “corner case leakage control” problem. Light-weightVthhopping (LW-VH) is a candidate technique to tackle the energy overhead problem. This paper demonstrates the application of LW-VH on microarchitectural- and RTL-level idleness exploitation with adaptive control techniques for TV/PV compensation. Adaptive LW-VH shows 30% average saving on total CPU leakage at microarchitectural level, and 4% to 15% leakage saving at RTL level. By combining all the techniques proposed in this paper, a three-tier aggressive leakage control system is introduced to fully exploit idleness at all levels.

With the technology moving into the deep sub-100-nm region, the increase of leakage power consumption necessitates more aggressive power reduction techniques. Power gating is a promising technique. Our research emphasizes that with the latest and future technologies, power gating operates frequently in its transition mode, especially for aggressive leakage reduction. The dynamic characteristics of power gating during its mode transition is critical for making design decision. Hence we derive a fast, accurate, and temperature-aware model to characterize the dynamic behavior of power gating during mode transition. The applications of this model include the estimation of several key design parameters for power gating, such as dynamic virtual ground voltage, dynamic leakage variation and energy break-even time. It provides an efficient estimation engine for power gating design optimization. The accuracy of the model has been verified by extensive HSPICE experiments. The model is computationally efficient due to the usage of various approximation methods.

Power gating (PG) and body biasing (BB) are popular leakage control techniques at microarchitectural level. However, their large overhead prevents them from being applied for active leakage reduction. The overhead problem is further magnified by temperature and process variation, leading to the “corner case leakage control” problem. This paper presents an Adaptive Light-Weight Vth Hopping technique. This technique dramatically reduces the overhead for mode transition, addresses the corner case leakage control problem, and thus enables active leakage control.

Power gating has been widely adopted in multicore designs. The design of fast and reliable power mode transition for per-core power gating remains a challenging problem. This paper studies the design methodology for fast power gating wake-up with guaranteed power integrity. Two novel techniques, namely current shaping and multi-thread activation are proposed. Models and physical implementation of both techniques are analyzed. Experimental results demonstrated 1.5 to 11 times wake-up time speedup with no penalty on area or power consumptions by using the proposed techniques.

This paper presents a new at-speed logic built-in self-test (BIST) architecture supporting two launch-on-capture schemes, namely aligned double-capture and staggered double-capture, for testing multi-frequency synchronous and asynchronous clock domains in a scan-based BIST design. The proposed architecture also includes BIST debug and diagnosis circuitry to help locate BIST failures. The aligned scheme detects and allows diagnosis of structural and delay faults among all synchronous clock domains, whereas the staggered scheme detects and allows diagnosis of structural and delay faults among all asynchronous clock domains. Both schemes solve the long-standing problem of using the conventional one-hot scheme, which requires testing each clock domain one at a time, or the simultaneous scheme, which requires adding isolation logic to normal functional paths across interacting clock domains. Physical implementation is easily achieved by the proposed solution due to the use of a slow-speed, global scan enable signal and reduced timing-critical design requirements. Application results for industrial designs demonstrate the effectiveness of the proposed architecture.

This paper presents fault modeling and analysis for resistive bridging defects in a synchronizer constructed with two D flip-flops. Bridging defects are exhaustively injected into any two nodes of the synchronizer to find all possible faults that might occur in the synchronizer, and HSPICE is used to perform circuit analysis.

Ever since the invention of various leakage power reduction techniques, leakage and dynamic power reduction techniques are categorized into two separate sets. Most of them cannot be applied together during runtime. The gap between them is due to the large energy breakeven time (EBT) and wakeup time (WUT) of conventional leakage reduction techniques. This paper proposes a new leakage reduction technique (SLITH) based on Vthhopping. SLITH has very low EBT and WUT, yet keeps the effectiveness of leakage reduction. Thus, it is able to reduce the gap, and enables joint dynamic and leakage power reduction. SLITH can be applied together with clock gating, precomputation and operand isolation etc., and significantly reduces both dynamic and active leakage power consumption.

Runtime leakage control techniques, such as power gating (PG) and body biasing (BB), have been applied in a coarse-grained manner traditionally. In order to enable more aggressive leakage reduction, researchers are seeking ways to control leakage with finer granularity. Our research proposes two novel methods, namely circuit clustering for temporal and spatial idleness exploitation, to systematically reduce the granularity of leakage control and improve leakage reduction. Another strength of this paper is the quantitative study of leakage saving and control cost by leakage control with different granularity. With our quantitative study, designers can make the trade-off between leakage saving and control cost, and decide the optimum granularity for leakage control. A heuristic algorithm has been developed to automate the two circuit clustering methods and determine the optimum granularity for any given circuit. The analysis and experiments of this paper is mainly based on RBB. They are also applicable to PG by modifying the cost function.

Run-time Power Gating (RTPG) is a recent technique, which aims at aggressively reducing leakage power consumption. Energy breakeven time (EBT), or equivalent sleep time has been proposed as a critical figure of merit of RTPG. Our research introduces the definition of average EBT in a run-time environment. We develop a method to estimate the average EBT for any given circuit block, considering the impact of circuit states. HSPICE simulation results on ISCAS85 benchmark circuits show that the average EBT model has on the average 1.8% error. The CAD tool implemented based on the model can perform fast estimations with a speedup of 3000times over HSPICE.

Run-time active leakage reduction (RALR) is a recent technique and aims at aggressively reducing leakage power consumption. This paper studies the feasibility of RALR from the energy aspect, for both power gating (PG) and reverse body bias (RBB) implementations.We develop two energy saving models for PG and RBB, respectively. These models can accurately estimate the circuit energy saving at any time, even when the circuit is in state transition. In PG modeling, we discover a physical phenomenon called ldquoinstant savingrdquo, which can affect the model accuracy by 30%-50%. Based on the RBB model, we derive the optimum design point of RBB for RALR. Finally in terms of energy saving, we define four figures-of-merit, to compare the efficacy of using PG and RBB to implement RALR.

With the technology moving into the deep sub-100nm region, the increase of leakage power consumption necessitates more aggressive power reduction techniques. Power gating is a promising technique. Our research emphasizes the virtual ground voltage (VVG) as the key to make critical design trade-offs for power gating. We develop an accurate model to estimate the dynamic VVG value of a circuit block as a function of time after its ground is gated. Experimental results show that the model has less than 1% average error compared with HSPICE results. The CAD tool implemented based on the model has a 100 times speedup over HSPICE.

This paper describes a core-based test and diagnosis integration and automation system, called Turbo1500, which automatically synthesizes test and diagnosis logic in accordance with the IEEE 1500 standard. Turbo1500 serves two major purposes. One is for use as a core test automation tool in a system-on-chip (SOC) environment to automatically connect multiple cores from various sources and create testbenches each targeting an individual core under the control of a chip-level test access port (TAP) controller. The other is for hierarchical (block-by-block) core test and diagnosis when chips on a printed-circuit board are embedded with 1149.1 boundary scan I/O cells and cores under test and diagnosis are surrounded with 1500-compliant wrapper cells. Application experience showed that the simplicity of the IEEE 1500 standard combined with an easy-to-use automation tool can make core-based design for test and diagnosis no longer a nightmare, especially when some cores are extremely large or complex.

This paper presents a powerful routing method for pseudo-exhaustive built-in self-testing of high-speed interconnects with both capacitive and inductive crosstalk effects. Based on the concepts of test cone and cut-off locality, the routing method can generate an interconnect structure such that all nets can be tested by pseudoexhaustive patterns. The test pattern generation method is simple and efficient. Experimental results obtained by simulating a set of MCNC benchmarks demonstrate the feasibility of the proposed pseudo-exhaustive test approach and the efficiency of the proposed routing method.

Due to the spatial-locality property of data caches and the temporal-locality property of instruction caches, significant leakage reduction can be achieved by switching a large number of cache lines into the low-power standby or drowsy mode. It has been shown that 80%-90% of the data cache lines can be maintained in drowsy state without affecting the performance by more than 0.6% (IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 12, no. 2, pp. 167-184, Feb. 2004). However, with the introduction of the drowsy-cache design technique, new fault behaviors appear and more restrictive design rules must be applied to the chip fabrication process. In this paper, we simulate all possible spot defects (SDs) under normal mode and drowsy mode in different resistance regions using HSpice. Six new fault models appear with the introduction of drowsy mode for memory arrays. When we derive a march algorithm for the new fault models of this low-power cache, several simplification rules are utilized to reduce the test complexity. According to these simplification rules, each of these new faults has its equivalent counterpart existent in both data caches and instruction caches. As a result, we develop a march algorithm which can detect all SDs in either data caches or instruction caches. Since some faults occur only in drowsy mode, a built-in self-repair (BISR) scheme is developed. By utilizing BISR, the cache can still work even if some cache lines fail to work in drowsy mode

A novel routing algorithm, namely dynamic XY (DyXY) routing, is proposed for NoCs to provide adaptive routing and ensure deadlock-free and livelock-free routing at the same time.A new router architecture is developed to support the routing algorithm.Analytical models based on queuing theory are developed for DyXY routing for a two-dimensional mesh NoC architecture,and analytical results match very well with the simulation results.It is observed that DyXY routing can achieve better performance compared with static XY routing and odd-even routing.

With the introduction of the drowsy cache design technique (Kim et al., 2004), new fault behaviors appear and more restrictive design rules must be applied to the chip fabrication process. In this research, we simulate all possible spot defects (SDs) under normal mode and drowsy mode in different resistance regions using HSpice. Six new fault models appear with the introduction of drowsy mode for memory arrays. When we derive a march algorithm for the new fault models of this low-power cache, several simplification rules are utilized to reduce the test complexity. As a result, we develop a march algorithm which can detect all SDs in either data caches or instruction caches. Since some faults occur only in drowsy mode, a built-in self-repair (BISR) scheme is developed. By utilizing BISR, the cache can still work even if some cache lines fail to work in drowsy mode

In a later stage of a VLSI design, it is quite often to modify a design implementation to accommodate the new specification, design errors, or to meet design constraints. In addition to meet the design schedule for the new implementation, the reduction of the mask set have become very critical. In this paper, we propose a new method to add a programmable rectification module to reduce the mask cost and to improve the turn around time. When a modification is needed, one can program the rectification module to achieve the new implementation. The rectification module can be designed by one mask programmable gate array, or an embedded FPGA. To reduce the size needed for the rectification module, we also propose algorithms, which can intelligently select some internal signals of the old implementation to become pseudo primary inputs and primary outputs. Our experimental results are very encouraging.

Recently, it has been observed that embedded cores in a high-speed SoC circuit have the problem of broken scan chains that cannot shift properly. Also, scan chain intermittent faults caused by hold-time violations and crosstalk noises are pervasive. In this research, an efficient method is proposed to identify the faulty scan chain(s) at the core level. That is, the core where the scan chain is defective can be identified, even if the scan chain is broken. The result can be used to tune up the fabrication process or to guide the fine-grained scan cell identification process. Here, weight-based m-out-of-n codes, which can generate a large number of codewords, with small hardware overhead and high fault detection capability are used to generate the scan chain diagnostic patterns for permanent (and possibly intermittent) faults. An efficient codeword generation method is proposed to maximize the number of codewords, minimize the aliasing probabilities and test application cost. The idea of multiple m-out-of-n codes is also proposed to guarantee that sufficient number of codewords are generated to perturb the scan chains and the associated combinational circuits. Simulation results demonstrate the feasibility of the proposed method.

While set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which significantly reduces the power consumption for large set-associative caches. We propose to use a small cache, called location cache to store the location of future cache references. If there is a hit in the location cache, the supported cache is accessed as a direct-mapped cache. Otherwise, the supported cache is referenced as a conventional set-associative cache.The worst case access latency of the location cache system is the same as that of a conventional cache. The location cache is virtually indexed so that operations on it can be performed in parallel with the TLB address translation. These advantages make it ideal for L2 cache systems where traditional way-predication strategies perform poorly.We used the CACTI cache model to evaluate the power con-sumption and access latency of proposed cache architecture. Simplescalar CPU simulator was used to produce final results. It is shown that the proposed location cache architecture is power-efficient. In the simulated cache configurations, up-to 47% of cache accessing energy and 25% of average cache access latency can be reduced.

A built-in self-test (BIST) scheme which partitions the fixed (instead of movable) capacitance plates of a capacitive MEMS device is proposed. The BIST technique divides the fixed capacitance plate(s) at each side of the movable microstructure into three portions: one for electrostatic activation and the other two equal portions for capacitance sensing. Due to such partitioning, the BIST technique can be applied to surface-, bulk-micromachined MEMS devices and other technologies. Further, sensitivity and symmetry BIST methods based on this partitioning are also introduced. The combination of both BIST modes covers a larger defect set, thus a robust testing for the device can be expected. The BIST technique is verified by three typical capacitive MEMS devices. Simulation results show that the proposed technique is an effective BIST solution for various capacitive MEMS devices.

The concept of bus segmentation has been proposed to minimize power consumption by reducing the switched capacitance on each bus [Chen et al. 1999]. This paper details the design theory and implementation issues of segmented bus systems. Based on a graph model and the Gomory-Hu cut-equivalent tree algorithm, a bus can be partitioned into several bus segments separated by pass transistors. Highly communicating devices are placed to adjacent bus segments, so most data communication can be achieved by switching a small portion of the bus segments. Thus, a significant amount of power consumption can be saved. It can be proved that the proposed bus partitioning method achieves an optimal solution. The concept of tree clustering is also proposed to merge bus segments for further power reduction. The design flow, which includes bus tree construction in the register-transfer level and bus segmentation cell placement and routing in the physical level, is discussed for design implementation. The technology has been applied to a μ-controller design, and simulation results by PowerMill show significant improvement in power consumption.

In this work, based on the concept of test pattern broadcasting, we propose a new core-based testing method which gives core users the maximum level of test freedom. Instead of only using the test patterns delivered by core providers, core users are allowed to broadcast their own test patterns to the cores of a SoC (system on chip) design for parallel scan testing. The fault coverage of each core test, using test patterns developed by any core user, can be evaluated by an enhanced version of a traditional fault simulator. The netlist of each core is scrambled before it is delivered to core users, thus the netlist will not be revealed. The enhanced fault simulator of a core has the capabilities of decoding the scrambled netlist, and performing fault simulation for the test patterns provided by each of the core users. For each core, both random test patterns (applied by a core user), and golden test patterns (delivered by the core provider) jointly achieve high and flexible fault coverage requirements. The enhanced logic simulator of each core can also decrypt the scrambled netlist, and perform logic simulation with the objective of generating fault-free test responses for signature analysis (for example). The proposed method has the advantages of minimizing the number of scan pins, reducing the test application time, and achieving the maximum level of test quality control by core users. Simulation results demonstrate the feasibility of this method.

In this paper, the authors propose a new built-in self-diagnosis method to simultaneously diagnose spatially distributed memory modules with different sizes. Based on the serial interfacing technique, the serial fault masking effect is observed and a bidirectional serial interfacing technique is proposed to deal with such an issue. By tolerating redundant read/write operations, they develop a new march algorithm called DiagRSMarch to achieve the goals of low test signal routing overhead, tolerable diagnostic time, and high diagnostic coverage. It can be proved that DiagRSMarch can identify all stuck-at, transition, state coupling, and dynamic coupling faults occurring in all memory arrays. Experimental results also demonstrate that the test efficiency of DiagRSMarch is highly dependent on memory topology, defect-type distribution, and degree of parallelism.

In this paper, the authors propose a new transparent built-in self-test method to test in parallel multiple embedded memory arrays with various sizes. First, a new transparent test interface is designed to perform testing in the normal mode and to cope with test interrupts in a real-time manner. The circular scan test interface facilitates the processes of both test pattern generation and signature analysis. By tolerating redundant read/write/shift operations, we develop a new march algorithm called TRSMarch to achieve the goals of low hardware overhead, short test time, and high fault coverage. It can be proved that TRSMarch can detect all stuck-at faults, all transition faults, and each coupling fault occurring in different words. For each coupling fault occurring in the same word, depending on the coupling type and effect, it can be detected or its detection probability can be high as more transparent processes are executed. TRSMarch can be easily extended to deal with more faults such as single-cell read destructive faults and read destructive coupling faults.

In this work, we propose a new built-in self-testing (BIST) method that is able to concurrently test a set of spatially distributed embedded-memory modules with different sizes. Using the concept of redundant read-write operations, we develop a new march method, called RSMarch, to efficiently test each memory module. The new method has the advantages of low hardware overhead, short test time, and high-fault coverage. The total test time is dominated by large-size modules. To further reduce the test time, we also propose a split-mode test method to virtually partition each large memory array into smaller modules, which can be tested simultaneously.

Charge sharing, which occurs in any complementary metal-oxide-semiconductor (CMOS) domino gate, may degrade the output voltage level or may even cause an erroneous output value. In this paper, this problem is thoroughly investigated by considering circuit topology and circuit function. We describe a method to measure the sensitivity [called charge-sharing (CS) vulnerability] of the CS problem for each domino gate. A method to derive the CS vulnerability and the test vector for each domino gate is suggested. We also propose a transistor reordering method to dramatically reduce the CS vulnerabilities for all domino gates so that the CS problem can be alleviated. We also prove theoretically that a set of test vectors generated for single charge-sharing faults (SCSFs) can also detect all multiple charge-sharing faults (MCSFs). This good property significantly guarantees the test quality for the CS faults of domino circuits.

Because domino logic design offers smaller area and faster delay than conventional CMOS design, it is very popular in the high-performance processor. However, domino logic suffers from several problems and one of the most notable ones is the charge sharing problem. In this paper, we describe a method to measure the sensitivity of the charge-sharing problem for each domino gate. In addition, our algorithm also generates test vectors to detect the worst case of charge-sharing fault.

In this paper, we propose a new transparent Built-in Self-Diagnosis (BISD) method to diagnose multiple embedded memory arrays with various sizes in parallel. A new transparent diagnostic interface has been proposed to perform testing in normal mode. By tolerating redundant read/write/shift operations, we develop a new march algorithm called TDiagRSMarch to achieve the goals of low hardware overhead, lower test time, and high test coverage. Experimental results demonstrate that the diagnostic efficiency of TDiagRSMarch is independent of memory topology, defect-type distribution, and degree of parallelism.

The Charge Sharing (CS) problem is one of notorious noise problems in domino circuits design and test. In this paper, this problem is thoroughly investigated by considering circuit topology and circuit function. The sensitivity of each domino gate to the CS problem is represented by the concept of CS-vulnerability. A method to derive the CS-vulnerability and the test pattern for each domino gate is suggested. We also propose a transition reordering method to dramatically reduce the CS-vulnerabilities for all domino gates, so that the CS problem can be alleviated. Simulation results demonstrate that our transistor reordering method can efficiently reduce the CS-vulnerabilities for most of domino circuits.

To predict the difficulty of testing a wire stuck-at fault, testability analysis algorithms provide an estimated testability value by computing controllability and observability. In most common previous work such as COP and SCOAP, signal correlation between controllability and observability is not well handled. As a result, the estimated values can be quite inaccurate, On the other hand, some previous work can take into account signal correlation but may require more CPU time. This paper discusses an efficient method for testability analysis improvement. Our algorithm starts with results obtained from conventional testability analysis such as COP. For each stuck- at fault, we gradually refine these results by recursively applying some simple signal correlation rules. Experimental results show that, with reasonable run-time overhead, significant improvement for testability analysis can be achieved.

The advent of portable and high-density devices has made power consumption a critical design concern.In this paper, we address the problem of reducing power consumption via gate-level voltage scaling for those designs that are not under the strictest timing budget.We first use a maximum-weighted independent set formulation for voltage reduction on non-critical part of the circuit.Then, we use a minimum-weighted separator set formulation to do gate sizing and integrate the sizing procedure with a voltage scaling procedure to enhance power saving on the whole circuit.The proposed methods are evaluated using the MCNC benchmark circuits.and an average of 19.12% power reduction over the circuits having only one supply voltage has been achieved.

In this work, we propose a new built-in self-testing (BIST) method that is able to concurrently test a set of spatially distributed embedded-memory modules with different sizes. By allowing some redundant read/write operations for small modules, we develop a new march algorithm, called RSMarch, that can concurrently test all memory modules with the same fault coverage as if each module is tested individually. We also show that this method requires only one simple BIST controller and one test data line for all modules. Thus the new method has the advantages of short test time, high fault coverage and low area overhead.

This paper proposes a bus-segmentation method that efficiently reduces the switched capacitance on the bus. The power consumed by the bus can, therefore, be substantially reduced. The basic idea of bus segmentation is to partition the bus into several bus segments separated by pass transistors. Highly communicating devices are located to adjacent bus segments, thus, most data communication can be achieved by switching a small portion of the bus segments. As a result, power consumption and critical path delay are both reduced. Experimental results obtained by simulating a delay model and a power model demonstrate that the proposed segmented bus system reduces bus power by about 60%-70% and improves critical bus delay by about 10%-30%.

To predict the difficulty of testing a wire stuck-at fault, testability analysis algorithms provide an estimated testability value by computing controllability and observability. In all previous work, signal correlation between controllability and observability is generally ignored. As a result, the estimated value can be inaccurate. This paper discusses an efficient method to take into account signal correlation for testability analysis. Our experimental results have shown that, with little run time overhead, significant improvement of testability analysis can be achieved.

This paper presents a new test architecture, called Tree-LFSR/SR, to more effectively generate pseudo-exhaustive test patterns for combinational VLSI circuits. Instead of using a single scan chain, the proposed test architecture routes a scan tree driven by the LFSR to generate all possible input patterns for each output cone. The new test architecture is able to take advantages of both signal sharing and signal reuse. The benefits are: (1) the hardware overhead can be greatly reduced by saving routing area and XOR circuits, and (2) the difficulty of test architecture synthesis can be eased by accelerating the searching process of appropriate residues. The Tree-LFSR/SR configuration is then extended, if necessary, by adding XOR networks to deal with more complex input-output relations. An efficient method to directly synthesize the XOR network is also included. Experimental results obtained by simulating combinational benchmark circuits are very encouraging.

The defect level in circuit testing is the percentage of circuits such as chips, that are defective and shipped for use after testing. Our previously published results showed that the defect level of circuit fabrication and testing should be a probability distribution, rather than a single value, and the concept of confidence degree was proposed [Gondalia et al. 1993; Jone et al. 1995]. In this work, defect level is represented by a confidence interval which is more conventional and easier to interpret. The point estimate of defect level analysis and conditions to avoid meaningless confidence intervals are also investigated. Methods for adaptive random test length determination driven by different confidence intervals or interval length are proposed to meet both test requirements and test costs tradeoff. Finally, a complete test plan that can direct the test flow from fabrication infancy to maturity is suggested.

As the size of VLSI circuits increases, the use of random testing is becoming more common. One of the most important aspects of random testing is the determination of the test pattern length that guarantees a high confidence of fault detection. Generally, random test length is estimated by assuming that the set of test patterns applied is purely random. The assumption is not completely correct in applications where linear feedback shift registers (LFSR's) are employed to generate input vectors. In this paper, we have developed a test (Markov) model which faithfully reflects the pseudorandom behavior of test patterns, and all detectable single stuck-at faults (instead of the worst single stuck-fault only) are considered. The required test length is then determined by solving differential equations to achieve the specified test confidence. Based on the test model, analysis is first dedicated to the two-fault case, results are then extended to the k-fault analysis where k/spl ges/3. The test length thus determined is smaller than that derived based on the random pattern assumption, and test costs can be greatly reduced.

Due to the rapid progress in VLSI technology, the overall complexity of the chip has increased dramatically. There is a simultaneous need for more functions and higher speed in modern VLSI engineering. Therefore, use of a minimum amount of extra hardware to meet timing requirements is becoming a major issue in VLSI design. Here, we propose an efficient method for timing optimization using gate resizing. To control the hardware overhead, a minimum (or as small as possible) number of gates are selected for resizing with the aid of a powerful benefit function. To guarantee the performance of timing optimization, a modified version of PODEM, called /spl tau/PODEM, ensures that each resized gate is located on at least one critical path. Thus, resizing a gate definitively reduces circuit delay. Simulation results demonstrate that our timing optimization method can efficiently reduce circuit delay with a limited amount of gate resizing.>

In this paper, we present a circuit partitioning and test pattern generation technique for pseudo-exhaustive built-in self-testing of VLSI circuits. The circuit partitioning process divides a given circuit into a set of subcircuits which can be exhaustively tested, while the test pattern generation process generates reduced exhaustive test patterns for each subcircuit using a linear feedback shift register (LFSR). In conventional approaches, these two problems are considered separately. However, in this paper, both problems are considered and solved in the same phase. A graph theoretic model of VLSI circuits is proposed. Based on this model, a circuit partitioning algorithm using the concept of minimum vertex cut is devised to partition the circuit into a set of exhaustively testable subcircuits with restricted hardware overhead. Each time a subcircuit is generated by the partitioning algorithm, the test pattern generation problem is considered. A new algorithm, based on the subcircuit modification technique, is proposed with the objective of generating reduced exhaustive test patterns of limited length (e.g., /spl les/2/sup 20/) using LFSR's, for each of the subcircuits. This task is embedded in the circuit partitioning process itself, leading to an efficient and well-coordinated solution. Experiments using ISCAS benchmark circuit simulation have been conducted. The results demonstrate that the proposed method is very good.>

Test generation for sequential circuits has been a difficult task. This is due to the large search space to be considered in test pattern generation. In this paper the detection of permanent faults in sequential circuits by random testing is analyzed utilizing the circuit partitioning approach together with a continuous parameter Markov model. Given a large sequential circuit, it is partitioned into several smaller partitions using either series or parallel decomposition. For each partition with certain stuck faults specified, the original state table and its error version are derived from an analysis of the partition under fault-free and faulty conditions, respectively. A random testing strategy that uses a three-state Markov model is used for detecting permanent stuck faults. Experimentation on various sequential circuits has shown that a significant saving in testing or test generation time can be achieved if we partition the circuit and then test each of its components as opposed to testing the circuit in its original form.>

In this paper a new method called CACOP For the detection probability analyses of random test patterns is proposed. Considering computational complexity, CACOP is a compromise between O(n/sup 2/) testability analyses like full-range cutting algorithm (FRCA) and linear time testability analyses like the controllability observability program (COP). By propagating bounds of controllabilities and observabilities, CACOP can determine the detection probability lower bound (DPLB) efficiently. The DPLBs derived by CACOP are potentially higher (and thus more accurate) than by FRCA; in addition, CACOP is computationally more efficient than FRCA. The conventional linear time testability analyses cannot guarantee the derivation of DPLBs. On the contrary, CACOP can achieve the goal with tolerable increase in computing complexity.>

The defect level in circuit testing is the percentage of circuits, such as chips, which are defective and shipped for use after testing. In this work, it is demonstrated that the defect level of testing a circuit using random patterns should have a probability distribution rather than just a single value. Based on this concept, the confidence degree of a specified defect level for random testing can be derived, and the quality of circuit random testing is thus guaranteed. Results obtained based on random testing can be extended to other test methods, e.g., deterministic testing, pseudo-random testing, or functional testing. Experiments using computer simulation have been conducted for this work, and the results are very encouraging.>

General-purpose distributed systems comprised of computing nodes with different characteristics and connected by high-speed communication networks are very popular these days. The development of a dependable distributed system, however, necessitates the use of various techniques including fault tolerance to avert occurrences of failures or system malfunction. The ad hoc techniques of adding redundancy to improve reliability are not always suitable in these circumstances because of excessive design cost. Redundancies have to be allocated at various hardware and software levels in order to optimize their utilization in the system. This paper considers the design of general-purpose fault-tolerant distributed systems based on a layered approach. The benefits of the layered approach in the process of allocation of redundancy and fault tolerance at various system levels are presented and analyzed in the paper.

Parity checkers are widely used in digital systems to detect errors when systems are in operation. Since parity checkers are monitoring circuits, their reliability must be guaranteed by performing a thorough testing. In this work, multiple fault detection of parity checkers is investigated. We have found that all multiple stuck-at faults occurring on a parity tree can be completely detected using test patterns provided by the identity matrix plus zero vector. The identity matrix contains 1's on the main diagonal and 0's elsewhere; while the zero vector contains 0's. The identity matrix vectors can also detect all multiple general bridging faults, if the bridgings result in a wired-AND effect. However, test patterns generated from the identity matrix and binary matrix are required to detect a majority of the multiple bridging faults which yield wired-OR connections. Note that the binary matrix contains two 1's at each column of the matrix.>

Due to the rapid progress in VLSI technology, the overall complexity of the chip has increased dramatically.Both more functions and higher speed are required in modern VLSI engineering.Therefore, using a minimum amount of extra hardware to meet timing requirements is becoming a major issue in VLSI design.Here, we propose an efficient method for timing optimization using gate resizing.To control hardware overhead, a minimum (or as

The defect level in circuit testing is the percentage of circuits, such as chips, which are defective and shipped for use after testing. In this work, it is demonstrated that the defect level of testing a circuit using random patterns should have a probability distribution rather than just a single value. Based on this concept, the confidence degree of a specified defect level for random testing is thus guaranteed. Yield value is one of the parameters for defect level analysis, and methods for yield estimation are proposed. The performance of these methods is evaluated using both Monte Carlo simulation and theoretical analyses. Experiments using computer simulation have been conducted for this work, and the results are very encouraging.>

Sequential statistical analysis is applied to determine the defect level of random and pseudorandom testing. Results derived using worst-case analysis show that the defect of pseudorandom testing is always no larger than the defect of random testing. It is found that the defect level of random testing is a good approximation of that of pseudorandom testing only if either the yield or circuit detectability is high. The random test length is estimated, using the defect level as a basis. It is shown that random test length determination based on defect level yields a more realistic result than that based on escape probability. Monte Carlo simulation is also conducted to evaluate the performance and feasibility of the proposed defect level analysis. The results obtained are based primarily on the worst-case analysis. However, the analysis also provides an exact solution if each fault occurs equally likely (a general assumption). In addition, the approach may lead to a general solution.>

The authors examine the properties of fanout-free circuits, and develop an algorithm to generate single stuck-at fault test experiments that also detect all multiple stuck-at faults. These experiments are shown to be minimal in size. Results demonstrate that elaborate selection of nonsensitizing test pattern guarantees the detection of all multiple stuck-at faults using single stuck-at test experiments. The algorithm is deterministic, and will produce test sets for tree circuits containing any mixture of AND, OR, NOT, NAND, and NOR gates. The results can be extensively applied to multiple stuck-at fault detection for pseudo tree circuits such as parity checkers. The time complexity of the algorithm is determined to the O(n/sup 2/), where n is the number of gates in the circuit.>

One of the most important problems in random testing is the measurement of test confidence after a sequence of test vectors has been applied. Sequential statistical analysis is employed to determine the random test confidence. According to the analysis, the random test confidence depends on the detection probability of the circuit under test, the random test length, and the manufacturing yield. A detection procedure driven by a test quality indicator without presumed random test length is proposed based on the results of the sequential statistical analysis. Performance evaluation and simulation results demonstrate that the sequential statistical analysis reflects a better random test confidence than conventional approaches. This difference is due to the fact that conventional test confidence measures do not take the manufacturing yield into account.>

Hardware overhead reduction through counter selection is considered for the Hamming count compaction test. A method to choose the most effective syndrome and input variable counter pair is given. Both simulation and theoretical analysis illustrate that this method produces an optimal pairing. The aliasing probability of this two-counter test is developed and shown to reduce the exhaustive ones count aliasing probability by half an order.>

The problem of detecting permanent faults in sequential circuits by random testing is analyzed utilizing a continuous parameter Markov model. Given a sequential circuit with certain stuck faults specified, the original state table and its error version can be readily derived from an analysis of the circuit under fault-free and faulty conditions, respectively. By simulation of these two tables on a computer, the parameters of the desired Markov model can be obtained. The approach does not require formulation of a product state table corresponding to the fault-free state table and its faulty version, which is rather difficult, when dealing with large circuits. For a specified confidence degree, it is easy to derive the parameters of the model and to calculate the required lengths of random test patterns or the maximum testing time. A complete mathematical analysis of the model is given. It provides insight into the nature of faults in relation to random testing and the associated confidence degree.>

In this work, we propose a circuit partitioning and test pattern generation algorithm for built-in pseudoexhaustive self-testing of VLSI circuits. The circuit partitioning process is to partition a given circuit into a set of subcircuits such that pseudoexhaustive self-testing will be possible, while the test pattern generation process is to generate the pseudoexhaustive test patterns for each subcircuit using a linear feedback shift register (LFSR). Both problems are considered and solved in the same phase and lead to an efficient and well-coordinated solution. Experiments using computer simulation have been conducted. The results demonstrate that the proposed method is very good, especially for circuits that are highly locally connected.

This paper presents a test scheduling method, called overlaying concurrent testing, for built-in testing of VLSI circuits. The scheme is based on a resource-conflict analysis of of subcircuits and a scheduling algorithm. The algorithm fully exploits test parallelism by overlaying the test intervals of compatible subcircuits to test as many of them as possible concurrently. The technique is supported by a test hardware architecture whose design is well coordinated with the test scheduling leading to a considerable reduction of testing time, as demonstrated by simulation experiments.

A signature compaction method called Hamming count (H-count) is introduced. H-count is similar to a reduced Walsh spectral coefficient test, and encompasses all syndrome testable faults. H-count has both a lower masking probability and a simpler circuit design than the index vector test. The method provides an efficient and effective compaction technique.>