Melhorando o Desempenho de Algoritmos do Tipo Branch & Bound em MPI via Escalonador com Roubo Aleatório de Tarefas - Mór, Stéfano D. K.; Maillard, Nicolas (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2009: Anais do X Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2009.17387, 2009)
Nossa principal contribuição é a integração de um modelo de escalonamento distribuído por roubo de tarefas para computação em MPI capaz de otimizar o desempenho de programas do tipo Branch & Bound. Esse escalonador é introduzido em tempo de compilação e é independente da distribuição MPI usada. Resultados experimentais mostram que se pode obter um ganho de até 80% no desempenho, mantendo o speedup próximo ao linear e sem a perda do consumo linear de memória. Esses ganhos se confirmam mesmo em um ambiente de processadores homogêneos, que tendem a produzir um menor desbalanceamento da carga de trabalho.