Abstract
Giotto is a platform-independent language for specifying software for high-performance control applications. In this paper we present a new approach to the compilation of Giotto. Following this approach, the Giotto compiler generates code for a virtual machine, called the E machine, which can be ported to different platforms. The Giotto compiler also checks if the generated E code is time safe for a given platform, that is, if the platform offers sufficient performance to ensure that the E code is executed in a timely fashion that conforms with the Giotto semantics. Time-safety checking requires a schedulability analysis. We show that while for arbitrary E code, the analysis is exponential, for E code generated from typical Giotto programs, the analysis is polynomial. This supports our claim that Giotto identifies a useful fragment of embedded programs.
Supported in part by the DARPA SEC grant F33615-C-98-3614, MARCO GSRC grant 98-DT-660, AFOSR MURI grant F49620-00-1-0327, NSF grant CCR-9988172, and a Microsoft Research Fellowship.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
K. Altisen, G. Gössler, A. Pnueli, J. Sifakis, S. Tripakis, and S. Yovine. A framework for scheduler synthesis. In Proc. Real-Time Systems Symp., pp. 154–163. IEEE Computer Society, 1999.
J.R. Büchi and L.H. Landweber. Solving sequential conditions by finite-state strategies. Trans. AMS, 138:295–311, 1969.
N. Halbwachs. Synchronous Programming of Reactive Systems. Kluwer, 1993.
T.A. Henzinger, B. Horowitz, and C.M. Kirsch. Giotto: a time-triggered language for embedded programming. In Proc. Embedded Software, LNCS 2211, pp. 166–184. Springer, 2001.
T.A. Henzinger and C.M. Kirsch. The embedded machine: predictable, portable real-time code. In Proc. Conf. Programming Languages Design and Implementation, pp. 315–326. ACM, 2002.
C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard-realtime environment. J. A CM, 20:46–61, 1973.
J.W. Thatcher and J.B. Wright. Generalized finite-automata theory with an application to a decision problem in second-order logic. Mathematical Systems Theory, 2:57–81, 1968.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Henzinger, T.A., Kirsch, C.M., Majumdar, R., Matic, S. (2002). Time-Safety Checking for Embedded Programs. In: Sangiovanni-Vincentelli, A., Sifakis, J. (eds) Embedded Software. EMSOFT 2002. Lecture Notes in Computer Science, vol 2491. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45828-X_7
Download citation
DOI: https://doi.org/10.1007/3-540-45828-X_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44307-0
Online ISBN: 978-3-540-45828-9
eBook Packages: Springer Book Archive