State management for task queues

• US 9,244,652 B1
• Filed: 08/12/2013
• Issued: 01/26/2016
• Est. Priority Date: 06/03/2013
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: Ellis, Edric, Martin, Jocelyn, Stefansson, Halldor N.
• Primary Examiner(s): Won, Michael Y
• Application Number:
  US13/964,803
• Time in Patent Office: 897 Days
• Field of Search: 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/5017 Task decomposition
• 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/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A client device may receive information that identifies tasks to be performed by worker devices. The tasks may include at least one task that is to be performed by all worker devices, and may include at least one task that is to be performed by one worker device. The client device may identify, based on the information that identifies the tasks, an order and dependencies associated with performing the tasks. The client device may determine a task, of the tasks, to be performed by a work device, of the worker devices, based on the order and the dependencies. The client device may send, to the worker device, information associated with performing the task, and may receive, from the worker device, an indication that the task has been performed. The client device may determine, based on the order and the dependencies, another task to be performed by the worker device.

Claims

1. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions that, when executed by one or more processors, cause the one or more processors to;

identify a group of tasks to be performed by a pool of worker devices,

the group of tasks including a state manipulation task to be performed by every worker device, included in the pool of worker devices, to modify a state of every worker device, and

the group of tasks including a plurality of ordinary evaluation tasks,

each ordinary evaluation task, included in the plurality of ordinary evaluation tasks, to be performed by a single worker device included in the pool of worker devices;

identify an order associated with performing the group of tasks,

the order indicating that the plurality of ordinary evaluation tasks are to be performed before the state manipulation task;

determine that a final ordinary evaluation task, included in the plurality of ordinary evaluation tasks, is to be performed by a worker device included in the pool of worker devices,

the determination being based on the order and information associated with performing at least one other ordinary evaluation task included in the plurality of ordinary evaluation tasks;

send, to the worker device, information associated with performing the final ordinary evaluation task; and

send, to another worker device included in the pool of worker devices, information associated with performing the state manipulation task based on sending the information associated with performing the final ordinary evaluation task and before receiving an indication that the final ordinary evaluation task has been performed by the worker device.

2. The non-transitory computer-readable medium of claim 1, where the one or more instructions, when executed by the one or more processors, further cause the one or more processors to:

receive, via user input, program code associated with the group of tasks that are to be performed by the pool of worker devices; and

where the one or more instructions, that cause the one or more processors to identify the group of tasks, cause the one or more processors to;

identify the group of tasks based on receiving the program code associated with the group of tasks.

3. The non-transitory computer-readable medium of claim 1, where the one or more instructions, when executed by the one or more processors, further cause the one or more processors to:

determine information associated with program code that, when executed, causes the final ordinary evaluation task to be performed; and

where the one or more instructions, that cause the one or more processors to send the information associated with performing the final ordinary evaluation task, cause the one or more processors too;

send the information associated with the program code.

4. The non-transitory computer-readable medium of claim 1, where the one or more instructions, when executed by the one or more processors, further cause the one or more processors to:

receive a result associated with performing the final ordinary evaluation task; and

update a display screen, associated with the group of tasks, based on the result associated with performing the final ordinary evaluation task.

5. The non-transitory computer-readable medium of claim 1, where the one or more instructions, that cause the one or more processors to determine that the final ordinary evaluation task is to be performed, cause the one or more processors to:

determine that the final ordinary evaluation task has not been performed by any worker device, included in the pool of worker devices, and that all preceding ordinary evaluation tasks, included in the plurality of ordinary evaluation tasks, have been performed; and

determine that the final ordinary evaluation task is to be performed based on determining that the final ordinary evaluation task has not been performed by any worker device and that all preceding ordinary evaluation tasks have been performed.

6. The non-transitory computer-readable medium of claim 1, where the one or more instructions, when executed by the one or more processors, cause the one or more processors to:

execute program code while waiting for a result of performing the final ordinary evaluation task.

7. The non-transitory computer-readable medium of claim 1, where the group of tasks is associated with iterations of a parallel loop included in program code.

8. A method, comprising:

identifying, by a device, a group of tasks to be performed by a pool of worker devices,

the group of tasks including a state manipulation task to be performed by every worker device, included in the pool of worker devices, to modify a state of every worker device, and

the group of tasks including a plurality of ordinary evaluation tasks,

each ordinary evaluation task, included in the plurality of ordinary evaluation tasks, to be performed by a single worker device included in the pool of worker devices;

identifying, by the device, an order associated with performing the group of tasks,

the order indicating that the plurality of ordinary evaluation tasks are to be performed before the state manipulation task;

determining, by the device, that a final ordinary evaluation task, included in the plurality of ordinary evaluation tasks, is to be performed by a worker device included in the pool of worker devices,

the determination being based on the order and information associated with performing at least one other ordinary evaluation task included in the plurality of ordinary evaluation tasks;

sending, by the device and to the worker device, information associated with performing the final ordinary evaluation task; and

sending, by the device and to another worker device included in the pool of worker devices, information associated with performing the state manipulation task based on sending the information associated with performing the final ordinary evaluation task and before receiving an indication that the final ordinary evaluation task has been performed by the worker device.

9. The method of claim 8, further comprising:

receiving, via user input, program code associated with the group of tasks that are to be performed by the pool of worker devices; and

where identifying the group of tasks comprises;

identifying the group of tasks based on receiving the program code associated with the group of tasks.

10. The method of claim 8, further comprising:

determining information associated with program code that, when executed, causes the final ordinary evaluation task to be performed; and

where sending the information associated with performing the final ordinary evaluation task comprises;

sending the information associated with the program code.

11. The method of claim 8, further comprising:

receiving a result associated with performing the final ordinary evaluation task; and

updating a display screen, associated with the group of tasks, based on the result associated with performing the final ordinary evaluation task.

12. The method of claim 8, where determining that the final ordinary evaluation task is to be performed comprises:

determining that the final ordinary evaluation task has not been performed by any worker device, included in the pool of worker devices, and that all preceding ordinary evaluation tasks, included in the plurality of ordinary evaluation tasks, have been performed; and

determining that the final ordinary evaluation task is to be performed based on determining that the final ordinary evaluation task has not been performed by any worker device and that all preceding ordinary evaluation tasks have been performed.

13. The method of claim 8, further comprising:

executing program code while waiting for a result of performing the final ordinary evaluation task.

14. The method of claim 8, where the group of tasks is associated with iterations of a parallel loop included in program code.

15. A device, comprising:

one or more processors to;

identify a group of tasks to be performed by a pool of worker devices,

the group of tasks including a state manipulation task to be performed by every worker device, included in the pool of worker devices, to modify a state of every worker device, and

the group of tasks including a plurality of ordinary evaluation tasks,

each ordinary evaluation task, included in the plurality of ordinary evaluation tasks, to be performed by a single worker device included in the pool of worker devices;

identify an order associated with performing the group of tasks,

the order indicating that the plurality of ordinary evaluation tasks are to be performed before the state manipulation task;

determine that a final ordinary evaluation task, included in the plurality of ordinary evaluation tasks, is to be performed by a worker device included in the pool of worker devices,

the determination being based on the order and information associated with performing at least one other ordinary evaluation task included in the plurality of ordinary evaluation tasks;

send, to the worker device, information associated with performing the final ordinary evaluation task; and

send, to another worker device included in the pool of worker devices, information associated with performing the state manipulation task based on sending the information associated with performing the final ordinary evaluation task and before receiving an indication that the final ordinary evaluation task has been performed by the worker device.

16. The device of claim 15, where the one or more processors are further to:

receive, via user input, program code associated with the group of tasks that are to be performed by the pool of worker devices; and

where the one or more processors, when identifying the group of tasks, are to;

identify the group of tasks based on receiving the program code associated with the group of tasks.

17. The device of claim 15, where the one or more processors are further to:

determine information associated with program code that, when executed, causes the final ordinary evaluation task to be performed; and

where the one or more processors, when sending the information associated with performing the final ordinary evaluation task, are to;

send the information associated with the program code.

18. The device of claim 15, where the one or more processors are further to:

receive a result associated with performing the final ordinary evaluation task; and

update a display screen, associated with the group of tasks, based on the result associated with performing the final ordinary evaluation task.

19. The device of claim 15, where the one or more processors, when determining that the final ordinary evaluation task is to be performed, are to:

determine that the final ordinary evaluation task has not been performed by any worker device, included in the pool of worker devices, and that all preceding ordinary evaluation tasks, included in the plurality of ordinary evaluation tasks, have been performed; and

determine that the final ordinary evaluation task is to be performed based on determining that the final ordinary evaluation task has not been performed by any worker device and that all preceding ordinary evaluation tasks have been performed.

20. The device of claim 15, where the one or more processors are to:

execute program code while waiting for a result of performing the final ordinary evaluation task.