Computation Structures (MIT Electrical Engineering and Computer Science)

Developed as the text for the basic computer architecture course at MIT, Computation Structures integrates a thorough coverage of digital logic design with a comprehensive presentation of computer architecture. It contains a wealth of information for those who design computers or work with computer systems, spanning the entire range of topics from analog circuit design to operating systems. Ward and Halstead seek to demystify the construction of computing hardware by illustrating systematically how it is built up from digital circuits through higher level components to processors and memories, and how its design is affected by its intended uses. Computation Structures is unusually broad in scope, considering many real world problems and tradeoff decisions faced by practicing engineers. These difficult choices are confronted and given careful attention throughout the book. Topics addressed include the digital abstraction; digital representations and notation; combinational devices and circuits; sequence and state; synthesis of digital systems; finite state machines; control structures and disciplines; performance measures and tradeoffs; communication; interpretation; microinterpreter architecture; microprogramming and microcode; single sequence machines; stack architectures; register architectures; reduced instruction set computers; memory architectures; processes and processor multiplexing; process synchronization; interrupts, priorities, and real time; directions and trends. Stephen A. Ward and Robert H. Halstead are both Associate Professors of Computer Science and Electrical Engineering at MIT. Computation Structures is included in the MIT Electrical Engineering and Computer Science series. 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

Developed as the text for the basic computer architecture course at MIT, Computation Structures integrates a thorough coverage of digital logic design with a comprehensive presentation of computer architecture. It contains a wealth of information for those who design computers or work with computer systems, spanning the entire range of topics from analog circuit design to operating systems. Ward and Halstead seek to demystify the construction of computing hardware by illustrating systematically how it is built up from digital circuits through higher level components to processors and memories, and how its design is affected by its intended uses.Computation Structures is unusually broad in scope, considering many real world problems and tradeoff decisions faced by practicing engineers. These difficult choices are confronted and given careful attention throughout the book.Topics addressed include the digital abstraction; digital representations and notation;combinational devices and circuits; sequence and state; synthesis of digital systems; finite state machines; control structures and disciplines; performance measures and tradeoffs; communication;interpretation; microinterpreter architecture; microprogramming and microcode; single sequence machines; stack architectures; register architectures; reduced instruction set computers; memory architectures; processes and processor multiplexing; process synchronization; interrupts,priorities, and real time; directions and trends.Stephen A. Ward and Robert H. Halstead are both Associate Professors of Computer Science and Electrical Engineering at MIT. Computation Structures is included in the MIT Electrical Engineering and Computer Science series.

This book is very comprehensive, and drills deep down into the magic layers that make computers work. Anyone seriously interested in programming, and electronics should read this volume.