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.
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.
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