Decidindo entre GPU e CPU para Processar Grafos com Base em Métricas de Alto Nível
Resumo
Apesar dos avanços nas GPUs modernas ter acelerado a execução de aplicações que processam grandes quantidades de dados, acelerar o processamento de grafos nesses sistemas não é uma tarefa trivial: aplicações de grafos são caracterizadas por alto volume de acesso irregular à memória e que varia com a estrutura dos grafos, fazendo com que muitas vezes elas não alcancem seus picos de performance quando executadas em GPUs. Nesses casos, a execução em CPU é mais adequada. Felizmente, as estruturas dos grafos podem ser identificadas por meio de métricas de alto nível (e.g., diâmetro e coeficiente médio de clusterização), e elas podem auxiliar o projetista na tomada de decisão de onde executar a aplicação, se em GPU ou em CPU. Neste trabalho, nós propomos uma metodologia que usa essas características de alto nível em uma Regressão Linear para auxiliar na tomada de decisão de onde processar os grafos, em GPU ou CPU. Assim, sempre que um novo grafo precisar ser processado, a decisão de onde processá-lo será tomada com base nessas métricas, evitando qualquer execução adicional dos algoritmos de grafos. Nosso resultados experimentais, considerando 1 GPU e 2 CPUs, mostram que as métricas mais relevantes dos grafos variam conforme os algoritmo e as máquinas onde esses grafos serão executados. Nossa proposta apresentou uma acurácia média de 85% quando aplicado uma Regressão Linear com as características mais relevantes.
Referências
Benesty, J., Chen, J., Huang, Y., and Cohen, I. (2009). Pearson correlation coefficient. In Noise reduction in speech processing, pages 1-4. Springer.
Davidson, A., Baxter, S., Garland, M., and Owens, J. D. (2014). Work-efficient parallel gpu methods for single-source shortest paths. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pages 349-359. IEEE.
Davis, T. A. (2019). Algorithm 1000: Suitesparse: Graphblas: Graph algorithms in the language of sparse linear algebra. ACM Transactions on Mathematical Software (TOMS), 45(4):1-25.
de A. Rocha, H. M. G., Schwarzrock, J., Lorenzon, A. F., and Beck, A. C. S. (2022). Using machine learning to optimize graph execution on numa machines. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pages 1027-1032.
Greiner, J. (1994). A comparison of parallel algorithms for connected components. In Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, pages 16-25.
Harish, P. and Narayanan, P. J. (2007). Accelerating large graph algorithms on the gpu using cuda. In International conference on high-performance computing, pages 197-208. Springer.
Hong, S., Kim, S. K., Oguntebi, T., and Olukotun, K. (2011). Accelerating cuda graph algorithms at maximum warp. Acm Sigplan Notices, 46(8):267-276.
Jia, Y., Lu, V., Hoberock, J., Garland, M., and Hart, J. C. (2012). Edge v. node parallelism for graph centrality metrics. In GPU Computing Gems Jade Edition, pages 15-28. Elsevier.
Khorasani, F., Vora, K., Gupta, R., and Bhuyan, L. N. (2014). Cusha: vertex-centric graph processing on gpus. In Proceedings of the 23rd international symposium on High-performance parallel and distributed computing, pages 239-252.
Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data.
Lorenzon, A. F. and Beck Filho, A. C. S. (2019). Parallel computing hits the power wall: principles, challenges, and a survey of solutions. Springer Nature.
Lorenzon, A. F., Souza, J. D., and Beck, A. C. S. (2017). Laant: A library to automatically optimize edp for openmp applications. In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017, pages 1229-1232. IEEE.
Luo, L., Wong, M., and Hwu, W.-m. (2010). An effective gpu implementation of breadth-first search. In Design Automation Conference, pages 52-55. IEEE.
Mofrad, M. H., Melhem, R., Ahmad, Y., and Hammoud, M. (2020). Graphite: a numa-aware hpc system for graph analytics based on a new mpi* x parallelism model. Proceedings of the VLDB Endowment, 13(6):783-797.
Moori, M. K., Rocha, H. M. G. d. A., Schwarzrock, J., Lorenzon, A. F., and Beck, A. C. S. (2021). Aumentando a eficiência na execução de algoritmos de grafos em hpc. In Anais do XXII Simpósio em Sistemas Computacionais de Alto Desempenho, pages 132-143. SBC.
Rocha, H. M. G. d. A., Schwarzrock, J., Lorenzon, A. F., and Beck, A. C. S. (2021). Boosting graph analytics by tuning threads and data affinity on numa systems. In PDP, pages 161-168. IEEE.
Roy, A., Mihailovic, I., and Zwaenepoel, W. (2013). X-stream: Edge-centric graph processing using streaming partitions. page 472-488.
Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., and Özsu, M. T. (2020). The ubiquity of large graphs and surprising challenges of graph processing: extended survey. The VLDB Journal, 29(2):595-618.
Shun, J. and Blelloch, G. E. (2013). Ligra: a lightweight graph processing framework for shared memory. In ACM PPoPP, pages 135-146.
Staudt, C. L., Sazonovs, A., and Meyerhenke, H. (2016). Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508-530.
Sun, J., Vandierendonck, H., and Nikolopoulos, D. S. (2017). Graphgrind: Addressing load imbalance of graph partitioning. In Proceedings of the International Conference on Supercomputing, pages 1-10.
Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., and Owens, J. D. (2016). Gunrock: A high-performance graph processing library on the gpu. In Proceedings of the 21st ACM SIGPLAN symposium on principles and practice of parallel programming, pages 1-12.
Yang, C., Buluç, A., and Owens, J. D. (2022). Graphblast: A high-performance linear algebra-based graph framework on the gpu. ACM Transactions on Mathematical Software (TOMS), 48(1):1-51.
Zhang, K., Chen, R., and Chen, H. (2015). Numa-aware graph-structured analytics. SIGPLAN Not., 50(8):183-193.