SYSTEM AND METHOD FOR PROACTIVE TASK SCHEDULING

• US 20120167101A1
• Filed: 12/28/2010
• Published: 06/28/2012
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kandula, Srikanth, Ananthanarayanan, Ganesh, Greenberg, Albert, Lu, Yi, Saha, Bikas, Harris, Edward
• Granted Patent: US 9,307,048 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests

Abstract

The described implementations relate to distributed computing. One implementation provides a system that can include an outlier detection component that is configured to identify an outlier task from a plurality of tasks based on runtimes of the plurality of tasks. The system can also include a cause evaluation component that is configured to evaluate a cause of the outlier task. For example, the cause of the outlier task can be an amount of data processed by the outlier task, contention for resources used to execute the outlier task, or a communication link with congested bandwidth that is used by the outlier task to input or output data. The system can also include one or more processing devices configured to execute one or more of the components.

Claims

1. A system comprising:

an outlier detection component configured to identify an outlier task from a plurality of tasks based on runtimes of the plurality of tasks;

a cause evaluation component configured to evaluate a cause of the outlier task, wherein the cause of the outlier task is one or more of;

an amount of data processed by the outlier task,

contention for resources used to execute the outlier task, or

a communication link with congested bandwidth that is used by the outlier task to input or output data, and

one or more processing devices configured to execute one or more of the components.

2. The system according to claim 1, wherein the contention for resources is based on processor or memory utilization on a server that executes the outlier task.

3. The system according to claim 2, wherein at least two of the plurality of tasks execute concurrently.

4. The system according to claim 1, wherein the plurality of tasks comprise tasks from a processing phase of a job.

5. The system according to claim 4, further comprising a task scheduling component configured to schedule at least one task from a subsequent processing phase of the job after completion of at least one of the tasks from the processing phase.

6. The system according to claim 1, further comprising a task scheduling component configured to schedule the plurality of tasks in a plurality of processing slots.

7. The system according to claim 6, wherein the task scheduling component is further configured to:

determine if there is an available processing slot; and

duplicate the outlier task in the available processing slot.

8. The system according to claim 1, further comprising a task scheduling component configured to:

schedule a copy of the outlier task in an instance where the cause is contention for resources; and

continue to let the outlier task execute without scheduling the copy in an instance where the cause is the amount of data processed by the outlier task.

9. The system according to claim 1, further comprising a task scheduling component configured to:

determine a likelihood that a copy of the outlier task will complete before the outlier task; and

determine whether to kill and restart the outlier task based on the likelihood.

10. The system according to claim 1, further comprising a task scheduling component configured to:

compare an estimated remaining time for the outlier task to complete to an estimated time for a copy of the outlier task to complete; and

determine whether to duplicate the outlier task based on the comparing.

11. The system according to claim 10, wherein the estimated time for the copy of the outlier task to complete is based on processing rates of other individual tasks in the same processing phase as the outlier task.

12. The system according to claim 1, wherein:

the cause evaluation component is further configured to evaluate the plurality of tasks for probability of loss of output causing at least one subsequent task to be stalled waiting for the lost output to be recomputed, and

the system further comprises a scheduling component configured to replicate the output of an individual task based on the probability of loss of the output or rerun individual tasks whose output is detected to have been lost.

13. One or more computer-readable storage media comprising instructions which, when executed by one or more processing devices, perform:

monitoring execution of a plurality of tasks associated with a job; and

determining whether to schedule a copy of an individual one of the tasks based on an estimated remaining time for the individual task to complete,

wherein the copy comprises a duplicate of the individual task or a kill and restart of the individual task.

14. The computer-readable storage media according to claim 13, further comprising instructions which, when executed by the one or more processing devices, perform:

determining the estimated remaining time for the individual task to complete based on an amount of input data remaining to be processed by the individual task.

15. The computer-readable storage media according to claim 13, further comprising instructions which, when executed by the one or more processing devices, perform:

determining an estimated probability that the copy of the individual task will complete sooner than the individual task, based on the estimated remaining time.

16. The computer-readable storage media according to claim 15, further comprising instructions which, when executed by the one or more processing devices, perform:

scheduling the copy of the individual task, in an instance where the estimated probability exceeds a threshold.

17. A method comprising:

identifying an amount of data that is input or output by individual tasks associated with a job;

identifying available bandwidth for input or output of data by one or more processing devices;

comparing the amount of data to the available bandwidth; and

scheduling the individual tasks on individual processing devices based on the comparing.

18. The method according to claim 17, wherein the one or more processing devices comprise servers of a server rack, and the available bandwidth is bandwidth over a communication link connecting the servers of the server rack.

19. The method according to claim 17, further comprising:

computing data transfer times for permutations of placements of individual tasks on the one or more processing devices; and

selecting one of the permutations based on the data transfer times.

20. The method according to claim 17, wherein the plurality of tasks are associated with a reduce phase that processes outputs of at least one task from a preceding map phase.