2025-11-22T19:13:16.751799

A protocol to reduce worst-case latency in deflection-based on-chip networks

Indrusiak
We present a novel protocol that reduces worst-case packet latency in deflection-based on-chip interconnect networks. It enforces the deflection of the header of a packet but not its payload, resulting in a reduction in overall network traffic and, more importantly, worst-case packet latency due to decreased pre-injection latency.
academic

A protocol to reduce worst-case latency in deflection-based on-chip networks

基本信息

  • 论文ID: 2510.11361
  • 标题: A protocol to reduce worst-case latency in deflection-based on-chip networks
  • 作者: Leandro Soares Indrusiak (University of Leeds)
  • 分类: cs.NI (Networking and Internet Architecture), cs.PF (Performance)
  • 发表时间: 2025年10月13日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.11361

摘要

本文提出了一种新颖的协议，用于减少基于偏转路由的片上互连网络中的最坏情况数据包延迟。该协议强制偏转数据包的头部而非其负载，从而减少了总体网络流量，更重要的是，通过减少注入前延迟来降低最坏情况数据包延迟。

研究背景与动机

问题定义

  1. 核心问题：在基于偏转路由的片上网络(NoC)中，传统的全包偏转机制会导致严重的延迟问题，特别是在嵌入式实时系统中对性能保证的需求难以满足。
  2. 问题重要性：
    • 偏转路由网络虽然具有资源效率优势（减少85%芯片面积，降低10倍能耗），但会对网络延迟产生严重影响
    • 嵌入式多处理器平台需要性能保证，延迟的增加直接影响端到端性能
    • 现有分析模型显示偏转会显著增加最坏情况延迟
  3. 现有方法局限性：
    • 传统偏转路由在拥塞时会将整个数据包（包括头部和负载）沿替代路径发送
    • 这种做法增加了不必要的网络流量，特别是当数据包需要返回注入点重新尝试时
    • 现有优化方法主要关注改变路由或减少偏转次数，未考虑偏转过程中的流量优化
  4. 研究动机：
    • 观察到偏转数据包总是会经过其注入交换机才能再次到达目的地
    • 提出只偏转头部而丢弃负载的思路，在注入点重新注入负载
    • 目标是减少网络干扰，从而改善整体最坏情况延迟

核心贡献

  1. 提出新型偏转协议：创新性地将数据包头部和负载分离处理，只偏转头部而丢弃负载
  2. 建立理论分析模型：修改现有的最坏情况延迟分析框架，量化新协议的性能改进
  3. 提供性能保证：理论证明新协议在最坏情况延迟方面优于传统方法
  4. 广泛实验验证：通过应用特定和大规模合成评估，证明协议在不同场景下的有效性

方法详解

任务定义

输入：基于环形拓扑的无路由器片上网络，采用全包偏转路由机制 输出：改进的偏转协议，减少最坏情况数据包延迟 约束条件：保持原有网络功能，不增加额外缓冲开销，满足实时系统性能要求

协议架构

传统偏转机制

在传统协议中，当数据包在目的交换机无法弹出时（如弹出链路被占用），整个数据包会被偏转并沿环路传输直到再次到达目的地。

新协议设计

  1. 头部偏转：当发生偏转时，只有数据包头部继续在环路中传输
  2. 负载丢弃：数据包负载在偏转点被完全丢弃
  3. 负载重注入：当修改后的头部返回到注入交换机时，触发负载的重新注入
  4. 头部修改：目的交换机在偏转时修改头部字段，标识需要重新注入

关键技术细节

缓冲管理：

  • 数据包负载在注入后不能立即从注入缓冲区删除
  • 采用SAFC或SAMQ缓冲技术管理重注入需求
  • 在截止时间约束下（Di ≤ Ti），不需要额外缓冲内存

头部识别机制：

  • 注入交换机必须能识别偏转的头部
  • 头部包含目的交换机和数据包流的唯一标识符
  • 通过字段修改实现重注入触发机制

流量优化：

传统方式：完整数据包偏转 = 头部(H) + 负载(L-H)
新协议：仅头部偏转 = 头部(H)
流量减少 = (L-H) × 偏转次数 × 返回路径长度

技术创新点

  1. 分离式偏转策略：
    • 突破传统全包偏转思维
    • 利用环形网络拓扑特性（偏转包必经注入点）
    • 实现负载的就地重用
  2. 干扰减少机制：
    • 不直接减少单个数据包的偏转次数
    • 通过减少网络流量降低对其他数据包的干扰
    • 重点优化注入前延迟（Ipre）
  3. 向后兼容设计：
    • 可与现有偏转减少技术结合使用
    • 保持原有网络行为的一致性
    • 支持端到端确认机制扩展

实验设置

数据集

  1. 应用特定评估：
    • 使用39流自动驾驶车辆(AV)基准测试
    • 配置：VGA分辨率摄像头，8位色彩，25fps
    • 生成100个随机映射避免偏差
  2. 大规模合成评估：
    • 每个基准包含100个随机生成的流集
    • 流数量从20增加到280
    • 参数范围：周期1-100微秒，抖动0-50%周期，数据包大小16-48或32-96个flit

网络配置

  • 网络拓扑：4×4、5×5、6×6、7×7、8×8、9×9核心网络
  • 技术参数：32位flit，1-flit头部，1GHz时钟频率
  • 偏转设置：最多0-3次偏转，使用最老优先活锁预防机制

评价指标

  1. 最坏情况延迟减少百分比：新协议相对基线的延迟改进
  2. 可调度性比率：在基准测试集中完全可调度的案例百分比
  3. 池化平均改进：所有流和映射的平均改进

对比方法

  • 基线方法：Alazemi等人提出的传统无路由器网络协议
  • 分析方法：使用Indrusiak和Burns的最坏情况延迟分析模型

实验结果

主要结果

应用特定评估结果

网络规模4×45×56×67×78×89×9
最大改进(%)93.0789.4589.2689.3383.3680.66
池化平均(%)6.603.333.202.642.160.92

关键发现：

  • 所有网络拓扑都能从新协议中受益
  • 最大改进可达93%，主要出现在注入前干扰严重的流中
  • 随着网络规模增大，平均改进逐渐减小（流量分布更均匀）

大规模合成评估结果

新协议在可调度性比率方面显著优于基线：

  • 单次偏转场景：可调度性改进超过20%
  • 多次偏转场景：在中等负载下表现最佳
  • 网络规模影响：较小网络(4×4)改进更明显
  • 数据包大小影响：较大数据包(32-96 flit)推动网络趋向饱和

消融实验

通过不同偏转次数(0-3次)的对比分析：

  • 0次偏转：新协议与基线完全相同（验证正确性）
  • 1次偏转：新协议优势最明显
  • 多次偏转：改进程度随偏转次数增加而减小

理论分析验证

修改后的注入前空闲时间分析公式：

原始公式涉及所有流的完整数据包长度Lj
新协议公式将偏转流的负载长度替换为头部长度H
由于Lj > H，新协议理论上必然优于原始方法

实验发现

  1. 最佳改进条件：注入前干扰严重且网络未完全饱和的场景
  2. 规模效应：RLrec算法在大网络中生成更多小环，限制了改进空间
  3. 负载敏感性：改进效果与数据包大小和偏转频率正相关

相关工作

偏转路由研究方向

  1. Flit级偏转：每个flit独立做偏转决策，需要重排序机制
  2. 包级偏转：整个数据包统一偏转，保持flit顺序
  3. 混合方法：结合缓冲和偏转的策略

本文定位

  • 技术路线：选择包级偏转以获得资源效率优势
  • 创新角度：首次提出头部-负载分离偏转机制
  • 分析贡献：扩展现有最坏情况延迟分析框架

相关优化工作

  • 路由优化：如DARES等改变路由路径的方法
  • 硬件优化：缓冲区设计和仲裁策略改进
  • 拓扑优化：环配置和交换机设计优化

结论与讨论

主要结论

  1. 理论优势：新协议在最坏情况延迟方面理论上优于所有现有方法
  2. 实际效果：在多种场景下实现显著的延迟减少和可调度性改进
  3. 实现可行性：无需额外硬件开销，可使用现有缓冲技术实现
  4. 应用价值：特别适用于硬实时系统的性能保证需求

局限性

  1. 拓扑限制：主要适用于环形网络拓扑
  2. 改进衰减：在大型网络或高负载下改进效果有限
  3. 实现复杂性：需要修改注入缓冲管理和头部识别机制
  4. 评估范围：未量化平均情况延迟和能耗改进

未来方向

  1. 拓扑扩展：探索在其他网络拓扑中的应用可能性
  2. 性能量化：评估平均延迟和能耗改进效果
  3. 硬件实现：开发具体的硬件实现方案和原型验证
  4. 协议优化：与其他偏转减少技术的结合优化

深度评价

优点

  1. 创新性强：头部-负载分离的偏转思路具有原创性和启发性
  2. 理论严谨：提供完整的数学分析框架和理论证明
  3. 实验全面：涵盖应用特定和大规模合成两类评估方法
  4. 实用价值高：解决实时系统中的关键性能问题
  5. 写作清晰：技术描述准确，逻辑结构合理

不足

  1. 应用范围受限：主要针对环形网络，对其他拓扑的适用性不明确
  2. 实现细节不足：头部修改的具体编码方法和硬件实现细节缺乏
  3. 对比基线有限：主要与一种基线方法对比，缺乏与其他优化技术的比较
  4. 评估指标单一：重点关注最坏情况延迟，对平均性能和能耗影响分析不足

影响力

  1. 学术贡献：为偏转路由网络优化提供新的研究方向
  2. 实用价值：可直接应用于嵌入式实时系统的NoC设计
  3. 可复现性：提供详细的分析模型和实验设置，便于复现和扩展
  4. 启发意义：分离处理的思路可能启发其他网络优化研究

适用场景

  1. 硬实时系统：需要严格延迟保证的嵌入式应用
  2. 资源受限环境：对面积和功耗敏感的片上网络设计
  3. 环形网络架构：采用环形拓扑的NoC系统
  4. 中等规模网络：4×4到6×6规模的网络获得最佳改进效果

参考文献

本文引用了15篇相关研究，主要包括：

  • 1 Alazemi等人的无路由器网络架构
  • 6 Indrusiak和Burns的最坏情况延迟分析
  • 8 Liu等人的IMR环形网络设计
  • 其他偏转路由、实时分析和NoC优化相关工作

总体评价：这是一篇高质量的系统架构论文，提出了创新的偏转路由优化协议，具有扎实的理论基础和全面的实验验证。虽然在应用范围和实现细节方面存在一定局限性，但其核心思想具有重要的学术价值和实用意义，为片上网络优化研究提供了新的方向。