A Low Latency Router Supporting Adaptivity for On-ChipInterconnects∗Jongman Kim Dongkook Park T. Theocharides N. Vijaykrishnan Chita R. DasDepartment of Computer Science and EngineeringThe Pennsylvania State UniversityUniversity Park, PA 16802.{jmkim, dpark, theochar, vijay, das}@cse.psu.eduABSTRACTThe increased deployment of System-on-Chip designs has drawnattention to the limitations of on-chip interconnects. As a potentialsolution to these limitations, Networks-on -Chip (NoC) have beenproposed. The NoC routing algorithm significantly influences theperformance and energy consumption of the chip. We propose arouter architecture which utilizes adaptive routing while maintain-ing low latency. The two-stage pipelined architecture uses lookahead routing, speculative allocation, and optimal output path se-lection concurrently. The routing algorithm benefits from congestion-aware flow control, making better routin g decisions. We simulateand evaluate the proposed architecture in terms of network latencyand energy consumption. Our results indicate that the architectureis effective in balancing the performance and energy of NoC de-signs.Categories and Subject Descriptors:[B.4 I/O and Data Communications]:Interconnections(Subsystems),[B.8:Performance and Reliability]:Performance Analysis and De-sign Aids.General Terms:Design, Performance.Keyw ords:Adaptive Routing, Networks-On-Chip, Interconnection Networks.1. INTRODUCTIONWith the growing complexity of System-on-Chip (SoC) archi-tectures, the on-chip interconnects are becoming a critical bottle-neck in meeting performance and power consumption budgets ofthe chip design. The ICCAD 2004 Keynote Speaker [17] empha-sized the need for an interconnect centric design by illustrating thatin a 65nm chip design, up to 77% of the delay is due to intercon-nects. Packet-based on chip communication n etworks [10, 5, 4]∗This research was supported in part by NSF grants CCR-0093085,CCR-0098149, CCR-0208734, CCF-0429631, EIA-0202007, andMARCO/DARPA GSRC:PAS.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwi se, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.DAC 2005, June 13–17, 2005, Anaheim, California, USACopyright 2005 ACM 1-59593-058-2/05/0006 ...$5.00.(a.k.a network-on-chip (NoC) designs) have been proposed to ad-dress the challenges of increasing interconnect complexity.The desig n of NoC imposes sev eral interesting challenges ascompared to traditional off-chip networks. The resource limita-tions - area and power limitations - are major constraints influenc-ing NoC designs. Early NoC designs used dimension order rout-ing, due to its simplicity and deadlock avoidance. However, tra-ditional networks enjoy complicated routing algorithms and pro-tocols, which provide adaptivity to various traffic topologies, han-dling congestion as it ev o lves in the network. The challenge inusing adaptive routing in NoC designs, is to limit the overhead inimplementing such a design.In this work, we present a low-latency two-stage router archi-tecture suitable for NoC designs. The router architecture uses aspeculative strategy based on lookahead information obtained fromneighboring routers, in providing routing adaptation. A key aspectof the proposed design is its low latency feature that makes thelookahead information more representative than possible in manyexisting router architectures with higher latencies. Further, therouter employs a pre-selection mechanism for the output channelsthat helps to reduce the complexity of the crossbar switch design.We evaluated the proposed router architecture by using it in 2Dmesh and torus NoC topologies, and performing cycle-accuratesimulation of the entire NoC design using various workloads. Theexperimental results reveal that the proposed architecture results inlower latency th an when using a deeper pipeline router. This resultsfrom the more up to date congestion information used by the pro-posed low-latency router. We also demonstrate that the adaptivityprovides better performance in comparison to deterministic rout-ing for various workloads. We also evaluate our design from anenergy standpoint, as we designed and laid out the router compo-nents, and obtained both dynamic and leakage energy consumptio nof the router . Our results indicate that for non-uniform traffic, ouradaptiv e routing algorithm consumes less energy than dimensionorder routing, due to the decrease in the overall network latency.This paper is organized as follows. First, we give a short back-ground of existing w ork in Section 2. We present the proposedrouter architecture and the algorithm in Section 3, and we evalu-ate our architecture in Section 4. Finally we conclude our paper inSection 5.2. RELATED WORKThe quest for high performance and energy efficient NoC ar-chitectures has been the focus of many researchers. Fine-tuninga system into maximizing system performance and minimizing en-ergy consumption includes multiple trade-offs that have to be ex-plored. As with all digital systems, energy consumption and systemperformance tend to be contradictory forces in the design spaceof on-chip networks. Router architectures have dominated earlyNoC research, and the first NoC designs [5, 9] proposed the useof simplistic routers, with deterministic routing algorithms. Grad-ually researchers have explored multiple router implementations,and ongoing research such as [12, 2, 7, 3] explores implementationswhere pipelined router architectures utilize virtual channels and ar-bitration schemes to achieve Quality of Service (QoS) and high-bandwidth on-chip communication. Mullins, et. al. [14] propose asingle stage router with a doubly speculative pipeline to minimizedeterministic routing latency. Among the disadvantages however ofsuch approach, is an increased contention probability for the cross-bar switch, given the single-stage switching. The results given in[14] do not seem to take contention into consideration. Addition-ally, emphasis on the intra-router delay does not imply adaptivityto the network congestion. As such, a better approach should com-bine both low intra-routing latency, and adaptivity to the networktraffic.Under non-uniform traffic, or
View Full Document
Unlocking...