Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2006-07-04
2006-07-04
An, Meng-Ai (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C708S446000, C709S229000, C703S006000, C712S028000, C711S119000, C711S149000
Reexamination Certificate
active
07073175
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.
REFERENCES:
patent: 3614745 (1971-10-01), Podvin et al.
patent: 4607325 (1986-08-01), Horn
patent: 4843541 (1989-06-01), Bean et al.
patent: 4885684 (1989-12-01), Austin et al.
patent: 4965718 (1990-10-01), George et al.
patent: 4972314 (1990-11-01), Getzinger et al.
patent: 5099322 (1992-03-01), Gove
patent: 5164992 (1992-11-01), Turk et al.
patent: 5205993 (1993-04-01), Leib et al.
patent: 5247677 (1993-09-01), Welland et al.
patent: 5257372 (1993-10-01), Furtney et al.
patent: 5291599 (1994-03-01), Cohen et al.
patent: 5367687 (1994-11-01), Tarsy et al.
patent: 5392429 (1995-02-01), Agrawal et al.
patent: 5511153 (1996-04-01), Azarbayejani et al.
patent: 5563988 (1996-10-01), Maes et al.
patent: 5573013 (1996-11-01), Conlan
patent: 5606698 (1997-02-01), Powell
patent: 5619502 (1997-04-01), Kahn et al.
patent: 5664164 (1997-09-01), Riddle
patent: 5691902 (1997-11-01), Taniguchi et al.
patent: 5712976 (1998-01-01), Falcon, Jr. et al.
patent: 5713039 (1998-01-01), Tran
patent: 5742821 (1998-04-01), Prasanna
patent: 5757648 (1998-05-01), Nakamura
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5781787 (1998-07-01), Shafer et al.
patent: 5802580 (1998-09-01), McAlpine
patent: 5809161 (1998-09-01), Auty et al.
patent: 5809321 (1998-09-01), Hansen et al.
patent: 5819021 (1998-10-01), Stanfill et al.
patent: 5826080 (1998-10-01), Dworzecki
patent: 5826095 (1998-10-01), Jordan
patent: 5852449 (1998-12-01), Esslinger et al.
patent: 5860095 (1999-01-01), Iacobovici et al.
patent: 5884060 (1999-03-01), Vegesna et al.
patent: 5886995 (1999-03-01), Arsenault et al.
patent: 5887143 (1999-03-01), Saito et al.
patent: 5923890 (1999-07-01), Kubala et al.
patent: 5937084 (1999-08-01), Crabtree et al.
patent: 5953524 (1999-09-01), Meng et al.
patent: 5991804 (1999-11-01), Bolosky et al.
patent: 6088678 (2000-07-01), Shannon
patent: 6178542 (2001-01-01), Dave
patent: 6201999 (2001-03-01), Jevtic
patent: 6230303 (2001-05-01), Dave
patent: 6289488 (2001-09-01), Dave et al.
patent: 6330609 (2001-12-01), Garofalakis et al.
patent: 6421809 (2002-07-01), Wuytack et al.
patent: 6519498 (2003-02-01), Jevtic et al.
patent: 6779183 (2004-08-01), Chekuri et al.
patent: 6889178 (2005-05-01), Chacon
patent: 2001/0032109 (2001-10-01), Gonyea et al.
patent: 2001/0042189 (2001-11-01), Babaian et al.
patent: 2002/0056035 (2002-05-01), Rozenshein et al.
Carter et al., “Generational Scheduling for Dynamic Task Management in Herterogeneous Computing System”, 1998, Elsevier Science Inc., pp. 219-236.
Prasanna et al., “Generalized Multiprocessor Scheduling for Directed Acylic Graphs”, 1994, IEEE, pp. 237-246.
Prasanna et al., “Generalised Multiprocessor Scheduling Using Optimal Control”, 1991, AMC, pp. 216-228.
Atkeson, C.G., et al., “Locally Weighted Learning,”Artificial Intelligence Review, 11:11-73, 1997.
Atkeson, C.G., et al., “Locally Weighted Learning for Control,”Artificial Intelligence Review, 11:75-1133, 1997.
Bal, H.E. and Haines, M., “Approaches for Integrating Task and Data Parallelism,”IEEE Concurrency, 1998. To appear.
Boyan, J.A. and Littman, M.L., “Packet Routing in Dynamically Changing Networks: A Reinforcement Learning Approach,” In J.D. Cowan, G. Tesauro, and J. Alspector, editors,Advances in Neural Information Processing Systems 6(NIPS). Morgan Kaufman, 1994.
Chakrabarti, S., et al., “Models and Scheduling Algorithms for Mixed Data and Task Parallel Programs,”J. of Parallel and Distributed Computing, 47:168-184, 1997.
Darrell, T., et al., “Active Face Tracking and Pose Estimation in an Interactive Room,” 1063-6919/96, 1996 IEEE, (pp. 67-72).
Fujimoto, R.M., “The Virtual Time Machine,” Univ. of Utah, Symp. on Parallel Algorithms and Architecture, 1989.
Ghosh, K., et al., “Parallel Discrete Event Simulation Using Space-Time Memory,”International Conference on Parallel Processing, 1991.
Jefferson, D.R., “Virtual Time,” Univ. of So. Calif.,ACM Transactions on Programming Languages and Systems, vol. 7, No. 3, Jul. 1985, pp. 404-425.
Jordan, M.I. and Rumelhart, D.E., “Forward Models: Supervised Learning with a Distal Teacher,”Cognitive Science, 16:307-354, 1992.
Schaal, S. and Atkeson, C.G., “Assessing the Quality of Local Linear Models,” In J.D. Cowan, G. Tesauro, and J. Alspector, editors,Advances in Neural Information Processing Systems 6(NIPS), pp. 160-167. Morgan Kaufman, 1994.
Singla, A., et al., “Temporal Notions of Synchronization and Consistency in Beehive,” Georgia Inst. of Tech.,SPAA'97, Newport, R.I. . . .
Subholk, J., et al., “Communication and Memory Requirements as the Basis for Mapping Task and Data Parallel Programs,”Proc. Supercomputing '94, Nov. 1994.f.
Takeuchi, A., et al., “Situated Facial Displays: Towards Social Interaction,”CHI Mosaic of Creativity, Denver, CO, pp. 450-455, May 1995.
Verghese, B., et al., “Operating System Support for Improving Data Locality on CC-NUMA Compute Servers,” InProc. Seventh Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 279-289, Oct. 1986.
Wren, C.R., et al., “Pfinder: Real-Time Tracking of the Human Body,”IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7) : pp. 780-785 (Jul. 1997).
Wren, C.R., et al., “Pfinder: Real-Time Tracking of the Human Body,”SPIE1995, vol. 2615, pp. 89-98.
Puschner, et al., “Calculating the Maximum Execution Time of Real-Time Programs,” Digital Equipment Corporation, Apr. 7, 1989.
Jeffay, et al., “On Non-Preemptive Scheduling of Period and Sporadic Tasks,” Proceedings, Twelfth, vol., Iss. 4-6, Dec. 1991.
Lee, et al., “Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing,” vol. C-36, No. J, Jan. 1987, IEE.
Kwok, et al., “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessor,” vol. 7, Iss. 5, May 1996,IEEE.
Parhi, et al., “Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding,” vol. 40, Iss. 2, Feb. 1991,IEEE.
Lehoczky, et al., “An Optimal for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems,” Real-Time Systems Symposium, vol. Iss. 2-4, Dec. 1992.
Kasahara, et al., “Parallel Processing of Near Fine Grain Tasks Using Static Scheduling on OSCAR,” Supercomputing '90, Proceedings of, vol., Iss. 12-16, Nov. 1990.
Hong, et al., “On-Line Scheduling of Real-Time Tasks,” Real-Time Systems Symposium, Proceedings, vol., Iss. 6-8, Dec. 1988.
Hou, et al., “Allocation of Periodic Task Modules with Precedence and Deadline Constraints in Distributed Real-Time Systems,” Real-Time Systems Symposium, vol., Iss. 2-4, Dec. 1992.
Ramos-Thuel, et al., “On-Line Scheduling of Hard Deadline Aperiodic Tasks in Fixed-Priority Systems,” Real-Time Systems Symposium, Proceedings, vol., Iss. 1-3, Dec. 1993, pp. 160-171.
Davis, et al., “Optimal Priority Assignment for Aperiodic Tasks with Firm Deadlines in Fixed Priority Pre-emptive Systems,” Information Processing Letters, vol. 53, No. 5, Mar. 1995, pp. 249-254.
Prassana, S., “Compilation of Parallel Multimedia Computations—Extended Retiming Theory and Amdahl's Law,”Sixth ACM SIGPLAN Symposiu
Knobe Kathleen
Rehg James M.
An Meng-Ai
Hewlett-Packard Development Company, Inc.
Lange Richard P.
To Jennifer N.
LandOfFree
On-line scheduling of constrained dynamic applications for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with On-line scheduling of constrained dynamic applications for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-line scheduling of constrained dynamic applications for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3590962