Heuristic for Accelerating Run-Time Task Mapping in NoC-Based Heterogeneous MPSoCs

Authors: M. K. Benhaoua, A. K. Singh, A. E. H. Benyamina, A. Kumar, P. Boulet

Abstract:

In this paper, we propose a new packing strategy to find a free resource for run-time mapping of application tasks to NoC-based Heterogeneous MPSoC. The proposed strategy minimizes the task mapping time in addition to placing the communicating tasks close to each other. To evaluate our approach, a comparative study is carried out for a platform containing single task supported PEs. Experiments show that our strategy provides better results when compared to latest dynamic mapping strategies reported in the literature.

Keywords: Multi-Processor Systems-on-Chip (MPSoCs), Network-on-Chip (NoC), Heterogeneous architectures, Dynamic mapping heuristics.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1097261

References:

[1] L.Benini and G. D. Mecheli, “Networks on chips: a new SoC paradigm,” Computer, vol. 35 , Issue: 1, pp. 70–78, 2002.
[2] D.Bertozzi and L.Benini, “A network-on-chip architecture for gigascale systems-on-chip,” Circuits and Systems Magazine, IEEE, vol. 4 , Issue: 2, pp. 18–31, 2004.
[3] A.Singh, T.Srikanthan, A.Kumar, and W.Jigang, “Communicationaware heuristics for run-time task mapping on NoC-based MPSoC platforms,” Journal of Systems Architecture, vol. 56 , Issue: 7, pp. 242– 255, 2010.
[4] Y.Zhang and al, “Task scheduling and voltage selection for energy minimization,” in Design Automation Conference, 2002. Proceedings. 39th, 2002.
[5] D.Shin and J.Kim, “Power-aware communication optimization for networks-on-chips with voltage scalable links,” in Hardware/Software Codesign and System Synthesis, 2004. CODES + ISSS 2004. International Conference on, 2004.
[6] F.Vardi, S.Saeidi, and A.Khademzadeh, “Crinkle: A heuristic mapping algorithm for network on chip,” IEICE Electronics Express, vol. 6 , Issue: 24, pp. 1737–1744, 2009.
[7] Carvalho and al., “Evaluation of static and dynamic task mapping algorithms in NoC-based MPSoCs,” in 2009 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools, 2009.
[8] Smit and al., “Run-time mapping of applications to a heterogeneous SoC,” in Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings, 2004.
[9] Holzenspies, “Mapping streaming applications on a reconfigurable MPSoC platform at run-time,” in System-on-Chip, 2007 International Symposium on, 2007.
[10] CL.Chou and R. Marculescu, “Incremental run-time application mapping for homogeneous NoCs with multiple voltage levels,” in Hardware/Software Codesign and System Synthesis (CODES+ISSS), 2007 5th IEEE/ACM/IFIP International Conference on, 2007.
[11] CL.Chou and R. Marculescu, “User-aware dynamic task allocation in networks-on-chip,” in Design, Automation and Test in Europe, 2008. DATE ’08, 2008.
[12] A. Mehran, A. Khademzadeh, S. Saeidi, “DSM: A heuristic dynamic spiral mapping algorithm for network on chip,” IEICE Electronics, vol. 5 , Issue: 13, pp. 5–13, 2008.
[13] Marcelo, “Multi-task dynamic mapping onto NoC-based MPSoCs,” in SBCCI ’11 Proceedings of the 24th symposium on Integrated circuitsand systems design, 2011.
[14] E.Carvalho and F.Moraes, “Congestion-aware task mapping in heterogeneous MPSoCs,” in System-on-Chip, 2008. SOC 2008. International Symposium on, 2008.
[15] S.Wildermann, T.Ziermann, and J.Teichet, “Run time mapping of adaptive applications onto homogeneous NoC-based reconfigurable architectures,” in Field-Programmable Technology, 2009. FPT 2009. International Conference on, 2009.
[16] Holzenspies, J.Hurink, J.Kuper, and G.Smit, “Run-time spatial mapping of streaming applications to a heterogeneous multi-processor system-onchip (MPSOC),” in Design, Automation and Test in Europe, 2008. DATE ’08, 2008.
[17] A.Schranzhofer, C.Jian-Jia, L.Santinelli, and L.Thiele, “Dynamic and adaptive allocation of applications on MPSoC platforms,” in Design Automation Conference (ASP-DAC), 2010 15th Asia and South Pacific, 2010.
[18] E.Carvalho, N.Calazans, and F.Moraes, Dynamic task mapping for MPSoCsIEEE Design Test of Computers, vol. 27 , Issue: 5, pp. 26–35, 2010.
[19] A.K.Singh and al, “Eficient heuristics for minimizing communication overhead in NoC-based heterogeneous MPSoC platforms,” in Rapid System Prototyping, 2009. RSP ’09. IEEE/IFIP International Symposium on, 2009.
[20] M.Faruque, R.Krist, and J.Henkel, “Adam: Run-time agent-based distributed application mapping for on-chip communication,” in Design Automation Conference, 2008. DAC 2008. 45th ACM/IEEE, 2008.
[21] A. Jerraya et al., Guest editors’ introduction: multiprocessor systems-onchips, Computer 38 (7) (2005) 36–40.
[22] S. Vangal, J. Howard, G. Ruhl, S. Dighe, H. Wilson, J. Tschanz, D. Finan, P. Iyer, A. Singh, T. Jacob, S. Jain, S. Venkataraman, Y. Hoskote, N. Borkar, An 80-tile 1.28tflops ne twork-on-chip in 65nm cmos, in: Solid-State Circuits Conference, 2007, pp. 98–589.
[23] D. Bertozzi, L. Benini, Xpipes: a network-on-chip architecture for gigascale systems-on-chip, Circ. Syst. Mag. IEEE 4 (2) (2004) 18–31.
[24] L. Smit et al., Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture, in: FPT, 2004, pp. 421– 424.
[25] M. Kistler et al., Cell multiprocessor communication network: built for speed, IEEE Micro 26 (3) (2006) 10–23.
[26] E. Carvalho, N. Calazans, F. Moraes, Heuristics for Dynamic Task Mapping in NoC-based Heterogeneous MPSoCs, IEEE International Workshop on Rapid system Prototyping (RSP), 2007, pp. 34–40.
[27] P.K Sahu and S.Chattopadhyay, A survey on application mapping strategies for Network-on-Chip design, Journal of Systems Architecture: the EUROMICRO Journal, Volume 59 Issue 1, January, 2013, pp 60-76.
[28] A.K. Singh, W. Jigang, A. Kumar, T. Srikanthan, Run-time mapping of multiple communicating tasks on MPSoC platforms, Procedia Computer Science, 2010, pp. 1019-1026.
[29] A.K. Singh, M. Shafique, A. Kumar, J. Henkel, Mapping on multi/many-core systems: survey of current and emerging trends, Proceedings of the 50th Annual Design Automation Conference (DAC), 2013, pp. 1-10.