3. 序列比对计算瓶颈分析
做序列比对的都知道，BLAST 跑着跑着就卡住了。不是代码写得烂，是数据量实在太大、算法又太吃资源。我接触 GPU 加速之前，天天跟 CPU 上的 BLAST 瓶颈较劲，心里早就憋着火。今天咱们就把它拆开看。
3.1 数据规模爆炸
先聊聊数据量。十年前我们做一次全基因组比对，几百万条 query，跑一宿也就差不多了。现在呢？一台测序仪一天就能产出 20 TB 的数据。
我前两年接过一个项目，客户给的参考数据库已经膨胀到了 300 GB 以上。当时我用的 PC 端 BLAST，光加载索引就把 128 GB 内存吃满，swap 一开，性能直接崩盘。
为什么会这样？因为测序成本降得太快，数据增长曲线是超指数级的。我们来看几组数字：
| 年份 | GenBank 碱基数 | 增长倍数（相对2010） |
|---|---|---|
| 2010 | ≈ 1.2 × 10¹¹ | 1× |
| 2015 | ≈ 1.8 × 10¹² | 15× |
| 2020 | ≈ 2.5 × 10¹³ | 208× |
| 2024 | ≈ 4.0 × 10¹³ | 333× |
这还只是公开数据库。企业内部的宏基因组项目、肿瘤测序项目，数据量动不动就是 PB 级别。BLAST 这类基于动态规划或种子-扩展的算法，数据库越大，搜索空间越爆炸。
3.2 时间复杂度
再深一层，看算法本身。BLAST 的核心是局部比对，具体实现会先用 k-mer 索引快速定位候选区域，然后做 Smith-Waterman 或类似扩展。但你想想看，候选区域数量跟数据库大小、k-mer 频率直接挂钩。
我们来个简单估算：
- 假设 query 长度 N，数据库总长度 M
- BLAST 的启发式搜索复杂度大约 O(N × M × W)，其中 W 是每个种子扩展的平均代价
- 最坏情况下，如果数据库重复序列多，候选区域膨胀到 O(M)，复杂度直接回到 O(N × M²)
我在实际项目中测过一个 10 万条 query 对 100 GB 数据库的 BLAST 作业：单线程跑了 47 个小时。你算算，如果要完成 10 亿条 query，得等到明年去。
一个小技巧：如果你只是做同源搜索，可以先用 makeblastdb -dbtype nucl -in big.fasta 建立索引，再用 blastn -task megablast 跑，它使用更激进的 k-mer 跳过策略，复杂度低不少。但精度会打折。
还有一个常被忽略的点：内存带宽。BLAST 在扩展阶段需要频繁读取参考序列数据和 score matrix，每次命中 CPU 跳来跳去。单条指令延迟不高，但大量随机访存会把内存带宽打满。我做过 profiling，一个核心最多只能用到 30% 的浮点性能，其余时间都在等数据。
3.3 传统 CPU 比对的性能痛点
好了，说到痛点，我最有发言权。CPU 架构本质上是为通用计算设计的，不是为序列比对这种访存密集、指令并行度低的场景量身定做的。具体痛点我列几个：
- SIMD 利用率低
现代 x86 有 AVX-512，一次能处理 16 个 32-bit 整数。但 BLAST 的 Smith-Waterman 实现如果想用满 SIMD，需要做 16 路并行打分。内存布局稍有不连续，load 就变成 gather/scatter，效率暴跌。我试过手写 AVX-2 版本的 k-mer 扫描，速度只能提 2.5 倍，远达不到理论 8 倍。 - Cache 命中率差
数据库通常远超 L3 cache（几十 MB 到几百 GB）。BLAST 的随机访问模式导致每次扩展都可能跳到一个新位置。我调过一台机器的 perf，L2 miss 率高达 80%，L3 miss 60%。绝大部分时间 CPU 都在等内存。 - 多线程扩展难度大
BLAST 天然可以拆成 task 并行（每个 query 独立），但 thread 调度、锁竞争、NUMA 亲和性都是坑。我曾经把一个 64 核的机器跑 BLAST，加速比只有 12 倍左右，线程数翻一番性能反而下降，因为内存带宽成了瓶颈。 - 功耗与散热
跑大规模 BLAST 时 CPU 全核满载，功耗轻松突破 400W。实验室的空调根本压不住，机器降频后性能还不如一半核数开着 boost 跑。
这些痛点合在一起，就是：CPU 无法同时满足大数据量下的吞吐、时延和能效。
我曾经为了赶一个 deadline，用 4 台 128 核服务器组了个小型 BLAST 集群。调度器的网络开销、磁盘 I/O 争抢、再加上 NUMA 跨节点访问，最终实际吞吐不到理论 50%。那次之后我发誓：必须找更优的加速方案。
下面这张图把三个维度瓶颈的关联画出来了，方便你建立全局印象。
从上面可以看到，不管从哪条路径入手，最终都指向同一个结论：CPU 已经快撑不住了。数据规模只会更大，算法复杂度很难降下去（除非你用近似方法），传统 CPU 的硬件限制又是物理天花板。
那么换个角度想：我们能不能把 BLAST 里最耗时的部分，比如 k-mer 扩展、Smith-Waterman 打分，扔给 GPU？GPU 有上千核心、高内存带宽、天生的数据并行架构——这不正好跟 BLAST 的痛点互补吗？
嗯，这就引出了后面的内容。这一章我们先认清现状，后面再动手改造。