Final: Required Topics

In addition to the topics required for MT1 and MT2, the following topics can be included in the final exam.

Unit 12: Heap Management

  • Memory regions of a Linux process (stack, heap, data, code).
  • Additional context for each thread (PC, stack, registers).
  • User and kernel modes; how system calls change mode.
  • API and usage of malloc, calloc, free in C.
  • Heap memory allocation in Linux with sbrk.
  • Requirements for malloc implementations.
  • Performance of malloc implementations: throughput and utilization.
  • External and internal fragmentation.
  • Implementation of an explicit free list allocator (including coalescing, boundary tags, free list management, placement, splitting) and a segregated storage/fit allocator.
  • You should be able to say what an implementation would do, given the state of the heap and a sequence of malloc/free/realloc requests.
  • Garbage collection: Reference Counting, Mark & Sweep, Stop & Copy, Generational GC

Unit 13: Linking

  • The compilation process (preprocessor, compiler, assembler, linker).
  • How to keep helper functions and variables private with static.
  • How headers, function prototypes and extern variables should be used in C to share functions and global variables among compilation units.
  • Linker symbol types (local, external, global weak and strong).
  • Common linking problems and their resolution (for example: multiple units defining a global strong symbol with the same name; function prototypes or extern variable definitions with wrong types).
  • Main ideas of relocation.
  • How static and dynamic libraries work, advantages and disadvantages.

Unit 14: Pipelined CPUs

  • Pipelining: organization (FE, DE, EX, MEM, WB), latency and throughput of an $n$-stage pipeline.
  • Pipeline hazards (structural, control, data), stalling and forwarding.
  • The case of LD + dependent instruction (which needs forwarding and stalling, together).

Unit 15: Superscalar CPUs

  • Superscalar processors.
  • Dependency graphs for code reordering.
  • Static multiple-issue CPUs (VLIW).
  • Static scheduling with loop unrolling and register renaming.
  • RAW, WAW, WAR hazard and memory dependencies.
  • Out-of-order execution in dynamic multiple-issue CPUs (Tomasulo’s algorithm).
  • Speculative execution and re-order buffer (ROB).
  • General principles behind Spectre and Meltdown attacks.

Unit 16: Cache Coherence

  • Multicore systems: symmetric shared-memory processor (SMP), distributed shared-memory system (DSM), datacenter.
  • Cache coherence problems with multicore shared-memory (SMP/DSM).
  • MSI snooping protocol (you should be able to predict the state of a block at each core after a sequence of events, as on the “MSI in Action” slides)
  • False sharing