CS Memos

CS110 Project 3 调优日志

13分钟阅读

关于

这部分是笔者在进行 ShanghaiTech 的 Project 3 优化的实录，具体要求可见：项目页面

基本分析

首先这段代码是一个基本的 Chacha20 加密+ Merge Tree 算法，关于这两个的算法似乎已经没有什么优化了，所以接下来的重点都应该在应用程序的并行和热点的优化，接下来我再准备考虑内存分布。

OpenMP Parallel

这里能用 OpenMP 的并行的地方比较少，似乎就只有对 merge_hash 的调用和 merkle.c 里面的循环

嗯还是非常有效的，可以从 baseline 跑到 bare openmp 了，Gradescope 上大概 15 秒

OpenMP SIMD

试了一下，感觉挺多的循环上面都是有依赖的，加了还不如不加，以及有一些小的循环，想了想直接展开了。

读取

由于我们是统一的 main.c，关于从文件读取的话理论上都是一样的，接下来就是内存分析了，但是又不想这么快就分析 cacheline 和 prefetch。懒了，随便对一个耗时最大的 memcpy 用了一下 omp 并行读取，体感确实快了大概 1s，交上去也确实快了不少。至少能在 12s 左右了。

Trick

偷偷摸摸提交了一下 -O3 优化，发现 gs 上能跑到 3.4 秒！！！加油 （更正，后面又跑了一次 3.0 又跑了 2.4 秒，在 77 上大概 1s）

Unrolling chacha

现在尝试对 chacha 用展开，定义了一个 define 来做字符替换，然后重复 10 次。

终于！进入 10s 圈了！接下来是 77 ，仍然对 2 号数据计时，大概 2.4 秒。

ASM inline

终于到了我最喜欢的 ASM 内联环节！先下刀的是 merkle 的循环，原版是这样：

    for (int round = 0; round < 10; ++round) {
        for (int i = 0; i < 4; ++i) {
            state[i]   += state[4+i];  state[i]   = ROTL32(state[i],   7);
            state[8+i] += state[12+i]; state[8+i] = ROTL32(state[8+i], 7);
        }
        for (int i = 0; i < 4; ++i) {
            state[i]   += state[8+i];  state[i]   = ROTL32(state[i],   9);
            state[4+i] += state[12+i]; state[4+i] = ROTL32(state[4+i], 9);
        }
	}

然后把中间的几个循环改成汇编，特别是 ROTL，应该会有很大优化，并且展开内层小循环。

这里忘记分析数据依赖了，所以没有考虑能不能重排以及分散 load/store，交给以后的自己（x

同时试了一下 -march=native，现在 77 能跑到 1.3 s 了。

AVX 512

其实这一步放在了后面，主要是懒得重构（x

这一步对 chacha 用 AVX 512 的写了，嗯还行。尝试了一下单独对 chacha 用 O3 优化，发现 gs 能跑到 5s 左右，于是把这里用 avx 写了，嗯基本上是面目全非的改动。

然后尝试了一下寄存器绑定，用 register 关键字绑定到 xmm ，其他没有改，发现居然快了一点？但是可惜的是这里不能用 O3 了，否则直接报错，估计是把我的寄存器给占用了。

ASM again

然后尝试了一下汇编，发现 icx 和 gcc 的 O3 都差不多，而且在 O0 状态下即使是 intrinsics 也是会更复杂的，于是果断用 asm 重写，提交

嗯，gs 能跑到 3.5 秒了， 77 也能 1.1 秒左右

再尝试了 loop unrolling，更快了，gs 上 3.0 甚至 2.8。

Then merkle？

刚刚使出了浑身解数，终于让 chacha:merkel 从原来的几乎 4:1 变成了如今大概 2:3 的水准，啪叽啪叽！！！！现在本机上大概 tc 2 能跑 1.28s.

接下来继续优化 merkel，不然总觉得对不起它了。

试了一下，开全部的 O3 ， tc2 大概能跑到 1s 左右，对于 tc0,1 这种小数据的优化就几乎没有了，在 0.1～0.0x 数量级。如果用 asm + 入口函数 O3 的话还是 1.2 没有变化，但是只有 merge_tree 以及原始 loop 的话好像会更加迷人，跑到了 1s，小数据的优化也有！开抄！

尝试了一下 fallback 我的 merkel 到非 asm，居然会更快，而且对小数据的优化体现出来了？说不定用了 avx？让我看看

只 merge tree 优化：

CompilerLocalCA
gcc0.27/0.54/1.001.0
mpicc0.30/0.57/1.05No mpi
icx(global o3)0.27/0.51/1.01No omp
clang0.27/0.55/1.001.0
gcc(global o3)0.27/0.50/0.95GLIBC
clang(global o3)0.28/0.61/1.03GLIBC

最后的骄傲

参照 icx 的写法，我写了一个（应该）对 intel 机器友好的汇编 inline,其实他的优化非常巧妙，首先能够用 ymm 装下一个循环就不做循环！！！！这太强了

gradescope min 2.14s, 77

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 04:16:05 CST===
===TIME 0===
Average real time: .30660000000000000000s
===TIME 1===
Average real time: .55430000000000000000s
===TIME 2===
Average real time: 1.05175000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 04:16:45 CST===

结束了？

考虑到 false sharing,我在尝试把 4 个 block 合并在一起进行处理之后再合并输出，这样能减少 false sharing 的几率

本机：

===T5 TEST Started at 2025年 05月 21日 星期三 12:31:12 CST===
===TIME 0===
Average real time: .22280000000000000000s
===TIME 1===
Average real time: .40000000000000000000s
===TIME 2===
Average real time: .76560000000000000000s
===T5 TEST Ended at 2025年 05月 21日 星期三 12:31:12 CST===

77:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 12:31:13 CST===
===TIME 0===
Average real time: .29295000000000000000s
===TIME 1===
Average real time: .53735000000000000000s
===TIME 2===
Average real time: 1.05520000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 12:31:53 CST===

可以看到，大数据提升不明显，但是小数据可以提升大约 0.01～0.02 的分数

再次尝试对入口 O3 简单优化： 本机：

===T5 TEST Started at 2025年 05月 21日 星期三 12:35:40 CST===
===TIME 0===
Average real time: .22260000000000000000s
===TIME 1===
Average real time: .43480000000000000000s
===TIME 2===
Average real time: .72340000000000000000s
===T5 TEST Ended at 2025年 05月 21日 星期三 12:35:40 CST===

77:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 12:35:53 CST===
===TIME 0===
Average real time: .29075000000000000000s
===TIME 1===
Average real time: .53420000000000000000s
===TIME 2===
Average real time: 1.05220000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 12:36:32 CST===

几乎没什么用

Profile！

原版 ca1.0/gs2.4 我发现自己现在虽然快了特别多，但是 omp 的同步开销变大了， overhead 很严重。 考虑一下使用线程池了，懒了，晚点写。

看看 77 的表现：

嗯，不尽人意，最后的 omp 同步开销太大了

看看 4 blocks 的并行：

本机：

77：

看起来某种程度上确实减轻了 merkle tree 的同步开销，但是并没有优化多少。

77 Test

Chacha4 + Static + Tail:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 12:31:13 CST===
===TIME 0===
Average real time: .29295000000000000000s
===TIME 1===
Average real time: .53735000000000000000s
===TIME 2===
Average real time: 1.05520000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 12:31:53 CST===

Chacha4 ASM Dynamic:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 17:32:31 CST===
===TIME 0===
Average real time: .29960000000000000000s
===TIME 1===
Average real time: .53525000000000000000s
===TIME 2===
Average real time: 1.02700000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 17:33:09 CST===

Chacha4 O3:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 17:35:18 CST===
===TIME 0===
Average real time: .29055000000000000000s
===TIME 1===
Average real time: .52835000000000000000s
===TIME 2===
Average real time: 1.05605000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 17:35:57 CST===

Chacha4 Static + No Reg Modify:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 17:38:18 CST===
===TIME 0===
Average real time: .29975000000000000000s
===TIME 1===
Average real time: .53620000000000000000s
===TIME 2===
Average real time: 1.05400000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 17:38:57 CST===

Chacha4 + Tail + No Reg Modify:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 17:43:14 CST===
===TIME 0===
Average real time: .29690000000000000000s
===TIME 1===
Average real time: .53470000000000000000s
===TIME 2===
Average real time: 1.04860000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 17:43:53 CST===

不是哥们，如果我开 chacha4 Ofast:

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 20:13:21 CST===
===TIME 0===
Average real time: .28715000000000000000s
===TIME 1===
Average real time: .52450000000000000000s
===TIME 2===
Average real time: 1.03435000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 20:13:59 CST===

最终还是选用了 Chacha4 + Tail + No Reg Modify，gs 最快是 1.97, 77 上

===20 LOOPS TEST Started at 2025年 05月 21日 星期三 20:21:37 CST===
===TIME 0===
Average real time: .28520000000000000000s
===TIME 1===
Average real time: .55635000000000000000s
===TIME 2===
Average real time: 1.03835000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 21日 星期三 20:22:16 CST===

但是理论 O3 最优能达到 gs 1.7, 而且非常稳定，不知道为什么我用 ASM 却飘忽不定的，也许是因为我全局都在用 AVX 操作的原因，还没有弄清 AVX 的缓存结构，虽然在 77 上都没太大区别就是了……

以及 Cache miss 还是居高不下，即使是 O3 似乎也对这个无能为力，那我就默认这是不可立即优化的吧……

热点分析

我分析了一下程序的热点，发现有很多的 Spin and Overhead，可能是 OpenMP 同步造成的

Note

提示无法追踪 module

sudo sh -c 'echo 1 > /proc/sys/kernel/perf_event_paranoid'

可以看见，chacha 中有一些线程比较空闲的没有运用上，然后最后尾部的处理会独占一些时间，以及 chacha 和 merkle 的衔接会有一定的空闲，这里如果能优化将是绝杀！

想到了！！！

第一次的 omp 的开销估计是内存同步读取的开销，于是我在同步读取的时候进行了第一次计算 chacha，这样就能更快了！

果然，同步不见了！！！

而且 MEM 的访问也变少了，原来：

 Performance counter stats for './program ./testcases/test_2.meta':
 
       178,921,916      cache-references                                                      
       114,232,031      cache-misses                     #   63.84% of all cache refs         
 
       0.767909754 seconds time elapsed
 
       3.113853000 seconds user
       1.025536000 seconds sys

现在是：

 Performance counter stats for './program ./testcases/test_2.meta':
 
       141,726,864      cache-references                                                      
        95,687,178      cache-misses                     #   67.52% of all cache refs         
 
       0.686425677 seconds time elapsed
 
       2.736235000 seconds user
       0.499999000 seconds sys

抽卡多次之后， 1.8！！！77 上也是第一次看到 1s 以下了！

===20 LOOPS TEST Started at 2025年 05月 23日 星期五 02:11:49 CST===
===TIME 0===
Average real time: .27240000000000000000s
===TIME 1===
Average real time: .49100000000000000000s
===TIME 2===
Average real time: .95645000000000000000s
===20 LOOPS TEST Ended at 2025年 05月 23日 星期五 02:12:25 CST===

难道最后还得上生产者——消费者了吗……

未完待续……（走了走了）

线程数, 平均时间(s)
8, 1.133
9, 1.116
10, 1.070
11, 1.060
12, 1.020
13, .856
14, 1.010
15, .966
16, .953
17, .936
...
25, .890
...
86, .880
...
111, .883
112, .883

Final

最终成绩：

最近的笔记

关系图谱