Algoritmo Paralelo para Árvore Geradora Usando GPU
Resumo
Neste trabalho, usando o modelo BSP/CGM, propomos um algoritmo paralelo, com uma implementação em CUDA, para obter uma árvore geradora de um grafo. Trabalhos anteriores para este problema são baseados na solução do problema de list ranking que, embora eficiente na teoria, não produz bons ganhos na prática. Num trabalho posterior, baseado na ideia do cálculo de uma estrutura chamada esteio, Cáceres et al. propuseram um algoritmo paralelo no modelo BSP/CGM para obter uma árvore geradora sem a utilização de list ranking. O cálculo do esteio é obtido com a utilização de um grafo bipartido auxiliar, com o uso de ordenação inteira. Neste artigo melhoramos aquele trabalho em vários aspectos. No algoritmo proposto, para implementação em GPGPU, não é mais necessário calcular o grafo bipartido, e a construção do esteio não necessita do algoritmo de ordenação. A eficiência e escalabilidade do algoritmo proposto são verificadas por experimentos.
Referências
Boruvka, O. (1926). On a minimal problem. Prace Moravské Pridovedecké Spodecnosti, 3:37–58.
Cáceres, E. N., Dehne, F., Mongelli, H., Song, S. W., and Szwarcter, J. (2004). A coarsegrained parallel algorithm for spanning tree and connected components. In Euro-Par 2004. Lecture Notes in Computer Science, volume 3149, p. 828–831. Springer-Verlag.
Cáceres, E. N., Deo, N., Sastry, S., and Szwarcter, J. L. (1993). On nding Euler tours in parallel. Parallel Processing Letters, 3(3):223–231.
Chan, A. and Dehne, F. (1999). A note on coarse grained parallel integer sorting. Parallel Processing Letters, 9(4):533–538.
Chin, F. Y., Lam, J., and Chen, I.-N. (1982). Efcient parallel algorithms for some graph problems. Communications of the ACM, 25(9):659–665.
Dehne, F., Fabri, A., and Rau-Chaplin, A. (1996). Scalable Parallel Computational Geometry for Coarse Grained Multicomputers. International Journal on Computational Geometry & Applications, 6(3):298–307.
Dehne, F., Ferreira, A., Cáceres, E., Song, S. W., and Roncato, A. (2002). Efcient parallel graph algorithms for coarse grained multicomputers and BSP. Algorithmica, 33(2):183–200.
Dehne, F. and Song, S. W. (1997). Randomized parallel list ranking for distributed memory multiprocessors. International Journal of Parallel Programming, 25(1):1–16.
Graham, R. L. and Hell, P. (1985). On the history of of the minimum spanning tree problem. In Annals of the History of Computing, volume 7, p. 43–57.
Hawick, K. A., Leist, A., and Playne, D. (2010). Parallel graph component labelling with GPUs and CUDA. Parallel Computing, 36(12):655–678.
Hirschberg, D. S., Chandra, A. K., and Sarwate, D. V. (1979). Computing connected components on parallel computers. Comm. ACM, 22(8):461–464.
Johnson, D. and Metaxas, P. (1995). A parallel algorithm for computing minimum span ning trees. Journal of Algorithms, 19(3):383 – 401.
Johnsonbaugh, R. and Kalin, M. (1991). A graph generation software package. In Proceedings of the twenty-second SIGCSE technical symposium on Computer Science Education, volume 23, p. 151–154.
Karger, D. R., Klein, P. N., and Tarjan, R. E. (1995). A randomized linear-time algorithm to nd minimum spanning trees. Journal of the ACM, 42(2):321–328.
Li, D. and Becchi, M. (2013). Deploying graph algorithms on gpus: an adaptive solution. In Proceedings of IEEE 27th International Parallel and Distributed Processing Symposium, IPDPS 2013, p. 1013–1024.
Lima, A. C. d., Branco, R. G., Ferraz, S., Cáceres, E. N., Gaioso, R. R. A., Martins, W. S., and Song, S. W. (2016). Solving the maximum subsequence sum and related problems using BSP/CGM model and multi-GPU CUDA. Journal of The Brazilian Computer Society (Online), 22:1–13.
Nasre, R., Burtscher, M., and Pingali, K. (2013). Morph algorithms on GPUs. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, p. 147–156.
Nobari, S., Cao, T.-T., Karras, P., and Bressan, S. (2012). Scalable parallel minimum spanning forest computation. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, p. 205–214.
Valiant, L. G. (1990). A Bridging Model for Parallel Computation. Commun. ACM, 33(8):103–111.
Vineet, V., Harish, P., Patidar, S., and Narayanan, P. J. (2009). Fast minimum spanning tree for large graphs on the GPU. In Proceedings of the Conference on High Performance Graphics 2009, HPG '09, p. 167–171.
Cáceres, E. N., Dehne, F., Mongelli, H., Song, S. W., and Szwarcter, J. (2004). A coarsegrained parallel algorithm for spanning tree and connected components. In Euro-Par 2004. Lecture Notes in Computer Science, volume 3149, p. 828–831. Springer-Verlag.
Cáceres, E. N., Deo, N., Sastry, S., and Szwarcter, J. L. (1993). On nding Euler tours in parallel. Parallel Processing Letters, 3(3):223–231.
Chan, A. and Dehne, F. (1999). A note on coarse grained parallel integer sorting. Parallel Processing Letters, 9(4):533–538.
Chin, F. Y., Lam, J., and Chen, I.-N. (1982). Efcient parallel algorithms for some graph problems. Communications of the ACM, 25(9):659–665.
Dehne, F., Fabri, A., and Rau-Chaplin, A. (1996). Scalable Parallel Computational Geometry for Coarse Grained Multicomputers. International Journal on Computational Geometry & Applications, 6(3):298–307.
Dehne, F., Ferreira, A., Cáceres, E., Song, S. W., and Roncato, A. (2002). Efcient parallel graph algorithms for coarse grained multicomputers and BSP. Algorithmica, 33(2):183–200.
Dehne, F. and Song, S. W. (1997). Randomized parallel list ranking for distributed memory multiprocessors. International Journal of Parallel Programming, 25(1):1–16.
Graham, R. L. and Hell, P. (1985). On the history of of the minimum spanning tree problem. In Annals of the History of Computing, volume 7, p. 43–57.
Hawick, K. A., Leist, A., and Playne, D. (2010). Parallel graph component labelling with GPUs and CUDA. Parallel Computing, 36(12):655–678.
Hirschberg, D. S., Chandra, A. K., and Sarwate, D. V. (1979). Computing connected components on parallel computers. Comm. ACM, 22(8):461–464.
Johnson, D. and Metaxas, P. (1995). A parallel algorithm for computing minimum span ning trees. Journal of Algorithms, 19(3):383 – 401.
Johnsonbaugh, R. and Kalin, M. (1991). A graph generation software package. In Proceedings of the twenty-second SIGCSE technical symposium on Computer Science Education, volume 23, p. 151–154.
Karger, D. R., Klein, P. N., and Tarjan, R. E. (1995). A randomized linear-time algorithm to nd minimum spanning trees. Journal of the ACM, 42(2):321–328.
Li, D. and Becchi, M. (2013). Deploying graph algorithms on gpus: an adaptive solution. In Proceedings of IEEE 27th International Parallel and Distributed Processing Symposium, IPDPS 2013, p. 1013–1024.
Lima, A. C. d., Branco, R. G., Ferraz, S., Cáceres, E. N., Gaioso, R. R. A., Martins, W. S., and Song, S. W. (2016). Solving the maximum subsequence sum and related problems using BSP/CGM model and multi-GPU CUDA. Journal of The Brazilian Computer Society (Online), 22:1–13.
Nasre, R., Burtscher, M., and Pingali, K. (2013). Morph algorithms on GPUs. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, p. 147–156.
Nobari, S., Cao, T.-T., Karras, P., and Bressan, S. (2012). Scalable parallel minimum spanning forest computation. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, p. 205–214.
Valiant, L. G. (1990). A Bridging Model for Parallel Computation. Commun. ACM, 33(8):103–111.
Vineet, V., Harish, P., Patidar, S., and Narayanan, P. J. (2009). Fast minimum spanning tree for large graphs on the GPU. In Proceedings of the Conference on High Performance Graphics 2009, HPG '09, p. 167–171.
Publicado
17/10/2017
Como Citar
F. A. VASCONCELLOS, Jucele; N. CÁCERES, Edson; MONGELLI, Henrique; W. SONG, Siang.
Algoritmo Paralelo para Árvore Geradora Usando GPU. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 18. , 2017, Campinas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 292-303.
DOI: https://doi.org/10.5753/wscad.2017.257.
