Original Line Drawings and Graphs
This page contains our original Powerpoint line drawings and Excel
graphs for each figure in the CS:APP3e book. You may include them in
your lectures with attribution. They were redrawn by an artist for the
printed copy of the text, but the originals are complete and accurate.
You can also download a tarball that contains
all of the figures.
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: Multi-core processor organization.
- Figure 1.18: Some abstractions provided by a computer system.
Chapter 2: Representing and Manipulating Information
- Figure 2.12: Unsigned number examples for w=4.
- Figure 2.13: Two's-complement number examples for w=4.
- Figure 2.16: Comparing unsigned and two's-complement representations for w=4.
- Figure 2.17: Conversion from two's complement to unsigned.
- Figure 2.18: Conversion from unsigned to two's complement.
- Figure 2.20: Examples of sign extension from w=3 to w=4.
- Figure 2.21: Integer addition.
- Figure 2.22: Relation between integer addition and unsigned addition.
- Figure 2.23: Unsigned addition.
- Figure 2.24: Relation between integer and two's-complement addition.
- Figure 2.26: Two's-complement addition.
- Figure 2.31: Fractional binary representation.
- Figure 2.32: Standard floating-point formats.
- Figure 2.33: Categories of single-precision floating-point values.
- Figure 2.34: Representable values for six-bit floating-point format.
Chapter 3: Machine-Level Representation of Programs
- Figure 3.9: Illustration of stack operation.
- Figure 3.25: General stack frame structure.
- Figure 3.26: Illustration of call and ret functions.
- Figure 3.30: Stack frame structure for function proc.
- Figure 3.33: Stack frame for function call_proc.
- Figure 3.40: Stack organization for echo function.
- Figure 3.42: Stack organization for echo function with stack protector enabled.
- Figure 3.44: Stack frame structure for function vframe.
Chapter 4: Processor Architecture
- Figure 4.1: Y86-64 programmer-visible state.
- Figure 4.2: Y86-64 instruction set.
- Figure 4.3: Function codes for Y86-64 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: Simplified view of ret instruction processing.
- Figure 4.56: Processing mispredicted branch instructions.
- Figure 4.57: PIPE PC selection and fetch logic.
- Figure 4.58: PIPE decode and write-back stage logic.
- Figure 4.59: Demonstration of forwarding priority.
- Figure 4.60: PIPE execute stage logic.
- Figure 4.61: PIPE memory stage logic.
- Figure 4.62: Detailed processing of the ret instruction.
- 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.70: 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 an out-of-order processor.
- Figure 5.13: Graphical representation of inner-loop code for combine4.
- Figure 5.14: Abstracting combine4 operations as a 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 k x 1 loop unrolling.
- Figure 5.18: Graphical representation of inner-loop code for combine5.
- Figure 5.19: Abstracting combine5 operations as a data-flow graph.
- Figure 5.20: Data-flow representation of combine5 operating on a vector of length n.
- Figure 5.22: Graphical representation of inner-loop code for combine6.
- Figure 5.23: Abstracting combine6 operations as a data-flow graph.
- Figure 5.24: Data-flow representation of combine6 operating on a vector of length n.
- Figure 5.25: CPE performance of k x k loop unrolling.
- Figure 5.27: Graphical representation of inner-loop code for combine7.
- Figure 5.28: Abstracting combine7 operations as a data-flow graph.
- Figure 5.29: Data-flow representation of combine7 operating on a vector of length n.
- Figure 5.30: CPE performance for k x 1a loop unrolling.
- 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 bigram-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: movq A,%rax{
- Figure 6.8: Memory write transaction for a store operation: movq %rax{,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.13: Solid state disk (SSD).
- Figure 6.16: The gap between disk, DRAM, and CPU speeds.
- Figure 6.21: The memory hierarchy.
- Figure 6.22: The basic principle of caching in a memory hierarchy.
- Figure 6.24: Typical bus structure for cache memories.
- Figure 6.25: General organization of cache (S, E, B, m).
- Figure 6.27: Direct-mapped cache (E = 1).
- Figure 6.28: Set selection in a direct-mapped cache.
- Figure 6.29: Line matching and word selection in a direct-mapped cache.
- Figure 6.31: Why caches index with the middle bits.
- Figure 6.32: Set associative cache (1 < E < C/B).
- Figure 6.33: Set selection in a set associative cache.
- Figure 6.34: Line matching and word selection in a set associative cache.
- Figure 6.35: Fully associative cache (E = C/B).
- Figure 6.36: Set selection in a fully associative cache.
- Figure 6.37: Line matching and word selection in a fully associative cache.
- Figure 6.38: Intel Core i7 cache hierarchy.
- Figure 6.41: A memory mountain.
- Figure 6.42: Ridges of temporal locality in the memory mountain.
- Figure 6.43: A slope of spatial locality.
- Figure 6.46: Core i7 matrix multiply performance.
Chapter 7: Linking
- Figure 7.2: Static linking.
- Figure 7.3: Typical ELF relocatable object file.
- Figure 7.8: Linking with static libraries.
- Figure 7.13: Typical ELF executable object file.
- Figure 7.15: Linux x86-64 run-time memory image.
- Figure 7.16: Dynamic linking with shared libraries.
- Figure 7.18: Using the GOT to reference a global variable.
- Figure 7.19: Using the PLT and GOT to call external functions.
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: Process graph for the example program in Figure....
- Figure 8.17: Process graph for a nested fork.
- Figure 8.20: Organization of an argument list.
- Figure 8.21: Organization of an environment variable list.
- Figure 8.22: Typical organization of the user stack when a new program starts.
- Figure 8.27: Signal handling.
- Figure 8.28: Foreground and background process groups.
- Figure 8.31: Handlers can be interrupted by other handlers.
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&sweep example.
- Figure 9.53: Left and right pointers in a balanced tree of allocated blocks.
Chapter 10: System-Level I/O
- Figure 10.1: Portion of the Linux directory hierarchy.
- Figure 10.12: Typical kernel data structures for open files.
- Figure 10.13: File sharing.
- Figure 10.14: How a child process inherits the parent's open files.
- Figure 10.15: Kernel data structures after redirecting standard output by calling dup2(4,1).
- Figure 10.16: 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 travel 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.11: Anatomy of an Internet connection.
- Figure 11.12: Overview of network applications based on the sockets interface.
- Figure 11.14: The roles of the listening and connected descriptors.
- Figure 11.15: Data structure returned by getaddrinfo.
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 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.35: Performance of psum-local .
- Figure 12.39: Relationships between the sets of reentrant, thread-safe, and thread-unsafe functions.
- Figure 12.44: Progress graph for a program that can deadlock.
- Figure 12.45: Progress graph for a deadlock-free program.
Appendix A: Error Handling
