高级并行算法

📊 课程难度与压力分析

COMP4121 是 UNSW 计算机系的‘封神榜’。难点不再是写出能跑的代码，而是‘证明它在 1000 个处理器上依然高效’。当你面对 Chernoff Bound 的级数求和推导，或者需要手写并行前缀和的逻辑时，你会发现这不仅是编程，而是极其硬核的组合数学。压力主要来自于期末考试，题目往往非常简短（如：证明某问题在 NC 类中），但平均每道题需要 30 分钟的纯逻辑构建。挂科率显著，是区分顶级研发人才与普通开发者的绝对标尺。

🎯 备考重点与高分策略

高分秘籍：‘得概率工具者得 HD’。期末考试中，利用随机化思想简化复杂确定性问题是必考的大题，一定要练熟‘全概率公式’在算法稳定性中的应用。重点攻克‘Work-Depth 模型分析’，要能准确判定一个并行算法的理论加速上限。备考时，教材《Randomized Algorithms》(Motwani) 和《Parallel Algorithms》(Casas) 是核心参考。对于项目，HD 的关键在于‘缓存命中分析’——不仅实现并行，还要分析为什么在特定架构下出现了通信瓶颈。重视 Tutorial 里的每一道 NC 类证明题。

📚 学习建议与资源推荐

神书推荐：Motwani & Raghavan 的《Randomized Algorithms》，全球随机算法的圣经。如果并行概念太抽象，去 YouTube 搜‘CMU Parallel Computer Architecture’系列讲座。最重要的建议：养成画‘任务依赖图’的习惯，理清哪些操作是互不依赖可以并发的。学会利用 Python 的 `multiprocessing` 或 C 的 `OpenMP` 进行初步的加速实验。加入 MathSoc 的高级算法小组。

⚠️ 作业与 Lab 避坑指南

作业避坑：证明题严禁使用‘显然 (Clearly)’！每一个加速比的提升都必须对应一个特定的算法步骤改进。Assignment 写作中，严禁只给测试结果，必须提供详尽的‘通信开销分析’。此外，注意 Final 考试有 Hurdle 要求，平时分再高，期末如果没有想到那道随机化大题的证明思路，照样会挂。考试时，带好直尺和彩色笔，画并行执行时间轴（Gantt chart）时保持清晰。

💬 过来人经验分享

学长建议：这门课是为你进入 Google, NVIDIA 或顶级对冲基金拿的‘通关文牒’。学完后，你眼中的算力将不再是一个模糊的数字，而是一场由千万个核心交织出的精密舞蹈。建议找一个数学功底极其扎实的队友共同推导。拿 HD 的关键：在论述中展现出你对‘计算成本 (Communication vs Computation)’权衡的深刻觉知。坚持住，通关 4121，你就真正跨过了计算科学的最高门槛。这张成绩单是申请全球 Top 5 CS PhD 或大厂核心组的硬核通行证。