# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 6 Generalized Analytical Method for Directed Acyclic Graphs
### Finding the Optimal Runnable Periods  
Based on the control cost function in Equation (49) and the utilization function in Equation (53), our runnable periods optimization problem for the DAG model can be formulated with the three free variables \((p_{1},p_{c},p_{n})\) as follows:  
\[\begin{split}\underset{p_{1},p_{c},p_{n}}{\text{minimize}}& J(p_{1},p_{c},p_{n})=2\alpha p_{n}+2\beta(p_{1}+p_{c}+p_{n})\\ \text{subject to}& U(p_{1},p_{c},p_{n})=\frac{e_{1}}{p _{1}}+(n-2)\frac{e_{c}}{p_{c}}+\frac{e_{n}}{p_{n}}\leq 1.\end{split} \tag{54}\]  
To solve the optimization problem, a Lagrange function is formulated as follows:  
\[\begin{split}\mathcal{L}&=J(p_{1},p_{c},p_{n})- \lambda(U(p_{1},p_{c},p_{n})-1)\\ &=2\alpha p_{n}+2\beta(p_{1}+p_{c}+p_{n})-\lambda\left(\frac{e_{1 }}{p_{1}}+(n-2)\frac{e_{c}}{p_{c}}+\frac{e_{n}}{p_{n}}-1\right).\end{split} \tag{55}\]  
Then, we take the partial derivatives of \(\mathcal{L}\) with respect to \(p_{1}\), \(p_{c}\), \(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_{c}},\frac{\partial\mathcal{L}}{\partial p_{n} },\frac{\partial\mathcal{L}}{\partial\lambda}\right)=0, \tag{56}\]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_{c}}=2\beta+(n-2)\frac{e_{ c}}{p_{c}^{2}}\lambda=0,\\ &\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(\frac{e_{1}} {p_{1}}+(n-2)\frac{e_{c}}{p_{c}}+\frac{e_{n}}{p_{n}}-1\right)=0.\end{split} \tag{57}\]  
Then, the first, second, and third of Equation (57) 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_{c}^{2}}{(n-2)e_{c}},\\ &\lambda=-2(\alpha+\beta)\,\frac{p_{n}^{2}}{e_{n}}.\end{split} \tag{58}\]  
Then, by combining the first and second of Equation (58), we have the following:  
\[2\beta\,\frac{p_{1}^{2}}{e_{1}}=2\beta\,\frac{p_{c}^{2}}{(n-2)e_{c}} \Longrightarrow\,\frac{1}{p_{c}}=\frac{1}{p_{1}}\sqrt{\frac{e_{1}}{(n-2)e_{c }}}. \tag{59}\]  
By combining the first and third of Equation (58), 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)e_ {1}}{\beta e_{n}}}. \tag{60}\]  
By replacing \(\frac{1}{p_{c}}\) and \(\frac{1}{p_{n}}\) in the last of Equation (57) with the findings in Equations (59) and (60), we have the following:  
\[\frac{1}{p_{1}}\left(e_{1}+(n-2)e_{c}\sqrt{\frac{e_{1}}{(n-2)e_{c}}}+e_{n} \sqrt{\frac{(\alpha+\beta)e_{1}}{\beta e_{n}}}\right)=1. \tag{61}\]  
Finally, from Equations (59)-(61), we have the following solution:  
\[\begin{split}& p_{1}=e_{1}+\sqrt{(n-2)e_{1}e_{c}}+\sqrt{\frac{( \alpha+\beta)e_{1}e_{n}}{\beta}}\\ & p_{c}=p_{1}\sqrt{\frac{(n-2)e_{c}}{e_{1}}}\\ & p_{n}=p_{1}\sqrt{\frac{\beta e_{n}}{(\alpha+\beta)e_{1}}}.\end{split} \tag{62}\]  
After finding the optimal \((p_{1},p_{c},p_{n})\), the remaining runnable periods \((p_{2},p_{3},\cdots,p_{n-1})\) should be decided, too. For that, the assignment rule in Equation (50) is used.