Particionador paralelo de grafos utilizando algoritmos heurísticos para aplicação em simuladores paralelos de reservatórios de petróleo

Página do item simplificado
dc.contributor.advisor1Silva, Roney Pignaton da
dc.contributor.authorSilva, Leonardo Rogério Binda da
dc.contributor.referee1Lorenzoni, Luciano Lessa
dc.contributor.referee2Celeste, Wanderley Cardoso
dc.date.accessioned2016-08-29T15:39:01Z
dc.date.available2016-07-11
dc.date.available2016-08-29T15:39:01Z
dc.date.issued2014-03-14
dc.description.abstractOil is currently the most widely fuel used in the world. To obtain it to the greatest possible economic viability is a relentless pursuit of the producing companies. In this scenario, the numerical reservoir simulation using parallel computers with distributed memory (clusters) is emerging as an important tool. These application handle mashes of discrete points that represent the field of oil reservoir. An important step of the simulation using clusters is the partitioning of this mesh points so that each cluster process node can perform its calculations on a portion of this mesh. The domain meshes can be represented by graphs. Partitioning meshes then becomes a problem of graph partitioning. If the graph vertices number that represents the mesh is very high, serial partitioners can have performance problems. Graph partitioners using clusters appear as interesting alternatives in this situation, minimizing the time spent in partitioning. This research deals with the implementation of a parallel graph partitioner to be used in clusters based on partitioning heurists proposed and implemented serially by Bonatto (2010). The parallel partitioner has been developed using the Java programming language and MPJ Express messages passing library. Efficient abstract data types have been proposed and implemented in order to optimize the performance. The parallel graph partitioner performed the cutting of different graphs, obtaining, most of the time, smaller cuts than the ones found by serial partitioner of Bonatto (2010) and by programs such as METIS and CHACO. Improvements to the Bonatto (2010) serial partitioner have been proposed. Analysis of speedup and parallel efficiency have been performed to find out the gains of times abtained with the parallelization of the heuristics.
dc.description.resumoO petróleo é atualmente o combustível mais utilizado no mundo. Recuperá-lo com a maior viabilidade econômica possível é uma busca incessante das companhias produtoras. Nesse cenário, a simulação numérica de reservatórios utilizando computadores paralelos de memória distribuída (clusters) desponta como uma importante ferramenta. Esses aplicativos manipulam malhas de pontos discretizados que representam o domínio do reservatório de petróleo. Uma etapa importante da simulação utilizando clusters é o particionamento dessa malha para que cada um dos nós processadores possa executar seus cálculos sobre uma porção da mesma. As malhas de domínio podem ser representadas por grafos. Particionar malhas, então, torna-se um problema de particionamento de grafos. Caso o número de vértices do grafo que representa a malha seja muito elevado, particionadores seriais podem apresentar problemas de desempenho. Particionadores de grafos utilizando clusters surgem como alternativas interessantes nessa situação, minimizando os tempos gastos nos particionamentos. Trata da implementação de um particionador paralelo de grafos para ser utilizado em clusters baseado nas Heurísticas de particionamento propostas e implementadas de maneira serial por Bonatto (2010). O particionador paralelo foi desenvolvido utilizando a linguagem de programação Java e a biblioteca de passagem de mensagens MPJ Express. Tipos abstratos de dados eficientes foram propostos e implementados para que o desempenho fosse otimizado. O particionador de grafos paralelo realizou o corte de diversos grafos, obtendo em sua grande maioria cortes menores do que os encontrados pelo particionador serial de Bonatto (2010) e por programas como o METIS e o CHACO. Melhorias ao particionador serial de Bonatto (2010) foram propostas. Análises de speedup e eficiência paralela foram realizadas para constatar os ganhos de tempos obtidos com a paralelização das heurísticas.
dc.formatText
dc.identifier.citationSILVA, Leonardo Rogério Binda da. Particionador paralelo de grafos utilizando algoritmos heurísticos para aplicação em simuladores paralelos de reservatórios de petróleo. 2017. 171 f. Dissertação (Mestrado em Energia) - Programa de Pós-Graduação em Energia, Universidade Federal do Espírito Santo, São Mateus, 2014.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/5337
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Energia
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Energia
dc.rightsopen access
dc.subjectPetroleum engineeringeng
dc.subjectGraphs partitioningeng
dc.subjectHeuristicseng
dc.subjectParallel computingeng
dc.subjectReservoir simulationeng
dc.subjectClusters of Computereng
dc.subjectParticionamento de grafospor
dc.subjectComputação paralelapor
dc.subjectSimulação de reservatóriospor
dc.subjectClusters de computadorespor
dc.subject.br-rjbnEngenharia de petróleo
dc.subject.br-rjbnRepresentações dos grafos
dc.subject.br-rjbnHeurística
dc.subject.br-rjbnProgramação paralela (Computação)
dc.subject.cnpqEngenharia/Tecnologia/Gestão
dc.subject.udc620.9
dc.titleParticionador paralelo de grafos utilizando algoritmos heurísticos para aplicação em simuladores paralelos de reservatórios de petróleo
dc.typemasterThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
tese_7557_Leonardo Rogério Binda da Silva.pdf
Tamanho:
4 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Energia