Show simple item record

dc.contributor.advisorHexsel, Roberto Apt_BR
dc.contributor.authorFarias, Denilson Atilio Godrypt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Ciencias Exatas. Programa de Pós-Graduaçao em Informáticapt_BR
dc.date.accessioned2011-02-07T18:12:48Z
dc.date.available2011-02-07T18:12:48Z
dc.date.issued2011-02-07
dc.identifier.urihttp://hdl.handle.net/1884/25089
dc.description.abstractResumo: Este trabalho aborda a implementação paralela da técnica Branch-and-Bound em problemas de otimização combinatoria, especificamente busca em grafos. E utilizado na implementação o modelo de programação paralela por troca de mensagens com o uso da biblioteca Parallel Virtual Machine (PVM) sobre o sistema operacional Linux em uma arquitetura multicomputador. E analisado o comportamento da técnica Branch-and-Bound, em particular a relação entre (a) três critérios de busca, (b) a utilização dos recursos de memória e (c) granularidade de, processamento e comunicação entre processos. E proposto um esquema de implementação com processos mestre-escravos semi-distribuído, onde o processo mestre é responsável pela distribuição de tarefas e os processos escravos pela disseminação de resultados parciais no sistema. Resultados experimentais dessa implementação são exibidos e analisados, assim como algumas características relevantes ao desempenho global encontradas no uso da biblioteca PVM para esta arquitetura. De um modo geral obtivemos em média para os problemas investigados uma eficiência da execução paralela da ordem de 98% em comparação à execução serial.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.subjectTesespt_BR
dc.subjectOtimização combinatoriapt_BR
dc.subjectProcessamento paralelo (Computadores)pt_BR
dc.titleParalelização da Técnica Branch and Bound com PVMpt_BR
dc.typeDissertaçãopt_BR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record