NoC 死锁避免:从循环等待的形成到 turn model、虚通道与死锁证明思路
承 uncore-ring-mesh-interconnect——那一篇讲的是多核 uncore 为什么从总线进化到环和 mesh,以及报文在路由器之间怎么一站一站跳过去。但它有意跳过了一件事:报文在路由器缓冲区里排队等待时,会不会出现"你等我、我等他、他等你"的死结? 会的,而且一旦发生就是全网停摆——没有超时、没有重试、没有看门狗能救,只能整机复位。NoC 死锁避免就是片上网络设计里专门对付这个问题的一整套理论与工程手段:turn model 靠禁止特定转向让通道依赖图无环,虚通道靠把一条物理链路拆成多条逻辑资源来破环,自适应路由则必须在"绕路自由"与"可证明无死锁"之间走钢丝。报文在相邻路由器之间的具体移交规则见 noc-credit-flow-control,本篇聚焦"等待关系成环"这个更上层的全局问题。
本文要回答的问题
- NoC 里的死锁和操作系统的死锁是不是一回事?为什么教科书说"四个条件"在片上网络里几乎必然同时成立?
- 四个报文各转一个弯怎么就把 2x2 mesh 锁死了?循环等待到底长什么样?
- turn model 凭什么"禁掉两个转弯"就能证明无死锁?XY 路由是它的特例吗?
- 虚通道破环的原理是什么?为什么 dateline 方案能把环形拓扑救活?
- 自适应路由一边要绕开拥塞、一边要证明无死锁,设计者的证明思路是什么?
一、死锁在 NoC 里是什么:一场没有裁判的僵局
操作系统课上的死锁大家都背过:互斥、占有且等待、不可剥夺、循环等待,四条件齐了就出事。搬到片上网络,这四个条件几乎是为 NoC 量身定做的:
| 死锁条件 | 在 NoC 里的对应物 | 为什么必然成立 |
|---|---|---|
| 互斥 | 路由器输入缓冲区同一时刻只装一个报文(或一个 flit 串) | 缓冲区面积金贵,容量按 flit 计,天然独占 |
| 占有且等待 | 报文占着当前路由器的缓冲区,申请下一跳的缓冲区 | 报文不能"飞"过去,必须等下游 credit |
| 不可剥夺 | 已经进网的报文不能被中途丢弃或弹回 | 丢报文意味着一致性协议状态机错乱,不可接受 |
| 循环等待 | A 等 B 的缓冲区,B 等 C 的……最后一环等回 A | 路由路径在拓扑上可能绕圈 |
前三个条件是 NoC 的物理属性,改不动——你不能给缓冲区加抢占,也不能丢报文。所以NoC 死锁避免的全部火力都集中在第四个条件上:让"循环等待"在结构上不可能出现。这是和软件世界很不同的思路:软件里可以用银行家算法动态裁决,NoC 里路由器每拍都要做决策,没有跑全局算法的余地,只能靠静态可证明的资源分配规则。
还有一个 NoC 特有的残酷点:死锁不是性能问题而是功能问题。网络里只要存在一个环上互相等待的报文集,这些报文永远动不了;更要命的是它们的缓冲区被永久占住,拥塞会像血栓一样沿依赖边倒灌,最终把不相关的流量也堵死。一致性协议还在等响应,等不到响应的核就停在流水线里——整个芯片表现为"开机后某个负载下整机卡死",复现难、调试更难。这就是为什么流片前死锁必须是"证明出来的",而不是"测出来的"。
二、循环等待是怎么长出来的:一个 2x2 mesh 的最小事故
看一个教科书级最小案例。2x2 mesh,四个节点 NW、NE、SW、SE,每个路由器输入口只有一个报文的缓冲。假设路由算法是"最短路径自适应":只要是最短路径,两个方向随便挑。现在同时有四个报文:
- NW 的报文要去 SE,先往东走,占住 NE 的西向输入缓冲;
- NE 的报文要去 SW,先往南走,占住 SE 的北向输入缓冲;
- SE 的报文要去 NW,先往西走,占住 SW 的东向输入缓冲;
- SW 的报文要去 NE,先往北走,占住 NW 的南向输入缓冲。
然后每个报文都想转最后一个弯:NE 缓冲里的报文要南下去 SE 的缓冲——被占;SE 的要西去 SW——被占;SW 的要北去 NW——被占;NW 的要东去 NE——被占。四个报文各占一坑、各等下一坑,等出了一个闭环。

这张图里每个箭头都是一条"占有且等待"的依赖:报文占着所在路由器的缓冲,同时等待箭头指向的缓冲。四条依赖边恰好围成一个环——这就是通道依赖图(Channel Dependency Graph, CDG)里出现了环的物理图景。注意这个事故里没有任何硬件故障、没有任何协议 bug,纯粹是路由自由度太慷慨:允许"先东后南"也允许"先南后东",两类转弯凑在一起就拼出了环。既然环是路由自由度凑出来的,破环的第一思路自然是:把自由度砍到拼不出环为止。
三、turn model:禁掉两个转弯,环就拼不出来了
Glass 和 Ni 在 1992 年提出的 turn model(转向模型)思路直白得近乎粗暴:2D mesh 里一个报文可能转的弯一共八种(东→南、东→北、西→南、西→北、南→东、南→西、北→东、北→西),这八种转弯两两组合可能形成顺时针和逆时针两个抽象循环。每个循环只要禁掉一个转弯,环就闭合不了。八种里禁两种、留六种,就是既不死锁又保留相当路由自由度的甜点位。
三种经典限制方案:
| 方案 | 禁止的转弯 | 效果 |
|---|---|---|
| West-first | 西→北、西→南 | 要先往西就得最先走,之后不再允许西向转弯 |
| North-last | 东→北、西→北 | 北上只能作为旅程的最后一段 |
| Negative-first | 北→西、北→东 | 先走完负方向(北/西)才允许转正方向 |
而大家最熟的 **XY 维度序路由(Dimension-Order Routing, DOR)**是更狠的特例:八种转弯禁掉四种,只许"先 X 后 Y"。报文先在 X 维度走到目的列,再转 Y 维度一次到位——整个旅程最多转一次弯。X 维度的所有通道构成无环依赖(单向单调前进),Y 维度同理,X→Y 是"低维资源→高维资源"的单向跨越,通道依赖图按维度天然分层,环无从谈起。

这张图是 XY 无死锁证明的直观版:依赖关系从 X 层流向 Y 层,没有从 Y 层指回 X 层的边,层内又是单调的——整张依赖图是 DAG,无环即无死锁。代价也明显:路径唯一,中部的链路天然比边缘热(mesh 中心的 XY 路径密度最高),拥塞时不能绕。turn model 的价值正在于指出"XY 太保守":你只禁两种转弯就够了,何必禁四种——剩下的自由度就是自适应路由的生存空间。
四、虚通道:把一条物理链路拆成"可排序的逻辑资源"
砍路由自由度是一种破环法,还有第二条路:不动路由,动资源。虚通道(Virtual Channel, VC)把每条物理链路复用成多条逻辑通道,各有独立的缓冲区和 credit 账本。物理带宽时分复用,逻辑上却是几条互不干扰的通道。虚通道的流控细节见 noc-credit-flow-control,这里关心的是它的死锁杀伤力。
Dally 和 Seitz 的经典结论:只要能给所有虚通道编一个全序,并且保证报文总是从小编号通道流向大编号通道,通道依赖图就是无环的。编号本身就是破环刀。最漂亮的应用是救活环形拓扑:单向环上所有报文同向走,按理没有转弯,可它照样死锁——环上四个路由器缓冲全满,每个都在等下游,依赖边绕环一周闭合。解法叫 dateline(日期变更线):在环上任选一条链路作为"日界线",设两条虚通道 VC0、VC1;报文在环上前半段用 VC0,跨越 dateline 那一刻强制从 VC0 换到 VC1,且 VC1 永不许换回 VC0。

为什么这就行了?跨过 dateline 的报文从此只在 VC1 上等下游,没跨过的在 VC0 上等——而 VC0 上等待的终点(dateline 前的最后一个缓冲)里的报文必然即将跨入 VC1,VC1 的依赖链有终点(终点是已经到站的报文,会离开网络)。依赖关系被编号强行排成"VC0 → VC1 → 离开"的单向阶梯,环在 dateline 处被剪断。同一个思想放大到全网络,就是"给 VC 分层、报文只能升层"的通用破环框架。
五、自适应路由的死锁证明:绕路的自由怎么证明安全
真实设计不会满足于 XY 的一条死路径——热点要绕、故障链路要躲,自适应路由(adaptive routing)是刚需。但每放开一条绕路,就可能引入新的依赖环。Dally-Seitz 框架给出的证明套路至今是行业默认动作:
- 建通道依赖图:每个虚通道一个顶点;报文在通道 c1 等待时可能被放行到 c2,就画一条 c1 → c2 的边;
- 证明 CDG 无环:通常手段是给通道定义一个序号函数(维度、VC 编号、或两者组合),证明沿任何依赖边序号严格递增(或平维时不构成环);
- 区分逃逸通道与自由通道:Duato 协议的优雅做法——留一组满足 Dally-Seitz 条件的逃逸虚通道(比如跑 XY),自适应选择只允许在自由虚通道上进行,且规定:任何报文在自由通道里无论怎么绕,随时可以申请一条逃逸通道并按它走完。于是即便自由通道之间形成等待环,环上的每个报文都有一条"逃生门",环不构成真死锁。

这张图的关键在"随时可申请":证明死锁不存在,不是证明自由层里永远不成环(它真可能成环),而是证明环里每个成员都有一条通向无环层的出路。这就把证明负担从"全网络行为"收缩到"逃逸层无环 + 切换规则可达"两个小命题上。商用 mesh(Intel 片上 mesh、各类 AI 加速器 NoC)基本都是这个骨架:若干 VC 分成逃生层和性能层,协议层的请求/响应通道也常分属不同 VC 以避免协议级死锁——那是另一类"消息级死锁",本篇不展开。
工程落地时还有两条纪律值得一提。一是证明必须覆盖实现而不是论文:RTL 里的 VC 分配仲裁、跨时钟域的 credit 回传,任何一处让"逃逸通道申请永远被饿死"(livelock 变 deadlock)都会击穿理论保证,所以流片前用形式化工具对路由器微架构做死锁/活锁属性检查是签核项。二是死锁避免与活锁避免是两张支票:允许绕路的自适应路由还要限制绕路次数(如最多 k 次非最小跳转),否则报文可能永远绕圈不到站——不死锁但也永远不通,用户看来一样是卡死。
这一篇在知识体系里的位置
本篇是片上网络专题里"正确性"这一层,向上承接拓扑与流控、向下支撑一致性协议的可靠性:
- uncore-ring-mesh-interconnect:环与 mesh 拓扑本身的来龙去脉,本篇回答这些拓扑"怎么才能不死"。
- noc-credit-flow-control:相邻路由器之间的缓冲区移交机制,是"占有且等待"的微观载体。
- cache-mesi-moesif-protocols:跑在 NoC 之上的一致性协议,其请求/响应分类正是消息级死锁防御的应用层投影。
- cpu-microarch-overview:微架构全景导读,NoC 在多核版图中的位置见该篇。
- 芯片设计侧的互连视角见 on-chip-bus:从 AMBA 总线到 NoC 的演进脉络。
总结
NoC 死锁避免的全部工作是把"循环等待"从结构上消灭:互斥、占有且等待、不可剥夺是片上网络的物理属性改不动,所以只能砍第四个条件——turn model 通过禁止八种转弯中的一到四种让通道依赖图无环(XY 维度序路由是最保守的特例),虚通道通过给逻辑通道编全序号并用 dateline 之类的强制换层规则斩断环依赖(还能救活单向环),自适应路由则按 Duato 框架把 VC 分成"可绕路的自由层"和"可证明无环的逃逸层",把死锁证明收缩成"逃逸层无环 + 逃生门随时可达"两个小命题——流片前死锁必须是证明出来的,因为一旦在硅上发生,唯一的解药是整机复位。