片上网络路由算法的研究

路由算法作为片上网络研究的一项关键技术,负责将分组正确无误地发送到目的节点.片上网络路由算法可分为无关路由算法和自适应路由算法两种.无关路由算法简单易实现,但具有一定的盲目性,自适应路由算法能够灵活地选择路由路径,却需要复杂的控制逻辑和硬件电路.对目前已经出现的几种路由算法进行了分析、对比,并从所适用拓扑、是否防止死锁等方面对算法进行了评价,并提出了片上网络路由算法的研究方向.     

基于前缀的片上网络容错源路由算法

为克服片上网络链路永久性错误带来的路由问题,提出一种基于前缀的片上网络容错源路由算法PFTSR。该算法适用于二维mesh片上网络,采用预测路径并根据反馈信息调整路径的方法进行路由探测。在仿真平台NIRGAM上进行仿真,实验结果表明,与传统片上网络容错源路由算法SRN相比,PFTSR极大降低了片上系统的功耗,并且在大多数情况下能减少探测到第一条路径的时间。     

一种无缓存片上网络交叉开关调度机制

提出一种无缓存片上网络的交叉开关调度机制.无缓存是指将路由节点输入端口缓存以及相应的控制逻辑移除,以降低实现开销.该调度机制在每个输入端口设置一条自回环通道,并在“偏转”路由基础上采用一种基于“偏转”和自回环次数的优先级策略,以通过减小“偏转”次数提高无缓存片上网络的网络性能.实验表明,此调度机制相对于基本的无缓存机制,可保证在硬件开销与能耗不增的前提下,提高网络性能;相对于典型的有缓存机制,在负载较低时其网络性能更优,负载较高时性能略低,但可使硬件开销与能耗分别下降58.9％与40.2％,并使频率提高74.6％.     

片上网络容错路由算法研究

随着集成电路制造工艺的不断发展,集成在芯片上晶体管的数量也随之增多,已超过几十亿晶体管的规模,因此芯片上可以集成越来越多的IP核。随着芯片中IP核数量的增多,基于总线结构的片上系统(System-on-Chip,So C)已不能满足数据的通信要求,为了解决这个问题,片上网络(Network-on-Chip,No C)作为一种全新的互联结构被提出来。其核心是把网络设计的思想移植到芯片设计中,将片上资源互连起来,并将计算与通信分离。片上网络具有很好的空间可扩展性,采用的全局异步一局部同步的通信机制使并行通信效率更高。NOC带来了一种全新的片上通信方式,它的引入有利于提升可重用设计、解决通信瓶颈和全局同步等难题。本文在研究片上网络结构的基础上,针对片上网络多播通信的特点提出了一种多播容错路由算法。     

保证QoS的片上网络路由算法研究

路由算法在片上网络的服务质量保证机制中具有非常重要的地位,本文分析DyAD算法在路由过程中可能会选择一条非最短路径从而导致跳数增加,增大延迟导致服务质量性能下降。对此本文在DyAD基础上提出了一种改进型算法,该算法以确保尽可能地选择最短路径进行路由保证服务性能。仿真结果表明该改进算法可以有效减小延迟,改善性能,提供较好的服务质量保证。     

一种异构传感器网络的能量有效路由算法

无线传感器网络设计能量有效的路由算法是至关重要的.对于不同类型的传感器节点传输不同大小数据包信息以及拥有不同初始能量的异构传感器网络,本文提出了一种适合此传感器网络的D-REECR路由算法,此算法是在之前提出的REECR算法上改进而来.基于REECR没有考虑簇头在选择时的分布不均匀性,D-REECR将簇头闻的距离作为选择簇头的因素之一,与节点的剩余能量及能量消耗率一起作为选择簇头的依据.这样使各个簇大小基本一致,从而平衡各个节点的能量消耗,达到延长网络生命的目的.仿真结果显示,改进后的D-REECR算法比REECR算法在能量效率上大约提高5%～10%.     

片上网络路由算法分析与评估

本文对片上网络中的确定性XY路由算法和基于拐弯模型的4种自适应路由算法进行分析,并采用Noxim模拟器在6种合成通信模式下对5种路由算法的性能进行评估。实验结果表明,在均匀随机通信模式下,XY路由算法的性能优于自适应路由算法;在置换1和混洗通信模式下,奇偶路由算法的性能优于其他路由算法;在置换2、位反和蝶形通信模式下,负向优先路由算法的性能优于其他路由算法。     

片上网络容错路由算法分析和评价

片上网络技术是借鉴并行分布式计算机及传统计算机网络的概念解决片上多核系统的通信问题。片上网络代替片上总线通信,解决了片上总线结构所引起的可扩展性、效率、面积、功耗等问题。然而,片上网络在数据传输过程中可能由于各种原因产生故障,因此片上网络可靠性研究是当前一个研究热点。首先总结了片上网络故障分类,比较和分析了当前片上网络容错算法并给出其优势和缺陷,最后对全文进行总结,并给出了片上网络容错算法的展望。     

片上网络容错路由算法分析和评价

片上网络技术是借鉴并行分布式计算机及传统计算机网络的概念解决片上多核系统的通信问题。片上网络代替片上总线通信,解决了片上总线结构所引起的可扩展性、效率、面积、功耗等问题。然而,片上网络在数据传输过程中可能由于各种原因产生故障,因此片上网络可靠性研究是当前一个研究热点。首先总结了片上网络故障分类,比较和分析了当前片上网络容错算法并给出其优势和缺陷,最后对全文进行总结,并给出了片上网络容错算法的展望。     

基于拥塞控制的片上网络多播路由算法

为了满足片上网络日益丰富的应用要求,多播路由机制被应用到片上网络,以弥补传统单播通信方式的不足。以Mesh和Torus类的片上网络为例,分析了基于路径的3种多播路由算法(即XY路由、UpDown路由和SubPartition路由算法),并研究了相应的拥塞控制策略。通过模拟实验表明,多播较单播通信具有更小的平均传输延时和更高的网络吞吐量,且负载分配均匀;特别是SubPartition路由算法随着规模增大效果更加明显;提出的多播拥塞控制机制,能更有效地利用多播通信,提高片上网络的性能。     

二维网格片上网络中的新型自适应路由算法

本文针对二维网格的片上网络设计了一种称为维度气泡流控(DBFC)的新型流控策略。利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列相关的特点,设计实现了维度气泡流控。该流控策略建立在虚跨步(VCT)切换和信约流控机制之上,通过分析端口信约值和路由信息实现点点间的流控。在二维网格的片上网络中采用DBFC流控策略,即使网络中存在环相关,本文设计的自适应维度气泡路由(ADBR)算法仍可实现无死锁、最短距离的路由。对于以上结论,本文提供了详细证明。最后,通过修改通用的片上网络模拟工具-NOXIM的代码,实现了DBFC流控策略和ADBR算法。在NOXIM上分析了ADBR算法的性能,结果显示ADBR算法拥有较好的性能。     

NoC关键问题

片上网络(NOC)作为复杂SoC通信的一种解决方案,受到了工业界和学术界的广泛重视.NoC设计涉及了从物理层到应用层诸多方面的问题,本文对NoC研究中的关键问题做简单的介绍.     

基于全分布式分组无线网络的蚂蚁路由算法

该文介绍了全分布式分组无线网络中路由算法。当前广泛运用的OSPF路由算法在网络的链路发生阻塞时，不能及时探测到链路状况。当链路发生拥塞时，在发包率继续增大的时候，只能简单地丢弃数据包。就此该文在分布式的无线网络中应用了蚂蚁算法。该算法由发送探测包来担任“觅食蚂蚁”在短时间内找出最优路径，分散流量，避免网络的拥塞。通过仿真结果表明：该算法在网络利用率和数据包传送时延上有较好的改善。     

无线传感器网络异构驱动路由算法

融合表驱动路由和按需驱动路由的优点提出一种异构驱动的无线传感器网络路由算法,以实现无线传感器网络监测数据的高效汇集。算法将无线传感器网络的原有单一汇聚节点(Sink节点)扩充为一组无环连通点集,称为虚拟槽节点以覆盖全网。感知节点采用按需驱动路由策略将监测数据在短距离内传递给虚拟槽节点,随后数据在虚拟槽节点内部依照表驱动路由实现高速汇集。通过理论计算确定最优虚拟槽节点选取方式,并提出两跳邻居算法实现路由。经仿真实验,算法可保证网络内任意节点两跳可达虚拟槽节点,并通过分析仿真数据论证算法的有效性。     

一种改进的BFT型片上网络拓扑结构

针对片上网络(NoC)资源节点之间通信的局部性,提出改进的蝴蝶型胖树(BFT)拓扑结构XBFT及相应的路由算法.该结构在BFT结构的基础上改变边的连接关系,减少了路由节点数和物理连接链路数,理论分析表明,在64个IP核的NoC中,XBFT较BFT路由器数目减少了14.3％,物理链路数减少了10.7％,XBFT结构比BF...     

一种新的航空自组网混合路由算法

路由算法是航空自组网研究的重点和难点。针对目前对航空自组网高动态路由研究较少的现状,考虑到飞机节点高动态但局部结构相对稳定的特点,通过将ADS-B系统整合到路由表建立过程中,设计了一种基于分簇和地理位置信息的混合路由算法CGCR。应用ADS-B消息中的节点位速和飞行意向数据预测节点运动趋势,从而选择最优下一跳节点。通过扩大下一跳选择区域策略来避免路由空洞的产生。仿真结果表明,CGCR具有良好的性能。     

基于遗传算法的QoS多播路由优化算法

研究了带宽、延时、延时抖动和分组丢失率约束以及费用最小的QoS多播路由优化问题,提出了一种启发式遗传算法、该算法采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题。交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性。该算法采用简单维护操作维护好所有的不可行的染色体,交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性。计算机仿真实验证明该算法快速有效,可靠性高。     

Storus:一个二维片上网络拓扑结构

随着CMOS工艺集成度持续不断提高,单片多处理器正在成为高性能处理器结构的发展趋势,现有的片上总线结构已不足以满足片上系统设计的互连需求,近年来提出了片上网络这一新的互连结构,片上网络需要解决的问题有:选择合适的拓扑结构、路由算法、流控机制等等.文中为片上网络结构提供了一个新的拓扑结构Storus以及路由算法L2,并使用多种负载模式、多种流控机制对Storus与Torus结构进行模拟分析.模拟结果显示,Storus的平均路由延时约比Torus小2%～15%,使用热点负载模拟时,Storus的饱和吞吐量约为Torus结构的1.2～1.5倍.     

基于虚拟通道非均匀分布的路由算法

随着片上系统(systems on chip,SoC)集成度的提高,IP核之间的通信成为SoC急需解决的问题。近年来提出的片上网络(network on chip,NoC)是解决SoC通信问题的一种有效方法。虚拟通道和路由算法是NoC设计中的关键技术,对NoC的延时、吞吐量等性能有重要的影响。根据NoC负载分布特点,提出一种新的虚拟通道非均匀分布技术VCND。该技术在Mesh内部使用虚拟通道,在边界上使用非虚拟通道,从而减少缓冲单元的数量。同时提出一种改进的无死锁路由算法CXY(combination XY)。仿真结果表明,与XY路由算法和XY-YX路由算法相比,CXY路由算法提高了网络吞吐量,并降低了网络平均延时;相比虚拟通道均匀分布技术,VCND技术能够以较小的吞吐量和网络延时损失获得可观的缓冲单元利用率提升,并减少了路由器的面积。