Method for job impact learning

• US 6,618,742 B1
• Filed: 01/10/2000
• Issued: 09/09/2003
• Est. Priority Date: 01/10/2000
• Status: Expired due to Term

• Current Assignee: OpenPrint LLC (IPValuation Partners, LLC)
• Original Assignee: Imagex.Com Inc.
• Inventors: Krum, Brent
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): Tang, Kenneth
• Application Number:
  US09/480,816
• Time in Patent Office: 1,338 Days
• Field of Search: 714/47, 702/186, 705/400, 709/100-108
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

A method for processing requests to service computational tasks. An application server system receives requests to run various jobs. A job indicates that a certain application program is to be executed with a certain set of input. The application server system includes a master computer and multiple slave computers. The master computer receives requests to run jobs, selects a slave computer to run each job, and then assigns each job to slave computer selected for that job. The master computer of the application server system receives the requests from client computers that may be connected to the application server system via the Internet. A client-side component of the application server system may execute on the client computers to assist users in submitting their requests.

Claims

1. A method in a computer system for determining an estimated execution time for a job to run on a computing device, the method comprising:

determining a job size of the job;

determining a computing resource load for the computing device when the job is to run;

estimating the execution time for the job to run on the computing device, the estimating based on analysis of the actual execution time of another job, the analysis factoring in the determined job size, the job size of the other job, and a computing resource load of a computing device when the other job executed, wherein the execution time for the job is estimated by adjusting the actual execution time of the other job by a result of a projection factor applied to a difference between the computer resource load when the other job executed and the determined computing resource load.

2. The method of claim 1 including generating a mapping of execution times to various combinations of job sizes and computing resource loads.

3. The method of claim 2 wherein the mapping is based on actual execution times of previously executed jobs.

4. The method of claim 1 wherein the analysis factors in actual execution time of a job of the same job size running on a computing device with a computing resource load that is different from the determined computing resource load.

5. The method of claim 1 wherein the analysis factors in actual execution time of multiple jobs of approximately the same job size that run with various computing resource loads.

6. The method of claim 1 wherein the job size reflects anticipated computing resources to be used by the job when it is executed.

7. The method of claim 6 wherein the job size is based on size of input associated with the job.

8. The method of claim 6 wherein the job size is based on size of output associated with the job.

9. The method of claim 1 wherein a computing resource load reflects the amount of computer resources that would be used when a certain set of application programs are executed at the same time.

10. The method of claim 1 wherein a job identifies an application program to be executed and a set of input for execution of the application program.

11. The method of claim 10 wherein the application program has an application program load that reflects an estimate of computing resources used by the application program during execution.

12. The method of claim 11 wherein the analysis factors in the application program load of the application program.

13. The method of claim 1 wherein the job has an application program and wherein the analysis factors in actual execution times of jobs with the same application program.

14. The method of claim 1 wherein the job has an application program and including collecting the actual execution times of jobs that have the same application program.

15. The method of claim 14 wherein the actual execution times are associated with a computing resource load of the computing device during execution of the same application program.

16. The method of claim 14 wherein the actual execution times are associated with a job of a different job size with the same application program.

17. The method of claim 14 wherein the actual execution times are associated with a computing resource load of the computing device during execution of the same application program and with a job size of jobs having the same application program.

18. A computer-readable medium containing a data structure for use in estimating an execution time of a job, the data structure comprising a plurality of execution times, the execution times being derived from actual execution times of jobs having various job sizes and on computing devices with various computing resource loads, the execution times being grouped according to job size and according to computing resource load, wherein the execution times for a job size grouping at various computing resource loads are calculated by adjusting the actual execution time of a job by a result of a projection factor applied to a difference between the computer resource load when the job executed and the computing resource load for which the execution time is to be calculated.

19. The computer-readable medium of claim 18 wherein the execution times of the data structure for a given job size at various computing resource loads are projected based on an actual execution time for a job of that given job size on a computing device with a known computing resource load.

20. The computer-readable medium of claim 19 wherein the projecting is based on a projection factor.

21. The computer-readable medium of claim 20 wherein the projection factor is the same for all job sizes.

22. The computer-readable medium of claim 20 wherein each job size has it own projection factor.

23. The computer-readable medium of claim 20 wherein the projection factor is empirically derived by running sample jobs of each job size group on a computing device with different computing resource loads.

24. The computer-readable medium of claim 18 wherein an execution time of the data structure for a job size an d a computing resource load is based on a previous execution time of the data structure for that job size and that computing resource load.

25. The computer-readable medium of claim 18 wherein the execution times of the data structure for a given computing resource load are projected based on an actual execution time for a job on a computing device with the given computing resource load and a known job size.

26. The computer-readable medium of claim 18 wherein the execution times for job size at various computing resource loads are calculated according to

27. A method in a computer system for calculating an estimated execution time of an application program on a computing device, the method comprising:

collecting actual execution times of the application program with various input sizes executing on a computing device with various computing resource loads;

providing the input size of the application program;

providing an estimated computing resource load of the computing device when the application program is to be executed;

estimating the execution time for the application program with the provided input size when the application program is executed on a computing device with the provided computing resource load based on a collected actual execution time for the application program with a known input size executing on a computing device with a known computing resource load, wherein the execution time for the application program is estimated by adjusting the actual execution time of the application program with a known input size by a result of a projection factor applied to a difference between the known computer resource load and the estimated computing resource load.

28. The method of claim 27 wherein the estimating is based on a collected actual execution time for execution of the application program with the same input size as the provided input size.

29. The method of claim 27 wherein the estimating is based on a collected actual execution time for execution of the application program on a computing device with the same computing resource load as the provided computing resource load.

30. The method of claim 27 wherein the estimating estimates the execution times for the application program with various input sizes and at various computing resource loads according to

31. The method of claim 27 wherein the computing resource load reflects the amount of computer resources used when a certain set of application programs are executed at the same time.

32. The method of claim 27 wherein the application program has an application program load that reflects an estimate of computing resources used by the application program during execution.

33. The method of claim 32 wherein the estimating factors in the application program load of the application program.

34. The method of claim 27 wherein the collected execution times are used to generate a data structure comprising a plurality of execution times, the execution times being derived from actual execution times of the application program with various input sizes and on computing devices with various computing resource loads, the execution times being grouped according to input size and according to computing resource load.

35. The method of claim 34 wherein executions times of the data structure for a given input size at various computing resource loads are projected based on an actual execution time for the application program of that given input size on a computing device with a known computing resource load.

36. The method of claim 34 wherein an execution time of the data structure for an input size and a computing resource load is based on a previous execution time of the data structure for that input size and that computing resource load.

37. The method of claim 34 wherein execution times of the data structure for a given computing resource load for various input sizes are projected based on an actual execution time for the application program on a computing device with the given computing resource load and a known input size.

38. A method for calculating an estimated execution time of a job on a computing device, the job having an application program and input, the method comprising:

step for providing a job size of the job;

step for providing a computing resource load of the computing device when the job is to be executed;

step for estimating the execution time for the job when the job is executed on a computing device with the provided computing resource load based on an actual execution time of a job with the same application program with a known job size executing on a computing device with a known computing resource load, wherein the execution time for the job is estimated, by adjusting the actual execution time of the job with the same application program with a known job size by a result of a projection factor applied to a difference between the known computer resource load and the provided computing resource load.

39. The method of claim 38 wherein the step for estimating estimates based on an actual execution time of the application program with the same job size as the provided job size.

40. The method of claim 38 wherein the step for estimating estimates based on an actual execution time of the application program on a computing device with the same computing resource load as the provided computing resource load.

41. The method of claim 38 wherein the computing resource load reflects the amount of computing resources that would be used when a certain set of application programs are executed at the same time.

42. The method of claim 38 wherein the application program has an application program load that reflects an estimate of computing resources used by the application program during execution.

43. The method of claim 42 wherein the step for estimating factors in the application program load of the application program.