基于改进蚁群算法的拥塞规避QoS路由算法

服务质量(QoS)路由算法缺少拥塞规避机制,会影响业务QoS。为此,提出一种基于Ant-Pub&Enco的信息素模型,根据蚂蚁行进方向,利用相反的信息素引导模式以及不同的信息素更新策略进行路由搜索。基于改进蚁群算法设计一种规避拥塞算法求解QoS单播路 由问题。仿真结果表明,该算法能够有效规避网络中的拥塞链路,均衡网络负载。     

一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法

类脑处理器能够支持多种脉冲神经网络SNN的部署来完成多种任务。片上网络NoC能够用较少的资源和功耗解决片上复杂的互连通信问题。现有的类脑处理器多采用片上网络来连接多个神经元核,以支持神经元之间的通信。SNN在时间步内瞬时突发的通信会在短时间内产生大量的脉冲报文。在这种通信行为下,片上网络会在短时间内达到饱和,造成网络拥塞。片上网络中非拥塞感知路由算法会进一步加剧网络拥塞状态,如何在每一个时间步内有效处理这些数据包,从而降低网络延迟,提高吞吐率,成为了目前需要解决的问题。首先对SNN的瞬时猝发通信特性进行了分析;然后提出一种拥塞感知的哈密尔顿路径路由算法,以降低NoC平均延迟和提高吞吐率;最后,使用Verilog HDL实现该路由算法,并通过模拟仿真进行性能评估。在网络规模为16×16的2D Mesh结构的片上网络中,相对于没有拥塞感知的路由算法,在数量猝发模式和概率猝发模式下,所提出的拥塞感知路由算法的NoC平均延迟分别降低了13.9%和15.9%;吞吐率分别提高了21.6%和16.8%。     

直线引导的Torus结构路由算法

为了提高片上网络在Torus拓扑结构下的路由通信效率,提出了一种基于直线引导思想的路由算法Tline。该路由算法将Torus拓扑结构的片上网络拓展为类似Mesh结构的坐标平面,以数据包的源节点和目的节点构成的直线为路由转发方向,并根据周围邻近节点的拥塞状况选择传输路径方向实现部分自适应路由。实验结果表明,与XY、OE路由算法相比,在热点流量模式下Tline路由算法具有较好的路由性能,且平均能耗降低约8%。     

基三分层网络中的受限多播路由算法

多播路由算法对互连网络的通信性能和多处理机系统性能的发挥起着重要作用。针对基三分层互连网络,在权衡性能、成本和实现的基础上,提出一种基于树的受限多播路由算法TRMA。该算法充分利用基三分层互连网络的层次特性和节点编码中所含的网络拓扑信息实现消息路由,算法设计简单,易于硬件实现。和其他基于树的多播路由算法相比,TRMA算法不需要源节点在发送消息前构建多播树,并将多播树的信息存放在消息中,大大降低了源节点的工作负载,提高整个系统的性能。通过仿真比较了TRMA和基于单播的多播路由算法,结果表明TRMA具有较低的网络延迟和较小的网络流量。     

一种基于气泡流控的改进多播路由算法

多播通信在片上多核系统中占据很重要的地位,并会对多核系统上并行应用程序的性能产生很大影响。现有的多播路由算法大多存在资源利用不均衡的不足,从而导致片上缓存资源的利用率较低。提出一种新的基于气泡流控的多播路由算法,该方法充分利用了片上网络的缓存资源,并通过向网络注入气泡避免了死锁现象的产生。实验表明,该方法可以有效提高片上网络中多播通信的性能,在合成负载下,该方法相对于均衡自适应多播路由算法可以实现18.1%的网络平均时延的降低以及16.7%的网络饱和吞吐量的增加。     

直线引导的片上网络路由算法

为了提高片上网络路由通信效率及降低能耗,提出一种新颖的路由算法——Beeline路由算法.该算法以数据包源点和终点构成的直线为传输引导方向,首先计算当前路由节点所在的网格其他3个节点到该直线的距离,获得离该直线距离最近的路由节点;然后计算最近路由节点与当前路由节点的路由跳数,根据跳数及邻近路由节点的拥塞状况选择最佳传输路由节点;最后将路由算法与基于结构级模型的No C能耗模拟软件相结合.与XY,OE路由算法进行比较的实验结果表明,Beeline路由算法具有较好的路由性能,并且平均能耗下降约6%.     

AdHoc网络中基于熵的QoS多播路由研究

AdHoc网络自身固有的特点使得AdHoc网络的QoS路由协议面临许多新的挑战和机遇,而且出现了许多新的网络系统．如视频点播、远程教学、远程医疗等,这些多媒体实时系统已经不满足网络的单播数据。因此,网络数据的多播提上了日程。本文对QoS多播路由进行了阐述,提出了一种基于熵的稳定的QoS多播路由,并且对它进行了分析以及与已经存在的多QoS约束多播路由进行了比较。     

基于Concentrated-Mesh和2D-Mesh结构的NoC路由算法

针对Concentrated-Mesh结构大规模片上网络提出了最短路径优先的路由算法和2D-mesh结构的小规模片上网络提出了一种基于初始路由向量循环移位的容错路由算法,该算法以确定数目的数据包为一组,成组的进行多路路由。实验结果表明,这种方法具有低时延,低功耗特点,并具有一定的容错能力,适合作为片上网络的通信机制。     

Ad Hoc网络中基于熵的QoS多播路由研究

Ad Hoc网络自身固有的特点使得Ad Hoc网络的QoS路由协议面临许多新的挑战和机遇,而且出现了许多新的网络系统,如视频点播、远程教学、远程医疗等,这些多媒体实时系统已经不满足网络的单播数据。因此,网络数据的多播提上了日程。本文对QoS多播路由进行了阐述,提出了一种基于熵的稳定的QoS多播路由,并且对它进行了分析以及与已经存在的多QoS约束多播路由进行了比较。     

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

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

Efficient multicast schemes for 3-D Networks-on-Chip

3-D Networks-on-Chip (NoCs) have been proposed as a potent solution to address both the interconnection and design complexity problems facing future System-on-Chip (SoC) designs. In this paper, two topology-aware multicast routing algorithms, Multicasting XYZ (MXYZ) and Alternative XYZ (AL + XYZ) algorithms in supporting of 3-D NoC are proposed. In essence, MXYZ is a simple dimension order multicast routing algorithm that targets 3-D NoC systems built upon regular topologies. To support multicast routing in irregular regions, AL + XYZ can be applied, where an alternative output channel is sought to forward/replicate the packets whenever the output channel determined by MXYZ is not available. To evaluate the performance of MXYZ and AL + XYZ, extensive experiments have been conducted by comparing MXYZ and AL + XYZ against a path-based multicast routing algorithm and an irregular region oriented multiple unicast routing algorithm, respectively. The experimental results confirm that the proposed MXYZ and AL + XYZ schemes, respectively, have lower latency and power consumption than the other two routing algorithms, meriting the two proposed algorithms to be more suitable for supporting multicasting in 3-D NoC systems. In addition, the hardware implementation cost of AL + XYZ is shown to be quite modest.     

Reconfigurable multicast routing for Networks on Chip

Several unicast and multicast routing protocols have been presented for MPSoCs. Multicast protocols in NoCs are used for cache coherency in distributed shared memory systems, replication, barrier synchronization, or clock synchronization. Unicast routing algorithms are not suitable for multicast, as they increase traffic, congestion and deadlock probability. Famous multicast schemes such as tree-based and path-based schemes have been proposed originally for multicomputers and recently adapted to NoCs. In this paper, we propose a switch tree-based multicast scheme, called STBA. This method supports tree construction with a minimum number of routers. Our evaluation results reveal that, for both synthetic and real traffic loads, the proposed scheme outperforms the baseline tree-based routing scheme in a conventional mesh by up to 41% and reduces power consumption by up to 29%.     

Adaptive Wormhole Routing in Hypercube Multicomputers

Both adaptive unicast routing and efficient multicast communication have been shown to be important to the performance of distributed-memory multiprocessors, or multicomputers. In this paper, we propose a uniform adaptive routing strategy for wormhole-routed hypercube networks that accommodates both unicast and multicast communication. Based on a node labeling method, the resultant routing algorithms are shown to be deadlock-free without requiring virtual channels. We present an optimal ordering algorithm that minimizes the traffic generated under the proposed paradigm. A greedy algorithm with less time complexity is also proposed.     

Dynamic retransmission control for reliable mobile multicast

Most existing multicast protocols adopt a static retransmission scheme(unicast or multicast) to retransmit lost packets.In the mobile multicast environment,static multicast retransmission mode may lead to congestion in the receivers‘ wireless interfaces,while static unicast mode may result in great network load.Both static unicast and multicast retransmission modes will cause a performance loss.This paper logically divides the mobile multicast network into fixed and mobile parts,and focuses on the mobile part.Then this paper analyzes the retransmission costs when multicast or unicast mode is chosen.Two main parameters are used to compare their efficiencies:the average air-interface utilization of each receiver and the average network load.Based on the results of analysis,two new algorithms,called NLPA(Network Load Priority Algorithm)and AUPA(Air-interface Utilization Priority Algorithm)are presented.Finally,simulation results conclude that,with proper parameters,both NLPA and AUPA can dynamically alternate between unicast and multicast retransmission modes acording to the conditions of network and receiver,and avoid congestion in receivers‘ wireless interfaces as well as great network load,with a better use of network and terminal resources.     

A hybrid multicast–unicast assignment approach for data distribution management in HLA

The main focus of data distribution management (DDM) in HLA is to reduce the amount of data received by federates in large-scale distributed simulations. The use of limited multicast resources plays a key role in the performance of DDM. In order to improve the performance of DDM by using communication protocol effectively, a hybrid multicast–unicast data transmission problem and its formal definition are presented, and then a hybrid multicast–unicast assignment approach is proposed. The approach uses a new adaptive communication protocol selection (ACPS) strategy to utilize the advantages of multicast and unicast, avoid their disadvantages, and consider the inter-relationship between connections. It includes the ACPS static assignment algorithm and the ACPS dynamic assignment algorithm, according to the difference between the static connections and the dynamic connections. In our approach, a concept of distance is presented to measure the inter-relationship between connections for multicast and the message redundancy for unicast, which is the core of the two algorithms in order to gather the connections to a multicast group or to balance the use of unicast and multicast for best performance. As a result, our algorithms can more effectively decide whether a new connection should use unicast or multicast communication, and whether adjusting previous assignment result can further improve the performance. In addition, a control mechanism is introduced to deal with connection changes during the dynamic assignment. The experiment results indicate that our algorithms can utilize the multicast and unicast communication resources effectively, as well as can achieve better performance than existing methods in the real running environment.     

Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given     

MMNNN: A tree-based Multicast Mechanism for NoC-based deep Neural Network accelerators

Network-on-Chip (NoC) devices have been widely used in multiprocessor systems. In recent years, NoC-based Deep Neural Network (DNN) accelerators have been proposed to connect neural computing devices using NoCs. Such designs dramatically reduce off-chip memory accesses of these platforms. However, the large number of one-to-many packet transfers significantly degrade performance with traditional unicast channels. We propose a multicast mechanism for a NoC-based DNN accelerator called Multicast Mechanism for NoC-based Neural Network accelerator (MMNNN). To do so, we propose a tree-based multicast routing algorithm with excellent scalability and the ability to minimize the number of packets in the network. We also propose a router architecture for single-flit packets. Our proposed router transfers flits to multiple destinations in a single process and has no head-of-line blocking issue, offering higher throughput and lower latency than traditional wormhole router architectures. Simulation results show that our proposed multicast mechanism offers excellent performance in classification latency, average packet latency, and energy consumption.     

一种IBA规则网络的路由算法及其网络模拟

InfiniBand协议越来越得到网络互连界的认可。它定义了一种自由的网络拓扑。目前多数场合使用的是不规则IBA网络,采用通用的up/down路由算法;但是将up/down算法直接用于IBA网络时,需要以损失网络性能为代价的路径修正才能避免网络死锁[1,2]。为了满足用户的特殊需求,保证网络的高带宽、低延迟,构造了基于4元N树的IBA规则网络拓扑,给出其单播和多播路由算法,并建立一个较为完整的IBA系统模型,用于模拟网络的可行性以及算法的正确性。