# DAG Hierarchical Schedulability Analysis for Avionics Hypervisor in Multicore Processors
## 4 Schedulability Analysis
### Scheduling
#### 4.1.3 Exploiting Parallelism and Joint Dependency  
Using CPPE, the next goal is to maximize the parallelism of NC-joints and decrease latency of CP completion. On the basis of the CPCM, every parent \(\phi_{i}^{*}\) correlates with \(H(\phi_{i}^{*})\), \(G(\phi_{i}^{*})\). With \(v_{j}\in G(\phi_{i}^{*})\), it could run before \(H(\phi_{i}^{*})\) and use the capacity of \(\phi_{i}^{*}\) to run, if a high priority is assigned. In this instance, \(v_{j}\) prolongs the finish of \(H(\phi_{i}^{*})\) and the start of \(\phi_{i+1}^{*}\), squanders the capacity of its parent. Similar results are also acquired, which avoid this latency by first probing the front interfering joints. \(\forall\phi_{i}^{*},\phi_{i}^{*}\in\Phi^{\prime}:i<l\rightarrow\min_{v_{j}\in H (\phi_{i}^{*})}q_{j}>\max_{v_{k}\in H(\phi_{i}^{*})}q_{k}\). Consequently, a second allocation Rule is derived to rule the priority of every parent in the child groups. With any two neighboring parents \(\phi_{i}^{*}\) and \(\phi_{i+1}^{*}\), the priority of any child in \(H(\phi_{i}^{*})\) is higher than the children in \(H(\phi_{i+1}^{*})\). The latency from \(G(\phi_{i}^{*})\) on \(H(\phi_{i}^{*})\) can be minimized, because whole joints in \(G(\phi_{i}^{*})\) fall within children of following parents and are always assigned with a lower priority than joints in \(H(\phi_{i}^{*})\) in Rule 2. Scheduling the child joints in every \(H(\phi_{i}^{*})\), concurrent joints with the same lead time are sorted by the length of their longest full path. Nevertheless, on the basis of CPCM, a full path can be divided into some partial paths, and all of these partial paths fall within a subgroup of different parents. With partial paths in \(H(\phi_{i}^{*})\), the order of their lengths can be completely reversed from to the order of their full paths. Therefore, this method can prolong the end time of \(H(\phi_{i}^{*})\). In the constructed scheduling, it is guaranteed to assign higher priority to the longer local paths in a dependency-aware way. It will result in the final allocation rule. Symbol \(l_{j}(H(\phi_{i}^{*}))\) is the length of the longest local path in \(H(\phi_{i}^{*})\) that contains \(v_{j}\). This length can be calculated by traversing \(\mathit{ancestors}(v_{j})\cup\mathit{descendants}(v_{j})\) in \(H(\phi_{i}^{*})\), such as in Figure 2, \(l_{7}(H(\phi_{7}^{*}))=6\), \(l_{8}(H(\phi_{8}^{*}))=3\), so \(v_{7}\) is assigned a higher priority than \(v_{8}\). Rules 1-3 are applied to the sample, and the better-case schedule with a maximum full-time of 14 is finally obtained. \(v_{j},v_{k}\in H(\phi_{i}^{*}):l_{j}(H(\phi_{i}^{*}))>l_{k}(H(\phi_{k}^{*})) \rightarrow q_{j}>q_{k}\). Nevertheless, applying Rule 3 to every \(H(\phi_{i}^{*})\) is not enough. Given the DAG structure, every \(H(\phi_{i}^{*})\) can form a smaller DAG \(G\prime\), and an inner nested CPCM with the longest path in \(H(\phi_{i}^{*})\) is the parent. In addition, this process can be applied recursively to build an internal CPCM for every subgroup in the nested CPCM until whole local paths in the subgroup are completely absolute. With every internally CPCM, Rules 1 and 2 should be applied to maximize the capacity and minimize the latency of every subgroup, while Rule 3 is applied only to the independent paths in subgroups to maximize parallelism. This makes complete dependencies between joints and ensures that the longest path in every nested CPCM takes precedence. Algorithm 2 shows the method of priority allocation based on Rule. The approach starts from the outer-most CPCM \(CPCM(G,\delta^{*})\), assign the highest priority to whole parent joints according to Rule 1. In accordance with Rule 2, it starts from before \(H(\phi_{i}^{*})\) and searches for the longest local path \(\delta_{v_{e}}\) in \(H(\phi_{i}^{*})\). If there exists a dependency between nodes in \(\delta_{v_{e}}\) and \(H(\phi_{i}^{*})/\delta_{v_{e}}\), \(H(\phi_{i}^{*})\) is further constructed as an inner CPCM with the assignment algorithm applied recursively.