Analysis and optimisation of heterogeneous real-time embedded systems
Analysis and optimisation of heterogeneous real-time embedded systems
- Author(s): P. Pop ; P. Eles ; Z. Peng
- DOI: 10.1049/ip-cdt:20045069
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): P. Pop 1 ; P. Eles 1 ; Z. Peng 1
-
-
View affiliations
-
Affiliations:
1: Computer and Information Science Department, Linköping University, Linköping, Sweden
-
Affiliations:
1: Computer and Information Science Department, Linköping University, Linköping, Sweden
- Source:
Volume 152, Issue 2,
March 2005,
p.
130 – 147
DOI: 10.1049/ip-cdt:20045069 , Print ISSN 1350-2387, Online ISSN 1359-7027
An increasing number of real-time applications are today implemented using distributed heterogeneous architectures composed of interconnected networks of processors. The systems are heterogeneous, not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. Each network has its own communication protocol, each processor in the architecture can have its own scheduling policy, and several scheduling policies can share a processor. In this context, the task of designing such systems is becoming increasingly important and difficult at the same time. The success of such new design methods depends on the availability of analysis and optimisation techniques. Analysis and optimisation techniques for heterogeneous real-time embedded systems are presented in the paper. The authors address in more detail a particular class of such systems called multi-clusters, composed of several networks interconnected via gateways. They present a schedulability analysis for safety-critical applications distributed on multi-cluster systems and briefly highlight characteristic design optimisation problems: the partitioning and mapping of functionality, and the packing of application messages to frames. Optimisation heuristics for frame packing aimed at producing a schedulable system are presented. Extensive experiments and a real-life example show the efficiency of the frame-packing approach.
Inspec keywords: control engineering computing; processor scheduling; protocols; distributed processing; embedded systems; internetworking
Other keywords:
Subjects: Computer communications; Protocols; Protocols; Instrumentation buses and protocols; Distributed systems software; Multiprocessing systems; Computer networks and techniques; Control engineering computing
References
-
-
1)
- SAE Vehicle Network for Multiplexing and Data Communications Standards Committee, SAE J1850 Standard, 1994.
-
2)
- N. Audsley , A. Burns , R. Davis , K. Tindell , A. Wellings . Fixed priority preemptive scheduling: an historical perspective. Real-Time Syst. , 173 - 198
-
3)
- Audsley, N.C., Burns, A., Richardson, M.F., Wellings, A.J.: `Hard real-time scheduling: the deadline monotonic approach', Proc. 8th IEEE Workshop on Real-Time Operating Systems and Software, 1991, p. 127–132.
-
4)
- Profibus International, PROFIBUS DP specification, http://www.profibus.com/, 2003.
-
5)
- J.K. Strosnider , T.E. Marchok . Responsive, deterministic IEEE 802.5 token ring scheduling. Real-Time Syst. , 2 , 133 - 158
-
6)
- TTP-Plan, http://www.tttech.com/.
-
7)
- The FlexRay Group, FlexRay Requirements Specification, Version 2.0.2, http://www.flexray-group.com/, 2002.
-
8)
- TimeWiz, http://www.timesys.com.
-
9)
- Kienhuis, B., Deprettere, E., Vissers, K., Van Der Wolf, P.: `An approach for quantitative analysis of application-specific dataflow architectures', Proc. IEEE Int. Conf. on Application-Specific Systems, Architectures and Processors, 1997, p. 338–349.
-
10)
- Kopez, H., Nossal, R.: `The cluster-compiler - a tool for the design of time triggered real-time systems', Proc. ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Real-Time Systems, 1995, p. 108–116.
-
11)
- A. Rajnak , K. Tindell , L. Casparsson . (1998) Volcano communications concept.
-
12)
- Gutiérrez García, J.J., González Harbour, M.: `Optimized priority assignment for tasks and messages in distributed hard real-time systems', Proc. Workshop on Parallel and Distributed Real-Time Systems, 1995, p. 124–132.
-
13)
- C.R. Reeves . (1993) Modern heuristic techniques for combinatorial problems.
-
14)
- T.Y. Yen , W. Wolf . (1997) Hardware-software co-synthesis of distributed embedded systems.
-
15)
- Pop, P.: `Analysis and Synthesis of Communication-Intensive Heterogeneous Real-Time Systems', 2003, PhD dissertation, Linköping Studies in Science and Technology, No. 833, 2003.
-
16)
- F. Balarin , Y. Watanabe , H. Hsieh , L. Lavagno , C. Paserone , A. Sangiovanni-Vincentelli . Metropolis: an integrated electronic system design environment. Computer , 4 , 45 - 52
-
17)
- Audsley, N., Tindell, K., Burns, A.: `The end of line for static cyclic scheduling?', Proc. Euromicro Workshop on Real-Time Systems, 1993, p. 36–41.
-
18)
- Ermedahl, H., Hansson, H., Sjödin, M.: `Response-time guarantees in ATM networks', Proc. IEEE Real-Time Systems Symp., 1997, p. 274–284.
-
19)
- K. Jost . From fly-by-wire to drive-by-wire. Automot. Eng. Int.
-
20)
- K. Tindell , A. Burns , A. Wellings . Calculating CAN message response times. Control Eng.Pract. , 8 , 1163 - 1169
-
21)
- Pop, P., Eles, P., Peng, Z., Izosimov, V., Hellring, M., Bridal, O.: `Design optimisation of multi-cluster embedded systems for real-time applications', Proc. Design, Automation and Test in Europe Conf., 2004, p. 1028–1033.
-
22)
- X-by-Wire Consortium, X-by-wire: safety related fault tolerant systems in vehicles, http://www.vmars.tuwien.ac.at/projects/xbywire/, 1998.
-
23)
- RapidRMA, http://www.tripac.com.
-
24)
- C.L. Liu , J.W. Layland . Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM , 1 , 46 - 61
-
25)
- TTTech, Comparison CAN-Byteflight-FlexRay-TTP/C, Technical Report, availabe at http://www.tttech.com/.
-
26)
- Palencia, J.C., González Harbour, M.: `Schedulability analysis for tasks with static and dynamic offsets', Proc. 19th IEEE Real-Time Systems Symp., 1998, p. 26–37.
-
27)
- Aires, http://kabru.eecs.umich.edu/aires/.
-
28)
- A. Burns , A. Wellings . (2001) Real-time systems and programming languages.
-
29)
- Lönn, H., Axelsson, J.: `A comparison of fixed-priority and static cyclic scheduling for distributed automotive control applications', Proc. Euromicro Conf. on Real-Time Systems, 1999, p. 142–149.
-
30)
- Robert Bosch GmbH, CAN specification, version 2.0, http://www.can.bosch.com/, 1991.
-
31)
- K. Keutzer , S. Malik , A.R. Newton . System-level design: orthogonalization of concerns and platform-based design. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. , 12 , 1523 - 1543
-
32)
- Virtual component co-design, http://www.cadence.com/.
-
33)
- Echelon, LonWorks: The LonTalk protocol specification, http://www.echelon.com, 2003.
-
34)
- J. Xu , D.L. Parnas . On satisfying timing constraints in hard-real-time systems. IEEE Trans. Softw. Eng. , 1 , 70 - 84
-
35)
- J. Jonsson , K.G. Shin . Robust adaptive metrics for deadline assignment in distributed hard real-time systems. Real-Time Syst. , 3 , 239 - 271
-
36)
- Pop, P., Eles, P., Peng, Z.: `Scheduling with optimized communication for time triggered embedded systems', Proc. Int. Workshop on Hardware-Software Codesign, 1999, p. 178–182.
-
37)
- H. Kopetz . (1997) Real-time systems - design principles for distributed embedded applications.
-
38)
- Sandström, K., Norström, C.: `Frame packing in real-time communication', Proc. Int. Conf. on Real-Time Computing Systems and Applications, 2000, p. 399–403.
-
39)
- K. Tindell , J. Clark . Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogram. , 117 - 134
-
40)
- F. Balarin , L. Lavagno , P. Murthy , A. Sangiovanni-Vincentelli . Scheduling for embedded real-time systems. IEEE Des. Test Comput. , 71 - 82
-
41)
- B. Tabbara , A. Tabbara , A. Sangiovanni-Vincentelli . (2000) Function/ architecture optimisation and co-design of embedded systems.
-
42)
- F. Balarin . (1997) Hardware-software co-design of embedded systems: the POLIS approach.
-
43)
- G. Agrawal , B. Chen , W. Zhao , S. Davari . Guaranteeing synchronous message deadlines with the token medium access control protocol. IEEE Trans. Comput. , 3 , 327 - 339
-
44)
- SystemBuild/MatrixX, http://www.ni.com/matrixx.
-
45)
- Ascet/SD, http://en.etasgroup.com/products/ascet_sd/.
-
46)
- Pop, P., Eles, P., Peng, Z.: `Schedulability analysis and optimisation for the synthesis of multi-cluster distributed embedded systems', Proc. Design Automation and Test in Europe Conf., 2003, p. 184–189.
-
47)
- K. Richter , M. Jersak , R. Ernst . A formal approach to MpSoC performance verification. Computer , 4 , 60 - 67
-
48)
- Tindell, K.: `Adding time-offsets to schedulability analysis', YCS-94-221, 1994.
-
49)
- P. Puschner , A. Burns . A review of worst-case execution-time analyses. Real-Time Syst.
-
50)
- TTTech, TTP/C specification version 0.5, 1999, availabe at http://www.tttech.com/.
-
51)
- K. Hoyme , K. Driscoll . SAFEbus. IEEE Aerosp. Electron. Syst. Mag. , 3 , 34 - 39
-
52)
- Local interconnect network protocol specification, http://www.lin-subbus.org, 2003.
-
53)
- Kopetz, H.: `Automotive electronics–present state and future prospects', 25th Int. Symp. on Fault-Tolerant Computing, 1995.
-
54)
- Palencia, J.C., González Harbour, M.: `Exploiting precedence relations in the schedulability analysis of distributed real-time systems', Proc. 20th IEEE Real-Time Systems Symp., 1999, p. 328–339.
-
55)
- J. Xu , D.L. Parnas . Priority scheduling versus pre-run-time scheduling. Real Time Syst. , 1 , 7 - 24
-
56)
- C. Lee , M. Potkonjak , W. Wolf . Synthesis of hard real-time application specific systems. Des. Autom. Embedded Syst. , 4 , 215 - 241
-
57)
- G. Leen , D. Heffernan . Expanding automotive electronic systems. Computer , 1 , 88 - 93
-
58)
- Matlab/Simulink, http://www.mathworks.com.
-
59)
- P. Eles , A. Doboli , P. Pop , Z. Peng . Scheduling with bus access optimisation for distributed embedded systems. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. , 472 - 491
-
60)
- P. Pop , P. Eles , Z. Peng . Schedulability-driven communication synthesis for time-triggered embedded systems. Real-Time Syst. , 297 - 325
-
61)
- Pop, P., Eles, P., Peng, Z.: `Bus access optimisation for distributed embedded systems based on schedulability analysis', Proc. Design Automation and Test in Europe Conf., 2000, p. 567–574.
-
62)
- Hansen, P.: The Hansen report on automotive electronics, http://www.hansenreport.com/, July-August, 2002.
-
63)
- Kopetz, H.: `Automotive electronics', Proc. 11th Euromicro Conf. on Real-Time Systems, 1999, p. 132–140.
-
64)
- M. Chiodo . (1996) Automotive electronics: a major application field for hardware-software co-design, Hardware/software co-design.
-
65)
- Statemate, http://www.ilogix.com.
-
66)
- International Organization for Standardization, Road vehicles–controller area network (CAN)–Part 4: Time-triggered communication, ISO/DIS 11898-4, 2002.
-
67)
- J.A. Stankovic , K. Ramamritham . (1993) Advances in real-time systems.
-
68)
- EAST-EEA project, ITEA Full Project Proposal, http://www.itea-office.org, 2002.
-
69)
- RTA-OSEK Planner, http://www.livedevices.com.
-
70)
- B.P. Dave , N.K. Jha . COHRA: hardware-software cosynthesis of hierarchical heterogeneous distributed systems. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. , 10 , 900 - 919
-
71)
- Volcano Network Analyzer, http://www.volcanoautomotive.com/.
-
72)
- Pop, T., Eles, P., Peng, Z.: `Holistic scheduling and analysis of mixed time/event-triggered distributed embedded systems', Proc. Int. Symp. on Hardware/Software Codesign, 2002, p. 187–192.
-
73)
- Berwanger, J., Peller, M., and Griessbach, R.: A new high performance data bus system for safety-related applications, http://www.byteflight.de, 2000.
-
74)
- B.P. Dave , G. Lakshminarayana , N.J. Jha . COSYN: hardware-software co-synthesis of heterogeneous distributed embedded systems. IEEE Trans. VLSI Syst. , 1 , 92 - 104
-
75)
- J. Rushby . Bus architectures for safety-critical embedded systems. Lect. Notes Comput. Sci. , 306 - 323
-
76)
- Miner, P.S.: `Analysis of the SPIDER fault-tolerance protocols', Proc. 5th NASA Langley Formal Methods Workshop, 2000.
-
77)
- Nolte, T., Hansson, H., Norström, C., Punnekkat, S.: `Using bit-stuffing distributions in CAN analysis', Proc. IEEE/IEE Real-Time Embedded Systems Workshop, 2001.
-
1)