On-line scheduling of constrained dynamic applications for parallel targets

• US 7,073,175 B2
• Filed: 06/03/2005
• Issued: 07/04/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-Ai
• Assistant Examiner(s): To, Jennifer N.
• Application Number:
  US11/145,325
• Publication Number:
  US 20050223379A1
• Time in Patent Office: 396 Days
• Field of Search: 718100-108, 712/23, 712/208, 712/215, 712/28, 716/1, 716/2, 716/7, 716/18, 700/31, 700/101, 708/446, 703/6, 709/229, 711/119, 711/149, 717108-161
• US Class Current: 718/102
• 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 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.

2. The method of claim 1, further comprising:

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

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

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

4. The method of claim 1, further comprising:

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

5. The method of claim 4, wherein an optimal static schedule associated with a new scheduling state is computed using stored task execution costs.

6. The method of claim 5, wherein the cost of an individual task is updated using stored task execution costs with recent task execution costs having more importance.

7. The method of claim 5, wherein the cost of a schedule is updated using stored schedule execution costs with recent schedule execution costs having more importance.

8. The method of claim 1, wherein determining cost of the static schedules 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.

9. The method of claim 1, wherein the step of determining cost of the static schedules further comprises:

concurrently executing a copy of the application program with identical input data on a second processor, where the second processor is not executing the application program.

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.

11. The system of claim 10 further comprising:

a list of schedule costs which stores the 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.

12. The system of claim 10 further comprising:

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

13. The system of claim 12, wherein the schedule analyzer computes an optimal static schedule associated with a new scheduling state using stored task execution costs.

14. The system of claim 10 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.

15. The system of claim 10, wherein the schedule analyzer provides a copy of the application program and the stored application program input data for concurrent execution on a second processor, where the second processor is not executing the application program.

16. The system of claim 10, wherein a change in optimized schedules is immediately reflected to the schedule analyzer for use in a next schedule change of the application program.

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.

20. The computer system of claim 19 wherein the dynamic change in value of the at least one scheduling variable alters relative cost of tasks in the static schedules.