基于任务复制的分簇与调度算法.doc

:..1基于任务复制的分簇与调度算法何琨1),2),赵勇2),黄文奇1)1)(华中科技大学计算机科学与技术学院武汉430074)2)(华中科技大学控制科学与工程系武汉430074)摘要 对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法。改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界。实验结果优于近现代的典型任务复制算法,特别是对经典EZ算例的解(makespan为8)好于前人认为的理论最优解(),并证明了新的解为最优解。定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法。关键词 任务复制;任务分簇;调度算法;DAG;任务粒度中图法分类号 TP311AClusteringandSchedulingAlgorithmBasedonTaskDuplicationHEKun1),2),ZHAOYong2),HUANGWen-Qi1)1)(puterScience,HuazhongUniversityofScienceandTechnology,Wuhan430074)2)(ControlScienceandEngineeringDepartment,HuazhongUniversityofScienceandTechnology,Wuhan430074)AbstractThispaperaddressesanimportantandclassicschedulingproblem,,(DAG),monlycategorizedtoprioritylistbased,-duplication-based(TDB)algorithmsareofbetterperformancethannon-,riticalpredecessor(DCP)algorithm,,,DCPalgorithmachievesabe