# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 4 Analytical Solution for Linear Path Graphs
### Transformation of Control Cost Function  
When solving the optimization problem in the LPG model's scope, the first step is to redefine the control cost function as a function of the free variables of the optimization problem, i.e., runnable periods (\(p_{1},p_{2},\cdots,p_{n}\)). For the transformation of \(J(T,\Delta)\) in Equation (10) into a function of runnable periods, our strategy is to define both \(T\) and \(\Delta\) using only runnable periods considering the LPG model's runnable execution and data flow patterns.  
Control period \(T\) can be formally defined, from a plant's perspective, as a regular time interval between consecutive actuation instances. However, due to the jitter caused by preemption delays among concurrent runnables, the intervals may vary for each actuation instance. Thus, we consider the longest time interval as the worst-case period \(T\). For LPG-based applications, \(T\) can be defined as double the actuator runnable \(r_{n}\)'s period \(p_{n}\), which is  
\[T=2p_{n}. \tag{13}\]  
The worst-case scenario happens when a certain instance of \(r_{n}\) is scheduled at the beginning of its period, whereas, in the next instance, \(r_{n}\) is scheduled at the very end of its period. Assuming that actuation commands are emitted at each completion of \(r_{n}\) instances, the time interval between the actuation commands gets to the longest as possible in that particular scenario, which is \(2p_{n}\). It can be argued that \(e_{n}\) should be considered, and the exact worst-case time interval should be \(2p_{n}-e_{n}\). However, note that since \(e_{n}\) is the worst-case execution time, real execution times can be much smaller than \(e_{n}\); thus, for simplicity's sake, we do not take \(e_{n}\) into consideration when defining \(T\).  
The end-to-end delay \(\Delta\) is defined as the time taken for new sensor data to go through runnables until arriving at the actuator. According to the data flow architecture of our system model, the sensor runnable \(r_{1}\) sends out its output to its neighboring runnables with its own period \(p_{1}\). Then, the neighboring runnables also send out their outputs with their own periods. With these repeated transmissions, new sensor data originating from the source node \(r_{1}\) gradually propagate through the runnables toward the sink node, i.e., the actuator runnable \(r_{n}\). After \(r_{n}\) finally receives the updates, it can decide its actuation commands based on the new sensor data. In an LPG-based application where data flow through only a single path from \(r_{1}\) to \(r_{n}\), the worst-case end-to-end delay \(\Delta\) can be calculated as  
\[\Delta=2p_{1}+2p_{2}+\cdots+2p_{n}=2\sum_{i=1}^{n}p_{i}. \tag{14}\]  
The worst case happens as in the following: a runnable \(r_{i-1}\) emits its output for \(r_{i}\) at a certain time \(t\). Unfortunately, however, \(r_{i}\) begins just right before \(t\), reading the previous (old) output of \(r_{i-1}\). Let us assume that \(r_{i}\) is scheduled at the very beginning of its period at that time. Then, unfortunately again, the next instance of \(r_{i}\) is scheduled at the very end of its period, reading the new data and emitting its output at the end of the period (i.e., \(t+2p_{i}\)). In the above scenario, the time taken for the data to go through \(r_{i}\) is double the \(r_{i}\)'s period \(2p_{i}\). Assuming this scenario happening for every runnable in the path, the end-to-end delay \(\Delta\) becomes double the sum of all the runnable periods as in Equation (14). By combining Equations (13) and (14), the control cost function in Equation (10) is transformed into as follows:  
\[J(p_{1},p_{2},\cdots,p_{n})=2\alpha p_{n}+2\beta\sum_{i=1}^{n}p_{i}. \tag{15}\]