PKU HPCGame2026 个人writeup

得分情况：100%#

• 核心思路： 编程语言判定：Fortran (基于 program, implicit none, print ‘(a)’ 等语法特征) 该题目给出的源代码是一个典型的 Quine（自复制程序）。将其保存为q1.f90,并编译运行可得到结果。

1
gfortran q1.f90 -o quine
2
./quine

得分情况：0%#

得分情况：100%#

• 核心思路：发现 16 个线程分别操作独立的 Candle 结构体，但在多核环境下性能不升反降。查阅鲲鹏编程与调优指南中Cache和预取章节，发现Kunpeng 920缓存行为128B，大于Candle结构体大小，判断发生了伪共享，因此将结构体填充到128B。

1
struct alignas(128) Candle {
2
    double high;
3
    char __pad1[120];
4
    double low;
5
    char __pad2[120];
6
    double close;
7
    char __pad3[120];
8
    long long vol;
9
    char __pad4[120];
10
};

得分情况：100% （4.08s/5.5s on m=1e9）#

• 核心思路：经典的单源最短路 (Single Source Shortest Path, SSSP) 问题，为并行优化采用$\Delta$-stepping算法，预处理将邻接表转换为CSR图。

逐步优化过程#

V1：完全串行建CSR图，LLM辅助完成标准的$\Delta$-stepping算法，估计并行瓶颈主要在松弛过程中竞争距离数组，使用__sync_bool_compare_and_swap，实现原子操作版本的距离松弛。

V2：并行建CSR图，多个线程可能同时处理具有相同源节点 $u$ 的边，因此采用原子操作处理节点 $u$ 的当前边计数

1
#pragma omp atomic capture
2
local_pos = current[u]++;

这一版本在100e7的测试点上大约10s，pref采样之后分析发现

V3：建图原子操作太费时了，当前边计数是被随机访问的，原子操作也会冲突。因此将每个线程要处理的边的偏移位置数组提前分开，这样就可以使用线程私有边计数了。

1
// 直接计算写入位置，无需原子操作！
2
// thread_degree[tid][u] 是线程 tid 写入节点 u 的起始位置
3
// local_current[u] 是当前线程已经写入节点 u 的边数
4
uint32_t pos = thread_degree[tid][u] + local_current[u];
5
local_current[u]++;

此版本进行循环展开已经可以过5，6（稀疏图）测试点

V4：对于1e9边测试点依旧不够快，perf反汇编视图发现在local_current[u]++这附近是热点 尽管已经解决了跨线程依赖，但是没有改变索引u是随机乱跳的本质，考虑到n=1e6的情况下，使用uint32的local_current大约3.8MB，比1.25MB的L2 Cache大得多，所以会被随机换出，导致访存瓶颈。

但是分析题目图生成逻辑，是完全的随机图，也就是说n=1e6，m=1e9，16线程并行的情况下，每个线程处理的节点的平均出度只有63左右，作为近似正态分布。一个线程，储存一个节点的当前边计数的最大值，也就是P(最大线程私有出度>255)的概率，也就是Z分数等于=24左右的离群值概率，几乎可以忽略不记。

因此local_current可以直接用uint8，这样就能放进L2缓存，大幅度提升访问速度。此方法在m=1e9测试点上时间4.08s/5.5s。

1
posix_memalign((void **)&local_current, 64, n * sizeof(uint8_t));

得分情况：100%#

调试过程#

• 编写更多的测试，详细分析错误模式，发现：

N ≤ 16: 所有正确

N > 16: 大量错误 (45%+)

对角线上 正确

怀疑可能是SME的kernal参数或者分块参数错误

• 改变编译选项降级回SVEkernal，看看是不是kernal问题，发现SVE过不了测试的，但是SIMD版本就是正确的
• 发现测试点根本未使用SMEkernal，且SMEkernal并不是在level3调用的，对ssyrk的调用链进行分析

1
cblas_ssyrk()  // CBLAS接口
2
    ↓
3
void CNAME()   // interface/syrk.c (这个文件)
4
    ↓
5
    ├─→ [SME Direct路径] SSYRK_DIRECT_ALPHA_BETA_XX()  ← 未被调用！
6
    │
7
    └─→ [标准路径] syrk[(uplo << 1) | trans](&args, ...)
8
            ↓
9
        SYRK_UN/UC/LN/LC()  // driver/level3_syrk*.c
10
            ↓
11
        GEMM_KERNEL()       // kernel层

测试点并没有进入SME路径，而是降级回了SVEkernal，因此对level3/level3_syrk.c进行插桩分析，输出GEMM_R, GEMM_P, GEMM_Q, GEMM_UNROLL_M，N。然后交给LLM分析整个函数的执行过程，发现UNROLL_M=4，C代码会按 4 字节为步长进行切分，但是SVE的1VL为16个float元素，因此造成数值污染。尝试将param.h中此设备情况的SGEMM_DEFAULT_UNROLL_M改为16，MN改为32即解决。

得分情况：100%#

• 核心思路：采用PanelLU分解+TRSM+GEMM 的流程进行经典的并行LU分解。其主要瓶颈在GEMM上。

逐步优化过程#

V1：考虑到GEMM是主要瓶颈，因此PanelLU分解采用串行方式，TRSM较容易实现并行，因此采用并行。GEMM采用LLM建议的多种优化方式，设计L2-L1-寄存器的三级分块，使用openmp的simd指令进行内层指令级并行，使用__builtin_prefetch预取内层循环数据。

V2：再次改进GEMMkernal，使用Intrinsics函数进行simd。记录执行时间，发现此时的瓶颈已经转移到PanelLU分解上，因此PanelPL分解的行消元步骤进行并行化改进。

得分情况：100%#

• 一部分层常驻于显存，其他层需要时异步装载，异步卸载。分三个cuda stream，一个用于推理，一个在推理之前预装载层，一个卸载层。

逐步优化过程#

V1：根据显存计算出，常驻38层，动态加载26层，tokenizer常驻，为后26层注册异步钩子，以确保使用前完成发生层加载，使用后卸载。每层计算前，必须确保前面的计算完成（因推理过程由一个stream异步发射，因此可能出现发射层A计算，发射层B计算，发射层A卸载，此时层A还在计算，但是卸载命令已经启动）

V2：发现计算时间无法完全遮蔽加载卸载。采用batch化输入，以延长每一层推理时间。

V3：发现时间比要求稍长，怀疑是padding过多。为尽可能减少所需的padding，因此选择先按长度排序，再划分为batch。

得分情况：100%#

任务1#

单个SM并行，二级流水线，分为

1.加载 2.VXM计算和储存

任务2#

32个SM在K轴上并行，M，N分块大小分别为128，128，二级流水线，分为

1.加载 2.MXM乘加计算

任务3#

32个SM在K轴上并行，三级流水线，分为

1.加载 2.VXM去除量化 3.MXM矩阵乘加

任务4#

job数根据Q块数量设置，三级流水线，分为

1.加载 2.MXM算Q @ K_j → S_j（因为不依赖j-1数据） 3.Softmax(S_{j-1}) + P@V + 更新O，VXM和MXM操作，因为顺序依赖无法ILP并行

通过缓冲复用，可以仅使用两个K_tiles， S_tiles缓冲， V_tiles必须三个

得分情况：51%#

逐步优化过程#

V1：在LLM辅助下实现了一个简单的符号数学类，可以实现自动微分，以及对表达式进行零元消除，单位元消除，符号折叠，常数折叠等操作。使用此符号数学类，对加速度求偏导转换为标准的M，C矩阵，并简化矩阵内计算式。

V2：因没有使用原生cython环境，因此将整个化简后的动力学算式输出为C代码，并使用gcc或clang编译，随后使用ctypes以so库方式加载算式，包装为python函数返回。