Efficient Realization of Decision Trees for Real-Time Inference Chen, Kuan-Hsun Su, Chiahui Hakert, Christian Buschjäger, Sebastian Lee, Chao-Lin Lee, Jenq-Kuen Morik, Katharina Chen, Jian-Jia <jats:p>For timing-sensitive edge applications, the demand for efficient lightweight machine learning solutions has increased recently. Tree ensembles are among the state-of-the-art in many machine learning applications. While single decision trees are comparably small, an ensemble of trees can have a significant memory footprint leading to cache locality issues, which are crucial to performance in terms of execution time. In this work, we analyze memory-locality issues of the two most common realizations of decision trees, i.e., native and if-else trees. We highlight that both realizations demand a more careful memory layout to improve caching behavior and maximize performance. We adopt a probabilistic model of decision tree inference to find the best memory layout for each tree at the application layer. Further, we present an efficient heuristic to take architecture-dependent information into account thereby optimizing the given ensemble for a target computer architecture. Our code-generation framework, which is freely available on an open-source repository, produces optimized code sessions while preserving the structure and accuracy of the trees. With several real-world data sets, we evaluate the elapsed time of various tree realizations on server hardware as well as embedded systems for Intel and ARM processors. Our optimized memory layout achieves a reduction in execution time up to 75 % execution for server-class systems, and up to 70 % for embedded systems, respectively.</jats:p> Association for Computing Machinery (ACM) 2022 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_6501 https://ris.uni-paderborn.de/record/66209 Chen K-H, Su C, Hakert C, et al. Efficient Realization of Decision Trees for Real-Time Inference. <i>ACM Transactions on Embedded Computing Systems</i>. 2022;21(6):1-26. doi:<a href="https://doi.org/10.1145/3508019">10.1145/3508019</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3508019 info:eu-repo/semantics/altIdentifier/issn/1539-9087 info:eu-repo/semantics/altIdentifier/issn/1558-3465 info:eu-repo/semantics/closedAccess