复旦大学计算机科学技术学院徐扬教授科研团队的研究论文《BMW Tree: Large-scale, High-throughput and Modular PIFO Implementation using Balanced Multi-Way Sorting Tree》被ACM SIGCOMM 2023接收，论文的第一作者为博士生姚如意，第二作者为博士生张志禹，指导教师为徐扬教授和刘森青年副研究员。该工作联合了复旦大学微电子学院和纽约大学共同完成。
ACM SIGCOMM是国际通信网络领域的顶尖会议，以高质量、高影响力著称，在该会议几十年的历史上，第一单位是国内大陆科研院所的论文总数很少，这也是复旦大学首次以第一完成单位在SIGCOMM会议上发表学术成果。SIGCOMM 2023将于2023年9月10-14日在美国纽约市召开。
在网络设备中，数据包调度器对网络应用的服务质量起着至关重要的作用。传统的网络设备调度策略固化，通常只支持少量常见的调度算法供用户通过配置参数选择使用。然而在当前以数据中心网络为代表的复杂网络环境中，网络模型和流量模型愈发复杂，网络应用的调度目标也变得多种多样。随着新应用的不断出现，未来还可能出现新的未知的调度目标。传统固化的数据包调度器已经难以适用于多种调度目标的网络环境，需要可编程调度器来灵活便捷地实现各种调度算法。
可编程调度器数据结构示例：2叉平衡多路排序树
近几年国际上陆续有研究团队提出不同的可编程调度器设计方案，然而现有的方案无法兼顾高吞吐量、高可扩展性和高调度准确度这三个目标。针对该问题，论文设计了一种新型数据结构：平衡多路排序树（BMW-Tree），该数据结构具有节点模块化，“插入平衡性”好（Insertion-Balanced），支持流水线操作，以及支持准确调度等优点。基于此数据结构，论文设计了两种简单高效的硬件实现方案。第一种是基于寄存器的R-BMW方案，通过流水线设计，R-BMW能够取得与树深度无关的稳定高吞吐量。第二种方案（RPU-BMW）基于论文中提出的RPU（Ranking Processing Unit）处理引擎；通过将树节点存储在SRAM中，按需动态加载到RPU中进行排序操作，可以极大地降低寄存器的使用，取得极高的可扩展性。
论文将两种方案在Xilinx Alveo U200 FPGA加速卡上进行了原型实现。评估结果表明，与原始PIFO实现相比（SIGCOMM 2016论文），R-BMW在取得相似容量的同时，吞吐量提高了4.8倍。论文在GlobalFoundries的28纳米工艺上综合实现了具有更好可扩展性的RPU-BMW方案。结果表明，一个具有8层4叉的RPU-BMW调度器仅需使用约0.5%的芯片面积和0.57MB的片外SRAM存储开销，就能实现每秒2亿次数据包调度和87,000个流的调度规模。
