Implementação Paralela de Múltiplos K-Means em GPU

• Walter Bueno UFV
• Olavo Silva UFV
• José A. Nacif UFV
• Ricardo Ferreira UFV

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

Resumo

O algoritmo K-means possui intensidade aritmética O(3K) e seu desempenho é limitado pela memória para valores pequenos de k. Implementações paralelas utilizam valores altos de k para obter um melhor desempenho. Entretanto, a maioria dos problemas práticos busca valores baixos de k, ou seja, poucos grupos. Outro desafio é encontrar o melhor valor de k. Neste trabalho, propomos uma implementação paralela eficiente em GPU que explora múltiplos valores de k simultaneamente, utilizando adequadamente as arquiteturas de GPU para maximizar o desempenho. Comparada com a implementação da Nvidia Rapids CuML, nossa implementação mostrou ganhos de até 140 vezes em aceleração, para valores baixos de k, onde múltiplas execuções simultâneas de diferentes k são realizadas. O K-means também pode ser usado para redução de dimensionalidade. Apresentamos uma implementação com múltiplas chamadas do K-means para buscar quais atributos são mais adequados para a redução de dimensionalidade. Mostramos um exemplo de redução de um conjunto de dados com 18 atributos numéricos para uma codificação de 3 bits com uma pequena perda de acurácia, ou seja, uma redução de 96 vezes e aceleração de 790 vezes.

Referências

Aloise, D., Deshpande, A., Hansen, P., and Popat, P. (2009). Np-hardness of euclidean sum-of-squares clustering. Machine learning, 75:245–248.

Baydoun, M., Dawi, M., and Ghaziri, H. (2016). Enhanced parallel implementation of the k-means clustering algorithm. In 2016 3rd International Conference on Advances in Computational Tools for Engineering Applications (ACTEA), pages 7–11. IEEE.

Bhimani, J., Leeser, M., and Mi, N. (2015). Accelerating k-means clustering with parallel implementations and gpu computing. In IEEE HPEC.

Boutsidis, C., Zouzias, A., Mahoney, M. W., and Drineas, P. (2014). Randomized dimensionality reduction for k-means clustering. IEEE Trans on Information Theory.

Bragança, L., Canesche, M., Penha, J., Carvalho, W., Comarela, G., Nacif, J. A. M., and Ferreira, R. (2021). An open source custom k-means generator for aws cloud fpga accelerators. In Brazilian Symposium on Computing Systems Engineering (SBESC).

Bueno, W. (2024). Gerador de código multik para k-means. [link].

Bueno, W., da Silva, O., Nacif, J., and Ferreira, R. (2024). Redução de dimensionalidade para Árvores aleatórias. In Workshop de Iniciação Científica - Simpósio em Sistemas Computacionais de Alto Desempenho.

Cheng, J., Grossman, M., and McKercher, T. (2014). Professional CUDA c programming. John Wiley & Sons.

da Silva Alves, M., Silva, L. B., Penha, J., Ferreira, R., and Nacif, J. A. M. (2023). Kcgra– uma arquitetura reconfigurável de domínio específico para k-means. In Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD). SBC.

He, G., Vialle, S., and Baboulin, M. (2022). Parallel and accurate k-means algorithm on cpu-gpu architectures for spectral clustering. Concurrency and Computation: Practice and Experience, 34(14):e6621.

Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., and Wu, A. Y. (2002). An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence, 24(7):881–892.

Klöckner, A., Pinto, N., Lee, Y., Catanzaro, B., Ivanov, P., and Fasih, A. (2012). PyCUDA and PyOpenCL: A Scripting-Based Approach to GPU Run-Time Code Generation. Parallel Computing, 38(3):157–174.

Li, M., Frank, E., and Pfahringer, B. (2023). Large scale k-means clustering using gpus. Data Mining and Knowledge Discovery, 37(1):67–109.

Lutz, C., Breß, S., Rabl, T., Zeuch, S., and Markl, V. (2018). Efficient and scalable k-means on gpus. Datenbank-Spektrum, 18:157–169.

Nvidia (2024). cuml gpu-accelerated machine learning. [link].

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. (2011). Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825–2830.

Penha, J. C., Bragança, L., Coelho, K., Canesche, M., Silva, J., Comarela, G., Nacif, J. A. M., and Ferreira, R. (2018). A gpu/fpga-based k-means clustering using a parameterized code generator. In High Performance Computing Systems (WSCAD). IEEE.

Volkov, V. (2010). Better performance at lower occupancy. In Proceedings of the GPU technology conference, GTC, volume 10, page 16. San Jose, CA.

Whiteson, D. (2014). SUSY. UCI Machine Learning Repository. DOI: 10.24432/C54606.

Xia, S., Peng, D., Meng, D., Zhang, C., Wang, G., Giem, E., Wei, W., and Chen, Z. (2020). Ball k k-means: Fast adaptive clustering with no bounds. IEEE transactions on pattern analysis and machine intelligence, 44(1):87–99.