# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 5 Analytical Solution for Linear Multipath Graphs
### Finding the Optimal Runnable Periods  
After the transformation of the control cost function and the schedulability constraint function, our runnable periods optimization problem for the LMG model can be formulated with the three free variables (\(p_{1}\), \(p_{*}\), \(p_{n}\)) as follows:  
\[ \begin{split}\underset{p_{1},p_{*},p_{n}}{\text{minimize}}& J(p_{1},p_{*},p_{n})=2\alpha p_{n}+2\beta(p_{1}+p_{*}+p_{n})\\ \text{subject to}& U(p_{1},p_{*},p_{n})=\frac{e_{1}}{p _{1}}+\frac{\sum_{i=1}^{m}\sum_{k\in\hat{P}_{i}}\big{|}\hat{P}_{i}\big{|}\,e_ {k}}{p_{*}}+\frac{e_{n}}{p_{n}}\leq 1.\end{split}  \tag{34}\]  
To solve the optimization problem, a Lagrange function is formulated as follows:  
\[\mathcal{L}=2\alpha p_{n}+2\beta(p_{1}+p_{*}+p_{n})-\lambda\left(\frac{e_{1}} {p_{1}}+\frac{\sum_{i=1}^{m}\sum_{k\in\hat{P}_{i}}\big{|}\hat{P}_{i}\big{|}\,e _{k}}{p_{*}}+\frac{e_{n}}{p_{n}}-1\right). \tag{35}\]  
Then, we take the partial derivatives of \(\mathcal{L}\) with respect to \(p_{1}\), \(p_{*}\), \(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_{*}},\frac{\partial\mathcal{L}}{\partial p_{n }},\frac{\partial\mathcal{L}}{\partial\lambda}\right)=0, \tag{36}\]which in turn is expanded to the followings:  
\[ \begin{split}\frac{\partial L}{\partial p_{1}}&=2\beta+ \frac{e_{1}}{p_{1}^{2}}\lambda=0,\\ \frac{\partial L}{\partial p_{*}}&=2\beta+\frac{ \sum\limits_{i=1}^{m}\sum\limits_{k\in\hat{P}_{i}}\left|\hat{P}_{i}\right|e_{ k}}{p_{*}^{2}}\lambda=0,\\ \frac{\partial L}{\partial p_{n}}&=2(\alpha+\beta) +\frac{e_{n}}{p_{n}^{2}}\lambda=0,\\ \frac{\partial L}{\partial\lambda}&=-\left(\frac{e _{1}}{p_{1}}+\frac{\sum\limits_{i=1}^{m}\sum\limits_{k\in\hat{P}_{i}}\left| \hat{P}_{i}\right|e_{k}}{p_{*}}+\frac{e_{n}}{p_{n}}-1\right)=0.\end{split}  \tag{37}\]  
Then, the first, second, and third of Equation (37) are rearranged by isolating \(\lambda\) in each left-hand side as follows:  
\[ \begin{split}\lambda&=-2\beta\,\frac{p_{1}^{2}}{e_{ 1}},\\ \lambda&=-2\beta\,\frac{p_{*}^{2}}{\sum\limits_{i=1}^ {m}\sum\limits_{k\in\hat{P}_{i}}\left|\hat{P}_{i}\right|e_{k}},\\ \lambda&=-2(\alpha+\beta)\,\frac{p_{n}^{2}}{e_{n}}. \end{split}  \tag{38}\]  
Then, by combining the first and second of Equation (38), we have the following:  
\[2\beta\,\frac{p_{1}^{2}}{e_{1}}=2\beta\,\frac{p_{*}^{2}}{\sum \limits_{i=1}^{m}\sum\limits_{k\in\hat{P}_{i}}\left|\hat{P}_{i}\right|e_{k}} \Longrightarrow\frac{1}{p_{*}}=\frac{1}{p_{1}}\sqrt{\frac{e_{1}}{ \sum\limits_{i=1}^{m}\sum\limits_{k\in\hat{P}_{i}}\left|\hat{P}_{i}\right|e_{ k}}}. \tag{39}\]  
By combining the first and third of Equation (38), we have the following:  
\[2\beta\,\frac{p_{1}^{2}}{e_{1}}=2(\alpha+\beta)\,\frac{p_{n}^{2}}{e_{n}} \Longrightarrow\frac{1}{p_{n}}=\frac{1}{p_{1}}\sqrt{\frac{\alpha+\beta}{ \beta}}\sqrt{\frac{e_{1}}{e_{n}}}. \tag{40}\]  
By replacing \(\frac{1}{p_{*}}\) and \(\frac{1}{p_{n}}\) in the last of Equation (37) with the findings in Equations (39) and (40), we have the following:  
\[\frac{1}{p_{1}}\left(e_{1}+\sum\limits_{i=1}^{m}\sum\limits_{k\in\hat{P}_{i}} \left|\hat{P}_{i}\right|e_{k}\sqrt{\frac{e_{1}}{\sum\limits_{i=1}^{m}\sum \limits_{k\in\hat{P}_{i}}\left|\hat{P}_{i}\right|e_{k}}}+e_{n}\sqrt{\frac{( \alpha+\beta)\,e_{1}}{\beta e_{n}}}\right)=1. \tag{41}\]Finally, from Equations (39)-(41), we have the following solution:  
\[p_{1}=e_{1}+\sqrt{e_{1}\sum_{i=1}^{m}\sum_{k\in\hat{P}_{i}}\left|\hat{P}_{i} \right|e_{k}}+\sqrt{\frac{(\alpha+\beta)e_{1}e_{n}}{\beta}}\]  
\[p_{*}=p_{1}\sqrt{\frac{\sum_{i=1}^{m}\sum_{k\in\hat{P}_{i}}\left|\hat{P}_{i} \right|e_{k}}{e_{1}}} \tag{42}\]  
\[p_{n}=p_{1}\sqrt{\frac{\beta e_{n}}{(\alpha+\beta)\,e_{1}}}.\]  
We have one remaining step of deciding \((p_{2},p_{3},\cdots,p_{n-1})\). For that, we distribute \(p_{*}\) to runnables in each path in proportion to their \(e_{i}\)s as in Equation (30).