作者：王泽坤，文章来源：网络交换FPGA
一句话看懂：当数据中心被纳秒级时序"逼疯"、智能网卡被定时器"拖垮"，西安电子科技大学团队用一项被审稿人反复打磨的硬件优先级队列设计方案，把"原位更新"和"分组排序"两件事第一次同时塞进了硬件——并且让 4K 深度的定时器队列在 28 nm 工艺下以 526 MHz工作频率运行，FPGA 上比同类方案少用 37% 的 LUT。
完整 RTL 实现代码与测试环境的 GitHub 链接：https://github.com/wzk-code/UG_PQ_rtl。
写在前面
如果你正从事 RDMA 网卡、TOE 加速器、SDN 交换机、可编程数据面相关研发工作，或是曾编写过 setTimer() 相关定时逻辑代码，这篇论文值得你认真研读。
这是一项关于"看似最不起眼、实则最致命"的硬件组件——定时器——的体系结构级突破，最近被计算机系统结构国际顶刊 IEEE Transactions on Computers 接收（DOI ：10.1109/TC.2026.3688849）。
来自西安电子科技大学微电子学院 + 空天地一体化综合业务网全国重点实验室的研究团队，由 王泽坤（第一作者，博士生）、岳炳昊、潘伟涛（通讯作者，副教授）、史江义 教授和 郝跃 院士共同完成，研究受 国家重点研发计划（2023YFB4405100、2023YFB4405102）资助。
他们要解决的，是一道困扰高速网卡多年的"老大难三连":
既要支持原位更新（不能"先删后插"），又要纳秒级精度且与队列规模解耦，还要在固定位宽下优雅处理时间戳溢出。
业界过去三十年，没有任何一种硬件方案能同时拿下这三件事——直到现在。
一、为什么说定时器是网卡里"最被低估的关键部件"？
在很多人印象里，定时器只是一行 sleep 或一个内核 tick。但在现代高速网络里，它是事件调度和超时控制的中枢神经——它的精度和更新效率，直接决定了整张网卡能否支撑新一代网络协议的高效运行。
论文给出了三个非常具体的"压力源"：
1. 数据中心传输协议正在向纳秒级演进
Fastpass、以太网 TDMA、Packet Pacing 这些新型协议，已经把"包发送时刻的精度要求"推到了纳秒量级。论文引述的多项工作已经在论证 datacenter 网络里 ns 级时间同步的必要性。
2. 定时事件需要"在线动态调整"
SDN 流表的 idle/hard timeout 要随包到达不停刷新；
TCP 重传定时器的 RTO 要根据 RTT 实时调；
RDMA RC 服务的每个 QP 都挂一个独立重传定时器；
Packet Pacing的发送时刻随拥塞反馈动态变化。
3. 软件方案正在"塌方"
论文直接引用了一项扎心的实测数据：
软件做流表超时动态调整时，CPU 占用率超过 80%（[12] 的实测结果）。
而软件定时器还存在天然抖动、缺乏高分辨率支持等问题——一句话：软件已经卷不动了，必须把定时器搬进硬件。
二、可现有硬件方案，每一种都"瘸一条腿"
为了让读者统一对现有方案的认知，作者在论文中整理了一张关键对比表（论文 Table I）：
| 定时器管理方案 | 是否支持 update | 时间精度 P | 是否处理溢出 | 代表工作 |
|---|---|---|---|---|
| 软件：时间轮 | ✓ | μs/ms 级，P ∝ 桶内规模 nᵢ | — | AccelTCP[20] |
| 硬件：单周期遍历 | ✓ | μs 级，P ∝ 总规模 N | ✗ | JingZhao[16] |
| 硬件：时间轮 / 日历队列 | ✗ | ns/μs 级，P ∝ nᵢ | ✓ | Tassel[21], PCQ[22] |
| 硬件：传统优先级队列 | ✗ | ns 级，P 与 N 无关 | ✗ | Timestamp[18] |
| 硬件：支持删除的 PQ | ✗（只能"删了再插"） | ns 级，P 与 N 无关 | ✗ | AntiQ[15], PIEO[23] |
| 硬件：本文方案 | ✓ | ns 级，P 与 N 无关 |
把这一行行读下来，你会发现一件惊人的事：这张表的最后一行，是过去几十年里第一次被"全部打勾"。
论文也很坦率地点名了几个常见 trick 的代价：
想用扩位宽硬扛溢出？1 GHz 的 32 bit 计数器 4 秒就溢出，扩到 64 bit 虽能撑 584 年，但资源开销近乎翻倍；
想用"先 dequeue 再 enqueue"间接更新？PIEO 每次更新要 8 个周期，AnTiQ 也要 5 个周期，频繁更新场景里精度直接崩盘；
想用一周期遍历？16K 定时器扫一遍要 72 μs（[16] JingZhao 的实测）。
每一种方案都在为另外两个指标"还债"。
三、核心创新：把"比较"和"移动"两件事拆到底
研究团队没有再去打造"更大的轮子"或"更深的堆"，而是回到数据结构最底层的两个原子动作——
比较（Comparison） 决定元素之间的相对秩，移动（Movement） 把秩信息映射到物理位置。
所有的 enqueue、dequeue、remove 都可以被分解成这两个原子的不同组合。基于这个抽象，他们做了两件事：
创新 1：业界首个"原生 Update 操作" —— 通过基本操作的组合与传播实现
作者将"概念上无界的队列"切成若干有限深度子队列 qᵢ，并在子队列之间建立了一套"操作传播规则"。任何一次 update，都被分解成在某个 qᵢ 上做"找 ID + 找新优先级插入位"的子任务，并沿着子队列向相邻 qᵢ₊₁ 传播未完成的部分。
最终，他们用一张极其精炼的"操作传播表"（论文 Table II），用 enqueue / remove / dequeue / push first 四种基本操作的组合，覆盖了 update 在子队列内部的全部 4 种情况。
这是论文原话——"To the best of our knowledge, this work presents the first hardware priority queue to support an update operation through the composition and propagation of basic operations to modify the priorities of elements within the queue."
翻译过来就是：这是据作者所知，第一个真正在硬件里做到"原位改优先级"的优先级队列。
创新 2：分组排序 —— 用 1 个 bit 让定时器"跨越溢出"
时间戳溢出，是所有"用计数器做时间"的硬件方案绕不开的死结。作者的处理方式异常巧妙：
把定时器的 最高有效位（MSB） 当作"分组标识位"，作为组边界优先级，在入队比较过程中动态切换比较对象。
效果有多好？论文给出了一组直接对比：
在同一组流表仿真（2047 条流，119,870 个数据包，总时长 809,383 ns）下，不分组方案需要 17 bit 的定时器宽度才能保证排序正确，而分组排序方案只需要 9 bit——而且这个宽度不会随仿真时长继续增长。
8 个 bit 的硬件资源差距，对应的就是寄存器、比较器、多级走线的全面减负。
实现：1D 收缩阵列 + 移位寄存器的混合架构
工程上，作者采用一维收缩阵列（Systolic Array） 与 移位寄存器 的混合结构实现，由两个可调参数 N（Systolic Unit数）和 M（每个单元内 Shift Block 数，要求 M ≥ 2）决定。
这种结构的妙处在于：
比较仅限于一个Systolic Unit内，避免长组合逻辑链的广播出现；
移动基于移位寄存器实现，采用布尔逻辑运算求解控制逻辑；
关键路径短，因此能够支持较高的吞吐率。
四、实测数据：把所有人想问的问题一次性回答完
研究团队在两条工艺路径上做了完整评估：Xilinx XCVU13P FPGA（Vivado 2024.2）+ 28 nm ASIC 综合，固定 4K 深度、16 bit 优先级（即 64K 优先级空间），扫描不同 (N, M) 组合。
28 nm 工艺：硬指标狂飙
| 指标 | 数值 | 配置 |
|---|---|---|
| 最高主频 | 526 MHz | M=2 |
| 关键路径延迟 | 1.82 ns | M=2 |
| 峰值吞吐率 | 175 Mpps | M=2 |
| 最小定时精度 | 6 ns | — |
| 最优 ADP 配置 | M=14（次优 M=6） |
作为参照：同样支持 4K 深度的 PIFO[37]，关键路径延迟为 16.93 ns。本文方案在面积近似时把延迟砍掉了 84%。
FPGA：吞吐率与频率双高
| 指标 | 数值 | 配置 |
|---|---|---|
| 最高主频 | 339 MHz | M=6 |
| 峰值吞吐率 | 113 Mpps | M=6 |
| 单次 update 周期数 | 3 cycles |
与 AnTiQ / PIEO / 传统 PQ 的横向对决
在 64–4096 七档深度的 LUT、FF、Fmax 全面对比里：
vs AnTiQ：LUT 平均省 37%、FF 平均省 25.2%；vs 传统 1D 收缩阵列：LUT 仅多 1.5×、FF 仅多 1.25×，却额外支持 remove 与 update；vs PIFO（同等 4K 深度）：吞吐率 2.8×；vs R-BMW（同等 4K 深度）：吞吐率为其 60%，但本文额外支持 update 操作；vs 传统移位寄存器：最高频率提升 1.26×–3.2×。
更关键的是定时精度与更新操作吞吐率：
在七档队列深度下，本文方案的最小定时精度始终在 5.6–8.6 ns 区间；相比 AnTiQ 提升 50%，相比 PIEO 提升 80%。
就更新操作的吞吐率来讲，在这七档队列深度下，平均是AnTiQ的1.91倍，是PIEO的4.9倍。
而单周期遍历方案在 4096 深度下的精度只有 1.73 μs——差了近 300 倍。
流表仿真：贴近真实工作负载
作者用 UNIV1 公开数据集的子集（2047 条流、119,870 个包）跑包级仿真，队列深度 2048、时钟周期 2 ns，理论吞吐 166.6 Mpps。结果显示：
超时设为 127 时刻周期，实际吞吐达 166.41 Mpps，逼近理论极限；
整个流表超时更新过程完全由数据包驱动，无需软件干预；
无论怎么调整定时器宽度（在 p、TO 不变前提下），仿真结果完全一致——这正是分组排序保证的"宽度无关性"在工程上的直接体现。
五、这意味着什么？为什么这件事很重要
把镜头从"性能数字"拉远，可以看出这项工作有三个层面的价值：
1. 系统层面：把 CPU 从"超时维护"中彻底解放出来
前文那个 "CPU 占用 > 80%" 的痛点，在这套硬件队列里被釜底抽薪——所有 update 都由包到达事件驱动、在硬件内部 3 个周期完成。这意味着可编程数据面、SmartNIC、DPU 可以把宝贵的 CPU 资源还给业务逻辑。
2. 协议层面：让纳秒级时序协议"真的能跑"
Fastpass、Packet Pacing、RDMA 高扩展 RC、TOE 这些"理论上很美"的协议，过去常常卡在"硬件做不到精确时序"。6 ns 精度、与规模无关，意味着这些协议有了第一批可以稳定承载的硬件底座。
3. 体系结构层面：为"动态优先级硬件"打开了一扇门
可以想象，所提架构也绝不仅限于定时器：处理器硬件调度器、动态包调度算法、硬件防饥饿机制……所有"需要在线改优先级"的硬件场景都可以受益。
六、未来怎么走？
研究团队在论文末尾给出了清晰的路线图：
第一步：引入 RAM 宏单元模块，进一步压缩资源开销而不牺牲性能；
第二步：将该设计集成进具备状态处理能力的 NIC，在真实高速网络环境下完成端到端验证；
对于关注智能网卡、DPU、可编程数据面、RDMA、网络处理器架构的同学，这是一份值得加入"必读清单"的工作。
七、论文信息
标题：A Grouped Sorting Queue Supporting Dynamic Updates for Timer Management in High-Speed Network Interface Cards
期刊：IEEE Transactions on Computers（CCF-A，计算机系统结构顶级期刊）
关键词：Priority Queue, Timer Queue, Systolic Arrays
资助：国家重点研发计划（2023YFB4405100、2023YFB4405102）
作者单位：西安电子科技大学微电子学院 / 空天地一体化综合业务网全国重点实验室
写在最后：这是一项"看上去很硬"、但真的能改变高速网络落地节奏的工作。当大家都在追逐更大的 LLM、更强的 NPU 时，仍有人在最底层的硬件细节里，将 “6 纳秒定时精度” 这一目标做到极致 —— 这正是体系结构研究最具魅力的地方。
如果觉得这篇文章有价值，欢迎转发给你身边做 网卡 / RDMA / DPU / 可编程数据面 / 网络处理器 的朋友。
—— 关注我们，下一篇我们继续拆解："分组排序"在硬件包调度器里的更多可能。