Summary form only given. This paper examines four aspects of computing and communications that are widely accepted and commonly confused: mobility, nomadicity, ubiquity, and pervasiveness. These attributes of present and future digital devices provide significant opportunities for new markets and important challenges in design for dependability. The relationship between dependability and the public is presented. Alternative approaches to dependability appropriate for consumers are discussed. Particular digital devices considered include cell phones, PDAs, notebook computers, and RFID.

In this paper, new schemes are presented in which the spare nodes of a permanent-fault-tolerant processing array are utilized in their idling state to aid in an online transient-error recovery process. Though spares-based methods are well-known solutions to permanent-fault tolerance, the cost of these solutions and the idling spare capacity during normal operation have limited their widespread use. Manufacturers must be offered fault tolerance solutions which provide useful work at all times. We propose the enhanced utility of spares-based methods by commissioning idling spares (those spares remaining after fabrication and subsequent replacement of faulty units) to perform transient-error recovery tasks. Our scheme will commission idling spares to perform periodic on-line testing (verifying whether system is functioning correctly), and recovery point validation during normal operation. When an error occurs, the spare will perform additional testing to select recovery points. Transient-error recovery is required in harsh environments, such as high radiation, where frequent transient errors are unavoidable. In these environments, the cost of job completion can be extremely high without some form of error recovery. Successful job completion can be attained in environments frequented by error bursts by identifying reliable data through the process of periodic on-line testing. We apply our scheme to a mesh array architecture that has applications in digital signal processing. Simulations highlight the overhead of our schemes in terms of job completion time in environments burdened with frequent transient random errors and burst errors. The proposed strategies for recovery are limited to systems of regular structure. There are many applications in signal and image processing that require array processing in which the various nodes perform similar operations with different data sets. Therefore, it is not necessary to switch the application algorithms for the spares when they perform redundant computation in a staggered mode. While this is a significant feature, there is a small cost associated with presenting the same data to a node as well as a spare. With built-in hardware and reconfiguration switches in the fault tolerant arrays, we believe this cost will be insignificant. Extension of our work to more general systems requires consideration of many issues including system timing, and sub-unit communication & dependence. This is a problem for future research.

Heterogeneous computing environments, where computers may have different instruction set architectures, data representations, and operating systems, complicate checkpointing and recovery of processes. This paper describes an approach to recovery and an implementation, PREACHES, that provides portable checkpointing of single-process applications in heterogeneous systems using checkpoint propagation. The checkpoint propagation mechanism creates machine-dependent checkpoints for different architectures in the heterogeneous environment. A process is restored on a specific machine with the checkpoint that is appropriate for the architecture. An implementation of PREACHES has been evaluated on a heterogeneous network of workstations, including Sun, HP, and Pentium machines. The experimental results show that PREACHES achieves efficient checkpointing and rapid recovery.

Efficient identification of fault equivalence relations is essential for effective diagnostic test pattern generation. In this paper, we present efficient techniques for identifying functionally equivalent faults in combinational circuits. The techniques are based on implication of faulty values, and evaluation of faulty functions in cones of dominator gates of fault pairs. This is enhanced by utilizing circuit redundancy information. Both static and dynamic methods are developed to exploit relations among inputs of dominator cones and further speed up the identification of equivalent fault pairs. Experimental results for all ISCAS'85 circuits, full scan versions of ISCAS'89 circuits, and ITC'99 circuits show that most of the equivalent fault pairs are identified. Significant reductions are obtained in the runtime needed to prove equivalence and the runtime for diagnostic test pattern generation compared to previously proposed approaches.

We introduce theorems that enable efficient identification of indistinguishable fault pairs in synchronous sequential circuits using an iterative logic array of limited length. These theorems can be used for identifying fault pairs that can be dropped from. consideration before diagnostic ATPG starts, thus improving the efficiency of diagnostic ATPG. Experimental results are presented to demonstrate the effectiveness of the proposed theorems, which allow us to identify almost all the indistinguishable fault pairs in finite-state machine benchmarks.

A recovery proxy that implements proxy-based recovery is described in this paper Proxy-based recovery provides failure recovery for applications on connected handheld devices. This approach enables proxys to monitor clients' interaction with back end servers and locally maintain a client's state based on observed messages. The proxy described in this paper provides a general message logging mechanisms as well as an interface for applications to implement their own checkpointing and message analysis mechanisms. When a client moves from one proxy to another a migration protocol described in this paper can be used to efficiently transfer the client's state and network connections to the new proxy. Experimental results on the proxy's latency, throughput and client migration overhead are provided.

This paper describes a message logging optimization that improves performance for failure recovery protocols where messages exchanged between mobile hosts are logged at base stations. The algorithm described and evaluated in this paper does not generate orphan processes in spite of base station failures and achieves run-time performance similar to that of asynchronous logging.

A procedure for identifying functionally equivalent faults and improving the performance of diagnostic test pattern generation is described in this paper. The procedure is based on evaluation of faulty functions in cones of dominator gates of fault pairs. This is enhanced by utilizing circuit redundancy information. Equivalence is proved without the previously required circuit transformations. Stem-branch equivalences for reconvergent stems and their branches are identified efficiently obviating the need to check for non-masking and multiple-path sensitization. Both static and dynamic techniques are developed to exploit relations among inputs of dominator cones. This reduces the simulation time required by the procedure and enables evaluation of larger cones than could be evaluated earlier. As a result, more equivalent fault pairs are identified. Experiments performed on ISCAS85 circuits and full scan ISCAS89 circuits are used to demonstrate the effectiveness of the proposed techniques.

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

Very Long Instruction Word (VLIW) architectures can enhance performance by exploiting fine-grained instruction level parallelism. In this paper, we describe a compiler assisted multiple instruction word retry scheme for VLIW architectures. A read buffer is used to resolve the more frequent on-path hazards, while the compiler resolves the remaining branch hazards. Performance evaluation is described for 11 benchmark programs based on the IBM VLIW research compiler, Chameleon. Experimental results indicate that, for a VLIW machine with P functional units to rollback N instruction words, a read buffer of 2NP entries with the compiler assist can be an effective approach in producing low overhead runtime performance and small code growth, for P = 4, 8, 12, and 16 and N /spl les/ 3.

Reversible execution has not been fully exploited in symbolic debuggers. Debuggers that can undo instructions usually incur a significant performance penalty during a debugging session. We describe an efficient reversible debugging mechanism based on program instrumentation. The approach enables repetitive debugging sessions with selectable reversible routines and recording modes. Experimental results indicate that the execution penalty can be significantly reduced with moderate code growth.

The low communication bandwidth, slow processor and limited memory of hand-held devices make it undesirable for them to store their own checkpoints or send process state information over a wireless network. The paper describes an approach to failure recovery for three-tier client and server application environments where the client applications execute on wireless handheld devices. The key idea is to have the middle-tier proxy transparently monitor the client's interaction with the back-end server and continuously maintain a copy of the client's state based on messages exchanged between the client and the server. The proxy also sustains the client's connection to the back-end server when a client unexpectedly disconnects. The client does not participate in checkpointing nor message logging, thereby saving power, processor cycles and bandwidth. The proxy is scalable and enhances backend server performance. Experimental results are provided for recovery time and runtime overhead.

Numerous mathematical approaches have been proposed to determine the optimal checkpoint interval for minimizing total execution time of an application in the presence of failures. These solutions are often not applicable due to the lack of accurate data on the probability distribution of failures. Most current checkpoint libraries require application users to define a fixed time interval for checkpointing. The checkpoint interval usually implies the approximate maximum recovery time for single process applications. However, actual recovery time can be much smaller when message logging is used. Due to this faster recovery, checkpointing may be more frequent than needed and thus unnecessary execution overhead is introduced. In this paper, an adaptive checkpointing protocol is developed to accurately enforce the user-defined recovery time and to reduce excessive checkpoints. An adaptive protocol has been implemented and evaluated using a receiver-based message logging algorithm on wired and wireless mobile networks. The results show that the protocol precisely maintains the user-defined maximum recovery times for several traces with varying message exchange rates. The mechanism incurs lour overhead, avoids unnecessary checkpointing, and reduces failure free execution time.

Efficient identification of fault equivalence is essential for the completeness and efficiency of diagnostic test pattern generation. In this paper, we present new techniques to prove diagnostic fault equivalence. The techniques are based on implication of the faulty values, and functional evaluation at the dominator gate of the fault sites. The experimental results for all ISCAS85 circuits and full scan versions of ISCAS89 circuits show significant improvement compared to previously proposed techniques in both the number of equivalent pairs identified and the time to prove equivalence.

With the increase in the complexity of VLSI circuit design, logic design errors can occur during synthesis. In this work, we present a method for multiple design error diagnosis and correction. Our approach uses the results of test vector simulation for both error detection and error correction. This makes it applicable to circuits with no global BDD representation. In addition, diagnosis is performed through an implicit enumeration of potentially erroneous lines in an effort to avoid the exponential explosion of the error space. Experimental results on ISCAS'85 benchmark circuits show that our approach can typically detect and correct 1, 2 and 3 errors within seconds of CPU time.

We propose a procedure for generating test patterns for diagnosis of combinational (or fully-scanned sequential) circuits based on stuck-at faults. The test generation procedure avoids the conventional fault-oriented test generation by observing that a test pattern to distinguish two faults can be obtained from a test pattern that detects both of the faults by changing the test pattern so as to "undetect" one of the faults, or change the primary outputs on which the faults are detected. The proposed procedure is applied starting from a fault detection test set (a test set that detects every detectable stuck-at fault). For every pair of faults left undistinguished by the test set, the procedure attempts to modify a test pattern that detects both faults such that the resulting, modified pattern would distinguish the faults. We present experimental results to demonstrate the numbers of fault pairs that can be distinguished by the proposed procedure assuming diagnosis based on full responses and diagnosis based on pass/fail information.

In this paper, we present results for significantly improving the performance of sequential circuit diagnostic test pattern generation (DAWG).Our improvements are achieved by developing results that permit dynamic, fully functional, collapsing of candidate faults.Fault collapsing permits the organization of faults into disjoint partitions based on the indistinguishability relation.These results are used to develop a diagnostic test pattern generation algorithm that has the same order of complexity as that of detection-oriented test generation (ATPG).Techniques to identify untestable faults, based on exploiting indistinguishability identification, are also presented.Experimental results are presented on the ISCAS S9 benchmark circuits.

This paper presents dynamic two stage fault isolation for sequential random logic VLSI circuits, and introduces limited and dynamic fault dictionaries. In the first stage of the dynamic process, a limited fault dictionary identifies candidate faults, which are further distinguished in the second stage by a dictionary generated dynamically for the candidate faults and a subset of the test vectors. This provides high resolution but avoids the costs of full static dictionaries. Two-stage fault isolation is evaluated for benchmark circuits and on defects in industrial circuits.

A deductive technique is presented that uses voltage testing for the diagnosis of single bridging faults between two gate input or output lines and is applicable to combinational or full-scan sequential circuits. For defects in this class of faults the method is accurate by construction while making no assumptions about the logic-level wired-AND/OR behaviour. A path-trace procedure starting from failing outputs deduces potential lines associated with the bridge. The information obtained from the path-trace from failing outputs is combined using an intersection graph to make further deductions. All candidate faults are implicitly represented, thereby obviating the need to enumerate faults and hence allowing the exploration of the space of all faults. Results are provided for all large ISCAS89 benchmark circuits.

Failure diagnosis is resource intensive, frustrating, and often impossible. However, it is also critical and necessary for aggressive designs and manufacturing processes. Research in this area is making rapid progress, but the challenges are also rapidly growing in magnitude and importance.

A diagnosis technique that integrates the storage of precomputed information with some dynamic computation for the diagnosis of bridging faults in synchronous sequential circuits with no-scan or partial-scan is presented. The method addresses the accuracy, storage requirements, and computational complexity required for diagnosis. A combination of adaptively simulating the behavior of a bridging fault and storing faulty state information at select vectors ensures accuracy with low storage requirements. The combination of adaptive simulation, state storage, and pathtracing has low computational requirements. Experimental results are provided for the ISCAS89 benchmark circuits.

Describes a fault detection mechanism that uses the error codes returned by stream sockets to locate process failures. Since these errors are generated automatically when there is communication with a failed process, the mechanism does not incur in any failure-free overheads. However, for some types of faults, detection can only be attained if the surviving processes use certain communication operations. To assess the coverage and latency of the proposed mechanism, faults were injected during the execution of parallel applications. Our results show that in most cases, faults could be found using only the errors from the socket layer. Depending on the type of fault that was injected, detection occurred in an interval ranging from a few milliseconds to less than nine minutes.

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

This paper describes a generalized sequential diagnosis algorithm whose analysis leads to strong diagnosability results for a variety of multiprocessor interconnection topologies. The overall complexity of this algorithm in terms of total testing and syndrome decoding time is linear in the number of edges in the interconnection graph and the total number of iterations of diagnosis and repair needed by the algorithm is bounded by the diameter of the interconnection graph. The degree of diagnosability of this algorithm for a given interconnection graph is shown to be directly related to a graph parameter which we refer to as the partition number. We approximate this graph parameter for several interconnection topologies and thereby obtain lower bounds on degree of diagnosability achieved by our algorithm on these topologies. If we let N denote total number of vertices in the interconnection graph and /spl Delta/ denote the maximum degree of any vertex in it, then our results may be summarized as follows. We show that a symmetric d-dimensional grid graph is sequentially /spl Omega/(N[d/d+1])-diagnosable for any fixed d. For hypercubes, symmetric log N-dimensional grid graphs, it is shown that our algorithm leads to a surprising /spl Omega/([N log log N/log N]) degree of diagnosability. Next we show that the degree of diagnosability of an arbitrary interconnection graph by our algorithm is /spl Omega/(/spl radic/N//spl Delta/). This bound translates to an /spl Omega/(/spl radic/N) degree of diagnosability for cube-connected cycles and an /spl Omega/(/spl radic/N/k) degree of diagnosability for k-ary trees. Finally, we augment our algorithm with another algorithm to show that every topology is /spl Omega/(N/sup 1/3/)-diagnosable.

A method of execution retry for bypassing software faults in message-passing applications is described in this paper. Based on the techniques of checkpointing and message logging, we demonstrate the use of message replaying and message reordering as two mechanisms for achieving localized and fast recovery. The approach gradually increases the rollback distance and the number of affected processes when a previous retry fails, and is therefore named progressive retry. Examples from telecommunications software systems and performance measurements from an application-level implementation are described to illustrate the benefits of the scheme.

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

Integrated fault diagnosis techniques attempt to overcome the limitations associated with static (pre-computed information usage) and dynamic (run-time analysis) techniques by using a limited amount of pre-computed information and coupling this with simulation at diagnosis time, for rapid fault diagnosis. A significant problem with previous integrated techniques is that the pre-computed information is not targeted specifically toward reducing the run-time costs. We present a new approach to integrated fault diagnosis, by specifically creating the precomputed information to provide later savings in the simulation costs at diagnosis time. Experimental results on the ISCAS 85 and ISCAS 89 circuits illustrate the savings achieved by this technique.

State justification is a time-consuming operation in test generation for sequential circuits. In this paper, we present a technique to rapidly identify state elements (hip-hops) that are either difficult to set or unsettable. This is achieved by performing test generation on certain transformed circuits to identify state elements that are not settable to specific logic values. Two applications that benefit from this identification are sequential circuit test generation and partial scan design. The knowledge of the state space is shown to be useful in creating early backtracks in deterministic test generation. Partial scan selection is also shown to benefit from the knowledge of the difficult-to-set hip-hops. Experiments on the ISCAS89 circuits are presented to show the reduction in time for test generation and the improvements in the testability of the resulting partial scan circuits.

Selection of flip-flops that provide the best improvements in testability is a critical part of the partial scan design process. This paper describes a new technique for flip-flop selection that models the effect of scan in terms of the introduction of pseudo state transitions in the state transition graph. The identification of (desired) state transitions that provide for improved testability is based on an analysis of the known reachable states and desired states which ensure improved fault detection. Experiments are presented on the ISCAS 89 circuits to show significant improvements in the testability of the resulting partial scan design.

A significant problem with current diagnostic test generation techniques is the time spent in identifying diagnostic equivalences amongst fault pairs. Fault pair distance analysis is introduced in this paper to characterize diagnostically equivalent fault pairs and motivate local circuit transformations and structural analysis to identify equivalences in combinational circuits rapidly. Our results establish a connection between redundant faults and a specific class of diagnostically equivalent fault pairs. Structural analysis is then used to identify equivalences between fault pairs. Experimental results are presented on benchmark circuits to demonstrate the efficiency of the techniques.

The process of fault dictionary compaction can lead to a loss of information that is potentially useful in locating unmodeled failures. The focus of this paper is on developing alternative storage structures that can efficiently represent full fault dictionaries without discarding any information. We present the problem of storing the full fault dictionary storage as a labeled tree encoding problem. Two labeled trees are introduced to represent the diagnostic experiment. For the first tree, the unlabeled tree is stored using a binary string code, while the second tree is constructed so that the unlabeled tree is regular in structure, thus allowing implicit storage. Eight alternative representations based on the three label components are presented and two existing full fault dictionary representations (the matrix and the list dictionaries) are shown to be special cases in our general framework. Experimental results on the ISCAS 85 and ISCAS 89 circuits are used to study and characterize the performance of the proposed storage structures.

A dynamic diagnosis scheme for synchronous sequential circuits is proposed. In contrast with schemes like fault dictionaries no prior computation and storage of fault symptoms is performed. The technique combines cause-effect and effect-cause strategies. Cause-effect analysis is performed by single stuck at fault simulation followed by a matching algorithm. Effect-cause analysis is performed by an error propagation back-trace starting from the falling outputs. The error propagation back-trace eliminates from consideration faults that could not have caused the failing symptoms. The procedure is exact for defects behaving as single stuck-at faults. Experimental results are provided for the ISCAS89 benchmark circuits.

For a reconfigurable architecture, the harvest rate is the expected percentage of defect-free processors that can be connected into the desired topology. The authors give an analytical estimation for the harvest rate of reconfigurable multipipelines based on the following model: there are n pipelines each with m stages, where each stage of a pipeline is defective with identical independent probability 0.5 and spare wires are provided for reconfiguration. By formulating the "shifting" reconfiguration as weighted chains in a partial ordered set, they prove when n=/spl theta/(m), the harvest rate is between 34% and 72%.

Processor arrays, featuring modularity, regular interconnection, and high parallelism, are well suited for VLSI/WSI implementation and specific applications with high computational requirements. Error detection and recovery are important for some applications of processor arrays. Concurrent error detection (CED) techniques, which check normal system operations, are designed to detect errors caused by transient and intermittent faults, However, CED techniques typically suffer from costly hardware penalties or performance costs. This paper describes the periodic application of concurrent error detection (PACED) technique which allows the performance costs incurred through the use of time-redundant CED in processor array architectures to be reduced. The application of CED is varied in both time and space to provide probabilistic detection of errors in processor arrays. The probability of correctness of outputs from processor arrays is studied. Formulae are derived that predict, upon error detection, the amount of possibly erroneous output, for single processors, linear arrays and 2-dimensional mesh processor arrays. The results indicate that the error coverage can be surprisingly high when PACED is applied in processor arrays, e.g., 95% for checking performed 50% of the time.

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

Multiple instruction rollback (MIR) is a technique that has been implemented in mainframe computers to provide rapid recovery from transient processor failures. Hardware-based MIR designs eliminate rollback data hazards by providing data redundancy implemented in hardware. Compiler-based MIR designs have also been developed which remove rollback data hazards directly with data-flow transformations. This paper describes compiler-assisted techniques to achieve multiple instruction rollback recovery. We observe that some data hazards resulting from instruction rollback can be resolved efficiently by providing an operand read buffer while others are resolved more efficiently with compiler transformations. The compiler-assisted scheme presented consists of hardware that is less complex than shadow files, history files, history buffers, or delayed write buffers, while experimental evaluation indicates performance improvement over compiler-based schemes.>

This paper describes a compiler-based approach to provide multiple instruction rollback capability for general purpose processor registers. The objective is achieved by having the compiler remove all forms of N-instruction antidependencies. Pseudoregister antidependencies are removed by loop protection, node splitting, and loop expansion techniques; machine register antidependencies are prevented by introducing antidependency constraints in the interference graph used by the register allocator. To support separate compilation, inter-procedural antidependency constraints are added to the code generator to guarantee the termination of machine register antidependencies across procedure boundaries. The algorithms have been implemented in the IMPACT C compiler. Experiments illustrating the effectiveness of this approach are described.>

The contribution of this paper on the diagnosis (fault location) of CMOS bridging faults is threefold: First, the traditional fault dictionary (referred to as the full dictionary in this paper) is evaluated at the circuit level using a mixed-mode fault simulator. The fault set consists of randomly-generated gate input/output bridging faults. By using mixed-mode gate- and electrical-level detection methods, good diagnostic capability is achieved using only gate-level generated test sets. Second, we evaluate two reduced fault dictionaries, the pass/fail dictionary and the count dictionary. Finally, the effectiveness of I/sub DDQ/ for diagnosis is examined. The results show that I/sub DDQ/, combined with the proposed voltage detection methods, achieves the highest diagnostic performance, with nearly complete diagnosis.>

Uncoordinated checkpointing allows process autonomy and general nondeterministic execution, but suffers from potential domino effects and the associated space overhead. Previous to this research, checkpoint space reclamation had been based on the notion of obsolete checkpoints; as a result, a potentially unbounded number of nonobsolete checkpoints may have to be retained on stable storage. In this paper, we derive a necessary and sufficient condition for identifying all garbage checkpoints. By using the approach of recovery line transformation and decomposition, we develop an optimal checkpoint space reclamation algorithm and show that the space overhead for uncoordinated checkpointing is in fact bounded by N(N+1)/2 checkpoints where N is the number of processes.>

Interconnect diagnosis is an important problem in very large scale integration (VLSI), multichip module (MCM) and printed circuit board (PCB) production. The problem is to detect and locate all the shorts, opens and stuck-at faults among a set of nets using the minimum number of parallel tests. In this paper, we present worst-case optimal algorithms and lower bounds to several open problems in interconnect diagnosis.>

Superscalar and Very Long Instruction Word (VLIW) architectures exploit fine-grain parallelism to achieve better performance. Static scheduling techniques, such as trace scheduling and superblock scheduling, can effectively produce compact code for these architectures. In this paper, we present an analytical approach for bookkeeping in code scheduling that alleviates the coding complexity and instruction duplication limitations of the previous approaches. We describe techniques that allow instructions to be moved around loop and if-then-else constructs using global information. We also show that according to the classification of the register sets, certain instructions can be moved around subroutine calls, since their register live ranges can be predetermined across the procedural boundaries at compile time. Performance is compared with respect to the speed-up, the code size and the scheduling time. Experimental results indicate that the code growth and the speed-up are both improved with a small increase in scheduling time.

Checkpointing techniques in parallel systems use dependency tracking and/or message logging to ensure that a system rolls back to a consistent state. Traditional dependency tracking in distributed shared memory (DSM) systems is expensive because of high communication frequency. In this paper we show that, if designed correctly, a DSM system only needs to consider dependencies due to the transfer of blocks of data, resulting in reduced dependency tracking overhead and reduced potential for rollback propagation. We develop an ownership timestamp scheme to tolerate the loss of block state information and develop a passive server model of execution where interactions between processors are considered atomic. With our scheme, dependencies are significantly reduced compared to the traditional message-passing model.>

The contribution of this paper on the diagnosis (fault location) of CMOS bridging faults is threefold: First, the traditional fault dictionary (referred to as the full dictionary) is evaluated at the circuit level using a mixed-mode fault simulator. The fault set consists of randomly-generated gate input/output bridging faults. By using detection methods good diagnostic capability is achieved using only gate-level generated test sets. Second, the authors evaluate two reduced fault dictionaries, the pass/fail dictionary and the count dictionary. The results show the performance of the much smaller pass/fail dictionary is nearly equal to the full dictionary. Third, the effectiveness of I/sub DDQ/ for diagnosis is examined. The results show that I/sub DDQ/ combined with the proposed voltage detection methods achieves the highest diagnostic performance, with near complete diagnosis.>

Abstract Previous work on compiler‐based multiple instruction retry has utilized a series of compiler transformations, loop protection, node splitting, and loop expansion, to eliminate anti‐dependencies of length ≤Nin the pseudo register, the machine register, and the post‐pass resolver phases of compilation.1The results have provided a means of rapidly recovering from transient processor failures by rolling backNinstructions. This paper presents techniques for improving compilation and run‐time performance in compiler‐based multiple instruction retry. Incremental updating enhances compilation time when new instructions are added to the program. Post‐pass code rescheduling and spill register reassignment algorithms improve the run‐time performance and decrease the code growth across the application programs studied. Branch hazards are shown to be resolvable by simple modifications to the incremental updating schemes during the pseudo register phase and to the spill register reassignment algorithm during the post‐pass phase.

Abstract This paper describes a compiler‐based approach to checkpointing for process recovery. The implementation is transparent to both the programmer and the hardware. The compiler‐generatedsparse potential checkpointcode maintains the desired checkpoint interval.Adaptive checkpointingreduces the size of the checkpoints.Trainingis used to select low‐cost, high‐coverage potential checkpoints. The problem of selecting potential checkpoints is shown to be NP‐complete, and a heuristic algorithm is introduced that determines a quick suboptimal solution. These compiler‐assisted checkpointing techniques have been implemented in a modified version of the GNU C (GCC) compiler. Experiments involving the modified version of the GCC compiler on a Sun SPARC workstation are summarized.

Several variations of cache-based checkpointing for rollback error recovery from transient errors in shared-memory multiprocessors have been recently developed. By modifying the cache replacement policy, these techniques use the inherent redundancy in the memory hierarchy to periodically checkpoint the computation state. Three schemes, different in the manner in which they avoid rollback propagation, are evaluated in this paper. By simulation with address traces from parallel applications running on an Encore Multimax shared-memory multiprocessor, we evaluate the performance effect of integrating the recovery schemes in the cache coherence protocol. Our results indicate that the cache-based schemes can provide checkpointing capability with low performance overhead, but with uncontrollable high variability in the checkpoint interval.>

A new technique for creating small fault dictionaries for sequential circuits is presented, along with a hybrid combination of that new technique with another and performance improvements for a previously published technique. Seven techniques are compared and evaluated by their impact on dictionary size, fault simulation costs, and diagnostic resolution losses. The comparisons show that compact dictionaries with full resolution are computationally expensive, while small, inexpensive dictionaries almost always suffer a resolution loss. Measures of diagnostic resolution are described with an algorithm to approximate them in linear time. Experiments are presented for the ISCAS sequential benchmark circuits.

Redundant Arrays of Distributed Disks (RADD) can be used in a distributed computing system or database system to provide recovery in the presence of disk crashes and temporary and permanent failures of single sites. In this paper, we look at the problem of partitioning the sites of a distributed storage system into redundant arrays in such a way that the communication costs for maintaining the parity information are minimized. We show that the partitioning problem is NP-hard. We then propose and evaluate several heuristic algorithms for finding approximate solutions. Simulation results show that significant reduction in remote parity update costs can be achieved by optimizing the site partitioning scheme.

We study the performance of two redun dant disk array organizations in a transaction processing environment and compare it to that of mirrored disk organi zations and organizations using no striping and no redun dancy. Redundant disk arrays and mirrored disks are used for providing rapid recovery from mediafailures in systems requiring high availability. The disk array organizations examined are: data striping with rotated parity (RAIDS) and Parity Striping. RAIDS provides high data transfer rates by striping the data over multiple disks. It also pro vides better load balancing over the disks in the array. At the same time, data striping increases disk arm use which can lead to longer queuing delays. In transaction process ing environments, because of the nature of I/O requests, namely a large number of small size requests, disk arms are a more valuable resource than data transfer bandwidth. Hence, parity striping was proposed as an alternative to RAIDS. It provides rapid recovery from failure at the same low storage cost without interleaving the data over multiple disks. In this study, we use data from a large scale commer cial transaction processing site to evaluate and compare the performance of the above organizations. We consider both non-cached systems as well as systems using a non-volatile cache in the controller.

The technique of lazy checkpoint coordination, which preserves process autonomy while employing communication-induced checkpoint coordination for bounding rollback propagation is proposed. The notion of laziness is introduced to control the coordination frequency and allow a flexible tradeoff between the cost of checkpoint coordination and the average rollback distance. Worst-case overhead analysis provides a means for estimating the extra checkpoint overhead. Communication trace-driven simulation for several parallel programs is used to evaluate the benefits of the proposed scheme.>

An algorithm for garbage collection in distributed systems with object sharing across processor boundaries is described. The algorithm allows local garbage collection at each node in the system to proceed independently of local collection at the other nodes. It requires no global synchronization or knowledge of the global state of the system and exhibits the capability for graceful degradation. The concept of a specialized dump node is proposed to facilitate the collection of inaccessible circular structures. An experimental evaluation of the algorithm is also described. The algorithm is compared with a corresponding scheme that requires global synchronization. The results show that the algorithm works well in distributed processing environments even when the locality of object references is low.>

A twin-page storage method, which is an alternative to the TWIST (twin slot) approach by A. Reuter

The authors propose a method for using redundant disk arrays to support rapid recovery from system crashes and transaction aborts in addition to their role in providing media failure recovery. A twin-page scheme is used to store the parity information in the array, making it possible to keep the old version of the parity along with the new version. The old version of the parity is used to undo updates performed by aborted transactions or by transactions interrupted by a system failure. Using an analytical model, it is shown that the proposed method achieves a significant increase in the throughput of database systems using redundant disk arrays by reducing the number of recovery operations needed to maintain the consistency of the database.>

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

Message-passing systems with a communication protocol transparent to the applications typically require message logging to ensure consistency between checkpoints. A periodic independent checkpointing scheme with optimistic logging to reduce performance degradation during normal execution while keeping the recovery cost acceptable is described. Both time and space overhead for message logging can be reduced by detecting messages that need not be logged. A checkpoint space reclamation algorithm is presented to reclaim all checkpoints which are not useful for any possible future recovery. Communication trace-driven simulation for several hypercube programs is used to evaluate the techniques.>

Reconfigurable logic and memory structures are an important means of increasing manufacturing yield as both circuit density and chip size continue to increase. Yield enhancement through reconfiguration, however, necessarily relies on accurate diagnosis of fault locations. Although a substantial body of literature exists concerning testing of logic arrays, little is known regarding diagnosis of the specific locations of multiple faults in such arrays. In the paper a fault diagnosis algorithm is presented for large programmable logic arrays (PLAs).>

Reconfiguration of memory arrays with spare rows and columns has been shown to be an NP-complete problem. An analysis of average-case time complexities of several existing heuristics is presented, as well as a provably average-case polynomial-time algorithm for reconfiguration of memories with spare rows and columns. The algorithm runs faster than previous heuristics when the problem size is larger.>

Multicomputer cache simulation results derived from address traces collected from an Intel iPSC/2 hypercube multicomponent are presented. The primary emphasis is on examining how increasing the number of processor nodes executing a parallel application affects the overall multicomputer cache performance. The effects on multicomputer direct-mapped cache performance of application-specific data partitioning, data access patterns, communication distribution, and communication frequency are illustrated. The effects of system accesses on total cache performance are explored, as well as the reasons for application-specific differences in cache behavior for system and user accesses. Comparing user code results with full user and system code analysis reveals the significant effect of system accesses, and this effect increases with multicomputer size. The time distribution of an application's message-passing operations is found to more strongly affect cache performance than the total amount of time spent in message-passing code.>

In this paper, we present the results of multiple-fault fault simulation experiments which have been performed on ISCAS combinational [I] and sequential [2] benchmarks. Using test sets generated by a single stuck-at fault test generator [3], we performed symbolic fault simulation to determine multiple stuck-at fault coverage. Injecting all faults simultaneously, our fault simulation algorithm uses N-ary decision diagrams (NDDs) to determine the effects of the faults on the behavior of the circuit. A testing function is generated by comparing the outputs computed by the faultfree circuit and the circuit with faults activated. The coverage is then determined by computing the ratio of the size of the satisfying set of the testing function and the number of possible multiple-fault scenarios.

A two-stage procedure for locating VLSI faults is presented. The approach utilizes dynamic fault dictionaries, test set partitioning, and reduced fault lists to achieve a reduction in size and complexity over classic static fault dictionaries. An industrial implementation is reported in which faults were injected and diagnosed in a VLSI chip and the perjiormunce of two-stage fault location was measured.

Fault dictionaries are examined as a tool for automated diagnosis of VLSI failures. A compressed fault dictionary format and diagnosis algorithms are presented. Both combinational and sequential circuits are considered. Dictionaries are created, for example ISCAS circuits and simulated errors diagnosed.>

A twin-page disk-storage management scheme for rapid database transaction-undo recovery is presented and evaluated. In contrast to previous twin-page schemes, this approach uses static page mapping and allows dirty pages in the main memory to be written, at any instant, onto disk without the requirement of undo logging. No explicit undo is required when a transaction is aborted. Transaction undo is implicitly performed by not subsequently fetching from disk the invalid pages updated by the aborted transaction. Performance in terms of disk I/O and CPU overhead for transaction-undo recovery is analyzed and compared with a previous approach called TWIST. It is shown that the present scheme achieves rapid transaction-undo recovery without degrading average system performance for various workloads, and that the scheme is well suited for applications with a large number of updates and frequent transaction aborts.>

Partial detectability profiles are introduced for estimating the fault coverage of random pattern input vectors. Partial profiles are justified mathematically, and the relationship between sample size and error introduced is quantified. The results of circuit simulations are presented, illustrating the accuracy of estimates based on partial detectability profiles. The reason for use of partial profiles instead of full profiles is that they do not require fault simulation over all possible input vectors. Similarly, the advantage partial profiling has over simulating a few random faults for all input vectors is that the number of possible input vectors often becomes prohibitive before the number of faults in very large circuits. Another interesting application is to use partial profiles to determine which faults have the lowest detectabilities.>

Diagnosis strategies are investigated for repairable VLSI and WSI structures based on integrated diagnosis and repair. Knowledge of the repair strategy, the probability of each unit being good, and the expected test time of each unit is used by the diagnosis algorithm to select units for testing. The general problem is described, followed by an examination of a specific case. For k-out-of-n structures, a complete proof is given for the optimal diagnosis procedure of Y. Ben-Dov (1981). A compact representation of the optimal diagnosis procedure is described, which requires O(n/sup 2/) space and can be generated in O(n/sup 2/) time. Simulation results are provided to show the improvement in diagnosis time over online repair and offline repair.>

The problem of rollback recovery in distributed shared virtual environments, in which the shared memory is implemented in software in a loosely coupled distributed multicomputer system, is examined. A user-transparent checkpointing recovery scheme and a new twin-page disk storage management technique are presented for implementing recoverable distributed shared virtual memory. The checkpointing scheme can be integrated with the memory coherence protocol for managing the shared virtual memory. The twin-page disk design allows checkpointing to proceed in an incremental fashion without an explicit undo at the time of recovery. The recoverable distributed shared virtual memory allows the system to restart computation from a checkpoint without a global restart.>

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

This paper describes the application of the Object-Oriented Design of Reliable/Reconfigurable Architectures (OODRA) workbench to the performance simulation of an adaptive digital beamforming architecture. The performance effects due to chip partitioning and reconfiguration for fault tolerance and yield enhancement are presented. The experiments described illustrate the flexibility of the OODRA work-bench in architectural-level performance evaluation of algorithm-specific reconfigurable architectures.

The authors investigate wafer probing strategies for the diagnosis of repairable VLSI and WSI (wafer scale integration) structures based on integrated diagnosis and repair. Knowledge of the repair strategy, the probability of each unit being good, and the expected test time each unit are used by the diagnosis algorithm to select units for wafer probe testing. The general problem is described followed by an examination of a specific case. Wafer probe diagnosis of k-out-of-n systems is analyzed and optimal diagnosis algorithms are derived. A compact representation of the optimal diagnosis scheme which needs O(n/sup 2/) space and can be generated in O(n/sup 2/) time is described.>

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces for these simulations is a difficult problem for single processors and particularly for multicomputers. Even when existing trace methods can be used on multicomputers, the amount of collected data typically grows with the number of processors, so I/O and trace storage costs increase. A new technique is presented in this paper which modifies the executable code to dynamically collect the address trace from the user code and analyzes this trace during the execution of the program. This method helps resolve the I/O and storage problems and facilitates parallel analysis of the address trace. If a trace stored on disk is desired, the generated trace information can also be written to files during execution, with a resultant drop in program execution speed. An initial implementation on the Intel iPSC/2 hypercube multicomputer is detailed, and sample simulation results are presented. The effect of this trace collection method on execution time is illustrated.

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

Two linked data structures utilizing virtual backpointers, the virtual double-linked list (VDLL) and the B-tree with virtual backpointers (VBT), are described. Four experiments that provide example measurements of the capabilities (behavior under multiple error conditions) and performance (time overhead) of both local concurrent error detection and correction using sample VDLL and VBT instances are described. For these structures, double errors within a fixed-size checking window can be detected in constant time, and single errors detected during forward moves can be corrected in constant time.>

Examines the problem of reliable storage reclamation in a distributed object-oriented system. A distributed algorithm is proposed that utilizes a modified reference counting strategy for intermode pointers and mark-and-sweep for local garbage collection. The algorithm allows nodes to fail in a failstop manner, in which case the global garbage collection functions in a gracefully degraded mode of operation. Compaction of objects is supported and object locality is exploited to reduce overhead.>

A technique that uses the concepts of the checking window and the virtual backpointer is presented. The checking window was used to define the locality in which local concurrent error detection and correction are performed, and also to state specifically the size of that locality. The virtual backpointer was used to construct two new data structures: the virtual double-linked list, which requires the same storage as the standard double-linked list, and the B-tree with virtual-backpointers of order m, which requires m+4 extra fields per node. For these structures, double errors can be detected in constant time and single errors detected during forward moves can be corrected in constant time.>

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

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

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

An approach to the design of reconfigurable tree architectures is presented in which spare processors are allocated at the leaves. The approach is unique in that spares are associated with subtrees and sharing of spares between these subtrees can occur. The Subtree Oriented Fault Tolerance (SOFT) approach is more reliable than previous approaches capable of tolerating link and switch failures for both single-chip and multichip tree implementations while reducing redundancy in terms of both spare processors and links. VLSI layout is O(n) for binary trees and is directly extensible to N-ary trees and fault tolerance through performance degradation.

This paper proposes a new representation of nets for gate matrix layout, called dynamic-net-lists. The dynamic-net-list representation is better suited for layout optimization than the traditional fixed-net-list since with it net-bindings can be delayed until the gate-ordering has been constructed. Based on dynamic-net-lists, an efficient modified min-net-cut algorithm has been developed to solve the gate ordering problem for gate matrix layout. This new approach is shown through theoretical analysis and experimental results to reduce the number of horizontal tracks and hence the area significantly. The time complexity of the algorithm is O(N log N), where N is the total number of transistors and gate-net contacts. It is also shown that an ideal min-net-cut algorithm for optimal gate matrix layout with n gate signals is at worst a log-n approximation algorithm and is conjectured to be a relative approximation algorithm.

This paper examines the problem of comparing large replicated files in a context in which communication dominates the cost of comparison. A low-cost checking matrix is proposed for comparison of these replicated files. The checking matrix is composed of check symbols generated by a divide-and-conquer encoding algorithm. The matrix allows for detection and diagnosis of disagreeing pages with very little communication overhead. In contrast to a previous O(N) proposal, the storage requirement for the checking matrix is O(log N), where N is the number of pages in the file. The matrix can be stored in main memory without the need for extra accesses to disk during normal updates of pages.

The issue of yield degradation due to physical failures in large memory and processor arrays is of significant importance to semiconductor manufacturers. One method of increasing the yield for iterated arrays of memory cells or processing elements is by incorporating spare rows and columns in the die or wafer which can be programmed into the array. This paper addresses the issue of computer-aided design approaches to optimal reconfiguration of such arrays. The paper presents the first formal analysis of the problem. The complexity of optimal reconfiguration is shown to be NP-complete for rectangular arrays utilizing spare rows and columns. In contrast to previously proposed exhaustive search and greedy algorithms, this paper develops a heuristic branch and bound approach based on the complexity analysis, which allows for flexible and highly efficient reconfiguration. Initial screening is performed by a bipartite graph matching algorithm.

This paper describes a variety of fault and error models which are used as the basis for designing fault-tolerant Very Large Scale Integrated (VLSI) systems. The fault models describe physical defects and failures and the input patterns which will expose them, and are suitable for testing, while error models describe the effects on the functional outputs of defects and are useful for on-line error detection. The models are described at various levels of abstraction. The differences between fault and error models for identical functional modules are also illustrated.

Comprehensive VLSI fault models are proposed for three broad classes of interconnection networks between multiple processors and multiple memory modules. System-level algorithms are given for concurrent detection of errors produced by these faults during the normal use of the networks. The proposed algorithms are shown to be applicable to the three classes of interconnection networks with minimal changes in their classical design. The algorithms are appropriate for the broad classes of permanent and transient faults predominant in dense VLSI and wafer-scale integration with a minimal amount of network redundancy required for implementation.