# AUTOSAR Runnable Periods Optimization for DAG-Based Complex Automobile Applications
## 2 Related Work  
Periods selection problemControl-scheduling codesign methods have been developed in the literature to improve a control system's performance through optimizing its scheduling parameters. In this regard, [PERSON] et al. 's seminal work [12] first presented a periods selection problem assuming that the control performance can be expressed as an exponential decay function of sampling periods and that the tasks are scheduled under a dynamic-priority scheduling algorithm. The periods selection problem was extended to fixed-priority systems by finding the finite set of feasible period ranges using a branch and bound-based integer programming method [13]. Later, [PERSON] and [PERSON] [14] proposed a faster algorithm that finds a sub-optimal periods assignment, which can be used for task sets of practical size that are not solvable by previous methods due to high computing demands. [PERSON] et al. [15] presented an analytical solution using the Lagrange multiplier method and an online algorithm for overloaded situations. [PERSON] et al. [9] developed a heuristic algorithm for multicore processors. Delay-aware approachesA common assumption of the above studies regarding the periods selection problem is that the control performance is only affected by sampling rates, i.e., task periods, of a control system. However, delays between sensing and actuation also have significant effects on control performance. With this motivation, [PERSON] and [PERSON] [6] incorporated each task's delay into their optimization cost function. In their work, to find the optimal periods assignment, cost functions are approximated as linear functions of control period and delay, and the delay is also approximated assuming the fluid model scheduler. Through the approximations, they proposed an analytical solution. [PERSON] et al. [16] extended this approach for systems with harmonic periods. Periods and deadlines selection problemWu et al. [8] formulated an optimization problem for selecting both task periods and deadlines simultaneously for EDF-scheduled systems. They showed that we can upper bound the amount of delays and jitters each task can experience by regulating relative deadlines of tasks. The cost function is assumed to be a nonlinear function of period and deadline of each task. Based on that, a two-step approach was proposed, which first fixes periods and later tries to minimize deadlines exploiting unused resources. [PERSON] et al. [10] proposed an algorithm that simultaneously adjusts periods and deadlines assuming EDF-scheduled linear-quadratic-Gaussian (LQG) controllers. They showed that their algorithm is more robust with various workloads than the previous method. [PERSON] et al. [17] proposed a heuristic algorithm for the periods and deadlines selection problem with arbitrary nonlinear control cost functions for systems scheduled by the RM scheduling algorithm. Cause-effect chain analysisThe above studies commonly assume independent real-time tasks, where there is no data dependency among tasks and each task is responsible for its dedicated control target plant. To deal with practical automobile control applications composed of tasks with complex dependencies, DAG-based control applications had been studied in the context of cause-effect chain analyses of real-time tasks [18; 19; 20; 21]. Even though they are using tasks instead of runnables, their system model is similar to ours. However, they address the opposite direction of our optimization problem, which is to analyze end-to-end delays for a DAG of tasks with given periods. Besides, [22] analyzed end-to-end delays of an engine management system, which is given as a DAG of runnables. AUTOSAR system optimizationIn automobile control systems based on the AUTOSAR standard, each control application is designed as a DAG of fine-granular runnables with more complex data dependencies compared with traditional real-time task-based systems. In this context, [PERSON] et al.