Fast performance prediction for periodic task systems

ABSTRACT

During design exploration, many implementations of the same system specification may need to be evaluated. In this paper, we present an approach to construct sufficient and necessary conditions for a given system specifications. These conditions can be employed in the design exploration process to rapidly determine if an implementation of the system satisfies the timing constraints. We prove that our conditions always outperform the existing respective conditions. Experimental results are also provided to compare our approach with known scheduling results.

REFERENCES

• 1: N. Audsley, A. Bums, M. Richardson, K. Tindell and A.J. Wellings, "Applying new scheduling theory to static priority pre-emptive scheduling," Software Engineering Journal, vol. 8, no. 5, pp. 284-292, 1993.
• 2: Jörg Liebeherr , Almut Burchard , Yingfeng Oh , Sang H. Son, New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems, IEEE Transactions on Computers, v.44 n.12, p.1429-1442, December 1995 [doi>10.1109/12.477248]
• 3: Sheng-Tzong Cheng , A. K. Agrawala, Allocation and scheduling of real-time periodic tasks with relative timing constraints, Proceedings of the 2nd International Workshop on Real-Time Computing Systems and Applications, p.210, October 25-27, 1995
• 4: R.P. Dick and J.K. Jha, "MOGAC: A multiobjective genetic algorithm for the co-synthesis of hardware-software embedded systems," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 920-935, vol. 17, no. 10, Oct 1998.
• 5: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 6: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 7: W.A. Halang and A.D. Stoyenko, "Next generation of real-time operating systems: industrial perspective," Proceedings of the NATO Advanced Study Institute on Real Time Computing, pp. 595-596, 1994.
• 8: C.-C. Han , H.-Y. Tyan, A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), p.36, December 03-05, 1997
• 9: M. G. Harbour , M. H. Klein , J. P. Lehoczky, Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems, IEEE Transactions on Software Engineering, v.20 n.1, p.13-28, January 1994 [doi>10.1109/32.263752]
• 10: Rajeshkumar S. Sambandam , Xiaobo Hu, Predicting timing behavior in architectural design exploration of real-time embedded systems, Proceedings of the 34th annual conference on Design automation, p.157-160, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266054]
• 11: James P. Huang, Modeling of software partition for distributed real-time applications, IEEE Transactions on Software Engineering, v.11 n.10, p.1113-1126, Oct. 1985 [doi>10.1109/TSE.1985.231859]
• 12: X. Hu and d. G. Dgtmbrosio, "Hardware/software partitioning for real-time embedded systems," Journal of Design Automation for Embedded Systems. vol. 2, no. 3/4, pp. 339-358, 1997.
• 13: d. Lehoczky, L. Sha and Y Ding, "The rate monotonic scheduling algorithm: Exact characterization and average case behavior" Proceedings of the 1989 IEEE Real-time System Symposium, pp. 166-171, 1989.
• 14: d. Lehoczky and S. Ramos-Thue, "An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems," Proceedings of the 11992 IEEE Real-time System Symposium, pp. 110-123, 1992.
• 15: d. Y-T., Leung, "A new algorithm for scheduling periodic, real-time tasks ", Algorithmica, vol. 4, pp. 209-219, 1989.
• 16: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 17: Dong-Won Park , S. Natarajan , A. Kanevsky , Myung Jun Kim, A generalized utilization bound test for fixed-priority real-time scheduling, Proceedings of the 2nd International Workshop on Real-Time Computing Systems and Applications, p.73, October 25-27, 1995
• 18: Dong-Won Park , Swaminathan Natarajan , Arkady Kanevsky, Fixed-priority scheduling of real-time systems using utilization bounds, Journal of Systems and Software, v.33 n.1, p.57-63, April 1996 [doi>10.1016/0164-1212(95)00105-0]
• 19: K. Ramamritham, and d. A. Stankovic, "Dynamic task scheduling in distributed real-time systems" IEEE Software, vol. 1, no. 3, pp. 65- 75, July, 1984.
• 20: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 21: W. Wolf, "Hardware-software co-design of embedded systems," Proceedings of the IEEE, vol. 82, no. 7, pp. 967-989, July 1994.
• 22: Ti-Yen Yen , Wayne Wolf, Performance estimation for real-time distributed embedded systems, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.64-71, October 02-04, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Performance