On-line scheduling of constrained dynamic applications for parallel targets
First Claim
Patent Images
1. A computer implemented on-line scheduling method for scheduling application program tasks, comprising:
- defining static schedules for an application program which is expressible by a task graph, each static schedule including an assignment of tasks in the application program to processors, tasks and task dependencies being determined from the task graph, the task graph being fixed but optimal schedule depending on values of scheduling variables;
determining cost of the static schedules based on performance of the application program during run time;
detecting, at run time, dynamic change in value of at least one scheduling variable in the application program or an environment of the application program, the dejected dynamic change in value of the at least one scheduling variable altering costs of the static schedules; and
designating a static schedule with a lowest cost as an optimal schedule for a scheduling state defined by value of the at least one scheduling variable.
0 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.
101 Citations
20 Claims
-
1. A computer implemented on-line scheduling method for scheduling application program tasks, comprising:
-
defining static schedules for an application program which is expressible by a task graph, each static schedule including an assignment of tasks in the application program to processors, tasks and task dependencies being determined from the task graph, the task graph being fixed but optimal schedule depending on values of scheduling variables; determining cost of the static schedules based on performance of the application program during run time; detecting, at run time, dynamic change in value of at least one scheduling variable in the application program or an environment of the application program, the dejected dynamic change in value of the at least one scheduling variable altering costs of the static schedules; and designating a static schedule with a lowest cost as an optimal schedule for a scheduling state defined by value of the at least one scheduling variable. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. An on-line scheduling system for scheduling application programs stored in a computer comprising:
-
static schedules for an application program which is expressible by a task graph, each static schedule including an assignment of tasks from the application program to processors, tasks and task dependencies being determined from the task graph, the task graph being fixed but optimal schedule depending on values of scheduling variables; and a schedule analyzer which; determines cost of the static schedules based on performance of the application program during run time; detects, at run time, dynamic change in value of at least one scheduling variable in the application program or an environment of the application program, the detected dynamic change in value of the at least one scheduling variable altering costs of the static schedules; and designates a static schedule with a lowest cost as an optimal schedule for a scheduling state defined by value of the at least one scheduling variable. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. An on-line scheduling system for scheduling application programs stored in a computer comprising:
-
static schedules for an application program which is expressible by a task graph, each static schedule including an assignment of tasks to processors, tasks and task dependencies being determined from the task graph, the task graph being fixed but optimal schedule depending on values of scheduling variables; means for determining cost of the static schedules based on performance of the application program during run time; means for detecting, at run time, dynamic change in value of at least one scheduling variable in the application program or an environment of the application program, the detected dynamic change in value of the at least one scheduling variable altering costs of the static schedules; and means for designating a static schedule with a lowest cost as an optimal schedule for a scheduling state defined by value of the at least one scheduling variable.
-
-
18. A computer program product for system on-line scheduling, the computer program product comprising a computer storage medium having computer readable program code thereon to be executed by a computer, including program code which:
-
defines static schedules for an application program which is expressible by a task graph, each static schedule including an assignment of tasks in the application program to processors, tasks and task dependencies being determined from the task graph, the task graph being fixed but optimal schedule depending on values of scheduling variables; determines cost of the static schedules based on performance of the application program during run time; detects, at run time, dynamic change in value of at least one scheduling variable in the application program or an environment of the application program, the detected dynamic change in value of the at least one scheduling variable altering costs of the static schedules; and designates a static schedule with a lowest cost as an optimal schedule for a scheduling state defined by value of the at least one scheduling variable.
-
-
19. 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 includes; static schedules for an application program which is expressible by a task graph, each static schedule including an assignment of tasks from the application program to processors, tasks and task dependencies being determined from the task graph, the task graph being fixed but optimal schedule depending on values of scheduling variables; and
.a schedule analyzer which; determines cost of the static schedules based on performance of the application program during run time; detects, at run time, dynamic change in value of at least one scheduling variable in the application program or an environment of the application program, the detected dynamic change in value of the at least one scheduling variable altering costs of the static schedules; and designates a static schedule with a lowest cost as an optimal schedule for a scheduling state defined by value of the at least one scheduling variable. - View Dependent Claims (20)
-
Specification