
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.contributor | Hexsel, Roberto, 1960- | - |
| Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
| Autor(es): dc.creator | Farias, Denilson Atilio Godry | - |
| Data de aceite: dc.date.accessioned | 2025-09-01T12:34:44Z | - |
| Data de disponibilização: dc.date.available | 2025-09-01T12:34:44Z | - |
| Data de envio: dc.date.issued | 2024-10-21 | - |
| Data de envio: dc.date.issued | 2024-10-21 | - |
| Data de envio: dc.date.issued | 2000 | - |
| Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/25089 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/25089 | - |
| Descrição: dc.description | Orientador: Roberto A. Hexsel | - |
| Descrição: dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática | - |
| Descrição: dc.description | Resumo: 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. | - |
| Descrição: dc.description | Abstract: This work presents a parallel implementation employing the Branch-and-Bound technique for solving combinatorial optimization problems, specifically search in graphs. The implementation is based on message passing, using the Parallel Virtual Machine (PVM) library on top of the Linux operational system on a network of PCs. The behaviour of this implementations of Branch-and-Bound is analyzed,whith emphasis on the relationships between (a) three graph search strategies, (b) memory resources utilization, (c) granularity (computation versus communication). The implementation consists of a master and slave processes. The master process is responsible for allocation of work amongst the slaves, and the slave processes for performing the graph search and communicating the parcial results to the master. We present experimental data of several runs of the program on the network of PCs, and analyse the performance of the implementation. We also discuss several issues related to the global performance attained, and on the use of the PVM library in this architecture. Our implementation achieved up to 98% of eficiency in some of the experiments performed. | - |
| Formato: dc.format | 99 f. : tabs. ; 30cm. | - |
| Formato: dc.format | application/pdf | - |
| Formato: dc.format | application/pdf | - |
| Relação: dc.relation | Disponível em formato digital | - |
| Palavras-chave: dc.subject | Otimização combinatoria | - |
| Palavras-chave: dc.subject | Processamento paralelo (Computadores) | - |
| Palavras-chave: dc.subject | Ciência da Computação | - |
| Título: dc.title | Paralelização da Técnica Branch and Bound com PVM | - |
| Tipo de arquivo: dc.type | livro digital | - |
| Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: