一种基于任务复制调度算法研究  

Research on a Scheduling Algorithm Based on Task Duplication

作　　者：林剑柠[1] 吴慧中[1] 

机构地区：[1]南京理工大学计算机系,江苏南京210094

出　　处：《小型微型计算机系统》2006年第7期1296-1299,共4页Journal of Chinese Computer Systems

基　　金：国防预研课题基金项目(51404020303BQ0220)资助;南京市重点攻关基金项目资助.

摘　　要：分布式计算系统中任务调度是NP完全问题,调度算法可以分为任务复制和无任务复制两类.本文在简述了传统TDS算法的缺陷后,提出了一种改进的TDS任务调度算法-M TDS.该算法基于异构计算系统的特点,采用动态DAG图,尽可能的提前每个任务的执行时间,缩短所有任务完成的执行时间;并且避免出现在某一个执行序列中由于某一任务执行时间过长,而影响整个程序的执行时间.The problem of scheduling parallel program task s on network of work station is known to be NP complete. The scheduling algorithms are classified into two categories： one is to include task duplication; the other is non-task duplication. Drawbacks of the custom TDS algorithm were discussed and a modified TDS algorithm called as MTDS was presented. This algorithm was based on the characters of the HC and the dynamical DAG, which would shorten the makespan of the whole tasks ; and also avoided that some certain tasks that were in one execution list occupy the computing resources too much time so as to delay execution time of the whole programs.

关 键 词：分布式 任务复制 DAG 异构 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]