Implementações Eficientes de Random Forest em FPGA de Baixo Custo para Internet das Coisas e Computação de Borda
Resumo
Random Forest é uma abordagem robusta e amplamente utilizada em aprendizado de máquina. Embora existam diversas implementações paralelas em FPGA, não há estudos comparativos entre essas abordagens. Neste trabalho, comparamos implementações baseadas em multiplexadores, equações e tabelas, utilizando diferentes modelos de FPGAs. Demonstramos que, dependendo da ferramenta de síntese utilizada por cada fabricante, um tipo de descrição pode ser mais apropriado. Esta pesquisa propõe uma avaliação sistemática dessas implementações, com foco na redução de recursos para aplicações em computação de borda e Internet das Coisas. Os resultados indicam que é possível obter uma redução de até 43 vezes nos recursos utilizados, sem comprometer a acurácia. Além das técnicas tradicionais, exploramos também quantização, diagramas de decisão binária, algoritmos de agrupamento k-means e Random Forest com dois níveis.Referências
Amato, F., Barbareschi, M., Casola, V., Mazzeo, A., and Romano, S. (2013). Towards automatic generation of hardware classifiers. In Algorithms and Architectures for Parallel Processing (ICA3PP). Springer.
Asuncion, A. and Newman, D. (2007). Uci machine learning repository.
Bragança, L., Canesche, M., Penha, J., 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). IEEE.
Bueno, W., , Barros, O., Nacif, J., and Ferreira, R. (2024a). Implementação paralela de múltiplos k-means em gpu. In Simpósio em Sistemas Computacionais de Alto Desempenho.
Bueno, W., da Silva, O., Nacif, J., and Ferreira, R. (2024b). Redução de dimensionalidade para Árvores aleatórias. In Workshop de Iniciação Científica - Simpósio em Sistemas Computacionais de Alto Desempenho.
Dávila-Rodríguez, I.-A., Nuño-Maganda, M.-A., Hernández-Mier, Y., and Polanco-Martagón, S. (2019). Decision-tree based pixel classification for real-time citrus segmentation on fpga. In Int Conf on ReConFigurable Computing and FPGAs. IEEE.
Ikeda, T., Sakurada, K., Nakamura, A., Motomura, M., and Takamaeda-Yamazaki, S. (2020). Hardware/algorithm co-optimization for fully-parallelized compact decision tree ensembles on fpgas. In Applied Reconfigurable Computing(ARC). Springer.
Jinguji, A., Sato, S., and Nakahara, H. (2018). An fpga realization of a random forest with k-means clustering using a high-level synthesis design. IEICE TRANSACTIONS on Information and Systems, 101(2):354–362.
Lin, X., Blanton, R. S., and Thomas, D. E. (2017). Random forest architectures on fpga for multiple applications. In Great Lakes Symposium on VLSI.
Lin, Z., Sinha, S., and Zhang, W. (2019). Towards efficient and scalable acceleration of online decision tree learning on fpga. In IEEE FCCM.
Murtovi, A., Bainczyk, A., Nolte, G., Schlüter, M., and Steffen, B. (2023). Forest gump: a tool for verification and explanation. International Journal on Software Tools for Technology Transfer, pages 1–13.
Nakahara, H., Jinguji, A., Sato, S., and Sasao, T. (2017). A random forest using a multi-valued decision diagram on an fpga. In IEEE Symposium on multiple-valued logic.
Oberg, J., Eguro, K., Bittner, R., and Forin, A. (2012). Random decision tree body part recognition using fpgas. In Field Programmable Logic and Applications (FPL). IEEE.
Owaida, M., Zhang, H., Zhang, C., and Alonso, G. (2017). Scalable inference of decision tree ensembles: Flexible design for cpu-fpga platforms. In 2017 27th International Conference on Field Programmable Logic and Applications (FPL), pages 1–8. IEEE.
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., da Silva, A., Barros, O., Moreira, I., Nacif, J., and Ferreira, R. (2023). Avaliação de estilos de código para árvores de decisão em gpu com microbenchmarks. In Simpósio em Sistemas Computacionais de Alto Desempenho.
Penha, J. C., Bragança, L., Canesche, M., Comarela, G., Nacif, J. A. M., and Ferreira, R. (2018). A gpu/fpga-based k-means clustering using a parameterized code generator. In Symp on High Performance Computing Systems (WSCAD). IEEE.
Qu, Y. R. and Prasanna, V. K. (2014). Scalable and dynamically updatable lookup engine for decision-trees on fpga. In High Performance Extreme Computing Conf. IEEE.
Saqib, F., Dutta, A., Plusquellic, J., Ortiz, P., and Pattichis, M. S. (2013). Pipelined decision tree classification accelerator implementation in fpga (dt-caif). IEEE Transactions on Computers, 64(1):280–285.
Shah, M., Neff, R., Wu, H., Minutoli, M., Tumeo, A., and Becchi, M. (2022). Accelerating random forest classification on gpu and fpga. In Proceedings of the 51st International Conference on Parallel Processing, pages 1–11.
Silva, O. A., Silva, A. K., Moreira, Í. G., Nacif, J. A., and Ferreira, R. S. (2023). Rdsf: Everything at same place all at once-a random decision single forest. In 2023 XIII Brazilian Symposium on Computing Systems Engineering (SBESC), pages 1–6. IEEE.
UFV (2024). Geradores de código para random forest. [link].
Van Essen, B., Macaraeg, C., Gokhale, M., and Prenger, R. (2012). Accelerating a random forest classifier: Multi-core, gp-gpu, or fpga? In IEEE FCCM.
Wang, H., Wu, Z., Wang, X., Bian, L., and Jin, H. (2022). Hardgbm: A framework for accurate and hardware-efficient gradient boosting machines. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
Zhao, S. and Chen, S. (2018). A discretization method for floating-point number in fpga-based decision tree accelerator. In IEEE Conf on Computer and Communications.
Zhao, S., Chen, S., Yang, H., Wang, F., and Wei, Z. (2021). Rf-risa: A novel flexible random forest accelerator based on fpga. Journal of Parallel and Distributed Computing.
Zhu, M., Luo, J., Mao, W., and Wang, Z. (2022). An efficient fpga-based accelerator for deep forest. In Int Symp on Circuits and Systems (ISCAS). IEEE.
Asuncion, A. and Newman, D. (2007). Uci machine learning repository.
Bragança, L., Canesche, M., Penha, J., 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). IEEE.
Bueno, W., , Barros, O., Nacif, J., and Ferreira, R. (2024a). Implementação paralela de múltiplos k-means em gpu. In Simpósio em Sistemas Computacionais de Alto Desempenho.
Bueno, W., da Silva, O., Nacif, J., and Ferreira, R. (2024b). Redução de dimensionalidade para Árvores aleatórias. In Workshop de Iniciação Científica - Simpósio em Sistemas Computacionais de Alto Desempenho.
Dávila-Rodríguez, I.-A., Nuño-Maganda, M.-A., Hernández-Mier, Y., and Polanco-Martagón, S. (2019). Decision-tree based pixel classification for real-time citrus segmentation on fpga. In Int Conf on ReConFigurable Computing and FPGAs. IEEE.
Ikeda, T., Sakurada, K., Nakamura, A., Motomura, M., and Takamaeda-Yamazaki, S. (2020). Hardware/algorithm co-optimization for fully-parallelized compact decision tree ensembles on fpgas. In Applied Reconfigurable Computing(ARC). Springer.
Jinguji, A., Sato, S., and Nakahara, H. (2018). An fpga realization of a random forest with k-means clustering using a high-level synthesis design. IEICE TRANSACTIONS on Information and Systems, 101(2):354–362.
Lin, X., Blanton, R. S., and Thomas, D. E. (2017). Random forest architectures on fpga for multiple applications. In Great Lakes Symposium on VLSI.
Lin, Z., Sinha, S., and Zhang, W. (2019). Towards efficient and scalable acceleration of online decision tree learning on fpga. In IEEE FCCM.
Murtovi, A., Bainczyk, A., Nolte, G., Schlüter, M., and Steffen, B. (2023). Forest gump: a tool for verification and explanation. International Journal on Software Tools for Technology Transfer, pages 1–13.
Nakahara, H., Jinguji, A., Sato, S., and Sasao, T. (2017). A random forest using a multi-valued decision diagram on an fpga. In IEEE Symposium on multiple-valued logic.
Oberg, J., Eguro, K., Bittner, R., and Forin, A. (2012). Random decision tree body part recognition using fpgas. In Field Programmable Logic and Applications (FPL). IEEE.
Owaida, M., Zhang, H., Zhang, C., and Alonso, G. (2017). Scalable inference of decision tree ensembles: Flexible design for cpu-fpga platforms. In 2017 27th International Conference on Field Programmable Logic and Applications (FPL), pages 1–8. IEEE.
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., da Silva, A., Barros, O., Moreira, I., Nacif, J., and Ferreira, R. (2023). Avaliação de estilos de código para árvores de decisão em gpu com microbenchmarks. In Simpósio em Sistemas Computacionais de Alto Desempenho.
Penha, J. C., Bragança, L., Canesche, M., Comarela, G., Nacif, J. A. M., and Ferreira, R. (2018). A gpu/fpga-based k-means clustering using a parameterized code generator. In Symp on High Performance Computing Systems (WSCAD). IEEE.
Qu, Y. R. and Prasanna, V. K. (2014). Scalable and dynamically updatable lookup engine for decision-trees on fpga. In High Performance Extreme Computing Conf. IEEE.
Saqib, F., Dutta, A., Plusquellic, J., Ortiz, P., and Pattichis, M. S. (2013). Pipelined decision tree classification accelerator implementation in fpga (dt-caif). IEEE Transactions on Computers, 64(1):280–285.
Shah, M., Neff, R., Wu, H., Minutoli, M., Tumeo, A., and Becchi, M. (2022). Accelerating random forest classification on gpu and fpga. In Proceedings of the 51st International Conference on Parallel Processing, pages 1–11.
Silva, O. A., Silva, A. K., Moreira, Í. G., Nacif, J. A., and Ferreira, R. S. (2023). Rdsf: Everything at same place all at once-a random decision single forest. In 2023 XIII Brazilian Symposium on Computing Systems Engineering (SBESC), pages 1–6. IEEE.
UFV (2024). Geradores de código para random forest. [link].
Van Essen, B., Macaraeg, C., Gokhale, M., and Prenger, R. (2012). Accelerating a random forest classifier: Multi-core, gp-gpu, or fpga? In IEEE FCCM.
Wang, H., Wu, Z., Wang, X., Bian, L., and Jin, H. (2022). Hardgbm: A framework for accurate and hardware-efficient gradient boosting machines. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
Zhao, S. and Chen, S. (2018). A discretization method for floating-point number in fpga-based decision tree accelerator. In IEEE Conf on Computer and Communications.
Zhao, S., Chen, S., Yang, H., Wang, F., and Wei, Z. (2021). Rf-risa: A novel flexible random forest accelerator based on fpga. Journal of Parallel and Distributed Computing.
Zhu, M., Luo, J., Mao, W., and Wang, Z. (2022). An efficient fpga-based accelerator for deep forest. In Int Symp on Circuits and Systems (ISCAS). IEEE.
Publicado
23/10/2024
Como Citar
SILVA, Alysson; SILVA, Olavo; MOREIRA, Icaro; NACIF, José A.; FERREIRA, Ricardo.
Implementações Eficientes de Random Forest em FPGA de Baixo Custo para Internet das Coisas e Computação de Borda. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 25. , 2024, São Carlos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 49-60.
DOI: https://doi.org/10.5753/sscad.2024.244782.
