Techniques for job flow processing

• US 10,310,896 B1
• Filed: 12/13/2018
• Issued: 06/04/2019
• Est. Priority Date: 03/15/2018
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Kichak, John Michael, Rowe, Edward L., Georges, James Edward, Kelly, Daniel Thomas, Sidle, Glenn Daniel, Cavalier, Charles Michael
• Primary Examiner(s): Swift, Charles M
• Application Number:
  US16/219,036
• Time in Patent Office: 173 Days
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• 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

Abstract

Various embodiments are generally directed to techniques for job flow processing, such as by ordering the performance of parallel tasks in a job flow to minimize a makespan for the job flow, for instance. Some embodiments are particularly directed to ordering the performance of tasks in a job flow based on computation of one or more independent and dependent metrics for tasks in a job flow. In many embodiments, tasks along a critical path of a job flow may be identified and prioritized using the one or more metrics computed for tasks in the job flow. For example, computing a time remaining until end and/or a longest path to end for each task in a job flow may enable a listing of tasks in the job flow to be ordered in a manner that prioritizes tasks to optimize the makespan for the job flow to be executed.

Claims

1. An apparatus comprising a processor and a storage to store instructions that, when executed by the processor, cause the processor to perform operations comprising:

identify a job flow comprising a set of tasks for performance, each task in the job flow associated with a duration, and each task in the job flow is connected to at least one upstream task or at least one downstream task, wherein an upstream task for a respective task requires completion before performance of the respective task and a downstream task requires completion after performance of the respective task;

determine a list of upstream tasks in the job flow;

identify a set of end chain tasks comprising one or more tasks in the job flow and excluded from the list of upstream tasks, the set of end chain tasks including a first end chain task and a second end chain task;

generate a data structure to store a held time remaining until end (TRUE) value for each task in the job flow;

compute a current TRUE value for each end chain task, wherein a respective current TRUE value for a respective end chain task in the set of end chain tasks comprises a duration associated with the respective end chain task;

update the held TRUE value in the data structure with the current TRUE value for each end chain task when the current TRUE value exceeds the held TRUE value;

identify a first set of upstream tasks comprising a first upstream task and a second upstream task, the first set of upstream tasks comprising one or more upstream tasks connected to the first end chain task in the set of end chain tasks;

compute a current TRUE value for each task in the first set of upstream tasks, wherein a respective current TRUE value for a respective task in the first set of upstream tasks comprises a sum of a duration associated with the respective task and the held TRUE value for the first end chain task;

update the held TRUE value in the data structure with the current TRUE value for each task in the first set of upstream tasks when the current TRUE value exceeds the held TRUE value; and

generate a job queue based on the data structure to store the held TRUE value for each task in the job flow, the job queue comprising a list of tasks in the job flow ordered from a largest held TRUE value to a smallest held TRUE value.

2. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

identify a second set of upstream tasks including the second upstream task and a third upstream task, the second set of upstream tasks comprising one or more upstream tasks connected to the second end chain task in the set of end chain tasks;

compute a current TRUE value for each task in the second set of upstream tasks, wherein a respective current TRUE value for a respective task in the second set of upstream tasks comprises a sum of a duration associated with the respective task and the held TRUE value for the second end chain task; and

update the held TRUE value in the data structure with the current TRUE value for each task in the second set of upstream tasks when the current TRUE value exceeds the held TRUE value.

3. The apparatus of claim 2, wherein the processor is caused to perform operations comprising replace the held TRUE value in the data structure with the current TRUE value based on a comparison of the current value for the second upstream task and the held TRUE value for the second upstream task to update the held TRUE value in the data structure with the current TRUE value for each task in the second set of upstream tasks when the current TRUE value exceeds the held TRUE value.

4. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

select a next task for assignment from the job queue;

identify an available task executor in a set of task executors; and

assign the next task for assignment to the available task executor for performance.

5. The apparatus of claim 1, the job queue including an indication of each upstream task of each task in the job flow.

6. The apparatus of claim 5, wherein the processor is caused to perform operations comprising assign a highest task in the job queue with all upstream tasks completed to a task executor when the task executor become available.

7. The apparatus of claim 1, wherein the processor is caused to perform operations comprising perform a trial run for each task in the set of tasks to determine the duration for each task in the set of tasks.

8. The apparatus of claim 1, wherein the processor is caused to perform operations comprising compute a makespan for the job flow, the makespan comprising a duration to perform the job flow with a defined number of executors based on the job queue.

9. The apparatus of claim 8, wherein the processor is caused to perform operations comprising recompute the makespan for the job flow based on a change in the defined number of executors.

10. The apparatus of claim 1, wherein the processor is caused to perform operations comprising identify a critical path for the job flow that begins with the task with the largest held TRUE value.

11. A computer-implemented method, comprising:

identifying a job flow comprising a set of tasks for performance, each task in the job flow associated with a duration, and each task in the job flow is connected to at least one upstream task or at least one downstream task, wherein an upstream task for a respective task requires completion before performance of the respective task and a downstream task requires completion after performance of the respective task;

determining a list of upstream tasks in the job flow;

identifying a set of end chain tasks comprising one or more tasks in the job flow and excluded from the list of upstream tasks, the set of end chain tasks including a first end chain task and a second end chain task;

generating a data structure to store a held time remaining until end (TRUE) value for each task in the job flow;

computing a current TRUE value for each end chain task, wherein a respective current TRUE value for a respective end chain task in the set of end chain tasks comprises a duration associated with the respective end chain task;

updating the held TRUE value in the data structure with the current TRUE value for each end chain task when the current TRUE value exceeds the held TRUE value;

identifying a first set of upstream tasks comprising a first upstream task and a second upstream task, the first set of upstream tasks comprising one or more upstream tasks connected to the first end chain task in the set of end chain tasks;

computing a current TRUE value for each task in the first set of upstream tasks, wherein a respective current TRUE value for a respective task in the first set of upstream tasks comprises a sum of a duration associated with the respective task and the held TRUE value for the first end chain task;

updating the held TRUE value in the data structure with the current TRUE value for each task in the first set of upstream tasks when the current TRUE value exceeds the held TRUE value; and

generating a job queue based on the data structure to store the held TRUE value for each task in the job flow, the job queue comprising a list of tasks in the job flow ordered from a largest held TRUE value to a smallest held TRUE value.

12. The computer-implemented method of claim 11, comprising:

identifying a second set of upstream tasks including the second upstream task and a third upstream task, the second set of upstream tasks comprising one or more upstream tasks connected to the second end chain task in the set of end chain tasks;

computing a current TRUE value for each task in the second set of upstream tasks, wherein a respective current TRUE value for a respective task in the second set of upstream tasks comprises a sum of a duration associated with the respective task and the TRUE value for the second end chain task; and

updating the held TRUE value in the data structure with the current TRUE value for each task in the second set of upstream tasks when the current TRUE value exceeds the held TRUE value.

13. The computer-implemented method of claim 12, comprising replacing the held TRUE value in the data structure with the current TRUE value based on a comparison of the current value for the second upstream task and the held TRUE value for the second upstream task to update the held TRUE value in the data structure with the current TRUE value for each task in the second set of upstream tasks when the current TRUE value exceeds the held TRUE value.

14. The computer-implemented method of claim 11, comprising:

selecting a next task for assignment from the job queue;

identifying an available task executor in a set of task executors; and

assigning the next task for assignment to the available task executor for performance.

15. The computer-implemented method of claim 11, the job queue including an indication of each upstream task of each task in the job flow.

16. The computer-implemented method of claim 15, comprising assigning a highest task in the job queue with all upstream tasks completed to a task executor when the task executor become available.

17. The computer-implemented method of claim 11, comprising performing a trial run for each task in the set of tasks to determine the duration for each task in the set of tasks.

18. The computer-implemented method of claim 11, comprising computing a makespan for the job flow, the makespan comprising a duration to perform the job flow with a defined number of executors based on the job queue.

19. The computer-implemented method of claim 18, comprising recomputing the makespan for the job flow based on a change in the defined number of executors.

20. The computer-implemented method of claim 11, comprising identifying a critical path for the job flow that begins with the task with the largest held TRUE value.

21. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a processor to perform operations comprising:

identify a job flow comprising a set of tasks for performance, each task in the job flow associated with a duration, and each task in the job flow is connected to at least one upstream task or at least one downstream task, wherein an upstream task for a respective task requires completion before performance of the respective task and a downstream task requires completion after performance of the respective task;

determine a list of upstream tasks in the job flow;

identify a set of end chain tasks comprising one or more tasks in the job flow and excluded from the list of upstream tasks, the set of end chain tasks including a first end chain task and a second end chain task;

generate a data structure to store a held time remaining until end (TRUE) value for each task in the job flow;

compute a current TRUE value for each end chain task, wherein a respective current TRUE value for a respective end chain task in the set of end chain tasks comprises a duration associated with the respective end chain task;

update the held TRUE value in the data structure with the current TRUE value for each end chain task when the current TRUE value exceeds the held TRUE value;

identify a first set of upstream tasks comprising a first upstream task and a second upstream task, the first set of upstream tasks comprising one or more upstream tasks connected to the first end chain task in the set of end chain tasks;

compute a current TRUE value for each task in the first set of upstream tasks, wherein a respective current TRUE value for a respective task in the first set of upstream tasks comprises a sum of a duration associated with the respective task and the held TRUE value for the first end chain task;

update the held TRUE value in the data structure with the current TRUE value for each task in the first set of upstream tasks when the current TRUE value exceeds the held TRUE value; and

generate a job queue based on the data structure to store the held TRUE value for each task in the job flow, the job queue comprising a list of tasks in the job flow ordered from a largest held TRUE value to a smallest held TRUE value.

22. The computer-program product of claim 21, including instructions operable to cause a processor to perform operations comprising:

identify a second set of upstream tasks including the second upstream task and a third upstream task, the second set of upstream tasks comprising one or more upstream tasks connected to the second end chain task in the set of end chain tasks;

compute a current TRUE value for each task in the second set of upstream tasks, wherein a respective current TRUE value for a respective task in the second set of upstream tasks comprises a sum of a duration associated with the respective task and the TRUE value for the second end chain task; and

update the held TRUE value in the data structure with the current TRUE value for each task in the second set of upstream tasks when the current TRUE value exceeds the held TRUE value.

23. The computer-program product of claim 22, including instructions operable to cause a processor to perform operations comprising replace the held TRUE value in the data structure with the current TRUE value based on a comparison of the current value for the second upstream task and the held TRUE value for the second upstream task to update the held TRUE value in the data structure with the current TRUE value for each task in the second set of upstream tasks when the current TRUE value exceeds the held TRUE value.

24. The computer-program product of claim 21, including instructions operable to cause a processor to perform operations comprising:

select a next task for assignment from the job queue;

identify an available task executor in a set of task executors; and

assign the next task for assignment to the available task executor for performance.

25. The computer-program product of claim 21, the job queue including an indication of each upstream task of each task in the job flow.

26. The computer-program product of claim 25, including instructions operable to cause a processor to perform operations comprising assign a highest task in the job queue with all upstream tasks completed to a task executor when the task executor become available.

27. The computer-program product of claim 21, including instructions operable to cause a processor to perform operations comprising perform a trial run for each task in the set of tasks to determine the duration for each task in the set of tasks.

28. The computer-program product of claim 21, including instructions operable to cause a processor to perform operations comprising compute a makespan for the job flow, the makespan comprising a duration to perform the job flow with a defined number of executors based on the job queue.

29. The computer-program product of claim 28, including instructions operable to cause a processor to perform operations comprising recompute the makespan for the job flow based on a change in the defined number of executors.

30. The computer-program product of claim 21, including instructions operable to cause a processor to perform operations comprising identify a critical path for the job flow that begins with the task with the largest held TRUE value.