MigBSP++: balanceamento de carga eficiente para aplicações paralelas em fases

A migração de processos é uma técnica utilizada no remapeamento de um processo para um processador mais rápido ou para aproximá-lo de outros processos com os quais se comunica frequentemente. Esta dissertação descreve o MigBSP++, um modelo de reescalonamento de processos que utiliza a técnica de migração para realizar o balanceamento de carga em sistemas paralelos. Direcionado às aplicações do tipo Bulk-Synchronous Parallel (BSP), o modelo apresentado redistribui os processos com o intuito de reduzir o tempo de cada super-passo. De modo similar ao MigBSP, o MigBSP++ combina múltiplas métricas a fim de decidir as migrações necessárias para que o sistema entre em equilíbrio sem a intervenção do usuário. As métricas utilizadas são: computação, comunicação e sobrecusto de migração. Através de sua função de decisão, chamada Potencial de Migração (PM), essas métricas são utilizadas para eleger os processos mais propícios a trazer o equilíbrio ao sistema. O MigBSP++ responde as questões necessárias para a política de migração de processos: quando realizar a migração de processos; quais processos são candidatos à migração e; para onde migrar os processos selecionados. Como contribuição científica, o MigBSP++ introduz as soluções para duas questões que estão em aberto no MigBSP: (a) a detecção de desbalanceamento de carga quando há mais processos do que processadores e; (b) a definição de quantos processos irão migrar de fato. Para a questão (a), propõe-se alteração do modo de detecção de desbalanceamento utilizada, observando o tempo total de computação de cada processador. Para a questão (b) é apresentado um algoritmo chamado de Algoritmo de Predição BSP (APBSP). Os dados de entrada do APBSP são os processos eleitos pela técnica de PM e a saída é uma lista de processos que irão, de fato, migrar proporcionando a redução do tempo do próximo super-passo. Para demonstrar os resultados da aplicação deste modelo, foram desenvolvidas duas aplicações BSP com o auxílio da biblioteca Adaptive Message Passing Interface (AMPI). Essa ferramenta oferece um arcabouço uniforme que, através da migração de processos, permite o balanceamento de carga de forma transparente ao usuário. Foram desenvolvidas as estratégias de balanceamento de carga, baseadas no MigBSP e no MigBSP++, para a realização da comparação entre elas e com as estratégias já existentes no sistema. Os resultados apontam que, nos casos onde a granularidade da tarefa é maior, os ganhos em tempo de execução são mais evidentes, podendo ser de até 46% em relação à aplicação sem balanceamento e de até 37% em relação às estratégias nativas do AMPI. Esses números sugerem que o modelo MigBSP++ tem aplicação prática e pode produzir resultados satisfatórios.