一种扩展的随机DAG模型

针对并行程序结构产生任务计算量和通信量随机性的情况,提出了一种扩展的随机DAG(Directed Acyclic Graph)模型,同时考虑了计算环境异构性和并行程序结构带来的计算时间和通信时间偏移量;基于此扩展的随机DAG,给出了DAG中节点的EST(Earliest Start Time)和偏移量的计算方法,以标准方差和平均值的和的数学期望来表示;最后,给出了基于扩展随机DAG的并行程序建模方法,通过计算实例验证了该扩展的合理性.实验结果表明,通过优化并行程序结构,可以提高并行程序的执行效率,并且更好地实现并行计算负载平衡.

Expanded stochastic DAG model

Considering the fact that parallel program structure can induce the randomcity of tasks' computing and communication cost,the definition of stochastic directed acyclic graph(DAG) was expanded,in which the heterogeneity and the parallel program structure were considered together.Based on this model,the method to computing the nodes' earliest start time(EST) and standard deviation were presented,which was expressed as the expectation operator of a summation of standard deviation and the mean.A parallel program modeling method was provided based on the expanded stochastic DAG.The expanded definition has been validated by experiments.The results show that by optimizing the parallel program structure and considering the heterogeneous environment,the parallel program execution efficiency can be improved greatly,as well as the load-balance.