Efficient Granularity and Clustering of the Directed Acyclic Graphs

摘要：

The granularity of the DAG which determines the trade-off between communication and execution costs is the most important factor in DAG scheduling. So this paper firstly gives a DAG model and its clustering problem; Secondly, it addresses the drawbacks of the existing granularity definitions; Thirdly, it proposes a new granularity definition of the DAG which is very useful for the large communication delay DAGs. Based on this new definition, the paper proves that nonlinearly clustering is better for linearly clustering for the fine grain DAGs;Finally, it gives the bounds for linearly clustering for the DAGs.

关键词： DAG Granularity Linearly Clustering Nonlinearly Clustering performance bound

作者: Qiangsheng Hua Zhigang Chen

作者单位: Student Member, ACM, IEEE and IEEE Computer Society and Communication Society College of Information Science&Engineering, Central South University, Changsha (410083),China

会议类型: 国际会议

会议名称: Proceedings of The Fourth International Conference on Parallel and Distribyted Computing,Applications and Technologies(第四届并行与分布式计算应用与技术国际会议)

会议地点: 成都

会议语种:英文

页码: 625-628

在线出版日期: 2003-08-27（万方平台首次上网日期，不代表论文的发表时间）