Files in this item



application/pdf9210890.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Compiler-assisted rollback recovery
Author(s):Li, Chung-Chi
Doctoral Committee Chair(s):Fuchs, W. Kent
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:This thesis examines the feasibility of applying compile-time information to assist in rollback recovery. Depending on the configuration of the original system, one or more of the following three compiler capabilities are applied: (1) code insertion, (2) code analysis, and (3) code transformation.
Chapter 2 describes the compiler-assisted checkpointing approach for systems without built-in fault-tolerance features. The compiler-generated sparse potential checkpoint code is inserted in the program to maintain the desired checkpoint interval. The adaptive checkpointing technique reduces the checkpoint size for programs with large variations in memory usage. To reduce the potential checkpoint time overhead, a training technique is used to select low-cost, high-coverage potential checkpoints. This potential checkpoint selection problem is shown to be NP-complete, and a heuristic algorithm has been developed to obtain a quick suboptimal solution. These techniques have been implemented in a modified version of the GNU C (GCC) compiler.
Chapter 3 describes the concept of scalable checkpoints for hypercube programs and a compiler-assisted approach to maintaining scalable checkpoints during execution and recovery. By means of a pair of information-preserving scaling functions, a program implanted with checkpoint subroutines can achieve not only graceful degradation when one or more processors become faulty, but also gradual enhancement when another adjacent subcube of the same size becomes available. To reduce the programmer's effort, the compiler analyzes the source program to generate candidate scaling functions, which are then approved by the programmer.
Chapter 4 describes the compiler-assisted approach to providing multiple instruction rollback capability for general purpose registers. The objective is achieved by having the compiler remove all forms of N-instruction anti-dependencies. Pseudo register anti-dependencies are removed by loop protection, node splitting, and loop expansion techniques; machine register anti-dependencies are prevented by introducing anti-dependency constraints in the interference graph used by the register allocator. To support separate compilation, inter-procedural anti-dependency constraints are added to the code generator to guarantee the termination of machine register anti-dependencies across procedure boundaries. The algorithms are implemented in the IMPACT C compiler.
Issue Date:1991
Rights Information:Copyright 1991 Li, Chung-Chi
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9210890
OCLC Identifier:(UMI)AAI9210890

This item appears in the following Collection(s)

Item Statistics