MachSuite 里的基准我一个个跑下来nw 是让我印象比较深的一个。nw 全称 Needleman-Wunsch是做生物序列全局比对的动态规划算法放在体系结构评测里它代表的是典型的数据依赖密集型负载。这个 benchmark 看起来只有两层循环加一个求最大值但把它放到模拟器里跑一遍会发现芯片内部的访存压力、流水线停顿、缓存行为全都不太一样。这篇就具体讲讲 MachSuite.nw 的算法实现、微架构特征、我实测到的性能数据以及针对它做优化时容易踩的坑。如果你是刚接触基准测试分析或者正准备拿 nw 做加速器评估这篇应该能帮你少走一些弯路。1. 先把MachSuite和nw放在一起看1.1 为什么体系结构研究喜欢用这类基准MachSuite 这类基准套件的定位并不是给用户跑分而是让体系结构研究者在可控环境里反复对比不同微架构设计。完整应用基准虽然更接近真实负载但编译依赖多运行时间也长放到模拟器里一次要跑几小时甚至几天。MachSuite 把一段典型算法从真实应用里抽出来用几十到几百行 C 代码实现每个内核自带输入集和参考输出编译过程几乎没有额外依赖非常适合在模拟器里做全流程探索。我第一次用它时从拉代码到跑通全部内核只花了一下午。这个体验比很多大型基准好很多。nw 在这个套件里是让我印象最深的几个之一。它解决了生物信息学里一个非常基础的问题给定两条序列找出全局最优比对。放在体系结构研究里它的价值不在于算法本身有多复杂而在于它刚好暴露出数据依赖和访存局部性这两个体系结构最关心的矛盾。你把它放到乱序执行核心上会发现流水线不像跑整数计算那样满速运转你把它放到加速器上又会发现它的并行窗口其实很规整。所以用 nw 做 benchmark能同时看到通用处理器和专用硬件之间的差距。1.2 nw在解决什么问题算法流程是什么Needleman-Wunsch 做的事情可以这样理解两条序列字符一一对比匹配加分错配扣分插入或者删除算 gap 惩罚。算法维护一个二维得分矩阵 DD[i][j] 表示第一条序列前 i 个字符和第二条第 j 个字符已经比对完时能拿到的最高得分。填充规则很简单每个格子从左上、上方、左方三个方向取最大值D[i][j] max( D[i-1][j-1] score(a[i], b[j]), D[i-1][j] gap, D[i][j-1] gap )填完矩阵之后还要回溯从右下角沿着记录下来的来源方向一路回到左上角这条路径就是最优比对结果。回溯阶段相比填充阶段计算量小很多但它是严格串行的每个格子要先知道下一个格子的方向才能走没法直接并行。很多做加速器的人容易忽略这一段实际上它会影响最终输出正确性设计时绕不开。1.3 MachSuite里nw的实现长什么样MachSuite 里的 nw 具体代码我没有原样抄过来但核心结构大概是下面这样。先初始化第一行第一列的 gap 惩罚然后两层循环填充矩阵#define N 128 int score[N1][N1]; int a[N], b[N]; int gap -1; for (int i 0; i N; i) { score[i][0] i * gap; score[0][i] i * gap; } for (int i 1; i N; i) { for (int j 1; j N; j) { int match (a[i-1] b[j-1]) ? 1 : -1; int diag score[i-1][j-1] match; int up score[i-1][j] gap; int left score[i][j-1] gap; score[i][j] diag up ? (diag left ? diag : left) : (up left ? up : left); } }这里 score 是完整的二维数组行主序存储。内层循环遍历 j对当前单元格要读 score[i-1][j-1]、score[i-1][j]、score[i][j-1]再写 score[i][j]。每一次循环产生三次读和一次写类型是 int只用到 4 字节。缓存行如果是 64 字节理论上一行数据可以被连续 16 个单元格复用但实际情况要复杂得多因为三路访问的地址偏移差很多缓存行利用率并不高。这一点我在下一节单独拆。2. 从微架构角度拆解nw的工作负载特征2.1 数据依赖链决定并行度上限我先把填充阶段看成一张有向无环图每个节点是 D[i][j]依赖 D[i-1][j]、D[i][j-1]、D[i-1][j-1]。在单核执行时这些依赖会形成很长的链。尤其沿对角线方向从 D[0][0] 到 D[N][N] 的路径长度是 2N 步每一步都要等上一步写完才能算。IPC 上不去并不是因为分支多而是因为每个循环迭代都被前一个迭代的数据结果卡住。如果换一个视角所有满足 ijconstant 的格子彼此之间没有依赖也就是说同一条反斜对角线上的节点是可以并行计算的。这个并行度从矩阵左上角开始是 1走到中间变大到 N然后到右下角又降回 1平均差不多是 N/2。加速器想利用 nw 的并行性主要就是利用这个波前特性。但在普通 CPU 上指令级并行最多只能跨几个对角线的距离乱序窗口再大也覆盖不了多远。2.2 访存模式与缓存行为nw 的访存模式比想象中更要命。行主序存储时计算 D[i][j] 需要访问三个位置D[i-1][j] 的地址和当前行差一行跨度是 N 个 intD[i][j-1] 是当前行前一个位置连续访问D[i-1][j-1] 的偏移是 (N-1) 个 int。如果 N128跨一个行等于偏移 512 字节也就是 8 个缓存行如果 N1024偏移 4KB正好是一页大小跨页访问带来的 TLB 压力也不小。我对 1024×1024 的输入算过一笔账score 矩阵大约 4MB远超常规 L1甚至超过 L2。填充阶段每个单元格要读三个整数、写一个整数总计约 400 万次访存。按理说这个次数不算多但问题在于访问的地址是三条不同的流而且每条流都是跨行的缓存行里只用到一个 4 字节实际有效利用很低。所以 nw 看起来不像 sort 那样随机却依然能把缓存替换策略打得很难受。2.3 控制流和乱序执行的相互作用这个代码里分支其实很少只有一个三元运算符和最后的比较。分支误预测率通常很低乱序执行核心根本不需要担心跳转开销。真正的瓶颈是 load-use 延迟链读回 score[i-1][j] 之后立刻做加法和比较这个依赖链必须等内存访问完成。现代处理器可以同时发起多个 load但 nw 的每个迭代又都需要上一次迭代写入的 score[i][j-1]等于把访存延迟一段段串起来。编译器对三目运算符通常生成条件移动指令条件移动不会导致分支预测失败但会延长执行链。我测到 nw 的分支误预测率只有不到百分之零点几但流水线前端仍然会因为等待整数运算结果而停顿。换句话说这个基准测试的主要矛盾不是指令取指不是分支预测而是数据依赖与访存延迟叠加后的复合瓶颈。分析的时候如果只看分支相关指标很容易得出“这个程序很温和”的错误结论。2.4 加速器看到的并行机会从硬件加速角度nw 的波前并行特质很适合映射成二维脉动阵列每个处理单元负责一个单元格数据沿右、下、右下三个方向流动。难点在于边界条件和索引映射。另一个方案是只加速填充阶段把回溯放到 CPU 上做。填充阶段占绝大部分运行时间这样做收益明显而且不用处理回溯的串行依赖。不过回溯阶段虽然只有 O(N) 步却需要访问整个矩阵里的方向信息如果矩阵存在外面访存成本也不小通常要在片上留一块缓冲保存回溯指针或者在填充的同时把方向信息压缩存储。3. 实测数据我跑出来的结果和一些对比3.1 实验配置与运行方式先说明一下环境免得数字没办法复现。我用的是一套常见的乱序单核模拟配置频率设为 2GHz四发射ROB 192 项L1 数据缓存 32KB 8 路L2 256KB 8 路内存延迟大约 200 个周期。执行方式是用户态模拟直接加载可执行文件不跑整个操作系统。输入序列准备了两组一组长度 128一组长度 1024。为什么故意用 32KB 的 L1因为 128 序列对应的 score 矩阵约 64KB虽然比 L2 小但 L1 放不下1024 序列对应的矩阵约 4MB连 L2 都放不下。这样能让缓存缺失特征暴露得更明显。每次模拟结束前我会把输出的最终得分跟参考输出比对确认运行结果无误后再记录统计。如果得分对不上那性能数据再漂亮也没有意义。3.2 核心性能数据下面是我在这套配置下跑出来的数据不同配置数值会有差异但趋势基本一致指标nw (N128)nw (N1024)IPC0.530.41L1D miss rate9.7%18.2%L2 miss rate3.1%12.4%分支误预测率0.2%0.2%每周期执行访存指令数0.180.14128 的时候 IPC 只有 0.53放在一个四发射机器上明显偏低。原因不是没指令可发而是大量指令排在 load-use 链后面只能在等待中耗尽周期。1024 时 IPC 进一步掉到 0.41L1 miss rate 翻倍到 18.2%L2 miss rate 12.4% 意味着有相当一部分数据请求要一路跑到主存。这里还要注意每周期执行访存指令数只有 0.14说明访存指令本身不多但每条访存指令的代价都被依赖链放大了。3.3 和其他几个MachSuite基准对比为了看 nw 在整套基准里的位置我用同一套配置跑了另外两个内核一个是规则网格迭代一个是随机访问排序类内核。对比结果如下基准核心特征IPCL1D miss ratenw动态规划链式依赖0.4118.2%网格迭代规则邻居更新0.788.9%随机排序随机访问分支密集0.6221.5%有意思的点是 nw 的 L1 miss rate 不是最高的随机排序那个内核更高但 nw 的 IPC 反而最低。原因是缓存缺失后的隐藏能力不同。随机排序访问的地址很散但每个元素处理完以后后面还有大量独立任务可以并行执行乱序窗口能把缺失延迟盖住一部分。nw 的每个 load 结果立刻被下一个迭代使用缺失延迟几乎全部暴露在关键路径上。所以不能只看 miss rate 判断程序性能依赖链长度同样关键。3.4 不同输入规模的影响我又把输入长度从 64 一路加到 2048观察到一个比较清楚的规律当 score 矩阵小于 L1 时IPC 可以到 0.7 左右矩阵一旦超过 L1IPC 掉到 0.4 到 0.5 之间再超过 L2额外损失逐渐变小因为主存带宽开始成为限制因素。另外当 N1024 时score 每一行正好 4KB和页面大小一致内层循环每访问一次上一行就会触发一次跨页访问TLB 压力明显上升L2 miss rate 也更高。这给做 benchmark 分析提了个醒想评估访存敏感型负载不能只跑一个输入规模至少要覆盖小于缓存和大于缓存两种情况。如果只拿小输入测nw 看起来是一个温和的依赖型程序换到大输入它立刻变成一个访存和 TLB 敏感的程序。结论完全不同。4. 针对nw的优化我在实验里试过的几种方案4.1 编译器和循环交换看清瓶颈再动手我先试的是把编译选项从 -O2 换成 -O3结果 IPC 只提升了不到 5%。这个结果不意外因为瓶颈在数据依赖和访存延迟不在编译器能处理的指令调度范围内。接着做循环交换把 i 和 j 的顺序对调结果更差。原因是原来的行主序下score[i][j-1] 是顺序访问连续 16 个单元格可以共享一个缓存行交换后变成按列处理score[i-1][j] 变成顺序访问但 score[i][j-1] 变成跨行读取总体缓存缺失反而增加。这里有个容易踩的坑循环交换到底有没有用取决于矩阵的存储布局。如果你把 score 转置成按列主序存放那么交换循环后内层顺序访问的就是列方向情况会反转。所以在做任何循环变换之前先搞清楚存储布局和后端硬件特性不要看到一个优化技巧就套上去。4.2 波前并行化把对角线切成可并行任务填充阶段的波前并行可以写成下面这种形式for (int s 2; s N N; s) { int start (s N) ? 1 : s - N; int end (s N) ? s - 1 : N; for (int i start; i end; i) { int j s - i; // D[i][j] 只依赖上一条对角线 D[i-1][j], D[i][j-1], D[i-1][j-1] } }这个版本把填充过程改成按对角线扫描同一条对角线内部的迭代互相独立。理论上可以用线程把循环拆开每个对角线结束后做一次同步。但我实际试下来在 8 核机器上N1024 时加速比只有 3.2 左右。瓶颈不在核心数量而在每个对角线同步和循环调度开销太大。细粒度波前的并行粒度太小CPU 上的线程同步成本比计算成本还高。更实用的做法是分块波前把矩阵切成小块块内串行计算块与块之间按对角线依赖关系形成粗粒度波前。这样同步次数大大减少也保留了缓存局部性。后面我会继续讲分块。4.3 分块兼顾并行和局部性的常用方法分块的基本思路是把矩阵分成 B×B 的小块块内按照依赖顺序填充块与块之间按波前关系调度。我试过 B 等于 8、16、32 三种在 32KB L1 下 B8 效果最好。原因是 8×8 的 int 块只占 256 字节能很好地留在缓存里同时块内计算还能复用缓存行。相比原版分块后的 L1D miss rate 降低了约 30%IPC 提升到 0.6 左右。分块也有代价边界处理很烦尤其是当 N 不能被 B 整除时。另外分块改变了计算顺序如果后续要做回溯方向信息的存储也得跟着调整不能只改填充部分。如果你要在 FPGA 上做加速这个思路和把矩阵切到片上缓冲的 design space exploration 是一致的值得在动手前先做一轮块大小扫描。4.4 HLS尝试绕开依赖的那些坑我在某个主流 HLS 工具里试过综合 nw 的核心循环。直接对内部循环添加流水线指令时工具给出的循环启动间隔是 3意思是每隔 3 个周期才能进入一个新的迭代。原因是当前迭代写入 score[i][j]下一个迭代要读 score[i][j-1]正好形成 RAW 冲突。想要达到间隔 1得把二维数组拆成多个寄存器变量或者改成移位寄存器结构才能在硬件上把写入和读取路径分开。另一个做法是把两层循环展平成一重对角循环确保流水线内不会同时访问同一个矩阵单元。这种写法对代码可维护性伤害很大但能显著降低间隔。我建议做 HLS 时不要一开始就追求间隔 1先把不同间隔下的面积和时序报告拉出来再决定目标。间隔 2 或者 3 的综合结果可能面积更小、频率更高整体收益反而更好。5. 实操中踩过的坑和排查技巧5.1 编译和运行时的低级坑最常见的问题是输入文件路径。MachSuite 的驱动会从当前目录读取输入文件如果在其他目录执行会直接报无法打开文件。我习惯把可执行文件和输入文件放到同一目录或者用绝对路径。另一个问题是参数个数有些版本会检查命令行参数不传参就默认走小输入容易让人误以为跑的是目标配置。还有一个让我折腾很久的问题数组下标越界。nw 的 score 矩阵需要多开一行一列用来放下标 0 的行和列。我移植的时候经常写成分配 N×N结果访问 score[i][j-1] 时在 i1, j1 处访问到 score[1][0]而 score[1][0] 其实是上一行的最后一个元素程序不一定会报错但得分完全不对。所以拿到任何动态规划代码先检查数组边界初始化。5.2 输出比对不一致的排查MachSuite 的参考输出一般是最终得分有些版本还会输出回溯路径。我遇到过得分正确但路径对不上的情况。原因在于回溯方向优先级不同如果某个格子同时有多个方向得到相同的最大值选择顺序会影响回溯路径。两个实现如果方向优先级不一样最终得分可能一样路径却差很多。调试时建议先只比较整数得分确认填充阶段正确后再单独检查回溯路径。如果你想修改回溯逻辑最好把方向矩阵单独存下来不要在得分矩阵里直接改符号。我之前为了省内存把方向信息压缩到几个 bit 里结果边界情况经常出错调试成本比省下来的内存高得多。5.3 模拟器上跑太久怎么办体系结构模拟比原生运行慢几个数量级nw 的 1024 输入在模拟器里可能要跑半小时甚至更久。我一般先用 128 输入做全流程确认结果无异常再换 1024 做完整统计。如果还想更快可以把模拟器的详细内存模型关掉只开周期级统计这样能省掉不少模拟开销。另外尽量用用户态模拟不要跑全系统模拟nw 不依赖操作系统功能全系统模拟的额外开销对结果没有帮助。模拟时间长了以后优先级也值得调整。先测小规模找瓶颈方向再跑大规模验证结论比一上来就怼最大输入高效得多。这个基准测试做研究时不太需要超大数据核心规律在小数据上已经能显示出来。5.4 几个常见认知误区第一nw 不是 Smith-Waterman。后者做局部比对初始化规则和回溯规则都不同拿后者的优化经验硬套到 nw 上会出问题。第二不要只盯着算法复杂度访存模式对运行时间的影响有时候比复杂度更直接。第三只优化填充阶段也不够回溯阶段虽然时间短但决定了最终结果而且很难并行必须在设计早期就想好怎么处理。我做加速器方案时第一版只加速填充结果回溯部分反而变成瓶颈后来花了很大力气才把回溯也搬进去。6. 我自己做基准分析的一点习惯做基准分析这件事我自己的体会是不要一开始就扑到优化上。拿到一个内核先放到模拟器里完整跑一遍拆一下 CPI 栈看瓶颈到底在访存、依赖、分支还是计算。然后再改一版最简单的高层优化去验证判断比如这里说的分块或者对角线程化。只有判断和结果对上了后面的大改动才有意义。nw 让我印象最深的地方是代码短到一眼能看完但它能把一个四发射乱序核心的流水线拖到接近空转。平时做体系结构研究容易低估这类动态规划内核因为它在源码层面实在太简单了。拿 nw 当试金石有一个好处它直接暴露访存和依赖这两件硬件设计里最难处理的事。后续我打算把同一套分析方法用到其他几个内核上到时候能横向对比出来不同负载对微架构的压力差异。如果你也在折腾 MachSuite或者正在评估某个加速器方案建议先从 nw 开始多跑几组输入再下结论。