Skip to content

Instantly share code, notes, and snippets.

@eevmanu

eevmanu/download-lectures.sh

Last active March 27, 2025 21:30
Show Gist options
  • Save eevmanu/32c5fa300f18190586b789ac7f2573b2 to your computer and use it in GitHub Desktop.
Save eevmanu/32c5fa300f18190586b789ac7f2573b2 to your computer and use it in GitHub Desktop.
Download ZIP
MIT 6.172 | Fall 2018 | Undergraduate Performance Engineering of Software Systems course
Raw
download-lectures.sh
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/d0c73dd51c79b95196a2e6faa824e1b4_MIT6_172F18_lec1.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-01-introduction-and-matrix-multiplication.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/1a57adbec9520270d4485b42a2e1a316_MIT6_172F18_lec2.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-02-bentley-rules-for-optimizing-work.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/cc6983c9ebd77c28e8ae85bc0e575360_MIT6_172F18_lec3.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-03-bit-hacks.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/8955b91dbd47c241fb2904c700fdb697_MIT6_172F18_lec4.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-04-assembly-language-and-computer-architecture.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/b0d1c7f457920326cef5c958237ea743_MIT6_172F18_lec5.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-05-c-to-assembly.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/cbef71a2b92bc700fbad43e69f951513_MIT6_172F18_lec6.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-06-multicore-programming.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/543e419bff1ed05b1a649115c24c44b3_MIT6_172F18_lec7.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-07-races-and-parallelism.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/5655e50541f85421cc47b7c85d8e5de3_MIT6_172F18_lec8.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-08-analysis-of-multithreaded-algorithms.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/df628b3fffb046d18f9442f01a812ccf_MIT6_172F18_lec9.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-09-what-compilers-can-and-cannot-do.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/4d7f4bb31bf1ed90c669a11867d36d36_MIT6_172F18_lec10.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-10-measurement-and-timing.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/68624442da6047731a33b3590cefd030_MIT6_172F18_lec11.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-11-storage-allocation.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/24c247c943024dcda40bcc7caa206581_MIT6_172F18_lec12.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-12-parallel-storage-allocation.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/fe9b746636bea5357ea8269fe6463020_MIT6_172F18_lec13.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-13-the-cilk-runtime-system.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/329bfc6e1808c375afa517feb3c4c273_MIT6_172F18_lec14.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-14-caching-and-cache-efficient-algorithms.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/cef17369f91d3140409f2be4ad9246a4_MIT6_172F18_lec15.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-15-cache-oblivious-algorithms.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/e4fe97d2a250b57bb1e330fba8cf5992_MIT6_172F18_lec16.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-16-nondeterministic-parallel-programming.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/fc3b846f6e13e15e4982a92369ca3825_MIT6_172F18_lec17.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-17-synchronization-without-locks.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/6cd2359235c415ad55960be2dfc7e136_MIT6_172F18_lec18.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-18-domain-specific-languages-and-autotuning.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/809f3351da7a2e5a6afc7c22e2e68e4d_MIT6_172F18_lec19.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-19-leiserchess-codewalk.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/076be084af69b7d645c30b1f337a3b08_MIT6_172F18_lec20.pdf' -o '6-172-performance-engineernig-of-software-systems-lecture-20-speculative-parallelism-and-leiserchess.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/dd989b76928a0561851e73da6d028763_MIT6_172F18_lec21.pdf' -o '6-172-performance-engineering-in-software-systems-lecture-21-tuning-a-tsp-algorithm.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/f58df934e205b870e473c2af3fe5e6f7_MIT6_172F18_lec22.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-22-graph-optimization.pdf'
curl -sSL 'https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/4dd5830c2bb4e4da2a51c5baae8accb8_MIT6_172F18_lec23.pdf' -o '6-172-performance-engineering-of-software-systems-lecture-23-high-performance-in-dynamic-languages.pdf'
Raw
join-pdfs.sh
pdfunite 6-172-performance-engineering-of-software-systems-lecture-01-introduction-and-matrix-multiplication.pdf 6-172-performance-engineering-of-software-systems-lecture-02-bentley-rules-for-optimizing-work.pdf 6-172-performance-engineering-of-software-systems-lecture-03-bit-hacks.pdf 6-172-performance-engineering-of-software-systems-lecture-04-assembly-language-and-computer-architecture.pdf 6-172-performance-engineering-of-software-systems-lecture-05-c-to-assembly.pdf 6-172-performance-engineering-of-software-systems-lecture-06-multicore-programming.pdf 6-172-performance-engineering-of-software-systems-lecture-07-races-and-parallelism.pdf 6-172-performance-engineering-of-software-systems-lecture-08-analysis-of-multithreaded-algorithms.pdf 6-172-performance-engineering-of-software-systems-lecture-09-what-compilers-can-and-cannot-do.pdf 6-172-performance-engineering-of-software-systems-lecture-10-measurement-and-timing.pdf 6-172-performance-engineering-of-software-systems-lecture-11-storage-allocation.pdf 6-172-performance-engineering-of-software-systems-lecture-12-parallel-storage-allocation.pdf 6-172-performance-engineering-of-software-systems-lecture-13-the-cilk-runtime-system.pdf 6-172-performance-engineering-of-software-systems-lecture-14-caching-and-cache-efficient-algorithms.pdf 6-172-performance-engineering-of-software-systems-lecture-15-cache-oblivious-algorithms.pdf 6-172-performance-engineering-of-software-systems-lecture-16-nondeterministic-parallel-programming.pdf 6-172-performance-engineering-of-software-systems-lecture-17-synchronization-without-locks.pdf 6-172-performance-engineering-of-software-systems-lecture-18-domain-specific-languages-and-autotuning.pdf 6-172-performance-engineering-of-software-systems-lecture-19-leiserchess-codewalk.pdf 6-172-performance-engineernig-of-software-systems-lecture-20-speculative-parallelism-and-leiserchess.pdf 6-172-performance-engineering-in-software-systems-lecture-21-tuning-a-tsp-algorithm.pdf 6-172-performance-engineering-of-software-systems-lecture-22-graph-optimization.pdf 6-172-performance-engineering-of-software-systems-lecture-23-high-performance-in-dynamic-languages.pdf output.pdf
Raw
study-plan.md

Okay, here is an exhaustive and comprehensive study plan for MIT's 6.172 Performance Engineering of Software Systems, leveraging the provided lecture list and integrating anticipated content from the corresponding PDF materials. This plan is structured lecture-by-lecture, highlighting key concepts and suggesting focus areas.

Course Goal: To understand and apply techniques for building scalable and high-performance software systems by analyzing performance, utilizing algorithmic strategies, optimizing at various levels (instruction, cache, parallel), and understanding the underlying hardware and system software.

Prerequisites (Assumed): Solid understanding of C/C++, data structures, algorithms, and basic computer organization.

General Study Approach:

  1. Pre-Reading/Skimming: Before each lecture, quickly skim the relevant PDF slides to get a sense of the topics.
  2. Active Lecture Participation: Attend or watch lectures actively, taking notes and focusing on the why behind techniques, not just the what.
  3. Post-Lecture Review & Deep Dive: After each lecture, thoroughly review the PDF slides and your notes. Identify key concepts, definitions, algorithms, and techniques.
  4. Practical Application: Crucially, implement and experiment with the concepts. Use the provided tools (compilers, profilers, analyzers). Work diligently on labs and projects (like Leiserchess). Performance engineering is learned by doing.
  5. Tool Proficiency: Become comfortable using performance analysis tools mentioned (compilers with optimization flags, perf, gdb, Cachegrind, Cilksan, Cilkscale, potentially Valgrind, etc.).
  6. Connect Concepts: Constantly relate new topics back to previous ones (e.g., how architecture affects loop optimizations, how memory allocation impacts caching).

Detailed Study Plan:

Module 1: Foundations & Serial Performance (Lectures 1-5)

  • L1: Intro and Matrix Multiplication

    • Core Topics: Motivation for performance engineering (Moore's Law limitations, power wall), defining performance (latency, throughput, metrics), importance vs. other software properties (correctness, maintainability), introduction to matrix multiplication as a running example.
    • Key Concepts: Performance as a currency, identifying bottlenecks, initial code versions (Python, Java, C), basic timing, GFLOPS calculation, peak performance.
    • Focus: Understand why performance matters now more than ever. Grasp the baseline performance of a simple algorithm (matrix multiplication) in different languages. Learn basic timing methods.

  • L2: Bentley's Rules

    • Core Topics: Principles of optimizing work (reducing total operations), Jon Bentley's optimization rules (or a modern interpretation).
    • Key Concepts: Work reduction heuristics. Categories:
      • Data Structures: Packing, encoding, augmentation, precomputation, compile-time initialization, caching (memoization), sparsity.
      • Logic: Constant folding/propagation, common subexpression elimination, algebraic identities, short-circuiting, ordering tests, fast paths, combining tests.
      • Loops: Hoisting, sentinels, unrolling, fusion, eliminating wasted iterations.
      • Functions: Inlining, tail-recursion elimination, coarsening recursion.
    • Focus: Internalize the principles behind work reduction. Understand how each rule reduces operations. Apply these rules mentally to simple code snippets. Relate to the TSP example if presented.

  • L3: Bit Hacks

    • Core Topics: Low-level bit manipulation for performance and specific tasks.
    • Key Concepts: Binary/Hexadecimal/Two's Complement representations, C bitwise operators (&, |, ^, ~, <<, >>), setting/clearing/toggling bits, extracting/setting bit fields, XOR swap, branchless minimum/conditional selection, population count (popcount) algorithms, potential pitfalls (compiler re-optimization, ILP interactions). Queens problem example.
    • Focus: Master bitwise operations. Understand the logic and application of common bit hacks. Recognize their potential performance benefits (e.g., avoiding branches) and limitations.

  • L4: Architecture and Vectorization

    • Core Topics: Relevant computer architecture concepts, Instruction Set Architecture (ISA), pipelining, hazards, and Single Instruction Multiple Data (SIMD) execution.
    • Key Concepts: x86-64 ISA basics (registers, common instructions, addressing modes, register aliasing), instruction formats, AT&T vs. Intel syntax, data types and suffixes, condition codes (RFLAGS), pipelining stages (IF, ID, EX, MA, WB), hazards (structural, data - RAW, WAR, WAW, control), pipeline stalls, superscalar execution, out-of-order execution, branch prediction, vector hardware (SIMD lanes), SSE/AVX instruction sets, vector registers (XMM, YMM).
    • Focus: Understand how instructions are executed on modern hardware. Grasp the concepts of pipelining, hazards, and how processors mitigate them (bypassing, OoO, branch prediction). Understand the basic principle of SIMD/vectorization.

  • L5: C to Assembly

    • Core Topics: The compilation process, focusing on the translation from C to assembly, particularly via LLVM IR.
    • Key Concepts: Compilation pipeline (preprocessing, compilation to IR, optimization, assembly generation, linking), LLVM IR structure (instructions, registers, basic blocks, control-flow graph - CFG), mapping C constructs (assignments, arithmetic, function calls, conditionals, loops) to LLVM IR, function calling conventions (Linux x86-64: stack frames, frame pointer %rbp, stack pointer %rsp, argument passing registers, return value register, caller/callee-saved registers), call/ret instructions.
    • Focus: Understand the role of the intermediate representation (LLVM IR). Learn how high-level C constructs are broken down. Master the Linux x86-64 calling convention – how functions interact at the assembly level.

Module 2: Parallelism Fundamentals (Lectures 6-9)

  • L6: Multicore Programming

    • Core Topics: Introduction to multicore processors and the need for parallel programming. Shared memory concepts.
    • Key Concepts: End of frequency scaling, power density wall, multicore architecture overview, shared memory model, cache coherence problem, snooping protocols (MSI), concurrency platforms (Pthreads, TBB, OpenMP, Cilk Plus - brief overview).
    • Focus: Understand the hardware shift to multicore and why parallel programming is essential for performance. Grasp the concept of cache coherence. Get a first look at different ways to write parallel programs.

  • L7: Races and Parallelism

    • Core Topics: Defining and identifying race conditions, introduction to the Cilk concurrency platform, work-span analysis.
    • Key Concepts: Race conditions (determinacy races vs. data races), nondeterminism, Cilk keywords (cilk_spawn, cilk_sync, cilk_for), serial elision, computation DAGs, Work (T1), Span (Tinf), Parallelism (T1/Tinf), Speedup, Amdahl's Law vs. Work-Span, using the Cilksan race detector.
    • Focus: Deeply understand determinacy races and their implications. Learn the Cilk model and keywords. Master the work-span model for analyzing parallel performance potential. Practice using Cilksan.

  • L8: Analysis of Multithreaded Algorithms

    • Core Topics: Applying the work-span model to analyze recursive parallel algorithms.
    • Key Concepts: Analyzing series and parallel compositions (work adds, span adds/maxes), recurrence relations for work and span, using the Master Method for solving recurrences (Cases 1, 2, 3), analyzing parallel matrix multiplication and parallel merge sort.
    • Focus: Become proficient in setting up and solving work and span recurrences for divide-and-conquer parallel algorithms using the Master Method.

  • L9: What Compilers Can and Cannot Do

    • Core Topics: Understanding compiler optimizations, their limitations (especially with aliasing), and how intermediate representations like Tapir/LLVM help.
    • Key Concepts: Review of compiler optimizations (hoisting, CSE, inlining etc.), compiler reports (-Rpass), memory aliasing as an obstacle, restrict and const keywords, undefined behavior (signed integer overflow), Tapir/LLVM's approach to integrating parallelism analysis with standard optimizations.
    • Focus: Appreciate the power and limitations of compilers in optimization. Understand how aliasing restricts optimization and how to help the compiler. Learn how to interpret compiler optimization reports.

Module 3: Measurement, Memory, and Runtime (Lectures 10-13)

  • L10: Measurement and Timing

    • Core Topics: Accurately measuring performance and understanding sources of variability.
    • Key Concepts: Timing challenges (DVFS, interrupts, context switches, cache effects), quiescing systems, measurement tools (time, clock_gettime, rdtsc pitfalls), hardware performance counters (perf), simulation (Cachegrind), statistical analysis (minimum vs. average, geometric mean for ratios), performance modeling (linear regression).
    • Focus: Learn reliable methods for timing code. Understand the pitfalls of naive timing. Become familiar with using perf for deeper insights. Know how to interpret measurement results statistically.

  • L11: Storage Allocation

    • Core Topics: Managing dynamic memory allocation on the heap (serial context).
    • Key Concepts: Stack allocation vs. Heap allocation (malloc/free), fragmentation (internal and external), fixed-size allocation (free lists, bitmaps), variable-size allocation (binned free lists, buddy systems), coalescing free blocks, garbage collection basics (reachability, roots, mark-and-sweep, reference counting, copying collectors).
    • Focus: Understand the mechanisms and tradeoffs of different heap allocation strategies. Grasp the concept and types of fragmentation. Learn the fundamental ideas behind garbage collection.

  • L12: Parallel Storage Allocation

    • Core Topics: Challenges of memory allocation in parallel programs.
    • Key Concepts: Scalability issues with global allocator locks (contention), local heaps (memory drift), local ownership strategy, false sharing (active vs. passive), Hoard allocator (design, superblocks, fragmentation bounds), other allocators (jemalloc, SuperMalloc), parallel/concurrent garbage collection challenges, cactus stacks for parallel function calls (Cilk).
    • Focus: Understand the unique challenges of parallel memory management. Learn about false sharing and how allocators can mitigate it. Grasp the design principles of scalable allocators like Hoard.

  • L13: The Cilk Runtime System

    • Core Topics: Internal workings of the Cilk work-stealing runtime system.
    • Key Concepts: Work-stealing scheduler details, worker deques (implementation, THE protocol for synchronization), Cilk stack frames (__cilkrts_stack_frame), spawn helpers, function call/return/spawn/sync implementation, full frames, cactus stack implementation, handling steals and continuations (setjmp/longjmp).
    • Focus: Understand the key data structures and protocols used by the Cilk runtime to implement its parallel execution model efficiently, particularly the work-stealing deque and cactus stack management.

Module 4: Caching and Advanced Parallelism (Lectures 14-17)

  • L14: Caching and Cache-Efficient Algorithms

    • Core Topics: Cache behavior, cache performance analysis, and cache-aware algorithm design.
    • Key Concepts: Cache hierarchy review, associativity (direct-mapped, set-associative, fully-associative), write policies, replacement policies (LRU), cache misses (compulsory, capacity, conflict, true/false sharing), ideal-cache model (M, B), tall-cache assumption (B² << M), analyzing cache misses (matrix multiplication loop orders), cache-aware algorithms (tiling/blocking for matrix multiplication), cache conflicts in practice.
    • Focus: Deepen understanding of cache behavior and its impact on performance. Learn to analyze algorithms using the ideal-cache model. Understand the tiling technique.

  • L15: Cache-Oblivious Algorithms

    • Core Topics: Designing algorithms that perform well on different cache hierarchies without explicit cache parameter tuning.
    • Key Concepts: Motivation (avoiding tuning parameters, handling multiple cache levels), recursive algorithms (matrix multiplication, merge sort revisited for cache analysis), cache complexity analysis, cache-oblivious matrix multiplication, cache-oblivious sorting (funnelsort), cache-oblivious stencil computations (trapezoidal decomposition).
    • Focus: Understand the principle of cache-obliviousness through recursive design. Analyze the cache performance of these algorithms.

  • L16: Nondeterministic Programming

    • Core Topics: Problems arising from nondeterminism, synchronization primitives (mutexes), and deadlock.
    • Key Concepts: Determinism vs. Nondeterminism, sequential consistency vs. relaxed memory models, instruction reordering, memory fences/barriers, atomicity, critical sections, mutexes (implementation using atomics like xchg), Peterson's algorithm (proof of correctness), deadlock (conditions, Dining Philosophers example), deadlock prevention (lock ordering), potential deadlocks in Cilk (cilk_sync while holding locks).
    • Focus: Understand the dangers of nondeterminism. Learn how mutexes provide mutual exclusion. Master the conditions for deadlock and strategies for prevention.

  • L17: Synchronization without Locks

    • Core Topics: Techniques for achieving synchronization without traditional locks.
    • Key Concepts: Problems with locks (contention, priority inversion, deadlock), atomic instructions (Compare-and-Swap - CAS), lock-free programming, lock-free stack implementation, ABA problem (causes and solutions like versioning/epoch-based reclamation), wait-free programming (briefly), introduction to transactional memory (atomicity, commit/abort, conflicts).
    • Focus: Understand the concept and benefits of lock-free programming. Learn how to use CAS. Be aware of the ABA problem. Get a basic understanding of transactional memory.

Module 5: Advanced Topics & Applications (Lectures 18-23)

  • L18: DSLs and Autotuning

    • Core Topics: Using Domain-Specific Languages (DSLs) and automated tuning to achieve high performance.
    • Key Concepts: Motivation for DSLs (capturing intent, enabling optimization), separating algorithm from schedule (optimization strategy), examples (Halide for image processing, GraphIt for graphs), optimization tradeoffs (locality vs. parallelism vs. redundant work), autotuning concepts, search space definition, search techniques (random, hill climbing, simulated annealing, genetic algorithms, ensembles), OpenTuner framework.
    • Focus: Understand the DSL approach to performance. Learn how separating algorithm and schedule facilitates optimization. Grasp the principles of autotuning.

  • L19: Leiserchess Code Walk

    • Core Topics: Understanding the structure and key components of the Leiserchess codebase for Project 2.
    • Key Concepts: Leiserchess rules recap, Forsyth-Edwards Notation (FEN), Universal Chess Interface (UCI), codebase organization (player/, move_gen.c, search.c, eval.c), board representation (mailbox vs. bitboards, sentinels), move generation (move_t structure), static evaluation function (eval), search algorithms (minimax, alpha-beta), Perft for move generation debugging.
    • Focus: Familiarize yourself thoroughly with the Leiserchess codebase. Understand how the different parts (move generation, evaluation, search) interact. Know how to use Perft.

  • L20: Speculative Parallelism/Project Parallelization Strategies

    • Core Topics: Applying advanced parallelism techniques, particularly speculation, to problems like game tree search, relevant to Leiserchess.
    • Key Concepts: Speculative parallelism (definition, when to use), parallelizing short-circuiting computations, alpha-beta search review, parallel alpha-beta strategies (Young Siblings Wait, Jamboree Search), handling wasted work, abort mechanisms, specific Leiserchess optimizations (move ordering heuristics - transposition table, killers, history; null-move pruning, futility pruning, late-move reductions, quiescence search, endgame databases, Zobrist hashing).
    • Focus: Understand speculative parallelism in the context of search. Learn various techniques used in high-performance chess engines. Apply these ideas to parallelizing Leiserchess.

  • L21: Guest Lecture (Example: Julia)

    • Core Topics: High performance in dynamic languages (using Julia as an example).
    • Key Concepts: The "two-language problem," vectorization limitations, Julia's approach (JIT compilation, type inference, multiple dispatch), performance comparisons (Vandermonde matrices, special functions), metaprogramming for code generation.
    • Focus: Appreciate how modern dynamic languages attempt to achieve high performance, bridging the gap with static languages.

  • L22: Graph Optimization

    • Core Topics: Performance considerations and optimizations specific to graph algorithms.
    • Key Concepts: Graph representations (Adjacency Matrix, Adjacency List, Compressed Sparse Row - CSR), properties of real-world graphs (large, sparse, power-law degree distribution), BFS implementations (serial, parallel work-span, cache analysis), direction-optimizing BFS (push vs. pull), graph compression techniques (delta coding, variable-length codes), graph reordering for locality.
    • Focus: Understand CSR representation. Learn about direction-optimizing BFS and its tradeoffs. Grasp the concepts of graph compression and reordering for performance.

  • L23: Guest Lecture (Example: TSP Tuning)

    • Core Topics: A case study in performance tuning, likely using the Traveling Salesperson Problem (TSP).
    • Key Concepts: Algorithm engineering process, iterative refinement, impact of compiler optimizations (-O3), hardware improvements over time, constant factor improvements (data types, precomputation), algorithmic improvements (reducing search space, pruning), bounding techniques (MST lower bound), caching/memoization (hash tables), heuristics (sorting edges).
    • Focus: Observe a practical, iterative process of performance tuning, combining various techniques learned throughout the course. Understand the interplay between hardware, compilers, algorithms, and data structures.

This plan provides a detailed roadmap. Remember to actively engage with the material, especially through coding and experimentation, to truly master performance engineering. Good luck!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment