带有分支结构OpenMP任务图的响应时间分析

Exactly Analyzing Response Time of OpenMP Tasks with Conditional Branches

随着多核技术在实时系统中广泛应用,实时程序的并行化成为当前的研究热点.在实时领域,有向无环图(DAG)是刻画并行实时程序的理论模型.然而,传统的DAG任务图并不能刻画并行程序的实际特征(例如if-else控制流结构).于是,能够同时反映程序的并行负载特征和if-else控制流结构的分支并行任务图(conditional DAG:con-DAG)应运而生.目前,实时领域通常假设con-DAG满足某种特殊结构,即图中的并行子结构和分支子结构必须是单入口和单出口(简称为“单入单出”).在这种约束下,con-DAG的响应时间分析问题具有多项式时间算法.然而,现实的OpenMP程序具有更加灵活的结构.“单入单出”假设一旦失效,con-DAG响应时间分析是否依然存在多项式时间算法为开放性问题.本文针对一般情况下OpenMP程序的分支结构开展研究.对于非“单入单出”con-DAG图上响应时间分析问题,基于动态规划理论,提出了多项式时间的求解方法.实验表明,本文方法求得的con-DAG响应时间在之前方法的基础上能够提升3%,为实时并行程序的可预测性提供更精确的理论支撑.

Multi-cores are becoming mainstream hardware platforms for embedded and real-time systems.To fully utilize the processing capacity of multi-cores,software should be parallelized.Recently much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs(DAG),motivated by the parallel task structures supported by popular parallel programming frameworks such as OpenMP.The DAG-based task models in existing real-time scheduling research cannot fully capture critical features of parallel programs,e.g.,if-else conditional structure.Recently,the conditional DAG models are proposed to formulate the real-time systems composed by parallel workload and conditional components.Existing DAG-based task models in real-time scheduling research assume special structures recursively composed by single-source-single-sink parallel and conditional components.With this special assumption,polynomial-time response time analysis method is developed.However,realistic OpenMP task systems in general have more flexible structures that do not comply with this assumption.This paper studies general OpenMP task systems with general branching structures,and develops a polynomial-time dynamic programming algorithm to efficiently calculate response time bounds for OpenMP task systems.First,this paper outlines OpenMP program semantics,and model the behaviors of general OpenMP task systems with general branching structures,including task models,execution models and scheduling models.Second,this paper deeply analyzes the related method in the existing work.By constructing a counterexample,we find that the existing method cannot accurately calculate the response time boundary of the task graphs,and there is a certain pessimism.The specific reason is that although the existing method considers OpenMP task graphs with multi-source-multi-sink conditional branching structures,it cannot correctly analyze some situations,e.g.,the parameters associated with the two branches in the conditional branching structure are quite different.Third,for the analysis problem of response time on multi-source-multi-sink con-DAG graphs,based on dynamic programming theory,this paper proposes an accurate solution method of polynomial time.The main idea of this method is as follows.The DAG graph is traversed topologically in reverse order,then the parameters associated with the predecessor nodes are calculated by using the calculation results of the successor nodes,and finally the response time bound of the DAG graph is calculated based on the values of the associated variables of the source node.Compared with the existing algorithm,the algorithm in this paper introduces more node-associated variables and considers more node types.In the experiment part,we implement the algorithm of existing work and the algorithm in this paper.The response time bounds of the two algorithms are evaluated by randomly generated DAGs.Experimental work shows that compared to the traditional method,our method can effectively improve the accuracy of the response time bound.Under average conditions,the accuracy of the response time bound can be increased by 3%.It is very important for real-time system to improve the accuracy of response time bound effectively.In real-time systems,the response time directly affects the schedulability of systems.For real-time systems whose schedulability is in critical state,the accuracy of response time is increased by 1%,which is likely to greatly increase the schedulability of systems.