RoB-Router : A Reorder Buffer Enabled Low Latency Network-on-Chip Router
- 20 March 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 29 (9) , 2090-2104
Abstract
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.Keywords
Funding Information
- National Key Research and Development Program of China (2016YFB0200400)
- NSFC (61672526)
- FANEDD (201450)
This publication has 19 references indexed in Scilit:
- VIX2014
- NoRD: Node-Router Decoupling for Effective Power-gating of On-Chip Routers2012
- DSENT - A Tool Connecting Emerging Photonics with Electronics for Opto-Electronic Networks-on-Chip Modeling2012
- Packet chaining2011
- An analysis of on-chip interconnection networks for large-scale chip multiprocessorsACM Transactions on Architecture and Code Optimization, 2010
- Flattened butterflyACM SIGARCH Computer Architecture News, 2007
- A delay model and speculative architecture for pipelined routers2002
- A comparative study of arbitration algorithms for the Alpha 21364 pipelined routerACM SIGARCH Computer Architecture News, 2002
- Virtual-channel flow controlIEEE Transactions on Parallel and Distributed Systems, 1992
- Input Versus Output Queueing on a Space-Division Packet SwitchIEEE Transactions on Communications, 1987