Uma implementação da busca em largura com estrutura bag e OpenMP
Resumo
Neste artigo, são mostrados resultados de uma re-implementação da busca em largura na linguagem C++ com estrutura bag e interface OpenMP. A implementação é baseada em uma proposta existente na bibliografia que utilizou a linguagem Cilk++, que foi descontinuada. Para os experimentos realizados neste presente trabalho, foram utilizados 10 grafos não direcionados e 10 digrafos em uma máquina composta de oito núcleos, com duas threads por núcleo. Em relação à versão serial, a nova implementação apresentou aceleração de 3,2 a 5,7x ao utilizar oito threads e de aproximadamente 3 a 8x ao utilizar 16 threads.Referências
Belova, M. and Ouyang, M. (2017). Breadth-first search with a multi-core computer. In IEEE Int. Parallel and Distributed Processing Symposium Workshops, pages 579–587.
Brandão, D., Coutinho, R., Silva, P. H. G., Assis, L. S., Sá, F. P. G., and Gonzaga de Oliveira, S. L. (2019). Estudo sobre o uso do framework openmp na paralelização de um algoritmo para o problema de busca em largura. In Anais do LI Simpósio Brasileiro de Pesquisa Operacional (SBPO 2019), volume 2, page 108262, Limeira, SP. Sobrapo.
Cabral, F. L., Gonzaga de Oliveira, S. L., Osthoff, C., Costa, G. P., Brandão, D. N., and Kischinhevsky, M. (2020). An evaluation of MPI and OpenMP paradigms in finitedifference explicit methods for PDEs on shared-memory multiand manycore systems. Concurrency and Computation: Practice and Experience, 32(20):e5642.
Chhugani, J., Satish, N., Kim, C., Sewall, J., and Dubey, P. (2012). Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency. In Proc. of the 2012 IEEE 26th Int. Parallel and Distributed Processing Symposium, pages 378–389.
Davis, T. A. and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1):1–25.
Gonzaga de Oliveira, S. L. and Silva, L. M. (2020a). An ant colony hyperheuristic approach for matrix bandwidth reduction. Applied soft computing, 94:106434.
Gonzaga de Oliveira, S. L. and Silva, L. M. (2020b). Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method. Engineering with Computers, 36:1857–1873.
Gonzaga de Oliveira, S. L. and Silva, L. M. (2021). Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy. Rairo Operations Research, 55(4):2247–2264.
Hassaan, M. A., Burtscher, M., and Pingali, K. (2010). Ordered and unordered algorithms for parallel breadth first search. In Parallel Architectures and Compilation Techniques Conference Proceedings, PACT, pages 539–540.
Hassaan, M. A., Burtscher, M., and Pingali, K. (2011). Ordered vs. unordered: A comparison of parallelism and work-efficiency in irregular algorithms. In Proc. of the ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, pages 3–12.
Hong, S., Oguntebi, T., and Olukotun, K. (2011). Efficient parallel graph exploration on multicore CPU and GPU. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT’11), pages 100–113.
Leiserson, C. E. and Schardl, T. B. (2010). A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). In Proc. of the 22nd annual ACM Symp. on Parallelism in algorithms and architectures, pages 303–314.
Shun, J. and Blelloch, G. E. (2013a). Ligra: A lightweight graph processing framework for shared memory. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, pages 135–146, New York. ACM.
Shun, J. and Blelloch, G. E. (2013b). Ligra: A lightweight graph processing framework for shared memory. ACM SIGPLAN Notices, 48(8):135–146.
Shun, J., Dhulipala, L., and Blelloch, G. E. (2015). Smaller and faster: Parallel processing of compressed graphs with ligra+. In Data Compression Conference, pages 403–412.
St. John, T., Dennis, J. B., and Gao, G. R. (2012). Massively parallel breadth first search using a tree-structured memory model. In Proceedings of the 2012 Int. Workshop on Programming Models and Applications for Multicores and Manycores, pages 115–123.
Suzumura, T., Ueno, K., Sato, H., Fujisawa, K., and Matsuoka, S. (2011). Performance characteristics of Graph500 on large-scale distributed environment. In IEEE International Symposium on Workload Characterization (IISWC), pages 149–158.
Tithi, J. J., Matani, D., Menghani, G., and Chowdhury, R. A. (2013). Avoiding locks and atomic instructions in shared-memory parallel BFS using optimistic parallelization. In Proceedings IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW, pages 1628–1637.
Brandão, D., Coutinho, R., Silva, P. H. G., Assis, L. S., Sá, F. P. G., and Gonzaga de Oliveira, S. L. (2019). Estudo sobre o uso do framework openmp na paralelização de um algoritmo para o problema de busca em largura. In Anais do LI Simpósio Brasileiro de Pesquisa Operacional (SBPO 2019), volume 2, page 108262, Limeira, SP. Sobrapo.
Cabral, F. L., Gonzaga de Oliveira, S. L., Osthoff, C., Costa, G. P., Brandão, D. N., and Kischinhevsky, M. (2020). An evaluation of MPI and OpenMP paradigms in finitedifference explicit methods for PDEs on shared-memory multiand manycore systems. Concurrency and Computation: Practice and Experience, 32(20):e5642.
Chhugani, J., Satish, N., Kim, C., Sewall, J., and Dubey, P. (2012). Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency. In Proc. of the 2012 IEEE 26th Int. Parallel and Distributed Processing Symposium, pages 378–389.
Davis, T. A. and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1):1–25.
Gonzaga de Oliveira, S. L. and Silva, L. M. (2020a). An ant colony hyperheuristic approach for matrix bandwidth reduction. Applied soft computing, 94:106434.
Gonzaga de Oliveira, S. L. and Silva, L. M. (2020b). Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method. Engineering with Computers, 36:1857–1873.
Gonzaga de Oliveira, S. L. and Silva, L. M. (2021). Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy. Rairo Operations Research, 55(4):2247–2264.
Hassaan, M. A., Burtscher, M., and Pingali, K. (2010). Ordered and unordered algorithms for parallel breadth first search. In Parallel Architectures and Compilation Techniques Conference Proceedings, PACT, pages 539–540.
Hassaan, M. A., Burtscher, M., and Pingali, K. (2011). Ordered vs. unordered: A comparison of parallelism and work-efficiency in irregular algorithms. In Proc. of the ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, pages 3–12.
Hong, S., Oguntebi, T., and Olukotun, K. (2011). Efficient parallel graph exploration on multicore CPU and GPU. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT’11), pages 100–113.
Leiserson, C. E. and Schardl, T. B. (2010). A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). In Proc. of the 22nd annual ACM Symp. on Parallelism in algorithms and architectures, pages 303–314.
Shun, J. and Blelloch, G. E. (2013a). Ligra: A lightweight graph processing framework for shared memory. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, pages 135–146, New York. ACM.
Shun, J. and Blelloch, G. E. (2013b). Ligra: A lightweight graph processing framework for shared memory. ACM SIGPLAN Notices, 48(8):135–146.
Shun, J., Dhulipala, L., and Blelloch, G. E. (2015). Smaller and faster: Parallel processing of compressed graphs with ligra+. In Data Compression Conference, pages 403–412.
St. John, T., Dennis, J. B., and Gao, G. R. (2012). Massively parallel breadth first search using a tree-structured memory model. In Proceedings of the 2012 Int. Workshop on Programming Models and Applications for Multicores and Manycores, pages 115–123.
Suzumura, T., Ueno, K., Sato, H., Fujisawa, K., and Matsuoka, S. (2011). Performance characteristics of Graph500 on large-scale distributed environment. In IEEE International Symposium on Workload Characterization (IISWC), pages 149–158.
Tithi, J. J., Matani, D., Menghani, G., and Chowdhury, R. A. (2013). Avoiding locks and atomic instructions in shared-memory parallel BFS using optimistic parallelization. In Proceedings IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW, pages 1628–1637.
Publicado
26/10/2021
Como Citar
OLIVEIRA, S. L. Gonzaga de; SANTANA, M. I.; BRANDÃO, D.; OSTHOFF, C..
Uma implementação da busca em largura com estrutura bag e OpenMP. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 22. , 2021, Belo Horizonte.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 1-12.
DOI: https://doi.org/10.5753/wscad.2021.18507.
