A Routing based Genetic Algorithm for Task Mapping on MPSoC
Resumo
This work proposes an optimized task mapping solution called Routing Model-based Genetic Algorithm (RMGA) that combines task mapping and routing problems using an Integer Linear Programming (ILP) model as a fitness function. We compared our proposed RMGA with other Genetic Algorithms (GA) that address the mapping problem using a classical flow×distance fitness function evaluation. Experimental results evaluating communication latency demonstrate that the proposed algorithm outperforms two GAs from literature. It presents up to 30% lower delay when simulating tasks communication pattern of six different applications and varying packet injection rate and NoC dimension. Additionally, RMGA presents the lowest delay of more than 70% in all simulated scenarios compared to the other GAs.
Palavras-chave:
Mapping Problem, Routing Problem, Exact Fitness Evaluation, ILP Routing Model
Referências
A. C. S. Beck C. A. L. Lisbôa and L. Carro Adaptable embedded systems Springer Science & Business Media 2012.
W. Wolf A. A. Jerraya and G. Martin "Multiprocessor system-on-chip (mpsoc) technology" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems vol. 27 no. 10 pp. 1701-1713 2008.
N. E. Jerger T. Krishna and L.-S. Peh "On-chip networks" Synthesis Lectures on Computer Architecture vol. 12 no. 3 pp. 1-210 2017.
L. Benini and G. De Micheli "Networks on chips: A new soc paradigm" Computer-IEEE Computer Society- vol. 35 no. EPFL-ARTICLE-165542 pp. 70-78 2002.
A. Agarwal C. Iskander and R. Shankar "Survey of network on chip (noc) architectures & contributions" Journal of engineering Computing and Architecture vol. 3 no. 1 pp. 21-27 2009.
S. Tosun O. Ozturk E. Ozkan and M. Ozen "Application mapping algorithms for mesh-based network-on-chip architectures" The Journal of Supercomputing vol. 71 no. 3 pp. 995-1017 2015.
M. R. Garey and D. S. Johnson Computers and intractability New York:wh freeman vol. 29 2002.
X. Wang H. Liu Z. Yu and K. Shen "A novel two-phase heuristic for application mapping onto mesh-based network-on-chip" iEICE Electronics Express 2016.
W. Zhang L. Hou J. Wang S. Geng and W. Wu "Comparison research between xy and odd-even routing algorithm of a 2-dimension 3⨯3 mesh topology network-on-chip" 2009 WRI Global Congress on Intelligent Systems vol. 3 pp. 329-333 2009.
S. Tosun "New heuristic algorithms for energy aware application mapping and routing on mesh-based nocs" Journal of Systems Architecture vol. 57 no. 1 pp. 69-78 2011.
J. Gomes Filho M. Strum and W. J. Chau "Using genetic algorithms for hardware core placement and mapping in noc-based reconfigurable systems" International Journal of Reconfigurable Computing vol. 2015 2015.
M. Zang Q. Ye and H. Liu "Energy and thermal aware mapping for noc using non-dominated sorting genetic algorithm ii" Journal of Information & Computational Science vol. 12 no. 1 pp. 201-209 2015.
A. S. Pillai K. Singh V. Saravanan A. Anpalagan I. Woungang and L. Barolli "A genetic algorithm-based method for optimizing the energy consumption and performance of multiprocessor systems" Soft Computing vol. 22 no. 10 pp. 3271-3285 2018.
J. V. Bruch E. A. Da Silva C. A. Zeferino and L. S. Indrusiak "Deadline energy and buffer-aware task mapping optimization in noc-based socs using genetic algorithms" 2017 VII Brazilian Symposium on Computing Systems Engineering (SBESC) pp. 86-93 2017.
V. A. Palaniveloo J. A. Ambrose and A. Sowmya "Improving ga-based noc mapping algorithms using a formal model" 2014 IEEE Computer Society Annual Symposium on VLSI pp. 344-349 2014.
M. R. Bussieck and S. Vigerske "Minlp solver software" Wiley encyclopedia of operations research and management science 2010.
E. B. Van Der Tol and E. G. Jaspers "Mapping of mpeg-4 decoding on a flexible architecture platform" Media Processors 2002 vol. 4674 pp. 1-13 2001.
S. Murali and G. De Micheli "Bandwidth-constrained mapping of cores onto noc architectures" Proceedings design automation and test in Europe conference and exhibition vol. 2 pp. 896-901 2004.
D. Bertozzi A. Jalabert S. Murali R. Tamhankar S. Stergiou L. Benini et al. "Noc synthesis flow for customized domain specific multiprocessor systems-on-chip" IEEE transactions on parallel and distributed systems vol. 16 no. 2 pp. 113-129 2005.
C. A. Marcon J. C. Palma N. L. Calazans F. G. Moraes A. A. Susin and R. Reis "Modeling the traffic effect for the application cores mapping problem onto nocs" in Vlsi-Soc: From Systems To Silicon Springer pp. 179-194 2007.
A. Jalabert S. Murali L. Benini and G. De Micheli "xpipescompiler: A tool for instantiating application-specific networks on chip" in Design Automation and Test in Europe Springer pp. 157-171 2008.
V. Catania A. Mineo S. Monteleone M. Palesi and D. Patti "Noxim: An open extensible and cycle-accurate network on chip simulator" 2015 IEEE 26th international conference on application-specific systems architectures and processors (ASAP) pp. 162-163 2015.
M. López-Ibáñez J. Dubois-Lacoste L. P. Cáceres M. Birattari and T. Stützle "The irace package: Iterated racing for automatic algorithm configuration" Operations Research Perspectives vol. 3 pp. 43-58 2016.
S. D. Chawade M. A. Gaikwad and R. M. Patrikar "Review of xy routing algorithm for network-on-chip architecture" International Journal of Computer Applications vol. 43 no. 21 pp. 975-8887 2012.
W. Wolf A. A. Jerraya and G. Martin "Multiprocessor system-on-chip (mpsoc) technology" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems vol. 27 no. 10 pp. 1701-1713 2008.
N. E. Jerger T. Krishna and L.-S. Peh "On-chip networks" Synthesis Lectures on Computer Architecture vol. 12 no. 3 pp. 1-210 2017.
L. Benini and G. De Micheli "Networks on chips: A new soc paradigm" Computer-IEEE Computer Society- vol. 35 no. EPFL-ARTICLE-165542 pp. 70-78 2002.
A. Agarwal C. Iskander and R. Shankar "Survey of network on chip (noc) architectures & contributions" Journal of engineering Computing and Architecture vol. 3 no. 1 pp. 21-27 2009.
S. Tosun O. Ozturk E. Ozkan and M. Ozen "Application mapping algorithms for mesh-based network-on-chip architectures" The Journal of Supercomputing vol. 71 no. 3 pp. 995-1017 2015.
M. R. Garey and D. S. Johnson Computers and intractability New York:wh freeman vol. 29 2002.
X. Wang H. Liu Z. Yu and K. Shen "A novel two-phase heuristic for application mapping onto mesh-based network-on-chip" iEICE Electronics Express 2016.
W. Zhang L. Hou J. Wang S. Geng and W. Wu "Comparison research between xy and odd-even routing algorithm of a 2-dimension 3⨯3 mesh topology network-on-chip" 2009 WRI Global Congress on Intelligent Systems vol. 3 pp. 329-333 2009.
S. Tosun "New heuristic algorithms for energy aware application mapping and routing on mesh-based nocs" Journal of Systems Architecture vol. 57 no. 1 pp. 69-78 2011.
J. Gomes Filho M. Strum and W. J. Chau "Using genetic algorithms for hardware core placement and mapping in noc-based reconfigurable systems" International Journal of Reconfigurable Computing vol. 2015 2015.
M. Zang Q. Ye and H. Liu "Energy and thermal aware mapping for noc using non-dominated sorting genetic algorithm ii" Journal of Information & Computational Science vol. 12 no. 1 pp. 201-209 2015.
A. S. Pillai K. Singh V. Saravanan A. Anpalagan I. Woungang and L. Barolli "A genetic algorithm-based method for optimizing the energy consumption and performance of multiprocessor systems" Soft Computing vol. 22 no. 10 pp. 3271-3285 2018.
J. V. Bruch E. A. Da Silva C. A. Zeferino and L. S. Indrusiak "Deadline energy and buffer-aware task mapping optimization in noc-based socs using genetic algorithms" 2017 VII Brazilian Symposium on Computing Systems Engineering (SBESC) pp. 86-93 2017.
V. A. Palaniveloo J. A. Ambrose and A. Sowmya "Improving ga-based noc mapping algorithms using a formal model" 2014 IEEE Computer Society Annual Symposium on VLSI pp. 344-349 2014.
M. R. Bussieck and S. Vigerske "Minlp solver software" Wiley encyclopedia of operations research and management science 2010.
E. B. Van Der Tol and E. G. Jaspers "Mapping of mpeg-4 decoding on a flexible architecture platform" Media Processors 2002 vol. 4674 pp. 1-13 2001.
S. Murali and G. De Micheli "Bandwidth-constrained mapping of cores onto noc architectures" Proceedings design automation and test in Europe conference and exhibition vol. 2 pp. 896-901 2004.
D. Bertozzi A. Jalabert S. Murali R. Tamhankar S. Stergiou L. Benini et al. "Noc synthesis flow for customized domain specific multiprocessor systems-on-chip" IEEE transactions on parallel and distributed systems vol. 16 no. 2 pp. 113-129 2005.
C. A. Marcon J. C. Palma N. L. Calazans F. G. Moraes A. A. Susin and R. Reis "Modeling the traffic effect for the application cores mapping problem onto nocs" in Vlsi-Soc: From Systems To Silicon Springer pp. 179-194 2007.
A. Jalabert S. Murali L. Benini and G. De Micheli "xpipescompiler: A tool for instantiating application-specific networks on chip" in Design Automation and Test in Europe Springer pp. 157-171 2008.
V. Catania A. Mineo S. Monteleone M. Palesi and D. Patti "Noxim: An open extensible and cycle-accurate network on chip simulator" 2015 IEEE 26th international conference on application-specific systems architectures and processors (ASAP) pp. 162-163 2015.
M. López-Ibáñez J. Dubois-Lacoste L. P. Cáceres M. Birattari and T. Stützle "The irace package: Iterated racing for automatic algorithm configuration" Operations Research Perspectives vol. 3 pp. 43-58 2016.
S. D. Chawade M. A. Gaikwad and R. M. Patrikar "Review of xy routing algorithm for network-on-chip architecture" International Journal of Computer Applications vol. 43 no. 21 pp. 975-8887 2012.
Publicado
23/11/2020
Como Citar
ROCHA, Hiago; BECK, Antonio Carlos; MAIA, Sílvia; KREUTZ, Márcio; PEREIRA, Monica.
A Routing based Genetic Algorithm for Task Mapping on MPSoC. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SISTEMAS COMPUTACIONAIS (SBESC), 10. , 2020, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 103-110.
ISSN 2237-5430.
