Uma estratégia de implementação paralela eficiente de uma heurísticas de particionamento de grafos aplicado à simulação de escoamento multifásico

Abstract

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.