20 March 2018 in IEEE Transactions on Parallel and Distributed Systems
Traditional input-queued routers in network-on-chips (NoCs) only have a small number of virtual channels (VCs) and packets in a VC are organized in a fixed order. Such design is susceptible to head-of-line (HoL) blocking as only the packet at the head of a VC can be allocated by the switch allocator. Since switch allocation is the critical pipeline stage in on-chip routers, HoL blocking significantly degrades the performance of NoCs. In this paper, we propose to schedule packets in input buffers utilizing reorder buffer (RoB) techniques. We design VCs as RoBs to allow packets located not at the head of a VC to be allocated before the head packets. RoBs reduce the conflicts in switch allocation and mitigate the HoL blocking and thus improve the NoC performance. However, it is hard to reorder all the units in a VC due to circuit complexity and power overhead. We propose RoB-Router, which leverages elastic RoBs in VCs to only allow a part of a VC to act as RoB. RoB-Router automatically determines the length of RoB in a VC based on the number of buffered flits. This design minimizes the resource while achieving excellent efficiency. Furthermore, we propose two independent methods to improve the performance of RoB-Router. One is to optimize the packet order in input buffers by redesigning VC allocation strategy. The other combines RoB-Router with current most efficient switch allocator TS-Router. We perform evaluations and the results show that our design can achieve 46% and 15.7% performance improvement in packet latency under synthetic traffic and traces from PARSEC than TS-Router, and the cost of energy and area is moderate. Additionally, average packet latency reduction by our two improving methods under uniform traffic is 13% and 17% respectively.
12 December 2018 in International Journal of Parallel Programming
Endpoint congestion is one of the most challenging issues when designing low latency and high bandwidth on-chip interconnection networks. Tree saturation and head-of-line blocking caused by the endpoint congestion seriously decrease system throughput and increases network latency, leading to overall performance degradation. Adaptive routing algorithms utilize dynamic network states to route packets around congestion areas and potentially mitigate network congestions, but still cannot deal with endpoint congestions. Existing adaptive routing algorithms mainly take the current route information into account, and rarely use the route information of past packets. In this paper, we explore the route information of past packets, and led to the following novel observations that the virtual channel (VC) allocations of prior packets can be collected as useful information, and the tree saturation can be isolated through better VC selection strategy based on the past route information. Based on this observation, a novel history-aware adaptive routing algorithm for endpoint congestion, HARE, is proposed to improve network performance. We implement HARE based on the state-of-the-art routing algorithm, Footprint, and conduct extensive simulation experiments to compare it with our algorithm. The evaluation results show that our design alleviate the impact of tree saturation consistently and achieve high throughput on both synthetic and trace-driven workloads.
23 February 2023 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Distributed real-time systems (DRTS) composed of many embedded end-systems have been widely adopted in the industrial fields. Time-sensitive Networking (TSN), as a promising communication infrastructure for DRTS, has shown great potential in industry and academia. TSN assumes that an end-system can release critical tasks to process critical packets strictly according to the pre-scheduled time. Unfortunately, two factors currently damage this assumption: (1) the jitter caused by system architecture during task release, task execution and packet transmission; (2) a TSN schedule result may exceed the execution capability of the end-system and cause conflicts. This paper proposed DetChip, a system-on-chip capable of deterministically implementing the TSN schedule result. DetChip supports time-triggered task release, time-predictable task execution and precise network transmission. Based on DetChip, this paper first formalizes the execution capability of the end-system as end-system constraints (ECs). Existing TSN scheduling algorithms integrating ECs can solve conflicts by co-scheduling end-systems and the TSN network. Compared with previous works, DetChip only introduces few clock cycles jitter for critical task execution according to the TSN schedule result. The proposed ECs obtain 2 8x more conflict-free solutions for advanced scheduling algorithms with a linear increase in time overhead. Compared with the general end-system, DetChip can reduce 6 20x processing jitter to achieve better clock synchronization.
24 December 2019 in International Journal of Parallel Programming
28 April 2021 in IEEE Transactions on Computers
Hierarchical high-radix router microarchitecture consisting of small SRAM-based intermediate buffers has been used in large-scale supercomputers interconnection networks. While hierarchical organization enables efficient scaling to higher switch port count, it requires intermediate buffers which can cause performance bottleneck. Shallow intermediate buffers can cause head-of-line blocking to create backpressure towards input buffers and reduce overall performance. Increasing intermediate buffer size overcomes this problem but becomes infeasible due to the large overhead. In this work, we propose to organise decentralized intermediate buffers as a centralized buffer and leverage alternate memory technology to increase its capacity. In particular, we exploit the high-density nature of Spin-Torque Transfer Magnetic RAM (STT-MRAM) to increase intermediate buffer depth while also providing near-zero leakage power. STT-MRAM has disadvantages such as higher write latency and higher write energy. To overcome these disadvantages, we propose DeepHiR, a novel deep hybrid buffer organization (STT-MRAM and SRAM) combined with a centralized buffer organization to provide high performance with minimal cost. Although the deep intermediate buffer provided by DeepHiR can effectively improve router performance, a large amount of input buffer will still cause a lot of hardware overhead. At the same time, deeper intermediate buffers also makes it take longer for the backpressure to propagate to the source node, thereby reducing the performance of DeepHiR. Therefore, we further propose ElasHiR, which leverages elastic input buffer design in the centralized row buffer to allow a part of the centralized row buffer to act as input buffer. ElasHiR adopts reduced input buffers and automatically determines the length of input buffer in the centralized row buffer. This design minimizes the buffer resource while achieving excellent efficiency. Evaluation results show that DeepHiR can achieve 56.7 percent performance improvement in packet latency under synthetic traffic, and the cost of energy and area is moderate. ElasHiR can reduce the input buffer by 93.8 percent with performance comparable to DeepHiR.