Article

Schedulability-driven frame packing for multi-cluster distributed embedded systems

Authors:

Zebo PengAuthors Info & Claims

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

Pages 113 - 122

https://doi.org/10.1145/780732.780748

Published: 11 June 2003 Publication History

Abstract

We present an approach to frame packing for multi-cluster 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, we have also 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]

N. Audsley, A. Burns, R. Davis, K. Tindell, A. Wellings, "Fixed Priority Preemptive Scheduling: An Historical Perspective", Real-Time Systems, 8(2/3), 173--198, 1995.

Digital Library

[2]

N. Audsley, K. Tindell, A. Burns, "The End of Line for Static Cyclic Scheduling?", Euromicro Workshop on Real-Time Systems, 36--41, 1993.

[3]

F. Balarin, L. Lavagno, P. Murthy, A. Sangiovanni-Vincentelli, "Scheduling for Embedded Real-Time Systems", IEEE Design and Test of Computers, January-March, 71--82, 1998.

Digital Library

[4]

Robert Bosch GmbH, "CAN Specification, Version 2.0", http://www.can.bosch.com/, 1991.

[5]

P. Eles, A. Doboli, P. Pop, Z. Peng, "Scheduling with Bus Access Optimization for Distributed Embedded Systems", IEEE Transactions on VLSI Systems, 472--491, 2000.

Digital Library

[6]

The FlexRay Group, "FlexRay Requirements Specification, Version 2.0.2", http://www.flexray-group.com/, 2002.

[7]

J. J. Gutiérrez Garcia, M. González Harbour, "Optimized Priority Assignment for Tasks and Messages in Distributed Hard Real-Time Systems", Proceedings of the Workshop on Parallel and Distributed Real-Time Systems, 124--132, 1995.

Digital Library

[8]

H. Kopetz, "Real-Time Systems -- Design Principles for Distributed Embedded Applications", Kluwer Academic Publishers, 1997.

Digital Library

[9]

H. Kopez, R. Nossal, "The Cluster-Compiler -- A Tool for the Design of Time Triggered Real-Time Systems", Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Real-Time Systems, 108--116, 1995.

Digital Library

[10]

H. Lönn, J. Axelsson, "A Comparison of Fixed-Priority and Static Cyclic Scheduling for Distributed Automotive Control Applications", Euromicro Conference on Real-Time Systems, 142--149, 1999.

[11]

J. C. Palencia, M. González Harbour, "Schedulability Analysis for Tasks with Static and Dynamic Offsets", Proceedings of the 19th IEEE Real-Time Systems Symposium, 26--37, 1998.

Digital Library

[12]

T. Pop, P. Eles, Z. Peng, "Holistic Scheduling and Analysis of Mixed Time/Event-Triggered Distributed Embedded Systems", International Symposium on Hardware/Software Codesign, 187--192, 2002.

Digital Library

[13]

P. Pop, P. Eles, Z. Peng, "Bus Access Optimization for Distributed Embedded Systems Based on Schedulability Analysis", Proceedings of the Design Automation and Test in Europe Conference, 567--574, 2000.

Digital Library

[14]

P. Pop, P. Eles, Z. Peng, "Schedulability Analysis and Optimization for the Synthesis of Multi-Cluster Distributed Embedded Systems", Design Automation and Test in Europe Conference, 2003 (to be published).

Digital Library

[15]

P. Pop, P. Eles, Z. Peng, "Scheduling with Optimized Communication for Time Triggered Embedded Systems", International Workshop on Hardware-Software Codesign, 178--182, 1999.

Digital Library

[16]

K. Sandström, C. Norström, "Frame Packing in Real-Time Communication", Proceedings of the International Conference on Real-Time Computing Systems and Applications, 399--403, 2000.

Digital Library

[17]

K. Tindell, "Adding Time-Offsets to Schedulability Analysis", Department of Computer Science, University of York, Report No. YCS-94-221, 1994.

[18]

K. Tindell, A. Burns, A. Wellings, "Calculating CAN Message Response Times", Control Engineering Practice, 3(8), 1163--1169, 1995.

[19]

K. Tindell, J. Clark, "Holistic Schedulability Analysis for Distributed Hard Real-Time Systems", Microprocessing & Microprogramming, Vol. 50, No. 2--3, 1994.

Digital Library

[20]

A. Rajnak, K. Tindell, L. Casparsson, "Volcano Communications Concept", Volcano Communication Technologies AB, 1998.

[21]

J. Xu, D. L. Parnas, "On satisfying timing constraints in hard-real-time systems", IEEE Transactions on Software Engineering, 19(1), 1993.

Digital Library

[22]

T. Y. Yen, W. Wolf, "Hardware-Software Co-Synthesis of Distributed Embedded Systems", Kluwer Academic Publishers, 1997.

Digital Library

Cited By

Saket RNavet N(2018)Frame packing algorithms for automotive applicationsJournal of Embedded Computing10.5555/1370986.13709952:1(93-102)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.5555/1370986.1370995
Bouyssounouse BSifakis J(2005)Computing platformsEmbedded Systems Design10.5555/2137690.2137723(388-449)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/2137690.2137723
Bouyssounouse BSifakis JBouyssounouse BSifakis J(2005)Computing PlatformsEmbedded Systems Design10.1007/978-3-540-31973-3_29(388-449)Online publication date: 2005
https://doi.org/10.1007/978-3-540-31973-3_29
Show More Cited By

Index Terms

Schedulability-driven frame packing for multi-cluster distributed embedded systems
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Schedulability-driven frame packing for multi-cluster distributed embedded systems
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).

We present an approach to frame packing for multi-cluster 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 ...
Schedulability-driven frame packing for multicluster distributed embedded systems

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 ...
Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised

Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

June 2003

304 pages

ISBN:1581136471

DOI:10.1145/780732

General Chair:
Frank Mueller
North Carolina State University
,
Publications Chair:
Uli Kremer
Rutgers University

ACM SIGPLAN Notices Volume 38, Issue 7
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).
July 2003
293 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/780731
Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

LCTES03

Sponsor:

LCTES03: ACM SIGPLAN Symposium on Languages, Compilers, and Tools for Embedded Systems

June 11 - 13, 2003

California, San Diego, USA

Acceptance Rates

LCTES '03 Paper Acceptance Rate 29 of 128 submissions, 23%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
472
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saket RNavet N(2018)Frame packing algorithms for automotive applicationsJournal of Embedded Computing10.5555/1370986.13709952:1(93-102)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.5555/1370986.1370995
Bouyssounouse BSifakis J(2005)Computing platformsEmbedded Systems Design10.5555/2137690.2137723(388-449)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/2137690.2137723
Bouyssounouse BSifakis JBouyssounouse BSifakis J(2005)Computing PlatformsEmbedded Systems Design10.1007/978-3-540-31973-3_29(388-449)Online publication date: 2005
https://doi.org/10.1007/978-3-540-31973-3_29
Ishigooka TNarisawa F(2010)Message Packing Algorithm for CAN-Based Legacy Control Systems Mixed with CAN and FlexRaySAE International Journal of Passenger Cars - Electronic and Electrical Systems10.4271/2010-01-06853:1(88-97)Online publication date: 12-Apr-2010
https://doi.org/10.4271/2010-01-0685
Bouyssounouse BSifakis JBouyssounouse BSifakis J(2005)Computing PlatformsEmbedded Systems Design10.1007/978-3-540-31973-3_29(388-449)Online publication date: 2005
https://doi.org/10.1007/978-3-540-31973-3_29

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents