Publicado em: 09/08/2012

Dissertação de Mestrado em Processamento Paralelo e Distribuído

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————————
DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluna: Manuela Klanovicz Ferreira
Orientador: Prof. Dr. Philippe Olivier Alexandre Navaux

Título: Mapeamento Estático de Processos MPI com Emparelhamento Perfeito de Custo Máximo em Cluster Homogêneo de Multi-cores
Linha de Pesquisa: Processamento Paralelo e Distribuído

Data: 14/08/2012
Hora: 13h30min
Local: Auditório José Mauro Volkmer de Castilho, Prédio 43424 – Instituto de Informática

Banca Examinadora:
Prof. Dr. Adenauer Correa Yamim (UFPEL)
Prof. Dr. Alexandre da Silva Carissimi (UFRGS)
Prof. Dr. Cláudio Fernando Resin Geyer (UFRGS)

Presidente da Banca: Prof. Dr. Philippe Olivier Alexandre Navaux

Resumo:
Um importante fator que precisa ser considerado para alcançar alta performance 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 com dois processadores por nó e quatro núcleos por processador.

Palavras-Chave: Mapeamento de processos, MPI, Multi-core, Comunicação entre processos, Emparelhamento perfeito de custo máximo.