System for computing the optimal static schedule using the stored task execution costs with recent schedule execution costs
First Claim
Patent Images
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
46 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
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. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
-
-
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.
-
Specification