# Overlay-ML: Unioning Memory and Storage Space for On-Device AI on Mobile Devices
## 2 Background and Related Work
### Memory Management Policy of Embedded Operating System  
Today, most embedded devices commonly adopt Linux family as their operating system [22]. For example, high-end embedded devices that have sufficient DRAM memory and CPU power commonly use Android OS, while low-end devices with limited hardware resources employ customized Linux, such as Raspberry Pi OS [7]. We believe that the use of Linux will be growing over time. This is because Linux can be easy to customize codes (i.e., Kernel) according to requirements and expand to support a diversity of hardware resources, such as ZigBee [23], IoT Hub [24], etc.  
In this paper, we focus on Android OS and its memory management policy; it is widely used and follows the basic functionalities of Linux. Android OS guarantees the available memory space for each application by allocating memory space in an incremental way to store application data. It manages free memory space by killing an application if the accumulated memory usage exceeds the available memory limitation of one application (i.e., 256 MB). But, it is a very interesting termination because it occurs even if available memory space is enough. In other words, this termination is not triggered by _low memory killer daemon_ (LMKD) that secures memory space under high memory pressure and low available memory space [25; 26].  
Meanwhile, Android gives us _largeHeap_ option as a guide to solve this problem. This option works because of two reasons. First, the _largeHeap_ option extends the total memory usage of an application to 512 MB [27]. Second, most data generated from on-device ML is saved on the _heap_ area of a process. Unfortunately, some applications using on-device ML can require more memory space than 512 MB of memory space. In this case, the applications will be terminated when exceeding the total memory usage over 512 MB regardless of the _largeHeap_ option. To confirm the effect of the option and the reason why an application is killed, we performed an experimental evaluation. For evaluation, we first implemented a simple application where an image is recognized and classified using on-device ML [15]. Figure 2 shows our evaluation results and memory usage that was monitored by _Symple System Monitor application_. As shown in Figure 2 (right), when the total memory usage of the application exceeds 512 MB, the application is killed with the following message _\"Out-Of-Memory Error\"_ even though available memory space is enough. To understand the reason, we studied and found out that the error message means the application cannot allocate additional memory space because it had consumed its available memory space; we call it **(C3) challenge of software limitation**.  
Figure 2: The results of experiment evaluation. An application developed by TensorFlow Lite (**a**) and its memory usage collected by a system monitoring application (**b**).  
In summary, on-device ML still suffers from three challenges. We believe **C2** will naturally resolve over time because many researchers and engineers try to stably transform all functionalities of ML running on server or desktop environments. Therefore, we are motivated by a simple question: Can we address the **C1** and **C3** challenges with small trade-offs?