ABSTRACT
Because most programs are irreversible, reversibility must be added before they can be used in a reversible computing context. Broadly speaking, there
are two major approaches to adding reversibility to irreversible programs: checkpointing and reverse computation. Checkpointing takes snapshots of the memory while reverse computation takes snapshots of the control flow of the program. More generally, checkpointing can in fact be subsumed by reverse computation when the unit of control flow is relaxed to vary in the spectrum of reversible units from simple arithmetic operations all the way to large subroutines. When an entire code fragment, such as a subroutine, is viewed as a single operation, the entire state potentially modified by the fragment is saved as control flow information, which essentially corresponds to checkpointing of the same data. However, it is useful to keep the distinction between checkpointing and reverse computation because of the optimizations that are possible to be performed more easily for checkpointing schemes when the unit of computation is known/assumed to be sufficiently large. In a unified, composite approach, there is little in the way of theoretical feasibility to have a single tool chain that subsumes all the different approaches. The range of alternatives is shown in Figure 9.1, each of which is described next.
