作者搜索 |
 |
新闻 |
 10.5.5C-DBLP系统正式发布作者研究兴趣及学术活动展示功能，请访问作者页面试用。
|
|
09.7.6 C-DBLP的文献BibTex信息展示功能正式上线，请访问文章详细页面使用。
|
|
09.7.29 C-DBLP系统新增同名区分功能，欢迎大家在作者页面试用。该功能部分使用了清华大学王建勇老师课题组提出的GHOST（GrapH-based framewOrk for name diStincTion）算法，在此表示感谢。
|
|
09.6.2 C-DBLP系统集成了作者的相关图片并在搜索结果页面展示，敬请试用。
|
| 基于扩展的随机DAG的并行任务调度算法研究 BibTex | |
| 作者： | 姜燕 胡凯 杨志斌 张新宇 |
| 单位： | 北京航空航天大学计算机学院 |
| 关键词： | 扩展的随机DAG;EST;SCP算法;SSCP算法 |
| 出处： | 计算机科学 2008 年 07期 |
| 基金： | 航空科学基金资助项目(20060151003) |
| 全文链接： | 查看全文>> |
| 摘要： | |
| 针对并行程序结构产生任务计算量和通信量的随机性,提出了一种扩展的随机DAG模型。基于此模型对DAG调度中常用调度算法关键路径SCP(Static Critical Path)算法进行了详细的分析,提出了相应的扩展的随机DAG的调度方法SSCP(Stochastic Static Critical Path)算法。同时,给出了扩展的随机DAG中节点的EST(Earliest Start Time)计算方法,并以SCP算法为例进行实验模拟。实验结果表明,SSCP算法相对于SCP算法,减少了并行任务执行时间,并能更精确地预测任务调度的平均执行时间。 | |
| 正文快照： | |
| 1引言自上个世纪60年代以来,国内外的学者就开始研究怎样调度DAG(directed acyclic graph)任务图,并且诞生了很多调度算法。一般情况下,DAG调度是NP完全问题。目前的大部分DAG调度算法均基于启发式调度,包括表调度算法[1,2],聚簇类算法[3,4],基于任务复制的调度算法[5,6],以及 | |
| Parallel Tasks Scheduling Based on Expanded Stochastic DAG | |
| Author： | JIANG Yan HU Kai YANG Zhi-bing ZHANG Xin-yu (School of Computer Science and Technology;Beijing University of Aeronautics and Astronautics;Beijing 100083;China) |
| Keywords： | Expanded stochastic DAG,EST,SCP algorithm,SSCP algorithm |
| Abstract： | |
| Considering that fact the structure of parallel program can induce the randomcity of tasks computing and communication cost,the definition of stochastic DAG is expanded.Some researches on parallel tasks scheduling algorithms have been done based on this expanded model.The typical algorithms(SCP) are anglicized in detail,SSCP algorithm for the expanded stochastic DAG is presented correspondingly.Then a method to compute the nodes EST is provided.And experiments have been done to simulate it.The experiments results indicate that a significant improvement in the average parallel execution times of expanded stochastic DAG can be achieved by the proposed approach and SSCP algorithm is able to more accurately predict the actual performance than the algorithm SCP. | |