Method of scheduling grid applications with task replication

摘要

A method of scheduling grid applications comprises the steps of estimating the task execution times, grouping the tasks and assigning said groups of tasks to computational units or grid nodes. As the grid nodes complete their task, tasks are replicated so as to balance the remaining amount of computation between the nodes. In one particular embodiment scheduling of the tasks is done using a task queue which is updated when a node completes the processing of a task. Where a replica of the task is still running this is aborted by the scheduling unit. If the node is idle then tasks still running on slower units are replicated to the idle unit. The task queue may correspond to a list of tasks ordered by size. The grouping of tasks may be based on a static determination of the relative processing power of a node. The replication may occur if a task has not been completed in a specified time wherein the node will be considered to be offline or have failed.