# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 3 Background and Problem Description  
### System Model  
This paper assumes an automobile control application based on the AUTOSAR standard. Figure 1 shows an example system where the application is composed of \(N\) software components  
\[\{C_{1},C_{2},\cdots,C_{N}\}. \tag{1}\]  
Each software component \(C_{i}\) is also composed of \(|C_{i}|\) runnables where \(|C_{i}|\) denotes the number of runnables in \(C_{i}\). Note that a runnable is the smallest unit function in the AUTOSAR standard. As shown in the figure, runnables, denoted by \(r_{i}\)s, are connected with directed edges representing data dependencies among them. Thus, the whole system can be thought of as a DAG of runnables without explicitly specifying which software component each runnable belongs to. A DAG \(G\) is formally defined as  
\[G=(V,E\subset V\times V) \tag{2}\]  
where the set of vertices \(V\) is a set of \(n\) nodes or runnables \(\{r_{1},r_{2},\cdots,r_{n}\}\) where \(n=\sum_{i=1}^{N}|C_{i}|\) and \(E\) represents a set of directed edges or links among them. There exists a directed edge \((r_{j},r_{k})\in E\) if and only if the runnable \(r_{k}\) has a data dependency on the runnable \(r_{j}\). Then, each \(i\)-th runnable \(r_{i}\) is defined by a tuple  
\[r_{i}=(p_{i},e_{i}) \tag{3}\]  
where \(p_{i}\) is its period and \(e_{i}\) is the worst-case execution time. Among the runnables, we assume that \(r_{1}\), the _sensor runnable_, plays a special role of collecting data from sensors, and \(r_{n}\), the _actuator runnable_, is responsible for controlling actuators. Thus, \(G\) has only one source node \(r_{1}\) and one sink node \(r_{n}\). Our system model assumes that, in an ECU, there is only one CPU running a single control application described by \(G\), where the ECU handles only a single control target plant, which is common in the automotive industry's federated architecture [28; 29]. Note that \(e_{i}\)s are given properties of the system, whereas \(p_{i}\)s are controllable parameters. Thus, the runnable periods  
\[(p_{1},p_{2},\cdots,p_{n}) \tag{4}\]  
should be decided before integrating the runnables on the AUTOSAR platform. Once \(p_{i}\)s are decided, runnables with the same \(p_{i}\)s are grouped and consolidated into RTOS tasks, which are scheduled following the scheduling strategy of the RTOS. For communications between runnables, an asynchronous sender-receiver communication is used [30]. In this communication method, a sender runnable periodically generates its output in a shared memory buffer with its own period, then a receiver runnable asynchronously reads the data in the memory buffer with its own period. When multiple writes occur to the same memory location without any reading operation from the receiver, the most recent data are always overwritten in the buffer. For further discussions afterward, we formally introduce the following definitions:  
**Definition 1**. : **(Paths)** _For a DAG \(G=(V,E)\), there is a finite number of directed paths from the source node \(r_{1}\) to the sink node \(r_{n}\). We assume that there are \(m\) paths in \(G\), which is denoted by_  
\[\mathbb{P}(G)=\{P_{1},P_{2},\cdots,P_{m}\}. \tag{5}\]  
_Then, a path is formally defined as an ordered set of runnables beginning with \(r_{1}\) and ending with \(r_{n}\) in which all runnables are distinct and every pair of adjacent runnables is joined by a directed edge in \(E\). From now on, for the notational convenience, when we refer to a path \(P\in\mathbb{P}(G)\), it can denote the ordered set of runnable indexes \((1\leq i\leq n)\) as well as the runnables themselves depending on the context._  
**Definition 2**. : **(Length)** _For a path \(P\in\mathbb{P}(G)\), its length is defined as_  
\[\sum_{i\in P}p_{i}, \tag{6}\]  
_which is the sum of runnable periods following a specific path \(P\).