# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 1 Introduction  
AUTOSAR is the de facto standard software architecture for automobile control systems, covering a wide range of applications such as engine management, motor-driven power steering, and advanced driver assistance systems [1; 2; 3]. In the AUTOSAR standard, a control system is designed as a set of _software components_, which are the units of software packaging and deployment. Usually, multiple software components are connected and communicate through the AUTOSAR runtime environment (RTE). Each software component is also composed of a set of _runnables_, which are the smallest unit functions for software development and scheduling. Runnables communicate with each other within each software component and across different software components, using asynchronous message passing interfaces provided by the RTE. As a result, a system can be modeled as a directed acyclic graph (DAG) of runnables where data flow from sensors to actuators through the runnables in the DAG. For runnable executions, each runnable is associated with an event source, which is usually a periodic timer, and runnables with the same periods are grouped into periodic tasks for scheduling on the AUTOSAR real-time operating system (RTOS). Runnable periods should be carefully optimized since they are control knobs for balancing the trade-off between a system's load and control performance. For example, imagine a system with extremely short runnable periods. The systemwill then be much too heavily loaded, hence not schedulable since the runnables should execute with extremely high frequencies. On the other hand, the short runnable periods, if realized, can produce a high control performance due to fast data flows and high control frequencies. At the opposite extreme, i.e., a system with extremely long runnable periods, it will be lightly loaded and hence easily schedulable; however, its control performance will be significantly degraded due to slow data flows and low control frequencies. In that sense, we need a method to find optimal runnable periods between those two extreme cases. However, in the automotive industry, runnable periods are usually decided in an ad-hoc manner with time-consuming trials and errors [4], making it difficult to extract the optimal control performance out of given hardware resources. To cope with this problem, this paper formulates a runnable periods optimization problem for maximizing the control performance of a given system. Our previous work's initial approach was to use a simple combinatorial search method to find real optimal runnable periods [5]. However, our preliminary experiment revealed that even for a small system with a dozen runnables, since the optimization process cannot find solutions in polynomial times, it takes too much time, making it impractical for complex industry applications. To deal with this scalability problem, our approach is to develop an analytical method that can find near-optimal solutions without time-consuming searches. For that, the first step is to pick an appropriate control performance model as the optimization objective. Among various models in the literature, we chose the linear control cost model from [PERSON] [6] that represents a control system's performance as an approximate linear cost function of its control period and delay [6]. This model has been used as a standard tool by many control-scheduling codesign studies [7; 8; 9; 10]. The second step is to define the optimization constraint, that is, the schedulability constraint in our problem. Since the AUTOSAR standard assumes a priority-driven scheduling algorithm, we use the Liu and Layland (L&L) utilization bound method [11], which can be used for both the rate monotonic (RM) and the earliest deadline first (EDF) scheduling algorithms. For the explanation purpose, the EDF scheduling algorithm is mostly assumed throughout this paper, and later our method is extended to the RM scheduling algorithm.