Parameter selection for optimization of task execution based on execution history for prior tasks

Patent metadata

Field	Value
Publication number	US-9720732-B1
Application number	US-201313764708-A
Country	US
Kind code	B1
Filing date	Feb 11, 2013
Priority date	Feb 11, 2013
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

Methods and systems for optimization of task execution are disclosed. A definition of a task is received. A plurality of parameter values for execution of the task are selected based on an execution history for a plurality of prior tasks performed for a plurality of clients. The plurality of parameter values are selected to optimize one or more execution constraints for the execution of the task. The execution of the task is initiated using one or more computing resources configured with the selected parameter values.

First claim

What is claimed is:

1. A system, comprising:
a plurality of computing devices configured to implement a plurality of computing resources of a provider network, wherein each computing resource has associated performance characteristics; and
one or more computing devices configured to implement a resource manager, wherein the resource manager is operable to:
receive a task specification and one or more execution constraints for execution of a task, wherein the execution constraints comprise a completion time for the execution of the task;
select a plurality of parameter values and one or more of the plurality of computing resources for the execution of the task based at least in part on an execution history for a plurality of prior tasks performed for a plurality of clients and based at least in part on the associated performance characteristics of the one or more of the plurality of computing resources, wherein the associated performance characteristics comprise a modeled completion time for the execution of the task, and wherein the selected parameter values and the selected computing resources optimize the one or more execution constraints for the execution of the task;
configure the selected computing resources with the selected parameter values; and
initiate the execution of the task using the selected computing resources configured with the selected parameter values.

2. The system as recited in claim 1 , wherein the resource manager is further operable to:
execute a plurality of additional tasks, wherein the parameter values vary for each of the plurality of additional tasks; and
monitor differences in execution among the plurality of additional tasks;
wherein the plurality of parameter values and the one or more computing resources are selected for the execution of the task based on the differences in execution among the plurality of additional tasks.

3. The system as recited in claim 1 , wherein the selected parameter values and the selected computing resources optimize a cost of the execution of the task as a primary constraint and the completion time as a secondary constraint, or wherein the selected parameter values and the selected computing resources optimize the completion time as the primary constraint and the cost as the secondary constraint.

4. The system as recited in claim 1 , wherein the execution constraints comprise a successful completion of the execution of the task.

5. A computer-implemented method, comprising:
receiving a definition of a task and one or more execution constraints for execution of the task, wherein the execution constraints comprise a completion time for the execution of the task;
selecting a plurality of parameter values for the execution of the task based on an execution history for a plurality of prior tasks performed for a plurality of clients, wherein the plurality of parameter values optimize the one or more execution constraints for the execution of the task; and
initiating the execution of the task using one or more computing resources configured with the selected parameter values, wherein the one or more computing resources are selected based at least in part on associated performance characteristics, wherein the associated performance characteristics comprise a modeled completion time for the execution of the task.

6. The method as recited in claim 5 , wherein the one or more execution constraints comprise a cost of the execution of the task.

7. The method as recited in claim 5 , wherein the plurality of parameter values optimize the one or more execution constraints for execution of the task and one or more additional tasks.

8. The method as recited in claim 5 , further comprising:
monitoring differences in execution for the plurality of prior tasks, wherein the parameter values vary for each of the plurality of prior tasks;
wherein the plurality of parameter values are selected for the execution of the task based on the differences in execution among the plurality of prior tasks.

9. The method as recited in claim 5 , wherein at least one of the parameter values comprises an indication of a cluster size or a cluster composition.

10. The method as recited in claim 5 , wherein at least one of the parameter values comprises an indication of an instance type for a compute instance.

11. The method as recited in claim 5 , wherein at least one of the parameter values comprises a ratio of mappers to reducers in a Hadoop cluster.

12. The method as recited in claim 5 , wherein the plurality of parameter values are selected using a constrained optimization process having a plurality of constraints, wherein at least one of the plurality of constraints comprises a successful completion of the execution of the task.

13. The method as recited in claim 5 , wherein the plurality of parameter values optimize a cost of the execution as a primary constraint and the completion time as a secondary constraint, or wherein the plurality of parameter values optimize the completion time as the primary constraint and the cost as the secondary constraint.

14. A system, comprising:
at least one processor;
a memory coupled to the at least one processor, wherein the memory stores program instructions, wherein the program instructions are executable by the at least one processor to:
receive a definition of a task and one or more execution constraints for execution of the task, wherein the execution constraints comprise a completion time for the execution of the task;
select a plurality of parameter values for the execution of the task based at least in part on an execution history for a plurality of prior tasks performed for a plurality of clients, wherein the plurality of parameter values optimize the one or more execution constraints for the execution of the task using one or more selected computing resources, wherein the computing resources are selected based at least in part on associated performance characteristics, wherein the associated performance characteristics comprise a modeled completion time for the execution of the task; and
initiate the execution of the task using the one or more selected computing resources configured with the selected parameter values.

15. The system as recited in claim 14 , wherein the program instructions are executable by the at least one processor to:
monitor differences in execution for a plurality of additional tasks, wherein the parameter values vary for each of the plurality of additional tasks;
wherein the plurality of parameter values are selected for the execution of the task based on the differences in execution among the plurality of additional tasks.

16. The system as recited in claim 15 , wherein the plurality of additional tasks comprise tasks submitted by a first client and a second client.

17. The system as recited in claim 14 , wherein the selected parameter values optimize a cost of the execution as a primary constraint and the completion time as a secondary constraint, or wherein the selected parameter values optimize the completion time as the primary constraint and the cost as the secondary constraint.

18. The system as recited in claim 14 , wherein the execution constraints comprise a successful completion of the execution of the task.

19. A non-transitory, computer-readable storage medium storing program instructions computer-executable to perform:
receiving a definition of a task and one or more execution constraints for execution of the task, wherein the execution constraints comprise a completion time for the execution of the task;
sel

Assignees

• Amazon Tech Inc

Inventors

• Shih Kathryn Marie
• Christofferson Carl Louis
• Cole Richard Jeffrey
• Sirota Peter
• Aggarwal Vaibhav

Classifications

• G06F9/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 title

• G06F2209/506

  Constraint · CPC title

• G06F2209/485

  Resource constraint · CPC title

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title