Register Your Forests: Decision Tree Ensemble Optimization by Explicit CPU Register Allocation
This work addresses performance bottlenecks for resource-constrained embedded setups, but it is incremental as it builds on existing code generation and optimization techniques.
The paper tackles the problem of inefficient CPU register usage in decision tree ensemble inference, especially in embedded systems, by presenting a code generation approach that directly produces machine assembly from high-level models, resulting in performance improvements of up to about 1.6 times.
Bringing high-level machine learning models to efficient and well-suited machine implementations often invokes a bunch of tools, e.g.~code generators, compilers, and optimizers. Along such tool chains, abstractions have to be applied. This leads to not optimally used CPU registers. This is a shortcoming, especially in resource constrained embedded setups. In this work, we present a code generation approach for decision tree ensembles, which produces machine assembly code within a single conversion step directly from the high-level model representation. Specifically, we develop various approaches to effectively allocate registers for the inference of decision tree ensembles. Extensive evaluations of the proposed method are conducted in comparison to the basic realization of C code from the high-level machine learning model and succeeding compilation. The results show that the performance of decision tree ensemble inference can be significantly improved (by up to $\approx1.6\times$), if the methods are applied carefully to the appropriate scenario.