Analysis and optimisation of hierarchically scheduled multiprocessor embedded systems. (English) Zbl 1135.68343
Summary: We present an approach to the analysis and optimisation of heterogeneous multiprocessor embedded systems. The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. When several scheduling policies share a resource, they are organised in a hierarchy. In this paper, we first develop a holistic scheduling and schedulability analysis that determines the timing properties of a hierarchically scheduled system. Second, we address design problems that are characteristic to such hierarchically scheduled systems: assignment of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities. We also present several algorithms for solving these problems. Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilisation of the system. The developed algorithms are evaluated using extensive experiments and a real-life example.
Keywords:
Hierarchical schedulers; Multiprocessor embedded systems; Static/dynamic communication protocolsReferences:
| [1] | Abdelhazer T.F. and Shin K.G. (1999). Combined task and message scheduling in distributed real-time systems. IEEE T. Parall. Distr. 10(11): 1179–1191 · doi:10.1109/71.809575 |
| [2] | Agrawal G., Chen B., Zhao W. and Davari S. (1994). Guaranteeing synchronous message deadlines with the timed token medium access control protocol. IEEE T. Comput. 43(3): 327–339 · doi:10.1109/12.272433 |
| [3] | Almeida, L.: Flexibility and timeliness in fieldbus-based real-time systems. Ph. D. Thesis, University of Aveiro, Portugal (1999) |
| [4] | Almeida L., Pedreiras P. and Fonseca J.A.G. (2002). The FTT-CAN protocol: why and how. IEEE T. Ind. Electron. 49(6): 1189–1201 · doi:10.1109/TIE.2002.804967 |
| [5] | Audsley, N., Tindell, K., Burns, A.: The end of line for static cyclic scheduling? 5th Euromicro Workshop on Real-Time Systems (1993) |
| [6] | Audsley, N., Burns, A., et. al.: Fixed priority preemptive scheduling: an historical perspective. Real-Time Syst 8(2/3) (1995) |
| [7] | Balarin, F., Lavagno, L., et. al.: Scheduling for embedded real-time systems. IEEE Des Test Comput, January–March (1998) |
| [8] | Bini, E., Butazzo, G., Butazzo, G.: A hyperbolic bound for the rate monotonic algorithm. Proceedings of the 13th Euromicro Conference on Real-Time Systems, pp. 59–66 (2001) |
| [9] | Coffman, E.G. Jr., Graham, R.L.: Optimal scheduling for two processor systems. Acta Inform 1, (1972) |
| [10] | Demmeler T. and Giusto P. (2001). A Universal Communication Model for an Automotive System Integration Platform,. Design, Automation and Test in Europe (DATE’01) Conference, Munich, 47–54 |
| [11] | Dobrin, R., Fohler, G.: Implementing off-line message scheduling on Controller Area Network (CAN). Proceedings of the 8th IEEE International Conference on Emerging Technologies and Factory Automation, 1 (2001) |
| [12] | Dobrin, R., Fohler, G., Puschner, P.: Translating off-line schedules into task attributes for fixed priority scheduling. Proceedings of Real-Time Systems Symposium (2001) |
| [13] | Ekelin, C., Jonsson, J.: Solving embedded system scheduling problems using constraint programming. Chalmers University of Technology, Sweden, Report number TR 00–12 (2000) |
| [14] | Eles P., Doboli A., Pop P. and Peng Z. (2000). Scheduling with bus access optimization for distributed embedded systems. IEEE T. VLSI Syst. 8(5): 472–491 · doi:10.1109/92.894152 |
| [15] | Ermedahl, H., Hansson, H., Sjödin, M.: Response time guarantees in ATM networks. Proceedings of Real-Time Systems Symposium (1997) |
| [16] | FlexRay homepage: http://www.flexray-group.com/ (2006) |
| [17] | González Harbour, M., Klein, M.H., Lehoczky, J.P.: Fixed priority scheduling of periodic tasks with varying execution priority. Proceedings of 12th IEEE Real-Time Systems Symposium, pp. 116–128 (1991) |
| [18] | Gonzaléz Harbour, M., Palencia, J.C.: Response time analysis for tasks scheduled under EDF within fixed priorities. Proceedings of Real-Time Systems Symposium, pp. 200–209 (2003) |
| [19] | Gutiérrez García, J.J., González Harbour, M.: Optimized priority assignment for tasks and messages in distributed hard real-time systems. Proceedings of the 3rd Workshop on Parallel and Distributed Real-Time Systems, Santa Barbara, pp. 124–132 (1995) |
| [20] | Hansson, H., Sjödin, M., Tindell, K.: Guaranteeing real-time traffic through an ATM network. Proceedings of the 30th Hawaii International Conference on System Sciences, 5 (1997) |
| [21] | Jonsson, J., Shin, K.J.: A parametrized branch-and-bound strategy for scheduling precedence-constrained tasks on a multiprocessor system. Proceedings of the International Conference on Parallel Processing (ICPP), pp. 158–165 (1997) |
| [22] | Jorgensen, P.B., Madsen, J.: Critical path driven cosynthesis for heterogeneous target architectures. Proceedings of the 5th International Workshop on Hardware-Software Co-design, pp. 15–19 (1997) |
| [23] | Koopman P. (2002). Critical embedded automotive networks. IEEE Micro. 22(4): 14–18 · doi:10.1109/MM.2002.1028471 |
| [24] | Kopetz, H., Fohler, G., Grünsteidl, G., Kantz, H., Pospischil, G., Puschner, P., Reisinger, J., Schlatterbeck, R., Schütz, W., Vrchoticky, A., Zainlinger, R.: The programmer’s view of MARS. Proceedings of 13th IEEE Real-Time Systems Symposium, pp. 223–226 (1992) |
| [25] | Kopetz, H.: Real-time systems–design principles for distributed embedded applications. Kluwer Academic Publisher (1997) · Zbl 0930.68148 |
| [26] | Kuchcinski, K.: Embedded system synthesis by timing constraint solving. Proceedings of the International Symposium on System Synthesis, pp. 50–57 (1997) |
| [27] | Lehoczky, J., Sha, L., Ding, Y.: The rate monotonic scheduling algorithm: exact characterization and average case behaviour. Proceedings of 11th Real-Time Systems Symposium, pp. 166–171 (1989) |
| [28] | Lehoczky, J.P.: Fixed priority scheduling of periodic task sets with arbitrary deadlines. Proceedings of 11th IEEE Real-Time Systems Symposium, pp. 201–209 (1990) |
| [29] | Leung J.Y.T. and Whitehead J. (1989). On the complexity of fixed priority scheduling of periodic, real-time tasks. Perform. Evaluation 2(4): 237–250 · Zbl 0496.90046 · doi:10.1016/0166-5316(82)90024-4 |
| [30] | Liu C.L. and Layland J.W. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment. J. ACM 20(1): 46–61 · Zbl 0265.68013 · doi:10.1145/321738.321743 |
| [31] | Livani, M.A., Kaiser, J.: EDF consensus on CAN bus access for dynamic real-time applications. Proceedings of the IPPS/SPDP Workshops, pp. 1088–1097 (1998) |
| [32] | Lönn, H., Axelsson, J.: A comparison of fixed-priority and static cyclic scheduling for distributed automotive control applications. Proceedings of the 11th Euromicro Conference on Real-Time Systems, pp. 142–149 (1999) |
| [33] | Douglas Locke C. (1992). Software architecture for hard-real time applications: cyclic executives vs. fixed priority executives. J. Real-Time Syst. 4: 37–53 · doi:10.1007/BF00365463 |
| [34] | Palencia, J.C., González Harbour, M.: Schedulability analysis for tasks with static and dynamic offsets. Proceedings of the 19th IEEE Real-Time Systems Symposium, pp. 26–37 (1998) |
| [35] | Palencia, J.C., González Harbour, M.: Exploiting precedence relations in the schedulability analysis of distributed real-time systems. Proceedings of the 20th IEEE Real-Time Systems Symposium (1999) |
| [36] | Palencia, J.C., Gonzaléz Harbour, M.: Offset-based response time analysis of distributed systems scheduled under EDF. Proceedings of the Euromicro Conference on Real-Time Systems, pp. 3–12 (2003) |
| [37] | Pleinevaux, P.: An improved hard real-time scheduling for IEEE 802.5. J. Real-Time Syst. 4(2) (1992) |
| [38] | Pop, P., Eles, P., Peng, Z.: Bus access optimization for distributed embedded systems based on schedulability analysis, pp. 567–574. Design, Automation and Test in Europe (DATE’00) (2000) |
| [39] | Pop P., Eles P., Peng Z. and Doboli A. (2000). Scheduling with bus access optimization for distributed embedded systems. IEEE T. VLSI Syst. 8(5): 472–491 · doi:10.1109/92.894152 |
| [40] | Pop, P., Eles, P., Pop, T., Peng, Z.: An approach to incremental design of distributed embedded systems. Proceedings of the 38th Design Automation Conference (DAC), pp. 450–455. Las Vegas, USA (2001) |
| [41] | Pop, P., Eles, P., Pop, T., Peng, Z.: Minimizing system modification in an incremental design approach. Proceedings of the 9th International Workshop on Hardware/Software Codesign (CODES 2001), pp. 183–188. Copenhagen, Denmark (2001) |
| [42] | Pop P., Eles P. and Peng Z. (2004). Schedulability-driven communication synthesis for time-triggered embedded systems. Real-Time Syst. J. 24: 297–325 · Zbl 1067.68027 · doi:10.1023/B:TIME.0000018246.09796.a3 |
| [43] | Pop, P., Eles, P., Peng, Z.: Schedulability analysis and optimization for the synthesis of multi-cluster distributed embedded systems. Design, Automation and Test in Europe (DATE’03) Conference, pp. 184–189. Munich, Germany (2003) |
| [44] | Pop, P., Eles, P., Peng, Z.: Analysis and synthesis of Distributed Real-Time Embedded Systems. Kluwer Academic Publishers (2004) · Zbl 1067.68027 |
| [45] | Pop, T., Eles, P., Peng, Z.: Holistic scheduling and analysis of mixed time/event-triggered distributed embedded systems. Proceedings of the 10th International Symposium on Hardware/Software Codesign (CODES 2002), pp. 187–192. Estes Park, Colorado, USA (2002) |
| [46] | Pop, T., Eles, P., Peng, Z.: Schedulability analysis for distributed heterogeneous time/event-triggered real-time systems, 15th Euromicro Conference on Real-Time Systems (ECRTS 2003), pp. 257–266 (2003) |
| [47] | Pop, T., Eles, P., Peng, Z.: Design optimization of mixed time/event triggered distributed embedded systems. CODES+ISSS’03 (first merged conference) (2003) |
| [48] | Pop, T., Pop, P., Eles, P., Peng, Z.: Optimization of hierarchically scheduled heterogeneous embedded systems. 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’05), pp. 67–71 (2005) · Zbl 1135.68343 |
| [49] | Prakash S. and Parker A. (1992). SOS: synthesis of application specific heterogeneous multiprocessor systems. J. Parallel Distr. Com. 16: 338–351 · Zbl 0786.68009 · doi:10.1016/0743-7315(92)90017-H |
| [50] | Richter, K., Ernst, R.: Event model interfaces for heterogeneous system analysis. Proceedings of Design, Automation and Test in Europe Conference (DATE’02), Paris, France (2002) |
| [51] | Richter K., Jersak M. and Ernst R. (2003). A formal approach to MpSoC performance verification. IEEE Comput. 36(4): 60–67 |
| [52] | Schwehm, M., Walter, T.: Mapping and scheduling by genetic algorithms. Conference on Algorithms and Hardware for Parallel Processing, pp. 832–841 (1994) |
| [53] | Sha L., Rajkumar R. and Lehoczky J.P. (1990). Priority inheritance protocols: an approach to real time synchronization. IEEE T. Comput. 39(9): 1175–1185 · doi:10.1109/12.57058 |
| [54] | Stankovic, J.A., Spuri, M., di Natale, M., Butazzo, G.C.: Implications of classical scheduling results for real-time systems. Technical Report UM-CS-94–089, Computer Science Department, University of Massachusetts (1994) |
| [55] | Strosneider, J.K., Marchok, T.E.: Responsive, deterministic IEEE 802.5 Token Ring Scheduling. J. Real-Time Syst. 1(2), (1989) |
| [56] | Tindell K., Burns A. and Wellings A.J. (1992). Allocating hard real-time tasks (An NP-hard problem made easy). J. Real-Time Syst. 4(2): 145–165 · doi:10.1007/BF00365407 |
| [57] | Tindell, K., Clark, J.: Holistic schedulability analysis for distributed hard real-time systems. Microproc. Microprog. 50(2–3) (1994) |
| [58] | Tindell, K., Hansson, H., Wellings, A.J.: Analysing real-time communications: controller area network (CAN). Proceedings of Real-Time Systems Symposium (1994) |
| [59] | Tindell, K.: Adding time-offsets to schedulability analysis. Department of Computer Science, University of York, Report Number YCS-94–221 (1994) |
| [60] | Ullman D. (1975). NP-complete scheduling problems. J. Comput. Syst. Sci. 10(3): 384–393 · Zbl 0313.68054 · doi:10.1016/S0022-0000(75)80008-0 |
| [61] | Wandeler, E., Thiele, L.: Real-time interfaces for interface-based design of real-time systems with fixed priority scheduling. ACM Conference on Embedded Software (EMSOFT), pp. 80–89 (2005) |
| [62] | World FIP fieldbus, http://www.worldfip.org/ , April 2003 |
| [63] | Xu, J., Parnas, D.L.: On satisfying timing constraints in hard-real-time systems. IEEE T. Software Eng. 19(1) (1993) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
