More Web Proxy on the site http://driver.im/

research-article

Open access

Smart-Hop Arbitration Request Propagation: Avoiding Quadratic Arbitration Complexity and False Negatives in SMART NoCs

Authors:

Yashar Asgarieh,

Bill LinAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 24, Issue 6

Article No.: 64, Pages 1 - 25

https://doi.org/10.1145/3356235

Published: 14 October 2019 Publication History

All formats PDF

Abstract

SMART-based NoC designs achieve ultra-low latencies by enabling flits to traverse multiple hops within a single clock cycle. Notwithstanding the clear performance benefits, SMART-based NoCs suffer from several shortcomings: each router must arbitrate among a quadratic number of requests, which leads to high costs; each router independently makes its own arbitration decisions, which leads to a problem called false negatives that causes throughput loss. In this article, we propose a new SMART-based NoC design called SHARP that overcomes these shortcomings. Our evaluation demonstrates that SHARP increases throughput by up to 19% and average link utilization by up to 24% by avoiding false negatives. By avoiding quadratic arbitration, our evaluation further demonstrates that SHARP reduces the wiring and area overhead significantly.

References

[1]

Niket Agarwal, Tushar Krishna, Li-Shiuan Peh, and Niraj K. Jha. 2009. GARNET: A detailed on-chip network model inside a full-system simulator. In ISPASS. IEEE Computer Society, 33--42. http://dblp.uni-trier.de/db/conf/ispass/ispass2009.html#AgarwalKPJ09.

[2]

James Balfour and William J. Dally. 2006. Design tradeoffs for tiled CMP on-chip networks. In ACM International Conference on Supercomputing (ICS). 187--198.

[3]

Luca Benini and Giovanni De Micheli. 2002. Networks on chips: A new SoC paradigm. IEEE Computer 35, 1 (2002), 70--78.

Digital Library

[4]

Nathan Binkert, Bradford Beckmann, Gabriel Black, Steven K. Reinhardt, Ali Saidi, Arkaprava Basu, Joel Hestness, Derek R. Hower, Tushar Krishna, Somayeh Sardashti, Rathijit Sen, Korey Sewell, Muhammad Shoaib, Nilay Vaish, Mark D. Hill, and David A. Wood. 2011. The Gem5 simulator. SIGARCH Comput. Archit. News 39, 2 (Aug. 2011), 1--7.

Digital Library

[5]

Xianmin Chen and Niraj K. Jha. 2016. Reducing wire and energy overheads of the SMART NoC using a setup request network. IEEE Transactions on Very Large Scale Integration (VLSI) Systems PP, 99 (2016), 1--14.

[6]

William J. Dally and Brian Towles. 2001. Route packets, not wires: On-chip inteconnection networks. In Proceedings of the 38th Annual Design Automation Conference (DAC’01). ACM, New York, 684--689.

[7]

Boris Grot, Joel Hestness, Stephen W. Keckler, and Onur Mutlu. 2009. Express cube topologies for on-chip interconnects. In Proceedings of the IEEE International Symposium on High-Performance Computer Architecture (HPCA). 163--174.

[8]

Nikos Hardavellas, Michael Ferdman, Babak Falsafi, and Anastasia Ailamaki. 2009. Reactive NUCA: Near-optimal block placement and replication in distributed caches. In Proceedings of the 36th Annual International Symposium on Computer Architecture (ISCA’09). ACM, New York, 184--195. http://doi.acm.org/10.1145/1555754.1555779

Digital Library

[9]

John Kim, James Balfour, and William Dally. 2007. Flattened butterfly topology for on-chip networks. In Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'40). IEEE Computer Society, Washington, DC, 172--182.

Digital Library

[10]

Tushar Krishna, Chia-Hsin Owen Chen, Woo-Cheol Kwon, and Li-Shiuan Peh. 2013. Breaking the on-chip latency barrier using SMART. In Proceedings of the 19th IEEE International Symposium on High Performance Computer Architecture (HPCA 2013 (Shenzhen, China, Feb. 23-27, 2013). 378--389.

Digital Library

[11]

Amit Kumar, Partha Kundu, Arvind P. Singh, Li-Shiuan Peh, and Niraj K. Jha. 2007. A 4.6Tbits/s 3.6GHz single-cycle NoC router with a novel switch allocator in 65nm CMOS. In Proceedings of ICCD. IEEE, 63--70. http://dblp.uni-trier.de/db/conf/iccd/iccd2007.html#KumarKSPJ07.

[12]

Amit Kumar, Li-Shiuan Peh, and Niraj K. Jha. 2008. Token flow control. In Proceedings of the 41st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'41). IEEE Computer Society, Washington, DC, 342--353.

[13]

Amit Kumar, Li-Shiuan Peh, Partha Kundu, and Niraj K. Jha. 2007. Express virtual channels: Towards the ideal interconnection fabric. In Proceedings of the 34th Annual International Symposium on Computer Architecture (ISCA’07). ACM, New York, 150--161.

[14]

Hiroki Matsutani, Michihiro Koibuchi, Hideharu Amano, and Tsutomu Yoshinaga. 2009. Prediction router: Yet another low latency on-chip router architecture. In Proceedings of HPCA. IEEE Computer Society, 367--378. http://dblp.uni-trier.de/db/conf/hpca/hpca2009.html#MatsutaniKAY09.

[15]

Amirhossein Mirhosseini, Mohammad Sadrosadati, Behnaz Soltani, Hamid Sarbazi-Azad, and Thomas F. Wenisch. 2017. BiNoCHS: Bimodal network-on-chip for CPU-GPU heterogeneous systems. In Proceedings of the 11th IEEE/ACM International Symposium on Networks-on-Chip. ACM, 7.

[16]

Robert Mullins, Andrew West, and Simon Moore. 2004. Low-latency virtual-channel routers for on-chip networks. In Proceedings of the 31st Annual International Symposium on Computer Architecture (ISCA’04). IEEE Computer Society, Washington, DC, 188--197. http://dl.acm.org/citation.cfm?id=998680.1006717

Digital Library

[17]

Sunghyun Park, Tushar Krishna, Chia-Hsin Owen Chen, Bhavya K. Daya, Anantha Chandrakasan, and Li-Shiuan Peh. 2012. Approaching the theoretical limits of a mesh NoC with a 16-node chip prototype in 45nm SOI. In Proceedings of DAC, Patrick Groeneveld, Donatella Sciuto, and Soha Hassoun (Eds.). ACM, 398--405. http://dblp.uni-trier.de/db/conf/dac/dac2012.html#ParkKCDCP12.

Digital Library

[18]

Li-Shiuan Peh and William J. Dally. 2001. A delay model and speculative architecture for pipelined routers. In Proceedings of the 7th International Symposium on High-Performance Computer Architecture (HPCA’01). IEEE Computer Society, Washington, DC, USA, 255--266. http://dl.acm.org/citation.cfm?id=580550.876446

Digital Library

[19]

Jacob Postman, Tushar Krishna, Christopher Edmonds, Li-Shiuan Peh, and Patrick Chiang. 2013. SWIFT: A low-power network-on-chip implementing the token flow control router architecture with swing-reduced interconnects. IEEE Trans. Very Large Scale Integr. Syst. 21, 8 (Aug. 2013), 1432--1446. http://dx.doi.org/10.1109/TVLSI.2012.2211904

Digital Library

[20]

Korey Sewell, Ronald G. Dreslinski, Thomas Manville, Sudhir Satpathy, Nathaniel Pinckney, Geoffrey Blake, Michael Cieslak, Reetuparna Das, Thomas F. Wenisch, Dennis Sylvester, et al. 2012. Swizzle-switch networks for many-core systems. IEEE Journal on Emerging and Selected Topics in Circuits and Systems 2, 2 (2012), 278--294.

[21]

Chen Sun, Chia-Hsin Owen Chen, George Kurian, Lan Wei, Jason Miller, Anant Agarwal, Li-Shiuan Peh, and Vladimir Stojanovic. 2012. DSENT - A tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling. In Proceedings of the 2012 IEEE/ACM 6th International Symposium on Networks-on-Chip (NOCS’12). IEEE Computer Society, Washington, DC, 201--210.

Digital Library

[22]

Michael Bedford Taylor, Jason Kim, Jason Miller, David Wentzlaff, Fae Ghodrat, Ben Greenwald, Henry Hoffman, Paul Johnson, Jae-Wook Lee, Walter Lee, Albert Ma, Arvind Saraf, Mark Seneski, Nathan Shnidman, Volker Strumpen, Matt Frank, Saman Amarasinghe, and Anant Agarwal. 2002. The RAW microprocessor: A computational fabric for software circuits and general-purpose programs. IEEE Micro 22, 2 (2002), 25--35.

Digital Library

[23]

Sriram Vangal, Jason Howard, Gregory Ruhl, Saurabh Dighe, Howard Wilson, James Tschanz, David Finan, Priya Iyer, Arvind Singh, Tiju Jacob, and Shailendra Jain. 2007. An 80-tile 1.28 TFLOPS network-on-chip in 65nm CMOS. In Proceedings of the IEEE International Solid-State Circuits Conference. 98--99.

Cited By

Zhou XHao PLiu D(2023)PCCNoC: Packet Connected Circuit as Network on Chip for High Throughput and Low Latency SoCsMicromachines10.3390/mi1403050114:3(501)Online publication date: 21-Feb-2023
https://doi.org/10.3390/mi14030501
Afshan Amin Khan Mir RNajeeb-ud-Din (2023)Scheduling Strategies and Future Directions for NoC: A Systematic Literature ReviewAutomatic Control and Computer Sciences10.3103/S014641162304004157:4(413-421)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.3103/S0146411623040041
Chen PChen HLiu WLong LChang WGuan N(2023)DAG-Order: An Order-Based Dynamic DAG Scheduling for Real-Time Networks-on-ChipACM Transactions on Architecture and Code Optimization10.1145/363152721:1(1-24)Online publication date: 3-Nov-2023
https://dl.acm.org/doi/10.1145/3631527
Show More Cited By

Index Terms

Smart-Hop Arbitration Request Propagation: Avoiding Quadratic Arbitration Complexity and False Negatives in SMART NoCs
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Interconnection architectures
      2. Multicore architectures

Recommendations

Implementation and Evaluation of Large Interconnection Routers for Future Many-core Networks on Chip
HPCC '12: Proceedings of the 2012 IEEE 14th International Conference on High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems

As the number of processing elements in the future Networks on Chip (NoC) increases from multi-cores to many-cores, the role of the interconnection communications becomes more critical. The number of cores on a System on Chip (SoC) will reach thousands ...
A NoC-based hybrid message-passing/shared-memory approach to CMP design

Future chip-multiprocessors (CMP) will integrate many cores interconnected with a high-bandwidth and low-latency scalable network-on-chip (NoC). However, the potential that this approach offers at the transport level needs to be paired with an analogous ...
Stream arbitration: Towards efficient bandwidth utilization for emerging on-chip interconnects
Special Issue on High-Performance Embedded Architectures and Compilers

Alternative interconnects are attractive for scaling on-chip communication bandwidth in a power-efficient manner. However, efficient utilization of the bandwidth provided by these emerging interconnects still remains an open problem due to the spatial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 24, Issue 6

November 2019

275 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3357467

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2019 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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 14 October 2019

Accepted: 01 August 2019

Revised: 01 August 2019

Received: 01 December 2018

Published in TODAES Volume 24, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
937
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)10

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou XHao PLiu D(2023)PCCNoC: Packet Connected Circuit as Network on Chip for High Throughput and Low Latency SoCsMicromachines10.3390/mi1403050114:3(501)Online publication date: 21-Feb-2023
https://doi.org/10.3390/mi14030501
Afshan Amin Khan Mir RNajeeb-ud-Din (2023)Scheduling Strategies and Future Directions for NoC: A Systematic Literature ReviewAutomatic Control and Computer Sciences10.3103/S014641162304004157:4(413-421)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.3103/S0146411623040041
Chen PChen HLiu WLong LChang WGuan N(2023)DAG-Order: An Order-Based Dynamic DAG Scheduling for Real-Time Networks-on-ChipACM Transactions on Architecture and Code Optimization10.1145/363152721:1(1-24)Online publication date: 3-Nov-2023
https://dl.acm.org/doi/10.1145/3631527
Chen HChen PLuo XHuai SLiu W(2022)LAMP: Load-Balanced Multipath Parallel Transmission in Point-to-Point NoCsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.315102141:12(5232-5245)Online publication date: Dec-2022
https://doi.org/10.1109/TCAD.2022.3151021
Chen HChen PZhou JDuong LLiu W(2022)ArSMART: An Improved SMART NoC Design Supporting Arbitrary-Turn TransmissionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.309196141:5(1316-1329)Online publication date: May-2022
https://doi.org/10.1109/TCAD.2021.3091961
Lee DLin BCheng C(2021)SMT-Based Contention-Free Task Mapping and Scheduling on 2D/3D SMART NoC with Mixed Dimension-Order RoutingACM Transactions on Architecture and Code Optimization10.1145/348701819:1(1-21)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3487018
Monemi APérez ILeyva NVallejo EBeivide RMoretó MKrishna TKim JAbadal SMiguel J(2021)PIugSMARTProceedings of the 15th IEEE/ACM International Symposium on Networks-on-Chip10.1145/3479876.3481601(41-48)Online publication date: 14-Oct-2021
https://dl.acm.org/doi/10.1145/3479876.3481601
Chen HZhang ZChen PLuo XLi SLiu W(2021)MARCO: A High-performance Task Mapping and Routing Co-optimization Framework for Point-to-Point NoC-based Heterogeneous Computing SystemsACM Transactions on Embedded Computing Systems10.1145/347698520:5s(1-21)Online publication date: 23-Sep-2021
https://dl.acm.org/doi/10.1145/3476985
Chen PChen HZhou JLiu DLi SLiu WChang WGuan NHung CHong JBechini ASong E(2021)Partial order based non-preemptive communication scheduling towards real-time networks-on-chipProceedings of the 36th Annual ACM Symposium on Applied Computing10.1145/3412841.3441895(145-154)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3412841.3441895
Chen PLiu WChen HLi SLi MYang LGuan N(2021)Reduced Worst-Case Communication Latency Using Single-Cycle Multihop Traversal Network-on-ChipIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.301544040:7(1381-1394)Online publication date: Jul-2021
https://doi.org/10.1109/TCAD.2020.3015440
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents