Engineering topics

Fuchs, W. K.

Publications and source records attributed to Fuchs, W. K..

27 records · Page 2

NASA NTRS1992

Database recovery using redundant disk arrays

Redundant disk arrays provide a way for achieving rapid recovery from media failures with a relatively low storage cost for large scale database systems requiring high availability. In this paper a method is proposed 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 so that the time for transaction commit processing is not degraded. 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.

Mourad, Antoine N.↗

NASA NTRS1992

Site partitioning for distributed redundant disk arrays

Distributed redundant disk arrays can be used in a distributed computing system or database system to provide recovery in the presence of temporary and permanent failures of single sites. In this paper, we look at the problem of partitioning the sites into redundant arrays in such way that the communication costs for maintaining the parity information are minimized. We show that the partitioning problem is NP-complete and we propose two heuristic algorithms for finding approximate solutions.

Mourad, Antoine N.↗

NASA NTRS1992

Address tracing of parallel systems via TRAPEDS

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces to use in these simulations, however, is a difficult problem for parallel processor architectures. A technique termed TRAPEDS modifies executable code (at the assembly language level) to dynamically collect the address trace from executing code. TRAPEDS has recently been implemented on both a hypercube multicomputer and a shared-memory multiprocessor. Particular attention is focused on strategies for efficiently and accurately collecting traces from both classes of parallel machines. The iPSC/2 hypercube multicomputer implementation traces both user and system code, and performs simulation on-the-fly to avoid large storage costs. Strategies are detailed for mitigating address trace distortion when collecting operating system traces. The Encore Multimax multiprocessor implementation uses a timer-based approach to reflect the interleaving of the processor traces and stores the traces to disc. Time and space overhead results are presented for both TRAPEDS implementations. Experimental cache simulation results derived from iPSC/2 address traces are presented to illustrate the importance of tracing operating system references.

Stunkel, Craig B.↗

NASA NTRS1991

Experimental evaluation of multiprocessor cache-based error recovery

Several variations of cache-based checkpointing for rollback error recovery 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. By simulation with address traces from parallel applications running on an Encore Multimax shared-memory multiprocessor, the performance effect of integrating the recovery schemes in the cache coherence protocol are evaluated. The results indicate that the cache-based schemes can provide checkpointing capability with low performance overhead but uncontrollable high variability in the checkpoint interval.

Janssens, Bob↗

NASA NTRS1991

Implementing forward recovery using checkpointing in distributed systems

The paper describes the implementation of a forward recovery scheme using checkpoints and replicated tasks. The implementation is based on the concept of lookahead execution and rollback validation. In the experiment, two tasks are selected for the normal execution and one for rollback validation. It is shown that the recovery strategy has nearly error-free execution time and an average redundancy lower than TMR.

Long, Junsheng↗

NASA NTRS1991

Memory management and compiler support for rapid recovery from failures in computer systems

This paper describes recent developments in the use of memory management and compiler technology to support rapid recovery from failures in computer systems. The techniques described include cache coherence protocols for user transparent checkpointing in multiprocessor systems, compiler-based checkpoint placement, compiler-based code modification for multiple instruction retry, and forward recovery in distributed systems utilizing optimistic execution.

Fuchs, W. K.↗

NASA NTRS1991

Collecting address traces from parallel computers

Trace driven simulation is a well-established method of performance analysis for single processor computer systems. However, efficient and accurate memory address tracing for parallel computer systems is not well understood. In this paper we present a critical survey of recently implemented approaches to address tracing and highlight the issues specific to collection of traces for both shared and distributed memory parallel computers. These issues include potential distortion of the relative ordering of events by the address tracing activity, realistic interleaving of addresses generated by multiple processors, and I/O and storage problems associated with collecting traces for large parallel systems. The strengths and weaknesses of the parallel tracing approaches are described.

Stunkel, Craig B.↗

NASA NTRS1987

Local concurrent error detection and correction in data structures using virtual backpointers

A new technique, based on virtual backpointers, for local concurrent error detection and correction in linked data structures is presented. Two new data structures, the Virtual Double Linked List, and the B-tree with Virtual Backpointers, are described. For these structures, double errors can be detected in 0(1) time and errors detected during forward moves can be corrected in 0(1) time. The application of a concurrent auditor process to data structure error detection and correction is analyzed, and an implementation is described, to determine the effect on mean time to failure of a multi-user shared database system. The implementation utilizes a Sequent shared memory multiprocessor system operating on a shared databased of Virtual Double Linked Lists.

Li, C. C.↗

NASA NTRS1986

Reconfiguration algorithms for tree architectures using sub-tree oriented fault tolerance

An approach to reconfiguration in tree architectures has been developed in which redundant processors are allocated at the leaves. The scheme is called sub-tree oriented fault tolerances (SOFT) and is capable of tolerating both link failures as well as multiple processor failures. In this paper, the SOFT scheme is examined from the perspective of reconfigurability. Specific algorithms are presented for reconfiguration.

Lowrie, M. B.↗