Economical Duplication Based Task Scheduling for Heterogeneous and Homogeneous Computing Systems
Economical Duplication Based Task Scheduling for Heterogeneous and Homogeneous Computing Systems
复制标题
DOI：
10.1109/iadcc.2009.4808986
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
A. Agarwal;Padam Kumar
中科院分区：
文献类型：
--
作者：
A. Agarwal;Padam Kumar
基于任务复制的调度算法在不牺牲效率的情况下产生较短的调度时间，但由于大量的复制而使计算资源过度消耗。在本文中，我们试图优化后产生的时间表，而不影响总的时间表长度（makespan）的重复。本文提出了两种具有经济复制的工作流调度算法，即同构系统的缩减复制算法（ReducedDuplicationforHomogeneousSystems，RD）和异构系统的异构经济复制算法（HeterogeneousEconomicalDuplicationforHomogeneousSystems，HED）。在这些算法中，一个静态的任务调度使用基于插入的任务重复调度策略，并试图通过删除一些重复的任务在调度中，删除不影响的最大完工时间的负面影响进行优化。此外，在某些情况下，任务的较早调度在其稍后在不同处理器上被复制之后变得无效。该算法调查和删除这样的时间表，以减少处理器的消耗。删除这些无用的任务会在调度中产生更大的调度洞，这可以更好地用于调度其他并行和分布式应用程序，如在网格环境中。仿真结果表明，RD和HED算法在同构系统中比SD、CPFD算法和异构系统中比HLD、LDBS算法具有更少的重复次数和更少的处理器消耗，从而产生更好的调度.
Task duplication based scheduling algorithms generate shorter schedules without sacrificing efficiency but leave the computing resources over consumed due to the heavily duplications. In this paper, we try to optimize the duplications after generating a schedule without affecting the overall schedule length (makespan). Here, we suggested two workflow scheduling algorithms with economical duplication i.e. Reduced Duplication for homogeneous systems (RD) and Heterogeneous Economical Duplication (HED) for heterogeneous systems respectively. In these algorithms, a static task schedule is generated using an insertion-based task-duplication scheduling strategy and try to optimized by removing some duplicated tasks in the schedule whose removal does not affect the makespan adversely. Further, in some situations, the earlier schedule of a task becomes unproductive after it has been duplicated later on different processor(s). The algorithms investigate and remove such schedules in order to reduce processor consumption. Removing such useless tasks generate larger scheduling holes in the schedule, which can be better utilized for scheduling other parallel and distributed applications such as in grid environment. The simulation results show that RD and HED algorithms generate better schedule with lesser number of duplications and remarkably less processor consumption as compared with SD, CPFD for homogeneous systems and HLD, LDBS for heterogeneous systems.