动态规划不是不能并行——是你还没找到它的「并行基因」
去年我在做语音端点检测(VAD)模块时,遇到一个典型的'教科书级尴尬':串行版 HMM 前向 DP 在 ARM Cortex-A76 上跑一帧 MFCC 要 180ms,而实时系统要求端到端延迟 ≤30ms。
我第一反应是'换 GPU',结果把 kernel 搬上 Mali-G78 后,性能反而更差——因为没处理好 dp[t][s] 对上一时刻整行状态的依赖,大量线程在等同一个内存地址,L1 cache miss 率飙到 65%。
那一刻我才真正意识到:动态规划的并行化,从来不是把 for 循环套个 #pragma omp parallel 就完事;它是对问题数学结构的一次逆向工程——你要亲手把它拆开,看清哪些依赖是刚性的、哪些是柔性的、哪些其实可以'假装没看见'。
下面这整篇文章,就是我过去两年在生物信息、语音识别、嵌入式路径规划三个领域反复验证过的 DP 并行化心法。它不讲定义,只讲你怎么动手;不画大饼,只告诉你 在哪条路上容易翻车、哪个参数调错会让加速比变成 0.8x、为什么你的 CUDA kernel 永远只跑满 30% 的 SM。
先问自己一个问题:你的 DP,真的需要全量同步吗?
很多工程师一看到'DP 必须按序计算',就默认得用全局屏障(barrier)或原子操作来保序。但现实是:绝大多数经典 DP 问题的依赖图,远没有教科书里画得那么密不透风。
以编辑距离为例,状态转移方程:
dp[i][j] = min(
dp[i-1][j] + 1, // 依赖正上方
dp[i][j-1] + 1, // 依赖正左方
dp[i-1][j-1] + δ // 依赖左上方
);
表面看,每个格子都要等三个邻居——但如果你把坐标 (i,j) 换成对角线索引 k = i + j,就会发现:
- 所有
k=0的状态(只有dp[0][0])是边界,直接初始化; - 所有
k

