Skip to Content

Introduction to Reversible Computing

By Kalyan S. Perumalla

Chapman and Hall/CRC – 2013 – 325 pages

Series: Chapman & Hall/CRC Computational Science

Purchasing Options:

  • Add to CartHardback: $89.95
    978-1-43-987340-3
    September 10th 2013

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.

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 Bio

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.

Name: Introduction to Reversible Computing (eBook)Chapman and Hall/CRC 
Description: By Kalyan S. Perumalla. 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...
Categories: Supercomputing, Algorithms & Complexity, Computational Numerical Analysis