research-article

Position-based weighted round-robin arbitration for equality of service in many-core network-on-chips

Authors:

Kiyoung ChoiAuthors Info & Claims

NoCArc '12: Proceedings of the Fifth International Workshop on Network on Chip Architectures

Pages 51 - 56

https://doi.org/10.1145/2401716.2401728

Published: 01 December 2012 Publication History

Abstract

This paper presents the position-based weighted round-robin arbitration for equality of service in many-core network-on-chips employing a deterministic routing algorithm. We concentrate on the network saturation induced by the hot-spot traffic that occurs when the threads running on the system simultaneously access shared data, global shared locks, etc. It exploits the deterministic properties of the interconnect network---the topology and the routing algorithm. This leads to the omission of additional information in packet headers, compared to the previous approaches. The hardware overhead is minimal, requiring only the weight counters in addition to a typical round-robin arbiter. Compared with the previous work, the proposed algorithm also reduces the critical path delay due to its simplicity. Although designed against the hot-spot traffic, the proposed arbitration scheme shows little performance degradation under other traffic patterns in terms of the average latency and the saturation throughput.

References

[1]

J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 5th ed., MA: Morgan Kaufmann, 2012.

Digital Library

[2]

ITRS, "International Technology Roadmap for Semiconductors 2011," 2011. {Online}. Available: http://www.itrs.net/Links/2011ITRS/Home2011.htm.

[3]

M. M. Lee, J. Kim, D. Abts, M. Marty, and J. W. Lee, "Probabilistic distance-based arbitration: providing equality of service for many-core CMPs," in 43rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-43), Georgia, 2010.

Digital Library

[4]

G. F. Pfister and V. A. Norton, ""Hot Spot" Contention and Combining in Multistage Interconnection Networks," IEEE Transactions on Computers, vol. c-34, no. 10, pp. 943--948, 1985.

[5]

L. L. Peterson and B. S. Davie, Computer Networks: A Systems Approach, 5th ed., MA: Morgan Kaufmann, 2012.

Digital Library

[6]

A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: The sigle-node case," IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 344--357, 1993.

Digital Library

[7]

J. B. Nagle, "On packet switches with infinite storage," IEEE Transactions on Communications, vol. 35, no. 4, pp. 435--438, 1987.

[8]

D. Abts and D. Weisser, "Age-based packet arbitration in large-radix k-ary n-cubes," in 2007 Supercomputing (SC07), Reno, 2007.

Digital Library

[9]

C. J. Glass and L. M. Ni, "The turn model for adaptive routing," Journal of the Association for Computing Machinery, vol. 41, no. 5, pp. 874--902, 1994.

Digital Library

[10]

P. Gupta and N. McKeown, "Designing and implementing a fast crossbar scheduler," IEEE Micro, pp. 20--28, Jan/Feb 1999.

Digital Library

[11]

W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks, CA: Morgan Kaufmann, 2004.

Digital Library

[12]

W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Transactions on Computers, vol. c-36, no. 5, pp. 547--553, 1987.

Digital Library

[13]

Accellera Systems Initiative, "SystemC," {Online}. Available: http://www.accellera.org.

[14]

J. Howard, S. Dighe, Y. Hoskote, S. Vangal, D. Finan, G. Ruhl, D. Jenkins, H. Wilson, N. Borkar, G. Schrom, F. Pailet, S. Jain, T. Jacob, S. Yada, S. Marella, P. Salihundam, V. Erraguntla, M. Konow, M. Riepen, G. Droege, J. Lindemann, M. Gries, T. Apel, K. Henriss, T. Lund-Larsen, S. Steibl, S. Borkar, V. De, R. V. D. Wijngaart, and T. Mattson, "A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS," in IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2010.

[15]

S. Bell, B. Edwards, J. Amann, R. Conlin, K. Joyce, V. Leung, J. MacKay, M. Reif, L. Bao, J. Brown, M. Mattina, C.-C. Miao, C. Ramey, D. Wentzlaff, W. Anderson, E. Berger, N. Fairbanks, D. Khan, F. Montenegro, J. Stickney, and J. Zook, "TILE64 processor: A 64-core SoC with mesh interconnect," in IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2008.

Cited By

Matin MMehranzadeh AChekin MMosleh M(2024)HTPA: a hybrid traffic pattern aware arbitration strategy for network on chip systemsCluster Computing10.1007/s10586-024-04568-327:8(11471-11489)Online publication date: 27-May-2024
https://doi.org/10.1007/s10586-024-04568-3
Monemi AKhunjush FPalesi MSarbazi-Azad H(2020)An Enhanced Dynamic Weighted Incremental Technique for QoS Support in NoCACM Transactions on Parallel Computing10.1145/33914427:2(1-31)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3391442
Cardona JHernandez CAbella JCazorla F(2018)EOmesh: Combined Flow Balancing and Deterministic Routing for Reduced WCET Estimates in Embedded Real-Time SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285729837:11(2451-2461)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2857298
Show More Cited By

Index Terms

Position-based weighted round-robin arbitration for equality of service in many-core network-on-chips
1. Networks
  1. Network architectures

Recommendations

Ping-lock round robin arbiter

Arbiter is the core element in shared-resources systems such as in network-on-chip (NoC), conventional interconnection buses and computer network switch schedulers. Arbiters are located in the critical path delay (CPD) of these systems, that ...
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 ...
Flexible Reconfigurable On-chip Networks for Multi-core SoCs
HEART '18: Proceedings of the 9th International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies

Multi and many-core embedded SoCs (System-on-Chip) provide key solutions to meet the extraordinary demands of current and future applications. This fact becomes critical when the chip design dives to the limitation of sub-nanometer technologies that ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

NoCArc '12: Proceedings of the Fifth International Workshop on Network on Chip Architectures

December 2012

79 pages

ISBN:9781450315401

DOI:10.1145/2401716

Program Chairs:
Maurizio Palesi
Kore University, Italy
,
Terrence Mak
The Chinese University of Hong Kong

Copyright © 2012 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

Publication History

Published: 01 December 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Research Foundation of Korea

Conference

NoCArc '12

NoCArc '12: Fifth International Workshop on Network on Chip Architectures

December 1, 2012

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 46 of 122 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
217
Total Downloads

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

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Matin MMehranzadeh AChekin MMosleh M(2024)HTPA: a hybrid traffic pattern aware arbitration strategy for network on chip systemsCluster Computing10.1007/s10586-024-04568-327:8(11471-11489)Online publication date: 27-May-2024
https://doi.org/10.1007/s10586-024-04568-3
Monemi AKhunjush FPalesi MSarbazi-Azad H(2020)An Enhanced Dynamic Weighted Incremental Technique for QoS Support in NoCACM Transactions on Parallel Computing10.1145/33914427:2(1-31)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3391442
Cardona JHernandez CAbella JCazorla F(2018)EOmesh: Combined Flow Balancing and Deterministic Routing for Reduced WCET Estimates in Embedded Real-Time SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285729837:11(2451-2461)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2857298
Cardona JHernandez CMezzetti EAbella JCazorla F(2018)NoCo: ILP-Based Worst-Case Contention Estimation for Mesh Real-Time Manycores2018 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2018.00043(265-276)Online publication date: Dec-2018
https://doi.org/10.1109/RTSS.2018.00043
Panić MHernandez CAbella JRoca AQuiñones ECazorla FFanucci LTeich J(2016)Improving performance guarantees in wormhole mesh NoC designsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972154(1485-1488)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.5555/2971808.2972154
Park HChoi K(2016)Adaptively weighted round‐robin arbitration for equality of service in a many‐core network‐on‐chipIET Computers & Digital Techniques10.1049/iet-cdt.2015.004910:1(37-44)Online publication date: Jan-2016
https://doi.org/10.1049/iet-cdt.2015.0049
Han SLee JChoi KMehdipour FDimitrakopoulos G(2014)Tree-Mesh Heterogeneous Topology for Low-Latency NoCProceedings of the 2014 International Workshop on Network on Chip Architectures10.1145/2685342.2685346(19-24)Online publication date: 13-Dec-2014
https://dl.acm.org/doi/10.1145/2685342.2685346

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.

Media

Figures

Other

Tables

View Table of Contents