Otimização de modelos de aprendizado de máquina em dispositivos de borda: Random Forest e XGBoost

Abstract

A crescente demanda por processamento inteligente em dispositivos de borda (edge computing) tem impulsionado o desenvolvimento de técnicas de Tiny Machine Learning (TinyML), que visam executar algoritmos de aprendizado de máquina em plataformas com severas restrições de energia, memória e capacidade computacional. Neste contexto, os Field-Programmable Gate Arrays (FPGAs) emergem como uma alternativa promissora, oferecendo equilíbrio único entre eficiência energética, desempenho e reconfigurabilidade. No entanto, a implementação eficiente de modelos de aprendizado de máquina em FPGAs de borda enfrenta desafios significativos, incluindo a lacuna entre ferramentas de alto nível como scikit-learn e XGBoost e as descrições de hardware de baixo nível necessárias para programação de FPGAs (como Verilog e VHDL). Esta dissertação propõe um conjunto integrado de quatro ferramentas que automatiza o fluxo completo desde o modelo treinado até o circuito otimizado em FPGA, aplicando otimizações em múltiplos níveis: poda de árvores, quantização durante o mapeamento e poda de circuitos a nível de Look-up Tables (LUTs). A primeira ferramenta, XGB2GPU, realiza exploração paralela do espaço de poda de modelos XGBoost utilizando GPUs, implementando três estratégias topológicas (Flat, Linear e Exponencial) e alcançando ganho de desempenho de 900× a 3000× em comparação com implementações em CPU. A segunda ferramenta, RDSF, mapeia modelos Random Forest em FPGAs utilizando Binary Decision Diagrams (BDDs) para otimização de funções Booleanas. A terceira ferramenta, TreeLUT, estendida neste trabalho, mapeia modelos XGBoost aplicando quantização em duas etapas (dados de entrada e pesos das folhas), incluindo contabilização completa dos recursos de hardware (módulos de quantização e argmax) com geração eficiente do código Verilog. A implementação das árvores baseada em multiplexadores reduziu o uso de LUTs em aproximadamente 20% comparada à abordagem por equações. A quarta ferramenta, Go-Fast, implementa simulação aproximada acelerada por GPU para poda de circuitos baseados em LUTs, alcançando ganhos de desempenho de cinco ordens de magnitude (10^5) em comparação com simuladores de Verilog do estado da arte como Verilator. Os resultados demonstraram que é possível alcançar reduções de área: até 90% via poda de árvores mantendo degradação de acurácia inferior a 5% em alguns casos, e até 41% via poda de circuitos com erro controlado. Adicionalmente, demonstrou-se que simulação com grandes volumes de estímulos (2^30 amostras) revela configurações superiores às encontradas com conjuntos reduzidos (2^14 amostras), evidenciando a importância da amostragem ampla. A principal contribuição deste trabalho reside na demonstração de que otimizações em diferentes níveis de abstração (modelo, mapeamento e circuito) podem ser compostas de forma conjunta para alcançar implementações eficientes, reduzindo significativamente a barreira entre ferramentas de alto nível e implementações em hardware reconfigurável para aplicações de TinyML. Palavras-chave: Tiny Machine Learning; FPGA; XGBoost ; Random Forest ; Poda de Árvores ; Computação Aproximada ; GPU ; Otimização de Hardware.The growing demand for intelligent processing in edge computing devices has driven the development of Tiny Machine Learning (TinyML) techniques, which aim to execute machine learning algorithms on platforms with severe energy, memory, and computational capacity constraints. In this context, Field-Programmable Gate Arrays (FPGAs) emerge as a promising alternative, offering a unique balance between energy efficiency, performance, and reconfigurability. However, the efficient implementation of machine learning models on FPGAs faces significant challenges, including the gap between high-level tools like scikit-learn and XGBoost and the low- level hardware descriptions required for FPGA programming (such as Verilog and VHDL). This dissertation proposes an integrated set of four tools that automates the complete flow from the trained model to the optimized circuit on FPGA, applying optimizations at multiple levels: tree pruning, quantization during mapping, and circuit pruning at the Look-up Tables (LUTs) level. The first tool, XGB2GPU, performs parallel exploration of the XGBoost model pruning space using GPUs, implementing three topological strategies (Flat, Linear, and Exponential) and achieving speedups of 900x to 3000x compared to CPU implementations. The second tool, RDSF, maps Random Forest models onto FPGAs using Binary Decision Diagrams (BDDs) for Boolean function optimization. The third tool, TreeLUT, extended in this work, maps XGBoost models by applying two-stage quantization (input data and leaf weights), including full accounting of hardware resources (quantization modules and argmax). The fourth tool, Go-Fast, implements GPU-accelerated approximate simulation for LUT-based circuit pruning, achieving speedups of five orders of magnitude (10^5) compared to traditional simulators like Verilator. The results demonstrated that substantial area reductions are achievable: up to 90% via tree pruning while maintaining accuracy degradation below 5% in some cases, and up to 41% via circuit pruning with controlled error. The multiplexer-based implementation reduced LUT usage by approximately 20% compared to the equation-based approach. Additionally, it was demonstrated that simulation with large volumes of stimuli (2^30 samples) reveals configurations superior to those found with reduced sets (2^14 samples), highlighting the importance of broad sampling. The main contribution of this work lies in demonstrating that optimizations at different abstraction levels (model, mapping, and circuit) can be jointly composed to achieve efficient implementations, significantly reducing the barrier between high-level tools and reconfigurable hardware implementations for TinyML applications. Keywords: Tiny Machine Learning; FPGA ; XGBoost; Random Forest; Tree Pruning; Approximate Computing; GPU; Hardware Optimization