Enforcing Schedulability of Multi-Task Systems by Hardware-Software Codesign

ABSTRACT

This paper deals with the problem of hardware-software codesign of hard real-time systems. For a given task set, we perform an exact schedulability test to determine whether the task set is schedulable or not. When there is a task that cannot meet the deadline, we compute the amount of time by which the deadline is missed. Then we determine which tasks should reduce their execution time to compensate that amount of time deviation. The reduction of execution time is achieved by implementing parts of the tasks with hardware. With this approach, we can systematically design a hard real-time system which is infeasible with all software implementation. Preliminary experimental results are given to demonstrate the effectiveness of our approach.

REFERENCES

• 1: Ti-Yen Yen , Wayne Wolf, Hardware-Software Co-Synthesis of Distributed Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1996
• 2: Chunho Lee , Miodrag Potkonjak , Wayne Wolf, System-Level Synthesis of Application Specific Systems using A* Search and Generalized Force-Directed Heuristics, Proceedings of the 9th international symposium on System synthesis, p.2, November 06-08, 1996
• 3: Youngsoo Shin , Kiyoung Choi, Software synthesis through task decomposition by dependency analysis, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.98-104, November 10-14, 1996, San Jose, California, United States
• 4: [4] J. Jeon and K. Choi, "An effective force-directed partitioning algorithm for hardware-software partitioning problem," submitted to 5th Int. Workshop on Hardware/Software Co-Design, Dec. 1996.
• 5: [5] K. Kim, "Generation of interface module in hardware-software codesign," M.S. thesis, Seoul National University, Feb. 1996, in Korean.
• 6: Kyuseok Kim , Yongjoo Kim , Youngsoo Shin , Kiyoung Choi, An integrated hardware-software cosimulation environment with automated interface generation, Proceedings of the 7th IEEE International Workshop on Rapid System Prototyping (RSP '96), p.66, June 19-21, 1996
• 7: 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]
• 8: [8] J. Lehoczky, L. Sha, and Y. Ding, "The rate monotonic scheduling algorithm: exact characterization and average case behavior," in Proc. IEEE Real-Time Systems Symposium , Dec. 1989, pp. 166-171.
• 9: [9] L. Sha, R. Rajkumar, and S. Sathaye, "Generalized rate-monotonic scheduling theory: A framework for developing real-time systems," Proceedings of the IEEE, vol. 82, no. 1, pp. 68-82, Jan. 1994.
• 10: Lui Sha , John B. Goodenough, Real-Time Scheduling Theory and Ada, Computer, v.23 n.4, p.53-62, April 1990 [doi>10.1109/2.55469]
• 11: [11] N. Audlsey, A. Burns, A. Richardson, and A. Wellings, "Hard real-time scheduling: The deadline monotonic approach," in IEEE Workshop on Real-Time Operating Systems and Software, May 1991.
• 12: [12] M. Joseph and P. Pandya, "Finding response times in a real-time system," The Computer J., vol. 29, no. 5, pp. 390-395, Oct. 1986.
• 13: 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]
• 14: D. I. Katcher , H. Arakawa , J. K. Strosnider, Engineering and Analysis of Fixed Priority Schedulers, IEEE Transactions on Software Engineering, v.19 n.9, p.920-934, September 1993 [doi>10.1109/32.241774]
• 15: Alan Burns , Ken Tindell , Andy Wellings, Effective Analysis for Engineering Real-Time Fixed Priority Schedulers, IEEE Transactions on Software Engineering, v.21 n.5, p.475-480, May 1995 [doi>10.1109/32.387477]
• 16: [16] C. Locke, D. Vogel, and T. Mesler, "Building a predictable avionics platform in Ada: A case study," in Proc. Real-Time Systems Symp., Dec. 1991.

INDEX TERMS

Keywords:
Codesign, real-time, schedulability, deadline, rate-monotonic scheduling