> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/toward-reconfigurable-kernel-datapaths-with-learned-optimizations.md).

# Toward Reconfigurable Kernel Datapaths with Learned Optimizations

* Problem: OS kernels are under stress! (diversifying applications and hardware) 
  * Heterogenous hardware such as SmartNICs, TPU and GPU, along with their diverging computer units, memory hierarchy, and accelerators 
  * Applications are evolving: distinct characteristics, latency, different memory access patterns 
* Kernel optimizations today
  * **Key limitations with today's kernel optimizations** 
    * **Ad hoc heuristics**, without guarantees they'll always work 
    * **One-size-fit-all optimizations** for all apps and workloads 
    * **Cannot generalize to new** apps, workloads, and hardware
* **Research agenda** 
  * **Goal**: better, principled kernel optimizations 
    * Tailored for each app, workload, or hardware
    * Adapt to new scenarios 
    * Minimize hand-tuning and benchmarking 
  * Approach: leverage machine learning (ML) 
* Why ML?
  * Four types of benefits 
    * **Reduce unnecessary kernel monitoring** 
      * e.g. reduce page faults caused by memory affinity monitoring 
    * **Better and more robust heuristics** 
      * e.g., use-cases in ML based page prefetching, task migration, I/O scheduling, and congestion control etc. 
    * **Generalization to unseen scenarios** 
      * E.g. ML prefetcher could do online adaptation to new access patterns 
    * **Cross-application optimizations** 
      * E.g., enable efficient communication between producer and consumers 
  * Kernel-ML example 
    * Swap area page prefetching 
      * Baseline #1: linux readahead
        * Only captures sequential patterns 
      * Baseline #2: majority-vote based prefetcher (leap)
        * Captures sequential and striding patterns 
      * Ours: decision tree based prefetcher 
        * Captures more complex patterns 
    * Workloads: contain non-sequential / striding patterns 
      * E.g., video resizing and matrix convolution 
      * Each workload runs in a dedicated cgroup 
    * Better performance on multiple metrics 
      * **Better coverage**: higher hit-rate and less access overhead 
      * **Better accuracy**: less memory pollution by irrelevant pages 
      * **Better execution time**: workload completes faster 

But, how?

* **A range of research questions** exist:
  * What should be the in-kernel ML infrastructure? 
  * How to rearchitect the kernel to use learned decisions? 
  * How to manage a diverse range of ML models? 
* Our proposal: reconfigurable kernel datapaths 
  * Architect kernel datapaths with reconfigurable match tables (RMT)
    * **Matches** check execution context (e.g., page faults)
    * **Actions** perform data collection and adaptive decisions 
    * **Kernel ML lib** performs learning and inference (e.g., NNs)  
    * Complexity and behavior is analyzed by the RMT verifier for performance and safty guarantees 

![](/files/DAVKNEpbKXcrHLrkjCwE)

### Challenges 

* **Challenge #1: Infrastructure for in kernel ML** 
  * Applications in user space can easily build up ML models, however, if we want to deploy the ML to interfere kernel and achieve run-time reconfigurability --> need an infrastructure 
    * Data monitoring and collection 
    * Kernel ML deployment 
    * Model management 
  * Even with eBPF, existing kernel does not support such functionality 
  * Thus, we need to build our own in-kernel RMT infrastructure to interfere critical kernel decisions 
* **Proposal #1: in-kernel RMT virtual machine** 
  * Achieve dynamic reconfigurability 
  * Steps 
    * RMT program: initializing and inserting the match-action table 
    * Verified, and compiled into byte code and further compiled into machine code 
    * Main block: match-action table 
      * K-V map manner 
      * Define key decision point in kernel data path 
      * Match: kernel reacts 
      * Entry: execution context, such as CPU load, process ID, and training ML model, or use the ML model to replace the heuristics 
* **Challenge #2: Customizing ML for the kernel** 
  * Kernel operations are limited and time-sensitive, we need to mitigate the overheads induced by ML 
  * What techniques can be adopted to achieve efficient and high-accuracy ML training, and prediction inside kernel with tolerable overhead 
* **Proposal #2: lightweight in-kernel ML** 
  * ML library to fasten the model construction and calculation 
    * ML data structure: Conv layer, MLP layer, etc.
    * Helper fuctions: mat mul, backware prop 
  * ML training 
    * Efficient background training
    * Offline training and updates 
    * ...
  * Customized ML
    * Neural architecture search 
    * Meta learning 
    * ... 
  * ML inference 
    * Model compression
    * Model quantization 
    * ... 
* **Challenge #3: guarantees of infrastructure behavior**
  * We need to guarantee the integrity of the whole infrastructure 
  * Decision based on ML leads to desirable state: e.g., resource imbalance 
  * Incorrect model causing kernel panic: eg., defective ML model
  * Privacy violation: e.g., data leaking 
* **Proposal #3: The RMT verifier** 
  * Performance interference: prevent RMT program from inducing kernel into undesirable states
  * Model safety: verify the correctness of the model or add guardrails to black box inference 
  * Privacy enhancement: implement privacy mechanism to prevent malicious queries 

### Summary

* Motivation: better, generalizable kernel optimizations 
* Proposal: reconfigurable kernel data-paths with learned optimizations 
* Key approach 
  * The RMT virtual machine 
  * Lightweight kernel ML 
  * The RMT verifier 
* Preliminary results 
  * Page prefetching, CPU scheduling