# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 4 Analytical Solution for Linear Path Graphs
### Finding the Optimal Runnable Periods  
For visual understanding of the optimization process, let us pick an example system with only two runnables \(\{r_{1},r_{2}\}\). Then, the transformation of the control cost function is illustrated in Figure 4. In the left-hand side, the original control cost function is depicted, which is transformed into a function of \(p_{1}\) and \(p_{2}\) as in the right-hand side by Equation (15). Then, Figure 5 illustrates the optimization process where the schedulability constraint and the transformed control cost function are shown uponthe two-dimensional problem space of \(p_{1}\) and \(p_{2}\). In the figure, our optimization objective is to find the lowest point in the control cost plane that is inside the green schedulable area. This concept can be generally extended to \(n\)-runnable systems in \(n\)-dimensional problem spaces. In general, our original optimization problem in Equation (12) can be transformed into the following using the transformed control cost function:  
\[\underset{p_{1},p_{2},\cdots,p_{n}}{\text{minimize}} J(p_{1},p_{2},\cdots,p_{n})=2\alpha p_{n}+2\beta\sum_{i=1}^{n}p_{i}\] (16) subject to \[U(p_{1},p_{2},\cdots,p_{n})=\sum_{i=1}^{n}\frac{e_{i}}{p_{i}} \leq 1.\]  
To analytically solve the transformed optimization problem, the Lagrange multiplier method is applied. For the first step, a Lagrange function is formulated as follows:  
\[\mathcal{L}=2\alpha p_{n}+2\beta\sum_{i=1}^{n}p_{i}-\lambda\left(\sum_{i=1}^{n }\frac{e_{i}}{p_{i}}-1\right). \tag{17}\]  
Then, we take the partial derivatives of \(\mathcal{L}\) with respect to \(p_{1}\), \(p_{2}\), \(\cdots\), \(p_{n}\), and \(\lambda\), respectively and set them to zeros as follows:  
\[\
abla\mathcal{L}=\left(\frac{\partial\mathcal{L}}{\partial p_{1}},\frac{ \partial\mathcal{L}}{\partial p_{2}},\cdots,\frac{\partial\mathcal{L}}{ \partial p_{n}},\frac{\partial\mathcal{L}}{\partial\lambda}\right)=0, \tag{18}\]  
Figure 4: Visually illustrated transformation of control cost function [5].  
Figure 5: Visually illustrated constrained optimization process [5].  
which in turn is expanded to the followings:  
\[\begin{split}\frac{\partial\mathcal{L}}{\partial p_{1}}& =2\beta+\frac{e_{1}}{p_{1}^{2}}\lambda=0,\\ \frac{\partial\mathcal{L}}{\partial p_{2}}&=2\beta+ \frac{e_{2}}{p_{2}^{2}}\lambda=0,\\ \cdots,\\ \frac{\partial\mathcal{L}}{\partial p_{n}}&=2(\alpha +\beta)+\frac{e_{n}}{p_{n}^{2}}\lambda=0,\\ \frac{\partial\mathcal{L}}{\partial\lambda}&=- \left(\sum_{i=1}^{n}\frac{e_{i}}{p_{i}}-1\right)=0.\end{split} \tag{19}\]  
Then, by isolation \(\lambda\) in the left-hand side of the first in Equation (19), we have  
\[\lambda=-\frac{2\beta{p_{1}}^{2}}{e_{1}}, \tag{20}\]  
which can be applied to the remaining of Equation (19) except the last one. As a result, \(p_{2}\), \(p_{3}\), \(\cdots\), and \(p_{n}\) are given in terms of \(p_{1}\) as in the second to the last of the followings:  
\[\begin{split} p_{1}&=\sum_{i=1}^{n-1}\sqrt{e_{1}e_{ i}}+\sqrt{\frac{(\alpha+\beta)e_{1}e_{n}}{\beta}},\\ p_{2}&=p_{1}\sqrt{\frac{e_{2}}{e_{1}}},\\ \cdots,\\ p_{n-1}&=p_{1}\sqrt{\frac{e_{n-1}}{e_{1}}},\\ p_{n}&=p_{1}\sqrt{\frac{\beta e_{n}}{(\alpha+\beta )e_{1}}}.\end{split} \tag{21}\]  
Additionally, \(p_{1}\) is given as the first of the above by replacing \(p_{2}\), \(p_{3}\), \(\cdots\), and \(p_{n}\) in the last of Equation (19) with the second to the last of the above. Then, by Equation (21), we can find the real optimal runnable periods for arbitrary LPG-based applications.