research-article

Open access

Integrated Mapping and Synthesis Techniques for Network-on-Chip Topologies with Express Channels

Authors:

Sandeep D'souza,

Santanu ChattopadhyayAuthors Info & Claims

ACM Transactions on Architecture and Code Optimization (TACO), Volume 12, Issue 4

Article No.: 40, Pages 1 - 26

https://doi.org/10.1145/2831233

Published: 16 November 2015 Publication History

Abstract

The addition of express channels to a traditional mesh network-on-chip (NoC) has emerged as a viable solution to solve the problem of high latency. In this article, we address the problem of integrated mapping and synthesis for express channel--based mesh NoC topologies. An integer linear programming--based formulation has been presented for the mapping problem followed by a constructive heuristic for simultaneous application mapping and synthesis for an express channel--based NoC. The static and dynamic simulation results indicate that the obtained mappings lead to significant reduction in both average packet delay and network energy consumption. The obtained synthesized topologies were also found to be much more power efficient compared to conventional express channel topologies.

References

[1]

D. Atienza, F. Angiolini, S. Murali, A. Pullini, L. Benini, and D. G. Micheli. 2008. Network-on-chip design and synthesis outlook. Integration—The VLSI Journal 41, 2.

Digital Library

[2]

J. Balfour and W. J. Dally. 2006. Design tradeoffs for tiled CMP on-chip networks. In Proceedings of the 20th Annual International Conference on Supercomputing. 187--198.

Digital Library

[3]

L. Benini. 2006. Application specific NoC design. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’06). 1--5.

Digital Library

[4]

C. Celic and C. Bazlamacci. 2014. Evaluation of energy and buffer aware application mapping for networks on chip. Microprocessors and Microsystems 38, 4.

[5]

CPLEX. 2013. IBM ILOG CPLEX. Retrieved October 14, 2015, from http://www.ibm.com/software/in/integration/optimization/cplex.

[6]

W. J. Dally and B. Towles. 2001. Route packets, not wires: On-chip interconnection networks. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’01). 684--689.

Digital Library

[7]

R. P. Dick, D. L. Rhodes, and W. Wolf. 1998. TGFF: Task graphs for free. In Proceedings of the 6th International Workshop on Hardware/Software Codesign. 97--101.

Digital Library

[8]

A. Faruque, M. Abdullah, R. Krist, and J. Henkel. 2008. ADAM: Run-time agent-based distributed application mapping for on-chip communication. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’08). 760--765.

[9]

P. Ghosh, A. Sen, and A. Hall. 2009. Energy efficient application mapping to NoC processing elements operating at multiple voltage levels. In Proceedings of the IEEE International Symposium on Network-on-Chip (NoCS’09). 80--85.

Digital Library

[10]

B. Grot, J. Hestness, S. W. Keckler, and O. Mutlu 2009. Express cube topologies for on-chip interconnects. In Proceedings of the International Symposium on High Performance Computer Architecture. 163--174.

[11]

J. Hu and R. Marculescu. 2003. Energy-aware mapping for tile-based NoC architectures under performance constraints. In Proceedings of the 2003 Asia and South Pacific Design Automation Conference (ASP-DAC’03). 233--239.

Digital Library

[12]

Intel Sandy Bridge Architecture Document. 2011. http://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf.

[13]

International Technology Roadmap for Semiconductors. 2007. http://www.itrs.net/ITRS&percnt;201999-2014&percnt;20Mtgs,&percnt;20Presentations&percnt;20&&percnt;&percnt;20Links/2007ITRS/Home2007.htm.

[14]

N. Jiang, J. Balfour, D. Becker, B. Towles, W. J. Dally, G. Michelogiannakis, and J. Kim. 2013. A detailed and flexible cycle-accurate network-on-chip simulator. In Proceedings of the 2013 IEEE International Symposium on Performance Analysis of Systems and Software. 86--96.

[15]

A. B. Kahng, B. Li, L. Peh, and K. Samadi. 2009. Orion 2.0: A fast and accurate NoC power and area model for early stage design space exploration. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’09). 423--428.

Digital Library

[16]

B. Kernighan and S. Lin. 1970. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49, 2, 291--307.

[17]

J. Kim, J. Balfour, and W. J. Dally. 2007. Flattened butterfly topology for on-chip networks. Computer Architecture Letters 6, 2, 37--40.

Digital Library

[18]

H. Kuhn. 2005. The Hungarian method for the assignment problem. Naval Research Logistics 2, 1--2, 83--97.

[19]

A. Kumar, L. S. Peh, P. Kundu, and N. K Jha. 2007. Express virtual channels: Towards the ideal interconnection fabric. In Proceedings of the IEEE International Symposium on Computer Architecture. 150--161.

Digital Library

[20]

F. T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Arrays--Trees--Hypercubes. Morgan Kaufmann, San Mateo, CA.

Digital Library

[21]

R. Marculescu and P. Bogdan. 2009. The chip is the network: Toward a science of network-on-chip design. Foundations and Trends in Electronic Design Automation 2, 4, 371--461.

Digital Library

[22]

F. Moein-Darbari, A. Khademzade, and G. Gharooni-Fard. 2009. CGMAP: A new approach to network-on-chip mapping problem. IEICE Electron Express 6, 1, 27--34.

[23]

S. Murali and G. D. Micheli. 2004a. Bandwidth constrained mapping of cores onto NoC architectures. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’04). 896--901.

Digital Library

[24]

S. Murali and G. D. Micheli. 2004b. SUNMAP: A tool for automatic topology selection and generation for NoCs. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’04). 914--919.

Digital Library

[25]

U. Y. Ogras and R. Marculescu. 2006. It's a small world after all: NoC performance optimization via long range link insertion. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 14, 7, 693--705.

Digital Library

[26]

O. Ozturk, M. Kandemir, and S. W. Son. 2007. An ILP based approach to reducing energy consumption in NoC based CMPs. In Proceedings of the IEEE International Symposium on Low Power Electronics and Design (ISLPED’07). 411--414.

Digital Library

[27]

M. Palesi, R. Holsmark, S. Kumar, and V. Catania. 2009. Application specific routing algorithms for networks on chip. IEEE Transactions on Parallel and Distributed Systems 20, 3, 316--330.

Digital Library

[28]

P. P. Pande, C. Grecu, A. Ivanov, and R. Saleh. 2003. High-throughput switch-based interconnect for future SoCs. In Proceedings of the IEEE International Workshop on System-on-Chip for Real Time Applications. 304--310.

[29]

D. Pham, S. Asano, M. Bolliger, M. N. Day, H. P. Hofstee, C. Johns, J. Kahle, A Kameyama, Y. Masubuchi, M. Riley, D. Shippy, D. Stasiak, M. Suzuoki, M. Wang, J. Warnock, S. Weitzel, D. Wendel, T. Yamazaki, and K. Yazawa. 2006. Overview of the architecture, circuit design, and physical implementation of a first-generation cell processor. IEEE Journal of Solid-State Circuits 41, 1, 179--196.

[30]

R. Pop and S. Kumar. 2004. A Survey of Techniques for Mapping and Scheduling Applications to Network on Chip Systems. Research Report 04:4. School of Engineering, Jönköping University, Jönköping, Sweden.

[31]

Z. Qian, P. Bogdan, G. Wei, C. Y. Tsui, and R. Marculescu. 2012. A traffic aware adaptive routing algorithm on a highly reconfigurable network-on-chip architecture. In Proceedings of the 11th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis.

Digital Library

[32]

P. K. Sahu and S. Chattopadhyay. 2013. A survey on application mapping strategies for network-on-chip design. Journal of Systems Architecture 59, 1, 60--76.

Digital Library

[33]

P. Sahu, T. Shah, K. Manna, and S. Chattopadhyay. 2014. Application mapping onto mesh based network-on-chip using discrete particle swarm optimization. IEEE Transactions on Very Large Scale Integrated (VLSI) Systems 22, 2.

Digital Library

[34]

K. Srinivasan, K. S. Chatha, and G. Konjevod. 2006. Linear-programming-based techniques for synthesis of network-on-chip architectures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 14, 4, 407--420.

Digital Library

[35]

S. Tosun. 2011. Cluster-based application mapping for network-on-chip. Advances in Engineering Software 42, 10.

Digital Library

[36]

S. R. Vangal, J. Howard, G. Ruhl, S. Dighe, H. Wilson, J. Tschanz, D. Finan, A. Singh, T. Jacob, S. Jain, V. Erraguntla, C. Roberts, Y. Hoskote, N. Borkar, and S. Borkar. 2008. An 80-tile sub-100-W TeraFLOPS processor in 65-nm CMOS. IEEE Journal of Solid-State Circuits 43, 1, 29--41.

[37]

D. Wentzlaff, P. Griffin, H. Hoffman, L. Bao, B. Edwards, C. Ramey, M. Mattina, C. Miao, J. F. Brown, and A. Agarwal. 2007. On-chip interconnection architecture of the tile processor. IEEE Micro 27, 5, 15--21.

Digital Library

[38]

D. Zhu, L. Chen, S. Yue, and M. Pedram. 2014. Application mapping for express channel-based networks-on-chip. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’14). 1--6.

Digital Library

Cited By

Balamurugan KUmamaheswaran SMamo TNagarajan SRao Namamula L(2022)Roadmap for machine learning based network-on-chip (M/L NoC) technology and its analysis for researchersJournal of Physics Communications10.1088/2399-6528/ac4dd56:2(022001)Online publication date: 18-Feb-2022
https://doi.org/10.1088/2399-6528/ac4dd5

Index Terms

Integrated Mapping and Synthesis Techniques for Network-on-Chip Topologies with Express Channels
1. Hardware
  1. Hardware validation

Recommendations

Application-Specific Network-on-Chip synthesis with flexible router Placement

Network-on-Chip (NoC) has been proposed as a possible solution to the communication problem in nanoscale System-on-Chip (SoC) design. NoC architectures with optimized application-specific topologies have been found to be superior to the regular ...
Express virtual channels: towards the ideal interconnection fabric

Due to wire delay scalability and bandwidth limitations inherent in shared buses and dedicated links, packet-switched on-chip interconnection networks are fast emerging as the pervasive communication fabric to connect different processing elements in ...
Express virtual channels: towards the ideal interconnection fabric
ISCA '07: Proceedings of the 34th annual international symposium on Computer architecture

Due to wire delay scalability and bandwidth limitations inherent in shared buses and dedicated links, packet-switched on-chip interconnection networks are fast emerging as the pervasive communication fabric to connect different processing elements in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Architecture and Code Optimization

ACM Transactions on Architecture and Code Optimization Volume 12, Issue 4

January 2016

848 pages

ISSN:1544-3566

EISSN:1544-3973

DOI:10.1145/2836331

Editor:
Koen De Bosschere
Ghent University

Issue’s Table of Contents

Copyright © 2015 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: 16 November 2015

Accepted: 01 September 2015

Revised: 01 September 2015

Received: 01 April 2015

Published in TACO Volume 12, Issue 4

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

1
Total Citations
View Citations
387
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balamurugan KUmamaheswaran SMamo TNagarajan SRao Namamula L(2022)Roadmap for machine learning based network-on-chip (M/L NoC) technology and its analysis for researchersJournal of Physics Communications10.1088/2399-6528/ac4dd56:2(022001)Online publication date: 18-Feb-2022
https://doi.org/10.1088/2399-6528/ac4dd5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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