Instructor Site: Original Line Drawings
This page contains our original Powerpoint line drawings for each
figure in the CS:APP2e book that you can include in your
lectures. They were later redrawn by artists in two colors for the
printed copy of the text, but these originals are complete and
accurate.
Chapter 1: A Tour of Computer Systems
- Figure 1.3: The compilation system.
- Figure 1.4: Hardware organization of a typical system.
- Figure 1.5: Reading the hello command from the keyboard.
- Figure 1.6: Loading the executable from disk into main memory.
- Figure 1.7: Writing the output string from memory to the display.
- Figure 1.8: Cache memories.
- Figure 1.9: An example of a memory hierarchy.
- Figure 1.10: Layered view of a computer system.
- Figure 1.11: Abstractions provided by an operating system.
- Figure 1.12: Process context switching.
- Figure 1.13: Process virtual address space.
- Figure 1.14: A network is another I/O device.
- Figure 1.15: Using telnet to run hello remotely over a network.
- Figure 1.16: Categorizing different processor configurations.
- Figure 1.17: Intel Core i7 organization.
- Figure 1.18: Some abstractions provided by a computer system.
Chapter 2: Representing and Manipulating Information
- Figure 2.11: Unsigned number examples for w=4.
- Figure 2.12: two's-complement number examples for w=4.
- Figure 2.15: Comparing unsigned and two's-complement representations for w=4.
- Figure 2.16: Conversion from two's complement to unsigned.
- Figure 2.17: Conversion from unsigned to two's complement.
- Figure 2.19: Examples of sign extension from w=3 to w=4.
- Figure 2.20: Integer addition.
- Figure 2.21: Relation between integer addition and unsigned addition.
- Figure 2.22: Unsigned addition.
- Figure 2.23: Relation between integer and two's-complement addition.
- Figure 2.25: Two's-complement addition.
- Figure 2.30: Fractional binary representation.
- Figure 2.31: Standard floating-point formats.
- Figure 2.32: Categories of single-precision, floating-point values.
- Figure 2.33: Representable values for six-bit floating-point format.
Chapter 3: Machine-Level Representation of Programs
- Figure 3.5: Illustration of stack operation.
- Figure 3.21: Stack frame structure.
- Figure 3.22: Illustration of call and ret functions.
- Figure 3.24: Stack frames for caller and swap_add.
- Figure 3.27: Stack frame for recursive factorial function.
- Figure 3.32: Stack organization for echo function.
- Figure 3.34: Stack organization for echo function with stack protector enabled.
- Figure 3.43: Stack frame structure for call_proc.
- Figure 3.44: Stack frame for function sfact_helper.
Chapter 4: Processor Architecture
- Figure 4.1: Y86 programmer-visible state.
- Figure 4.2: Y86 instruction set.
- Figure 4.3: Function codes for Y86 instruction set.
- Figure 4.9: Logic gate types.
- Figure 4.10: Combinational circuit to test for bit equality.
- Figure 4.11: Single-bit multiplexor circuit.
- Figure 4.12: Word-level equality test circuit.
- Figure 4.13: Word-level multiplexor circuit.
- Figure 4.14: 4-way multiplexor.
- Figure 4.15: Arithmetic/logic unit (ALU).
- Figure 4.16: Register operation.
- Figure 4.22: Abstract view of SEQ, a sequential implementation.
- Figure 4.23: Hardware structure of SEQ, a sequential implementation.
- Figure 4.25: Tracing two cycles of execution by SEQ.
- Figure 4.27: SEQ fetch stage.
- Figure 4.28: SEQ decode and write-back stage.
- Figure 4.29: SEQ execute stage.
- Figure 4.30: SEQ memory stage.
- Figure 4.31: SEQ PC update stage.
- Figure 4.32: Unpipelined computation hardware.
- Figure 4.33: Three-stage pipelined computation hardware.
- Figure 4.34: Three-stage pipeline timing.
- Figure 4.35: One clock cycle of pipeline operation.
- Figure 4.36: Limitations of pipelining due to nonuniform stage delays.
- Figure 4.37: Limitations of pipelining due to overhead.
- Figure 4.38: Limitations of pipelining due to logical dependencies.
- Figure 4.39: Shifting the timing of the PC computation.
- Figure 4.40: SEQ+ hardware structure.
- Figure 4.41: Hardware structure of PIPE-, an initial pipelined implementation.
- Figure 4.42: Example of instruction flow through pipeline.
- Figure 4.43: Pipelined execution of prog1 without special pipeline control.
- Figure 4.44: Pipelined execution of prog2 without special pipeline control.
- Figure 4.45: Pipelined execution of prog3 without special pipeline control.
- Figure 4.46: Pipelined execution of prog4 without special pipeline control.
- Figure 4.47: Pipelined execution of prog2 using stalls.
- Figure 4.48: Pipelined execution of prog4 using stalls.
- Figure 4.49: Pipelined execution of prog2 using forwarding.
- Figure 4.50: Pipelined execution of prog3 using forwarding.
- Figure 4.51: Pipelined execution of prog4 using forwarding.
- Figure 4.52: Hardware structure of PIPE, our final pipelined implementation.
- Figure 4.53: Example of load/use data hazard.
- Figure 4.54: Handling a load/use hazard by stalling.
- Figure 4.55: PIPE PC selection and fetch logic.
- Figure 4.56: PIPE decode and write-back stage logic.
- Figure 4.57: Demonstration of forwarding priority.
- Figure 4.58: PIPE execute stage logic.
- Figure 4.59: PIPE memory stage logic.
- Figure 4.60: Simplified view of ret instruction processing.
- Figure 4.61: Actual processing of the ret instruction.
- Figure 4.62: Processing mispredicted branch instructions.
- Figure 4.63: Processing invalid memory reference exception.
- Figure 4.65: Additional pipeline register operations.
- Figure 4.67: Pipeline states for special control conditions.
- Figure 4.68: PIPE pipeline control logic.
- Figure 4.69: Execute and memory stages capable of load forwarding.
Chapter 5: Optimizing Program Performance
- Figure 5.2: Performance of prefix-sum functions.
- Figure 5.3: Vector abstract data type.
- Figure 5.8: Comparative performance of lowercase conversion routines.
- Figure 5.11: Block diagram of a modern processor.
- Figure 5.13: Graphical representation of inner-loop code for combine4.
- Figure 5.14: Abstracting combine4 operations as data-flow graph.
- Figure 5.15: Data-flow representation of computation by n iterations by the inner loop of combine4.
- Figure 5.17: CPE performance for different degrees of loop unrolling.
- Figure 5.18: Graphical representation of inner-loop code for combine5.
- Figure 5.19: Abstracting combine5 operations as data-flow graph.
- Figure 5.20: Data-flow representation of combine5 operating on a vector of length n.
- Figure 5.22: CPE performance for k-way loop unrolling with k-way parallelism.
- Figure 5.23: Graphical representation of inner-loop code for combine6.
- Figure 5.24: Abstracting combine6 operations as data-flow graph.
- Figure 5.25: Data-flow representation of combine6 operating on a vector of length n.
- Figure 5.27: CPE performance for k-way loop unrolling with reassociation.
- Figure 5.28: Graphical representation of inner-loop code for combine7.
- Figure 5.29: Abstracting combine7 operations as data-flow graph.
- Figure 5.30: Data-flow representation of of combine7 operating on a vector of length n.
- Figure 5.33: Code to write and read memory locations, along with illustrative executions.
- Figure 5.34: Detail of load and store units.
- Figure 5.35: Graphical representation of inner-loop code for write_read.
- Figure 5.36: Abstracting the operations for write_read.
- Figure 5.37: Data-flow representation of function write_read.
- Figure 5.38: Profile results for different versions of n-gram frequency counting program.
Chapter 6: The Memory Hierarchy
- Figure 6.1: Inverted pendulum.
- Figure 6.3: High-level view of a 128-bit 16 x 8 DRAM chip.
- Figure 6.4: Reading the contents of a DRAM supercell.
- Figure 6.5: Reading the contents of a memory module.
- Figure 6.6: Example bus structure that connects the CPU and main memory.
- Figure 6.7: Memory read transaction for a load operation: movl A,%eax.
- Figure 6.8: Memory write transaction for a store operation: movl %eax,A.
- Figure 6.9: Disk geometry.
- Figure 6.10: Disk dynamics.
- Figure 6.11: Example bus structure that connects the CPU, main memory, and I/O devices.
- Figure 6.12: Reading a disk sector.
- Figure 6.15: Solid state disk (SSD).
- Figure 6.18: The increasing gap between disk, DRAM, and CPU speeds.
- Figure 6.23: The memory hierarchy.
- Figure 6.24: The basic principle of caching in a memory hierarchy.
- Figure 6.26: Typical bus structure for cache memories.
- Figure 6.27: General organization of cache (S, E, B, m).
- Figure 6.29: Direct-mapped cache (E = 1).
- Figure 6.30: Set selection in a direct-mapped cache.
- Figure 6.31: Line matching and word selection in a direct-mapped cache.
- Figure 6.33: Why caches index with the middle bits.
- Figure 6.34: Set associative cache (1 < E < C/B).
- Figure 6.35: Set selection in a set associative cache.
- Figure 6.36: Line matching and word selection in a set associative cache.
- Figure 6.37: Fully associative cache (E = C/B).
- Figure 6.38: Set selection in a fully associative cache.
- Figure 6.39: Line matching and word selection in a fully associative cache.
- Figure 6.40: Intel Core i7 cache hierarchy.
- Figure 6.43: The memory mountain.
- Figure 6.44: Ridges of temporal locality in the memory mountain.
- Figure 6.45: A slope of spatial locality.
- Figure 6.48: Core i7 matrix multiply performance.
Chapter 7: Linking
- Figure 7.2: Static linking.
- Figure 7.3: Typical ELF relocatable object file.
- Figure 7.7: Linking with static libraries.
- Figure 7.11: Typical ELF executable object file.
- Figure 7.13: Linux run-time memory image.
- Figure 7.15: Dynamic linking with shared libraries.
Chapter 8: Exceptional Control Flow
- Figure 8.1: Anatomy of an exception.
- Figure 8.2: Exception table.
- Figure 8.3: Generating the address of an exception handler.
- Figure 8.5: Interrupt handling.
- Figure 8.6: Trap handling.
- Figure 8.7: Fault handling.
- Figure 8.8: Abort handling.
- Figure 8.12: Logical control flows.
- Figure 8.13: Process address space.
- Figure 8.14: Anatomy of a process context switch.
- Figure 8.16: Examples of fork programs and their process graphs.
- Figure 8.19: Organization of an argument list.
- Figure 8.20: Organization of an environment variable list.
- Figure 8.21: Typical organization of the user stack when a new program starts.
- Figure 8.26: Signal handling.
- Figure 8.27: Foreground and background process groups.
Chapter 9: Virtual Memory
- Figure 9.1: A system that uses physical addressing.
- Figure 9.2: A system that uses virtual addressing.
- Figure 9.3: How a VM system uses main memory as a cache.
- Figure 9.4: Page table.
- Figure 9.5: VM page hit.
- Figure 9.6: VM page fault (before).
- Figure 9.7: VM page fault (after).
- Figure 9.8: Allocating a new virtual page.
- Figure 9.9: How VM provides processes with separate address spaces.
- Figure 9.10: Using VM to provide page-level memory protection.
- Figure 9.12: Address translation with a page table.
- Figure 9.13: Operational view of page hits and page faults.
- Figure 9.14: Integrating VM with a physically addressed cache.
- Figure 9.15: Components of a virtual address that are used to access the TLB.
- Figure 9.16: Operational view of a TLB hit and miss.
- Figure 9.17: A two-level page table hierarchy.
- Figure 9.18: Address translation with a k-level page table.
- Figure 9.19: Addressing for small memory system.
- Figure 9.20: TLB, page table, and cache for small memory system.
- Figure 9.21: The Core i7 memory system.
- Figure 9.22: Summary of Core i7 address translation.
- Figure 9.23: Format of level 1, level 2, and level 3 page table entries.
- Figure 9.24: Format of level 4 page table entries.
- Figure 9.25: Core i7 page table translation.
- Figure 9.26: The virtual memory of a Linux process.
- Figure 9.27: How Linux organizes virtual memory.
- Figure 9.28: Linux page fault handling.
- Figure 9.29: A shared object.
- Figure 9.30: A private copy-on-write object.
- Figure 9.31: How the loader maps the areas of the user address space.
- Figure 9.32: Visual interpretation of mmap arguments.
- Figure 9.33: The heap.
- Figure 9.34: Allocating and freeing blocks with malloc and free.
- Figure 9.35: Format of a simple heap block.
- Figure 9.36: Organizing the heap with an implicit free list.
- Figure 9.37: Splitting a free block to satisfy a three-word allocation request.
- Figure 9.38: An example of false fragmentation.
- Figure 9.39: Format of heap block that uses a boundary tag.
- Figure 9.40: Coalescing with boundary tags.
- Figure 9.42: Invariant form of the implicit free list.
- Figure 9.48: Format of heap blocks that use doubly linked free lists.
- Figure 9.49: A garbage collector's view of memory as a directed graph.
- Figure 9.50: Integrating a conservative garbage collector and a C malloc package.
- Figure 9.52: Mark and sweep example.
- Figure 9.53: Left and right pointers in a balanced tree of allocated blocks.
Chapter 10: System-Level I/O
- Figure 10.11: Typical kernel data structures for open files.
- Figure 10.12: File sharing.
- Figure 10.13: How a child process inherits the parent's open files.
- Figure 10.14: Kernel data structures after redirecting standard output by calling dup2(4,1).
- Figure 10.15: Relationship between Unix I/O, standard I/O, and RIO.
Chapter 11: Network Programming
- Figure 11.1: A client-server transaction.
- Figure 11.2: Hardware organization of a network host.
- Figure 11.3: Ethernet segment.
- Figure 11.4: Bridged Ethernet segments.
- Figure 11.5: Conceptual view of a LAN.
- Figure 11.6: A small internet.
- Figure 11.7: How data travels from one host to another on an internet.
- Figure 11.8: Hardware and software organization of an Internet application.
- Figure 11.10: Subset of the Internet domain name hierarchy.
- Figure 11.13: Anatomy of an Internet connection
- Figure 11.14: Overview of the sockets interface.
- Figure 11.18: The roles of the listening and connected descriptors.
Chapter 12: Concurrent Programming
- Figure 12.1: Step 1: Server accepts connection request from client.
- Figure 12.2: Step 2: Server forks a child process to service the client.
- Figure 12.3: Step 3: Server accepts another connection request.
- Figure 12.4: Step 4: Server forks another child to service the new client.
- Figure 12.7: State machine for a logical flow in a concurrent event-driven echo server.
- Figure 12.12: Concurrent thread execution.
- Figure 12.17: Assembly code for the counter loop (lines...--...) in badcnt.c.
- Figure 12.19: Progress graph for the first loop iteration of badcnt.c.
- Figure 12.20: An example trajectory.
- Figure 12.21: Safe and unsafe trajectories.
- Figure 12.22: Using semaphores for mutual exclusion.
- Figure 12.23: Producer-consumer problem.
- Figure 12.27: Organization of a prethreaded concurrent server.
- Figure 12.30: Relationships between the sets of sequential, concurrent, and parallel programs.
- Figure 12.33: Performance of the program in Figure... on a multi-core machine with four cores.
- Figure 12.37: Relationships between the sets of reentrant, thread-safe, and non-thread-safe functions.
- Figure 12.42: Progress graph for a program that can deadlock.
- Figure 12.43: Progress graph for a deadlock-free program.
Appendix A: Error Handling
