Repositório Digital

A- A A+

Mapeamento estático de processos MPI com emparelhamento perfeito de custo máximo em cluster homogêneo de multi-cores

.

Mapeamento estático de processos MPI com emparelhamento perfeito de custo máximo em cluster homogêneo de multi-cores

Mostrar registro completo

Estatísticas

Título Mapeamento estático de processos MPI com emparelhamento perfeito de custo máximo em cluster homogêneo de multi-cores
Outro título Static MPI processes mapping using maximum weighted perfect matching at homogeneous multi-core clusters
Autor Ferreira, Manuela Klanovicz
Orientador Navaux, Philippe Olivier Alexandre
Data 2012
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Mpi
Processamento paralelo
[en] Maximum weighted perfect matching
[en] MPI
[en] Multicore
[en] Processes’ communication
[en] Process mapping
Resumo Um importante fator que precisa ser considerado para alcançar alto desempenho em aplicações paralelas é a distribuição dos processos nos núcleos do sistema, denominada mapeamento de processos. Mesmo o mapeamento estático de processos é um problema NP-difícil. Por esse motivo, são utilizadas heurísticas que dependem da aplicação e do hardware no qual a aplicação será mapeada. Nas arquiteturas atuais, além da possibilidade de haver mais de um processador por nó do cluster, é possível haver mais de um núcleo de processamento por processador, assim, o mapeamento estático de processos pode considerar pelo menos três níveis de comunicação entre os processos que executam em um cluster multi-core: intra-chip, intra-nó e inter-nó. Este trabalho propõe a heurística MapEME (Mapeamento Estático MPI com Emparelhamento) que emprega o Emparelhamento Perfeito de Custo Máximo (EPCM) no cálculo do mapeamento estático de processos paralelos MPI em processadores multi-core. Os resultados alcançados pelo mapeamento gerado pela MapEME são comparados aos resultados obtidos pelo mapeamento gerado pela aplicação Scotch, que utiliza o Biparticionamento Recursivo Dual (BRD), já utilizado como heurística para mapeamento estático de processos. Ambas as heurísticas são comparadas à Busca Exaustiva (BE) para verificar o quanto estão próximas do ótimo. Os três métodos têm a complexidade e o ganho no tempo de execução em ralação à distribuição padrão da biblioteca MPICH2 comparados entre si. A principal contribuição deste trabalho é mostrar que a heurística EPCM apresenta ganho de até 40% equivalente a já difundida BRD, e possui uma complexidade menor ao ser aplicado em um cluster multi-core que compartilha cache nível 2 a cada dois núcleos.
Abstract An important factor that must be considered to achieve high performance on parallel applications is the mapping of processes on cores. However, since this is defined as an NP-Hard problem, it requires different mapping heuristics that depends on the application and the hardware on which it will be mapped. On the current architectures we can have more than one multi-core processors per node, and consequently the process mapping can consider three process communication types: intrachip, intranode and internode. This work propose the MapEME (Static Mapping MPI using Matching) that use the Maximum Weighted Perfect Matching (MWPM) to calculate the static process mapping and analyze its performance. The results provided by MapEME are compared with the results of application Scotch. It uses Dual Recursive Bipartitioning (DRB), an already used heuristics for static mapping. Both heuristics are compared with Exhaustive Search (ES) to verify how much the two heuristics are near the optimum. The three methods have theirs complexities analyzed. Also the mapping gain when compared with the standard MPICH2 distribution was measured. The main contribution of this work is to show that the heuristic, EPCM, provides gain up to 40%, close of DRB gain. Furthermore, EPCM has a lower complexity when applied to a multicore cluster that shares L2 cache every two cores.
Tipo Dissertação
URI http://hdl.handle.net/10183/65636
Arquivos Descrição Formato
000870189.pdf (2.596Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.