Stanford-cs149

Stanford CS149, Fall 2025 PARALLEL COMPUTING

PARALLEL COMPUTING Assignment —— Stanford CS149 并行计算课程作业（个人实现 + 实验报告）

Topics Include

• Fast networks, multicore, accelerators and vector instruction sets
• Implicit vs. explicit parallelism
• Shared vs. non-shared memory
• Synchronization mechanisms such as locking, atomicity, transactions and barriers
• Parallel programming models such as threads, MapReduce, Apache Spark and SIMT

📖 各作业 README（点击直达 GitHub 源码）：Assignment 1 · Assignment 2 · Assignment 3 · Assignment 4 · Assignment 5

Assignments（各作业简介）

Assignment 1: Performance Analysis on a Quad-Core CPU（四核 CPU 上并行执行的性能分析）

在 4 核 Intel Core i7 处理器（支持 AVX2 八路 SIMD 与超线程）上，通过 6 个程序亲身体验现代 CPU 的两种并行执行形式——核内 SIMD 与跨核多线程，并练习测量与推理并行程序性能：

• Program 1：用 std::thread 并行计算 Mandelbrot 分形，做空间分解、分析加速比与线程耗时，并改进工作分配策略
• Program 2：用 CS149 假向量指令集（CS149intrin.h）向量化 clampedExp，学习 mask 与向量利用率
• Program 3：用 ISPC（foreach 与 launch tasks）并行计算 Mandelbrot，同时利用 SIMD 与多核
• Program 4：用 ISPC 实现 Newton 迭代法开方 sqrt，对比 SIMD 与多核各自的加速
• Program 5：用 ISPC 实现 BLAS saxpy（内存带宽受限的简单问题）
• Program 6：优化 K-Means 聚类算法，练习定位性能热点（目标 ≥2.1x 加速）

📄 实验报告：report/asst1_report.md

Assignment 2: Building A Task Execution Library from the Ground Up（从零构建任务执行库）

实现一个 C++ 任务执行库，把应用提交的大量任务高效调度到多核 CPU 上（功能类似 ISPC task launch / Intel TBB / Apache Spark）：

• Part A：同步 bulk task launch。run() 一次性启动同一任务的多个实例，返回前必须全部执行完。逐步实现三套复杂度递增的任务系统：
  • TaskSystemParallelSpawn：每次 run() 现建线程
  • TaskSystemParallelThreadPoolSpinning：线程池 + 自旋等待
  • TaskSystemParallelThreadPoolSleeping：线程池 + 条件变量休眠
• Part B：任务图（DAG）调度。实现异步 runAsyncWithDeps() / sync()，支持任务间依赖关系（如 PyTorch / TensorFlow 的计算图），并用互斥锁、条件变量做依赖簿记

📄 实验报告：report/asst2_report.md

Assignment 3: A Simple CUDA Renderer（简易 CUDA 渲染器）

用 CUDA 编写并优化（在 NVIDIA T4 GPU 上运行）：

• Part 1：CUDA 版 SAXPY 热身（5 pts），对比核内执行时间与含主机-设备数据传输的完整时间
• Part 2：并行 exclusive prefix-sum（10 pts），并基于它实现 find_repeats（找所有 A[i]==A[i+1] 的下标）
• Part 3：绘制半透明圆的并行渲染器（85 pts）。核心挑战是设计可并行构建的数据结构，并同时保证像素更新的原子性与按圆输入顺序更新

📄 实验报告：report/asst3_report.md

Assignment 4: Programming a Machine Learning Accelerator（机器学习加速器编程）

为 AWS Trainium2 架构编写与优化 kernel，体验张量处理与片上 SRAM 管理的底层细节：

• Part 1：通过向量加与自写矩阵转置 kernel 熟悉 Trainium 架构与数据搬移模式
• Part 2：在 Trainium2 上实现融合的 convolution + maxpool 层，体会循环分块（blocking）与循环融合（fusion）等保持局部性的优化

Assignment 5: Write a Fast Kernel（写出最快的 Kernel）

开放式期末项目：从给定的 AI 相关 kernel 列表中自选（Histogram、1D Occupancy Decoder、FlashAttention、RK4 热方程、SwiGLU），在 H100 GPU 上做极致性能优化（可用 CUDA / Triton / Tilelang），提交到班级排行榜，按工作量日志评分。

Reports（实验报告）