METHOD FOR ESTIMATING JOB RUN TIME

• US 20140115592A1
• Filed: 07/08/2011
• Published: 04/24/2014
• Est. Priority Date: 07/08/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Peter D.E. Vocht
• Inventors: Frean, Marcus, Kydd, David, Teeling, Chris, Jordan, Josiah, Tisch, Anna, Soukalopoulos, Peter, De Vocht, Peter, Hogan, Tim, Houston, Scott, Fellows, Dave, Lundy, Darryl, Adrian, John
• Granted Patent: US 9,058,216 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4818 Priority circuits therefor
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A process controller adapted to provide an estimated prediction of a processing time for a data processing job to be run on one or more of a plurality of data processing devices that operate within a distributed processing system having a range of platforms, the process controller being in communication with a job prediction engine adapted to calculate an estimated processing time associated with the data processing job, wherein the process controller uses the estimated processing time to determine the estimated prediction and is further adapted to control the assignment of the data processing job to the data processing devices upon acceptance of the estimated prediction by a user.

Claims

1. A computer implemented method for estimating a processing time for a data processing job to be run on a data processing device including the steps of:

a. creating an input array containing one or more parameters;

b. using a scoring algorithm to obtain a closest neighbouring array by comparing the input array to a plurality of known arrays;

c. for at least one parameter of the input array, using the closest neighbouring array and at least one other neighbouring array to determine a variation in estimated processing time; and

d. providing a processing time estimate that is a combination of the processing time of a closest neighbouring array and the variation in estimated processing time.

2. A method as claimed in claim 1 wherein each known array has an associated known processing time.

3. A method as claimed in claim 2 wherein each known array includes the associated known processing time as part of the array.

4. A method as claimed in claim 1 wherein the input array is a vector.

5. A method as claimed in claim 1 wherein the closest neighbouring array is a vector.

6. A method as claimed in claim 1 wherein the one or more other arrays are vectors.

7. A method as claimed in claim 1 wherein an associated known processing time is associated with each known array.

8. A method as claimed in claim 7 wherein the associated known processing time associated with each known array is stored as a parameter value within the known array.

9. A method as claimed in claim 1 wherein the known arrays are stored in a single array.

10. A method as claimed in claim 9 wherein the known arrays are stored as a matrix.

11. A method as claimed in claim 10 wherein the known arrays are represented by either the columns or the rows of the matrix.

12. A method as claimed in claim 9 wherein known arrays are added to the single array as processing times are determined.

13. A method as claimed in claim 2 wherein the associated known processing time of a known array is updated.

14. A method as claimed in claim 13 wherein the associated known processing time is updated by averaging the old associated known processing time with a new time.

15. A method as claimed in claim 1 wherein each parameter is one of:

binary, integer, calculated.

16. A method as claimed in claim 1 wherein the input array is created at least in part by a user.

17. A method as claimed in claim 16 wherein a user selects parameters to create the input array using a graphical user interface.

18. A method as claimed in claim 16 wherein a user selects parameters to create the input array using a command line.

19. A method as claimed in claim 16 wherein a user selects parameters to create the input array using a plugin and/or extension for a third party program.

20. A method as claimed in claim 1 wherein the input array is created at least in part by an application programming interface.

21. A method as claimed in claim 1 wherein the scoring algorithm produces a score for each known array.

22. A method as claimed in claim 1 wherein the scoring algorithm excludes at least one known array from being scored based on preset criteria.

23. A method as claimed in claim 21 wherein each score is based on comparison between each corresponding parameter in the input array and the known array.

24. A method as claimed in claim 23 wherein each parameter has an associated scaling factor such that the importance of the parameter to a final score is represented by the associated scaling factor.

25. A method as claimed in claim 21 wherein the score for each known array is proportional to the closeness between the known array and the input array.

26. A method as claimed in claim 21 wherein a higher score corresponds to a higher closeness between the input array and the known array.

27. A method as claimed in claim 26 wherein the highest scoring known array is selected as the closest neighbouring array.

28. A method as claimed in claim 26 wherein some of the known arrays are excluded from being selected as the closest neighbouring array, and the highest scoring non-excluded known array is selected as the closest neighbouring array.

29. A method as claimed in claim 28 wherein known arrays with binary parameters not identical to the corresponding parameters in the input array are excluded from being selected as the closest neighbouring array.

30. A method as claimed in claim 28 wherein only known arrays with a score within or greater than a predetermined range may be selected as the closest neighbouring vector.

31. A method as claimed in claim 1 wherein the at least one other neighbouring array is selected from the plurality of known arrays excluding the known array selected as the closest neighbouring array, and wherein at least one other neighbouring array is found for each parameter in the input array that is not identical to the associated parameter in the closest neighbouring array.

32. A method as claimed in claim 31 wherein one other neighbouring array is found for each parameter in the input array that is not identical to the associated parameter in the closest neighbouring array.

33. A method as claimed in claim 32 wherein the other neighbouring array is found by finding a known array with an associated parameter value closest to the associated parameter value of the closest neighbouring array.

34. A method as claimed in claim 33 wherein only known arrays with associated parameter values less than the associated parameter value of the closest neighbouring array are considered when determining the other neighbouring array.

35. A method as claimed in claim 32 wherein an associated known processing time of the closest neighbouring vector and an associated known processing time of the other neighbouring vector are used to calculate a variation in estimated processing time.

36. A method as claimed in claim 35 wherein the variation in estimated processing time is calculated at least in part by performing a linear fit between the two times.

37. A method as claimed in claim 31 wherein more than one other neighbouring array is found for each parameter in the input array that is not identical to the associated parameter in the closest neighbouring array, wherein each other neighbouring array includes an associated known processing time, and wherein a curve fitting algorithm is used to calculate the variation in estimated processing time.

38. A method as claimed in claim 1 wherein extrapolation is used to determine the variation in estimated processing time.

39. A method as claimed in claim 1 wherein interpolation is used to determine the variation in estimated processing time.

40. A method as claimed in claim 1 wherein the processing time estimate is the sum of the associated known processing time of the closest neighbouring array and the at least one variation in estimated processing time.

41. A method as claimed in claim 1 wherein the processing time estimate is presented to a user.

42. A method as claimed in claim 41 wherein the presentation is achieved using a graphical user interface.

43. A method as claimed in claim 1 wherein the processing time estimate includes a confidence measurement.

44. A method as claimed in claim 1 wherein the processing time is the product of the number of processors that the data processing job is being run on and the total time the job runs for.

45. A method as claimed in claim 1 wherein historical user data is used to adjust the processing time estimate.

46. A method as claimed in claim 1 wherein the processing time estimate includes an estimate of the time until the job will begin.

47. A method as claimed in claim 46 wherein the estimate of the time until the job will begin is at least in part based on the processing time estimates previously made for currently running and queued jobs.

48. A method as claimed in claim 1 wherein the processing time estimate includes a cost estimate at least in part based on the processing time estimate.

49. A method for causing a user to accept or decline a data processing job including the steps of:

a. estimating a processing time for the data processing job using a method as claimed in claim 1.

b. providing the processing time estimate to the user; and

c. prompting the user to accept or decline the data processing job based at least in part on the processing time estimate.

50. A method as claimed in claim 49 wherein the user is given the option to adjust one or more of the parameters in the input array if the user declines the data processing job.

51. A method as claimed in claim 49 wherein the user may be prompted to select a shorter processing time in exchange for an increase in cost.

52. A computer implemented method for estimating a processing time for a data processing job to be run on a data processing device including the steps of:

a. creating an input array containing one or more parameters;

b. using a scoring algorithm to obtain a plurality of neighbouring arrays;

c. for at least one parameter in the input array, using a plurality of the neighbouring arrays to determine an estimated processing time.

53-62. -62. (canceled)

63. A computer implemented method of training an optimised time estimation system for completing a data processing job to be run on at least one data processing device that operates within a distributed processing system having a range of platforms, the method including the steps of:

a. creating a prediction algorithm based upon retrieved operational parameters associated with a data processing job,

b. retrieving further operational parameters associated with the data processing job,

c. updating the prediction algorithm based on the further operational parameters, wherein the prediction algorithm is updated by modifying parameter values associated with variable parameters of the prediction algorithm, and

d. determining the cost of using current parameter values by calculating the sum of all errors made when processing previous data processing jobs.

64. The method of claim 63 further including the steps of determining a sum of errors based on the cost of using current weight values, and determining the variation in cost based on variations in the parameter values.

66. The method of claim 63 further including the steps of determining a gradient based on the rate of change of the cost and using local approximation to determine the change in cost based on the change in weight values.

65. (canceled)

67. A computer implemented method of determining an optimised time estimation for completing a data processing job to be run on at least one data processing device that operates within a distributed processing system having a range of platforms, the method including the steps of:

a. utilising a prediction algorithm to receive a predicted time estimation for completing a data processing job using at least one data processing device,

b. modifying the predicted time estimation based on one or more parameters associated with the processing devices within the distributed processing system, and based on determining the optimal parallelization of the data processing job.

68. The method of claim 67 wherein the parameters include one or more of the availability of processing devices within the distributed processing system, the start up time of processing devices within the distributed processing system, and historical run time data for the processing devices.

70. The method of claim 67 wherein the optimal parallelisation involves the splitting or clustering of the data processing job.

69. (canceled)

71-75. -75. (canceled)