Communication architecture optimization: making the shortest path shorter in regular networks-on-chip

ABSTRACT

Network-on-Chip (NoC)-based communication represents a promising solution to complex on-chip communication problems. Due to their regular structure, mesh-like NoC architectures have become very popular recently. However, they have poor topological properties such as long inter-node distances. In this paper, we address this very issue and explore the potential of partial NoC customization to improve both static and dynamic properties of the network significantly, while minimally affecting its regularity. Precise energy measurements on an FPGA prototype show that the improvement in network properties is achieved without a significant penalty in area and communication energy consumption.

REFERENCES

• 1: A. Hemani, et. al. "Network on Chip: An architecture for billion transistor era," Proc. IEEE NorChip Conference, Nov. 2000.
• 2: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 3: Mikael Millberg , Erland Nilsson , Rikard Thid , Shashi Kumar , Axel Jantsch, The Nostrum Backbone - a Communication Protocol Stack for Networks on Chip, Proceedings of the 17th International Conference on VLSI Design, p.693, January 05-09, 2004
• 4: Davide Bertozzi , Antoine Jalabert , Srinivasan Murali , Rutuparna Tamhankar , Stergios Stergiou , Luca Benini , Giovanni De Micheli, NoC Synthesis Flow for Customized Domain Specific Multiprocessor Systems-on-Chip, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.113-129, February 2005 [doi>10.1109/TPDS.2005.22]
• 5: E. Rijpkema , K. G. W. Goossens , A. Radulescu , J. Dielissen , J. van Meerbergen , P. Wielage , E. Waterlander, Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.10350, March 03-07, 2003
• 6: Srinivasan Murali , Giovanni De Micheli, SUNMAP: a tool for automatic topology selection and generation for NoCs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996809]
• 7: J. Hu, R. Marculescu, "Energy- and Performance-Aware Mapping for Regular NoC Architectures," IEEE Trans. on Computer-Aided Design of ICs and Systems, 24(4), April 2005.
• 8: Alessandro Pinto , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Efficient Synthesis of Networks On Chip, Proceedings of the 21st International Conference on Computer Design, p.146, October 13-15, 2003
• 9: Umit Y. Ogras , Radu Marculescu, Energy- and Performance-Driven NoC Communication Architecture Synthesis Using a Decomposition Approach, Proceedings of the conference on Design, Automation and Test in Europe, p.352-357, March 07-11, 2005 [doi>10.1109/DATE.2005.137]
• 10: Krishnan Srinivasan , Karam S. Chatha , Goran Konjevod, Linear Programming based Techniques for Synthesis of Network-on-Chip Architectures, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.422-429, October 11-13, 2004
• 11: U. Y. Ogras , R. Marculescu, Application-specific network-on-chip architecture customization via long-range link insertion, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.246-253, November 06-10, 2005, San Jose, CA
• 12: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Proceedings of the 19th annual international symposium on Computer architecture, p.278-287, May 19-21, 1992, Queensland, Australia
• 13: G. Kotsis, "Interconnection Topologies for Parallel Processing Systems," Proc. of Parallele Systeme und Algorithmen, 1993.
• 14: D. J. Watts, S. H. Strogatz, "Collective dynamics of small-world networks", In Nature, vol. 393, pp. 440--442, 1998
• 15: M. E. J. Newman, D. J. Watts, "Scaling and percolation in the small-world network model," Phys. Rev. E 60, 7332--7342, 1999
• 16: R. Albert, A. Barabasi, "Statistical mechanics of complex networks," Reviews of Modern Physics, vol. 74, 2002.
• 17: Henryk Fukś , Anna T. Lawniczak, Performance of data networks with random links, Mathematics and Computers in Simulation, v.51 n.1-2, p.101-117, Dec. 22, 1999 [doi>10.1016/S0378-4754(99)00125-1]
• 18: L. Carloni, et. al. "Theory of latency-insensitive design," IEEE Trans. on Computer-Aided Design of ICs and Systems. 20(9), 2001.
• 19: R. Dick, "Embedded system synthesis benchmarks suites (E3S)," http://www.ece.northwestern.edu/~dickrp/e3s/.
• 20: Hyung Gyu Lee , Kyungsoo Lee , Yongseok Choi , Naehyuck Chang, Cycle-Accurate Energy Measurement and Characterization of FPGAs, Analog Integrated Circuits and Signal Processing, v.42 n.3, p.239-251, March 2005 [doi>10.1007/s10470-005-6758-5]