Response Time Analysis for Probabilistic Dag Tasks in Multicore Real-Time Systems

Parallel real-time systems often contain functionalities with complex dependencies and execution uncertainties, leading to significant timing variability which can be represented as a probabilistic distribution. However, existing timing analysis either produces a single conservative bound or incurs high computational costs due to the exhaustive enumeration of every execution scenario. This significantly hinders the exploitation of the probabilistic timing behaviours during system design, leading to sub-optimal design solutions. Modelling the system as a probabilistic directed acyclic graph ($p$-DAG), this paper presents a probabilistic response time analysis based on different longest paths of the$p$-DAG across all execution scenarios, enhancing the capability of the analysis by eliminating the need for enumeration. We first identify every longest path candidate based on the structure of$\boldsymbol{p}$-DAG and compute the probability of its occurrence, where each candidate is the longest under certain execution scenarios. Then, the worst-case interfering workload is computed for each longest path candidate, forming a complete probabilistic response time distribution with correctness guarantees. Experiments show that compared to the enumeration-based approach, the proposed analysis reduces the computation cost by six orders of magnitude while maintaining a low deviation ($\mathbf{1. 0 4 \%}$on average and below$\mathbf{5 \%}$for most$\boldsymbol{p}$-DAGs).