Uso de GPUs na resolução do Problema da Mochila Multidimensional
Resumo
O problema da mochila multidimensional (MKP) é um problema clássico da área de otimização combinatória. Embora tenha muitas aplicações práticas, não se conhece qualquer algoritmo de complexidade polinomial para a sua resolução, ou seja, pertence à classe NP-difícil. Essa situação tem levado à busca por técnicas mais eficientes para a sua resolução. Contudo, mesmo as abordagens mais promissoras não conseguem resolver instâncias de maior porte em um tempo computacional aceitável. Isso tem motivado o uso de paralelismo em sua resolução e, particularmente, a adoção de GPUs devido à possibilidade de processar em paralelo grandes volumes de dados. Nesse contexto, o presente trabalho tem o objetivo de identificar, por meio de uma revisão sistemática da literatura, o estado da arte das técnicas que utilizam processos de GPUs para resolver o MKP.
Palavras-chave:
Mochila Multidimensional, Unidade Gráfica de Processamento, MKP, GPU
Referências
Bansal, J. C. and Deep, K. (2012). A Modified Binary Particle Swarm Optimization for Knapsack Problems. Appl. Math. Comput., 218:11042–11061.
Beasley, J. E. (1990). OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society, 41(11):1069–1072.
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1 edition.
Berger, K.-E. and Galea, F. (2013). An Efficient Parallelization Strategy for Dynamic Programming on GPU. In 2013 IEEE International Symposium on Parallel Distributed Processing, Workshops and Phd Forum, pages 1797–1806.
Boukedjar, A., Lalami, M., and El-Baz, D. (2012). Parallel Branch and Bound on a CPU-GPU System. In 20th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2012, pages 392–398.
Boyer, V., El Baz, D., and Elkihel, M. (2011a). Dense Dynamic Programming on Multi GPU. In 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, pages 545–551.
Boyer, V., El Baz, D., and Elkihel, M. (2011b). Solving knapsack problems on GPU. Computers and Operations Research, 39(1):42–47.
Das, P. K., Deka, G. C. (2016). History and Evolution of GPU Architecture. In Deka, G. C., Siddesh, G., Srinivasa, K. G., Patnaik, L., editor, Emerging Research Surrounding Power Consumption and Performance Issues in Utility Computing, pages 109–135. IGI Global, IGI Global.
de Almeida Dantas, B. and Cáceres, E. N. (2014). A parallel implementation to the multidimensional knapsack problem using augmented neural networks. In Proceedings of the 2014 Latin American Computing Conference, CLEI 2014, pages 1–9.
de Almeida Dantas, B. and Cáceres, E. N. (2015). Sequential and Parallel Implementation of GRASP for the 0-1 Multidimensional Knapsack Problem. In Procedia Computer Science, pages 2739–2743.
de Almeida Dantas, B. and Cáceres, E. N. (2016a). A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU. In Symposium on Computer Architecture and High Performance Computing, pages 134–140.
de Almeida Dantas, B. and Cáceres, E. N. (2016b). Sequential and Parallel Hybrid Aproaches of Augmented Neural Networks and GRASP for the 0-1 Multidimensional Knapsack Problem. In Gervasi, O., Murgante, B., Misra, S., Rocha, A. M. A., Torre, C. M., Taniar, D., Apduhan, B. O., Stankova, E., and Wang, S., editors, Computational Science and Its Applications – ICCSA 2016. Lecture Notes in Computer Science, volume 9787, pages 207–222. Springer International Publishing, Cham.
de Almeida Dantas, B. and Cáceres, E. N. (2018). An experimental evaluation of a parallel simulated annealing approach for the 0–1 multidimensional knapsack problem. Journal of Parallel and Distributed Computing, 120:211–221.
El-Shafei, M., Ahmad, I., and Alfailakawi, M. (2018). Hardware accelerator for solving 0-1 knapsack problems using binary harmony search. International Journal of Parallel, Emergent and Distributed Systems, 33:87–102.
Fingler, H., Cáceres, E., Mongelli, H., and Song, S. (2014). A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29:84–94.
Garland, M., Le Grand, S., Nickolls, J., Anderson, J., Hardwick, J., Morton, S., Phillips, E., Zhang, Y., and Volkov, V. (2008). Parallel Computing Experiences with CUDA. IEEE Micro, 28(4):13–27.
Gavish, B. and Pirkul, H. (1982). Allocation of Databases and Processors in a Distributed Computing System. In Akoka, J., editor, Management of Distributed Data Processing, volume 31, pages 215–231. North-Holland.
Gilmore, P. C. and Gomory, R. E. (1966). The Theory and Computation of Knapsack Functions. Operations Research, 14(6):1045–1074.
Hajarian, M., Shahbahrami, A., and Hoseini, F. (2016). A parallel solution for the 0-1 knapsack problem using firefly algorithm. In 1st Conference on Swarm Intelligence and Evolutionary Computation, CSIEC 2016 - Proceedings, pages 25–30.
Hanafi, S. and Freville, A. (1998). An efficient tabu search approach for the 0–1 multidimensional knapsack problem. European Journal of Operational Research, 106(2):659–675.
Lalami, M. E. and El-Baz, D. (2012). GPU Implementation of the Branch and Bound Method for Knapsack Problems. In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops PhD Forum, pages 1769–1777.
Lorie, J. H. and Savage, L. J. (1955). Three problems in capital rationing. Journal of Business, 28(4):229–239.
Martello, S. and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons.
Nickolls, J., Buck, I., Garland, M., and Skadron, K. (2008). Scalable Parallel Programming with CUDA: Is CUDA the parallel programming model that application developers have been waiting for? Queue, 6(2):40–53.
Parsifal Ltd. (2018). Parsifal. https://parsif.al/. Último acesso em 23/08/21.
Pospíchal, P., Schwarz, J., and Jaros, J. (2010). Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU. In 16th International Conference on Soft Computing MENDEL, pages 64–70. Brno University of Technology.
Shih, W. (1979). A Branch and Bound Method for the Multiconstraint Zero-One Knap-sack Problem. Journal of the Operational Research Society, 30(4):369–378.
Wang, L., Zheng, X.-L., and Wang, S.-Y. (2013). A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowledge-Based Systems, 48:17–23.
Wazlawick, R. S. (2014). Metodologia de Pesquisa para Ciencia da Computação. Elsevier, Rio de Janeiro – RJ, Brasil, 2 edition.
Zan, D. and Jaros, J. (2014). Solving the Multidimensional Knapsack Problem using a CUDA accelerated PSO. In IEEE Congress on Evolutionary Computation, CEC 2014, pages 2933–2939.
Beasley, J. E. (1990). OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society, 41(11):1069–1072.
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1 edition.
Berger, K.-E. and Galea, F. (2013). An Efficient Parallelization Strategy for Dynamic Programming on GPU. In 2013 IEEE International Symposium on Parallel Distributed Processing, Workshops and Phd Forum, pages 1797–1806.
Boukedjar, A., Lalami, M., and El-Baz, D. (2012). Parallel Branch and Bound on a CPU-GPU System. In 20th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2012, pages 392–398.
Boyer, V., El Baz, D., and Elkihel, M. (2011a). Dense Dynamic Programming on Multi GPU. In 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, pages 545–551.
Boyer, V., El Baz, D., and Elkihel, M. (2011b). Solving knapsack problems on GPU. Computers and Operations Research, 39(1):42–47.
Das, P. K., Deka, G. C. (2016). History and Evolution of GPU Architecture. In Deka, G. C., Siddesh, G., Srinivasa, K. G., Patnaik, L., editor, Emerging Research Surrounding Power Consumption and Performance Issues in Utility Computing, pages 109–135. IGI Global, IGI Global.
de Almeida Dantas, B. and Cáceres, E. N. (2014). A parallel implementation to the multidimensional knapsack problem using augmented neural networks. In Proceedings of the 2014 Latin American Computing Conference, CLEI 2014, pages 1–9.
de Almeida Dantas, B. and Cáceres, E. N. (2015). Sequential and Parallel Implementation of GRASP for the 0-1 Multidimensional Knapsack Problem. In Procedia Computer Science, pages 2739–2743.
de Almeida Dantas, B. and Cáceres, E. N. (2016a). A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU. In Symposium on Computer Architecture and High Performance Computing, pages 134–140.
de Almeida Dantas, B. and Cáceres, E. N. (2016b). Sequential and Parallel Hybrid Aproaches of Augmented Neural Networks and GRASP for the 0-1 Multidimensional Knapsack Problem. In Gervasi, O., Murgante, B., Misra, S., Rocha, A. M. A., Torre, C. M., Taniar, D., Apduhan, B. O., Stankova, E., and Wang, S., editors, Computational Science and Its Applications – ICCSA 2016. Lecture Notes in Computer Science, volume 9787, pages 207–222. Springer International Publishing, Cham.
de Almeida Dantas, B. and Cáceres, E. N. (2018). An experimental evaluation of a parallel simulated annealing approach for the 0–1 multidimensional knapsack problem. Journal of Parallel and Distributed Computing, 120:211–221.
El-Shafei, M., Ahmad, I., and Alfailakawi, M. (2018). Hardware accelerator for solving 0-1 knapsack problems using binary harmony search. International Journal of Parallel, Emergent and Distributed Systems, 33:87–102.
Fingler, H., Cáceres, E., Mongelli, H., and Song, S. (2014). A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29:84–94.
Garland, M., Le Grand, S., Nickolls, J., Anderson, J., Hardwick, J., Morton, S., Phillips, E., Zhang, Y., and Volkov, V. (2008). Parallel Computing Experiences with CUDA. IEEE Micro, 28(4):13–27.
Gavish, B. and Pirkul, H. (1982). Allocation of Databases and Processors in a Distributed Computing System. In Akoka, J., editor, Management of Distributed Data Processing, volume 31, pages 215–231. North-Holland.
Gilmore, P. C. and Gomory, R. E. (1966). The Theory and Computation of Knapsack Functions. Operations Research, 14(6):1045–1074.
Hajarian, M., Shahbahrami, A., and Hoseini, F. (2016). A parallel solution for the 0-1 knapsack problem using firefly algorithm. In 1st Conference on Swarm Intelligence and Evolutionary Computation, CSIEC 2016 - Proceedings, pages 25–30.
Hanafi, S. and Freville, A. (1998). An efficient tabu search approach for the 0–1 multidimensional knapsack problem. European Journal of Operational Research, 106(2):659–675.
Lalami, M. E. and El-Baz, D. (2012). GPU Implementation of the Branch and Bound Method for Knapsack Problems. In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops PhD Forum, pages 1769–1777.
Lorie, J. H. and Savage, L. J. (1955). Three problems in capital rationing. Journal of Business, 28(4):229–239.
Martello, S. and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons.
Nickolls, J., Buck, I., Garland, M., and Skadron, K. (2008). Scalable Parallel Programming with CUDA: Is CUDA the parallel programming model that application developers have been waiting for? Queue, 6(2):40–53.
Parsifal Ltd. (2018). Parsifal. https://parsif.al/. Último acesso em 23/08/21.
Pospíchal, P., Schwarz, J., and Jaros, J. (2010). Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU. In 16th International Conference on Soft Computing MENDEL, pages 64–70. Brno University of Technology.
Shih, W. (1979). A Branch and Bound Method for the Multiconstraint Zero-One Knap-sack Problem. Journal of the Operational Research Society, 30(4):369–378.
Wang, L., Zheng, X.-L., and Wang, S.-Y. (2013). A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowledge-Based Systems, 48:17–23.
Wazlawick, R. S. (2014). Metodologia de Pesquisa para Ciencia da Computação. Elsevier, Rio de Janeiro – RJ, Brasil, 2 edition.
Zan, D. and Jaros, J. (2014). Solving the Multidimensional Knapsack Problem using a CUDA accelerated PSO. In IEEE Congress on Evolutionary Computation, CEC 2014, pages 2933–2939.
Publicado
25/10/2021
Como Citar
LEMOS, Dayllon Vinícius Xavier; LONGO, Humberto J..
Uso de GPUs na resolução do Problema da Mochila Multidimensional. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 9. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 68-81.
DOI: https://doi.org/10.5753/erigo.2021.18434.
