Introduction to Reversible Computing  book cover
1st Edition

Introduction to Reversible Computing

ISBN 9781439873403
Published September 10, 2013 by Chapman & Hall
326 Pages 50 B/W Illustrations

FREE Standard Shipping
USD $200.00

Prices & shipping based on shipping country


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

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



View More



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.