优化决策树的最坏情况执行时间，提升嵌入式系统实时性能
WCDT: Systematic WCET Optimization for Decision Tree Implementations
- 用路径长度和分支数构建执行时间线性预测模型
- 算法使最坏情况执行时间比未优化版本最多减少17%
- 适合对实时性要求高的嵌入式机器学习部署场景
机器学习模型越来越多地部署在资源受限且有严格时序约束的嵌入式系统中。在此类场景下，必须确保模型的最坏情况执行时间（WCET）以保障安全运行。决策树是一类重要的机器学习模型，也是树基集成模型（如随机森林）的主要组件，常用于资源受限的嵌入式系统。本文提出一种系统化的决策树实现WCET优化方法。为此，我们引入一个线性代理模型，基于路径长度和实际执行的分支数量来估计决策树中各路径的执行时间。我们设计了一种优化算法，可构造出针对该代理模型的WCET最优实现。实验评估表明，与未优化实现相比，该优化算法使分析确定的WCET最高降低17%。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。