Proposta de paralelização em GPUs CUDA do algoritmo MPS para resolução do problema de encontrar os K-Caminhos Mais Curtos Sem Repetições de Vértices em grafos direcionados e não direcionados
Resumo
O Problema dos K-Caminhos mais Curtos sem Repetições de Vértices (K-Shortest Loopless Paths – KSLP) consiste em encontrar K | K > 1 caminhos, sem repetições de vértices, classificados em ordem crescente de distância, em um grafo G(V, E), no qual V representa o conjunto de vértices e E o conjunto dos arestas que os conecta. Dada a dificuldade de obter bom desempenho para solução do problema, este trabalho propõe a paralelização em GPUs CUDA do algoritmo mais veloz existente na literatura para o problema.
Palavras-chave:
K-Caminhos mais Curtos sem Repetições de Vértices
Referências
Berclaz, J., Fleuret, F., Turetken, E., and Fua, P. (2011). Multiple object tracking using k-shortest paths optimization. IEEE transactions on pattern analysis and machine intelligence, 33(9):1806–1819.
Bergstrom, L. and Reppy, J. (2012). Nested data-parallelism on the GPU. In ACM SIGPLAN Notices, volume 47, pages 247–258. ACM.
Bernstein, A. (2010). A nearly optimal algorithm for approximating replacement paths and K shortest simple paths in general graphs. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 742–755, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.
Bock, F., Kantner, H., and Haynes, J. (1957). An algorithm (the r-th best path algorithm) for finding and ranking paths through a network. Armour Research Foundation.
Chen, R. and Prasanna, V. K. (2016). Accelerating equi-join on a CPU-FPGA heterogeneous platform. In 2016 IEEE 24th Annual International Symposium on FieldProgrammable Custom Computing Machines (FCCM), pages 212–219. IEEE.
Clarke, S., Krikorian, A., and Rausen, J. (1963). Computing the N best loopless paths in a network. Journal of the Society for Industrial and Applied Mathematics, 11(4):1096– 1102.
Cook, S. (2012). CUDA programming: a developer’s guide to parallel computing with GPUs. Newnes.
Cook, S. (2013). CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition.
Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1:269:271.
Eppstein, D. (1998). Finding the k shortest paths. SIAM Journal on computing, 28(2):652–673.
Feng, G. (2014). Improving space efficiency with path length prediction for finding k shortest simple paths. IEEE Transactions on Computers, 63(10):2459–2472.
Golub, G. H. and Van Loan, C. F. (1996). Matrix Computations (3rd Ed.). Johns Hopkins University Press, USA.
Gotthilf, Z. and Lewenstein, M. (2009). Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett., 109:352–355.
Harish, P. and Narayanan, P. (2007). Accelerating large graph algorithms on the GPU using CUDA. In International conference on high-performance computing, pages 197– 208. Springer.
Hershberger, J., Maxel, M., and Suri, S. (2007). Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms (TALG), 3(4):45.
Hildebrand, B. F. (1987). Introduction to Numerical Analysis: 2nd Edition. Dover Publications, Inc., USA.
Hoffman, W. and Pavley, R. (1959). A method for the solution of the n th best path problem. Journal of the ACM (JACM), 6(4):506–514.
Katoh, N., Ibaraki, T., and Mine, H. (1982). An efficient algorithm for k shortest simple paths. Networks, 12(4):411–427.
Luebke, D. (2008). CUDA: Scalable parallel programming for high-performance scientific computing. In 2008 5th IEEE International Symposium on Biomedical imaging: from nano to macro, pages 836–838. IEEE.
Martins, E. d. Q. V., Pascoal, M. M. B., and dos Santos, J. L. E. (1997). A new algorithm for ranking loopless paths. Technical report, Research Report (CISUC), Universidade de Coimbra.
Martins, E. d. Q. V., Pascoal, M. M. B., and dos Santos, J. L. E. (1999). Deviation algorithms for ranking shortest paths. International Journal of Foundations of Computer Science, 10(03):247–261.
Nvidia (2018). CUDA toolkit documentation v10.1.105.
Pettie, S. (2004). A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47–74.
Pollack, M. (1961). Letter to the editor - the k-th best route through a network. Operations Research, 9(4):578–580.
Sakarovitch, M. (1968). The k shortest chains in a graph. Transportation Research, 2(1):1 – 11.
Schmid, R., Pisani, F., Borin, E., and Cáceres, E. (2016). An evaluation of segmented sorting strategies on GPUs. In 2016 IEEE 18th International Conference on High Performance Computing and Communications; IEEE 14th International Conference on Smart City; IEEE 2nd International Conference on Data Science and Systems (HPCC/SmartCity/DSS), pages 1123–1130. IEEE.
Singh, A. P. and Singh, D. P. (2015a). Implementation of k-shortest path algorithm in GPU using CUDA. Procedia Computer Science, 48:5–13.
Singh, A. P. and Singh, D. P. (2015b). Implementation of k-shortest path algorithm in GPU using CUDA. Procedia Computer Science, 48:5 – 13. International Conference on Computer, Communication and Convergence (ICCC 2015).
Srivastava, A., Chen, R., Prasanna, V. K., and Chelmis, C. (2015). A hybrid design for high performance large-scale sorting on fpga. In 2015 International Conference on ReConFigurable Computing and FPGAs (ReConFig), pages 1–6. IEEE.
Thorup, M. (1999). Undirected single source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3):362–394. Announced at FOCS’97.
Wen, Q., Zhou, Q., Zhao, C., and Ma, X. (2013). Fixed-point realization of latticereduction aided mimo receivers with complex k-best algorithm. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5031–5035. IEEE.
Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. management Science, 17(11):712–716.
Zuse-Institute (2020). Survivable fixed telecommunication network design. http:// sndlib.zib.de/home.action, Visitado pela última vez em 10 de julho, 2020.
Bergstrom, L. and Reppy, J. (2012). Nested data-parallelism on the GPU. In ACM SIGPLAN Notices, volume 47, pages 247–258. ACM.
Bernstein, A. (2010). A nearly optimal algorithm for approximating replacement paths and K shortest simple paths in general graphs. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 742–755, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.
Bock, F., Kantner, H., and Haynes, J. (1957). An algorithm (the r-th best path algorithm) for finding and ranking paths through a network. Armour Research Foundation.
Chen, R. and Prasanna, V. K. (2016). Accelerating equi-join on a CPU-FPGA heterogeneous platform. In 2016 IEEE 24th Annual International Symposium on FieldProgrammable Custom Computing Machines (FCCM), pages 212–219. IEEE.
Clarke, S., Krikorian, A., and Rausen, J. (1963). Computing the N best loopless paths in a network. Journal of the Society for Industrial and Applied Mathematics, 11(4):1096– 1102.
Cook, S. (2012). CUDA programming: a developer’s guide to parallel computing with GPUs. Newnes.
Cook, S. (2013). CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition.
Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1:269:271.
Eppstein, D. (1998). Finding the k shortest paths. SIAM Journal on computing, 28(2):652–673.
Feng, G. (2014). Improving space efficiency with path length prediction for finding k shortest simple paths. IEEE Transactions on Computers, 63(10):2459–2472.
Golub, G. H. and Van Loan, C. F. (1996). Matrix Computations (3rd Ed.). Johns Hopkins University Press, USA.
Gotthilf, Z. and Lewenstein, M. (2009). Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett., 109:352–355.
Harish, P. and Narayanan, P. (2007). Accelerating large graph algorithms on the GPU using CUDA. In International conference on high-performance computing, pages 197– 208. Springer.
Hershberger, J., Maxel, M., and Suri, S. (2007). Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms (TALG), 3(4):45.
Hildebrand, B. F. (1987). Introduction to Numerical Analysis: 2nd Edition. Dover Publications, Inc., USA.
Hoffman, W. and Pavley, R. (1959). A method for the solution of the n th best path problem. Journal of the ACM (JACM), 6(4):506–514.
Katoh, N., Ibaraki, T., and Mine, H. (1982). An efficient algorithm for k shortest simple paths. Networks, 12(4):411–427.
Luebke, D. (2008). CUDA: Scalable parallel programming for high-performance scientific computing. In 2008 5th IEEE International Symposium on Biomedical imaging: from nano to macro, pages 836–838. IEEE.
Martins, E. d. Q. V., Pascoal, M. M. B., and dos Santos, J. L. E. (1997). A new algorithm for ranking loopless paths. Technical report, Research Report (CISUC), Universidade de Coimbra.
Martins, E. d. Q. V., Pascoal, M. M. B., and dos Santos, J. L. E. (1999). Deviation algorithms for ranking shortest paths. International Journal of Foundations of Computer Science, 10(03):247–261.
Nvidia (2018). CUDA toolkit documentation v10.1.105.
Pettie, S. (2004). A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47–74.
Pollack, M. (1961). Letter to the editor - the k-th best route through a network. Operations Research, 9(4):578–580.
Sakarovitch, M. (1968). The k shortest chains in a graph. Transportation Research, 2(1):1 – 11.
Schmid, R., Pisani, F., Borin, E., and Cáceres, E. (2016). An evaluation of segmented sorting strategies on GPUs. In 2016 IEEE 18th International Conference on High Performance Computing and Communications; IEEE 14th International Conference on Smart City; IEEE 2nd International Conference on Data Science and Systems (HPCC/SmartCity/DSS), pages 1123–1130. IEEE.
Singh, A. P. and Singh, D. P. (2015a). Implementation of k-shortest path algorithm in GPU using CUDA. Procedia Computer Science, 48:5–13.
Singh, A. P. and Singh, D. P. (2015b). Implementation of k-shortest path algorithm in GPU using CUDA. Procedia Computer Science, 48:5 – 13. International Conference on Computer, Communication and Convergence (ICCC 2015).
Srivastava, A., Chen, R., Prasanna, V. K., and Chelmis, C. (2015). A hybrid design for high performance large-scale sorting on fpga. In 2015 International Conference on ReConFigurable Computing and FPGAs (ReConFig), pages 1–6. IEEE.
Thorup, M. (1999). Undirected single source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3):362–394. Announced at FOCS’97.
Wen, Q., Zhou, Q., Zhao, C., and Ma, X. (2013). Fixed-point realization of latticereduction aided mimo receivers with complex k-best algorithm. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5031–5035. IEEE.
Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. management Science, 17(11):712–716.
Zuse-Institute (2020). Survivable fixed telecommunication network design. http:// sndlib.zib.de/home.action, Visitado pela última vez em 10 de julho, 2020.
Publicado
20/10/2020
Como Citar
REIS, Daniel; ESPÍNDOLA, Álvaro; SOUZA, Sérgio; MILANÉS, Anolan.
Proposta de paralelização em GPUs CUDA do algoritmo MPS para resolução do problema de encontrar os K-Caminhos Mais Curtos Sem Repetições de Vértices em grafos direcionados e não direcionados. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 17. , 2020, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 662-673.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2020.12168.
