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

research-article

A DP-network for optimal dynamic routing in network-on-chip

Authors:

Peter Y.K. Cheung,

Kai Pui LamAuthors Info & Claims

CODES+ISSS '09: Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis

Pages 119 - 128

https://doi.org/10.1145/1629435.1629452

Published: 11 October 2009 Publication History

Abstract

Dynamic routing is desirable because of its substantial improvement in communication bandwidth and intelligent adaptation to faulty links and congested traffics. However, implementation of adaptive routing in a network-on-chip (NoC) system is not trivial and further complicated by the requirements of deadlock-free and real-time optimal decision making. In this paper, we present a deadlock-free routing architecture which employs a dynamic programming (DP) network to provide on-the-fly optimal path planning and network monitoring for packet switching. Also, a new routing strategy called k-step look ahead is introduced. This new strategy can substantially reduced the size of routing table and maintain a high quality of adaptation which leads to a scalable dynamic routing solution with minimal hardware overhead. Our results based on a cycle-accurate simulator demonstrate the effectiveness of the DP-network, which outperforms both the deterministic and adaptive routing algorithms in average delay on various traffic scenarios by 22.3%. Moreover, the hardware overhead for DP-network is insignificant based on the results obtained from the hardware implementations.

References

[1]

ASCIA, G., CATANIA, V., PALESI, M., AND PATTI, D. Implementation and analysis of a new selection strategy for adaptive routing in Networks-on-Chip. IEEE Transactions on Computers 57 (2008), 809--820.

Digital Library

[2]

BELLMAN, R. On a routing problem. Quarterly of Applied Mathematics 16 (1958), 87--90.

[3]

BENINI, L., AND BERTOZZI, D. Network-on-Chip architectures and design methods. IEE Proc.-Comput. Digit. Tech. 152 (2005), 261--272.

[4]

BERTSEKAS, D., AND TSITSIKLIS, J. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Inc., Princeton, NJ, 1989.

Digital Library

[5]

CHIU, G.-M. The Odd-Even turn model for adaptive routing. IEEE Trans. Parallel and Distributed Systems 11 (2000), 729--738.

Digital Library

[6]

DALLY, W. J., AND TOWLES, B. Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004.

Digital Library

[7]

FAZZINO, F., PALESI, M., AND PATTI, D. Noxim, Network-on-Chip simulator.

[8]

GLASS, C. J., AND NI, L. M. The turn model for adaptive routing. In Proc. of the International Symposium on Computer Architecture (1992).

Digital Library

[9]

HU, J. Design Methodologies For Application Specific Networks-on-Chip. PhD thesis, Carnegie Mellon University, 2005.

[10]

HU, J., AND MARCULESCU, R. DyAD -- smart routing for Networks-on-Chip. In Proc. of the 41st ACM/IEEE Design Automation Conference (2004).

Digital Library

[11]

KUMAR, S., JANTSCH, A., SOININEN, J.-P., FORSELL, M., MILLBERG, M., BERG, J., TIENSYRJ, K., AND HEMANI, A. A Network-on-Chip architecture and design methodology. In Proc. of International Symposium in VLSI (2002).

Digital Library

[12]

LAM, K., AND TONG, C. Closed semiring connectionist network for the bellman--ford computation. IEE Proc. Comput. Digit. Tech. 143 (1996), 189--195.

[13]

MAK, T., SEDCOLE, P., CHEUNG, P., LUK, W., AND LAM, K. A hybrid analog-digital routing network for NoC dynamic routing. Proc. IEEE International Symposium on Networks-on-Chip (2007).

Digital Library

[14]

OGRAS, U., AND MARCULESCU, R. Application-specific Network-on-Chip architecture customization via long-range link insertion. In Proc. of ICCAD (2005).

Digital Library

[15]

PALESI, M., HOLSMARK, R., AND KUMAR, S. A methodology for design of application specific deadlock-free routing algorithms for noc systems. In Proc. of the 4th international conference on Hardware/software codesign and system synthesis (2006).

Digital Library

[16]

SCHONWALD, T., ZIMMERMANN, J., BRINGMANN, O., AND ROSENSTIEL, W. Fully adaptive fault-tolerant routing algorithm for Network-on-Chip architectures. In Proc. of 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools (2007).

Digital Library

[17]

WU, D., AL-HASHIMI, B. M., AND SCHMITZ, M. T. Improving routing efficiency for network-on-chip through contention-aware input selection. In Proc. of ASP-DAC (2006).

Digital Library

[18]

XILINX. Xilinx System Generator for DSP version 8.2.02: User Guide.

Cited By

Wang LWang XMak T(2016)Adaptive Routing Algorithms for Lifetime Reliability Optimization in Network-on-ChipIEEE Transactions on Computers10.1109/TC.2015.250657165:9(2896-2902)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1109/TC.2015.2506571
Wang LWang XMak T(2015)Dynamic Programming-Based Lifetime Reliability Optimization in Networks-on-ChipVLSI-SoC: Internet of Things Foundations10.1007/978-3-319-25279-7_1(1-20)Online publication date: 25-Nov-2015
https://doi.org/10.1007/978-3-319-25279-7_1
Dahir NAl-Dujaily RMak TYakovlev A(2014)Thermal Optimization in Network-on-Chip-Based 3D Chip Multiprocessors Using Dynamic Programming NetworksACM Transactions on Embedded Computing Systems10.1145/258466813:4s(1-25)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1145/2584668
Show More Cited By

Index Terms

A DP-network for optimal dynamic routing in network-on-chip
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Hardware
  1. Very large scale integration design

Recommendations

A survey of routing algorithm for mesh Network-on-Chip

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (...
An Advanced NoP Selection Strategy for Odd-Even Routing Algorithm in Network-on-Chip
ICA3PP '09: Proceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing

The Odd-Even (OE) [5] routing strategy has greatly improved the degree of adaptiveness over other adaptive routing strategies. It depends on an efficient selection strategy to achieve the potential performance of the improved adaptiveness. Asica <em>et ...
A traffic-aware adaptive routing algorithm on a highly reconfigurable network-on-chip architecture
CODES+ISSS '12: Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

In this paper, we propose a flexible NoC architecture and a dynamic distributed routing algorithm which can enhance the NoC communication performance with minimal energy overhead. In particular, our proposed NoC architecture exploits the following two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CODES+ISSS '09: Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis

October 2009

498 pages

ISBN:9781605586281

DOI:10.1145/1629435

Program Chairs:
Wolfgang Rosenstiel
University of Tübingen, Germany
,
Kazutoshi Wakabayashi
NEC, Japan

Copyright © 2009 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWeek '09

Sponsor:

ESWeek '09: Fifth Embedded Systems Week

October 11 - 16, 2009

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
340
Total Downloads

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

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang LWang XMak T(2016)Adaptive Routing Algorithms for Lifetime Reliability Optimization in Network-on-ChipIEEE Transactions on Computers10.1109/TC.2015.250657165:9(2896-2902)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1109/TC.2015.2506571
Wang LWang XMak T(2015)Dynamic Programming-Based Lifetime Reliability Optimization in Networks-on-ChipVLSI-SoC: Internet of Things Foundations10.1007/978-3-319-25279-7_1(1-20)Online publication date: 25-Nov-2015
https://doi.org/10.1007/978-3-319-25279-7_1
Dahir NAl-Dujaily RMak TYakovlev A(2014)Thermal Optimization in Network-on-Chip-Based 3D Chip Multiprocessors Using Dynamic Programming NetworksACM Transactions on Embedded Computing Systems10.1145/258466813:4s(1-25)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1145/2584668
Wang LWang XMak T(2014)Dynamic programming-based lifetime aware adaptive routing algorithm for Network-on-Chip2014 22nd International Conference on Very Large Scale Integration (VLSI-SoC)10.1109/VLSI-SoC.2014.7004156(1-6)Online publication date: Oct-2014
https://doi.org/10.1109/VLSI-SoC.2014.7004156
Dahir NTarawneh GMak TAl-Dujaily RYakovlev A(2014)Design and Implementation of Dynamic Thermal-Adaptive Routing Strategy for Networks-on-ChipProceedings of the 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing10.1109/PDP.2014.70(384-391)Online publication date: 12-Feb-2014
https://dl.acm.org/doi/10.1109/PDP.2014.70
Al-Dujaily RMak TXia FYakovlev APalesi M(2013)Run-Time Deadlock DetectionRouting Algorithms in Networks-on-Chip10.1007/978-1-4614-8274-1_3(41-68)Online publication date: 25-Sep-2013
https://doi.org/10.1007/978-1-4614-8274-1_3
Al-Dujaily RMak TZhou KLam KMeng YYakovlev APoon C(2011)On-chip dynamic programming networks using 3D-TSV integration2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation10.1109/SAMOS.2011.6045478(318-325)Online publication date: Jul-2011
https://doi.org/10.1109/SAMOS.2011.6045478
Mak TAl-Dujaily RKuan Zhou Kai-Pui Lam Yicong Meng Yakovlev AChi-Sang Poon (2011)Dynamic Programming Networks for Large-Scale 3D Chip IntegrationIEEE Circuits and Systems Magazine10.1109/MCAS.2011.94210211:3(51-62)Online publication date: 2011
https://doi.org/10.1109/MCAS.2011.942102
Kia HAbabei C(2011)A new fault-tolerant and congestion-aware adaptive routing algorithm for regular Networks-on-Chip2011 IEEE Congress of Evolutionary Computation (CEC)10.1109/CEC.2011.5949923(2465-2472)Online publication date: Jun-2011
https://doi.org/10.1109/CEC.2011.5949923
Mak TLam KNg HRachmuth GPoon C(2010)A CMOS current-mode dynamic programming circuitIEEE Transactions on Circuits and Systems Part I: Regular Papers10.1109/TCSI.2010.205266157:12(3112-3123)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/TCSI.2010.2052661
Show More Cited By

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