Publicado em: 29/03/2010

Dissertação de Mestrado em Sistemas de Computação

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

Aluno: Stéfano Drimon Kurz Mór
Orientador: Prof. Dr. Nicolas Bruno Maillard

Titulo: Escalonamento On-line Eficiente de Programas Fork-Join Recursivos do Tipo Divisão e Conquista em MPI
Área de Pesquisa: Sistemas de Computação

Data: 30/03/2010
Hora: 10h30min
Local: Auditório Prof. José Volkmer de Castilho (Verde), Prédio 43424

Banca Examinadora:
Prof. Dr. Philippe Olivier Alexandre Navaux (UFRGS)
Prof. Dr. Cláudio Fernando Resin Geyer (UFRGS)
Prof. Dr. Maurício Lima Pilla (UFPEL)

Presidente da Banca: Prof. Dr. Nicolas Bruno Maillard

Resumo:
Esta Dissertação de Mestrado propõe dois novos algoritmos para tornar mais eficiente o      escalonamento on-line de tarefas com dependências estritas em agregados de computadores que usam como middleware para troca de mensagens alguma implementação da MPI (até a versão 2.1). Esses algoritmos foram projetados tendo-se em vista programas construídos no modelo de programação fork /  join, onde a operação de fork é usada sobre uma chamada recursiva da função. São eles:
1.  O algoritmo RatMD, implementado através de uma biblioteca de primitivas do tipo   map-reduce , que funciona para qualquer implementação MPI, com qualquer versão da norma. Utilizado para minimizar o tempo de execução de uma computação paralela; e
2. O algoritmo RtMPD, implementado através de um sistema distribuído sobre   daemons  gerenciadores de processos criados dinamicamente com a implementação MPICH2 (que implementa a MPI-2). Utilizado para permitir execuções de instâncias maiores de programas paralelos dinâmicos.
Ambos se baseiam em roubo de tarefas, que é a estratégia de balanceamento de carga mais difundida na literatura. Para ambos os algoritmos apresenta-se modelagem téorica de custos. Resultados experimentais obtidos ficam dentro dos limites teóricos calculados. RatMD  provê uma redução no tempo de execução de até 80% em relação ao algoritmo usual (baseado em round-robin), com manutenção do speedup próximo ao linear e complexidade espacial idêntica à popular implementação com round-robin .   RtMPD  mantém, no mínimo, o mesmo desempenho que a implementação canônica do escalonamento em MPICH2, dobrando-se o limite físico de processos executados simultaneamente por cada nó.

Palavras-Chave: MPI-2, Escalonamento, Tarefas, Dinamismo