Computation structures

Computation Structures (ISBN:0262231395)......Page
Front Matter......Page CS_Page_004.djvu
cover......Page CS300c.djvu
Copyright......Page CS_Page_005.djvu
Contents......Page CS_Page_006.djvu
Preface......Page CS_Page_016.djvu
1 The Digital Abstraction......Page CS_Page_024.djvu
1.1 Information and the Digital Abstraction......Page CS_Page_025.djvu
1.2 Representation of Discrete Variables......Page CS_Page_026.djvu
1.3 Combinational Devices......Page CS_Page_027.djvu
1.4 The Static Discipline: Logic Levels......Page CS_Page_028.djvu
1.5 Rate of Information Flow......Page CS_Page_030.djvu
1.6 Transitions and Validity......Page CS_Page_031.djvu
1.8 DigitalCircuit Implementation......Page CS_Page_032.djvu
1.10 Context......Page CS_Page_047.djvu
1.11 Problems......Page CS_Page_048.djvu
2 Binary Representations and Notation......Page CS_Page_056.djvu
2.1 Representation of Numbers......Page CS_Page_057.djvu
2.2 FloatingPoint Representations......Page CS_Page_062.djvu
2.3 Other Representations......Page 62
2.4 HeXadecimal Notation......Page CS_Page_063.djvu
2.5 *Unrepresentable Values......Page CS_Page_064.djvu
2.6 Error Detection and Correction......Page CS_Page_065.djvu
2.8 Problems......Page CS_Page_067.djvu
3.1 Boolean Functions and Truth Tables......Page CS_Page_070.djvu
3.2 Elementary Gate Circuits......Page CS_Page_074.djvu
3.3 Synthesis of Logic Circuits......Page CS_Page_077.djvu
3.4 Temporal Considerations in Combinational Circuits......Page CS_Page_084.djvu
3.6 Problems......Page CS_Page_089.djvu
4 Sequences and State......Page CS_Page_098.djvu
4.1 Feedback and State......Page CS_Page_099.djvu
4.2 Latches, FlipFlops, and Registers......Page CS_Page_101.djvu
4.3 Edge-Triggered Flip-Flops and Registers......Page CS_Page_106.djvu
4.4 Register Timing......Page CS_Page_108.djvu
4.5 Models of Sequential Circuits......Page CS_Page_109.djvu
4.6 Synchronization and State......Page CS_Page_116.djvu
4.8 Problems......Page CS_Page_123.djvu
5.1 Building Blocks for Logic Design......Page CS_Page_128.djvu
5.2 Regular Structures......Page CS_Page_142.djvu
5.3 Design Example: A Combinational Multiplier......Page CS_Page_153.djvu
5.5 Problems......Page CS_Page_157.djvu
6 FiniteState Machines......Page CS_Page_166.djvu
6.1 Synthesis of FiniteState Machines......Page CS_Page_168.djvu
6.2 Synchronous FSM Circuit Models......Page CS_Page_169.djvu
6.4 *Equivalence of FSMs......Page CS_Page_171.djvu
6.5 *Regular Expressions and Nondeterministic FSMs......Page CS_Page_174.djvu
6.6 Context......Page CS_Page_177.djvu
6.7 Problems......Page CS_Page_178.djvu
7 Control Structures and Disciplines......Page CS_Page_194.djvu
7.1 Timing Disciplines......Page CS_Page_195.djvu
7.2 Degrees of Synchrony......Page CS_Page_196.djvu
7.3 Constraints on Control Structure......Page CS_Page_200.djvu
7.4 Synchronous GloballyTimed Control......Page CS_Page_210.djvu
7.5 Synchronous Locally Timed Control......Page CS_Page_213.djvu
7.6 Asynchronous Locally Timed Control......Page CS_Page_214.djvu
7.7 Context......Page CS_Page_219.djvu
7.8 Problems......Page CS_Page_220.djvu
8 Performance Measures and Trade-offs......Page CS_Page_224.djvu
8.1 Pipelining......Page CS_Page_227.djvu
8.2 Systematic Pipeline Construction......Page CS_Page_233.djvu
8.3 Cost-Performance Trade-offs and Options......Page CS_Page_235.djvu
8.4 Implementations of Bubble Sort......Page CS_Page_236.djvu
8.5 More Efficient Sorting Algorithms......Page CS_Page_244.djvu
8.6 Summary......Page CS_Page_247.djvu
8.7 Context......Page CS_Page_248.djvu
8.8 Problems......Page CS_Page_249.djvu
9.1 Physical Limits and Constraints......Page CS_Page_260.djvu
9.2 Communication Buses......Page CS_Page_268.djvu
9.3 Serial Communication......Page CS_Page_283.djvu
9.4 Context......Page CS_Page_287.djvu
9.5 Problems......Page CS_Page_288.djvu
10.1 Turing Machines and Computability......Page CS_Page_292.djvu
10.2 Universality......Page CS_Page_295.djvu
10.3 Uncomputable Functions......Page CS_Page_297.djvu
10.4 Interpretation versus Compilation......Page CS_Page_298.djvu
10.5 Context......Page CS_Page_300.djvu
10.6 Problems......Page CS_Page_301.djvu
11 Microinterpreter Architecture......Page CS_Page_304.djvu
11.1 Data Paths versus Control......Page CS_Page_305.djvu
11.2 A Basic Data-Path Architecture......Page CS_Page_306.djvu
11.3 Typical Data-Path Subsystems and Uses......Page CS_Page_310.djvu
11.4 Control Subsystem......Page CS_Page_316.djvu
11.5 The Control Machine as an Interpreter......Page CS_Page_321.djvu
11.7 Problems......Page CS_Page_322.djvu
12 Microprogramming and Microcode......Page CS_Page_326.djvu
12.1 Microcode Semantics......Page CS_Page_327.djvu
12.2 Symbolic Microprogramming......Page CS_Page_335.djvu
12.3 Microcoding Examples......Page CS_Page_342.djvu
12.6 Problems......Page CS_Page_348.djvu
13.1 Machine Language as an Abstraction......Page CS_Page_358.djvu
13.2 Gross Organization of the Single-Sequence Machine......Page CS_Page_359.djvu
13.3 Influences on Machine-Language Design......Page CS_Page_360.djvu
13.4 Implementation Considerations......Page CS_Page_376.djvu
13.5 The von Neumann Machine......Page CS_Page_379.djvu
13.6 Perspectives and Trends......Page CS_Page_385.djvu
13.7 Context......Page CS_Page_387.djvu
13.8 Problems......Page CS_Page_389.djvu
14 Stack Architectures: The S Machine......Page CS_Page_390.djvu
14.1 Basic Instructions......Page CS_Page_391.djvu
14.2 S-Machine Instruction Coding......Page CS_Page_394.djvu
14.3 *MAYBE Implementation......Page CS_Page_395.djvu
14.4 Compilation Techniques for Stack Machines......Page CS_Page_404.djvu
14.5 Flow of Control on the S Machine......Page CS_Page_408.djvu
14.6 *Relative Addressing and Position-Independent Code......Page CS_Page_412.djvu
14.7 Stack Frames and Procedure Linkage......Page CS_Page_416.djvu
14.8 *LexicalScoping Support......Page CS_Page_423.djvu
14.9 Traps......Page CS_Page_431.djvu
14.10 Summary......Page CS_Page_434.djvu
14.12 Problems......Page CS_Page_435.djvu
15 Register Architectures: The G Machine......Page CS_Page_450.djvu
15.1 Addressing Modes......Page CS_Page_451.djvu
15.2 The G Machine......Page CS_Page_457.djvu
15.3 *MAYBE Implementation......Page CS_Page_465.djvu
15.4 Other GeneralRegister Architectures......Page CS_Page_473.djvu
15.5 Procedure Linkage......Page CS_Page_475.djvu
15.6 Register Allocation by Compilers......Page CS_Page_480.djvu
15.7 Traps......Page CS_Page_481.djvu
15.9 Summary......Page CS_Page_482.djvu
15.10 Context......Page CS_Page_483.djvu
15.11 Problems......Page CS_Page_484.djvu
16 Memory Architectures......Page CS_Page_494.djvu
16.1 Locality of Reference and Other Regularities of Memory Access......Page CS_Page_496.djvu
16.2 Interleaved Memory Modules......Page CS_Page_499.djvu
16.4 Top-of-Stack Cache......Page CS_Page_501.djvu
16.5 Multilevel Memory......Page CS_Page_502.djvu
16.6 Cache Memory......Page CS_Page_503.djvu
16.7 Paging and Virtual Memory......Page CS_Page_509.djvu
16.9 Context......Page CS_Page_519.djvu
16.10 Problems......Page CS_Page_520.djvu
17 ReducedInstructionSet Computers......Page CS_Page_536.djvu
17.1 Basic Data Pipeline......Page CS_Page_537.djvu
17.2 Pipeline Timing......Page CS_Page_539.djvu
17.3 Interface Issues......Page CS_Page_542.djvu
17.4 Instruction-Stream Constants......Page CS_Page_543.djvu
17.5 Instruction Fetch and Branch Control......Page CS_Page_545.djvu
17.6 Main-Memory Timing Conflict......Page CS_Page_548.djvu
17.7 Impact of Lengthened Pipeline......Page CS_Page_551.djvu
17.8 Alternatives and Issues......Page CS_Page_552.djvu
17.10 Context......Page CS_Page_553.djvu
17.11 Problems......Page CS_Page_554.djvu
18 Processes and Processor Multiplexing......Page CS_Page_556.djvu
18.1 The Process Abstraction......Page CS_Page_557.djvu
18.2 Process Management......Page CS_Page_560.djvu
18.3 Operating-System Services......Page CS_Page_562.djvu
18.4 Memory Mapping......Page CS_Page_567.djvu
18.5 Protection......Page CS_Page_571.djvu
18.6 Summary......Page CS_Page_572.djvu
18.8 Problems......Page CS_Page_573.djvu
19.1 ProcessSynchronization Constraints......Page CS_Page_582.djvu
19.2 Semaphores and Precedence Constraints......Page CS_Page_583.djvu
19.4 Semaphores for Mutual Exclusion......Page CS_Page_584.djvu
19.5 Producer-Consumer Synchronization......Page CS_Page_586.djvu
19.7 Implementing Semaphores......Page CS_Page_588.djvu
19.8 Deadlock......Page CS_Page_596.djvu
19.10 Context......Page CS_Page_599.djvu
19.11 Problems......Page CS_Page_600.djvu
20 Interrupts, Priorities, and Real Time......Page CS_Page_610.djvu
20.1 Mutual-Exclusion Requirements......Page CS_Page_613.djvu
20.2 Enable/Disable Mechanism......Page CS_Page_614.djvu
20.3 Interrupts and Stack Discipline......Page CS_Page_615.djvu
20.4 Implementation of Interrupts......Page CS_Page_616.djvu
20.5 Weak Priorities......Page CS_Page_617.djvu
20.6 Processor Priorities......Page CS_Page_618.djvu
20.7 Scheduling and Priority Assignments......Page CS_Page_619.djvu
20.8 Summary......Page CS_Page_622.djvu
20.9 Context......Page CS_Page_623.djvu
20.10 Problems......Page CS_Page_624.djvu
21 Architectural Horizons......Page CS_Page_628.djvu
21.1 Models of Computation......Page CS_Page_629.djvu
21.2 The Multiprocessor Challenge......Page CS_Page_631.djvu
21.3 Taxonomy of Multiprocessors......Page CS_Page_635.djvu
21.4 Hiding Parallelism: Concurrent SSM EXecution......Page CS_Page_636.djvu
21.5 Data Parallelism......Page CS_Page_637.djvu
21.6 Other SIMD Approaches......Page CS_Page_638.djvu
21.7 SharedMemory Multiprocessors......Page CS_Page_639.djvu
21.8 Distribution of Subcomputations......Page CS_Page_643.djvu
21.9 Summary......Page CS_Page_644.djvu
21.10 Context......Page CS_Page_645.djvu
A1.1 Simple Data Types and Declarations......Page CS_Page_648.djvu
A1.2 Expressions......Page CS_Page_649.djvu
A1.3 Statements and Programs......Page CS_Page_651.djvu
A1.4 Arrays and Pointers......Page CS_Page_654.djvu
A1.5 Structures......Page CS_Page_656.djvu
A2.1 Control-ROM Bit Fields......Page CS_Page_660.djvu
A2.2 Circuit Details......Page CS_Page_663.djvu
A2.3 Microinstruction Set......Page CS_Page_671.djvu
A2.4 Control-ROM Listing......Page CS_Page_675.djvu
A2.5 Macro Definitions for Microinstructions......Page CS_Page_690.djvu
A3.1 Switch Console......Page CS_Page_694.djvu
A3.2 Microsubroutines......Page CS_Page_709.djvu
A4.1 Instruction-Set Details......Page CS_Page_718.djvu
A4.2 Language Definition......Page CS_Page_723.djvu
A4.3 Sample S-Machine Program......Page CS_Page_726.djvu
A4.4 Complete MAYBE S-Machine Microcode......Page CS_Page_727.djvu
A5.1 Instruction-Set Details......Page CS_Page_746.djvu
A5.2 Language Definition......Page CS_Page_748.djvu
A5.3 Sample G-Machine Program......Page CS_Page_751.djvu
A5.4 Complete MAYBE G-Machine Microcode......Page CS_Page_752.djvu
Bibliography......Page CS_Page_772.djvu
Index......Page CS_Page_784.djvu