KCGRA – Uma Arquitetura Reconfigurável de Domínio Específico para K-means

• Matheus da Silva Alves UFV
• Lucas Bragança Silva UFV
• Jerônimo Penha UFV
• Ricardo Ferreira UFV
• José Augusto M. Nacif UFV

DOI: https://doi.org/10.5753/wscad.2023.235892

Resumo

Este trabalho apresenta um novo acelerador reconfigurável de domínio específico para o algoritmo K-Means. O acelerador pode ser totalmente reconfigurado em menos de 2,34 milissegundos para explorar diversos valores de agrupamentos e atributos e alcança até 668 Gop/s de desempenho. O acelerador foi validado em FPGAs de alto desempenho com memórias HBM. A reconfiguração dinâmica não reduz o desempenho em comparação com as implementações estáticas em HLS e RTL, que demandam horas para serem reconfiguradas. O acelerador foi construído usando um gerador genérico de CGRA parametrizado e possui um formato intermediário para sua reconfiguração de forma transparente.

Referências

Abdelrahman, T. S. (2016). Accelerating k-means clustering on a tightly-coupled processor-fpga heterogeneous system. In 2016 IEEE 27th International Conference on Applicationspecific Systems, Architectures and Processors (ASAP), pages 176–181.

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).

Choi, Y.-M. and So, H. K.-H. (2014). Map-reduce processing of k-means algorithm with fpga-accelerated computer cluster. In IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE.

Cong, J. and et al. (2018). Understanding performance differences of fpgas and gpus. In 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 93–96. IEEE.

Dias, L. A., Ferreira, J. C., and Fernandes, M. A. (2020). Parallel implementation of k-means algorithm on fpga. IEEE Access, 8:41071–41084.

Gorgin, S., Javaheri, D., and Lee, J.-A. (2022). An energy-efficient k-means clustering fpga accelerator via most-significant digit first arithmetic. In IEEE ICFPT.

Jain, A., Goel, P., Aggarwal, S., Fell, A., and Anand, S. (2020). Symmetric k-means for deep neural network compression and hardware acceleration on fpgas. IEEE Journal of Selected Topics in Signal Processing, 14(4):737–749.

Li, Y., Zhao, K., Chu, X., and Liu, J. (2013). Speeding up k-means algorithm by gpus. Journal of Computer and System Sciences, 79(2):216–229.

Lloyd, S. (1982). Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137.

Lopes, J. D., de Sousa, J. T., Neto, H., and Véstias, M. (2017). K-means clustering on cgra. In International Conference on Field Programmable Logic and Applications (FPL).

Paulino, N., Ferreira, J. C., and Cardoso, J. M. (2020). Optimizing opencl code for performance on fpga: k-means case study with integer data sets. IEEE Access.

Penha, J., Bragança, L., Coelho, K., Canesche, M., Nacif, J. A. M., and Ferreira, R. (2018). A gpu/fpga-based k-means clustering using a parameterized code generator. In Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD).

Silva, L., Canesche, M., Ferreira, R., and Nacif, J. A. (2020). Hpcgra an orthogonal designed cgra generator for high performance spatial accelerators. In XXI Simpósio em Sistemas Computacionais de Alto Desempenho (WSCAD).

Silva, L., Penha, J., Ribeiro, D., Silva, A., Nacif, J., and Ferreira, R. (2022). Hpyc-fpga - integração de aceleradores em fpga de alto desempenho com python para jupyter notebooks. In XXIII Simpósio em Sistemas Computacionais de Alto Desempenho.

Tang, Q. Y. and Khalid, M. A. (2016). Acceleration of k-means algorithm using altera sdk for opencl. ACM Trans on Reconfigurable Technology and Systems (TRETS), 10(1).