go back to main content index

1 ATour Of Computer Systems

1. 1. A tour of Computer System
2. 2. Programs are translatedxd by other Programs into Different Forms
3. 3. It pays to understand How Compilation System Works
4. 4. Processors Read and Interpret instructions Stored in Memory
   • Hardware Organization of a System
   • Buses
   • I/O Devices
   • Main Memory
   • Processor
5. Running the hello Program
6. Caches Matters
7. Storage Devices Form a Hiararchy
8. The Operating System Manages the Hardware
   • Processes
   • Threads
   • Virtual Memory
   • Files
9. Systems Communicate with Other Systems Using Networks
10. Important Themes
    • Concurrency and Parallelism
    • Thread-Level Concurrency
    • Instruction-Level Parallelism
    • The Importance of Abstractions in Computer Systems
11. Summary

2. Representing and Manipulating Information

1. 1. 2.1 Information Storage
   • 2.1.1 Hexadecimal Notation
   • 2.1.2 Words
   • 2.1.3 Data Sizes
   • 2.1.4 Addressing and Byte Ordering
   • 2.1.5 Representing Strings
   • 2.1.6 Representing Code
   • 2.1.7 Introduction to Boolean Algebra
   • 2.1.8 Bit-Level Operations in C
   • 2.1.9 Logical Operations in C
   • 2.1.10 Shift Operations in C
2. 2.2 Integer Representations
   • 2.2.1 Integral Data Types
   • 2.2.2 Unsigned Encodings
   • 2.2.3.Two’s-Complement Encodings
   • 2.2.4 Conversions Between Signed and Unsigned
   • 2.2.5 Signed vs. Unsigned in C
   • 2.2.6 Expanding the Bit Representation of a Number
   • 2.2.7 Truncating Numbers
   • 2.2.8 Advice on Signed vs. Unsigned
3. 2.3 Integer Arithmetic
   • 2.3.1 Unsigned Addition
   • 2.3.2 Two’s-Complement Addition
   • 2.3.3 Two’s-Complement Negation
   • 2.3.4 Unsigned Multiplication
   • 2.3.5 Two’s-Complement Multiplication
   • 2.3.6 Multiplying by Constants
   • 2.3.7 Dividing by Powers of Two
   • 2.3.8 Final Thoughts on Integer Arithmetic
4. 2.4 Floating Point
   • 2.4.1 Fractional Binary Numbers
   • 2.4.2 IEEE Floating-Point Representation
   • 2.4.3 Example Numbers
   • 2.4.4 Rounding
   • 2.4.5 Floating-Point Operations
   • 2.4.6 Floating Point in C
5. 2.5 Summary

3. Machine-Level Representation Of Programs

1. 1. 3.1 A Historical Perspective
2. 2. 3.2 Program Encodings
   • 3. 3.2.1 Machine-Level Code
   • 4. 3.2.2 Code Examples
   • 5. 3.2.3 Notes on Formatting
3. 3.3 Data Formats
4. 3.4 Accessing Information
   • 3.4.1 Operand Specifiers
   • 3.4.2 Data Movement Instructions
   • 3.4.3 Data Movement Example
5. 3.5 Arithmetic and Logical Operations
   • 3.5.1 Load Effective Address
   • 3.5.2 Unary and Binary Operations
   • 3.5.3 Shift Operations Destination
   • 3.5.4 Discussion
   • 3.5.5 Special Arithmetic Operations
6. 3.6 Control
   • 3.6.1 Condition Codes
   • 3.6.2 Accessing the Condition Codes
   • 3.6.3 Jump Instructions and Their Encodings
   • 3.6.4 Translating Conditional Branches
   • 3.6.5 Loops
   • 3.6.6 Conditional Move Instructions
   • 3.6.7 Switch Statements
7. 3.7 Procedures
   • 3.7.1 Stack Frame Structure
   • 3.7.2 Transferring Control
   • 3.7.3 Register Usage Conventions
   • 3.7.4 Procedure Example
   • 3.7.5 Recursive Procedures
8. 3.8 Array Allocation and Access
   • 3.8.1 Basic Principles
   • 3.8.2 Pointer Arithmetic
   • 3.8.3 Nested Arrays
   • 3.8.4 Fixed-Size Arrays
   • 3.8.5 Variable-Size Arrays
9. 3.9 Heterogeneous Data Structures
   • 3.9.1 Structures
   • 3.9.2 Unions
   • 3.9.3 Data Alignment
10. 3.10 Putting It Together: Understanding Pointers
11. 3.11 Life in the Real World: Using the gdb Debugger
12. 3.12 Out-of-Bounds Memory References and Buffer Overflow
    • 3.12.1 Thwarting Buffer Overflow Attacks
    • Stack Randomization
    • Stack Corruption Detection
    • Limiting Executable Code Regions
13. 3.13 x86-64: Extending IA32 to 64 Bits
    • 3.13.1 History and Motivation for x86-64
14. 3.13.2 An Overview of x86-64
    • Data Types
    • Assembly-Code Example
15. 3.13.3 Accessing Information
    • Arithmetic Instructions
16. 3.13.4 Control
    • Procedures
    • Argument Passing
    • Stack Frames
    • Register Saving Conventions
17. 3.13.5 Data Structures
18. 3.13.6 Concluding Observations about x86-64
19. 3.14 Machine-Level Representations of Floating-Point Programs
20. 3.15 Summary

4 Processor Architecture

1. 4.1 The Y86 Instruction Set Architecture
   • 2. 4.1.1 Programmer-Visible State
   • 3. 4.1.2 Y86 Instructions
   • 4. 4.1.3 Instruction Encoding
     • Aside Comparing IA32 to Y86 instruction encodings
     • Aside RISC and CISC instruction sets
     • Aside The RISC versus CISC controversy
   • 5. 4.1.4 Y86 Exceptions
   • 6. 4.1.5 Y86 Programs
   • 7. 4.1.6 Some Y86 Instruction Details
2. 4.2 Logic Design and the Hardware Control Language HCL
   • 9. 4.2.1 Logic Gates
   • 10. 4.2.2 Combinational Circuits and HCL Boolean Expressions
   • 11. 4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions
   • 12. 4.2.4 Set Membership
   • 13. 4.2.5 Memory and Clocking
3. 4.3 Sequential Y86 Implementations
   • 15. 4.3.1 Organizing Processing into Stages
   • 16. 4.3.2 SEQ Hardware Structure
   • 17. 4.3.3 SEQ Timing
   • 18. 4.3.4 SEQ Stage Implementations
     • 19. Fetch Stage 1
     • 20. Decode and Write-Back Stages 1
     • 21. Execute Stage 1
     • 22. Memory Stage 1
     • 23. PC Update Stage
     • 24. Surveying SEQ
4. 4.4 General Principles of Pipelining
   • 26. 4.4.1 Computational Pipelines
   • 27. 4.4.2 A Detailed Look at Pipeline Operation
   • 28. 4.4.3 Limitations of Pipelining
     • 29. Nonuniform Partitioning
     • 30. Diminishing Returns of Deep Pipelining
   • 31. 4.4.4 Pipelining a System with Feedback
5. 4.5 Pipelined Y86 Implementations
   • 33. 4.5.1 SEQ+: Rearranging the Computation Stages
   • 34. 4.5.2 Inserting Pipeline Registers
   • 35. 4.5.3 Rearranging and Relabeling Signals
   • 36. 4.5.4 Next PC Prediction
   • 37. 4.5.5 Pipeline Hazards
   • 38. 4.5.6 Avoiding Data Hazards by Stalling
   • 39. 4.5.7 Avoiding Data Hazards by Forwarding
   • 40. 4.5.8 Load/Use Data Hazards
   • 41. 4.5.9 Exception Handling
   • 42. 4.5.10 PIPE Stage Implementations
     • 43. Decode and Write-Back Stage 2s
     • 44. Execute Stage 2
     • 45. Memory Stage 2
   • 46. 4.5.11 Pipeline Control Logic
     • 47. Desired Handling of Special Control Cases
     • 48. Detecting Special Control Conditions
     • 49. Pipeline Control Mechanisms
     • 50. Combinations of Control Conditions
   • 51. 4.5.12 Performance Analysis
   • 52. 4.5.13 Unfinished Business
     • 53. Multicycle Instructions
     • 54. Interfacing with the Memory System

5 Optimizing Program Performance

1. 5.1 Capabilities and Limitations of Optimizing Compilers
2. 5.2 Expressing Program Performance
3. 5.3 Program Example
4. 5.4 Eliminating Loop Inefficiencies
5. 5.5 Reducing Procedure Calls
6. 5.6 Eliminating Unneeded Memory References
7. 5.7 Understanding Modern Processors
   • 5.7.1 Overall Operation
   • 5.7.2 Functional Unit Performance
   • 5.7.3 An Abstract Model of Processor Operation
   • From Machine-Level Code to Data-Flow Graphs
   • Other Performance Factors
8. 5.8 Loop Unrolling
9. 5.9 Enhancing Parallelism
   • 5.9.1 Multiple Accumulators
   • 5.9.2 Reassociation Transformation
10. 5.10 Summary of Results for Optimizing Combining Code
11. 5.11 Some Limiting Factors
    • 5.11.1 Register Spilling
    • 5.11.2 Branch Prediction and Misprediction Penalties
      • Do Not Be Overly Concerned about Predictable Branches
      • Write Code Suitable for Implementation with Conditional Moves
12. 5.12 Understanding Memory Performance
    • 5.12.1 Load Performance
    • 5.12.2 Store Performance
13. 5.13 Life in the Real World: Performance Improvement Techniques
14. 5.14 Identifying and Eliminating Performance Bottlenecks
    • 5.14.1 Program Profiling [gprof is not available for mac]
    • 5.14.2 Using a Profiler to Guide Optimization
    • 5.14.3 Amdahl’s Law
15. 5.15 Summary

6 The Memory Hierarchy

1. 1. 6.1 Storage Technologies
   • 2. 2. 6.1.1 Random-Access Memory
     • 3. 3. Static RAM
     • 4. 4. Dynamic RAM
     • 5. 5. Conventional DRAMs
     • 6. 6. Memory Modules
     • 7. 7. Enhanced DRAMs
     • 8. 8. Nonvolatile Memory
     • 9. 9. Accessing Main Memory
   • 10. 10. 6.1.2 Disk Storage
     • 11. 11. Disk Geometry
     • 12. 12. Disk Capacity
     • 13. 13. Disk Operation
     • 14. 14. Logical Disk Blocks
     • 15. 15. Connecting I/O Devices
     • 16. 16. Accessing Disks
     • 17. 17. Anatomy of a Commercial Disk
   • 18. 18. 6.1.3 Solid State Disks
   • 19. 19. 6.1.4 Storage Technology Trends
2. 20. 6.2 Locality
   • 21. 21. 6.2.1 Locality of References to Program Data
   • 22. 22. 6.2.2 Locality of Instruction Fetches
   • 23. 23. 6.2.3 Summary of Locality
3. 24. 6.3 The Memory Hierarchy
   • 25. 25. 6.3.1 Caching in the Memory Hierarchy
     • 26. 26. Cache Hits
     • 27. 27. Cache Misses
     • 28. 28. Kinds of Cache Misses
     • 29. 29. Cache Management
   • 30. 30. 6.3.2 Summary of Memory Hierarchy Concepts
4. 31. 6.4 Cache Memories
   • 32. 32. 6.4.1 Generic Cache Memory Organization
   • 33. 33. 6.4.2 Direct-Mapped Caches
     • 34. 34. Set Selection in Direct-Mapped Caches
     • 35. 35. Line Matching in Direct-Mapped Caches
     • 36. 36. Word Selection in Direct-Mapped Caches
     • 37. 37. Line Replacement on Misses in Direct-Mapped Caches
     • 38. 38. Putting It Together: A Direct-Mapped Cache in Action
     • 39. 39. Conflict Misses in Direct-Mapped Caches
   • 40. 40. 6.4.3 Set Associative Caches
     • 41. 41. Set Selection in Set Associative Caches
     • 42. 42. Line Matching and Word Selection in Set Associative Caches
     • 43. 43. Line Replacement on Misses in Set Associative Caches
   • 44. 44. 6.4.4 Fully Associative Caches
     • 45. 45. Set Selection in Fully Associative Caches
     • 46. 46. Line Matching and Word Selection in Fully Associative Caches
   • 47. 47. 6.4.5 Issues with Writes
   • 48. 48. 6.4.6 Anatomy of a Real Cache Hierarchy
   • 49. 49. 6.4.7 Performance Impact of Cache Parameters
     • 50. 50. Impact of Cache Size
     • 51. 51. Impact of Block Size
     • 52. 52. Impact of Associativity
     • 53. 53. Impact of Write Strategy
5. 54. 6.5 Writing Cache-friendly Code
6. 55. 6.6 Putting It Together: The Impact of Caches on Program Performance
   • 56. 56. 6.6.1 The Memory Mountain
   • 57. 57. 6.6.2 Rearranging Loops to Increase Spatial Locality
   • 58. 58. 6.6.3 Exploiting Locality in Your Programs
7. 59. 6.7 Summary