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.
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
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
����. ����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)
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
Wu Min You, Shu Wei, Chen Yong. Runtime parallel incremental scheduling of DAGs International Conference on Parallel Processing. 2000:541-548
�²���,����ǿ,�λ���. һ����Ԥ�Ⲣ�г���Ч�ʵ�����ģ��[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)
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