Muutke küpsiste eelistusi

E-raamat: Introduction to Reversible Computing

5.00/5 (1 hinnangut Goodreads-ist)
(Oak Ridge National Laboratory, Knoxville, Tennessee, USA)
Teised raamatud teemal:
  • Formaat - EPUB+DRM
  • Hind: 64,99 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
  • Raamatukogudele
Introduction to Reversible ComputingSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

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.

List of Figures
xiii
List of Tables
xv
List of Algorithms
xvii
Preface xix
About the Author xxi
Acknowledgments xxiii
Book Organization xxv
I Introduction
1(30)
1 Scope
3(6)
1.1 Notions of Computing
3(1)
1.2 A Whole New Dimension
4(1)
1.3 Related Terms and Synonyms
5(2)
1.4 Similar yet Unrelated Concepts
7(2)
2 Application Areas
9(16)
2.1 General Reversible Computing Problem
9(1)
2.2 Energy-Optimal Computing
10(1)
2.3 Parallel Computing and Synchronization
11(4)
2.3.1 Asynchronous Computing
11(1)
2.3.2 Supercriticality
12(2)
2.3.3 Performance Effects
14(1)
2.4 Processor Architectures
15(2)
2.4.1 Speculative Execution
15(1)
2.4.2 Very Large Instruction Word
16(1)
2.4.3 Anti-Memoization
16(1)
2.5 Debugging
17(1)
2.6 Source Code Control Systems
18(1)
2.7 Fault Detection
19(1)
2.8 Fault Tolerance
20(2)
2.9 Database Transactions
22(1)
2.10 Quantum Computing
23(1)
2.11 Additional Applications
23(2)
3 Reversible Computing Spectrum
25(6)
3.1 Spectrum
25(2)
3.1.1 Components
25(1)
3.1.2 Common Cases
26(1)
3.2 Partial Reversibility
27(1)
3.3 Unit of Reversibility
28(3)
3.3.1 Reversing a Child's Play
28(1)
3.3.2 Reversing the Movement of Library Books
29(1)
3.3.3 Reversing Different Units of Computation
29(2)
II Theory
31(70)
4 Systems and Principles
33(16)
4.1 Logical Computations and Physical Processes
33(1)
4.2 System Theoretic View of Computation
34(6)
4.2.1 A Computation Example
35(1)
4.2.2 Basic Components of Computational Energy
35(2)
4.2.3 Dissipated Energy as Theoretical Energy Cost of Computation
37(1)
4.2.4 Theoretical Lower Bound on Dissipated Energy
37(1)
4.2.5 Reversibility for Zero Dissipated Energy
38(2)
4.3 Reversible Circuits as Bit Compressors
40(4)
4.3.1 Irreversible User Circuit within an Expanded Reversible Circuit
40(1)
4.3.2 Clean and Dirty Bits
40(1)
4.3.3 Custom Computation Circuit
41(1)
4.3.4 General-Purpose Computation Circuit
41(1)
4.3.5 Energy Cost of the Circuit
42(1)
4.3.6 Analogy with Refrigeration
42(1)
4.3.7 Reversibility in the Eye of the Beholder
43(1)
4.4 Deterministic versus Non-Deterministic Reversal
44(5)
4.4.1 Bit Erasure Cost versus Bit Reset Cost
45(1)
4.4.2 Zero Energy Cost Schemes
45(4)
5 Reversibility-Related Paradoxes
49(22)
5.1 Entropy
49(1)
5.2 Reversibility and Entropy
50(1)
5.3 Ehrenfest's Urn Model
51(4)
5.3.1 Model Configuration and Operation
51(1)
5.3.2 Analysis
52(1)
5.3.3 Forward and Reverse Algorithms
53(1)
5.3.4 System versus Computational Reversibility
53(2)
5.4 Kac-Ring Model
55(4)
5.4.1 Model Configuration and Operation
55(1)
5.4.2 Analysis
56(1)
5.4.3 Forward and Reverse Algorithms
57(1)
5.4.4 An Entropy Function
57(1)
5.4.5 System versus Computational Reversibility
57(2)
5.5 Relation to Maxwell's Demon
59(4)
5.5.1 Development
59(1)
5.5.2 Setup and Operation
60(1)
5.5.3 Operation as a Computer Program
60(1)
5.5.4 Paradox Resolution
61(2)
5.6 Relation to Other Paradoxes
63(3)
5.6.1 Loschmidt's Paradox
63(1)
5.6.2 Zermelo's Paradox
63(1)
5.6.3 Berry's Paradox
64(2)
5.7 Algorithmic Entropy
66(2)
5.7.1 Definition
66(1)
5.7.2 Non-Computability
67(1)
5.8 Further Reading
68(3)
6 Theoretical Computing Models
71(20)
6.1 Overview
71(1)
6.2 Turing Machine Model
72(1)
6.3 Sources of Irreversibility in the Turing Machine Model
73(1)
6.4 Definition of a Reversible Model
74(3)
6.4.1 Rewriting Transition Rules: Quintuples to Quadruples
75(1)
6.4.2 Adding History and Output Tapes
75(1)
6.4.3 Canonical Turing Machine Model
76(1)
6.5 Mapping Conventional Model Programs to a Reversible Model
77(2)
6.6 Universality of Computation and Its Reversal
79(1)
6.7 Space and Time Complexity of Reversible Execution
80(6)
6.7.1 Complexity of Simple Reversal with One Segment
80(1)
6.7.2 Partitioning Execution into Two Segments
80(3)
6.7.3 Partitioning Execution into g Segments
83(1)
6.7.4 Optimizing g for Minimal Total Space
83(1)
6.7.5 Generalizing the Time-Space Trade-Off
84(2)
6.8 Pebble Games
86(3)
6.8.1 Rules and Objective
86(1)
6.8.2 Analogies with the Reversible Turing Model
87(1)
6.8.3 Complexity Analysis
88(1)
6.8.4 Partial Reversibility
88(1)
6.9 Further Reading
89(2)
7 Relaxing Forward-Only Execution into Reversible Execution
91(10)
7.1 Overview of Paradigms
91(1)
7.2 Compute-Copy-Uncompute Paradigm
92(1)
7.2.1 Equivalence Conditions
92(1)
7.3 Forward-Reverse-Commit Paradigm
92(3)
7.3.1 Equivalence Conditions
93(1)
7.3.2 Sequence Conditions
94(1)
7.3.3 Sequence Examples
95(1)
7.4 Undo-Redo-Do Paradigm
95(2)
7.5 Begin-Rollback-Commit Paradigm
97(4)
III Software
101(148)
8 Reversible Programming Languages
103(24)
8.1 Role of Reversible Languages
103(2)
8.2 Language-Level Reversibility Issues
105(6)
8.2.1 Sequence and Recursive Reversal
105(1)
8.2.2 Destructive Updates
106(1)
8.2.3 Arithmetic
106(1)
8.2.4 Conditionals
107(2)
8.2.5 Loops
109(1)
8.2.6 Additional Control Flow Issues
110(1)
8.3 Procedural Languages
111(14)
8.3.1 SRL and ESRL Reversible Languages
112(1)
8.3.2 EPA Reversible Language
113(1)
8.3.3 Janus Reversible Language
114(9)
8.3.4 R Reversible Language
123(2)
8.4 Functional and Logic Languages
125(1)
8.5 Further Reading
126(1)
9 Adding Reversibility to Irreversible Programs
127(20)
9.1 Overview
127(2)
9.2 Checkpointing
129(7)
9.2.1 Full Checkpointing
129(1)
9.2.2 Periodic Checkpointing
130(1)
9.2.3 Incremental Checkpointing
131(2)
9.2.4 Differential Checkpointing
133(2)
9.2.5 Example Application
135(1)
9.3 Reverse Computation
136(8)
9.3.1 Automated: Compiler-Based
136(4)
9.3.2 Automated: Interpreter-Based
140(3)
9.3.3 Automated: Library-Based
143(1)
9.3.4 Programmer-Assisted: Source Code-Based
143(1)
9.3.5 Programmer-Assisted: Model-Based
144(1)
9.4 Unified Composite
144(2)
9.5 Further Reading
146(1)
10 Reverse C Compiler
147(30)
10.1 Reversibility of C Language Programs
148(2)
10.2 Source-to-Source Method for Reversible C
150(3)
10.2.1 Notation
151(1)
10.2.2 Definition of Correctness of Reversible Execution
151(1)
10.2.3 Runtime Tape Interface
152(1)
10.2.4 Compilation Phases
152(1)
10.3 Normalization
153(7)
10.3.1 Declarations
153(1)
10.3.2 Side-Effect Expressions
153(1)
10.3.3 Function Calls
154(1)
10.3.4 Arithmetic Expressions
154(1)
10.3.5 For Statements
154(1)
10.3.6 Do While Statements
155(1)
10.3.7 While Statements
156(1)
10.3.8 Return Statements
157(1)
10.3.9 Continue Statements
158(1)
10.3.10 Break Statements
158(1)
10.3.11 Switch Statements
158(1)
10.3.12 Post-Normalization State
159(1)
10.4 Transformation
160(8)
10.4.1 Expression Statements
160(1)
10.4.2 Function Calls
161(1)
10.4.3 Jump Statements
161(2)
10.4.4 Compound Statements
163(1)
10.4.5 Jumps across Nested Blocks
163(1)
10.4.6 If Statements
164(1)
10.4.7 Switch Statements
165(1)
10.4.8 While Statements
166(1)
10.4.9 Libraries and I/O
167(1)
10.4.10 Pragmas
168(1)
10.5 Optimization
168(5)
10.5.1 Value Recovery or Reconstruction
168(1)
10.5.2 Irreversible and Environment Slices
168(2)
10.5.3 Eliminating Reversal of Initialization
170(1)
10.5.4 Invariant Expressions
171(1)
10.5.5 Common Sub-Expression Elimination
172(1)
10.5.6 Switch Statement Trade-Offs
172(1)
10.5.7 Tape Compression
172(1)
10.6 Tape Size Upper Bounds
173(2)
10.7 Tape Size Determination
175(2)
11 Reversal of Linear Codes
177(10)
11.1 Automated Generation
177(1)
11.2 Example: Fibonacci Sequence
178(1)
11.3 General Linear Codes
179(1)
11.4 Linear Code Reversal Algorithm
179(5)
11.4.1 Preprocessing
180(1)
11.4.2 Matrix Representation
180(2)
11.4.3 Eliminating Singularity
182(2)
11.5 Fast Backward
184(1)
11.6 Other Common Linear Codes
185(2)
12 Reversible Random Number Generation
187(20)
12.1 Random Stream Traversal: Forward versus Reverse
187(2)
12.2 Memory-Based Method to Make a Generator Reversible
189(3)
12.3 Pseudorandom Numbers
192(2)
12.3.1 Forward Generation
192(1)
12.3.2 Reversible Generation
193(1)
12.4 Reversible Generation from the Uniform Distribution
194(3)
12.4.1 Open versus Closed Ranges
194(1)
12.4.2 Linear Congruential Generators
195(1)
12.4.3 Counting-Based Generators
196(1)
12.5 Reversible Generation from Invertible Cumulative Distributions
197(1)
12.6 Reversible Generation from Probability Density Functions
197(7)
12.6.1 Reversibility Problem
198(1)
12.6.2 Upper-Bounded Rejection-Based Sampling
199(3)
12.6.3 Upper- and Lower-Bounded Rejection-Based Sampling
202(2)
12.7 Further Reading
204(3)
13 Reversible Memory Allocation and Deallocation
207(6)
13.1 The Problem: Reversible Dynamic Memory
207(1)
13.2 A Simple Solution with Poor Memory Utilization
208(1)
13.3 A Memory-Efficient Solution
209(4)
13.3.1 Verification of Correctness of Allocation
210(1)
13.3.2 Verification of Correctness of Deallocation
211(2)
14 Reversible Numerical Computation
213(28)
14.1 Software and Hardware Views
213(1)
14.2 Sources of Irreversibility in Software
214(1)
14.3 Considerations in Adding Reversibility
215(1)
14.4 Defining Reversibility of Numerical Computation
216(2)
14.4.1 Software-Level Operator Reversal
216(1)
14.4.2 Operators with Constants
217(1)
14.4.3 Operation Sequence Reversal
217(1)
14.4.4 Hardware Circuit-Level Reversal
217(1)
14.5 Reversal of Basic Arithmetic Operations in Software
218(9)
14.5.1 Illustration of Basic Approach
218(1)
14.5.2 Integer Operands
219(6)
14.5.3 Floating Point Operands
225(2)
14.6 Alternative Integer Framework for Reversibility
227(10)
14.6.1 Internal Representation
227(1)
14.6.2 Encoding Certain Error Conditions
228(1)
14.6.3 Notation
229(1)
14.6.4 Signed Values and Modulo Adjustment
229(1)
14.6.5 Backward Compatibility
229(2)
14.6.6 Computing Q and R for Base v
231(1)
14.6.7 Bit Representation Examples
231(1)
14.6.8 Reversible Set of Arithmetic Operations
231(4)
14.6.9 Combined Operation: A Simple Illustration
235(2)
14.6.10 Reversal of Multiple Arithmetic Operations
237(1)
14.7 Reversal of Basic Arithmetic in Hardware
237(2)
14.8 Further Reading
239(2)
15 Reversing a Sorting Procedure
241(2)
16 Implementing Undo--Redo--Do
243(6)
16.1 Application Model
243(1)
16.2 Data Structures
244(1)
16.3 Algorithms
245(1)
16.4 Deletions and Memory Reclamation
246(1)
16.5 Alternative Implementations
247(2)
16.5.1 Undo and Redo Stacks
247(1)
16.5.2 State Recreation via Reverse Computation
247(2)
IV Hardware
249(24)
17 Reversible Logic Gates
251(10)
17.1 Basic Concepts
251(2)
17.1.1 Inadequacy of 2-Bit Gates
252(1)
17.1.2 w-Bit Gate Candidates, w ≥ 3
252(1)
17.2 3-Bit Reversible Gates
253(1)
17.3 Fredkin Gate
254(2)
17.3.1 Reversibility
254(1)
17.3.2 Universality
255(1)
17.4 Toffoli Gate
256(3)
17.4.1 Reversibility
256(1)
17.4.2 Universality
257(1)
17.4.3 Increasing the Width to w Bits
257(2)
17.5 Conservative Logic
259(1)
17.6 Synthesis of Reversible Circuits
260(1)
18 Reversible Instruction Set Architectures
261(12)
18.1 Instruction Set Issues
261(3)
18.1.1 Instruction Set for Memory Operations
262(1)
18.1.2 Instruction Set for Simple Arithmetic
262(1)
18.1.3 Instruction Set for Jumps
263(1)
18.1.4 Implementation Considerations for Jumps
264(1)
18.2 Reversible PDP-10-Like Instruction Set Architecture
264(2)
18.2.1 Memory Operations
264(1)
18.2.2 Arithmetic
265(1)
18.2.3 Branches
266(1)
18.3 Pendulum Instruction Set Architecture
266(3)
18.3.1 Memory Operations
268(1)
18.3.2 Arithmetic
268(1)
18.3.3 Branches
268(1)
18.3.4 Hardware Stacks
268(1)
18.3.5 Input/Output
269(1)
18.4 Hardware Interface to Reversible Memory
269(2)
18.5 Further Reading
271(2)
V Summary
273(6)
19 Future Directions
275(4)
19.1 Phased Transition from Irreversible to Reversible
275(1)
19.2 Need for Additional Progress
276(2)
19.3 Outlook
278(1)
References 279(14)
Index 293
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.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97810400592966e.html
Märksõnad: