System and method for distributed resource requirement and allocation

1. A computer-implemented method comprising:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster;

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups; and

determining, based on the resource requirement for each of the one or more groups, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein obtaining the duration information comprises obtaining input data from one or more historical runs of the distributed compute phase and extracting the duration information from the input data; and

wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein extracting the duration information comprises applying a streaming data technique to obtain tiered duration information.

2. The computer-implemented method of claim 1 , wherein the input data is stationary over time and an amount of the input data is below a predetermined threshold and further wherein the duration information is extracted for all of the one or more tasks.

3. The computer-implemented method of claim 1 , wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein the duration information is extracted for a random selection of durations associated with the one or more tasks.

4. The computer-implemented method of claim 1 , wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein the duration information is extracted for a predetermined number of durations associated with the one or more tasks.

5. The computer-implemented method of claim 1 , wherein the input data exhibits at least one time-varying pattern and further wherein extracting the duration information comprises:

obtaining, from the input data, historical percentile duration information for each of the one or more historical runs of the distributed compute phase; and

forecasting, based on the historical percentile duration information, predicted percentile duration information for at least one future run of each phase.

6. The computer-implemented method of claim 1 , wherein the one or more tasks are to be performed in one or more compute slots and further wherein sorting the one or more tasks into the one or more groups comprises determining a partition of the one or more groups that meets a desired number for the one or more groups and minimizes a total area of the one or more compute slots.

7. The computer-implemented method of claim 6 , wherein determining the partition of the one or more groups comprises applying a dynamic programming technique to minimize a cost function representative of the total area.

8. The computer-implemented method of claim 6 , wherein sorting the one or more tasks into the one or more groups comprises:

(a) computing a first total area of the one or more compute slots with the one or more tasks sorted into a first number of the one or more groups;

(b) incrementing the first number by a predetermined step, thereby obtaining a second number for the one or more groups;

(c) computing a second total area of the one or more compute slots with the one or more tasks sorted into the second number of the one or more groups;

(d) computing a difference between the first total area and the second total area and comparing the difference to a predetermined threshold;

(e) responsive to determining that the difference is within the predetermined threshold, setting the first number as the desired number; and

(f) responsive to determining that the difference is beyond the predetermined threshold, incrementing the second number by the predetermined step, thereby obtaining a third number for the one or more groups, setting the second number as the first number, setting the third number as the second number, and repeating steps (a) to (f).

9. The computer-implemented method of claim 1 , wherein determining the resource requirement comprises determining, for each of the one or more groups, a number of the one or more tasks, an average task duration, and a maximum task duration.

10. The computer-implemented method of claim 1 , wherein determining the time-varying allocation of the resources for the distributed compute phase comprises, for each of the one or more groups:

determining an upper bound on a time until completion of a given one of the one or more tasks that is last to finish; and

creating, based on the upper bound, a two-dimensional shape representative of an allocation of resources for the distributed compute phase, the two-dimensional shape having a width equal to a value of the upper bound.

11. The computer-implemented method of claim 1 , further comprising receiving the distributed compute job from a job submitter.

12. The computer-implemented method of claim 1 , further comprising outputting the time-varying allocation of the resources to a resource planner for planning execution of the distributed compute job in the distributed compute cluster.

13. A computing device comprising:

at least one processing unit; and

a non-transitory memory communicatively coupled to the at least one processing unit and storing computer-readable program instructions executable by the at least one processing unit for:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster,

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups, and

determining, based on the resource requirement for each of the one or more groups, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein the computer-readable program instructions are executable by the at least one processing unit for obtaining input data from one or more historical runs of the distributed compute phase and extracting the duration information from the input data; and

wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein the computer-readable program instructions are executable by the at least one processing unit for applying a streaming data technique to obtain tiered duration information.

14. The computing device of claim 13 , wherein the input data is stationary over time and an amount of the input data is below a predetermined threshold and further wherein the computer-readable program instructions are executable by the at least one processing unit for extracting the duration information for all of the one or more tasks.

15. The computing device of claim 13 , wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein the computer-readable program instructions are executable by the at least one processing unit for extracting the duration information for a random selection of durations associated with the one or more tasks.

16. The computing device of claim 13 , wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein the computer-readable program instructions are executable by the at least one processing unit for extracting the duration information for a predetermined number of durations associated with the one or more tasks.

17. The computing device of claim 13 , wherein the input data exhibits at least one time-varying pattern and further wherein the computer-readable program instructions are executable by the at least one processing unit for extracting the duration information comprising:

obtaining, from the input data, historical percentile duration information for each of the one or more historical runs of the distributed compute phase; and

forecasting, based on the historical percentile duration information, predicted percentile duration information for at least one future run of each phase.

18. The computing device of claim 13 , wherein the one or more tasks are to be performed in one or more compute slots and further wherein sorting the one or more tasks into the one or more groups comprises determining a partition of the one or more groups that meets a desired number for the one or more groups and minimizes a total area of the one or more compute slots.

19. The computing device of claim 18 , wherein the computer-readable program instructions are executable by the at least one processing unit for applying a dynamic programming technique to minimize a cost function representative of the total area.

20. The computing device of claim 18 , wherein sorting the one or more tasks into the one or more groups comprises:

(a) computing a first total area of the one or more compute slots with the one or more tasks sorted into a first number of the one or more groups;

(b) incrementing the first number by a predetermined step, thereby obtaining a second number for the one or more groups;

(c) computing a second total area of the one or more compute slots with the one or more tasks sorted into the second number of the one or more groups;

(d) computing a difference between the first total area and the second total area and comparing the difference to a predetermined threshold;

(e) responsive to determining that the difference is within the predetermined threshold, setting the first number as the desired number; and

(f) responsive to determining that the difference is beyond the predetermined threshold, incrementing the second number by the predetermined step, thereby obtaining a third number for the one or more groups, setting the second number as the first number, setting the third number as the second number, and repeating steps (a) to (f).

21. The computing device of claim 13 , wherein the computer-readable program instructions are executable by the at least one processing unit for defining the resource requirement comprising specifying, for each of the one or more groups, a number of the one or more tasks, an average task duration, and a maximum task duration.

22. The computing device of claim 13 , wherein determining the time-varying allocation of the resources for the distributed compute phase comprises, for each of the one or more groups:

determining an upper bound on a time until completion of a given one of the one or more tasks that is last to finish; and

creating, based on the upper bound, a two-dimensional shape representative of an allocation of resources for the distributed compute phase, the two-dimensional shape having a width equal to a value of the upper bound.

23. The computing device of claim 13 , wherein the computer-readable program instructions are executable by the at least one processing unit for receiving the distributed compute job from a job submitter.

24. The computing device of claim 13 , wherein the computer-readable program instructions are executable by the at least one processing unit for outputting the time-varying allocation of the resources to a resource planner for planning execution of the distributed compute job in the distributed compute cluster.

25. A non-transitory computer readable medium having stored thereon program code, the program code executable by a processor for:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster;

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups; and

determining, based on the resource requirement, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein obtaining the duration information comprises obtaining input data from one or more historical runs of the distributed compute phase and extracting the duration information from the input data; and

wherein the input data is stationary over time and an amount of the input data is above a predetermined threshold and further wherein extracting the duration information comprises applying a streaming data technique to obtain tiered duration information.

26. A computer-implemented method comprising:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster;

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups; and

determining, based on the resource requirement for each of the one or more groups, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein the one or more tasks are to be performed in one or more compute slots and further wherein sorting the one or more tasks into the one or more groups comprises determining a partition of the one or more groups that meets a desired number for the one or more groups and minimizes a total area of the one or more compute slots; and

wherein sorting the one or more tasks into the one or more groups comprises:

(a) computing a first total area of the one or more compute slots with the one or more tasks sorted into a first number of the one or more groups;

(b) incrementing the first number by a predetermined step, thereby obtaining a second number for the one or more groups;

(c) computing a second total area of the one or more compute slots with the one or more tasks sorted into the second number of the one or more groups;

(d) computing a difference between the first total area and the second total area and comparing the difference to a predetermined threshold;

(e) responsive to determining that the difference is within the predetermined threshold, setting the first number as the desired number; and

(f) responsive to determining that the difference is beyond the predetermined threshold, incrementing the second number by the predetermined step, thereby obtaining a third number for the one or more groups, setting the second number as the first number, setting the third number as the second number, and repeating steps (a) to (f).

27. The computer-implemented method of claim 26 , wherein determining the partition of the one or more groups comprises applying a dynamic programming technique to minimize a cost function representative of the total area.

28. A computer-implemented method comprising:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster;

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups; and

determining, based on the resource requirement for each of the one or more groups, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein determining the time-varying allocation of the resources for the distributed compute phase comprises, for each of the one or more groups:

determining an upper bound on a time until completion of a given one of the one or more tasks that is last to finish; and

creating, based on the upper bound, a two-dimensional shape representative of an allocation of resources for the distributed compute phase, the two-dimensional shape having a width equal to a value of the upper bound.

29. The computer-implemented method of claim 28 , wherein obtaining the duration information comprises obtaining input data from one or more historical runs of the distributed compute phase and extracting the duration information from the input data.

30. A computing device comprising:

at least one processing unit; and

a non-transitory memory communicatively coupled to the at least one processing unit and storing computer-readable program instructions executable by the at least one processing unit for:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster,

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups, and

determining, based on the resource requirement for each of the one or more groups, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein the one or more tasks are to be performed in one or more compute slots and further wherein sorting the one or more tasks into the one or more groups comprises determining a partition of the one or more groups that meets a desired number for the one or more groups and minimizes a total area of the one or more compute slots; and

wherein sorting the one or more tasks into the one or more groups comprises:

(a) computing a first total area of the one or more compute slots with the one or more tasks sorted into a first number of the one or more groups;

(b) incrementing the first number by a predetermined step, thereby obtaining a second number for the one or more groups;

(c) computing a second total area of the one or more compute slots with the one or more tasks sorted into the second number of the one or more groups;

(d) computing a difference between the first total area and the second total area and comparing the difference to a predetermined threshold;

(e) responsive to determining that the difference is within the predetermined threshold, setting the first number as the desired number; and

(f) responsive to determining that the difference is beyond the predetermined threshold, incrementing the second number by the predetermined step, thereby obtaining a third number for the one or more groups, setting the second number as the first number, setting the third number as the second number, and repeating steps (a) to (f).

31. The computing device of claim 30 , wherein determining the partition of the one or more groups comprises applying a dynamic programming technique to minimize a cost function representative of the total area.

32. A computing device comprising:

at least one processing unit; and

a non-transitory memory communicatively coupled to the at least one processing unit and storing computer-readable program instructions executable by the at least one processing unit for:

obtaining duration information indicative of an amount of time taken by each of one or more tasks of a distributed compute phase of a distributed compute job to be executed in a distributed compute cluster,

sorting the one or more tasks into one or more groups based on the duration information, and determining a resource requirement for each of the one or more groups, and

determining, based on the resource requirement for each of the one or more groups, a time-varying allocation of resources of the distributed compute cluster for the distributed compute phase; and

wherein determining the time-varying allocation of the resources for the distributed compute phase comprises, for each of the one or more groups:

determining an upper bound on a time until completion of a given one of the one or more tasks that is last to finish; and

creating, based on the upper bound, a two-dimensional shape representative of an allocation of resources for the distributed compute phase, the two-dimensional shape having a width equal to a value of the upper bound.

33. The computing device of claim 32 , wherein obtaining the duration information comprises obtaining input data from one or more historical runs of the distributed compute phase and extracting the duration information from the input data.