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

Autores

  • Roney P. da Silva Universidade Federal do ES
  • Leonardo Rogerio Binda da Silva

DOI:

https://doi.org/10.21712/lajer.2014.v1.n1.p91-100

Resumo

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

Não há dados estatísticos.

Biografia do Autor

Roney P. da Silva, Universidade Federal do ES

Departamento de Computação e Eletrônica

Engenharia de Sistemas Telemáticos

Leonardo Rogerio Binda da Silva

Faculdade de Colatina

Ciencia da Computação

Downloads

Publicado

2021-02-05

Edição

Seção

Artigos