WCDT: Systematic WCET Optimization for Decision Tree Implementations
This addresses timing constraints for embedded systems using decision trees, but it is incremental as it builds on existing WCET optimization methods.
The paper tackles the problem of optimizing worst-case execution time (WCET) for decision tree implementations on resource-constrained embedded systems, achieving up to 17% improvement in analytically determined WCET compared to unoptimized implementations.
Machine-learning models are increasingly deployed on resource-constrained embedded systems with strict timing constraints. In such scenarios, the worst-case execution time (WCET) of the models is required to ensure safe operation. Specifically, decision trees are a prominent class of machine-learning models and the main building blocks of tree-based ensemble models (e.g., random forests), which are commonly employed in resource-constrained embedded systems. In this paper, we develop a systematic approach for WCET optimization of decision tree implementations. To this end, we introduce a linear surrogate model that estimates the execution time of individual paths through a decision tree based on the path's length and the number of taken branches. We provide an optimization algorithm that constructively builds a WCET-optimal implementation of a given decision tree with respect to this surrogate model. We experimentally evaluate both the surrogate model and the WCET-optimization algorithm. The evaluation shows that the optimization algorithm improves analytically determined WCET by up to $17\%$ compared to an unoptimized implementation.