Accelerating the Training of Tree-Based Machine Learning Algorithms for Edge Systems

Abstract

Tree-based algorithms, such as XGBOOST – an open source implementation of Gradient Boosted Decision Trees (GBDT) – are ubiquitous for many Machine Learning (ML) tasks, especially when dealing with tabular/structured data and requir- ing explainability. As dataset size continues to grow, training ensembles of trees (random forest, XGBOOST, CatBoost, Light- GBM) has been parallelized on multi-core systems, accelerated on GPUs, and distributed on computer clusters. However, FPGA acceleration targeting the training of tree-based ML remains underexplored. Analyzing the tree structure of trained GBDT models, we observe a significant overlap of the features used as nodes at the top levels of the ensemble. Guided by this insight, we modify the training algorithm of GBDT to harness the computational redundancy associated with the top nodes, as well as to create a novel accelerator architecture, FaGBM. For training, FaGBM reduces end-to-end GBDT training latency by up to 2× speedup over NVIDIA Jetson Thor with XGBOOST, LightGBM, and Cat- Boost. Moreover, for GBDT, FaGBM employs a novel adaptive approximate division to compute the split gain, which reduces LUT usage by up to 40K. For Decision Trees training, this paper investigates bit-wise approximate logarithms, resulting in an 87% reduction in DSP usage in FPGAs compared to a fixed- point implementation. The experiments further demonstrate that FaGBM preserves model accuracy while achieving significant energy efficiency over optimized multi-core and GPU baselines.