Code Generation from Regression Trees for Microsecond-Scale Decisions in Operating Systems

Abstract

In today's world of heterogeneous server hardware, deciding on suitable task and data placements is a far from trivial undertaking. Depending on system load and application behaviour, some compute and memory assignments improve performance, while others impair it. Yet, these increasingly complex decisions must be made quickly: spending 5 ms just to decide on a placement that reduces latency by merely 2 ms is a net loss. So far, developers have resorted to hand-crafted heuristics for this task. While these are founded in real-world experience, they are hard to reason about, hard to adjust, and rarely free from bugs or inefficiencies. In our opinion, a transition towards model-guided placement decisions is due - i.e., using machine learning models to predict compute/data placement from system status and application requirements. To this end, we examine the suitability of regression trees for fast (nano- to microsecond-scale) runtime decisions within operating systems. We examine three types of trees / forests with three different code generation methods, and show that, depending on tree complexity and data type, median latency is 23 ns to 79 &mgr;s per placement decision. By using C++ template expansion to transform entire trees into equivalent machine code, we are able to reduce inference latency by up to an order of magnitude compared to conventional approaches, while (for 8-bit integer data) also halving the code size. At the same time, trees are compact and can easily be generated from, e.g., Python-based machine learning models.