System for computing the optimal static schedule using the stored task execution costs with recent schedule execution costs

• US 7,010,788 B1
• Filed: 05/19/2000
• Issued: 03/07/2006
• Est. Priority Date: 05/19/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Rehg, James M., Knobe, Kathleen
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Vo, Lilian
• Application Number:
  US09/574,866
• Time in Patent Office: 2,118 Days
• Field of Search: 718/100, 718/102, 718/103, 718/104, 718/108, 700/31, 700/101, 716/18, 716/1, 716/7, 716/2, 705/8, 712/23, 712/208, 712/215, 712/214
• US Class Current: 718/100
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06V 10/96 Management of image or video recognition tasks

Abstract

A static schedule is selected from a set of static schedules for an application dependent on the state of the application. A scheduling system stores a set of pre-defined static schedules for each state of the application. A scheduling system learns the costs of predefined schedules for each state of the application on-line as the application executes. Upon the detection of a state change in the application during run-time, the scheduling system selects a new static schedule for the application. The new static schedule is determined based on schedule costs and exploration criteria.

Claims

1. A computer implemented scheduling method comprising the steps of:

based on scheduling states, defining a set of static schedules for an application program, each static schedule including an assignment of tasks in the application program to processors, each scheduling state including dynamically changing application variables;

during run time, learning a cost of a set of static schedules based on performance of the application program;

maintaining a task execution cost for each task in the application program for each scheduling state; and

designating a static schedule with a lowest cost as an optimal schedule for a scheduling state, an optimal static schedule associated with a new scheduling state is computed using stored task execution costs, the cost of a schedule is updated using stored task execution costs with recent schedule execution costs having more importance.

2. A scheduling method as claimed in claim 1 wherein the cost of a set of static schedules is learned each time there is a change in scheduling state.

3. A scheduling method as claimed in claim 1 wherein the cost of a set of static schedules is learned continuously during run time.

4. A scheduling method as claimed in claim 1 further comprising:

storing a set of all possible schedules associated with each scheduling state; and

upon a change of state, selecting the optimal schedule associated with the scheduling state.

5. A scheduling method as claimed in claim 4 wherein a selected schedule is the schedule with a lowest cost.

6. A scheduling method as claimed in claim 4 wherein a selected schedule is the schedule with an unknown cost.

7. A scheduling method as claimed in claim 6 wherein the schedule is randomly selected dependent on utility of exploration associated with the schedule.

8. A scheduling method as claimed in claim 1 wherein the cost of a schedule is computed and stored after the schedule is executed.

9. A scheduling method as claimed in claim 1 wherein the cost of an individual task is updated using stored task execution costs with recent schedule execution costs having more importance.

10. A scheduling method as claimed in claim 1 further comprising:

predicting the cost of a schedule dependent on stored task execution costs.

11. A scheduling method as claimed in claim 10 wherein a schedule is selected for further exploration dependent on the predicted schedule cost.

12. A scheduling method as claimed in claim 1 wherein the step of learning further comprises:

storing application program input data received during an active period in the application program; and

exploring optimal schedules while replaying stored input data during an idle period in the application program.

13. A scheduling method as claimed in claim 12 wherein the step of learning further comprises:

concurrently executing a copy of an application program with identical input data on a processor other than another processor on which the application program is executing.

14. A scheduling method as claimed in claim 13 wherein a change in optimized schedules is immediately reflected to a schedule analyzer for use in a next schedule change of the application program.

15. The method of claim 1, wherein the performance of the application program is based on time to complete one iteration of the application program.

16. A scheduling system for scheduling application programs stored in a computer comprising:

a set of static schedules for an application program, the static schedules based on scheduling states, each static schedule including an assignment of tasks in the application program to processors, each scheduling state including dynamically changing application variables;

a task execution table which stores a task execution cost for each task in the application program for each scheduling state; and

a schedule analyzer which;

during run time, learns a cost of the set of static schedules based on performance of the application program;

computes an optimal static schedule associated with a new scheduling state using stored task execution costs;

updates the cost of a schedule using a sliding window by discounting older execution results at an expense of more recent execution results; and

designates a static schedule with a lowest cost as an optimal schedule for a scheduling state.

17. A scheduling system as claimed in claim 16 wherein the schedule analyzer learns the cost of a set of static schedules each time there is a change in scheduling state.

18. A scheduling system as claimed in claim 16 wherein the schedule analyzer learns the cost of a set of static schedules continuously during run time.

19. A scheduling system as claimed in claim 16 further comprising:

a list of schedule costs which stores an optimal schedule associated with each schedule state wherein upon a change of state the schedule analyzer selects the optimal schedule corresponding to the schedule state.

20. A scheduling system as claimed in claim 19 wherein the schedule analyzer selects a schedule with a lowest cost.

21. A scheduling system as claimed in claim 19 wherein the schedule analyzer selects a schedule with an unknown cost.

22. A scheduling system as claimed in claim 21 wherein the schedule analyzer randomly selects a schedule dependent on utility of exploration associated with the schedule.

23. A scheduling system as claimed in claim 16 wherein the schedule analyzer computes the cost of a schedule and stores a computed cost after the schedule is executed.

24. A scheduling system as claimed in claim 16 wherein the schedule analyzer updates the cost of an individual task using a sliding window by discounting older execution results at an expense of more recent execution results.

25. A scheduling system as claimed in claim 16 wherein the schedule analyzer predicts the cost of a schedule dependent on stored task execution costs.

26. A scheduling system as claimed in claim 25 wherein the scheduler analyzer selects a schedule for further exploration dependent on a predicted schedule cost.

27. A scheduling system as claimed in claim 16 further comprising:

memory which stores application program input data received during an active period in the application program, stored application program input data allowing the schedule analyzer to explore optimal schedules while replaying the application program input data during an idle period in the application program.

28. A scheduling system as claimed in claim 27 wherein the schedule analyzer provides a copy of an application program and the stored application program input data for concurrent execution on a processor other than another processor on which the application program is executing.

29. A scheduling system as claimed in claim 28 wherein a change in optimized schedules is immediately reflected to the schedule analyzer for use in a next schedule change of the application program.

30. A scheduling system for scheduling application programs stored in a computer comprising:

a set of static schedules for an application program, the static schedules based on scheduling states, each static schedule including an assignment of tasks to processors, each scheduling state including dynamically changing application variables;

a task execution table which stores a task execution cost for each task in the application program for each scheduling state;

means for learning which during run time, learns a cost of a set of static schedules based on performance of the application program; and

means for selecting which designates a static schedule with a lowest cost as an optimal schedule for a scheduling state, an optimal static schedule associated with a new scheduling state is computed using stored task execution costs, the cost of a schedule is updated using stored task execution costs with recent schedule execution costs having more importance.

31. A scheduling system as claimed in claim 30 wherein the means for learning learns the cost of a set of static schedules each time there is a change in scheduling state.

32. A scheduling system as claimed in claim 30 wherein the means for learning learns the cost of a set of static schedules continuously during run time.

33. A scheduling system as claimed in claim 30 further comprising:

a list of schedule costs which stores an optimal schedule associated with each schedule state wherein upon a change of state the means for analyzing selects the optimal schedule associated with the schedule state.

34. A scheduling system as claimed in claim 33 wherein the means for selecting selects a schedule with a lowest cost.

35. A scheduling system as claimed in claim 33 wherein the means for selecting selects a schedule with an unknown cost.

36. A scheduling system as claimed in claim 35 wherein the means for selecting randomly selects a schedule dependent on utility of exploration associated with the schedule.

37. A scheduling system as claimed in claim 30 wherein the means for selecting computes the cost of a schedule and stores a computed cost after the schedule is executed.

38. A scheduling system as claimed in claim 30 wherein the means for selecting updates the cost of an individual task using a sliding window by discounting older execution results at a expense of more recent execution results.

39. A scheduling system as claimed in claim 30 wherein the means for selecting updates the cost of a schedule using a sliding window by discounting older execution results at a expense of more recent execution results.

40. A scheduling system as claimed in claim 30 wherein the means for selecting predicts the cost of a schedule dependent on stored task execution costs.

41. A scheduling system as claimed in claim 40 wherein the means for selecting selects a schedule for further exploration dependent on a predicted cost for the schedule.

42. A scheduling system as claimed in claim 30 wherein the further comprising:

memory which stores application program input data received during an active period in the application program, the application program input data allowing the scheduling analyzer to explore optimal schedules while replaying the application program input data during an idle period in the application program.

43. A scheduling system as claimed in claim 42 wherein an on-line scheduling system provides a copy of an application program and the application program input data for concurrent execution on a processor other than another processor on which the application program is executing.

44. A scheduling system as claimed in claim 43 wherein a change in optimized schedules is immediately reflected to the means for analyzing for use in a next schedule change of the application program.

45. A computer system comprising:

a central processing unit connected to a memory system by a system bus;

an I/O system, connected to the system bus by a bus interface; and

a scheduling system routine located in the memory system which;

based on scheduling states, defines a set of static schedules for an application program, each static schedule including an assignment of tasks in the application program to processors, each scheduling state including dynamically changing application variables;

a task execution table which stores a task execution cost for each task in the application program for each scheduling state;

during run time, learns a cost of a set of static schedules based on performance of the application program; and

designates a static schedule with a lowest cost as an optimal schedule for a scheduling state, an optimal static schedule associated with a new scheduling state is computed using stored task execution costs, the cost of a schedule is updated using stored task execution costs with recent schedule execution costs having more importance.

46. A computer program product for system scheduling, the computer program product comprising a computer usable medium having computer readable program code thereon to be executed by a computer, including program code which:

based on scheduling states, defines a set of static schedules for an application program, each static schedule including an assignment of tasks in the application program to processors, each scheduling state including dynamically changing application variables;

a task execution table which stores a task execution cost for each task in the application program for each scheduling state;

during run time, learns a cost of a set of static schedules based on performance of the application program; and

designates a static schedule with a lowest cost as an optimal schedule for a scheduling state, an optimal static schedule associated with a new scheduling state is computed using stored task execution costs, the cost of a schedule is updated using stored task execution costs with recent schedule execution costs having more importance.