Abstract
3-D Networks-on-Chip (NoCs) emerge as a powerful solution to address both the interconnection and design complexity problems facing future Systems-on-Chip (SoCs). Effective run-time application mapping on a 3-D NoC-based Multiprocessor Systems-on-Chip (MPSoC) can be quite challenging, largely due to the fact that the arrival order and task graphs of the target applications are not known a priori. This paper presents a power-aware run-time incremental mapping algorithm for 3-D NoCs that aims to minimize the communication power for each incoming application as well as reduce the impact of the mapped applications on future applications that are yet to be mapped. In this algorithm, if the vertical links are found to be shorter and provide higher communication bandwidth than horizontal links, more communications will be mapped to vertical links to reduce delay and power consumption. Extensive experiments have been conducted to evaluate the performance of the proposed algorithm and the results are compared with those obtained from the optimal mapping algorithm (branch-and-bound), a random mapping and a simple heuristic. When mapping a single application, the proposed algorithm is four orders of magnitude faster than the branch-and-bound algorithm at a small degradation of mapping quality. When mapping multiple applications incrementally, our algorithm can save 50% communication power compared to the random mapping and 20% communication power compared to the simple heuristic.
This work is supported in part by NSFC under the grants 60873112 and 61028004.
Chapter PDF
Similar content being viewed by others
References
Pavlidis, V.F., Friedman, E.G.: 3-D topologies for networks-on-chip. IEEE Trans. Very Large Scale Integration Systems 15(10), 1081–1090 (2007)
Davis, W.R., Wilson, J., Mick, S., Xu, J., Hua, H., Mineo, C., Sule, A.M., Steer, M., Franzon, P.D.: Demystifying 3D ICs: the pros and cons of going vertical. IEEE Design and Test of Computers 22(6), 498–511 (2005)
Kim, J., Nicopoulos, C., Park, D., Das, R., Xie, Y., Narayanan, V., Yousif, M.S., Das, C.R.: A novel dimensionally-decomposed router for on-chip communication in 3D architectures. In: Int’l Symp. Computer Architecture, vol. 35, pp. 138–149 (2007)
Addo-Quaye, C.: Thermal-aware mapping and placement for 3-D NoC designs. In: IEEE Int’l SoC Conf., pp. 25–28 (2005)
Chou, C.L., Marculescu, R.: Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 29(1), 78–91 (2010)
Chou, C.L., Ogras, U.Y., Marculescu, R.: Energy-and performance-aware incremental mapping for networks on chip with multiple voltage levels. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 27(10), 1866–1879 (2008)
Matsutani, H., Koibuchi, M., Amano, H.: Tightly-coupled multi-layer topologies for 3-D NoCs. In: Int’l Conf. Parallel Processing, pp. 75–85 (2007)
Feero, B.S., Pande, P.P.: Networks-on-Chip in a three-dimensional environment: a performance evaluation. IEEE Trans. Computers 58(1), 32–45 (2009)
Park, D., Eachempati, S., Das, R., Mishra, A.K., Xie, Y., Vijaykrishnan, N., Das, C.R.: MIRA: a multi-layered on-chip interconnect router architecture. In: Int’l Symp. Computer Architecture, pp. 251–261 (2008)
Wang, X., Yang, M., Jiang, Y., Liu, P.: A power-aware mapping approach to map IP cores onto NoCs under bandwidth and latency constraints. ACM Trans. Architecture and Code Optimization 7(1), 1–31 (2009)
Land, A.H., Doig, A.G.: An automatic method for solving discrete programming problems. Econometrica 28, 497–520 (1960)
Hu, J., Marculescu, R.: Energy-and performance-aware mapping for regular NoC architectures. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 24(4), 551–562 (2005)
Smit, L.T., Smit, G.J.M., Hurink, J.L., Broersma, H., Paulusma, D., Wolkotte, P.T.: Run-time assignment of tasks to multiple heterogeneous processors. In: Progress Embedded System Symp., pp. 185–192 (2004)
Carvalho, E., Calazans, N., Moraes, F.: Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs. In: IEEE/IFIP Workshop Rapid System Prototyping, pp. 34–40 (2007)
Lo, V., Windisch, K.J., Liu, W., Nitzberg, B.: Noncontiguous processor allocation algorithms for mesh-connected multicomputers. IEEE Trans. Parallel and Distributed Systems 8(7), 712–726 (1997)
TGFF: task graphs for free, http://ziyang.eecs.umich.edu/~dickrp/tgff/
Dick, R.: Embedded system synthesis benchmarks suite(E3S) (2002), http://ziyang.eecs.umich.edu/~dickrp/e3s/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 IFIP International Federation for Information Processing
About this paper
Cite this paper
Wang, X., Palesi, M., Yang, M., Jiang, Y., Huang, M.C., Liu, P. (2011). Power-Aware Run-Time Incremental Mapping for 3-D Networks-on-Chip. In: Altman, E., Shi, W. (eds) Network and Parallel Computing. NPC 2011. Lecture Notes in Computer Science, vol 6985. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24403-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-24403-2_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24402-5
Online ISBN: 978-3-642-24403-2
eBook Packages: Computer ScienceComputer Science (R0)