Introduction to Reversible Computing
Preview
Book Description
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.
Table of Contents
INTRODUCTION
Scope
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
Debugging
Source Code Control Systems
Fault Detection
Fault Tolerance
Database Transactions
Quantum Computing
Additional Applications
The Reversible Computing Spectrum
Spectrum
Partial Reversibility
Unit of Reversibility
THEORY
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
Entropy
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
Overview
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
SOFTWARE
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
Overview
Checkpointing
Reverse Computation
Unified Composite
Further Reading
Reverse C Compiler
Reversibility of C Language Programs
Source-to-Source Method for Reversible C
Normalization
Transformation
Optimization
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
Algorithms
Deletions and Memory Reclamation
Alternative Implementations
HARDWARE
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
SUMMARY
Future Directions
Phased Transition from Irreversible to Reversible
Need for Additional Progress
Outlook
REFERENCES
Bibliography
Index
Author(s)
Biography
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.