Granted Patent B2

US 9,875,142 · App. 13/848,934 · Granted Jan 23, 2018

Abstract

Claims (104)

1. A system for scheduling jobs in a cluster of compute nodes, said system comprising:

at least one processor programmed to:

receive a job with an unknown resource requirement profile, the job including a plurality of tasks;

wherein the resource requirement profile for the job includes the following compute resources:

central processing unit (CPU) usage;

disk input/output (I/O) usage; and

memory usage;

wherein the at least one processor is further programed to:

infer a compute resource that most affects task completion by:

determining a magnitude of an extent of dependence on CPU usage by scheduling tasks of the plurality of tasks on a first two compute nodes of the plurality of compute nodes that are similar with respect to disk I/O usage and memory usage but differ with respect to CPU usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the first two compute nodes;

determining a magnitude of an extent of dependence on disk I/O usage by scheduling tasks of the plurality of tasks on a second two compute nodes of the plurality of compute nodes that are similar with respect to CPU usage and memory usage but differ with respect to disk I/O usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the second two compute nodes; and

determining a magnitude of an extent of dependence on memory usage by scheduling tasks of the plurality of tasks on a third two compute nodes of the plurality of compute nodes that are similar with respect to CPU usage and disk I/O usage but differ with respect to memory usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the third two compute nodes;

wherein the processor is further programmed to schedule execution of remaining tasks of the job on the compute nodes of the cluster using the resource requirement profile based on the compute resource that most affects task completion.

2. The system according to claim 1 , wherein the plurality of tasks share a common resource requirement profile.

3. The system according to claim 1 , wherein the at least one processor is further programmed to:

match the resource requirement profile of the job to capability profiles of the compute nodes of the cluster to schedule execution of the remaining tasks of the job on the compute nodes of the cluster.

4. The system according to claim 1 , wherein the at least one processor is further programmed to:

infer the resource requirement profile for the job using a Bayesian experimental design.

5. The system according to claim 1 , wherein that at least one processor is further programmed to:

schedule execution of base tasks on the compute nodes, wherein the base tasks are different than the plurality of tasks;

receive timing information regarding execution time of the scheduled base tasks including an amount of time to complete execution of a base task; and

infer capability profiles for the compute nodes based on the received timing information regarding the base tasks.

6. The system according to the claim 5 , wherein the base tasks have known resource requirement profiles.

7. The system according to claim 5 , wherein the at least one processor is further programmed to:

schedule execution of each of the base tasks on each of the compute nodes.

8. The system according to claim 5 , wherein the at least one processor is further programmed to:

infer capability profiles for the compute nodes before scheduling execution of the some of the plurality of tasks.

9. The system according to claim 5 , wherein the at least one processor is further programmed to:

compare the relative time it took each of the compute nodes to finish each of the base tasks to infer the relative capability profiles for the compute nodes.

10. The system according to claim 1 , wherein the job utilizes a map-reduce framework.

11. The system according to claim 1 , wherein the at least one processor is further programmed to:

determine a metric indicative of how well the resource requirement profile was inferred; and

if the metric does not fall within a predetermined range, gather additional timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task, and update the resource requirement profile with the additional timing information.

12. A method for scheduling jobs in a cluster of compute nodes, said method performed by at least one processor and comprising:

receiving a job with an unknown resource requirement profile, the job including a plurality of tasks;

scheduling execution of some of the plurality of tasks on compute nodes of the cluster with differing capability profiles; and

receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task;

wherein the resource requirement profile for the job includes the following compute resources:

central processing unit (CPU) usage;

disk input/output (I/O) usage; and

memory usage;

wherein the method further incudes inferring a compute resource that most affects task completion by:

determining a magnitude of an extent of dependence on CPU usage by scheduling tasks of the plurality of tasks on a first two compute nodes of the plurality of compute nodes that are similar with respect to disk I/O usage and memory usage but differ with respect to CPU usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the first two compute nodes;

determining a magnitude of an extent of dependence on disk I/O usage by scheduling tasks of the plurality of tasks on a second two compute nodes of the plurality of compute nodes that are similar with respect to CPU usage and memory usage but differ with respect to disk I/O usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the second two compute nodes; and

determining a magnitude of an extent of dependence on memory usage by scheduling tasks of the plurality of tasks on a third two compute nodes of the plurality of compute nodes that are similar with respect to CPU usage and disk I/O usage but differ with respect to memory usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the third two compute nodes; and

wherein the method further includes scheduling execution of the remaining tasks of the job on the compute nodes using the resource requirement profile based on the compute resource that most affects task completion.

13. The method according to claim 12 , wherein the plurality of tasks share a common resource requirement profile.

14. The method according to claim 12 , further including:

matching the resource requirement profile of the job to capability profiles of the compute nodes of the cluster to schedule execution of the remaining tasks of the job on the compute nodes of the cluster.

15. The method according to claim 12 , further including:

inferring the resource requirement profile for the job using a Bayesian experimental design.

16. The method according to claim 12 , further including:

scheduling execution of base tasks on the compute nodes, wherein the base tasks are different than the plurality of tasks;

receiving timing information regarding execution time of the scheduled base tasks including an amount of time to complete execution of a base task; and

before scheduling execution of the some of the plurality of tasks, inferring capability profiles for the compute nodes based on the received timing information regarding the base tasks.

17. The method according to the claim 16 , wherein the base tasks have known resource requirement profiles.

18. The method according to claim 16 , further including:

comparing the relative time it took each of the compute nodes to finish each of the base tasks to infer the capability profiles for the compute nodes.

19. A map-reduce system for executing jobs, said system comprising:

a plurality of interconnected compute nodes defining a cluster, the plurality of interconnected compute nodes includes a name node and a plurality of data nodes, the name node configured to:

receive a job with an unknown resource requirement profile, the job including a plurality of tasks;

schedule execution of some of the plurality of tasks on data nodes of the cluster with differing capability profiles; and

receive timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task;

wherein the resource requirement profile for the job includes the following compute resources:

central processing unit (CPU) usage;

disk input/output (I/O) usage; and

memory usage;

wherein the name node is further configured to:

infer a compute resource that most affects task completion by:

determining a magnitude of an extent of dependence on CPU usage by scheduling tasks of the plurality of tasks on a first two data nodes of the plurality of data nodes that are similar with respect to disk I/O usage and memory usage but differ with respect to CPU usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the first two data nodes;

determining a magnitude of an extent of dependence on disk I/O usage by scheduling tasks of the plurality of tasks on a second two data nodes of the plurality of data nodes that are similar with respect to CPU usage and memory usage but differ with respect to disk I/O usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the second two data nodes; and

determining a magnitude of an extent of dependence on memory usage by scheduling tasks of the plurality of tasks on a third two data nodes of the plurality of data nodes that are similar with respect to CPU usage and disk I/O usage but differ with respect to memory usage, and receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task on the third two data nodes; and

wherein the name node is further configured to schedule execution of the remaining tasks of the job on the data nodes using the resource requirement profile based on a compute resource that most affects task completion.

20. The map-reduce system of claim 19 , wherein the name node is further configured to schedule the execution of the some of the plurality of tasks on data nodes of the cluster with differing capability profiles with a predetermined number of tasks of the plurality of tasks on pairs of data nodes that are substantially different from each other in terms of their resources.

21. The map-reduce system of claim 20 , wherein the predetermined number is three.

22. A method for scheduling jobs in a cluster of compute nodes, said method performed by at least one processor and comprising:

receiving a job with an unknown resource requirement profile, the job including a plurality of tasks;

scheduling execution of some of the plurality of tasks on compute nodes of the cluster with differing capability profiles;

receiving timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task;

inferring a resource requirement profile for the job based on the received timing information and the differing capability profiles; and

scheduling execution of remaining tasks of the job on the compute nodes of the cluster using the resource requirement profile;

wherein the resource requirement profile for the job includes the following compute resources:

central processing unit (CPU) usage;

disk input/output (I/O) usage; and

memory usage;

wherein the scheduling is based on a compute resource that most affects task completion;

wherein the method further includes:

determining a metric indicative of how well the resource requirement profile was inferred; and

in response to the metric not being within a predetermined range, gathering additional timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task, and updating the resource requirement profile with the additional timing information.

23. A map-reduce system for executing jobs, said system comprising:

a plurality of interconnected compute nodes defining a cluster, the plurality of interconnected compute nodes includes a name node and a plurality of data nodes, the name node configured to:

receive a job with an unknown resource requirement profile, the job including a plurality of tasks;

schedule execution of some of the plurality of tasks on data nodes of the cluster with differing capability profiles;

receive timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task;

infer a resource requirement profile for the job based on the received timing information and the differing capability profiles; and

schedule execution of remaining tasks of the job on the data nodes of the cluster using the resource requirement profile;

wherein the resource requirement profile for the job includes the following compute resources:

central processing unit (CPU) usage;

disk input/output (I/O) usage; and

memory usage;

wherein the scheduling is based on a compute resource that most affects task completion; and

wherein the name node is further configured to:

determine a metric indicative of how well the resource requirement profile was inferred; and

if the metric does not fall within a predetermined range, gather additional timing information regarding execution time of the scheduled tasks including an amount of time to complete execution of a task, and update the resource requirement profile with the additional timing information.

Assignments (9)