A Greedy Heuristic for Process Mapping on Networks-on-Chip
Resumo
The state-of-the-art related to many-core processors focuses on Networks-on-Chip (NoCs) as approach to provide on-chip message-passing communication. The main problem is the number of hops from source to destination increasing the latency to exchange data based on network packets. Our goal is to propose a greedy heuristic for process mapping on NoCs clustering processes that have more communication on nearest cores. The evaluation method is based on simulation of parallel workloads on a NoC. The greedy heuristic achieves a higher throughput (up to 23.04%) and lower energy consumption (up to 9.87%) than a direct mapping approach for most workloads.
Referências
G. Ascia, V. Catania, and M. Palesi. Multi-objective mapping for mesh-based noc architectures. In Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, CODES+ISSS '04, pages 182-187, New York, NY, USA, 2004. ACM.
L. Benini and G. D. Micheli. Networks on chips: A new soc paradigm. Computer, 35:70-78, January 2002.
T. Bjerregaard and S. Mahadevan. A survey of research and practices of network-on-chip. ACM Computing Surveys, 38:1-51, June 2006.
S. H. Bokhari. On the mapping problem. IEEE Trans. Comput., 30:207-214, March 1981.
E. Carvalho, N. Calazans, and F. Moraes. Heuristics for dynamic task mapping in noc-based heterogeneous mpsocs. In Proceedings of the 18th IEEE/IFIP International Workshop on Rapid System Prototyping, pages 34-40, Washington, DC, USA, 2007. IEEE Computer Society.
G. Chen, F. Li, S. W. Son, and M. Kandemir. Application mapping for chip multiprocessors. In Proceedings of the 45th annual Design Automation Confe- rence, DAC '08, pages 620-625, New York, NY, USA, 2008. ACM.
C. Chou and R. Marculescu. Contention-aware application mapping for network-on-chip communication architectures. IEEE International Conference on Computer Design, 0:164-169, 2008.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, New York, 2001.
E. H. Cruz, M. A. Alves, and P. O. A. Navaux. Process mapping based on memory access traces. Symposium on Computing Systems, 0:72-79, 2010.
H. C. Freitas. Arquitetura de noc programável baseada em múltiplos clusters de cores para suporte a padrões de comunicação coletiva. Master's thesis, Universidade Federal do Rio Grande do Sul, 2009.
H. C. Freitas, L. M. Schnorr, M. A. Z. Alves, and P. O. A. Navaux. Impact of parallel workloads on noc architecture design. In Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, PDP '10, pages 551- 555, Washington, DC, USA, 2010. IEEE Computer Society.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the sixth annual ACM symposium on Theory of computing, STOC '74, pages 172-184, New York, NY, USA, 1974. ACM.
J. Hu and R. Marculescu. Energy-aware mapping for tile-based noc architectures under performance constraints. In Proceedings of the 2003 Asia and South Pacic Design Automation Conference, ASP-DAC '03, pages 233-239, New York, NY, USA, 2003. ACM.
Intel. Tera ops research chip. Disponível em http://techresearch.intel.com/ProjectDetails.aspx?Id=151, 2011.
N. A. G. Júnior. Análise e simulação de topologias de redes em chip. Master's thesis, Universidade Estadual de Maringá, 2010.
J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2005.
S.-H. Lee, Y.-C. Yoon, and S.-Y. Hwang. Communication-aware task assignment algorithm for mpsoc using shared memory. J. Syst. Archit., 56:233-241, July 2010.
C. Marcon, N. Calazans, F. Moraes, A. Susin, I. Reis, and F. Hessel. Exploring noc mapping strategies: An energy and timing aware technique. In Proceedings of the conference on Design, Automation and Test in Europe - Volume 1, DATE '05, pages 502-507, Washington, DC, USA, 2005. IEEE Computer Society.
Noxim. Noxim the noc simulator. Disponível em http://noxim.sourceforge.net/, 2011.
NPB. Nas parallel benchmarks. Disponível em http://www.nas.nasa.gov/Resources/Software/npb.html, 2011.
R. Tornero, J. M. Orduña, M. Palesi, and J. Duato. A communication-aware topological mapping technique for nocs. In Proceedings of the 14th international Euro-Par conference on Parallel Processing, Euro-Par '08, pages 910-919, Berlin, Heidelberg, 2008. Springer-Verlag.
L. Benini and G. D. Micheli. Networks on chips: A new soc paradigm. Computer, 35:70-78, January 2002.
T. Bjerregaard and S. Mahadevan. A survey of research and practices of network-on-chip. ACM Computing Surveys, 38:1-51, June 2006.
S. H. Bokhari. On the mapping problem. IEEE Trans. Comput., 30:207-214, March 1981.
E. Carvalho, N. Calazans, and F. Moraes. Heuristics for dynamic task mapping in noc-based heterogeneous mpsocs. In Proceedings of the 18th IEEE/IFIP International Workshop on Rapid System Prototyping, pages 34-40, Washington, DC, USA, 2007. IEEE Computer Society.
G. Chen, F. Li, S. W. Son, and M. Kandemir. Application mapping for chip multiprocessors. In Proceedings of the 45th annual Design Automation Confe- rence, DAC '08, pages 620-625, New York, NY, USA, 2008. ACM.
C. Chou and R. Marculescu. Contention-aware application mapping for network-on-chip communication architectures. IEEE International Conference on Computer Design, 0:164-169, 2008.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, New York, 2001.
E. H. Cruz, M. A. Alves, and P. O. A. Navaux. Process mapping based on memory access traces. Symposium on Computing Systems, 0:72-79, 2010.
H. C. Freitas. Arquitetura de noc programável baseada em múltiplos clusters de cores para suporte a padrões de comunicação coletiva. Master's thesis, Universidade Federal do Rio Grande do Sul, 2009.
H. C. Freitas, L. M. Schnorr, M. A. Z. Alves, and P. O. A. Navaux. Impact of parallel workloads on noc architecture design. In Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, PDP '10, pages 551- 555, Washington, DC, USA, 2010. IEEE Computer Society.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the sixth annual ACM symposium on Theory of computing, STOC '74, pages 172-184, New York, NY, USA, 1974. ACM.
J. Hu and R. Marculescu. Energy-aware mapping for tile-based noc architectures under performance constraints. In Proceedings of the 2003 Asia and South Pacic Design Automation Conference, ASP-DAC '03, pages 233-239, New York, NY, USA, 2003. ACM.
Intel. Tera ops research chip. Disponível em http://techresearch.intel.com/ProjectDetails.aspx?Id=151, 2011.
N. A. G. Júnior. Análise e simulação de topologias de redes em chip. Master's thesis, Universidade Estadual de Maringá, 2010.
J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2005.
S.-H. Lee, Y.-C. Yoon, and S.-Y. Hwang. Communication-aware task assignment algorithm for mpsoc using shared memory. J. Syst. Archit., 56:233-241, July 2010.
C. Marcon, N. Calazans, F. Moraes, A. Susin, I. Reis, and F. Hessel. Exploring noc mapping strategies: An energy and timing aware technique. In Proceedings of the conference on Design, Automation and Test in Europe - Volume 1, DATE '05, pages 502-507, Washington, DC, USA, 2005. IEEE Computer Society.
Noxim. Noxim the noc simulator. Disponível em http://noxim.sourceforge.net/, 2011.
NPB. Nas parallel benchmarks. Disponível em http://www.nas.nasa.gov/Resources/Software/npb.html, 2011.
R. Tornero, J. M. Orduña, M. Palesi, and J. Duato. A communication-aware topological mapping technique for nocs. In Proceedings of the 14th international Euro-Par conference on Parallel Processing, Euro-Par '08, pages 910-919, Berlin, Heidelberg, 2008. Springer-Verlag.
Publicado
26/10/2011
Como Citar
OLIVEIRA, Poliana A. C.; AVELAR, Cíntia P.; GUIMARÃES, Silvio Jamil F.; FREITAS, Henrique C..
A Greedy Heuristic for Process Mapping on Networks-on-Chip. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 12. , 2011, Vitória.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 25-32.
DOI: https://doi.org/10.5753/wscad.2011.17264.
