# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 5 Analytical Solution for Linear Multipath Graphs
### Transformation of Control Cost Function  
For the optimization, the objective function \(J(T,\Delta)\) in Equation (10) should be transformed into a function of runnable periods \((p_{1},p_{2},\cdots,p_{n})\). For that, in the same way in Section 4.2, the period \(T\) is transformed into as follows:  
\[T=2p_{n}. \tag{22}\]  
For the end-to-end delay \(\Delta\), however, we cannot simply reuse the method in Section 4.2 since we have multiple paths with possibly different lengths. Thus, \(\Delta\) should be defined as the length of the longest path among them to represent the worst-case end-to-end delay. More specifically, let us remind that \(P_{i}\) denotes the \(i\)-th path of \(m\) independent paths \(\{P_{1},P_{2},\cdots,P_{m}\}\). Then, \(\Delta\) is defined as follows:  
\[\Delta=\max_{1\leq i\leq m}\left(\sum_{j\in P_{1}}2p_{j}\right). \tag{23}\]  
Thus, our original optimization problem is transformed into as follows:  
\[ \begin{array}{ll}\underset{p_{1},p_{2},\cdots,p_{n}}{\text{minimize}}&J(p_{1 },p_{2},\cdots,p_{n})=2\alpha p_{n}+\beta\max_{1\leq i\leq m}\left(\sum_{j\in P _{i}}2p_{j}\right)\\ \text{subject to}&U(p_{1},p_{2},\cdots,p_{n})=\sum_{i=1}^{n} \frac{e_{i}}{p_{i}}\leq 1,\end{array}  \tag{24}\]  
where unlike the LPG model, the max operator introduces nonlinearity making it difficult to develop an analytical solution. Fortunately, however, due to the LMG model's workload characteristics, we can simplify the problem by defining an equilibrium state, which is to be obtained to find the optimal runnable periods in the LMG model. The equilibrium state of an LMG can be defined as follows:  
**Definition 6**: **(Equilibrium state)** _For a set of \(m\) paths of a given LMG \(G\), which is denoted by \(\mathbb{P}(G)=\{P_{1},P_{2},\cdots,P_{m}\}\), \(G\) is in its equilibrium state if and only if_  
\[\sum_{i\in P_{1}}p_{i}=\sum_{i\in P_{2}}p_{i}=\cdots=\sum_{i\in P _{m}}p_{i}. \tag{25}\]  
**Theorem 1**: **(Equilibrium state theorem)** _If \(G\) is an LMG with its optimal runnable periods, \(G\) is always in its equilibrium state._  
**Proof of Theorem 1. ** If \(G\) is with its optimal runnable periods while not in the equilibrium state, we can increase runnable periods that do not belong to the critical path, without affecting the end-to-end  
Figure 6: Linear multipath graph (LMG) model with \(m\) independent paths identified by edges with different colors [27]. delay. Then, the increased runnable periods will make a lower system utilization, which can be used to further decrease the end-to-end delay by shortening runnable periods in the critical path. Thus, we can conclude that \(G\) is not with the optimal runnable periods, which is a contradiction. By the equilibrium state theorem, we can narrow down the problem space without sacrificing the optimality by excluding non-equilibrium states from the problem space. To express the equilibrium state more efficiently, \(\Delta\) is re-expressed by breaking it into three parts as  
\[\Delta=2p_{1}+\max_{1\leq i\leq m}\left(\sum_{j\in\hat{P}_{i}}2p_{j}\right)+2 p_{n} \tag{26}\]  
with a helper notation \(\hat{P}_{i}=P_{i}-\{1,n\}\). Then, to explicitly express the equilibrium state, we define a new notation \(p_{*}\) as in the following:  
\[p_{*}=\sum_{i\in\hat{P}_{1}}p_{i}=\sum_{i\in\hat{P}_{2}}p_{i}=\cdots=\sum_{i \in\hat{P}_{m}}p_{i}, \tag{27}\]  
which is an aggregate variable representing the path length of the middle part in the equilibrium state. Then, by using \(p_{*}\), \(\Delta\) can be re-expressed from Equations (26) and (27) as follows:  
\[\Delta=2(p_{1}+p_{*}+p_{n}). \tag{28}\]  
Finally, the control cost function \(J(T,\Delta)\) from Equation (10) is rewritten as a function of \((p_{1},p_{*},p_{n})\) by Equations (22) and (28) as in the following:  
\[J(p_{1},p_{*},p_{n})=2\alpha p_{n}+2\beta(p_{1}+p_{*}+p_{n}). \tag{29}\]  
With this transformed control cost function \(J(p_{1},p_{*},p_{n})\), our original problem of \(n\) runnable periods is transformed into a problem of three free variables \((p_{1},p_{*},p_{n})\).