基于重构的片上网络容错机制

为了保证片上网络的可靠性,本文提出了一种新的容错机制。在片上网络中由于路由器故障将导致与其连接的IP核不能与其他核通信,使片上网络的可靠性降低。本文的方法通过选择最优相邻的路由器来替代故障路由器,从而达到恢复IP核通信的目的。通过为每个路由器配置一个状态寄存器,用来存储相邻路由器的安全度,在路由时采用新的可重构路由算法绕过故障的路由器,以提高片上网络的可靠性。在OPNET平台上对5×52D-Mesh结构的片上网络进行仿真实验,统计了数据传输延时。试验结果表明,本文提出的路由算法与对比文献的路由算法相比,在延迟方面有明显的优势。     

BiLink: A high performance NoC router architecture using bi-directional link with double data rate

This paper presents a novel high performance Network-on-Chip (NoC) router architecture design using a bi-directional link with double data rate (BiLink). Ideally, it can provide as high as 2 times speed-up compared with the conventional NoC router. BiLink utilizes an extra link stage between routers and transmits two flits in one link per cycle using phase pipelining if both routers require to use the current link. To further increase the effective bandwidth, the direction of each link can be configured in every clock cycle to cater for different traffic loads from each side. Therefore, the data rate can be as high as 4 times compared with conventional NoC routers under uneven traffic. Centralized mode control scheme is implemented using a finite state machine (FSM) approach. Cycle-accurate simulations are carried out on both synthetic traffic patterns as well as real application benchmarks. Simulation results show that BiLink can provide as high as 90% and 250% speedup compared with conventional NoC routers for even and uneven traffic, respectively. 2X and 3X gains in throughput are obtained under even and uneven traffic, respectively, when compared with the conventional NoC router for the virtual channel flow control. The BiLink router architecture is synthesized using TSMC 65 nm process technology and it is shown that an area overhead of 28% over state-of-the-art bi-directional NoC is introduced while the critical path is about 9% higher than that of the conventional routers. Despite the overhead in critical path and power consumption, a 47.45% improvement of Energy-Delay-Product (EDP) is achieved by BiLink under high injection rate traffic.     

A fault-tolerant array processor designed for testability andself-reconfiguration

The design of a fault-tolerant rectangular array of processing elements (PEs) is presented in which the reconfiguration is done by means of on-chip distributed logic, without the help of any external host. Spare PEs are included in every column of the array, and faulty PEs are bypassed within a column to facilitate reconfiguration in the presence of faults. Scan paths are used to enhance the testability of the array. PEs are tested locally using near-neighbor comparisons without the need of an external host. Because the interconnections between logical neighbors are short, the speed penalty for reconfiguration is very small. Any amount of redundancy can be incorporated in the array without changing the topology of the scheme or the design of the reconfiguration switches. The scheme is well suited for very large-area, high-density chips and wafer-scale integration. In order to demonstrate the capabilities of the scheme and evaluate its performance, an experimental chip consisting of a 6×4 array was designed, fabricated, and tested. Details of the design and the implementation of the chip are presented. The scheme is also analyzed for yield and area utilization for a range of array sizes and PE survival probabilities     

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

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

Partial Virtual Channel Sharing: A Generic Methodology to Enhance Resource Management and Fault Tolerance in Networks-on-Chip

We present a novel Partial Virtual channel Sharing (PVS) NoC architecture which reduces the impact of faults on performance and also tolerates faults within the routing logic. Without PVS, failure of a component impairs the fault-free connected components, which leads to considerable performance degradation. Improving resource utilization is key in enhancing or sustaining performance with minimal overhead when faults or overload occurs. In the proposed architecture, autonomic virtual-channel buffer sharing is implemented with a novel algorithm that determines the sharing of buffers among a set of ports. The runtime allocation of the buffers depends on incoming load and fault occurrence. In addition, we propose an efficient technique for maintaining the accessibility of a processing element (PE) to the network even if its router is faulty. Our techniques can be used in any NoC topology and for both, 2D and 3D NoCs. The synthesis results for an integrated video conference application demonstrate 22 % reduction in average packet latency compared to state-of-the-art virtual channel (VC) based NoC architecture. Extensive quantitative simulation has been carried out with synthetic benchmarks. Simulation results reveal that the PVS architecture improves the performance significantly in presence of faults, compared to other VC-based NoC architectures.     

Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique

The network-on-chip (NoC) design problem requires the generation of a power and resource efficient interconnection architecture that can support the communication requirements for the SoC with the desired performance. This paper presents a genetic algorithm-based automated design technique that synthesizes an application specific NoC topology and routes the communication traces on the interconnection network. The technique operates on the system-level floorplan of the system on chip (SoC) and accounts for the power consumption in the physical links and the routers. The design technique solves a multi-objective problem of minimizing the power consumption and the router resources. It generates a Pareto curve of the solution set, such that each point in the curve represents a tradeoff between power consumption and associated number of NoC routers. The performance and quality of solutions produced by the technique are evaluated by experimentation with benchmark applications and comparisons with existing approaches.     

Topology and analysis of an N-stage cascaded polymer eight-port microring optical router with 7N channel wavelengths

Eight-port optical routers are widely used in cluster-mesh photonic networks-on-chip(No C). By using 24 groups of cross-coupling two-ring resonators, a 1-stage 8-port polymer optical router is proposed, which can optically route 7 channel wavelength data streams along definite path in two-dimensional(2D) plane. Under the selected 7 channel wavelengths, the insertion losses along all routing paths are within 0.02-0.58 d B, the maximum crosstalk of all routing operations is less than-39 d B, and the device footprint size is about 0.79 mm2. Then, a universal novel structure and routing scheme of N-stage cascaded 8-port optical router are presented, which contains 7N channel wavelengths. Because of the good scalability in wavelength, this device shows potential application of wideband signal routing in optical No C.     

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.     

一种故障通道隔离的低开销容错路由器设计

片上网络中路由器发生故障势必会影响整个网络的性能,过大的容错开销也会给网络带来很大的负担.对此,本文提出了一种故障通道隔离的低开销容错路由器架构,该路由器通过减少不必要的交叉开关及合理优化各个端口VC的数目来减小路由器整体开销,同时增加一个冗余通道来达到对路由器容错的目的.当路由器中某个通道发生故障时,通道隔离检测方法使路由器能够在检测故障类型的同时进行数据传输,带回收指针的重传buffer将会进一步减少整个容错结构的开销.实验结果表明在无故障情况下本文设计的路由器较传统路由器平均延时降低45%左右,最大吞吐率提高28%左右,面积开销仅仅增加了18.24%.在故障存在的情况下,本文方案也显现出很大的优越性,能够达到很好的容错效果.     

Mitigating the gateway bottleneck via transparent cooperative caching in wireless mesh networks

Wireless mesh networks (WMNs) have been proposed to provide cheap, easily deployable and robust Internet access. The dominant Internet-access traffic from clients causes a congestion bottleneck around the gateway, which can significantly limit the throughput of the WMN clients in accessing the Internet. In this paper, we present MeshCache, a transparent caching system for WMNs that exploits the locality in client Internet-access traffic to mitigate the bottleneck effect at the gateway, thereby improving client-perceived performance. MeshCache leverages the fact that a WMN typically spans a small geographic area and hence mesh routers are easily over-provisioned with CPU, memory, and disk storage, and extends the individual wireless mesh routers in a WMN with built-in content caching functionality. It then performs cooperative caching among the wireless mesh routers.We explore two architecture designs for MeshCache: (1) caching at every client access mesh router upon file download, and (2) caching at each mesh router along the route the Internet-access traffic travels, which requires breaking a single end-to-end transport connection into multiple single-hop transport connections along the route. We also leverage the abundant research results from cooperative web caching in the Internet in designing cache selection protocols for efficiently locating caches containing data objects for these two architectures. We further compare these two MeshCache designs with caching at the gateway router only.Through extensive simulations and evaluations using a prototype implementation on a testbed, we find that MeshCache can significantly improve the performance of client nodes in WMNs. In particular, our experiments with a Squid-based MeshCache implementation deployed on the MAP mesh network testbed with 15 routers show that compared to caching at the gateway only, the MeshCache architecture with hop-by-hop caching reduces the load at the gateway by 38%, improves the average client throughput by 170%, and increases the number of transfers that achieve a throughput greater than 1 Mbps by a factor of 3.     

TRACK: An algorithm for fault-tolerant,dynamic and scalable 2D mesh network-on-chip routing reconfiguration

Network-on-chip (NoC) is a reliable and scalable on-chip interconnect solution particularly used for MPSoCs and CMPs. Increasing susceptibility of NoC to failures is becoming a new research concern. Failures in components such as on-chip link or router may disrupt the underlying routing function. Reconfiguration of routing function is required to sustain network connectivity while maintaining deadlock-freedom in event of failure(s). Existing approaches either use routing tables or meta-data or involve all network nodes for participation in the reconfiguration process. This paper proposes TRACK, an algorithm for fast and scalable routing reconfiguration. It uses logic-based routing instead of tables and identifies affected nodes (i.e., rows/columns of mesh network) by single and double-link failures. In the proposed algorithm, reconfiguration is needed only for the affected nodes and the remaining network can continue to work. TRACK outperforms the existing one and reduces latency up to 42% and improves throughput up to 22% for single and double-link failures in 8 × 8 2D mesh network-on-chip. By employing logic-based routing, hardware cost is also reduced, i.e., 30% in area and 29.5% in power overhead for a 16 × 16 mesh router.     

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.     

Channel‐switching and power control mechanisms for improving network connectivity in wireless mesh networks

A Wireless Mesh Network (WMN) consists of fixed wireless routers, each of which provides service for mobile clients within its coverage area and inter‐connects mesh routers to form a connected mesh backbone. Wireless mesh routers are assigned with a channel or a code to prevent collisions in transmission. With a power control mechanism, each router could be assigned with a power level to control connectivity, interference, spectrum spatial reuse, and topology. Assigning high transmitting power level to a router can enhance the network connectivity but may increase the number of neighbors and worsen the collision problem. How to assign an appropriate power level to each router to improve the network connectivity with a constraint of limited channels is one of the most important issues in WMNs. Given a network topology and a set of channels that has been assigned to mesh routers, the proposed channel‐switching mechanism further reassigns each router with a power level and switches channels of routers to optimize both power efficiency and connectivity. A matrix‐based presentation and operations are proposed to respectively identify and resolve the channel switching problems. Simulation study reveals that the proposed mechanisms increase network throughput and provides a variety of route selection, and thus improves the performance of a given WMN. Copyright © 2009 John Wiley & Sons, Ltd.     

A network management architecture for robust packet routing in meshoptical access networks

We describe an architecture for an optical local area network (LAN) or metropolitan area network (MAN) access. The architecture allows for bandwidth sharing within a wavelength and is robust to both link and node failures. The architecture can be utilized with an arbitrary, link-redundant mesh network (node-redundancy is necessary only to handle all node failures), and assumes neither the use of a star topology nor the ability to embed such a topology within the physical mesh. Reservation of, bandwidth is performed in a centralized fashion at a (replicated) head end node, simplifying the implementation of complex sharing policies relative to implementation on a distributed set of routers. Unlike a router, however, the head end does not take any action on individual packets and, in particular, does not buffer packets. The architecture thus avoids the difficulties of processing packets in the optical domain while allowing for packetized shared access of wavelengths. We describe the route construction scheme and prove its ability to recover from single link and single node failures, outline a flexible medium access protocol and discuss the implications for implementing specific policies, and propose a simple implementation of the recovery protocol in terms of state machines for per-link devices     

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.     

Optimal redundancy allocation for high availability routers

How to optimally allocate redundant routers for high availability (HA) networks is a crucial task. In this paper, a 5‐tuple availability function A (N, M, λ, µ, δ) is proposed to determine the minimum required number of standby routers to meet the desired availability (ρ) of an HA router, where N and M are the numbers of active routers and standby routers, respectively, and λ, µ, and δ are a single router's failure rate, repair rate, and failure detection and recovery rate, respectively. We have derived the availability function, and analytical results show that the failure detection and recovery rate (δ) is a key parameter for reducing the minimum required number of standby routers of an HA router. Thus, we also propose a High Availability Management (HAM) middleware, which was designed based on an open architecture specification, called OpenAIS, to achieve the goal of reducing takeover delay (1/δ) by stateful backup. We have implemented an HA Open Shortest Path First (HA‐OSPF) router, which consists of two active routers and one standby router, to illustrate the proposed HA router. Experimental results show that the takeover delays of the proposed HA‐OSPF router were reduced by 6, 37.3, and 98.6% compared with those of the industry standard approaches, the Cisco‐ASR 1000 series router, the Juniper MX series router, and the Virtual Router Redundancy Protocol (VRRP) router, respectively. In addition, in contract to the industry routers, the proposed HA router, which was designed based on an open architecture specification, is more cost‐effective, and its redundancy model can be more flexibly adjusted. Copyright © 2010 John Wiley & Sons, Ltd.     

3DNoC关键通信部件容错方法研究综述

三维片上网络通过硅通孔（Through Silicon Via,TSV）将多层芯片进行堆叠,具有集成密度大,通信效率高等特点,是片上多核系统的主流通信架构。然而,工艺偏差及物理缺陷所引发的错误和TSV良率较低等因素,使得三维片上网络面临严重的故障问题。为保证通信效率,对三维片上网络关键通信部件进行容错设计必不可少。本文针对三维片上网络关键通信部件———路由器和TSV的故障和容错相关问题,从容错必要性、国内外研究现状、未来的研究方向和关键问题、以及拟提出的相关解决方案四个方面,展开深入探讨。为提高片上网络可靠性、保证系统高效通信提供一体化的解决方案。     

Design and implementation of Single-Buffered routers

A Single-Buffered （SB） router is a router where only one stage of shared buffering is sandwiched between two interconnects in comparison of a Combined Input and Output Queued （CIOQ） router where a central switch fabric is sandwiched between two stages of buffering. The notion of SB routers was firstly proposed by the High-Performance Networking Group （HPNG） of Stanford University, along with two promising designs of SB routers： one of which was Parallel Shared Memory （PSM） router and the other was Distributed Shared Memory （DSM） router. Admittedly, the work of HPNG deserved full credit, but all results presented by them appeared to relay on a Centralized Memory Management Algorithm （CMMA） which was essentially impractical because of the high processing and communication complexity. This paper attempts to make a scalable high-speed SB router completely practical by introducing a fully distributed architecture for managing the shared memory of SB routers. The resulting SB router is called as a Virtual Output and Input Queued （VOIQ） router. Furthermore, the scheme of VOIQ routers can not only eliminate the need for the CMMA scheduler, thus allowing a fully distributed implementation with low processing and commu- nication complexity, but also provide QoS guarantees and efficiently support variable-length packets in this paper. In particular, the results of performance testing and the hardware implementation of our VOIQ-based router （NDSC~ SR1880-TTM series） are illustrated at the end of this paper. The proposal of this paper is the first distributed scheme of how to design and implement SB routers publicized till now.     

Electrical steering of vehicles - fault-tolerant analysis and design

The topic of this paper is systems that need be designed such that no single fault can cause failure at the overall level. A methodology is presented for analysis and design of fault-tolerant architectures, where diagnosis and autonomous reconfiguration can replace high cost triple redundancy solutions and still meet strict requirements to functional safety. The paper applies graph-based analysis of functional system structure to find a novel fault-tolerant architecture for an electrical steering where a dedicated AC-motor design and cheap voltage measurements ensure ability to detect all relevant faults. The paper shows how active control reconfiguration can accommodate all critical faults and the fault-tolerant abilities are demonstrated on a warehouse truck hardware.     

On Topology Reconfiguration for Defect-Tolerant NoC-Based Homogeneous Manycore Systems

Homogeneous manycore systems are emerging for tera-scale computation and typically utilize Network-on-Chip (NoC) as the communication scheme between embedded cores. Effective defect tolerance techniques are essential to improve the yield of such complex integrated circuits. We propose to achieve fault tolerance by employing redundancy at the core-level instead of at the microarchitecture level. When faulty cores exist on-chip in this architecture, however, the physical topologies of various manufactured chips can be significantly different. How to reconfigure the system with the most effective NoC topology is a relevant research problem. In this paper, we first show that this problem is an instance of a well known NP-complete problem. We then present novel solutions for the above problem, which not only maximize the performance of the on-chip communication scheme, but also provide a unified topology to Operating System and application software running on the processor. Experimental results show the effectiveness of the proposed techniques.