Expanded stochastic DAG model
-
摘要: 针对并行程序结构产生任务计算量和通信量随机性的情况,提出了一种扩展的随机DAG(Directed Acyclic Graph)模型,同时考虑了计算环境异构性和并行程序结构带来的计算时间和通信时间偏移量;基于此扩展的随机DAG,给出了DAG中节点的EST(Earliest Start Time)和偏移量的计算方法,以标准方差和平均值的和的数学期望来表示;最后,给出了基于扩展随机DAG的并行程序建模方法,通过计算实例验证了该扩展的合理性.实验结果表明,通过优化并行程序结构,可以提高并行程序的执行效率,并且更好地实现并行计算负载平衡.Abstract: 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.
-
Key words:
- stochastic DAG /
- heterogeneity /
- parallel program structure /
- stander deviation
-
[1] Kamthe Ankur , Lee S Y . A stochastic approach to estimating earliest start times of nodes for scheduling DAGs on heterogeneous distributed computing systems Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, 2005 [2] Midorikawa Edson T, de Oliveira Helio M, Laine Jean M. PEMPIs:a new methodology for modeling and prediction of MPI programs performance 16th Symposium on Computer Architecture and High Performance Computing(SBAC-PAD-04),2004:246-253 [3] 崔焕庆. 基于Petri网的MPI并行程序建模与正确性验证 .泰安:山东科技大学计算机科学与工程学院,2004 Cui Huanqing. The model and verification of MPI parallel programs based on Petri net .Tai-an:College of Information Science and Engineering, Shandong University of Science and Technology, 2004 (in Chinese) [4] Paradyn Project. Paradyn developer-s guide . 2001. ftp://grilled.cs.wisc.edu./paradyn_manuals/developerGuide.pdf. [5] Wu C Eric, Bolmarcich Anthony. Gantt chart visualization for MPI and apache multi-dimensional trace files Parallel and Distributed Systems, IEEE, 2002 Proceedings Ninth International Conference. 2002:523-528 [6] Wu Min You, Shu Wei, Chen Yong. Runtime parallel incremental scheduling of DAGs International Conference on Parallel Processing. 2000:541-548 [7] 陈昌生,孙永强,何积丰. 一个可预测并行程序效率的评价模型[J]. 软件学报, 2000,11(11):1485-1491 Cheng Changsheng, Sun Yongqiang, He Jifeng. An evaluation model for predicting the efficiency of parallel programs [J]. Journal of Software, 2000,11(11):1485-1491(in Chinese) [8] Michael A Iverson, Fuèsun Oè zguèner, Lee Potter. Statistical prediction of task execution times through analytic benchmarking for scheduling in heterogeneous environment [J]. IEEE Transactions on Computers, 1999, 48(12):1374-1379 -
点击查看大图
计量
- 文章访问数: 3285
- HTML全文浏览量: 119
- PDF下载量: 1156
- 被引次数: 0
下载:
