Introduction to Reversible Computing

Abstract

This tutorial provides an introduction to the concept of reversible computing, adopting an expanded view: in addition to a quick overview of the traditional energy-motivated hardware viewpoint, it provides an in-depth coverage of an emerging application-motivated software approach to reversible computing. It is useful for understanding different novel ways in which reversible computing offers potential in large-scale computing (such as the envisioned exa-scale developments) complementing current approaches. The significance of generalized reversible computing to future parallel processing is illustrated in the context of fault tolerance, debugging, and synchronization in future very large-scale supercomputing. The tutorial covers theory, hardware and software aspects, salient fundamental limits, complexity analyses, algorithms, and automation approaches for reversible computing. Paradigms to relax conventional forward-only programming to reversible programming will be presented, including ‘compute-copy-uncompute’ and ‘compute-rollback-commit’ paradigms for low-power computing and optimistic parallel synchronization respectively. Practical algorithms will be presented for reversibility of common operations such as dynamic memory allocation and random number generation from complex distributions. Recent results will be presented indicating the possibility of overcoming the memory wall in some applications via reliance on software-level reversible computing instead of on checkpointing. Concepts underlying the design of new reversible programming languages will be articulated, and current compilation approaches for reversible execution of existing programs will be described with an initial case study on the C language. Outstanding challenges will be identified in a wider adoption of reversible computing in parallel processing, including reversible computer arithmetic and input/output interfaces, for which a few novel directions will be presented.