Perumalla, Kalyan S. 　著

目次

INTRODUCTIONScope 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 SynchronizationProcessor ArchitecturesDebugging Source Code Control Systems Fault Detection Fault ToleranceDatabase Transactions Quantum Computing Additional Applications The Reversible Computing Spectrum SpectrumPartial Reversibility Unit of Reversibility THEORY Systems and Principles Logical Computations and Physical Processes System Theoretic View of ComputationReversible Circuits as Bit CompressorsDeterministic versus Non-Deterministic Reversal Reversibility-Related Paradoxes Entropy Reversibility and Entropy Ehrenfest’s Urn ModelKac-ring ModelRelation to Maxwell’s DemonRelation to Other Paradoxes Algorithmic EntropyFurther Reading Theoretical Computing Models Overview Turing Machine Model Sources of Irreversibility in the Turing Machine Model Definition of a Reversible ModelMapping Conventional Model Programs to a Reversible Model Universality of Computation and Its Reversal Space and Time Complexity of Reversible ExecutionPebble GamesFurther 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 SOFTWAREReversible Programming Languages The Role of Reversible Languages Language-Level Reversibility IssuesProcedural LanguagesFunctional and Logic LanguagesFurther Reading Adding Reversibility to Irreversible Programs Overview CheckpointingReverse ComputationUnified CompositeFurther Reading Reverse C Compiler Reversibility of C Language Programs Source-to-Source Method for Reversible CNormalizationTransformationOptimizationTape 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 DistributionsReversible 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 ComputationReversal of Basic Arithmetic Operations in Software Alternative Integer Framework for ReversibilityReversal of Basic Arithmetic in HardwareFurther Reading Reversing a Sorting Procedure Implementing Undo-Redo-Do Application Model Data Structures Algorithms Deletions and Memory Reclamation Alternative Implementations HARDWAREReversible Logic GatesBasic 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 SUMMARYFuture Directions Phased Transition from Irreversible to Reversible Need for Additional Progress Outlook REFERENCES Bibliography Index