research-article

Minimally buffered deflection routing with in-order delivery in a torus

Authors:

Christian Mellwig,

Alexander Stegmeier,

Theo UngererAuthors Info & Claims

NOCS '17: Proceedings of the Eleventh IEEE/ACM International Symposium on Networks-on-Chip

Article No.: 1, Pages 1 - 8

https://doi.org/10.1145/3130218.3130227

Published: 19 October 2017 Publication History

Abstract

Bufferless deflection routing is a serious alternative to wormhole flow control and packet switching. It is based on the principle of deflecting a flit to a non-optimal route instead of buffering it, when two flits compete for the same link. The major weakness of deflection is the exploding number of misrouted flits at high network load, which increases the duration of flits within the network and requires to reassemble the flits at the receiver. These deflections can be reduced significantly by adding a small side buffer instead of always deflecting flits.

In the presented approach, the side buffer is complemented by a restricted deflection policy that preserves the flit order: x-y-routing in an unidirectional 2D-torus ensures that collisions are impossible, as long as a flit is transported in the same direction. Only at the transition from x- to y-direction, collisions may happen and are avoided by controlled in-order deflection in x-direction. In-order delivery not only simplifies the arbitration logic, but avoids costly mechanisms for livelock-prevention and reassembly of flits at the receiver.

References

[1]

R. Ausavarungnirun et al. Design and evaluation of hierarchical rings with deflection routing. In Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 230--237, 2014.

Digital Library

[2]

S. Borkar. Future of interconnect fabric: A contrarian view. In Workshop on System Level Interconnect Prediction, SLIP '10, pages 1--2, 2010.

Digital Library

[3]

W. J. Dally and B. Towles. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers, San Francisco, 2004.

Digital Library

[4]

C. Fallin, C. Craik, and O. Mutlu. CHIPPER: A low-complexity bufferless deflection router. In High Performance Computer Architecture (HPCA), pages 144--155, 2011.

Digital Library

[5]

C. Fallin et al. MinBD: Minimally-buffered deflection routing for energy-efficient interconnect. In Int. Symp. on Networks on Chip (NOCS), pages 1--10, 2012.

Digital Library

[6]

C. Gomez, M. E. Gomez, P. Lopez, and J. Duato. Reducing Packet Dropping in a Bufferless NoC. In Euro-Par Conference on Parallel Processing, 2008.

Digital Library

[7]

M. Hayenga, N. E. Jerger, and M. Lipasti. SCARAB: A Single Cycle Adaptive Routing and Bufferless Network. In Int. Symp. on Microarchitecture, MICRO 42, pages 244--254, 2009.

Digital Library

[8]

J. Hestness and S. W. Keckler. Netrace: Dependency-tracking traces for efficient network-on-chip experimentation. The University of Texas at Austin, Dept. of Computer Science, Tech. Rep, 2011.

[9]

J. Jose, B. Nayak, K. Kumar, and M. Mutyam. DeBAR: Deflection Based Adaptive Router with Minimal Buffering. In Conference on Design, Automation and Test in Europe (DATE), pages 1583--1588, 2013.

Digital Library

[10]

J. Kim. Low-cost router microarchitecture for on-chip networks. In Int. Symp. on Microarchitecture (MICRO 42), 2009.

Digital Library

[11]

J. Kim and H. Kim. Router microarchitecture and scalability of ring topology in on-chip networks. In Workshop on Network on Chip Architectures (NoCArc), 2009.

Digital Library

[12]

G. Michelogiannakis, D. Sanchez, W. J. Dally, and C. Kozyrakis. Evaluating bufferless flow control for on-chip networks. In Int. Symp. on Networks-on-Chip (NOCS), pages 9--16, 2010.

Digital Library

[13]

J. Mische and T. Ungerer. Low power flitwise routing in an unidirectional torus with minimal buffering. In Workshop on Network on Chip Architectures (NoCArc), pages 63--68, 2012.

Digital Library

[14]

T. Moscibroda and O. Mutlu. A case for bufferless routing in on-chip networks. In Int. Symp. on Computer Architecture (ISCA), 2009.

Digital Library

[15]

A. Olofsson, R. Trogan, O. Raikhman, and L. Adapteva. A 1024-core 70 GFLOP/W floating point manycore microprocessor. In Workshop on High Performance Embedded Computing (HPEC), 2011.

[16]

G. Oxman and S. Weiss. RIDER: Ring deflection router with buffers. Design Automation for Embedded Systems, 18(3-4):141--155, 2014.

Digital Library

[17]

N. Rathod, S. Balachandran, and N. Gala. CAERUS: An Effective Arbitration and Ejection Policy for Routing in an Unidirectional Torus. In Workshop on Interconnection Network Architecture: On-Chip, Multi-Chip (INA-OCMC), 2014.

Digital Library

[18]

A. Shpiner, E. Kantor, P. Li, I. Cidon, and I. Keslassy. On the capacity of bufferless networks-on-chip. IEEE Transactions on Parallel and Distributed Systems, 26(2):492--506, 2015.

[19]

S. Vangal et al. An 80-Tile Sub-100-W TeraFLOPS Processor in 65-nm CMOS. IEEE Journal of Solid-State Circuits, 43(1):29 -41, 2008.

[20]

D. Wentzlaff et al. On-chip interconnection architecture of the tile processor. Micro, IEEE, 27(5):15--31, 2007.

Digital Library

[21]

T. T. Ye, L. Benini, and G. D. Micheli. Packetized on-chip interconnect communication analysis for MPSoC. In Conference on Design, Automation and Test in Europe (DATE), pages 344--349. IEEE, 2003.

Digital Library

Cited By

Gonzalez YNelissen GTovar E(2022)IPDeN: Real-Time deflection-based NoC with in-order flits delivery2022 IEEE 28th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA55878.2022.00023(160-169)Online publication date: Aug-2022
https://doi.org/10.1109/RTCSA55878.2022.00023
Balamurugan KSubrahmanyeswara Rao BVijayaraj M(2021)Performance Analysis of Optad-NoC: A Novel Optimized Routing Algorithm and Intelligent Router for 3D Network-on-ChipWireless Personal Communications10.1007/s11277-021-08834-0Online publication date: 24-Aug-2021
https://doi.org/10.1007/s11277-021-08834-0
Das TGhosal PChatterjee N(2020)VCS: A method of in-order packet delivery for adaptive NoC routingNano Communication Networks10.1016/j.nancom.2020.100333(100333)Online publication date: Dec-2020
https://doi.org/10.1016/j.nancom.2020.100333
Show More Cited By

Index Terms

Minimally buffered deflection routing with in-order delivery in a torus
1. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers
  2. Network types
    1. Network on chip

Recommendations

Buffered deflection routing for networks-on-chip
INA-OCMC '12: Proceedings of the 2012 Interconnection Network Architecture: On-Chip, Multi-Chip Workshop

Bufferless deflection routing works surprisingly well when the network traffic is light or medium, and can outperform a virtual channel router with a small number of buffers, but when the network is working closer to saturation, classic buffered virtual ...
Minimally buffered single-cycle deflection router
DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

With the drift from computation centric designs to communication centric designs in the Chip Multi Processor (CMP) era, the interconnect fabric is gaining more importance. An efficient NoC in terms of power, area and average flit latency has a huge ...
Deflection routing in buffered binary hypercube switches

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

NOCS '17: Proceedings of the Eleventh IEEE/ACM International Symposium on Networks-on-Chip

October 2017

170 pages

ISBN:9781450349840

DOI:10.1145/3130218

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

NOCS '17

Sponsor:

NOCS '17: International Symposium on Networks-on-Chip

October 19 - 20, 2017

Seoul, Republic of Korea

Acceptance Rates

NOCS '17 Paper Acceptance Rate 14 of 44 submissions, 32%;

Overall Acceptance Rate 14 of 44 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
95
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gonzalez YNelissen GTovar E(2022)IPDeN: Real-Time deflection-based NoC with in-order flits delivery2022 IEEE 28th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA55878.2022.00023(160-169)Online publication date: Aug-2022
https://doi.org/10.1109/RTCSA55878.2022.00023
Balamurugan KSubrahmanyeswara Rao BVijayaraj M(2021)Performance Analysis of Optad-NoC: A Novel Optimized Routing Algorithm and Intelligent Router for 3D Network-on-ChipWireless Personal Communications10.1007/s11277-021-08834-0Online publication date: 24-Aug-2021
https://doi.org/10.1007/s11277-021-08834-0
Das TGhosal PChatterjee N(2020)VCS: A method of in-order packet delivery for adaptive NoC routingNano Communication Networks10.1016/j.nancom.2020.100333(100333)Online publication date: Dec-2020
https://doi.org/10.1016/j.nancom.2020.100333
Malik GKapre N(2019)Enhancing Butterfly Fat Tree NoCs for FPGAs with Lightweight Flow Control2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM.2019.00030(154-162)Online publication date: Apr-2019
https://doi.org/10.1109/FCCM.2019.00030
Wasly SPellizzoni RKapre N(2017)HopliteRT: An efficient FPGA NoC for real-time applications2017 International Conference on Field Programmable Technology (ICFPT)10.1109/FPT.2017.8280122(64-71)Online publication date: Dec-2017
https://doi.org/10.1109/FPT.2017.8280122

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten