• Semester preview: Layers of abstraction
• Endianness
• Program Memory Layout (Stack, Heap, etc.)
• Compilation Steps and Object Files

• Compilation Steps and Object Files (finish)
• AT&T syntax assembly
• X86-64 calling convention
• LEA (load effective address)
• If, loop-to assembly
• X86 condition codes (start)
  • cmpq versus subq
  • testq %rax, %rax

• X86 condition codes (finish)
  • SF, ZF
• Loop-to-assembly (revisited)
• C types
• Truth in C, &&, ||
• Pointer Arithmetic

• Jump Tables
• Arrays versus Pointers
• Bit shifting
• Bitwise and/or/xor

(add deadline)

• Command Line Tips
• printf
• struct and typedef struct
• malloc, free, dynamic arrays
• Problematic things in C:
  • Unsigned/signed comparision
  • Undefined behavior and its consequences
• Bit puzzle strategies
  • Mask and shift
  • Parallelism example: any-bit-set with &

• CISC versus RISC
• Y86-64 instruction set
• Y86-64 machine code

• SEQ components
  • Registers generally and the PC
  • Instruction and data memory
  • Register file
  • MUXes
• Simple processors: nop, addq, jmp, mov

• mov CPU, continued
• HCLRS intro
  • HCLRS built-in components
  • Defining register banks
  • Wires and wire widths
  • MUXes
• Simple processors in HCLRS

• HCLRS continued
  • Built-in components
• SEQ “stages”
• Setting MUXes

• SEQ stages/MUXes finishing details
• pipelining idea (laundry example)
• latency and throughput
• register tolerances and diminishing pipelining returns

• 12pm: notes, drawing 1 2 .kra
• 3pm: notes

• Critical paths
• Pipelining addq
• addq CPU pipelined in HCL
  • HCL register naming
• SEQ to PIPE
  • Where to add registers/what registers to add?
  • Rules for programming pipeline stages
• Hazards — Data and Control
• Stalling as a Hazard Solution

(drop deadline)

• Forwarding
  • Motivation, HCL example
• Forwarding paths exercies
• Branch prediction and squashing

• Remaining problem: The Load-Use Hazard
• Implementing stalling/squashing in HCLRS
  • bubble and stall signals
• Better branch prediction ideas
• Preview: Out-of-Order, Multiple Issue Execution
• The Memory Hierarchy Idea
• Locality
  • Spatial versus Temporal
  • Examples with Loops

(withdraw deadline)

• Direct-Mapped Caches
• Tag/Index/Offset for Direct-Mapped Caches
• Set-associative caches
• Tag/Index/Offset for set-associative caches

• Replacement policies
• Write policies and write buffers
• Cache parameters and performance
  • Average memory access time (AMAT)
• C code and cache misses

• Loop reordering
• Cache blocking

• Cache blocking (con’t)
• Compiler limitations
  • Aliasing
  • Seperate compilation
  • Code Size versus Time
• Inlining
• Removing redundant operations
• Loop Unrolling

12pm: notes, drawing 1 2

3pm: notes

• Loop Unrolling (review)
• Multiple Issue, Out-of-Order CPUs
  • What instruction queues do
  • The latency bound
  • Functional/execution units
  • Multiple accumulators, reassociation
• Rotate assignment intro
  • RIDX and C macros
  • partners
• [aside] Loop Unrolling Versus Cache Blocking

• Addressing efficiency
• Vector intructions
  • What they are, examples
  • The Intel intrinsics
• Profilers
• Processes
  • Time multiplexing and measuring an empty loop
  • Contexts and context switches

• Processes continued
  • Address spaces — illusions of dedicated memory
  • Threads — illusions of dedicated CPU
  • Process = Thread(s) + Address Space
• Kinds of exceptions
• System calls
  • Linux system call calling convention and example
• Lack of consistent exception/kernel mode terms
• Virtual versus physical addresses
  • What a “4GB address space” means
• Four-page example page table example
  • Splitting addresses: page number, page offset

• Address splitting and page counting examples
• Storing/using page tables in memory
  • Memory management units location in the CPU pipeline
• Preview: single-level tables too big, memory accesses too slow
  • Remark: how 48-bit virtual addresses on 64-bit system?
• Page table lookup exercises
• Page permission bits
  • Motivation: shared read-only code
• Page table ‘tricks’ (not failing on a page fault):
  • Allocating space on demand
  • Swapping
    • Motivation: HDD/SSD performance
    • Example timeline
  • Implementing write-back policies
  • Implementing swapping replacement policies
  • Copy-on-write

• Multi-level page tables
  • Motivation: impossibly huge single-level page tables
  • Motivation: large holes
  • Two-level page table lookup
  • Note that parts of VPNs aren’t VPNs
  • Splitting addresses for multi-level tables
  • Page table lookup exercises
  • x86-64 page table structure
  • Page table space exercises

• TLBs
  • Motivation: temporal locality in PTE accesses
  • TLBs versus L1 caches
  • TLBs and the memory management unit
  • TLB layout, lookup process
  • TLB + multi-level page table address splitting exercises
  • Changing page tables and TLB invalidation

• 12pm: notes
• 3pm: notes

7PM. Physics 203.