一种基于自适应蚁群优化算法的片上网络（Network-on-Chip）障碍物规避路由算法

《Microprocessors and Microsystems》：An adaptive ant colony optimization-based obstacle-avoidance routing algorithm for Network-on-Chip

蚁群优化-故障感知路由机制动态平衡网络可靠性、适应性和资源效率，通过路径柔性模型和缓冲区占用度量化指标优化路径选择，结合故障惩罚因子提升实时性，实验表明其吞吐量提升30%，平均延迟降低33%。

　　

曹佩萍|赵恒|苗祖佳|陈一涵|李慧云|唐志敏

深圳先进技术大学，中国广东省深圳市，518107

摘要

片上网络（NoC）的容错路由在实现可靠性、适应性和资源效率之间的最佳平衡方面面临重大挑战。传统方法（如基于维度顺序的XY路由）缺乏动态故障避免机制，因此在遇到故障节点或链接时经常导致拥塞和数据包丢失。尽管受生物启发的算法（包括蚁群优化（ACO）在自适应路由方面展现出潜力，但当前的实现方式未能充分将实时故障感知与拥塞控制相结合，同时保持可接受的硬件开销。为了解决这些限制，本文介绍了蚁群优化-故障感知（ACO-FA）路由机制，该机制结合了动态路径灵活性调整和基于缓冲区状态的拥塞缓解。所提出的方法采用定量路径灵活性模型，通过曼哈顿距离校正和故障位置感知动态修改最短路径。此外，路径缓冲区占用率（PBO）指标量化了多跳拥塞风险，而故障惩罚因子（$\beta$）优化了概率路径选择。实验评估表明，ACO-FA在多个性能维度上优于传统的XY路由。在包括单节点、双节点、多节点和链接故障的各种故障场景下，所提出的机制在接收/理想数据包传输比率上提高了多达3.0%，在饱和吞吐量上提高了多达30%，平均延迟减少了多达33%。

引言

近年来，多核异构处理器设计的快速发展促进了片上网络（NoC）架构的广泛应用。这些架构在可扩展性和高带宽方面具有显著优势，使其特别适用于高性能计算、人工智能和智能驾驶系统等多种应用。随着对高效数据处理和通信需求的不断增长，NoC已成为确保复杂系统在实时环境中无缝可靠运行的关键。例如，在高性能计算中，NoC促进了处理单元之间的快速数据交换，从而提高了计算效率并降低了延迟。在人工智能领域，NoC支持大规模数据集的并行处理，这对于训练复杂的机器学习模型至关重要。同样，在智能驾驶系统中，NoC使各种传感器和处理单元之间能够及时通信，确保关键决策能够迅速准确地做出。然而，这些系统的日益复杂性也带来了新的挑战，特别是在各种操作压力下维持系统级可靠性方面。热变化、电源波动和组件故障等因素可能对NoC架构的性能和可靠性产生不利影响。

当前的研究强调了NoC架构中需要强大的容错机制。最近的研究表明，制造缺陷、设备老化和瞬态干扰（如电磁干扰）显著增加了系统故障的风险。通信链接或路由节点的故障可能引发连锁效应，导致网络拥塞甚至灾难性的系统故障。因此，有越来越多的文献致力于开发自适应容错路由解决方案，以在确保可靠性的同时兼顾硬件开销的限制。这些解决方案通常采用动态重路由、冗余和错误检测等技术来减轻故障对系统性能的影响。然而，尽管取得了这些进展，许多现有方法在有效应对单点故障和多点故障（特别是在汽车系统等安全关键应用中）所提出的具体挑战方面仍然不足。在安全关键环境中，系统故障的后果可能是严重的，因此需要更全面地理解故障行为并实施更复杂的容错策略。研究人员越来越关注结合硬件和软件解决方案的混合方法，以提高韧性。这包括集成机器学习算法进行预测性维护和故障检测，以及开发能够自主从故障中恢复的自修复机制。

NoC架构中的容错问题因可能发生的故障类型多样而变得更加复杂。单点故障可能会破坏整个系统，而多点故障可能会引入系统性漏洞，对汽车级NoC的可靠性构成重大威胁。根据ISO 26262等安全标准，单点故障被视为系统性安全威胁，因为它们有可能破坏整个网络的功能。相比之下，在某些条件下，如果经过彻底分析和评估以确保不会导致灾难性故障，多点故障可能是可以接受的。这种区别突显了需要有效的保护措施来减轻这两种故障类型相关的风险。单点故障需要强大的检测和恢复机制来防止系统范围内的中断，而多点故障则需要一种更细致的方法来考虑网络内的相互依赖性。因此，解决这些故障模式对于确保智能驾驶系统的功能安全至关重要。在汽车级NoC系统中，同时确保对单点故障和多点故障的强大故障保护并优化网络性能仍然是一个重大挑战。为了应对这些挑战，本文进行了全面的研究，并提出了一种专为汽车级NoC定制的新型自适应路由机制。

我们引入了一种基于蚁群优化（ACO-FA）的故障感知路由框架，以克服传统自适应算法在处理网络故障方面的局限性。与现有方法不同，ACO-FA将实时故障数据和网络状态直接嵌入路由逻辑中。通过维护动态故障拓扑图，路由器主动绕过故障节点和拥塞。具体来说，我们制定了一个双指标评估方法，利用路径灵活性来量化替代路径的可用性，并使用缓冲区占用率来指示存储余量。这些指标共同优化路径选择，以平衡网络负载。最后，实时优化功能利用这些输入来确定最佳传输通道。该设计明确针对自动驾驶的严格延迟约束进行了定制，保证了关键数据流的可靠通信。

本文的结构如下：第2节讨论了NoC容错机制和受生物启发的路由的最新进展。第3节介绍了ACO-FA架构，详细介绍了其关键组成部分，如路径灵活性建模、拥塞评估和信息素更新逻辑，随后进行了复杂性和开销分析。第4节概述了仿真设置，并报告了从单点故障到多点故障的各种场景下的比较结果。最后，第5节总结了主要贡献和未来工作的潜在方向。

相关工作

相关工作

当前的研究通过多维方法提高了NoC的韧性。Krayem提出了一种基于数据重要性和永久故障图的内容感知路由策略。通过使用位混合错误缓解技术，容错数据可以传输通过故障路径。同时，当无故障路径不可用时，关键数据会被重新路由或复制，以确保完全连接。另外，Jain提出了一种轻量级方法

基于蚁群算法的容错路由设计方法

所提出的基于蚁群优化的容错路由算法的执行流程如图1所示。该算法通过一个集成的三阶段机制运行，结合了故障检测、路径发现和路径决策。故障检测阶段使用片上机制（如内置自测试（BIST）收集实时故障数据。这些信息被组织成故障拓扑图，并进行持续更新和传播

实验设置

实验验证使用了卡塔尼亚大学开发的Noxim仿真器进行。本研究对四种路由算法进行了全面的比较实验。XY路由作为确定性基准，实现了基于维度顺序的路由。ACO_BASIC代表没有故障感知的基本蚁群优化，以便进行消融研究以隔离容错机制的贡献。ACO-FA实现了所提出的故障感知自适应

贡献

为了提高片上网络系统的安全性和可靠性，本文提出了一种基于ACO-FA算法的自适应路由安全机制。首先，从理论上分析了ACO-FA的固有优势。随后，在路径缓冲区深度和路径灵活性两个维度上进行了系统探索，引入了故障惩罚因子作为自适应参数来优化传统的ACO-FA路径选择公式。

改进的ACO-FA路由

术语表

空单元

缩写	全称
ACO	蚁群优化
ACO-FA	蚁群优化-故障感知
BIST	内置自测试
CRC	循环冗余校验
DPF	双点故障
TPF	三点故障
DPSO	双粒子群优化
NoC	片上网络
PBO	路径缓冲区占用率
RBR	剩余缓冲区比率
RIFR	接收/理想数据包传输比率
RL	强化学习
SPF	单点故障
STR	饱和吞吐率

资助

本工作得到了深圳市基础研究项目 [资助编号 JCYJ20210324101210027, JCYJ20220818100814033]；广东省普通高校特色创新项目 [资助编号 2024KTSCX025]；以及广东省计算微电子重点实验室 [资助编号 2024B1212010007]的支持。

未引用参考文献

[27]

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的财务利益或个人关系。

苗祖佳于2024年在中国科学院深圳先进技术研究院获得硕士学位，2017年从中国科学技术大学合肥工业大学获得车辆工程学士学位。他目前在中国科学院深圳研究院攻读模式识别与智能系统博士学位。他的当前研究兴趣是自动驾驶汽车的安全性和异构芯片。