第三届北京大学高性能计算综合能力竞赛 - 个人参赛仓库

本仓库为我参加第三届北京大学高性能计算综合能力竞赛的个人提交与实验记录，覆盖 A-M 多道题目。

仓库信息

• 赛事：第三届北京大学高性能计算综合能力竞赛
• 形式：个人参赛
• 内容：题目说明、阶段代码、优化版本、测试脚本与阶段性结果记录
• 目标：在正确性约束下，针对 CPU/GPU/MPI/DSL 等场景进行性能优化

总体方法

• 先做正确性闭环：可复现实验、对拍/检查器、边界条件验证。
• 再做性能迭代：基线实现 -> 定位瓶颈 -> 针对性优化 -> 回归验证。
• 保留阶段性版本与日志，便于回溯每一步优化收益与风险。

题目 Write-up（简版）

A 题（签到）

• 简要思路：题面代码是 Fortran（program ... implicit none ... end program），且是一个 quine。
• 简要过程：识别语言后编译运行，输出为程序自身源码（自复制输出），据此完成签到提交与环境连通性确认。

B 题（问答）

• 按知识问答题处理，此处不展开实现细节。

C 题（Flash Ticker）

• 简要思路：热点在 candles[tid] 的并行写入，核心瓶颈是伪共享。
• 简要过程：只改 C-code/market.h，保持字段名和类型不变，把 Candle 从 32B 扩展到 128B（新增 char __padding[128 - 32]）。这样每线程写入独立对象，显著降低 cache line 争用和预取干扰。

D 题（Hyperlane Hopper, SSSP）

• 简要思路：先把随机边高效转换成 CSR，再做并行最短路迭代。
• 简要过程：在 D-code/sssp.cpp 中保留多套建图方案（atomic、sparse、lock-free）并按数据特征选择；配合 D-code/run.sh 分测试点评估建图与计算耗时。

E 题（OpenBLAS 修复）

• 简要思路：先复现错误，再定位到内核参数与打包步长不一致。
• 简要过程：依据 E-code/readme.md 的复盘，在 ARMV9SME 参数区补齐 SGEMM_DEFAULT_UNROLL_MN 和 DGEMM_DEFAULT_UNROLL_MN（均为 16），修复 SSYRK/SSYR2K 的 packed buffer 访问偏移问题。

F 题（LU 分解）

• 简要思路：在数值稳定前提下，用分块 + OpenMP 提升 CPU 利用率。
• 简要过程：在 F-code/solver.cpp 实现 partial pivoting 的 blocked LU（NB=256）、局部块更新（GEMM_BLK=64）和前后代回代；用 F-code/driver.cpp + F-code/checker.cpp 做回归。

G 题（大模型 Prefill）

• 简要思路：在 BF16 与显存上限约束下，用“计算/传输重叠”提升吞吐。
• 简要过程：在 G-code/prefill.py 中实现 MLP 三权重（gate/up/down）CPU->GPU 流水 offload、双缓冲（ping-pong）+ 独立传输流；同时做样本打包与 varlen attention 参数传递，减少 kernel launch 与重复计算开销。

H 题（KDT-DSL 算子设计）

• 简要思路：面向 Tile 执行模型，围绕流水线和片上存储利用率做优化。
• 简要过程：在 H-code/my_kernels.py 中分别实现 task1-task4，并在 task2/3 中使用双缓冲或三缓冲设计隐藏 load 与 compute 延迟；通过 H-code/judger/judger.py 逐任务验证。

I 题（Python 动力系统加速）

• 简要思路：减少 autograd 运行时开销，将符号求导结果静态化并编译成本地代码。
• 简要过程：在 I-code/code.py 中做表达式树构建与代数化简，自动生成 C 求解核并 gcc -Ofast 编译为 .so，运行时用 ctypes 直接调用，避免 Python 解释层与 autograd 热路径开销。

J 题（近似匹配 + 功耗约束）

• 简要思路：先降候选再精验，兼顾吞吐与功耗上限。
• 简要过程：在 J-code/match.cpp 里用“双 bigram 桶过滤 + AVX2 64B 校验（<=1 mismatch）+ OpenMP 分块并行”；并接入功耗采样线程与动态节流（usleep）保证总功耗不越界。

K 题

• 娱乐题，没有做。

L 题（稀疏注意力）

• 简要思路：围绕 Top-K 块稀疏注意力，实现“正确 + 高性能”的跨后端方案。
• 简要过程：在 L-code/solution.py 中实现双路径：CUDA 使用 TileLang JIT kernel，NPU 使用分块 gather + batched matmul 的 PyTorch 实现；用 L-code/benchmark.py 做 small/medium/large 全量验证与测速。

M 题（MPI SpGEMM Top-K）

• 简要思路：两阶段通信+本地累加，平衡 shuffle 成本与计算开销。
• 简要过程：在 M-code/src/spgemm_topk.cpp 采用“先同步/索引 B，再按行归并 A”的两阶段通信；本地用稠密 SPA（spa + spa_set + spa_indices）累加并用 partial_sort 提取 Top-K，最后输出分阶段计时。

结语

本次参赛的代码开发与迭代过程，全程使用 copilot[opus] 协助完成。 仓库整理以及 write-up 由 copilot[codex] 在既有代码与日志基础上完成。