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

摘要

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