Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Patent
1996-12-30
1999-09-21
Oberley, Alvin E.
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
G06F 900
Patent
active
059547928
ABSTRACT:
Efficient methods for verifying the timing behavior of a system in which various tasks are executed on a processor, and each task is enabled (i.e., becomes ready to execute) in response to the occurrence of an external event and/or the completion of another task. The methods are computationally efficient, requiring an execution time that is polynomial in the number of tasks in the system. The methods can be used in complementary fashion with more computationally intensive techniques for timing behavior verification, such as simulation or prototyping, by limiting the use of such techniques to those systems whose correctness is not proven by the methods.
REFERENCES:
patent: 4642756 (1987-02-01), Sherrod
patent: 4792890 (1988-12-01), Blair et al.
patent: 5012409 (1991-04-01), Fletcher et al.
patent: 5136705 (1992-08-01), Stubbs et al.
patent: 5210872 (1993-05-01), Ferguson et al.
patent: 5392429 (1995-02-01), Agrawal et al.
patent: 5768594 (1998-06-01), Blelloch et al.
Ha, Rhan et al., "Validating Timing Constraints in Multiprocessor and Distributed Real-Time Systems," Proceedings of the 14th International Conference on Distributed Computing Systems, Ponzan, Poland, Jun. 21-24, 1994, Institute of Electrical and Electronics Engineers, pp. 162-171.
Saksena, Manas C. et al., "Temporal Analysis for Hard Real-Time Scheduling," Proceedings of the 12th International Phoenix Conference on Computers and Communications, Tempe, Arizona, Mar. 23-26, 1993, Institute of Electrical and Electronics Engineers, pp. 538-544 (see p. 539, right-hand col., line 1 and p. 542, left-hand col., line 10).
Stoyenko, Alexander D., "A Schedulability Analyzer for Real-Time Euclid," Proceedings of the Real Time Systems Symposium, San Jose, California, Dec. 1-3, 1987, Institute of Electrical and Electronics Engineers, pp. 218-227.
Xu, Jia et al., "On Satisfying Timing Constraints in Hard-Real-Time Systems," IEEE Transactions on Software Engineering, vol. 19, No. 1, pp. 70-84, Jan. 1993.
Xu, Jia et al., "Schedule Processes with Release Times, Deadlines, Precedence, and Exclusion Relations," IEEE Transactions on Softward Engineering, vol. 16, No. 3, pp. 360-369, Mar. 1990.
Rajeev Alur, Thomas A. Henzinger, "Selective Quantitative Analysis and Interval Model Checking: Verifying Different Facets of a System", Computer Aided Verification, 8th Internatioinal Conference, CAV'96, New Brunswick, NJ, USA, Springer Editor, Jul. 31 to Aug. 3, 1996, pp. 257 to 68.
Neil C. Audsley, Alan Burns, M. Richardson, Ken W. Tindell, and Andy J. Wellings, "Applying new scheduling theory to static priority pre-emptive scheduling." Software Engineering Journal, pp. 284 to 292, Sep. 1993.
Neil C. Audsley, Ken W. Tindell, and Alan Burns. "The end of the line for static cyclic scheduling?" Proceedings of the 5th Euromicro Workshop on Real-Time Systems, pp. 36 to 41, Oulu, Finland, 1993.
Felice Balarin, "Schedule validation for embedded reactive real-time systems," in preparation, 1996, pp. 1 to 16.
Felice Balarin, Harry Hsieh, Attila Jurecska, Luciano Lavagno, and Alberto Sangiovanni-Vincentelli. "Formal verification of embedded systems based on CFSM networks." In Proceedings of the 33th ACM/IEEE Design Automation Conference, Jun. 1996, 4 pages.
Felice Balarin, Karl Petty, Alberto L. Sangiovanni-Vincentelli, and Pavin Varaiya. "Formal verification of the PATHO real-time operating system." In Proceedings of 33rd Conference on Decision and Control CDC'94, Dec. 1994.
Jin-Young Choi, Insup Lee, and Hong-Liang Xie. "The specification and schedulatity analysis of real-time systems using acsr." In Proceedings of IEEE Real-Time Systems Symposium, pp. 266 to 275. IEEE Computer Society Press, Dec. 1995.
Thoms H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Depth-first search," Chapter 23.3, Introduction to Algorithms, The MIT Press, McGraw-Hill Book Companypp. 477 to 487.
Michael R. Garey, David S. Johnson, "Computers and Intractability, a Guide to the Theory of Np-Completeness", W.H. Freeman and Company, New York, pp. 90 to 95.
Richard Gerber, Seongsoo Hong, and Manas Saksena. "Guaranteeing end-to-end timing constraints by calibrating intermediate processes." In Proceedings of IEEE Real-Time Systems Symposium, pp. 192 to 203. IEEE Computer Society Press, Dec. 1994.
Michael Gonzalez Harbour, Mark H. Klein, and John Lehoczky. "Timing analysis for fixed-priority scheduling of hard real-time systems." IEEE Transaction of Software Engineering, 20(1), Jan. 1994, pp. 13 to 28.
C. L. Liu and James W. Layland. "Scheduling algorithms for multiprogramming in a hard real-time environment." Journal of the Association for Computing Machinery, 20(1):46-61, Jan. 1973.
P. McGeer, A. Saldanha, R. Brayton, and A. Sangiovanni-Vincentelli. "Delay models and exact timing analysis." In T. Sasao, editor, Logic synthesis and optimization. Kluwer Academic Publishers, 1993, pp. 167 to 189.
Marco Spuri and John A. Stankovic. "How to integrate precedence constraints and shared resources in real-time scheduling." IEEE Transactions on Computers, 43(12):1407-12, 1994, reprinted as pp. 1 to 17.
Cadence Design Systems Inc.
Cherubin Yveste G.
Oberley Alvin E.
LandOfFree
Method for schedule validation of embedded systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for schedule validation of embedded systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for schedule validation of embedded systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-75766