On-line scheduling of constrained dynamic applications for parallel targets
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/46
G06F-007/38
G06F-015/16
G06F-015/00
G06F-012/00
G06G-007/48
G06G-007/00
G06F-009/44
G06F-009/45
출원번호
US-0145325
(2005-06-03)
발명자
/ 주소
Rehg,James M.
Knobe,Kathleen
출원인 / 주소
Hewlett Packard Development Company, Inc.
인용정보
피인용 횟수 :
19인용 특허 :
51
초록▼
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 o
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.
대표청구항▼
What is claimed is: 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 t
What is claimed is: 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.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (51)
Garofalakis Minos N. ; Ioannidis Yannis E.,GRX ; Ozden Banu ; Silberschatz Abraham, Admission control system and method for media-on-demand servers.
Esslinger Mark A. ; Clarke Allan D. ; Howard Robert M. ; Matchett Douglas K. ; Neuse Douglas M. ; Palmer James R. ; West Carolyn W., Apparatus for and method of displaying running of modeled system designs.
Bolosky William J. ; Need Dwayne R. ; Debgupta Siddhartha, Continuous media file server for cold restriping following capacity change by repositioning data blocks in the multiple.
Getzinger Thomas W. (La Habra CA) Habereder Hans L. (Anaheim CA) Harrison R. Loyd (Fullerton CA) Hopp Donald M. (Fullerton CA) Mitchell David L. (Fullerton CA) Pian Chao-Kuang (Anaheim CA) Propster J, Data flow signal processor method and apparatus.
George David A. (Somers NY) Rathi Bharat D. (Mahopac NY), Data processing system incorporating a memory resident directive for synchronizing multiple tasks among plurality of pro.
Bean George H. (Kingston NY) Borden Terry L. (Poughkeepsie NY) Farrell Mark S. (Pleasant Valley NY) Gum Peter H. (Poughkeepsie NY) Hough Roger E. (Highland NY) Johnson Francis E. (Poughkeepsie NY) Mc, Logical resource partitioning of a data processing system.
Jevtic Dusan, Method and apparatus for automatically generating schedules for wafer processing within a multichamber semiconductor wafer processing tool.
Kubala Jeffrey P. ; Nick Jeffrey M., Method and apparatus for optimizing the handling of synchronous requests to a coupling facility in a sysplex configurati.
Azarbayejani Ali (Cambridge MA) Galyean Tinsley (Cambridge MA) Pentland Alex (Cambridge MA), Method and apparatus for three-dimensional, textured models from plural video images.
Maes Pattie E. (Somerville MA) Blumberg Bruce M. (Pepperell MA) Darrell Trevor J. (Cambridge MA) Starner Thad E. (Somerville MA) Johnson Michael P. (Cambridge MA) Russell Kenneth B. (Boston MA) Pentl, Method and system for facilitating wireless, full-body, real-time user interaction with a digitally represented visual e.
Austin Edward B. (Woodbridge VA) Robertson Jeffrey E. (Manassas VA), Method for compiling a master task definition data set for defining the logical data flow of a distributed processing ne.
Sven Wuytack BE; Francky Catthoor BE; Hugo De Man BE, Method for determining a storage bandwidth optimized memory organization of an essentially digital device.
Agrawal Prathima (New Providence NJ) Telichevesky Ricardo (Cambridge MA) Trotter John A. (Somerville NJ), Method of operating a multiprocessor computer to solve a set of simultaneous equations.
Furtney Mark (Both of Apple Valley MN) Barriuso Frank R. (Both of Apple Valley MN) Andreasen Clayton D. (Rosemont MN) Hoel Timothy W. (Eagan MN) LaCroix Suzanne L. (Shorewood MN) Reinhardt Steven P. , Methods for efficient distribution of parallel tasks to slave processes in a multiprocessing system.
Vegesna Anantakotiraju ; Avula Jayachandra B. ; Jewett Peter H. ; Mundkur Yatin G. ; Naik Vinay J. ; Monaco James E., Processor which performs dynamic instruction scheduling at time of execution within a single clock cycle.
Falcon ; Jr. Lorenzo ; Saxena Ashok Raj, Video data streamer for simultaneously conveying same one or different ones of data blocks stored in storage node to ea.
Motoyama, Tetsuro; Fong, Avery, Class object wrappers for document object model (DOM) elements for project task management system for managing project schedules over a network.
Kumar, Mukul; Roy, Subhojit, Method and apparatus for providing intelligent interpretation of calendaring information to schedule computer data operations.
Lee, Juhnyoung; Mohan, Rakesh; Rosinski, Thomas D.; Sigl, Gerhard, Method and system for estimating financial benefits of packaged application service projects.
Lee, Juhnyoung; Mohan, Rakesh; Rosinski, Thomas D.; Sigl, Gerhard, Method and system for estimating financial benefits of packaged application service projects.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.