面灵AI→

寒武纪 AI 编译器二面:算子选择、内存复用与 tiling

轮次
二面
时间
2026-11
来源
牛客网

《面试题目》

  1. 你们这套 AI 编译器从 ONNX 到 NPU 指令,中间经过哪几步?你负责哪块?
  2. 算子选择怎么做?你的 cost model 用什么指标,准不准?
  3. 手撕:给你一张计算图,写一个拓扑排序,输出可执行的算子顺序,怎么写?
  4. 追问:图里有环怎么办?是直接报错还是尝试修?
  5. 算子融合为什么能省时间?Conv + BN + ReLU 融合到底省了什么?
  6. 手撕:实现一个 best fit 的内存池,怎么快速找到最合适的块?
  7. 追问:张量的内存复用怎么设计?两个 tensor 生命周期重叠还能复用吗?
  8. tiling 是为了解决什么问题?tile 大小怎么定?

《参考解析》

编译器的三段划分:前端负责解析 ONNX 成计算图、做 shape 推导与类型检查、转成内部 IR,不支持的算子走 CPU 回退或报错;图优化做常量折叠、死代码消除、算子融合、layout 转换消除;后端做算子选择(按 cost model 定 tiling 与指令)、内存分配、流水编排与代码生成,最后交给运行时下发。回答时要落到自己负责的那一段,并说清与其他段的接口——比如后端需要的「算子合法性约束」由前端 IR 提供,图优化不能破坏这些约束。

算子选择的 cost model:同一个算子往往有多套实现(direct、im2col + gemm、winograd 各有适用区间),按 shape 与 dtype 生成若干候选,再用代价模型打分。可用的指标包括片上存储占用、DMA 搬运字节数、MAC 利用率、寄存器压力、是否触发 bank conflict。手写公式初期误差可能到两成,用实测数据拟合并保留 autotune 兜底是常见做法:编译时间有预算时先查表,代价模型不确定就实测选优,并保留 top-2 候选在运行时切换。被问「准不准」时要给出量化口径——按 shape 分桶统计的误差、以及误差带来的端到端影响。

拓扑排序:统计每个节点的入度,入度为 0 的入队;出队时把后继入度减一,减到 0 再入队。复杂度 O(V+E)。工程细节比算法本身更值得说:邻接表用连续数组比哈希表快,队列用数组加头索引避免 deque 的块分配,同层节点按 id 排序保证两次编译产出一致的二进制。这个顺序既是下发顺序,也是后续内存复用分析的基础。

图里有环:拓扑排序输出的节点数小于总数就说明有环。定位环用 DFS 三色标记,遇到指向灰色节点的边时,回溯栈就是环的路径。处理策略上,合法 ONNX 图不应有环,遇到应当报错并打印环上的节点名与算子类型;但 Loop、If 这类控制流算子展开后可能成环,需要先做结构化。误判也要防:曾经出现过 Reshape 前后共用 buffer 被别名分析误判成环的情况,所以保留开关、线上只报错不自动修,是更稳的选择。

融合的收益:以 Conv + BN + ReLU 为例,不融合要把中间结果写三次、读三次,一个 56×56×64 的 FP16 特征图约 400 KB,三次往返就是 2.4 MB 的片外流量;融合后中间结果只在寄存器或片上 SRAM 里传递。第二笔收益是启动开销:每次 kernel launch 有数微秒的固定成本,ReLU 这种计算量极小的算子单独启动,开销比计算本身还大。融合的边界是 shape 与 layout 必须兼容,且不能跨 concat 这类多输入节点随意合并。

best fit 内存池:按大小分级(16、32、64 一直到 2048 字节),每级一条空闲链表,申请时向上取整到级,分配 O(1);更大的块交给伙伴系统。单链表版本的 best fit 要遍历所有空闲块找最小满足者,是 O(n);改成按大小排序的结构或分级链表可以降到 O(log n) 甚至 O(1)。best fit 的固有问题是产生大量小碎片,所以要配相邻空闲块合并与一定比例的 slack 容忍。

张量生命周期复用:按拓扑序算出每个张量的 [def, last_use] 区间,只有区间不重叠的张量才能共用同一块内存,这就是 liveness analysis。实现上维护按大小排序的空闲块集合,每次分配找最小满足的块,生命周期结束就归还并尝试与相邻块合并。收益通常很可观,中间激活能压掉一半以上;代价是调试变难,所以 debug 版本会关掉复用并给每个张量单独命名。

tiling 的动机与定法:片上 SRAM 容量有限(几 MB 量级),大特征图加权重根本放不下,必须切块搬入、算完搬出,让计算与搬运重叠。tile 大小的约束是一组不等式:一个 tile 的输入、权重、输出与双缓冲必须同时装进片上存储;切分要整除或至少让余数块的浪费可接受;还要满足 DMA 的对齐与最小传输粒度。在这些约束下按代价模型选使「搬运字节数 / MAC 数」最小的组合,再用 autotune 在真实硬件上校正。tile 太小会让 DMA 启动开销占比过高,太大则放不下或无法双缓冲,最优点通常在中间。