Implementações de Algoritmos Paralelos FPT para o Problema da k-Cobertura por Vértices utilizando Clusters e Grades Computacionais
Resumo
Em muitas aplicações problemas NP-completos precisam ser solucionados de forma exata. Um método promissor para tratar com alguns problemas intratáveis é através da Complexidade Parametrizada que divide a entrada do problema em uma parte principal e um parâmetro. A parte principal contribui polinomialmente com a complexidade total do problema, enquanto que o parâmetro é responsável pela explosão combinatorial. Consideramos o algoritmo paralelo FPT de Cheetham para solucionar o problema da k-Cobertura por Vértices e a implementação refinada e melhorada de Hanashiro. Como este é um problema em que grande parte do tempo de execução é feita de forma independente, sem a necessidade de comunicação entre os processadores, a utilização de grades computacionais torna-se bastante aplicável, com a possibilidade do emprego de um número grande de processadores. Este trabalho envolve a implementação no Integrade de algoritmos FPT paralelos para o problema da k-Cobertura por vértices. A grade computacional dos testes utiliza o middleware desenvolvido no Projeto Integrade. Estes algoritmos foram implementados usando a biblioteca BSPLib do Integrade e mostraram um desempenho muito bom e que pode ser melhorado com a adição de novos processadores. Em nossos experimentos no Integrade, em comparação a implementação em cluster, obtivemos tempos paralelos melhores do que os relatados por Hanashiro.Referências
E. J. Hanashiro. O problema da k-cobertura por Vértices: uma implementação FPT no modelo CGM. Dissertação de Mestrado, Universidade Federal de Mato Grosso do Sul, Março, 2004.
E. J. Hanashiro, H. Mongelli, e S. W. Song. Efficient implementation of the BSP/CGM parallel vertex covert FPT algorithm. In: Third International Workshop on Experimental and Efficient Algorithms - WEA 2004, Angra dos Reis. Lecture Notes in Computer Science. Springer-Verlag. 3059: 253-268, 2004.
J. Cheetham, F. Dehne, A. Rau-Chaplin, U. Stege, e P. J. Taillon. Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences, 67(4):691706, 2003.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, e C. Stein. Algoritmos: Teoria e Prática. Campus, 2002.
R. G. Downey e M. R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM Journal on Computing, 24:873921, 1995.
R. G. Downey e M. R. Fellows. Fixed-parameter tractability and completeness II: completeness for W[1]. Theoretical Computer Science, 141:109131, 1995.
R. G. Downey e M. R. Fellows. Parameterized computational feasibility. In Feasible Mathematics II, páginas 219244. Birkhauser Boston, 1995.
R. G. Downey e M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1998.
R. G. Downey e M. R. Fellows. Parameterized complexity after (almost) 10 years: review and open questions. In Combinatorics, Computation & Logic, DMTCS’99 and CATS’99, volume 21, número 3, páginas 133. Australian Computer Science Communications, Springer-Verlag, 1999.
R. G. Downey, M. R. Fellows, e U. Stege. Computational tractability: the view from Mars. Bulletin of the European Association for Theoretical Computer Science, 69:7397, 1999.
R. G. Downey, M. R. Fellows, e U. Stege. Parameterized complexity: a framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, volume 49 de AMS-DIMACS Proceedings Series, páginas 4999. 1999.
R. Niedermeier. Some prospects for efficient fixed parameter algorithms. In Conference on Current Trends in Theory and Practice of Informatics, páginas 168185. 1998.
J. F. Buss e J. Goldsmith. Nondeterminism within P. SIAM Journal on Computing, 22(3):560572, 1993.
R. Balasubramanian, M. R. Fellows, e V. Raman. An improved fixed-parameter algorithm for vertex cover. Information Processing Letters, 65:163168, 1998.
M. Pitanga. Construindo Supercomputadores com Linux. Brasport. 2004.
A. Goldchleger, F. Kon, A. Goldman, M. Finger, e G. C. Bezerra. InteGrade: Object-Oriented Grid Middleware Leveraging Idle Computing Power of Desktop Machines. 2000. Disponível em <http://gsd.ime.usp.br/publications/cpe03integrade.pdf>. Acesso em 16 de Maio de 2007.
L. G. Valiant. A bridging model for computation. Communications of the ACM, 33:103-111, 1990.
F. Dehne, A. Fabri, e A. Rau-Chaplin. Scalable parallel computational geometry for coarse grained multicomputers. In Proceedings of the ACM 9th Annual Computational Geometry, 298-307, 1993.
E. J. Hanashiro, H. Mongelli, e S. W. Song. Efficient implementation of the BSP/CGM parallel vertex covert FPT algorithm. In: Third International Workshop on Experimental and Efficient Algorithms - WEA 2004, Angra dos Reis. Lecture Notes in Computer Science. Springer-Verlag. 3059: 253-268, 2004.
J. Cheetham, F. Dehne, A. Rau-Chaplin, U. Stege, e P. J. Taillon. Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences, 67(4):691706, 2003.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, e C. Stein. Algoritmos: Teoria e Prática. Campus, 2002.
R. G. Downey e M. R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM Journal on Computing, 24:873921, 1995.
R. G. Downey e M. R. Fellows. Fixed-parameter tractability and completeness II: completeness for W[1]. Theoretical Computer Science, 141:109131, 1995.
R. G. Downey e M. R. Fellows. Parameterized computational feasibility. In Feasible Mathematics II, páginas 219244. Birkhauser Boston, 1995.
R. G. Downey e M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1998.
R. G. Downey e M. R. Fellows. Parameterized complexity after (almost) 10 years: review and open questions. In Combinatorics, Computation & Logic, DMTCS’99 and CATS’99, volume 21, número 3, páginas 133. Australian Computer Science Communications, Springer-Verlag, 1999.
R. G. Downey, M. R. Fellows, e U. Stege. Computational tractability: the view from Mars. Bulletin of the European Association for Theoretical Computer Science, 69:7397, 1999.
R. G. Downey, M. R. Fellows, e U. Stege. Parameterized complexity: a framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, volume 49 de AMS-DIMACS Proceedings Series, páginas 4999. 1999.
R. Niedermeier. Some prospects for efficient fixed parameter algorithms. In Conference on Current Trends in Theory and Practice of Informatics, páginas 168185. 1998.
J. F. Buss e J. Goldsmith. Nondeterminism within P. SIAM Journal on Computing, 22(3):560572, 1993.
R. Balasubramanian, M. R. Fellows, e V. Raman. An improved fixed-parameter algorithm for vertex cover. Information Processing Letters, 65:163168, 1998.
M. Pitanga. Construindo Supercomputadores com Linux. Brasport. 2004.
A. Goldchleger, F. Kon, A. Goldman, M. Finger, e G. C. Bezerra. InteGrade: Object-Oriented Grid Middleware Leveraging Idle Computing Power of Desktop Machines. 2000. Disponível em <http://gsd.ime.usp.br/publications/cpe03integrade.pdf>. Acesso em 16 de Maio de 2007.
L. G. Valiant. A bridging model for computation. Communications of the ACM, 33:103-111, 1990.
F. Dehne, A. Fabri, e A. Rau-Chaplin. Scalable parallel computational geometry for coarse grained multicomputers. In Proceedings of the ACM 9th Annual Computational Geometry, 298-307, 1993.
Publicado
24/10/2007
Como Citar
MONGELLI, Henrique; SAKAMOTO, Rodrigo Cesar.
Implementações de Algoritmos Paralelos FPT para o Problema da k-Cobertura por Vértices utilizando Clusters e Grades Computacionais. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 8. , 2007, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 145-152.
DOI: https://doi.org/10.5753/wscad.2007.18764.
