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

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.

• M. K. Benhaoua
• A. K. Singh
• A. E. H. Benyamina
• A. Kumar
• P. Boulet

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

[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.