UIUC ECE 408 应用并行编程 · 开篇与课程概览

{
  "lecture_topic": "Course Overview, Motivation for Parallel Computing, and GPU Architecture Introduction",
  "related_lab": "Lab 0: Device Query",
  "key_concepts_raw": [
    "power wall (2004)",
    "multicore transition",
    "massively parallel processor (>64 ops/clock)",
    "heterogeneous computing (host/device)",
    "SM (Streaming Multiprocessor)",
    "SIMT / warp",
    "latency hiding vs throughput",
    "arithmetic intensity",
    "Amdahl's law",
    "unified shader architecture",
    "device query and CUDA environment setup",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Understand the major types of hardware limitations that limit parallel program performance",
  ],
  "available_public_info": "公开的课程目录页给出 Official Description、Course Goals、Instructional Objectives A1-A17、Lab 0 (installation and test of programming environment)。公开讲义 Slide Deck 1 (Introduction)、Extra Deck 1 (A Historical Perspective)、Extra Deck 2 (Generalizing Parallelism)、Slide Deck 19 (GPUs in the PC Architecture) 均可公开下载。Lab 0 的 handout 本身未公开（通过 GitHub + NCSA Delta 分发）。",
  "source_slide_decks": [
    "Slide Deck 1: Introduction",
    "Extra Slide Deck 1: A Historical Perspective",
    "Extra Slide Deck 2: Generalizing Parallelism",
    "Slide Deck 19: GPUs in the PC Architecture",
  ]
}

{
  "lecture_topic": "CUDA Programming Model Fundamentals: Kernels, Thread Hierarchy, and Memory Model",
  "related_lab": "Lab 0 / Lab 1 (foundation)",
  "key_concepts_raw": [
    "__global__ / __device__ / __host__ qualifiers",
    "kernel launch <<<grid, block>>>",
    "grid-block-thread hierarchy",
    "gridDim/blockDim/blockIdx/threadIdx",
    "warp = 32 threads",
    "SIMT execution and warp divergence",
    "register / local / shared / global / constant / texture memory",
    "scope and lifetime of each memory space",
    "__syncthreads() block barrier",
    "cudaDeviceSynchronize vs asynchronous kernel launch",
    "thread coarsening (motivation)",
  ],
  "learning_objectives": [
    "Understand and apply common parallel programming interface features",
    "Review a parallel code segment and identify its behavior and potential problems",
  ],
  "available_public_info": "公开讲义 Slide Deck 2 (CUDA Introduction)、Slide Deck 3 (CUDA Parallelism Model)、Slide Deck 4 (CUDA Memory Model) 全部公开可下载，含二维线程索引、图片通道拆分、共享/常量内存的完整代码骨架。",
  "source_slide_decks": [
    "Slide Deck 2: CUDA Introduction",
    "Slide Deck 3: CUDA Parallelism Model",
    "Slide Deck 4: CUDA Memory Model",
  ]
}

{
  "lecture_topic": "Parallel Pattern 1 - Vector Addition: Thread Mapping and Memory Access",
  "related_lab": "Lab 1: Vector Addition",
  "key_concepts_raw": [
    "data parallelism",
    "thread-to-data mapping i = blockIdx.x*blockDim.x + threadIdx.x",
    "grid sizing with ceiling division",
    "boundary checking",
    "coalesced global memory access",
    "memory bandwidth bound kernel",
    "arithmetic intensity of vector add (0.125 FLOP/Byte)",
    "occupancy and block size selection",
    "grid-stride loop",
    "__restrict__ pointers",
    "validating against a CPU golden reference",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Design experiments to analyze the performance bottlenecks in their parallel code",
    "Apply common parallel techniques to improve performance given hardware constraints",
  ],
  "available_public_info": "公开讲义 Slide Deck 2/3/4 含 Review - Vector Addition Kernel 与 Review - Thread Assignment for vecAdd（gridDim.x / blockDim.x 的填空练习）；Slide Deck 7 (DRAM) 提供带宽分析依据。Lab 1 的完整 handout（含测试数据与评分脚本）未公开，通过 GitHub 分发。",
  "source_slide_decks": [
    "Slide Deck 2: CUDA Introduction",
    "Slide Deck 3: CUDA Parallelism Model",
    "Slide Deck 7: DRAM",
  ]
}

{
  "lecture_topic": "Parallel Pattern 2 - Simple Matrix Multiplication and Its Performance Bottlenecks",
  "related_lab": "Lab 2: Simple Matrix Multiply",
  "key_concepts_raw": [
    "GEMM definition, FLOPs = 2*M*N*K",
    "row-major linearization M[row*Width + col]",
    "thread-per-output mapping with 2D block/grid",
    "2K global loads per output element",
    "strided (uncoalesced) access to B columns",
    "arithmetic intensity 0.25 FLOP/Byte",
    "Roofline ceiling for naive matmul",
    "data reuse counts (A used N times, B used M times)",
    "matrix transpose to restore coalescing",
    "thread coarsening for register reuse",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Design experiments to analyze the performance bottlenecks in their parallel code",
  ],
  "available_public_info": "公开讲义 Slide Deck 5 (CUDA Tiled Matrix Multiplication) 的前半部分讲解基础矩阵乘法的访存问题；Slide Deck 7 (DRAM) 提供 DRAM burst 与合并访问的定量依据。Lab 2 的 handout 未公开。",
  "source_slide_decks": [
    "Slide Deck 5: CUDA Tiled Matrix Multiplication",
    "Slide Deck 6: More on Tiling",
    "Slide Deck 7: DRAM",
  ]
}

{
  "lecture_topic": "Tiled Parallel Matrix Multiplication: Shared Memory and Data Reuse",
  "related_lab": "Lab 3: Tiled Matrix Multiply",
  "key_concepts_raw": [
    "tiling",
    "shared memory (48KB-228KB/SM, ~20-30 cycle latency)",
    "data reuse, 2N -> 2N/TILE_WIDTH global accesses per output",
    "shared memory banks and bank conflicts",
    "padding to break bank conflicts",
    "__syncthreads() RAW/WAR hazards, two barriers per tile iteration",
    "arithmetic intensity TILE_WIDTH/4 FLOP/Byte",
    "thread coarsening with register accumulators",
    "occupancy vs shared memory tradeoff",
    "double buffering / cp.async prefetch (advanced)",
  ],
  "learning_objectives": [
    "Apply common parallel techniques to improve performance given hardware constraints",
    "Understand the major types of hardware limitations that limit parallel program performance",
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
  ],
  "available_public_info": "公开讲义 Slide Deck 5 (CUDA Tiled Matrix Multiplication) 与 Slide Deck 6 (More on Tiling) 完整公开，含 __shared__ float subTileM[TILE_WIDTH][TILE_WIDTH] 的完整 kernel 代码骨架、__syncthreads 语义、以及 bank conflict 与 padding 的讨论。Lab 3 的 handout 未公开。",
  "source_slide_decks": [
    "Slide Deck 5: CUDA Tiled Matrix Multiplication",
    "Slide Deck 6: More on Tiling",
  ]
}

{
  "lecture_topic": "Parallel Pattern 4 - Reduction: Reduction Trees and Warp-Level Primitives",
  "related_lab": "Lab 4: Parallel Reduction (catalog) / Lab 5: List Reduction (Sum 2025)",
  "key_concepts_raw": [
    "reduction with associative+commutative operator and identity",
    "reduction tree, log2(N) steps, N-1 work, work efficiency",
    "interleaved addressing (stride 1,2,4...) vs sequential addressing (stride blockDim/2...)",
    "warp divergence in reductions",
    "bank conflicts in shared memory reduction",
    "__syncthreads() inside a stride loop",
    "warp shuffle: __shfl_down_sync / __shfl_xor_sync",
    "independent thread scheduling on Volta+ and the _sync mask",
    "thread coarsening with grid-stride loop",
    "hierarchical multi-block reduction, atomicAdd",
    "latency/bandwidth-bound nature of reduction",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Apply common parallel techniques to improve performance given hardware constraints",
    "Understand the major types of hardware limitations that limit parallel program performance",
  ],
  "available_public_info": "公开讲义 Slide Deck 11 (Reduction Trees) 完整公开，含 reduction 的定义、work-efficient 分析、交错/顺序寻址的对比与共享内存 reduction 代码。Lab 5: List Reduction 的 handout 未公开；Lab 4 在课程目录页上的名字是 Parallel Reduction，在 2024/2025 时间线上 Lab 4 是 3D Convolution。",
  "source_slide_decks": [
    "Slide Deck 11: Reduction Trees",
  ]
}

{
  "lecture_topic": "Parallel Pattern 5 - Prefix Sum / Scan: Double Buffering and Hierarchical Algorithms",
  "related_lab": "Lab 5: Parallel Scan (catalog) / Lab 6: Scan (Sum 2025)",
  "key_concepts_raw": [
    "inclusive vs exclusive scan",
    "associative operator generalisation",
    "applications: recurrences, stream compaction, radix sort, histograms, polynomial evaluation",
    "Hillis-Steele (Kogge-Stone) scan: O(log N) steps, O(N log N) work, not work-efficient",
    "Blelloch work-efficient scan: up-sweep and down-sweep, O(N) work",
    "double buffering to avoid read-after-write hazards",
    "hierarchical multi-block scan (scan-scan-add three step)",
    "shared memory bank conflicts for different strides",
    "work efficiency vs latency tradeoff",
    "__syncthreads() between every scan step",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Understand and apply common parallel algorithm patterns",
    "Apply common parallel techniques to improve performance given hardware constraints",
  ],
  "available_public_info": "公开讲义 Slide Deck 12 (Parallel Prefix, or Scan) 完整公开，含 Hillis-Steele、Blelloch、double buffering、hierarchical scan 与 '100-inch sandwich' 类比。Lab 6: Scan 的 handout 未公开。",
  "source_slide_decks": [
    "Slide Deck 12: Parallel Prefix, or Scan",
  ]
}

{
  "lecture_topic": "Parallel Pattern 6 - Tiled Convolution: Constant Memory and Boundary Handling",
  "related_lab": "Lab 6: Tiled Parallel Convolution (catalog) / Lab 4: 3D Convolution (Sum 2025)",
  "key_concepts_raw": [
    "1D/2D/3D convolution definition, mask/filter, halo/apron",
    "constant memory: 64KB, __constant__, cudaMemcpyToSymbol, broadcast in constant cache",
    "boundary handling: zero padding, clamp, wrap; ghost cells",
    "warp divergence at boundaries",
    "tiled convolution with halo (TILE+2r)^2 shared memory capacity",
    "reduction of global traffic by (TILE+2r)^2/TILE^2",
    "thread coarsening and register blocking",
    "arithmetic intensity of convolution (~1 FLOP/Byte naive)",
    "3D convolution: larger halo volume, register pressure, cudaPitchedPtr",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Apply common parallel techniques to improve performance given hardware constraints",
    "Design experiments to analyze the performance bottlenecks in their parallel code",
  ],
  "available_public_info": "公开讲义 Slide Deck 8 (Convolution and Constant Memory)、Slide Deck 9 (Tiled Convolution)、Slide Deck 10 (Tiled Convolution Analysis) 全部公开。Slide Deck 9 明确写有 'prepare for MP-4: tiled 3D convolution'，证明 Lab 4 = 3D Convolution。Lab handout 未公开。",
  "source_slide_decks": [
    "Slide Deck 8: Convolution and Constant Memory",
    "Slide Deck 9: Tiled Convolution",
    "Slide Deck 10: Tiled Convolution Analysis",
  ]
}

{
  "lecture_topic": "Parallel Pattern 7 - Sparse Matrix-Vector Multiplication: Compact Formats and Load Balance",
  "related_lab": "Lab 7: Sparse Matrix-Vector Multiplication (catalog) / Lab 8: Sparse Matrix Multiply (Sum 2025)",
  "key_concepts_raw": [
    "sparsity in real systems, loss of regularity",
    "CSR: rowPtr[N+1], colIdx[nnz], values[nnz]",
    "ELL, ELLPACK, COO, JDS, hybrid ELL+COO",
    "load imbalance: rows with very different nnz within one warp",
    "indirect gather x[colIdx[j]] - uncoalesced and cache-unfriendly",
    "arithmetic intensity ~0.167 FLOP/Byte",
    "vectorised loads (float4), shared memory caching of x",
    "row reordering, warp-per-row with shuffle reduction",
    "compaction motivation (memory footprint and bandwidth)",
  ],
  "learning_objectives": [
    "Analyze and implement common parallel algorithm patterns in a parallel programming model such as CUDA",
    "Understand the major types of hardware limitations that limit parallel program performance",
    "Apply common parallel techniques to improve performance given hardware constraints",
  ],
  "available_public_info": "公开讲义 Slide Deck 14 (Parallel Sparse Methods) 与 Slide Deck 15 (Parallel Sparse Methods Part 2) 完整公开，含 'key techniques for compacting input data' 与 'challenge: retaining regularity'。Lab 8: Sparse Matrix Multiply 的 handout 未公开。",
  "source_slide_decks": [
    "Slide Deck 14: Parallel Sparse Methods",
    "Slide Deck 15: Parallel Sparse Methods (Part 2)",
  ]
}

{
  "lecture_topic": "Performance Analysis and Optimisation Methodology: Roofline, Occupancy, Coalescing, Atomics",
  "related_lab": "Applies to all labs",
  "key_concepts_raw": [
    "DRAM organisation, burst length, row buffer",
    "coalescing: 32 accesses -> 1..32 transactions of 128 bytes",
    "arithmetic intensity and machine balance (A100 = 12.5 FLOP/Byte)",
    "Roofline model: bandwidth-bound vs compute-bound knee",
    "Little's law for latency hiding, memory-level parallelism",
    "occupancy calculation and the 'good enough' rule",
    "cudaOccupancyMaxActiveBlocksPerMultiprocessor, nvcc --ptxas-options=-v",
    "atomic operations, serialisation on the same address",
    "data locality / privatisation (shared memory private histogram)",
    "profiling with nvprof / Nsight Compute, stall reasons",
  ],
  "learning_objectives": [
    "Design experiments to analyze the performance bottlenecks in their parallel code",
    "Learn about the features of a parallel profiler and use them to identify performance bottlenecks in their code",
    "Learn about the features of a parallel debugger and use them to identify and repair code defects",
  ],
  "available_public_info": "公开讲义 Slide Deck 7 (DRAM)、Slide Deck 6 (More on Tiling)、Slide Deck 10 (Tiled Convolution Analysis)、Slide Deck 13 (Atomic Operations and Histograms) 全部公开。Slide Deck 13 对应 Lab 7: Histogramming，是原子操作与私有化技术的最佳案例。",
  "source_slide_decks": [
    "Slide Deck 7: DRAM",
    "Slide Deck 6: More on Tiling",
    "Slide Deck 10: Tiled Convolution Analysis",
    "Slide Deck 13: Atomic Operations and Histograms",
  ]
}

{
  "lecture_topic": "Advanced Topics: Multi-Stream, Data Transfer, Tensor Cores, Deep Learning, Alternatives to CUDA (WebGPU/RAI)",
  "related_lab": "Final Project",
  "key_concepts_raw": [
    "GPU in the PC architecture: PCIe 3.0/4.0/5.0 bandwidth, NVLink, NVSwitch",
    "unified memory / cudaMallocManaged and page migration",
    "pinned (page-locked) host memory and true DMA",
    "CUDA streams, cudaMemcpyAsync, overlapping transfer with compute",
    "default stream semantics and events for inter-stream sync",
    "Tensor Cores, WMMA API, FP16/BF16/TF32 with FP32 accumulate",
    "deep learning: feedforward nets, gradient descent, convolution as GEMM (im2col)",
    "alternatives: OpenCL, SYCL, HIP, OpenACC, OpenMP offload, Vulkan/Metal, WebGPU (WGSL), RAI",
    "CUDA-to-WebGPU mapping table (grid/block/thread vs workgroup/invocation)",
  ],
  "learning_objectives": [
    "Identify design space and explore optimization opportunities for the solutions",
    "Identify limitations of the solutions and future directions",
    "Understand and apply common parallel programming interface features",
  ],
  "available_public_info": "公开讲义 Slide Deck 16 (Machine and Deep Learning)、Slide Deck 17 (Feedforward Networks and Gradient Descent)、Slide Deck 18 (Computation in Deep Neural Networks)、Slide Deck 19 (GPUs in the PC Architecture)、Slide Deck 20 (GPU Data Transfer)、Slide Deck 21 (Tensor Operations)、Slide Deck 22 (Alternatives to CUDA) 全部公开。课程目录页确认 'WebGPU for labs, RAI for final project'。",
  "source_slide_decks": [
    "Slide Deck 16: Machine and Deep Learning",
    "Slide Deck 17: Feedforward Networks and Gradient Descent",
    "Slide Deck 18: Computation in Deep Neural Networks",
    "Slide Deck 19: GPUs in the PC Architecture",
    "Slide Deck 20: GPU Data Transfer",
    "Slide Deck 21: Tensor Operations",
    "Slide Deck 22: Alternatives to CUDA",
  ]
}

{
  "lecture_topic": "Final Project: Problem Definition, Design, Optimisation, and Reporting",
  "related_lab": "Final Project: Proposal + Workshop + Presentation + Report",
  "key_concepts_raw": [
    "project deliverables and grading (25% of course; ~50% correctness, ~50% performance)",
    "problem selection: data parallelism, arithmetic intensity, regularity, scale",
    "performance engineering cycle: baseline, profile, hypothesise, change one variable, re-measure",
    "design space exploration: block size, tile size, coarsening factor, padding, vectorisation, streams",
    "golden reference construction and floating-point tolerance",
    "robustness: arbitrary sizes, boundary handling, multi-architecture builds",
    "technical report structure and honest reporting of failed attempts",
    "academic integrity and the AI-tool policy",
    "team work decomposition and interface contracts",
  ],
  "learning_objectives": [
    "Identify and solve a computational problem with parallel algorithm design and program",
    "Work with domain experts and teammates from different disciplines to maximize the effectiveness of solutions",
    "Properly divide up the responsibilities among teammates and support each other towards success",
    "Motivate the problem and approach in a presentation",
    "Properly explain the solutions experimented and justify the final decision and outcome",
    "Identify limitations of the solutions and future directions",
  ],
  "available_public_info": "课程目录页确认 'A final project report is required' 与 'Final Project that involves Project Proposal, Project Workshop, Project Presentation, and Project Report'。2025 夏季课程页确认 project 占 25%、含 demo/functionality/coding style 约 50% 与 performance with full functionality 约 50%。公开的 Project Plan PDF 与 Final Report Rubric 均为 404（未公开）。",
  "source_slide_decks": [
    "Slide Deck 10: Tiled Convolution Analysis (as methodology reference)",
  ]
}