# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 7 Evaluation
### Evaluation Results and Discussion  
Q1: Is our analytical method able to find near-optimal runnable periods? For the six DAGs from Figure 8a-f, their normalized average control costs by the _EXH_ method and our method are compared in Figure 10. In the figure, our method shows near-optimal control costs with marginal performance losses compared with the _EXH_ method. The minimum control cost increase is just 1.1% and the  
Figure 8: Small DAGs with varying number of runnables (denoted by \(n\)R) and links (denoted by \(m\)L). Figure 9: Large DAGs used for evaluating the practicality of our method. maximum is 12.3%. One interesting point is that DAG (a) shows a significantly better performance than the other DAGs. That is because our heuristic for selecting the critical path is always valid in this particular DAG shape. Note that, in DAG (a), \(<r_{1},r_{2},r_{3},r_{4}>\) will be correctly chosen as the critical path by our heuristic regardless of their execution times since every other path is a subset of it. On the other hand, in other DAGs, there are multiple choices for the critical path. Nonetheless, our method must bet on a certain path based on the given execution times. However, as shown in the figure, the performance losses from the real optimal solutions are marginal. Thus far, we have assumed the EDF scheduling algorithm. However, in the automotive industry, the RM scheduling algorithm is also widely used for scheduling real-time tasks. In this regard, Figure 11 compares the EDF case where the utilization bound is 100% and the RM case where the utilization bound is 69.3%. More specifically, Figure 11 compares their normalized average control costs across the six DAGs, each of which represents the relative optimization performance compared with the _EXH_ method. The figure shows that our method provides not much different optimization results across the two  
Q2: Is it practical to find real optimal solutions by the exhaustive search method? By looking at Q1's results, one can argue that if we can use the _EXH_ method to find real optimal runnable periods, why not just use the _EXH_ method instead of our method? However, this argument does not hold since the _EXH_ method is not usable for large DAGs due to the vast search space when \(n>6\). To answer the question, we evaluate our optimization method in terms of the required time for the optimization process. Table 1 shows the required optimization times for our method and the _EXH_ method with varying number of runnables. The numbers inside parentheses are projected numbers. As our method finds the runnable periods by an analytical method, it shows negligible computational complexities as predicted in Algorithm 1. With the _EXH_ method, we can find optimal runnable periods in about one month when the numbers of runnables is seven. However, after seven runnables, it is not feasible to use the _EXH_ method since it takes more than a year even for small and medium-size systems. Thus, due to the scalability problem, the _EXH_ method cannot be used for practical industrial applications, whereas our analytical method can be used for large industry applications. Q3: Is our method practically competitive when optimizing large systems? From Q1 and Q2, we showed that (i) our analytical method works well with small systems and (ii) real optimal solutions cannot be found for large systems. One remaining question is whether we can apply our analytical method to large systems with sufficient optimization performance. To answer this question, we use the three large DAGs with \(n=12,16,\) and \(25\), as in Figure 9. For the comparison, we additionally use an evolutionary metaheuristic algorithm known as particle swarm optimization (denoted by _PSO_) that searches an unknown vast problem space efficiently with swarm intelligence. To implement the _PSO_ method, we use the PySwarms library [40]. Figure 13 shows the normalized average control costs of our method compared with the _PSO_ method, letting the resulting control costs by the _PSO_ method as \(100\%\).