Uma estratégia de implementação paralela eficiente de uma heurísticas de particionamento de grafos aplicado à simulação de escoamento multifásico
DOI:
https://doi.org/10.21712/lajer.2014.v1.n1.p91-100Resumo
O Problema de Particionamento de Grafos (PPG) possui várias aplicações em diferentes áreas, tal como no projeto de circuitos VLSI (Very-large-scale integration), resolução de métodos numéricos para simulação de problemas que incluem fatoração de matrizes esparsas e particionamento de malhas de elementos finitos para aplicação de programação paralela. Entre suas aplicações, o foco deste trabalho é o desenvolvimento de uma solução paralela para esse problema aplicado à simulação de fluxo multifásico em meios porosos para recuperação de petróleo. Como resultado, as partições criadas permitem particionar o espaço discretizado de maneira que os mesmos seja simulados em paralelo. O PPG tende a ser NP-difícil e soluções ótimas para o problema são impossíveis quando o número de vértices do grafo é muito grande. Muitas heuristicas e metaheurística já foram propostos e usados para resolver o PPG com o objetivo de alcançar bons resultados, uma vez que resultados garantidamente ótimos não são obtidos na prática. Este trabalho propõe uma solução paralela eficiente para o PPG baseado na implementação de heurísticas existentes em uma plataforma computacional paralela do tipo Cluster. A solução proposta melhora o tempo de execução do algoritmo e, através da introdução de algumas características de aleatoriedade na heurística original, melhora a qualidade das partições criadas.
Downloads
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2016 Latin American Journal of Energy Research
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
O autor, no ato da submissão do artigo, transfere o direito autoral ao periódico.