Algoritmo Kmeans para Mapeamento Estático de Processos em Redes-em-Chip
Resumo
Desempenho é um ponto crucial em arquiteturas many-core com networks-on-chip. Uma das alternativas para alcanç á-lo consiste em mapear processos nos núcleos de processamento de forma a minimizar o custo de comunicação global entre processos. Nesse contexto, esse trabalho propõe o algoritmo Kmeans como uma estratégia alternativa às heurísticas BRD e Guloso. Para determinados padrões de comunicação, os resultados de simulação apontaram que o Kmeans conduz a melhores mapeamentos que as outras estratégias, sendo portanto uma boa opção para o mapeamento de processos em arquiteturas many-core com networks-on-chip.Referências
Abad, P., P.Prieto, L.Menezo, A.Colaso, V.Puente, and Gregorio, J. (2012). Topaz: An open-source interconnection network simulator for chip multiprocessors and supercomputers. NOCS.
Ascia, G., Catania, V., and Palesi, M. (2004). Multi-objective mapping for mesh-based noc architectures. pages 182–187.
Avelar, C., Oliveira, P., Freitas, H., and Navaux, P. (2011). Evaluating the problem of process mapping on network-on-chip for parallel applications. In Workshop on Architecture and Multi-Core Applications (WAMCA), pages 18–23, Vitória, Brazil.
Bertsekas, D. (1988). The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1):105–123.
Binkert, N. (2011). The gem5 simulator. ACM SIGARCH Computer Architecture News, 39.
Bokhari, P. H. (1981). On the mapping problem. IEEE Trans. Comput., pages 207–214.
Carvalho, E. C. and N. Moraes, F. (2007). Heuristics for dynamic task mapping in noc-based heterogeneous mpsocs. Rapid System Prototyping, 2007. RSP 2007. 18th IEEE/IFIP International Workshop on, pages 34–40.
de Oliveira, P. A. C. (2012). Avaliação de desempenho e caracterização de cargas de trabalho paralelas para redes-em-chip sem fio. Dissertação do Programa de Pos-Graduac˜ao em Informática. Pontifícia Universidade Católica de Minas Gerais.
Freitas, H. C., Alves, M. A. Z., and Navaux, P. O. A. (2009). Noc e nuca: Conceitos e tendências para arquiteturas de processadores many core. Minicurso do Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD-SSC).
Oliveira, P., Avelar, C., Guimaraes, S., and Freitas, H. (2011). A greedy heuristic for process mapping on networks-on-chip. In Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD-SSC), pages 1–8, Vitória, Brazil.
Pellegrini, F. (2008). Scotch 5.1: User’s guide. Technical report, LaBRI.
Ascia, G., Catania, V., and Palesi, M. (2004). Multi-objective mapping for mesh-based noc architectures. pages 182–187.
Avelar, C., Oliveira, P., Freitas, H., and Navaux, P. (2011). Evaluating the problem of process mapping on network-on-chip for parallel applications. In Workshop on Architecture and Multi-Core Applications (WAMCA), pages 18–23, Vitória, Brazil.
Bertsekas, D. (1988). The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1):105–123.
Binkert, N. (2011). The gem5 simulator. ACM SIGARCH Computer Architecture News, 39.
Bokhari, P. H. (1981). On the mapping problem. IEEE Trans. Comput., pages 207–214.
Carvalho, E. C. and N. Moraes, F. (2007). Heuristics for dynamic task mapping in noc-based heterogeneous mpsocs. Rapid System Prototyping, 2007. RSP 2007. 18th IEEE/IFIP International Workshop on, pages 34–40.
de Oliveira, P. A. C. (2012). Avaliação de desempenho e caracterização de cargas de trabalho paralelas para redes-em-chip sem fio. Dissertação do Programa de Pos-Graduac˜ao em Informática. Pontifícia Universidade Católica de Minas Gerais.
Freitas, H. C., Alves, M. A. Z., and Navaux, P. O. A. (2009). Noc e nuca: Conceitos e tendências para arquiteturas de processadores many core. Minicurso do Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD-SSC).
Oliveira, P., Avelar, C., Guimaraes, S., and Freitas, H. (2011). A greedy heuristic for process mapping on networks-on-chip. In Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD-SSC), pages 1–8, Vitória, Brazil.
Pellegrini, F. (2008). Scotch 5.1: User’s guide. Technical report, LaBRI.
Publicado
08/10/2014
Como Citar
AVELAR, Cíntia; PENNA, Pedro; FREITAS, Henrique.
Algoritmo Kmeans para Mapeamento Estático de Processos em Redes-em-Chip. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 15. , 2014, São José dos Campos.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 204-215.
DOI: https://doi.org/10.5753/wscad.2014.15012.
