# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 6 Generalized Analytical Method for Directed Acyclic Graphs
### Transformation of Control Cost Function  
With the above challenge, let us transform the control cost function to a function of runnable periods. For the period \(T\), we can use the same method as for the LPG model and the LMG model since it is only concerned with the actuator runnable \(r_{n}\). Thus, \(T\) is transformed into as follows:  
\[T=2p_{n}. \tag{43}\]  
Unfortunately, however, when transforming the end-to-end delay \(\Delta\), we cannot simply reuse the method for the LMG model in Section 5.2 since we cannot be sure that an equilibrium state can be made. To handle this challenge, let us begin with the general definition of \(\Delta\) as in the following, assuming \(m\) paths \(\{P_{1},P_{2},\cdots,P_{m}\}\):  
\[\Delta=\max_{1\leq i\leq m}\left(\sum_{j\in P_{i}}2p_{j}\right). \tag{44}\]  
For example, in Figure 6(a), there are four paths, \(P_{1}=<1,2,3,7>\), \(P_{2}=<1,2,4,7>\), \(P_{3}=<1,4,7>\), and \(P_{4}=<1,5,6,7>\). Among them, it is apparent that \(P_{3}\) cannot be the critical path since it is always shorter than \(P_{2}\). However, among \(P_{1}\), \(P_{2}\), and \(P_{4}\), we cannot be sure which is the longest since all of them can be the critical path according to how we decide \(p_{i}\)s.  
To overcome this challenge, we propose to employ a heuristic with a clear rule regarding which path should be the critical path. For that, with given \(e_{i}\)s, we employ a heuristic described by the following:  
\[p_{i}\propto e_{i},\text{ for }2\leq i\leq n-1. \tag{45}\]  
Certainly, the most important benefit from making \(p_{i}\)s simply proportional to \(e_{i}\)s is that we can simply decide the critical path based on the path weights (See Definition 3) such that we can choose the heaviest path (See Definition 5) as the critical path. For example, in Figure 6(a), the weights of paths, \(P_{1}\) to \(P_{4}\), are calculated as 15, 17, 13, and 10, respectively. Then, \(P_{2}\), specified by the red color, turns out to be the heaviest path. By the heuristic, it is used as the critical path. The intuition behind this heuristic is that we give longer periods to runnables with longer execution times to evenly distribute the system utilization across runnables, eliminating possible bottlenecks. Note that \(p_{1}\) and \(p_{n}\) are excluded in Equation (45) as they have no effect on deciding the critical path.  
For further explanations, we introduce a new notation \(r_{c}\), which is defined as the set of runnables in the critical path excluding \(r_{1}\) and \(r_{n}\). Figure 6(b) shows \(r_{c}\)= \(\{r_{2},r_{4}\}\). Then, let us think as if \(r_{c}\) is a virtual _composite runnable_ combining its member runnables just like the ellipse covering \(r_{2}\) and \(r_{4}\) in the figure. Then, the critical path can be thought of as a three-runnable ordered set \(<r_{1},r_{c},r_{n}>\). For \(r_{c}\), let us also define \(e_{c}\) and \(p_{c}\) as in the followings:  
\[e_{c}=\sum_{i\in r_{c}}e_{i} \tag{46}\]  
and  
\[p_{c}=\sum_{i\in r_{c}}p_{i}  
Then, regarding how to derive \(p_{2}\), \(p_{3}\), \(\cdots\), and \(p_{n-1}\) from \(p_{c}\), we use the following assignment rule following Equation (45):  
\[p_{i}=\frac{e_{i}}{e_{c}}p_{c}\text{ for }2\leq i\leq n-1. \tag{50}\]  
Under the above assignment rule, the followings are ensured:  
* \(p_{i}\)s are always proportional to \(e_{i}\)s;
* The length of the critical path excluding \(r_{1}\) and \(r_{n}\) is equal to \(p_{c}\);
* The length of any other path is always shorter than \(p_{c}\).  
As an example, in Figure 7b, we can find that \(e_{c}=e_{2}+e_{4}=12\) and \(p_{c}=p_{2}+p_{4}\). Once \(p_{c}\) is decided, each \(p_{i}\) can be derived as in the followings according to Equation (50):  
\[p_{2}=\frac{4}{12}p_{c},\ p_{3}=\frac{6}{e_{c}}p_{c},\ p_{4}=\frac{8}{12}p_{c}, \ p_{5}=\frac{2}{12}p_{c},\text{ and }p_{6}=\frac{3}{12}p_{c}. \tag{51}\]