skip to main content
article

Schedulability-driven frame packing for multicluster distributed embedded systems

Published: 01 February 2005 Publication History

Abstract

We present an approach to frame packing for multicluster distributed embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. In our approach, the application messages are packed into frames such that the application is schedulable, thus the end-to-end message communication constraints are satisfied. We have proposed a schedulability analysis for applications consisting of mixed event-triggered and time-triggered processes and messages, and a worst-case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Optimization heuristics for frame packing aiming at producing a schedulable system have been proposed. Extensive experiments and a real-life example show the efficiency of our frame-packing approach.

References

[1]
Audsley, N., Burns, A., Davis, R., Tindell, K., and Wellings, A. 1995. Fixed priority preemptive scheduling: An historical perspective. J. Real-Time Syst. 8, 2/3, 173--198.
[2]
Audsley, N., Tindell, K., and Burns, A. 1993. The end of line for static cyclic scheduling? In Proceedings of the Euromicro Workshop on Real-Time Systems. 36--41.
[3]
Balarin, F., Lavagno, L., Murthy, P., and Sangiovanni-Vincentelli, A. 1998. Scheduling for embedded real-time systems. IEEE Design and Test of Computers Jan.--Mar., 71--82.
[4]
Bosch GmbH.1991. CAN Specification, Version 2.0. http://www.can.bosch.com.
[5]
Dave, B. P. and Jha, N. J. 1998. COHRA: Hardware-software cosynthesis of hierarchical heterogeneous distributed systems. IEEE Trans. CAD 17, 10, 900--919.
[6]
EAST-EEA Project. 2002. ITEA full project proposal. http://www.itea-office.org.
[7]
Dave, B. P., Lakshminarayana, and Jha, N. J., 1999. COSYN: Hardware-software cosynthesis of heterogeneous distributed embedded systems. IEEE Trans. VLSI Syst. 7, 1, 92--104.
[8]
Edwards, S.,2000. Languages for Digital Embedded Systems. Kluwer Academic Publishers, Norwell, MA.
[9]
Eles, P., Doboli, A., Pop, P., and Peng, Z., 2000. Scheduling with bus access optimization for distributed embedded systems. In IEEE Trans. VLSI Syst., 472--491.
[10]
Ernst, R.1998. Codesign of embedded systems: Status and trends. IEEE Design & Test of Computers, Apr.--June, 45--54.
[11]
FlexRay Group.2002. FlexRay requirements specification, version 2.0.2. http://www.flexray-group. com.
[12]
Gutiérrez García, J. J. and González Harbour, M. 1995. Optimized priority assignment for tasks and messages in distributed hard real-time systems. In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems. 124--132.
[13]
Kopetz, H. 1997. Real-Time Systems---Design Principles for Distributed Embedded Applications. Kluwer Academic Publishers, Norwell, MA.
[14]
Kopez, H. and Nossal, R. 1995. The cluster-compiler---A tool for the design of time triggered real-time systems. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Real-Time Systems. 108--116.
[15]
Lavagno, L., Sangiovanni-Vincentelli, A., and Sentovich, E. 1999. Models of computation for embedded system design. In System-Level Synthesis. Kluwer Academic Publishers, Norwell, MA. 45--102.
[16]
Lee, E. A. and Parks, T. M. 1995. Dataflow process networks. Proc. IEEE 83, 773--801.
[17]
Lee, C., Potkonjak, M., and Wolf, W. 1999. Synthesis of hard real-time application specific systems. Design Automation for Embedded Systems 4, 4, 215--241.
[18]
Leen, G. and Heffernan, D. 2002. Expanding automotive electronic systems. Computer 35, 1, 88--93.
[19]
Liu, C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61.
[20]
Lonn, H. and Axelsson J. 1999. A comparison of fixed-priority and static cyclic scheduling for distributed automotive control applications. In Proceedings of the Euromicro Conference on Real-Time Systems. 142--149.
[21]
Melin, K. 1998. Volvo S80: Electrical system of the future. Technology Report, Volvo Corporation.
[22]
Nolte, T., Hansson, H., Norström, C., and Punnekkat, S. 2001. Using bit-stuffing distributions in CAN analysis. In Proceedings of the IEEE/IEE Real-Time Embedded Systems Workshop.
[23]
Palencia, J. C. and González Harbour, M. 1998. Schedulability analysis for tasks with static and dynamic offsets. In Proceedings of the 19th IEEE Real-Time Systems Symposium. 26--37.
[24]
Palencia, J. C. and González Harbour, M. 1999. Exploiting precedence relations in the schedulability analysis of distributed real-time systems. In Proceedings of the 20th IEEE Real-Time Systems Symposium. 328--339.
[25]
Pop, P. 2003. Analysis and synthesis of communication-intensive heterogeneous real-time systems. Ph.D. Dissertation No. 833, Linköping Studies in Science and Technology.
[26]
Pop, P., Eles, P., and Peng, Z. 1999. Scheduling with optimized communication for time triggered embedded systems. In Proceedings of the International Workshop on Hardware-Software Codesign. 178--182.
[27]
Pop, P., Eles, P., and Peng, Z. 2000. Bus access optimization for distributed embedded systems based on schedulability analysis. In Proceedings of the Design Automation and Test in Europe Conference. 567--574.
[28]
Pop, P., Eles, P., and Peng, Z. 2002. Holistic scheduling and analysis of mixed time/event-triggered distributed embedded systems. In Proceedings of the International Symposium on Hardware/Software Codesign. 187--192.
[29]
Pop, P., Eles, P., and Peng, Z. 2003. Schedulability analysis and optimization for the synthesis of multi-cluster distributed embedded systems. In Proceedings of Design Automation and Test in Europe Conference. 184--189.
[30]
Pop, P., Eles, P., and Peng, Z. 2004. Schedulability-driven communication synthesis for time-triggered embedded systems. J. Real-Time Syst. 24, 297--325.
[31]
Pop, P., Eles, P. Peng, Z. Izosimov, V. Hellring, M., and Bridal, O. 2004. Design optimization of multi-cluster embedded systems for real-time applications. In Proceedings of Design, Automation and Test in Europe Conference. 1028--1033.
[32]
Puschner, P. and Burns, A. 2000. A review of worst-case execution-time analyses. J. Real-Time Syst. 18, 115--128.
[33]
Rajnak, A., Tindell, K., and Casparsson, L. 1998. Volcano Communications Concept. Technical Report, Volcano Communication Technologies AB.
[34]
Reevs, C. R. 1993. Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications.
[35]
Sandström, K. and Norström, C. 2000. Frame packing in real-time communication. In Proceedings of the International Conference on Real-Time Computing Systems and Applications. 399--403.
[36]
Stankovic, J. A. and Ramamritham, K. 1993. Advances in Real-Time Systems. IEEE Computer Society Press, Los Alamitos, CA.
[37]
Tindell, K. 1994. Adding Time-Offsets to Schedulability Analysis. Report no. YCS--94--221, Department of Computer Science, University of York.
[38]
Tindell, K., Burns, A., and Wellings, A. 1995. Calculating CAN message response times. Control Engineering Practice 3, 8, 1163--1169.
[39]
Tindell, K. and Clark, J. 1994. Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogram. 40, 117--134.
[40]
TTTech. 1999. TTP/C specification version 0.5. http://www.tttech.com.
[41]
TTTech. 2002. Comparison CAN--Byteflight--FlexRay--TTP/C. Technical Report, http://www.tttech.com.
[42]
Wolf, W. 2003. A Decade of hardware/software codesign. Computer 36, 4, 38--43.
[43]
Xu, J. and Parnas, D. L. 1993. On satisfying timing constraints in hard-real-time systems. IEEE Trans. Software Eng. 19, 1, 70--84.
[44]
Xu, J. and Parnas, D. L. 2000. Priority scheduling versus pre-run-time scheduling. J. Real Time Syst. 18, 1, 7--24.
[45]
Yen, T. Y. and Wolf, W. 1997. Hardware-Software Co-Synthesis of Distributed Embedded Systems. Kluwer Academic Publishers, Norwell, MA.

Cited By

View all
  • (2024)Optimality-Guaranteed Design Space Pruning for CAN-FD Frame PackingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.329869943:1(44-56)Online publication date: 1-Jan-2024
  • (2022)Security-Aware CAN-FD Message Packing in Intelligent Automotive Cyber–Physical SystemsIEEE Internet of Things Journal10.1109/JIOT.2021.30854229:22(22343-22356)Online publication date: 15-Nov-2022
  • (2021)Efficient AUTOSAR-Compliant CAN-FD Frame Packing with Observed Optimality2021 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE51398.2021.9473962(1899-1904)Online publication date: 1-Feb-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems
ACM Transactions on Embedded Computing Systems  Volume 4, Issue 1
February 2005
254 pages
ISSN:1539-9087
EISSN:1558-3465
DOI:10.1145/1053271
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 01 February 2005
Published in TECS Volume 4, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Frame packing
  2. distributed embedded systems
  3. schedulability analysis

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Optimality-Guaranteed Design Space Pruning for CAN-FD Frame PackingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.329869943:1(44-56)Online publication date: 1-Jan-2024
  • (2022)Security-Aware CAN-FD Message Packing in Intelligent Automotive Cyber–Physical SystemsIEEE Internet of Things Journal10.1109/JIOT.2021.30854229:22(22343-22356)Online publication date: 15-Nov-2022
  • (2021)Efficient AUTOSAR-Compliant CAN-FD Frame Packing with Observed Optimality2021 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE51398.2021.9473962(1899-1904)Online publication date: 1-Feb-2021
  • (2021)Cluster-Based CAN-FD Frame Packing Framework Optimization Using Two StrategiesIEEE Transactions on Vehicular Technology10.1109/TVT.2021.307416370:5(4784-4795)Online publication date: May-2021
  • (2020)Approaches for Assigning Offsets to Signals for Improving Frame Packing in CAN-FDIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.290792139:5(1109-1122)Online publication date: May-2020
  • (2017)Offset Assignment to Signals for Improving Frame Packing in CAN-FD2017 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2017.00023(167-177)Online publication date: Dec-2017
  • (2017)An optimized design of CAN FD for automotive cyber-physical systemsJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2017.10.00881:C(101-111)Online publication date: 1-Nov-2017
  • (2016)Design optimisation of cyber‐physical distributed systems using IEEE time‐sensitive networksIET Cyber-Physical Systems: Theory & Applications10.1049/iet-cps.2016.00211:1(86-94)Online publication date: Dec-2016
  • (2016)Formal timing analysis of CAN-to-Ethernet gateway strategies in automotive networksReal-Time Systems10.1007/s11241-015-9243-y52:1(88-112)Online publication date: 1-Jan-2016
  • (2015)Design optimization of TTEthernet-based distributed real-time systemsReal-Time Systems10.1007/s11241-014-9214-851:1(1-35)Online publication date: 1-Jan-2015
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media