Redução Paralela Otimizada para Segmentos Regulares e Irregulares em GPU

• Michel B. Cordeiro UFPR
• Wagner M. Nunan Zola UFPR

DOI: https://doi.org/10.5753/sscad.2024.244797

Resumo

Redução é uma operação que combina todos os elementos de uma coleção aplicando uma operação binária, como soma, máximo ou mínimo, a todos os elementos para obter um único valor resultante. Este trabalho tem como objetivo investigar estratégias de implementação para redução segmentada em GPUs. Técnicas existentes de redução segmentada costumam ter um desempenho consistente, mas são relativamente ineficientes quando aplicadas a segmentos irregulares. Essas técnicas são frequentemente otimizadas para cargas de trabalho específicas e, como resultado, podem apresentar desempenho degradado para certos conjuntos de dados, especialmente quando os segmentos têm tamanhos muito variados. O algoritmo apresentado neste artigo utiliza três estratégias diferentes para lidar com tamanhos variados de segmentos e tem a capacidade de escolher a melhor estratégia em tempo de execução para otimizar o processamento de cada segmento conforme seu tamanho. O algoritmo proposto oferece um desempenho consistente, alcançando uma aceleração de até 49.47 vezes para segmentos de tamanhos variados e até 12.62 vezes para segmentos de tamanhos regulares, em comparação aos algoritmos de redução segmentada das melhores bibliotecas paralelas em GPU. Além disso, este artigo também explora estratégias para acelerar a redução não segmentada, resultando em uma melhoria de até 1.77 vezes em comparação às outras implementações.

Referências

Che, S., Boyer, M., Meng, J., Tarjan, D., Sheaffer, J. W., Lee, S.-H., and Skadron, K. (2009). Rodinia: A benchmark suite for heterogeneous computing. In 2009 IEEE international symposium on workload characterization (IISWC), pages 44–54. IEEE.

Cordeiro, M. and Zola, W. (2023). KNN paralelo em GPU para grandes volumes de dados com agregação de consultas. In Anais do XXIV Simpósio em Sistemas Computacionais de Alto Desempenho, pages 253–264, Porto Alegre, RS, Brasil. SBC.

Ferraz, S., Dias, V., Teixeira, C. H., Parthasarathy, S., Teodoro, G., and Meira, W. (2024). DuMato: An efficient warp-centric subgraph enumeration system for GPU. Journal of Parallel and Distributed Computing, 191:104903.

Gupta, K., Stuart, J. A., and Owens, J. D. (2012). A study of persistent threads style GPU programming for GPGPU workloads. In 2012 Innovative Parallel Computing (InPar).

Harris, M. (2007). Optimizing parallel reduction in CUDA. Nvidia developer technology.

Johnson, J., Douze, M., and Jégou, H. (2019). Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535–547.

Jradi, W. A. R., do Nascimento, H. A. D., and Martins, W. S. (2018). A fast and generic gpu-based parallel reduction implementation. In 2018 Symposium on High Performance Computing Systems (WSCAD), pages 16–22. IEEE.

Larsen, R. W. and Henriksen, T. (2017). Strategies for regular segmented reductions on gpu. In Proceedings of the 6th ACM SIGPLAN International Workshop on Functional High-Performance Computing, pages 42–52.

Luitjens, J. (2014). Faster parallel reductions on kepler. [link].

Meyer, B., Pozo, A., and Nunan Zola, W. M. (2021). Warp-centric K-nearest neighbor graphs construction on GPU. In 50th International Conference on Parallel Processing Workshop, ICPP Workshops ’21. Association for Computing Machinery.

NVIDIA (2024). CUB. [link].

Thrust (2024). Thrust: The C++ Parallel Algorithms Library. [link].

Warashina, T., Aoyama, K., Sawada, H., and Hattori, T. (2014). Efficient k-nearest neighbor graph construction using mapreduce for large-scale data sets. IEICE TRANSACTIONS on Information and Systems, 97(12):3142–3154.

Zola, W. M. N. and De Bona, L. C. E. (2012). Parallel speculative encryption of multiple AES contexts on GPUs. In 2012 Innovative Parallel Computing (InPar). IEEE.