This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/23407
Description
Title
Compiler-assisted rollback recovery
Author(s)
Li, Chung-Chi
Issue Date
1991
Doctoral Committee Chair(s)
Fuchs, W. Kent
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
