Article

Free access

Compiling real-time programs into schedulable code

Authors:

Richard GerberAuthors Info & Claims

PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation

Pages 166 - 176

https://doi.org/10.1145/155090.155106

Published: 01 June 1993 Publication History

Abstract

We present a programming language with first-class timing constructs, whose semantics is based on time-constrained relationships between observable events. Since a system specification postulates timing relationships between events, realizing the specification in a program becomes a more straightforward process.

Using these constraints, as well as those imposed by data and control flow properties, our objective is to transform the code so that its worst-case execution time is consistent with its real-time requirements. To accomplish this goal we first translate an event-based source program into intermediate code, in which the timing constraints are imposed on the code itself, and then use a compilation technique which synthesizes feasible code from the original source program.

References

[1]

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley Publishing Company, 1986.

Digital Library

[2]

Alexander Aiken and Alexandru Nicolau. A development environment for horizontal microcode. IEEE Transactions on Software Engineering, pages 584-594, May 1988.

Digital Library

[3]

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. A CM Transactions on Programming Languages and systems, 9:319-345, July 1987.

[4]

Ran Cytron, Andy Lowry, and Kenneth Zadeck. Code motion of control structures in high-level languages, in Conference Record 13ih Annual A CM Symposium on Principles of Programming Languages, pages 70-85. ACM, January 1986.

Digital Library

[5]

B. Dasarathy. Timing constraints of real-time systems: Constructs for expressing them, method for validating them. IEEE Transactions on Software Engineering, 11(1):80-86, January 1985.

Digital Library

[6]

Kemal Ebcioglu and Alexandru Nicolau. A global resource-constrained parallelization technique. In International Conference on $upercomputing, pages 154-163. ACM, June 1989.

Digital Library

[7]

Joseph A Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computer, 30:478-490, July 1981.

Digital Library

[8]

Franco Gasperoni. Compilation techniques for VLIW architectures. Technical Report RC 14915(~66741), IBM T. J. Watson Research Center, September 1989.

[9]

Y. Ishikawa, H. Tokuda, and C. W. Mercer. Object-oriented real-time language design: Constructs for timing constraints. In Proceedings of OOPSLA-90, pages 289-298, October 1990.

Digital Library

[10]

F. Jahanian and A1 Mok. Safety analysis of timing properties in real-time systems. IEEE Transaciions on Software Engineering, 12(9):890-904, September 1986.

Digital Library

[11]

Kevin B. Kenny and Kwei-Jay Lin. Building flexible real-time systems using the Flex language. IEEE Computer, pages 70-78, May 1991.

Digital Library

[12]

E. Kligerman and A. D. Stoyenko. Real-time Euclid: A language for reliable real-time systems. iEEE Transactions on Software Engineering, 12:941-949, September 1986.

Digital Library

[13]

Insup Lee and Vijay Gehlot. Language constructs for real-time programming, in Proceedings IEEE Real-Time Systems Symposium, pages 57-66. IEEE, 1985.

[14]

K. J. Lin and S. Natarajan. Expressing and maintaining timing constraints in FLEX. In Proceedings IEEE ReaL Time Systems Symposium, December 1988.

[15]

A1 Mok and et al. Evaluating tight execution time bounds of programs by annotations. In 6th Workshop on Real-Time Operating Systems and Software, pages 74-80. IEEE, May 1989.

[16]

Alexandru Nicolau. Parallelism, Memory Antialiasing and Correctness Issues for a Trace Scheduling Compiler. PhD thesis, Yale University, June 1984.

Digital Library

[17]

V. Nirkhe, S. Tripathi, and A. Agrawala. Language support for the Maruti real-time system. In Proceedings IEEE Real Time Systems Symposium, December 1990.

[18]

ChangYun Park and Alan C. Shaw. Experimenting with a program timing tool based on source-level timing schema. In Proceedings IEEE Real-Time Systems Symposium, pages 72-81, December 1990.

[19]

Alan C. Shaw. Reasoning about time in higher level language software. IEEE Transactions on Software Engineering, pages 875-889, July 1989.

Digital Library

[20]

Michael Smith, Mark Horowitz, and Monica Lain. Efficient superscalar performance through boosting. In Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 248-259. ACM, October 1992.

Digital Library

Cited By

Zhao WKreahling WWhalley DHealy CMueller F(2006)Improving WCET by applying worst-case path optimizationsReal-Time Systems10.1007/s11241-006-8643-434:2(129-152)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1007/s11241-006-8643-4
Zhao WKreahling WWhalley DHealy CMueller F(2005)Improving WCET by Optimizing Worst-Case PathsProceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium10.1109/RTAS.2005.29(138-147)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/RTAS.2005.29
Wankang Zhao Kulkarni PWhalley DHealy CMueller FGang-Ryung Uh (2004)Tuning the WCET of embedded applicationsProceedings. RTAS 2004. 10th IEEE Real-Time and Embedded Technology and Applications Symposium, 2004.10.1109/RTTAS.2004.1317294(472-481)Online publication date: 2004
https://doi.org/10.1109/RTTAS.2004.1317294
Show More Cited By

Index Terms

Compiling real-time programs into schedulable code
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Compiling real-time programs into schedulable code

We present a programming language with first-class timing constructs, whose semantics is based on time-constrained relationships between observable events. Since a system specification postulates timing relationships between events, realizing the ...
Compiling Embedded Programs to Byte Code
PADL '02: Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages

Functional languages have proven substantially useful for hosting embedded domain-specific languages. They provide an infrastructure rich enough to define both a convenient syntax for the embedded language, a type system for embedded programs, and an ...
Compiling Real-Time Programs With Timing Constraint Refinement and Structural Code Motion

We present a programming language called TCEL (Time-Constrained Event Language), whose semantics are based on time-constrained relationships between observable events. Such a semantics infers only those timing constraints necessary to achieve real-time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation

August 1993

313 pages

ISBN:0897915984

DOI:10.1145/155090

Editor:
Robert Cartwright
Rice Univ., Houston, TX

ACM SIGPLAN Notices Volume 28, Issue 6
June 1993
313 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/173262
Editor:
Richard Wexelblat
IDA/CSED, Alexandria, VA
Issue’s Table of Contents

Copyright © 1993 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI93

Sponsor:

SIGPLAN

PLDI93: ACM SIGPLAN Conference on Programming Languages Design and Implementation

June 21 - 25, 1993

New Mexico, Albuquerque, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
372
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)19

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao WKreahling WWhalley DHealy CMueller F(2006)Improving WCET by applying worst-case path optimizationsReal-Time Systems10.1007/s11241-006-8643-434:2(129-152)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1007/s11241-006-8643-4
Zhao WKreahling WWhalley DHealy CMueller F(2005)Improving WCET by Optimizing Worst-Case PathsProceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium10.1109/RTAS.2005.29(138-147)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/RTAS.2005.29
Wankang Zhao Kulkarni PWhalley DHealy CMueller FGang-Ryung Uh (2004)Tuning the WCET of embedded applicationsProceedings. RTAS 2004. 10th IEEE Real-Time and Embedded Technology and Applications Symposium, 2004.10.1109/RTTAS.2004.1317294(472-481)Online publication date: 2004
https://doi.org/10.1109/RTTAS.2004.1317294
Zhao WWhalley DHealy CMueller F(2004)WCET Code PositioningProceedings of the 25th IEEE International Real-Time Systems Symposium10.1109/REAL.2004.55(81-91)Online publication date: 5-Dec-2004
https://dl.acm.org/doi/10.1109/REAL.2004.55
Subramani K(2002)An Analysis of Zero-Clairvoyant SchedulingTools and Algorithms for the Construction and Analysis of Systems10.1007/3-540-46002-0_8(98-112)Online publication date: 14-Mar-2002
https://doi.org/10.1007/3-540-46002-0_8
Subramani EAgrawala A(2000)The static polytope and its applications to a scheduling problem2000 IEEE International Workshop on Factory Communication Systems. Proceedings (Cat. No.00TH8531)10.1109/WFCS.2000.882560(283-290)Online publication date: 2000
https://doi.org/10.1109/WFCS.2000.882560
Ko LAl-Yaqoubi NHealy CRatliff EArnold RWhalley DHarmon M(1999)Timing constraint specification and analysisSoftware: Practice and Experience10.1002/(SICI)1097-024X(199901)29:1<77::AID-SPE222>3.0.CO;2-329:1(77-98)Online publication date: Jan-1999
https://doi.org/10.1002/(SICI)1097-024X(199901)29:1<77::AID-SPE222>3.0.CO;2-3
Ganesh AMarlowe TStoyenko AYounis MSalinas J(1996)Architecture and language support for fault-tolerance in complex real-time systemsProceedings of ICECCS '96: 2nd IEEE International Conference on Engineering of Complex Computer Systems (held jointly with 6th CSESAW and 4th IEEE RTAW)10.1109/ICECCS.1996.558431(314-322)Online publication date: 1996
https://doi.org/10.1109/ICECCS.1996.558431
Gupta RSpezialetti M(1996)A compact task graph representation for real-time schedulingReal-Time Systems10.1007/BF0036552111:1(71-102)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1007/BF00365521
Nilsen KRygg BGerber RMarlowe T(1995)Worst-case execution time analysis on modern processorsProceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems10.1145/216636.216650(20-30)Online publication date: 1-Nov-1995
https://dl.acm.org/doi/10.1145/216636.216650
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents