150
Network-on-Chip
5.7 Summary
Application mapping refers to the problem of determining the router positions to which individual cores of an application be mapped. The major goal
of the operation is to minimize the communication cost. Communication
cost controls the latency of communication between the cores and the overall power consumption. The mapping problem is NP-hard. In this chapter,
various strategies for application mapping have been discussed. While ILPbased approaches produce the best results, the overall computation time is
high, restricting its usage to only a few cores in the application graph. The
constructive heuristic approaches attempt to construct a solution, which may
be followed by an iterative improvement phase. The evolutionary algorithms
perform particularly well. Such algorithms work well even for reasonably
large number of cores (e.g., 128 cores). The mapping problem can be extended
to the power- and thermal-aware strategies.
References
Ascia, G., Catania, V., and Palesi, M. 2004. Multi-objective mapping for Mesh-based
NoC architectures. International Conference on Hardware/Software Codesign and
System Synthesis, ACM, pp. 182–187.
Ascia, G., Catania, V., and Palesi, M. 2006. Multi-objective genetic approach to mapping problem on network-on-chip. Journal of Universal Computer Science, vol. 12,
no. 4, pp. 370–394.
Bender, A. 1996. MILP based task mapping for heterogeneous multiprocessor systems. Proceedings of International Conference on Design and Automation, IEEE
Computer Society Press, pp. 190–197.
Benyamina, A. H. and Boulet, P. 2007. Multi-objective mapping for NoC architecture.
Journal of Digital Information Management, vol. 5, pp. 378–384.
Benyamina, A. H., Boulet, P., Aroul, A., Eltar, S., and Dellal, K. 2010. Mapping real
time applications on NoC architecture with hybrid multi-objective algorithm.
International Conference on Metaheuristics and Nature Inspired Computing, pp. 1–10.
Bhardwaj, K. and Jena, R. K. 2009. Energy and bandwidth aware mapping of IPs onto
regular NoC architectures using multi-objective genetic algorithms. International
Symposium on System-on-Chip, IEEE Press, pp. 27–31.
Chang, Z., Xiong, G., and Sang, N. 2008. Energy-aware mapping for tree-based NoC
architecture by recursive bipartitioning. International Conference on Embedded
Software and Systems, IEEE Press, pp. 105–109.
Chen, Y., Xie, L., and Li, J. 2009. An energy-aware heuristic constructive mapping algorithm for network on chip. International Conference on ASIC, IEEE Press, pp. 101–104.
Chou, C. L. and Marculescu, R. 2008. Contention-aware application mapping for
network-on-chip communication architectures. IEEE International Conference on
Computer Design, IEEE Press, pp. 164–169.
Network-on-Chip
5.7 Summary
Application mapping refers to the problem of determining the router positions to which individual cores of an application be mapped. The major goal
of the operation is to minimize the communication cost. Communication
cost controls the latency of communication between the cores and the overall power consumption. The mapping problem is NP-hard. In this chapter,
various strategies for application mapping have been discussed. While ILPbased approaches produce the best results, the overall computation time is
high, restricting its usage to only a few cores in the application graph. The
constructive heuristic approaches attempt to construct a solution, which may
be followed by an iterative improvement phase. The evolutionary algorithms
perform particularly well. Such algorithms work well even for reasonably
large number of cores (e.g., 128 cores). The mapping problem can be extended
to the power- and thermal-aware strategies.
References
Ascia, G., Catania, V., and Palesi, M. 2004. Multi-objective mapping for Mesh-based
NoC architectures. International Conference on Hardware/Software Codesign and
System Synthesis, ACM, pp. 182–187.
Ascia, G., Catania, V., and Palesi, M. 2006. Multi-objective genetic approach to mapping problem on network-on-chip. Journal of Universal Computer Science, vol. 12,
no. 4, pp. 370–394.
Bender, A. 1996. MILP based task mapping for heterogeneous multiprocessor systems. Proceedings of International Conference on Design and Automation, IEEE
Computer Society Press, pp. 190–197.
Benyamina, A. H. and Boulet, P. 2007. Multi-objective mapping for NoC architecture.
Journal of Digital Information Management, vol. 5, pp. 378–384.
Benyamina, A. H., Boulet, P., Aroul, A., Eltar, S., and Dellal, K. 2010. Mapping real
time applications on NoC architecture with hybrid multi-objective algorithm.
International Conference on Metaheuristics and Nature Inspired Computing, pp. 1–10.
Bhardwaj, K. and Jena, R. K. 2009. Energy and bandwidth aware mapping of IPs onto
regular NoC architectures using multi-objective genetic algorithms. International
Symposium on System-on-Chip, IEEE Press, pp. 27–31.
Chang, Z., Xiong, G., and Sang, N. 2008. Energy-aware mapping for tree-based NoC
architecture by recursive bipartitioning. International Conference on Embedded
Software and Systems, IEEE Press, pp. 105–109.
Chen, Y., Xie, L., and Li, J. 2009. An energy-aware heuristic constructive mapping algorithm for network on chip. International Conference on ASIC, IEEE Press, pp. 101–104.
Chou, C. L. and Marculescu, R. 2008. Contention-aware application mapping for
network-on-chip communication architectures. IEEE International Conference on
Computer Design, IEEE Press, pp. 164–169.