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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (413 KB)

Source

International Conference on Hardware Software Codesign archive
Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis table of contents

Grenoble, France

SESSION: Architecture and routing for NoC table of contents

Pages 119-128

Year of Publication: 2009

ISBN:978-1-60558-628-1

Authors

Terrence Mak	Imperial College London, London, United Kingdom
Peter Y.K. Cheung	Imperial College London, London, United Kingdom
Wayne Luk	Imperial College London, London, United Kingdom
Kai Pui Lam	The Chinese University of Hong Kong, Hong Kong, Hong Kong

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 25, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629435.1629452 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
	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.
	5	CHIU, G.-M. The Odd-Even turn model for adaptive routing. IEEE Trans. Parallel and Distributed Systems 11 (2000), 729--738.
	6	DALLY, W. J., AND TOWLES, B. Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004.
	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).
	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).
	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).
	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).
	14	OGRAS, U., AND MARCULESCU, R. Application-specific Network-on-Chip architecture customization via long-range link insertion. In Proc. of ICCAD (2005).
	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).
	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).
	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).
	18	XILINX. Xilinx System Generator for DSP version 8.2.02: User Guide.