Implementações em Grades Computacionais de Algoritmos BSP/CGM para os Problemas da Mochila 0-1 e Mínimo Intervalar
Resumo
Neste artigo, apresentamos os resultados experimentais das implementações dos algoritmos BSP/CGM para os problemas da mochila 0-1 e do mínimo intervalar, utilizando uma grade computacional. A grade computacional dos testes utiliza o middleware desenvolvido no Projeto lntegrade. Estes algoritmos foram implementados usando a biblioteca BSPLib do lntegrade. Para analisar o desempenho do middleware, os algoritmos também foram implementados num Beowulf (cluster) usando as bibliotecas BSP-Pub e LAM-MPI. Os resultados obtidos foram bastante promissores na validação do middleware, apresentando bons tempos de processamento.
Referências
Pub-library. Disponível em http://wwwcs.unipaderborn.de/~bsp/, 2006. Último acesso em 31/03/2006.
N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Tel Aviv,lsrael69978, 1987. Tel Aviv University.
C. E. R. Alves. E. N. Cáceres, F. Dehne, and S. W. Song. A parallel wavefront algorithm for efficient biological sequence comparison. In Proceedings ICCSA 2003, volume 2668 of Lecture Notes in Computer Science, pages 249- 258. Springer, 2003.
R. Andonov, F. Raimbault. and P. Quinton. Dynamic programming parallel implementations for knapsack problem. Technical Report RI 740, IRISA. 1993.
G. Chen, M. Chem, and J. Jang. Pipeline architectures for dynamic programming algorithms. Parallel Computing, 13:1 11-117, 1990.
C. Chung., M. S. Hung, and W. O. Rom. A hard knapsack problem. Naval Research Logistics, 35:85-98, 1988.
D. P. da Silva. W. Cime, and F. V. Brasileiro. Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids. Lecture Notes in Computer Science, 2790:169- 180, 2003. 88
F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel computational geometry for coarse grained multicomputers. In Proceedings of the ACM 9th Annual Computational Geometry, pages 298-307, 1993.
A. Ferreira and J. M. Robson. Fast and scalable parallel algorithms for knapsack-like problems. J. Parallel Distrib. Comput., 39:1-13, 1996.
H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In STOC '84: Proceedings o f the sixteenth annual ACM symposium on Theory of computing, pages 135-143, New York, NY, USA, 1984. ACM Press. apud f22].
M. R. Garey and D. S. Johnson. Computers and lntractability- A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979. apud [16].
R. Garfinkel and G. Nemhauser. lnteger Programming. John Wiley and Sons, 1972.
P. C. Gilmore and R. E. Gomory. The theory and computation of knapsack functions. Operations Research, 14:1045-1074, 1966.
A. Goldchleger, F. Kon, A. Goldman, M. Finger, and G. C. Bezerra. Integrade: object-oriented grid middleware leveraging the idle computing power of desktop machines. Conrcurrency and Computation: Practice and Experience, 16(5):449-459, March 2004.
O. M. Group. CORBA v3.0 Specification. Needham, MA, Ju1y 2002. OMG Document 02-06-33.
E. J. Hanashiro. O problema da k-Cobertura por Vértices: Uma Implementação FfP no modelo BSP/CGM. Master's thesis, 2004.
T. C. Hu. Combinatorial Algorithms. Addison Wesley, 1982.
TnteGn1de. http://gsd.ime.usp.br/integrade. 2004.
S. Martello and P. Toth. Kanpsack Problems: Algorithms and Computer Jmplementations. John Wiley and Sons, 1990.
H. Mongelli and L. Gonda. Uma implementação de algoritmos bsp/cgm de ordenação. VI Work.slrop em Sistemas Computacionais de Alto Desempenho, I (89-96), 2005. Anais do VI Workshop em Sistemas Computacionais de Alto Desempenho-WSCAD 2005.
H. Mongelli, E. J. Hanashiro, and S. Song. Efficient implementation ofthe bsp/cgm parallel vertex cover fpt algorithm. Third lnternational Workshop on Experimental and Efficient Algoritms - WEA 2004, 3059(253-268), 2004. Lecture Notes in Computer Science.
H. Mongelli and S. Song. Parallel mnge minima on coarse grained multicomputers. Ttrtenrational Jounral of Foundations of Compute r Science. 10(4):375-389, 1999. f231 D. Morales, J. Roda, F. Almeida, C. Rodrigues, and F. Garcia. Integral knapsack problems: Parallel algorithms and theirs implementations on distributed systems. In Proc. of the ACM-ICS 95, pages 218-226, 1995.
J. H. Reif. Synthesis of Parallel Algorithms. editor (Morgan Kaufmann Publishers), 1993. apud [22].
R. A. Sevenich. Parallel processing using pvm. Linux J. , 1998(45es):2, 1998. apud [22].
S. Teng. Adaptative parallel algoritltm for integral knapsack problems. J. of Parallel and Distributed Computing, 14:1045- 1074, 1990. Ouro Preto, 17 a 20 de outubro de 2006
L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33:103-111, 1990.
J. Vuillemin. A unified look at data structures. pages 229-239, 1980. apud [22].
N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Tel Aviv,lsrael69978, 1987. Tel Aviv University.
C. E. R. Alves. E. N. Cáceres, F. Dehne, and S. W. Song. A parallel wavefront algorithm for efficient biological sequence comparison. In Proceedings ICCSA 2003, volume 2668 of Lecture Notes in Computer Science, pages 249- 258. Springer, 2003.
R. Andonov, F. Raimbault. and P. Quinton. Dynamic programming parallel implementations for knapsack problem. Technical Report RI 740, IRISA. 1993.
G. Chen, M. Chem, and J. Jang. Pipeline architectures for dynamic programming algorithms. Parallel Computing, 13:1 11-117, 1990.
C. Chung., M. S. Hung, and W. O. Rom. A hard knapsack problem. Naval Research Logistics, 35:85-98, 1988.
D. P. da Silva. W. Cime, and F. V. Brasileiro. Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids. Lecture Notes in Computer Science, 2790:169- 180, 2003. 88
F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel computational geometry for coarse grained multicomputers. In Proceedings of the ACM 9th Annual Computational Geometry, pages 298-307, 1993.
A. Ferreira and J. M. Robson. Fast and scalable parallel algorithms for knapsack-like problems. J. Parallel Distrib. Comput., 39:1-13, 1996.
H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In STOC '84: Proceedings o f the sixteenth annual ACM symposium on Theory of computing, pages 135-143, New York, NY, USA, 1984. ACM Press. apud f22].
M. R. Garey and D. S. Johnson. Computers and lntractability- A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979. apud [16].
R. Garfinkel and G. Nemhauser. lnteger Programming. John Wiley and Sons, 1972.
P. C. Gilmore and R. E. Gomory. The theory and computation of knapsack functions. Operations Research, 14:1045-1074, 1966.
A. Goldchleger, F. Kon, A. Goldman, M. Finger, and G. C. Bezerra. Integrade: object-oriented grid middleware leveraging the idle computing power of desktop machines. Conrcurrency and Computation: Practice and Experience, 16(5):449-459, March 2004.
O. M. Group. CORBA v3.0 Specification. Needham, MA, Ju1y 2002. OMG Document 02-06-33.
E. J. Hanashiro. O problema da k-Cobertura por Vértices: Uma Implementação FfP no modelo BSP/CGM. Master's thesis, 2004.
T. C. Hu. Combinatorial Algorithms. Addison Wesley, 1982.
TnteGn1de. http://gsd.ime.usp.br/integrade. 2004.
S. Martello and P. Toth. Kanpsack Problems: Algorithms and Computer Jmplementations. John Wiley and Sons, 1990.
H. Mongelli and L. Gonda. Uma implementação de algoritmos bsp/cgm de ordenação. VI Work.slrop em Sistemas Computacionais de Alto Desempenho, I (89-96), 2005. Anais do VI Workshop em Sistemas Computacionais de Alto Desempenho-WSCAD 2005.
H. Mongelli, E. J. Hanashiro, and S. Song. Efficient implementation ofthe bsp/cgm parallel vertex cover fpt algorithm. Third lnternational Workshop on Experimental and Efficient Algoritms - WEA 2004, 3059(253-268), 2004. Lecture Notes in Computer Science.
H. Mongelli and S. Song. Parallel mnge minima on coarse grained multicomputers. Ttrtenrational Jounral of Foundations of Compute r Science. 10(4):375-389, 1999. f231 D. Morales, J. Roda, F. Almeida, C. Rodrigues, and F. Garcia. Integral knapsack problems: Parallel algorithms and theirs implementations on distributed systems. In Proc. of the ACM-ICS 95, pages 218-226, 1995.
J. H. Reif. Synthesis of Parallel Algorithms. editor (Morgan Kaufmann Publishers), 1993. apud [22].
R. A. Sevenich. Parallel processing using pvm. Linux J. , 1998(45es):2, 1998. apud [22].
S. Teng. Adaptative parallel algoritltm for integral knapsack problems. J. of Parallel and Distributed Computing, 14:1045- 1074, 1990. Ouro Preto, 17 a 20 de outubro de 2006
L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33:103-111, 1990.
J. Vuillemin. A unified look at data structures. pages 229-239, 1980. apud [22].
Publicado
17/10/2006
Como Citar
CÁCERES, Edson N.; MONGELLI, Henrique; NISHIBE, Christiane; SANDIM, Hercules da C..
Implementações em Grades Computacionais de Algoritmos BSP/CGM para os Problemas da Mochila 0-1 e Mínimo Intervalar. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 7. , 2006, Ouro Preto.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2006
.
p. 73-80.
DOI: https://doi.org/10.5753/wscad.2006.18949.
