MachSuite.nw在MachSuite这套benchmark里属于存在感不高的一个。kernel不大、输入构造也不花哨、跑起来很快，很多人在做体系结构实验时会把它和viterbi、md之类一并归为“动态规划小核”然后直接快进。实际上，当你把nw真正放到perf下面或周期级模拟器上去看时序，会发现它既不适合拿来做并行算力mapping，也不适合当作普通流式访存负载来预取。它最珍贵的，是用来考察跨层流水线响应、链式依赖、以及小矩阵脉动式数据搬移的那一小块试验田。这篇拆解记录，就当是给后续要在MachSuite上做二次开发的人先蹚一遍路。
我会按照“算法背景 → 代码路径 → 实测数据 → 架构实验用法”的顺序来讲，最后补几个我自己踩过的坑。整个过程不依赖某个特定工具链，你拿到任何一套x86平台都能复现。
1. 为什么把MachSuite.nw单独拿出来拆
1.1 在MachSuite家族里，nw到底是个什么位置
MachSuite的目录列出来，大多数benchmark都有一个明确的主循环热点：GEMM是三层乘法循环，FFT是一堆蝶形运算，BFS的核心就是一条while队列+do-while邻居遍历。nw不一样，它的代码组织相对“扁平”，没有太多的启动-检测逻辑，也没有很多kernel可以选择，热点非常集中，几乎就是两个嵌套循环从头走到尾。
单从工作量看，nw像是拿来凑数的那个。可如果你把它放进一次体系结构研究里，它却承担着一个不太好替代的作用：经济地制造一条需要跨两次循环边界的依赖链。BFS同样有依赖链，但BFS的依赖链是“队列条目之间的指针追逐”，链长和负载均衡波动很大；GEMM的乘法累加可以靠重排和分块把依赖藏得很好；nw的递推却是一种“菱形展开后仍然甩不掉对角线依赖”的结构，乱序执行窗口再大，也无法把一行算完再去算下一行。
换句话说，在MachSuite这一组负载里，nw代表的是“动态规划类的串行瓶颈”。你在研究预取、多核分频、或者近存计算时，如果想找一个既不会因为分支乱跳太难预测、又充满访存依赖的样例，nw可能就是最省事的一个。
1.2 这篇拆解能帮你解决什么问题
很多人拿到benchmark之后的第一反应是直接跑分，看总执行时间或者IPC。nw这种kernel，直接跑分的结论非常单调：算得不多、访存很多、IPC不高。但这个结论对后续设计没有任何指导意义。这篇跟做的价值在于，把抽象结论落实到几个可以操作的分辨率上：缓存行被复用了几次，表格数据是被一次性读取还是反复取用，向量化起不起作用，跨行计算时下一行需要的依赖是否已经就绪。
如果你是想拿nw做“加速器设计”的验证，这篇也能帮你定位到合适的kernel切分点。MachSuite原始代码里没有为我们划好region，哪一段循环应该被放进硬件加速器、哪一段留着软件跑，需要你自己判断。我在第三节给出一个等价重构版本，保留原始依赖性质，但把边界划分得更清楚，方便你在模拟器上做抓取和重放。
2. 算法还原：nw在算的到底是什么
2.1 先替非生物背景的同学补一段背景
nw是Needleman-Wunsch的缩写，在生物信息里用来做两条序列的全局最优比对。你可以把两条序列想成两个字符串，字符串里的每个字符是一个碱基或者氨基酸残基；比对的目标是给它们配对齐，考虑三种操作：字符匹配、字符替换、插入空隙。打分规则就是匹配给正分、替换和空隙给罚分，最后要找到一个总得分最高的排列方式。
这不是一个可以靠贪心解决的问题，因为你每在一个地方插入gap，都可能彻底改变后续匹配的对应关系。标准的解法就是动态规划：用一张二维得分矩阵把子问题逐步填满，每个格子里的值取决于左、上、左上三个邻居的得分，再加一个按分数表得到的替换得分。
在MachSuite里，nw对应的输入通常被生成为两条“看起来很像样”的随机序列，分别对应两个物种或两个个体间某个基因区域的比对。生成逻辑并不复杂，但需要保证有一定长度，这样二维矩阵才会对cache造成足够的压力。小规模跑起来不够明显，大规模类别会让你清晰地看到逐行遍历带来的cache miss持续升高。
2.2 递推式与数据依赖图的本质
动态规划核心里就这么一个递推式，我用最容易核对的形式写出来：
S[i][j] = max( S[i-1][j-1] + substitution_score(A[i-1], B[j-1]), S[i-1][j] - gap_penalty, S[i][j-1] - gap_penalty )注意看依赖关系：当前格子(i,j)，同时要看上一行的j-1、上一行的j、以及本行的j-1。
这意味着如果你按行主序遍历矩阵，看起来像是“从左往右逐格推进”，但计算下一行时又需要上一行的旧值，所以整个计算矩阵存在一条“向右和向下同时扩散的依赖带”。严格来说，所有动态规划类问题都可以划成反对角线并行：同一条反对角线上的格子互相没有依赖，可以并行算；但每推进一个反对角线，所有格子同时依赖于前一条反对角线。MachSuite的原始实现大多数情况下不会去显式做这种对角化处理，而是简单直接按行循环，因此在现代乱序执行CPU上，你能观察到的效果就是：
- 同一时间只有一条狭窄的“当前行+右侧若干格子”的依赖窗口是活跃的；
- 即便流水线能同时加载多个内存请求，它们最终都要汇入同一个由行末向下一行递推的串行更新路径；
- 如果体系结构没有好的ALU压栈机制或比较链合并能力，每次三元max都会造成流水线停顿。
你可能会想：那能不能把矩阵转置成按列访问？很遗憾，转置后依赖从“右->下”变成“下->右”，本质不变，只是访存的cache局部性换了个方向，串行依赖依旧。这也解释了为什么nw很难通过简单的编译选项优化获得巨大提升。
2.3 验证逻辑与输入规模的影响
MachSuite的benchmark一般会带一个验证步骤，nw的验证会重新根据你算出来的得分矩阵回溯，或者比对一组预先算好的答案。在分析的时候，我建议把验证逻辑和真正的kernel分开关掉，因为验证阶段往往包含大量回溯指针跳转，会严重污染perf的统计结果。如果做模拟实验，输入量级更是关键，过小的序列长度会让整个执行时间停留在cache能容下的范围内，测出来的几乎全部是流水线效果；过大的长度又会让模拟器跑上几天。对nw，我通常会把矩阵的行/列长度调到能够超过L2容量、但总数控制在百万格子以内的范围，这个区间最能分辨“访存延迟”对内核的影响。
3. 源码阅读：从入口到热点kernel的完整路径
3.1 先跟一遍nw的调用路径，别上来就抠循环
MachSuite每个benchmark的基本框架都是：解析参数 → 生成或读取输入 → 调用计算kernel → 验证结果 → 汇总输出。nw也没有脱离这个套路。我拿到代码的第一件事是打开主函数，把kernel调用前后的打印和验证逻辑用注释标出来，然后让程序只执行kernel本身。这样做的原因是，打印输出的时间开销足以干扰后续精确测量，更不用提操作系统在stdout刷新时产生的频繁切换。
在nw原始文件里，输入是一段人为构造的序列对，读取到内存后，会先做一行首行/首列的初始化。首行首列的填充本质上是一个gap累积过程，依次增加罚分得分。这个初始化只有O(n+m)的复杂度，但因为它处理的是跨行数据，很多人在做cache分析时容易忘记：初始行的数据集在L1里根本没有预热的状态，第一次进入主循环时，对score表的访问基本全是cold miss。
3.2 我重建的最小等价内核
出于后续做周期级模拟器实验的便利，我一般不会直接在MachSuite源码上做修改，而是提取出等价逻辑单独编译。下面这段是我习惯用来做cbenchmark分析的最小版本，它保持了与原始nw一致的依赖方向和访存模式，同时去掉了所有外围初始化干扰：
#define MAX_LEN 4096 int score[MAX_LEN][MAX_LEN]; char seq_a[MAX_LEN], seq_b[MAX_LEN]; int blosum[24][24]; static inline int max3(int a, int b, int c) { if (a > b && a > c) return a; if (b > c) return b; return c; } void nw_kernel(int len_a, int len_b) { for (int i = 1; i < len_a; i++) { for (int j = 1; j < len_b; j++) { int s = blosum[(int)seq_a[i]][(int)seq_b[j]]; int match = score[i-1][j-1] + s; int del = score[i-1][j] - GAP; int ins = score[i][j-1] - GAP; score[i][j] = max3(match, del, ins); } } }这个版本里你看到的关键事实是：score是二维结构，按行填充；每次算score[i][j]时要读score[i-1][j]，而score[i-1][j]在上一行循环里已经写入过，距离现在可能隔了完整的一行长度，所以无法保证命中L1；score[i][j-1]则刚写过不久，能命中L1或store buffer。blosum表的访问由两条序列字符决定，因为序列本身是随机分布，它的访问模式同样是近似随机的，破坏预取器的顺序性。
相比MachSuite原始实现，我的最小版本只保留了“得分矩阵维护”这部分。原始代码有些版本会额外维护一个方向矩阵用于回溯，方向矩阵的写入模式与得分矩阵完全相同，本质上只是多了半行数据写；量化时引入它反而会掩盖访存带宽利用率，因此我的建议是分析阶段先去掉，等正式评估完整正确性再放回来。
3.3 代码里容易忽略、但影响性能的细节
有几个藏在源码里的小细节，会在实测中明显放大差距。
- 一是序列字符到分数表的映射。如果实现是把字符当作小整数直接索引blosum，那么score表访问虽然随机，仍然是单字节整数到二维数组的查表动作，比较友好；若在查表前加了一层结构体索引，则可能多一次依赖链上的指针解引用。
- 二是max的展开方式。编译器是否将三元max变成条件移动指令，直接影响是否产生组合分支。实测中，
-O3倾向于生成无分支的max序列，但依赖链依然存在于寄存器之间。 - 三是数组维度定义。MachSuite的nw如果用了静态二维数组，意味着矩阵总大小在编译期固定，比较容易放入BSS段；改成动态分配后，首次接触页面会产生严重的page fault冲击。做对比实验时，两种分配方式会导致低速区不同的初始执行代价，你会看到一遍快一遍慢的现象，容易误判成输入随机性问题。
4. 实测：算出来不是瓶颈，搬数据才是
4.1 我的实验环境与测量方式
我用来做这轮分析的原型环境是一台常见的64位Linux服务器，12线程，主频约2.6GHz，L1数据缓存32KB，L2缓存1MB，L3缓存16MB，编译器开-O3 -funroll-loops，工具只用了标准perf计数器。我刻意没有使用任何特殊调优参数，因为这些参数会拉平不同architecture之间的差异，让你看不出nw原本的特征。
测量流程分三步。先把序列长度定在256、512、1024、2048、4096五个档次，每个档次跑10次取中位数；然后用perf stat -e cycles,instructions,cache-references,cache-misses,branches,branch-misses记录整体；最后再用perf record把采样点落在kernel循环上，做一个热点收敛。整个过程只统计kernel本身，没有把初始化和验证时间计入。
4.2 一组有代表性的计数器读数
以2048×2048规模为例，我拿到的一轮典型数据是这样的（数值只表示数量级关系，不同微架构会有偏移）：
| 指标 | 观察值 | 含义 |
|---|---|---|
| 总指令数 | 约4.2×10^7 | 主要来自内层循环的取数、求max、存数 |
| 总周期数 | 约1.1×10^8 | 平均CPI约2.6 |
| L1数据cache miss率 | 6%~9% | 主要是blosum查表和跨行读取导致 |
| L2 miss率 | 25%~30% | 每行跨越后矩阵远大于L2的可见影响 |
| 分支预测miss率 | 小于1% | 内层分支很少，branch miss影响不大 |
| 向量化指令占比 | 很低 | 自动向量化几乎无效 |
注意最后的向量化一项。很多人看到max运算就认为可以AVX并行处理多列，实际不行。原因还是那条对角依赖：列j的结果会影响列j+1的ins项，所以同一行内严格串行。GCC的全auto-vectorize在这里基本只是把第一行初始化向量化，主循环依旧是标量的。如果你看到某个实验声称对nw做了SIMD优化并提速，那必然是用分块或者改变了算法结构，比如分成多个band分别以反对角线方向计算，否则在概念上说不通。
4.3 为什么“缓存命中率高”但时间还是慢
nw的单格计算量极少，理论上再慢的CPU也能流水化执行。实际瓶颈在于依赖链的时间跨度：score[i-1][j]在上一行的j列计算完成后才写入，而它需要等待上一行的j-1与j-2各自完成，所以实际上每一行是沿着对角线逐步解锁的。整个执行序列变成了一条锯齿状的前沿推进，而不是一条平坦的流水线。
当你把L1 miss延迟算进这条链里，每次跨行取数可能带来几十个周期的等待。即便有memory-level parallelism，能让多次缓存未命中重叠发出，最终消费端仍然需要这些数据按依赖顺序到达。等待时间掩盖了计算时间，这就是nw最典型的“访存延迟敏感而非带宽敏感”特征。可以把它的表现类比成一条只有几个工位的装配线，物料是提前堆好了，但每个工件都要在同一个工位处理后才能交给下一站，这时候无论你多快地把物料搬到仓库，产出率仍受限于装配线自身的节拍。
5. 架构研究里的正确打开方式
5.1 在周期级模拟器上跑nw需要重新裁剪
如果你准备把nw作为一个workload挂到周期级模拟器上做微体系结构评估，最忌讳的事情是直接把MachSuite整个工程编译后丢进模拟器。模拟器运行速度比真实硬件慢若干个数量级，而你并不需要真的跑完整个序列对齐。
我的做法是从重建的最小内核出发，做三处裁剪。第一，把矩阵规模裁到能匹配模拟器的L2大小，又足以超过L1大小；这个量级在256×256到1024×1024之间比较合适。第二，去掉验证阶段，只保留主循环。第三，如果你研究的是访存子系统，可以稍微改变布局，把score矩阵改成按块分配，让每一行在内存中的起始位置按256字节对齐。这样能方便你在模拟器的trace里对齐地址，观察bank冲突和MSHR站队情况。
裁剪后的内核必须与原版做数学等价性校验。我会先把输出得分矩阵的最后一个元素打印出来，分别跑原版和裁剪版，比对数值一致后再进模拟器。这一步看似多余，但往往能拦住一些只有编译器才看出来的微妙差异，比如整数溢出、无符号比较、数组越界写。
5.2 用nw来压测预取器和Runahead
在微体系结构预取器研究里，nw比BFS更干净，却比GEMM更刁钻。它给出的访存请求大部分是连续的列方向读入，跨行读请求则会周期性跨越一个固定stride。如果你在写一个流式预取器，会发现顺序预取在列方向上命中很高，但行与行之间的固定步长预取很容易踩空，因为blosum表查表带来的随机访存又混在里面。
这恰恰是设计“步长预取器”和“上下文预取器”的绝佳测试样例。评估时建议把nw和另外一组纯顺序流内核做对比实验：如果某个预取器在nw上提升明显，但在GEMM上反转退化，说明它对非固定模式太激进；如果nw上完全无效，说明预取器只擅长平整的顺序流，对锯齿状依赖带没有识别能力。你可以用两个基准的对比结果避免得出“一测一个准、换了负载就不行”的片面结论。
5.3 用作加速器mapping时的切分原则
还有不少人拿nw做近存计算或者可重构加速器的输入负载。这时最该关注的核心是：要不要把所有计算逻辑全部放进加速器？我的经验是，单格计算本身太简单，如果用一个大的脉动阵列去重放整个矩阵，时间损耗大部分发生在数据灌入和结果写回的搬运上。更划算的切分是把“列方向的连续分数表访问”留给CPU侧，让加速器只负责对角线方向的依赖链更新，并且让加速器与CPU之间的数据交换保持行块粒度。
在这个切分思路下，nw的访存特点会变成优势：它天然有行内连续写、块间固定stride的特点，只要块边界设置得当，跨块数据交换量很小。但要注意“回溯矩阵”的问题，标准Needleman-Wunsch需要保存在每个格子上选择的路径来源。如果你为了加速只实现了得分矩阵部分，回溯时又要重新读取原序列和得分，可能导致整体开销反而更大。实际项目里我赞成先做一次profiling，把回溯频率和访存交织画出来。对于纯性能研究可以忽略回溯，只保留得分矩阵；对要交付的加速单元则必须把回溯存储一起纳入面积预算。
6. 重写笔记与后续可以继续做的方向
6.1 拆完nw之后我认可的三个结论
第一，nw在MachSuite里不是用来测“峰值算力”的，它的慢源自依赖链而非吞吐不足，任何只看总执行时间不看延迟构成的对比都容易误导。第二，默认二维矩阵实现里，横向顺序访问和纵向跨行读取的叠加，让它在cache层级上呈现出“中段亏损”的特征，L1命中率尚可，L2开始逐步崩坏，L3勉强补救，非常适合观察多级缓存之间的失效传递。第三，一切的优化动作都绕不开那条对角线解锁节奏，你可以在软件层面重排格子计算顺序来改变依赖带的方向，但不能取消依赖本身。
6.2 我实际用过、并且觉得值得扩展的两个方向
第一个方向是把nw粘上trace采集工具，生成带地址注释的内核trace，然后拿去训练一个简单的地址流预测器。这是我个人在预取器实验里比较顺手的一条管线：先在真实机器上收集perf sample，过滤冗余指令，只留下访存指令；再用周期级模拟器重放trace，观察预测器和cache之间的交互。nw的内核小，trace文件不会爆炸，这个优点在批量实验时非常实用。
第二个方向是把它扩展到banded Needleman-Wunsch，也就是在矩阵上切一条带状区域，只算靠近主对角线的部分。切band之后，依赖链变短，列间并行度变大，访存模式也更接近纯流式，反而很适合做近存加速验证。你可以在MachSuite.nw的基础上加一个band参数，让代码既能跑原版全矩阵，又能跑裁剪版，这样同一套benchmark可以同时覆盖串行瓶颈场景和可并行场景，比较维度会比单一版本丰富很多。
如果你之后也打算用MachSuite系列做下一轮实验，我建议把nw放到BFS之后来跑，先看随机访存型负载，再看依赖型负载，最后回到GEMM这类规则计算型负载，三者合起来基本能把“访存子系统要面对的敌情”摸个七七八八。当然真要跑加速器对比，还要记得把验证开关关掉，否则回溯阶段的时间会被误算进kernel周期里，那个坑我踩过不止一次。
到O(nK log m)实战)
