Implementação Paralela de Múltiplos K-Means em GPU - Bueno, Walter; Silva, Olavo; Nacif, José A.; Ferreira, Ricardo (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), 2024)
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.