ABSTRACT
The traditional notion of forward-only execution seems to be comprehensible and acceptable quite naturally. However, when the notion of reversibility is introduced, it is not entirely intuitive as to how the forward-only notion may be relaxed to accommodate reversibility. Although many find the notion of computation easy to understand as a function y = P (x) that is applied on input bits x to obtain output bits y, a simple natural notion of how this view can be altered for reversible execution is not clear, in general. Nevertheless, based on research into using reversible computation in various contexts over the past few decades, multiple relaxations have taken shape. Among the relaxations, originally motivated by finding energy-optimal execution for reversible computing, the paradigm of Compute-Copy-Uncompute came into vogue (described later in this chapter). The application of reversible execution to synchronization problems arising from on-chip speculative execution and inter-processor virtual time synchronization resulted in the development of another paradigm, namely, Forward-Reverse-Commit. The use of a notion of reversibility in popular user-oriented applications gave rise to yet another paradigm, namely Undo-Redo-Do. These three paradigms are described next. Additional paradigms are possible, which may be discovered and developed in the future.e
In the most well-known use of reversible computing, energy loss is reduced by avoiding blind erasure of bits. This is conceptually achieved using the famous theoretical algorithm by Charles H. Bennett [Bennett, 1973] (and its later variants) whose essential operation is: compute, copy the output, and then uncompute (sometimes called the “Bennett trick” in the literature). This is the default approach that is commonly associated with classical approach to reversible computing. Given a program P , a traditional computing system executes P in forward-only mode, F (P ), and generates the desired output. A reversible computing system, utilizing a modified forward function F (P ) and its inverse R(F (P )), first executes F (P ), performs a copy operation Y (F (P )) to save the desired output, and then invokes the inverse R(F (P )) to clean up the effects of F (P ). This is illustrated in Table 7.1, and a schematic view of the control flow across all components of this paradigm is shown in Figure 7.2.
TABLE 7.1: Relaxation of Forward-Only Execution into the ComputeCopy-Uncompute Paradigm
