BDBComp
Parceria:
SBC
Dequeues auto balanceaveis para algoritmos branch and bound em MPI-1

Stéfano D K MorNicolas Bruno Maillard

A Message-Passing Interface (MPI) ´e o padr~ao em computac¸ ~ao paralela com troca demensagens. Por quest~oes de portabilidade, MPI n~ao prov^e uma maneira eficiente dedistribuic¸ ~ao de carga de trabalho gerada em tempo de execuc¸ ~ao aos computadores participantes.Isso ´e um problema, em especial, quando se consideram algoritmos do tipobranch and bound (B&B), que podem produzir, intrinsecamente, grande desbalanceamentode carga de trabalho entre os recursos dispon´ýveis.Prop~oe-se, ent~ao, uma biblioteca sobre MPI-1 que possa oferecer suporte a criacaoe escalonamento eficiente de tarefas criadas dinamicamente em algoritmos B&B. O nomedessa biblioteca e RAWSDM (Randomized Work-Stealing for Distributed Memory).Algoritmos paralelos que executam em forma de arvore - como B&B - n~ao s~aonovos. Uma das primeiras contribuicoes sobre o assunto e vista em [Wu e Kung 1991],que apresenta a analise dos limites assintoticos inferiores no escalonamento de nosda arvore em P processadores (totalmente) interconectados.

http://www.lbd.dcc.ufmg.br/colecoes/erad-rs/2011/0049.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD