# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 7 Evaluation
### Evaluation Method  
For the evaluation, we have to consider the following: (i) workload synthesis, (ii) control cost functions, (iii) optimization algorithms, and (iv) performance metrics. In the remainder of this subsection, the above topics are discussed to explain our evaluation method. _Workload synthesis._ As representative AUTOSAR workloads, a total of nine DAGs are artificially synthesized. Among them, the first six DAGs in Figure 8 are relatively small ones with four to six runables, whereas the remaining three DAGs in Figure 9 are with a relatively large number of runables ranging from 12 to 25. Note that the DAGs are manually generated, however, understand that the resulting DAGs are purely random without any unfair bias. The small DAGs are used to test the optimality of our method since we can find the real optimal solutions for those small DAGs in Figure 8. On the other hand, we cannot find the real optimal solutions for the large DAGs in Figure 9 due to the vast problem space. However, although we cannot evaluate the optimality of our method with the large DAGs, they are still useful when evaluating our method in comparison to other heuristic optimization methods. Each DAG in the figures is labeled by a notation \((nR,mL)\) representing its size and complexity, where \(nR\) denotes \(n\) runables and \(mL\) denotes \(m\) links (or edges) between them. Basically, with larger \(n\) and \(m\), DAGs become more and more complex. For example, the DAG in Figure 8a is labeled by \((4R,5L)\), which has four runnables and five links, and the DAG in Figure 9c, labeled by \((25R,34L)\), has 25 runnables and 34 links. For each DAG, we generate 100 sets of random runnable execution times uniformly distributed in the range of [20 ms, 150 ms]. _Control cost functions._ As our optimization objective, we use a linear control cost function as in Equation (10), which is a function of the control period (\(T\)) and the end-to-end delay (\(\Delta\)). As a representative control cost function, we use the following as our default control cost function, unless otherwise stated:  
\[J(T,\Delta)=0.01T+0.01\Delta. \tag{67}\]  
Note the above control cost function has two coefficients \(\alpha\) = 0.01 and \(\beta\) = 0.01. Here, however, the relative ratio of \(\alpha\) and \(\beta\) is more important than their absolute values since the ratio represents the control cost function's relative sensitivity to the control period and the end-to-end delay. By using the same values for \(\alpha\) and \(\beta\) in our default control cost function, the control cost is equally sensitive to the control period and the end-to-end delay. To represent other scenarios with varying relative sensitivities, we also use varying \(\alpha\)s and \(\beta\)s in the range of [0.01, 0.05]. _Optimization algorithms._ To evaluate the optimization performance of our method, for the comparison purpose, we specifically consider the following three optimization methods:  
* _OUR:_ Near-optimal solutions found by our analytical optimization method;
* _EXH:_ Real optimal solutions found by the exhaustive combinatorial search method;
* _PSO:_ Solutions optimized by the particle swarm optimization (PSO) method [39]. More specifically, the _EXH_ method searches through the discrete integer problem space within [1 ms, 1000 ms] for each runnable period. We compare our method with the _EXH_ method to evaluate the optimality of our optimization method with small DAGs to answer the question Q1. To evaluate the optimization performance with large DAGs as an answer to the question Q3, we compare our method with the _PSO_ method. _Performance metrics._ We mainly use two optimization performance metrics: (i) absolute control costs and (ii) normalized control costs. Absolute control costs are the raw control cost values resulting from an optimization process, whereas normalized control costs are used to compare our method with another algorithm, i.e., the _EXH_ method and the _PSO_ method.