With the widespread application of multi-core technology in real-time embedded systems,multi-core processors have become the mainstream hardware platform.To fully utilize the powerful computational capabilities of multi-cores,comprehensive parallelization must be implemented in real-time programs.Directed Acyclic Graph(DAG)describes the parallelism of real-time programs which can effectively depict the fine-grained parallel characteristics of complex tasks.Intra-task Priority Assignment can reduce the uncertainty in the runtime behavior of DAG tasks,resulting in a smaller Worst-Case Response Time(WCRT).Existing response time analyses for priority-based DAG tasks focus on the upper bound of the WCRT.However,these analyses tend to be pessimistic due to the gap between the upper bound and the exact WCRT.This pessimism limits the computational performance of real-time embedded systems,causing them to occupy more computational resources to ensure tasks are completed within their deadlines.This paper focuses on response time analysis of prioritized DAG tasks and proposes an improved method that employs Satisfiability Modulo Theories(SMT)to compute a more accurate upper bound for DAG task response time.Although previous studies have provided exact WCRT analysis for DAG tasks,these findings do not extend to DAGs with priorities,and existing methods still exhibit pessimism.This paper formalizes the response time analysis of priority-based DAG tasks into a satisfiability problem of mixed logical formulas and gets the exact WCRT.Experimental work shows that the method proposed in this paper not only guarantees the precision of the obtained bounds but also improves the average computational efficiency by 50%compared to existing methods for accurately calculating the WCRT of DAG tasks.
万方数据
维普
