More Web Proxy on the site http://driver.im/

article

Free access

Compiling real-time programs into schedulable code

Authors:

Richard GerberAuthors Info & Claims

ACM SIGPLAN Notices, Volume 28, Issue 6

Pages 166 - 176

https://doi.org/10.1145/173262.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

Wang FLo C(1999)Procedure-Level Verification of Real-time Concurrent SystemsReal-Time Systems10.1023/A:100800800333216:1(81-114)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1023/A%3A1008008003332
Gerber RHong S(1997)Slicing real-time programs for enhanced schedulabilityACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/256167.25639419:3(525-555)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/256167.256394
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
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
PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation

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 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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Published in SIGPLAN Volume 28, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
378
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)17

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang FLo C(1999)Procedure-Level Verification of Real-time Concurrent SystemsReal-Time Systems10.1023/A:100800800333216:1(81-114)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1023/A%3A1008008003332
Gerber RHong S(1997)Slicing real-time programs for enhanced schedulabilityACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/256167.25639419:3(525-555)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/256167.256394
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
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Issue’s Table of Contents