Resilient routing implementation in 2D mesh NoC

With the rapid shrinking of technology and growing integration capacity, the probability of failures in Networks-on-Chip (NoCs) increases and thus, fault tolerance is essential. Moreover, the unpredictable locations of these failures may influence the regularity of the underlying topology, and a regular 2D mesh is likely to become irregular. Thus, for these failure-prone networks, a viable routing framework should comprise a topology-agnostic routing algorithm along with a cost-effective, scalable routing mechanism able to handle failures, irrespective of any particular failure patterns. Existing routing techniques designed to route irregular topologies efficiently lack flexibility (logic-based), scalability (table-based) or relaxed switch design (uLBDR-based). Designing an efficient routing implementation technique to address irregular topologies remains a pressing research problem. To address this, we present a fault resilient routing mechanism for irregular 2D meshes resulting from failures. To handle irregularities, it avoids using routing tables and employs a few fixed configuration bits per switch resulting in a scalable approach. Experiments demonstrate that the proposed approach is guaranteed to tolerate all locations of single and double-link failures and most multiple failures. Also, unlike uLBDR it is not restricted to any particular switching technique and does not replicate any extra messages. Along with fault tolerance, the proposed mechanism can achieve better network performance in fault-free cases. The proposed technique achieves graceful performance degradation during failure. Compared to uLBDR, our method has 14% less area requirements and 16% less overall power consumption.     

Fault-Tolerant Mesh-Based NoC with Router-Level Redundancy

The aggressively scaled CMOS technology is increasingly threatening the dependability of network-on-chips (NoCs) architecture. In a mesh-based NoC, a faulty router or broken link may isolate a well functional processing element (PE). Also, a set of faulty routers may form isolated regions, which can degrade the design. In this paper, we propose a router-level redundancy (RLR) fault-tolerant scheme that differs from the traditional microarchitecture-level redundancy (MLR) approach to relieve the problem of isolated PE and isolated region. By simply adding one spare router within each router set in a mesh, RLR can be created and connection paths between adjacent routers can be diversified. To exploit this extra resource, two reconfiguration algorithms are demonstrated to detour observed faulty routers/links. The proposed RLR fault-tolerant scheme can tolerate at most one faulty router within a router set. After the reconfiguration, the original mesh topology is maintained. As a result, the proposed architecture does not need any support from the network layer routing algorithms. The scheme has been evaluated based on the three fault-tolerant metrics: reliability, mean time to failure (MTTF), and yield. The experimental results show that the performance RLR increases as the size of NoC grows; however, the relative connection cost decreases at the same time. This characteristic makes our architecture suitable for large-scale NoC designs.

     

Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs

An efficient routing algorithm is important for large on-chip networks [network-on-chip (NoC)] to provide the required communication performance to applications. Implementing NoC using table-based switches provide many advantages, including possibility of changing routing algorithms and fault tolerance, due to the option of table reconfigurations. However, table-based switches have been considered unsuitable for NoCs due to their perceived high area and power consumption. In this paper, we describe the region-based routing (RBR) mechanism which groups destinations into network regions allowing an efficient implementation with logic blocks. RBR can also be viewed as a mechanism to reduce the number of entries in routing tables. RBR is general and can be used in conjunction with any adaptive routing algorithm. In particular, we have evaluated the proposed scheme in conjunction with a general routing algorithm, namely segment-based routing (SR) and an Application Specific Routing Algorithm (APSRA) using regular and irregular mesh topologies. Our study shows that the number of entries in the table is significantly reduced, especially for large networks. Evaluation results show that RBR requires only four regions to support several routing algorithms in a 2-D mesh with no performance degradation. Considering link failures, our results indicate that RBR combined with SR is able to tolerate up to 7 link failures in an 8 $,times,$8 mesh. RBR also reduces area and power dissipation of an equivalent table-based implementation by factors of 8 and 10, respectively. Moreover, the degradation in performance of the network is insignificant when using APSRA combined with RBR.      

Mesh-connected rings topology for network-on-chip

With the feature size of semiconductor technology reducing and intellectual property （IP） cores increasing, on-chip interconnection network architectures have a great influence on the performance and area of system-on-chip （SoC） design. Focusing on trade-off performance, cost and implementation, a regular network-on-chip （NoC） architecture which is mesh-connected rings （MCR） interconnection network is proposed. The topology of MCR is simple, planar and scalable in architecture, which combines mesh with ring. A detailed theoretical analysis for MCR and mesh is given, and a simulation analysis based on the virtual channel router with wormhole switching is also presented. The results compared with the general mesh architecture show that MCR has better performance, especially in local traffics and low loads, and lower cost.     

基于网络监控器的专用片上网络动态容错路由

针对专用片上网络（Network on Chip,NoC）全局通信事务管理和可靠性设计问题,提出片上网络监控器的概念,用于获取全局网络实时状态信息及执行路径分配算法,基于此提出一种动态路由机制DyRS-NM.该机制能检测和定位NoC中的拥塞和故障链路,并能区分瞬时和永久性链路故障,采用重传方式避免瞬时故障,通过重新路由计算绕开拥塞和永久性故障.设计实现了RTL级网络监控器和与之通信的容错路由器模块,并将MPEG4解码器应用映射至基于网络监控器的4×4Mesh结构NoC体系结构中,验证了系统性能以及面积功耗开销.相比静态XY路由和容错动态路由FADR,DyRS-NM机制在可接受的开销代价下获得了更优的性能.     

Performance analysis of minimal path fault tolerant routing in NoC

Occurrence of faults in Network on Chip (NoC) is inevitable as the feature size is continuously decreasing and processing elements are increasing in numbers. Faults can be revocable if it is transient. Transient fault may occur inside router, or in the core or in communication wires. Examples of transient faults are overflow of buffers in router, clock skew, cross talk, etc.. Revocation of transient faults can be done by retransmission of faulty packets using oblivious or adaptive routing algorithms. Irrevocable faults causes non-functionality of segment and mainly occurs during fabrication process. NoC reliability increases with the efficient routing algorithms, which can handle the maximum faults without deadlock in network. As transient faults are temporary and can be easily revoked using retransmission of packet, permanent faults require efficient routing to route the packet by bypassing the nonfunctional segments. Thus, our focus is on the analysis of adaptive minimal path fault tolerant routing to handle the permanent faults. Comparative analysis between partial adaptive fault tolerance routing West-First, North-Last, Negative-First, Odd Even, and Minimal path Fault Tolerant routing (MinFT) algorithms with the nodes and links failure is performed using NoC Interconnect RoutinG and Application Modeling simulator (NIRGAM) for the 2D Mesh topology. Result suggests that MinFT ensures data transmission under worst conditions as compared to other adaptive routing algorithms.     

A low overhead load balancing router for network-on-chip

The design of a router in a network-on-chip (NoC) system has an important impact on some performance criteria. In this paper, we propose a low overhead load balancing router (LOLBR) for 2D mesh NoC to enhance routing performance criteria with low hardware overhead. The proposed LOLBR employs a balance toggle identifier to control the initial routing direction of X or Y for flit injection. The simplified demultiplexers and multiplexers are used to handle output ports allocation and contention, which provide a guarantee of deadlock avoidance. Simulation results show that the proposed LOLBR yields an improvement of routing performance over the reported routing schemes in average packet latency by 26.5%. The layout area and power consumption of the network compared with the reported routing schemes are 15.3% and 11.6% less respectively.     

Multicast-enabled network-on-chip routers leveraging partitioned allocation and switching

Multicast on-chip communication is encountered in various cache-coherence protocols targeting multi-core processors, and its pervasiveness is increasing due to the proliferation of machine learning accelerators. In-network handling of multicast traffic imposes additional switching-level restrictions to guarantee deadlock freedom, while it stresses the allocation efficiency of Network-on-Chip (NoC) routers. In this work, we propose a novel partitioned NoC router microarchitecture, called SmartFork, which employs a versatile and cost-efficient multicast packet replication scheme that allows the design of high-throughput and low-cost NoCs. The design is adapted to the average branch splitting observed in real-world multicast routing algorithms. Compared to state-of-the-art NoC multicast approaches, SmartFork is demonstrated to yield high performance in terms of latency and throughput, while still offering a cost-effective implementation.     

MatrixDCN: a high performance network architecture for large‐scale cloud data centers

With the widespread deployment of cloud services, data center networks are developing toward large‐scale, multi‐path networks. Conventional switching‐oriented data center network meets difficulties in terms of scalability and flexibility to support increasing bandwidth requirements for cloud services. To solve this problem, a simple and scalable architecture, MatrixDCN, is proposed in this paper. MatrixDCN is an approximate non‐blocking network, in which switches and servers are arranged in rows and columns that compose a matrix structure. A MatrixDCN network can accommodate up to hundreds of thousands of servers without bandwidth bottlenecks. Furthermore, the physical topology of a MatrixDCN network can be designed consistently with its logic topology, which helps to reduce the complexity of the management and maintenance of a data center. An efficient routing algorithm, named fault‐avoidance routing (FAR), is well designed for MatrixDCN to fully leverage the regularity in the topology. FAR builds two routing tables for a router. A BRT is built based on local topology, and a novel negative routing table (NRT) is increasingly built based on learned partial network failures, which really avoids the problem of network convergence and further shortens the calculating time of routing tables. FAR also greatly reduces the size of routing tables by introducing NRTs at routers. Theoretical analysis and simulations show that MatrixDCN has advantages on the scalability of topology, network throughput, and the performance of FAR. Copyright © 2015 John Wiley & Sons, Ltd.     

An interconnection architecture for network-on-chip systems

Network on Chip (NoC) is a discipline research path that primarily addresses the global communication in System on Chip (SoC). It is inspired and uses the same routing and switching techniques needed in multi-computer networks. Current shared-bus based on-chip communication architectures generally have limited scalability due to the nature of the buses especially when complex on-chip communication SoC is needed. The main goal is to have a dedicated communication infrastructure in the system that can scale up while minimizing the area and power. The selected topology of the components interconnects plays prime rule in the performance of NoC architecture as well as routing and switching techniques that can be used. In this paper, we introduce a new NoC architecture by adapting a recursive topology structure. An experimental study is performed to compare this structure with basic NoC topologies represented by 2D mesh and Spidergon. The analysis illustrates the main features of this topology and its unique benefits. The simulation results show that recursive network outperforms 2D mesh and Spidergon in main performance metrics.     

A load balancing bufferless deflection router for network-on-chip

The bufferless router emerges as an interesting option for cost-efficient in network-on-chip (NoC) design. However, the bufferless router only works well under low network load because deflection more easily occurs as the injection rate increases. In this paper, we propose a load balancing bufferless deflection router (LBBDR) for NoC that relieves the effect of deflection in bufferless NoC. The proposed LBBDR employs a balance toggle identifier in the source router to control the initial routing direction of X or Y for a flit in the network. Based on this mechanism, the flit is routed according to XY or YX routing in the network afterward. When two or more flits contend the same one desired output port a priority policy called nearer-first is used to address output ports allocation contention. Simulation results show that the proposed LBBDR yields an improvement of routing performance over the reported bufferless routing in the flit deflection rate, average packet latency and throughput by up to 13%, 10% and 6% respectively. The layout area and power consumption compared with the reported schemes are 12% and 7% less respectively.     

片上网络性能及功耗仿真实验研究

片上网络成为解决片上系统互联问题的研究热点。分析了基于SystemC的片上网络软件仿真平台。以NIRGAM模拟器为例,实现了JPEG编码器和XYYX路由算法,并对三种路由算法进行了功耗与时延的对比实验,体现了其方便的扩展能力及性能评估能力。实例表明软件模拟提供了灵活的实验方式,缩短了设计和验证的周期,利于培养创新能力。     

一种自适应动态缓存策略准入控制算法

针对片上网络的死锁问题,基于虚拟网络的自适应路由算法,设计了一个完全自适应片上路由器.重点介绍了路由算法及路由器的系统结构,设计实现了一个低代价、高效的完全自适应路由器,并在2DMesh拓扑结构下对其性能进行了模拟验证.实验结果表明,该路由器实现了无死锁的自适应路由,并提高了网络吞吐量,降低了平均网络延迟.     

S-Mesh: a Mesh-based on-chip network with separation of control and transmission

The current network-on-chip (NoC) topology cannot predict subsequent switch node status promptly. Switch nodes have to perform various functions such as routing decision, data forwarding, packet buffering, congestion control and properties of an NoC system. Therefore, these make switch architecture far more complex. This article puts forward a separating on-chip network architecture based on Mesh (S-Mesh). S-Mesh is an on-chip network that separates routing decision flow from the switches. It consists of two types of networks: datapath network (DN) and control network (CN). The CN establishes data paths for data transferring in DN. Meanwhile, the CN also transfers instructions between different resources. This property makes switch architecture simple, and eliminates conflicts in network interface units between the resource and switch. Compared with 2D-Mesh, Torus Mesh, Fat-tree and Butterfly, the average packet latency in S-Mesh is the shortest when the packet length is more than 53 B. Compared with 2D-Mesh, the areas savings of S-Mesh is about 3%--7%, and the power dissipation is decreased by approximate 2%.     

Application-aware virtual paths insertion for NOCs

Network-on-chip (NoC) has rapidly become a promising alternative for complex system-on-chip architectures including recent multicore architectures. Additionally, optimizing NoC architectures with respect to different design objectives that are suitable for a particular application domain is crucial for achieving high-performance and energy-efficient customized solutions. Despite the fact that many researches have provided various solutions for different aspects of NoCs design, a comprehensive NoCs system solution has not emerged yet. This paper presents a novel methodology to provide a solution for complex on-chip communication problems to reduce power, latency and area overhead. Our proposed NoC communication architecture is based on setting up virtual source–destination paths between selected pairs of NoCs cores so that the packets belonging to distance nodes in the network can bypass intermediate routers while traveling through these virtual paths. In this scheme, the paths are constructed for an application based on its task-graph at the design time. After that, the run time scheduling mechanism is applied to improve the buffer management, virtual channel and switch allocation schemes and hence, the constructed paths are optimized dynamically. Moreover, in our design the router complexity and its overheads are reduced. Additionally, the suggested router has been implemented on Xilinx Virtex-5 FPGA family. The evaluation results captured by SPLASH-2 benchmark suite reveal that in comparison with the conventional NoC router, the proposed router takes 25% and 53% reduction in latency and energy, respectively besides 3.5% area overhead. Indeed, our experimental results demonstrate a significant reduction in the average packet latency and total power consumption with negligible area overhead.     

Reliability- and performance-driven mapping for regular 3D NoCs using a novel latency model and Simulated Allocation

Network-on-Chip (NoC) -based communication architecture is promising in addressing the communication bottlenecks in current and future multicore processors. In this work, we consider the application-specific mapping problem and electromigration (EM) -induced through-silicon via (TSV) reliability issue in tile-based three-dimension (3D) NoC architectures. In 3D NoCs, network contention may result in unacceptable communication delay among the processing cores and thus has significant effect on the system performance. So we propose a new latency model for the routers which characterizes the network contentions among different traffic flows from sharing of network resources. Then we solve the core mapping problem by a fast while efficient stochastic algorithm called Simulated Allocation (SAL), which integrates our new latency model and also aims to optimize the communication power, latency in the mapping procedure. After that, we use an incremental method to optimize the reliability of the TSVs. Experimental results show that, contention-aware model (CAM) has 25% larger network latency than our latency model; compared with particle swarm optimization (PSO), our SAL algorithm can achieve 7% less power with about 7.5 × run-time speedup; as for reliability, our method can achieve better results (up to 10 × increase in terms of the void nucleation time (VNT)) with 7.64% increased latency.     

双链路故障时的共享路径保护

在波长路由光网络中,网络的存活性已经受到越来越多的重视.对单链路故障时的保护已经不能满足某些关键性业务对网络存活性的要求,因而研究了双链路故障时的共享路径保护技术.在动态业务下,将共享路径保护问题归结为整数线性规划.在节点无波长转换能力的情况下,分别提出了为当前业务计算最优路径和固定路径两种策略下的整数线性规划.数值结果表明,相对于专用保护,双链路故障时的共享路径保护能够节约30%左右的波长链路资源.     

A multiobjective scatter search algorithm for fault-tolerant NoC mapping optimisation

Mapping IP cores to an on-chip network is an important step in Network-on-Chip (NoC) design and affects the performance of NoC systems. A mapping optimisation algorithm and a fault-tolerant mechanism are proposed in this article. The fault-tolerant mechanism and the corresponding routing algorithm can recover NoC communication from switch failures, while preserving high performance. The mapping optimisation algorithm is based on scatter search (SS), which is an intelligent algorithm with a powerful combinatorial search ability. To meet the requests of the NoC mapping application, the standard SS is improved for multiple objective optimisation. This method helps to obtain high-performance mapping layouts. The proposed algorithm was implemented on the Embedded Systems Synthesis Benchmarks Suite (E3S). Experimental results show that this optimisation algorithm achieves low-power consumption, little communication time, balanced link load and high reliability, compared to particle swarm optimisation and genetic algorithm.     

Integrating machine learning in ad hoc routing: A wireless adaptive routing protocol

The nodes in a wireless ad hoc network act as routers in a self‐configuring network without infrastructure. An application running on the nodes in the ad hoc network may require that intermediate nodes act as routers, receiving and forwarding data packets to other nodes to overcome the limitations of noise, router congestion and limited transmission power. In existing routing protocols, the ‘self‐configuring’ aspects of network construction have generally been limited to the construction of routes that minimize the number of intermediate nodes on a route while ignoring the effects that the resulting traffic has on the overall communication capacity of the network. This paper presents a context‐aware routing metric that factors the effects of environmental noise and router congestion into a single time‐based metric, and further presents a new cross‐layer routing protocol, called Warp‐5 (Wireless Adaptive Routing Protocol, Version 5), that uses the new metric to make better routing decisions in heterogeneous network systems. Simulation results for Warp‐5 are presented and compared to the existing, well‐known AODV (Ad hoc On‐Demand Distance Vector) routing protocol and the reinforcement‐learning based routing protocol, Q‐routing. The results show Warp‐5 to be superior to shortest path routing protocols and Q‐routing for preventing router congestion and packet loss due to noise. Copyright © 2011 John Wiley & Sons, Ltd.     

Logical topology design for IP rerouting: ASONs versus static OTNs

IP-based backbone networks are gradually moving to a network model consisting of high-speed routers that are flexibly interconnected by a mesh of light paths set up by an optical transport network that consists of wavelength division multiplexing (WDM) links and optical cross-connects. In such a model, the generalized MPLS protocol suite could provide the IP centric control plane component that will be used to deliver rapid and dynamic circuit provisioning of end-to-end optical light paths between the routers. This is called an automatic switched optical (transport) network (ASON). An ASON enables reconfiguration of the logical IP topology by setting up and tearing down light paths. This allows to up- or downgrade link capacities during a router failure to the capacities needed by the new routing of the affected traffic. Such survivability against (single) IP router failures is cost-effective, as capacity to the IP layer can be provided flexibly when necessary. We present and investigate a logical topology optimization problem that minimizes the total amount or cost of the needed resources (interfaces, wavelengths, WDM line-systems, amplifiers, etc.) in both the IP and the optical layer. A novel optimization aspect in this problem is the possibility, as a result of the ASON, to reuse the physical resources (like interface cards and WDM line-systems) over the different network states (the failure-free and all the router failure scenarios). We devised a simple optimization strategy to investigate the cost of the ASON approach and compare it with other schemes that survive single router failures.