1st Edition

Introduction to Reversible Computing

By Kalyan S. Perumalla Copyright 2014
    326 Pages 50 B/W Illustrations
    by Chapman & Hall

    Few books comprehensively cover the software and programming aspects of reversible computing. Filling this gap, Introduction to Reversible Computing offers an expanded view of the field that includes the traditional energy-motivated hardware viewpoint as well as the emerging application-motivated software approach.

    Collecting scattered knowledge into one coherent account, the book provides a compendium of both classical and recently developed results on reversible computing. It explores up-and-coming theories, techniques, and tools for the application of reversible computing—the logical next step in the evolution of computing systems.

    The book covers theory, hardware and software aspects, fundamental limits, complexity analyses, practical algorithms, compilers, efficiency improvement techniques, and application areas. The topics span several areas of computer science, including high-performance computing, parallel/distributed systems, computational theory, compilers, power-aware computing, and supercomputing.

    The book presents sufficient material for newcomers to easily get started. It provides citations to original articles on seminal results so that readers can consult the corresponding publications in the literature. Pointers to additional resources are included for more advanced topics. For those already familiar with a certain topic within reversible computing, the book can serve as a one-stop reference to other topics in the field.

    Notions of Computing
    A Whole New Dimension
    Related Terms and Synonyms
    Similar yet Unrelated Concepts

    Application Areas
    General Reversible Computing Problem
    Energy-Optimal Computing
    Parallel Computing and Synchronization
    Processor Architectures
    Source Code Control Systems
    Fault Detection
    Fault Tolerance
    Database Transactions
    Quantum Computing
    Additional Applications

    The Reversible Computing Spectrum
    Partial Reversibility
    Unit of Reversibility

    Systems and Principles
    Logical Computations and Physical Processes
    System Theoretic View of Computation
    Reversible Circuits as Bit Compressors
    Deterministic versus Non-Deterministic Reversal

    Reversibility-Related Paradoxes
    Reversibility and Entropy
    Ehrenfest’s Urn Model
    Kac-ring Model
    Relation to Maxwell’s Demon
    Relation to Other Paradoxes
    Algorithmic Entropy
    Further Reading

    Theoretical Computing Models
    Turing Machine Model
    Sources of Irreversibility in the Turing Machine Model
    Definition of a Reversible Model
    Mapping Conventional Model Programs to a Reversible Model
    Universality of Computation and Its Reversal
    Space and Time Complexity of Reversible Execution
    Pebble Games
    Further Reading

    Relaxing Forward-Only Execution into Reversible Execution
    Overview of Paradigms
    Compute-Copy-Uncompute Paradigm
    Forward-Reverse-Commit Paradigm
    Undo-Redo-Do Paradigm
    Begin-Rollback-Commit Paradigm

    Reversible Programming Languages

    The Role of Reversible Languages
    Language-Level Reversibility Issues
    Procedural Languages
    Functional and Logic Languages
    Further Reading

    Adding Reversibility to Irreversible Programs
    Reverse Computation
    Unified Composite
    Further Reading

    Reverse C Compiler
    Reversibility of C Language Programs
    Source-to-Source Method for Reversible C
    Tape Size Upper Bounds
    Tape Size Determination

    Reversal of Linear Codes
    Automated Generation
    Example: Fibonacci Sequence
    General Linear Codes
    Linear Code Reversal Algorithm
    Fast Backward
    Other Common Linear Codes

    Reversible Random Number Generation
    Random Stream Traversal: Forward versus Reverse
    Memory-Based Method to Make a Generator Reversible
    Pseudorandom Numbers
    Reversible Generation from the Uniform Distribution
    Reversible Generation from Invertible Cumulative Distributions
    Reversible Generation from Probability Density Functions
    Further Reading

    Reversible Memory Allocation and Deallocation
    The Problem: Reversible Dynamic Memory
    A Simple Solution with Poor Memory Utilization
    A Memory-Efficient Solution

    Reversible Numerical Computation
    Software and Hardware Views
    Sources of Irreversibility in Software
    Considerations in Adding Reversibility
    Defining Reversibility of Numerical Computation
    Reversal of Basic Arithmetic Operations in Software
    Alternative Integer Framework for Reversibility
    Reversal of Basic Arithmetic in Hardware
    Further Reading

    Reversing a Sorting Procedure

    Implementing Undo-Redo-Do
    Application Model
    Data Structures
    Deletions and Memory Reclamation
    Alternative Implementations

    Reversible Logic Gates
    Basic Concepts
    Fredkin Gate
    Toffoli Gate
    Conservative Logic
    Synthesis of Reversible Circuits

    Reversible Instruction Set Architectures
    Instruction Set Issues
    Reversible PDP-10-Like Instruction Set Architecture
    Pendulum Instruction Set Architecture
    Hardware Interface to Reversible Memory
    Further Reading

    Future Directions
    Phased Transition from Irreversible to Reversible
    Need for Additional Progress




    Kalyan Perumalla, PhD, is a senior R&D staff member and manager at Oak Ridge National Laboratory and an adjunct professor at the Georgia Institute of Technology. Dr. Perumalla is a winner of the prestigious U.S. Department of Energy Career Award in Advanced Scientific Computing Research (2010-2015). He has published over 100 articles in computing and serves on the editorial boards and program committees of leading journals and conferences in computing. He earned a PhD in computer science from the Georgia Institute of Technology. His areas of interest include reversible computing, high-performance computing, parallel discrete event simulation, and parallel combinatorial optimization.