skip to main content
article

Polychronous design of embedded real-time applications

Published: 01 April 2007 Publication History

Abstract

Embedded real-time systems consist of hardware and software that controls the behavior of a device or plant. They are ubiquitous in today's technological landscape and found in domains such as telecommunications, nuclear power, avionics, and medical technology. These systems are difficult to design and build because they must satisfy both functional and timing requirements to work correctly in their intended environment. Furthermore, embedded systems are often critical systems, where failure can lead to loss of life, loss of mission, or serious financial consequences. Because of the difficulty in creating these systems and the consequences of failure, they require rigorous and reliable design approaches. The synchronous approach is one possible answer to this demand. Its mathematical basis provides formal concepts that favor the trusted design of embedded real-time systems. The multiclock or polychronous model stands out from other synchronous specification models by its capability to enable the design of systems where each component holds its own activation clock as well as single-clocked systems in a uniform way. A great advantage is its convenience for component-based design approaches that enable modular development of increasingly complex modern systems. The expressiveness of its underlying semantics allows dealing with several issues of real-time design. This article exposes insights gained during recent years from the design of real-time applications within the polychronous framework. In particular, it shows promising results about the design of applications from the avionics domain.

References

[1]
AADL Coordination Commitee. 2002. Avionics architecture description language. In AADL Seminar (Toulouse, France). Society of Automotive Engineers.
[2]
Airlines Electronic Engineering Committee. 1997a. ARINC report 651-1: Design guidance for integrated modular avionics. Tech. Rep. 651, Aeronautical Radio, Inc., Annapolis, Maryland. November.
[3]
Airlines Electronic Engineering Committee. 1997b. ARINC specification 653: Avionics application software standard interface. Tech. Rep. 653, Aeronautical Radio, Inc., Annapolis, Maryland. January.
[4]
Alur, R., Dang, T., Esposito, J., Hur, Y., Ivancic, F., Kumar, V., Lee, I., Mishra, P., Pappas, G., and Sokolsky, O. 2003. Hierarchical modeling and analysis of embedded systems. IEEE Press 91, 1, 11--28.
[5]
Amagbegnon, T., Besnard, L., and Le Guernic, P. 1994. Arborescent canonical form of Boolean expressions. Tech. Rep. 2290, INRIA. June. www.inria.fr/rrrt/rr-2290.html.
[6]
Amagbegnon, T., Besnard, L., and Le Guernic, P. 1995. Implementation of the data-flow synchronous language Signal. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM Press, New York. 163--173.
[7]
Arvind and Gostelow, K. 1978. Some Relationships Between Asynchronous Interpreters of a Dataflow Language. North-Holland, New York.
[8]
Audsley, N. and Wellings, A. 1996. Analysing APEX applications. In Real Time Systems Symposium (RTSS) (Washington, DC). IEEE Press.
[9]
Benveniste, A. 1998. Safety critical embedded systems design: The SACRES approach. In School on Formal Techniques in Real Time and Fault Tolerant Systems 1998: Material for the School. Technical University of Denmark, Lyngby, Denmark.
[10]
Benveniste, A., Caspi, P., Edwards, S., Halbwachs, N., Le Guernic, P., and de Simone, R. 2003. The synchronous languages twelve years later. Proc. IEEE 91, 1 (Jan.), 64--83.
[11]
Benveniste, A., Caspi, P., Le Guernic, P., Marchand, H., Talpin, J., and Tripakis, S. 2002. A protocol for loosely time-triggered architectures. In Proceedings of the 2nd International Conference on Embedded Software (EMSOFT) (London). Springer Verlag. 252--265.
[12]
Benveniste, A. and Le Guernic, P. 1990. Hybrid dynamical systems theory and the signal language. IEEE Trans. Autom. Control 35, 5 (May), 535--546.
[13]
Berry, G. and Sentovich, E. 1998. Embedding synchronous circuits in GALS-based systems. In Sophia-Antipolis Conference on Micro-Electronics (SAME). Sophia Antipolis MicroElectronics, Sophia-Antipolis, France.
[14]
Berthomieu, B., Ribet, P.-O., Vernadat, F., Bernartt, J. L., Farines, J.-M., Bodeveix, J.-P., Filali, M., Padiou, G., Michel, P., Farail, P., Gauffilet, P., Dissaux, P., and Lambert, J.-L. 2003. Towards the verification of real-time systems in avionics: The Cotre approach. Electron. Not. Theor. Comput. Sci. 80, 1--16.
[15]
Bodin, F. and Puaut, I. 2005. A WCET-oriented static branch prediction scheme for real time systems. In Proceedings of the 17th Euromicro Conference on Real Time Systems (ECRTS). 33--40.
[16]
Camus, J.-L. and Dion, B. 2003. Efficient development of airborne software with Scade suite. Tech. Rep., Esterel Technologies. www.esterel-technologies.com.
[17]
Caspi, P. 2001. Embedded control: From asynchrony to synchrony and back. In Proceedings of the 1st International Workshop on Embedded Software (EMSOFT) (Lake Tahoe, CA), Th. A. Henzinger and Ch. M. Kirsch, Eds. Lecture Notes in Computer Science, vol. 2211, Springer Verlag.
[18]
Closse, E., Poize, M., Pulou, J., Sifakis, J., Venier, P., Weil, D., and Yovine, S. 2001. Taxys: A tool for the development and verification of real-time embedded systems. In Proceedings of the Computer Aided Verification (CAV) (London). Springer Verlag.
[19]
Conmy, P. and McDermid, J. 2001. High level failure analysis for integrated modular avionics. In Proceedings of the 6th Australian Workshop on Safety Critical Systems and Software (SCS). Australian Computer Society, Darlinghurst Australia. 13--21.
[20]
Daws, C. and Yovine, S. 1995. Two examples of verification of multirate timed automata with Kronos. In Proceedings of the 16th IEEE Real Time Systems Symposium (RTSS) (Pisa, Italy). IEEE Press.
[21]
Dennis, J. B., Fossen, J. B., and Linderman, J. P. 1974. Data flow schemas. In Proceedings of the International Symposium on Theoretical Programming (London, UK), A. Ershov and V. A. Nepomniaschy, Eds. Lecture Notes in Computer Science, vol. 5, Springer Verlag. 187--216.
[22]
Di Vito, B. 1999. A model of cooperative noninterference for integrated modular avionics. In Proceedings of the Conference on Dependable Computing for Critical Applications (DCCA) (Washington, DC). IEEE Computer Society. 269.
[23]
ESPRESSO-IRISA. 2006. The Polychrony website. www.irisa.fr/espresso/Polychrony.
[24]
Gamatié, A. and Gautier, T. 2002. Synchronous modeling of modular avionics architectures using the Signal language. Tech. Rep. 4678, INRIA. December. www.inria.fr/rrrt/rr-4678.html.
[25]
Gamatié, A. and Gautier, T. 2003a. The signal approach to the design of system architectures. In Proceedings of the 10th IEEE International Conference and Workshop on the Engineering of Computer Based Systems (ECBS). 80.
[26]
Gamatié, A. and Gautier, T. 2003b. Synchronous modeling of avionics applications using the Signal language. In 9th IEEE Real-Time/Embedded Technology and Applications Symposium. IEEE Computer Society, Los Alamitos, CA.
[27]
Gamatié, A., Gautier, T., and Le Guernic, P. 2004. An example of synchronous design of embedded real-time systems based on IMA. In Proceedings of the 10th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA) (Gothenburg, Sweden). Lecture Notes in Computer Science. Springer Verlag.
[28]
Gautier, T. and Le Guernic, P. 1999. Code generation in the Sacres project. In Safety-Critical Systems Symposium (SSS) (Huntington, UK), F. Redmill and T. Anderson, Ed. Springer Verlag.
[29]
Grandpierre, T. and Sorel, Y. 2003. From algorithm and architecture specifications to automatic generation of distributed real-time executives: A seamless flow of graphs transformations. In Formal Methods and Models for Codesign Conference (MEMOCODE). IEEE Computer Society, Los Alamitos, CA.
[30]
Halbwachs, N. and Baghdadi, S. 2002. Synchronous modelling of asynchronous systems. In Proceedings of the Conference on Embedded Software (EMSOFT) (Grenoble, France), J. Sifakis and A. Sangiovanni-Vincentelli, Eds. Lecture Notes in Computer Science, vol. 2491, Springer Verlag. 240--251.
[31]
Halbwachs, N., Lagnier, F., and Raymond, P. 1993. Synchronous observers and the verification of reactive systems. In Algebraic Methodology and Software Technology. Springer Verlag, 1994, ISBN 3-540-19852-0, Enschede, The Netherlands. 83--96.
[32]
Hatcliff, J., Deng, W., Dwyer, M., Jung, G., and Prasad Ranganath, V. 2003. Cadena: An integrated development, analysis, and verification environment for component-based systems. In Proceedings of the 25th International Conference on Software Engineering (ICSE) (Washington, DC). IEEE Computer Society. 160--173.
[33]
Henzinger, T., Horowitz, B., and Kirsch, C. 2001. Embedded control systems development with Giotto. In Proceedings of the ACM SIGPLAN Workshop on Optimization of Middleware and Distributed Systems. ACM Press, New York. 64--72.
[34]
Kahn, G. 1974. The semantics of a simple language for parallel programming. In Information Processing, vol. 74, J. L. Rosenfeld, Ed. North-Holland, New York. 471--475.
[35]
Kountouris, A. 1998. Outils pour la validation temporelle et l'optimisation de programmes synchrones. Ph.D. thesis, Université de Rennes I, Rennes, France.
[36]
Kountouris, A. and Le Guernic, P. 1996. Profiling of Signal programs and its application in the timing evaluation of design implementations. In IEE Colloquium on Hardware-Software Cosynthesis for Reconfigurable Systems. (Jun. 1--9), Bristol, UK.
[37]
Le Guernic, P., Talpin, J.-P., and Le Lann, J.-C. 2003. Polychrony for system design. J. Circ. Syst. Comput. 12, 3 (Apr.), 261--304.
[38]
Lee, E. 2000. What's ahead for embedded software? IEEE Comput. Mag. 33, 9 (Sept.), 18--26.
[39]
Lee, E. 2001. Overview of the Ptolemy project. Tech. Rep. UBC/ERL M01/11, University of California, Berkeley. March.
[40]
Lee, Y.-H., Kim, D., Younis, M., Zhou, J., and McElroy, J. 2000. Resource scheduling in dependable integrated modular avionics. In Proceedings of the International Conference on Dependable Systems and Networks (DSN) (Washington, DC). IEEE Computer Society. 14--23.
[41]
Marchand, H., Bournai, P., Le Borgne, M., and Le Guernic, P. 2000. Synthesis of discrete-event controllers based on the Signal environment. Discrete Event Dynam. Syst. Theory Appl. 10, 4 (Oct.), 325--346.
[42]
Pnueli, A. 2002. Embedded systems: Challenges in specification and verification. In Proceedings of the 2nd International Conference on Embedded Software (EMSOFT) (Grenoble, France), J. Sifakis and A. Sangiovanni-Vincentelli, Eds. Lecture Notes in Computer Science, vol. 2491. Springer Verlag. 252--265.
[43]
Puaut, I. and Decotigny, D. 2002. Low-Complexity algorithms for static cache locking in multitasking hard real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS) (Washington, DC). IEEE Computer Society. 114.
[44]
Puschner, P. and Burns, A. 2000. A review of worst-case execution-time analysis. J. Real-Time Syst. 18, 2-3 (May), 115--128.
[45]
Romberg, J. 2002. Model-Based deployment with autofocus: A first cut. In Proceedings of the 14th Euromicro Conference on Real Time Systems (ECRTS) (Work in Progress session). IEEE Computer Society, Los Alamitos, CA. 41--44.
[46]
Rushby, J. 1999. Partitioning in avionics architectures: Requirements, mechanisms, and assurance. Tech. Rep. CR-1999-209347, NASA Langley Research Center. June. www.csl.sri.com/users/rushby/partitioning.html.
[47]
Sacres Consortium. 1997. The semantic foundations of Sacres. Tech. Rep. EP 20897, Esprit Project EP. March.
[48]
Sánchez-Puebla, M. and Carretero, J. 2003. A new approach for distributed computing in avionics systems. In Proceedings of the 1st International Symposium on Information and Communication Technologies (ISICT) (Dublin, Ireland). 579--584.
[49]
Sharp, D. and Roll, W. 2003. Model-Based integration of reusable component-based avionics systems. In Workshop on Model-Driven Embedded Systems in RTAS. IEEE Computer Society, Los Alamitos, CA.
[50]
Sifakis, J. 2001. Modeling real-time systems---Challenges and work directions. In Proceedings of the 1st International Workshop on Embedded Software (EMSOFT) (London). Springer Verlag.
[51]
Stankovic, J., Zhu, R., Poornalingam, R., Lu, C., Yu, Z., Humphrey, M., and Ellis, B. 2003. Vest: An aspect-based composition tool for real-time systems. In Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) (Washington, DC). IEEE Computer Society. 58.
[52]
Talpin, J.-P., Gamatié, A., Berner, D., Le Dez, B., and Le Guernic, P. 2003. Hard real-time implementation of embedded systems in Java. In Proceedings of the International Workshop on Scientific Engineering of Distributed JAVA Applications (Berlin). Springer Verlag. 33--47.
[53]
Vestal, S. 1997. MetaH support for real-time multi-processor avionics. In Workshop on Parallel and Distributed Real-Time Systems. IEEE Computer Society, Los Alamitos, CA.
[54]
Wadge, W. W. 1979. An extensional treatment of dataflow deadlock. In Semantics of Concurrent Computation, G. Kahn, Ed. Lecture Notes in Computer Science, vol. 70, Springer Verlag. 285--299.
[55]
Wirth, N. 2001. Embedded systems and real-time programming. In Proceedings of the 1st International Workshop on Embedded Software (EMSOFT) (Tahoe City, CA), Th. A. Henzinger and Ch. M. Kirsch, Eds. Lecture Notes in Computer Science, vol. 2211. Springer Verlag. 486--492.

Cited By

View all
  • (2024)Specification and Verification of Multi-Clock Systems Using a Temporal Logic with Clock ConstraintsFormal Aspects of Computing10.1145/367079436:2(1-51)Online publication date: 8-Jun-2024
  • (2024)A hovering swarm particle swarm optimization algorithm based on node resource attributes for hardware/software partitioningThe Journal of Supercomputing10.1007/s11227-023-05603-780:4(4625-4647)Online publication date: 1-Mar-2024
  • (2021)The w-calculus: a synchronous framework for the verified modelling of digital signal processing algorithmsProceedings of the 9th ACM SIGPLAN International Workshop on Functional Art, Music, Modelling, and Design10.1145/3471872.3472970(35-46)Online publication date: 27-Aug-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology
ACM Transactions on Software Engineering and Methodology  Volume 16, Issue 2
April 2007
117 pages
ISSN:1049-331X
EISSN:1557-7392
DOI:10.1145/1217295
Issue’s Table of Contents
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 April 2007
Published in TOSEM Volume 16, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Avionics
  2. IMA
  3. Signal
  4. Synchronous approach

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2024)Specification and Verification of Multi-Clock Systems Using a Temporal Logic with Clock ConstraintsFormal Aspects of Computing10.1145/367079436:2(1-51)Online publication date: 8-Jun-2024
  • (2024)A hovering swarm particle swarm optimization algorithm based on node resource attributes for hardware/software partitioningThe Journal of Supercomputing10.1007/s11227-023-05603-780:4(4625-4647)Online publication date: 1-Mar-2024
  • (2021)The w-calculus: a synchronous framework for the verified modelling of digital signal processing algorithmsProceedings of the 9th ACM SIGPLAN International Workshop on Functional Art, Music, Modelling, and Design10.1145/3471872.3472970(35-46)Online publication date: 27-Aug-2021
  • (2017)Quartz: A Synchronous Language for Model-Based Design of Reactive Embedded SystemsHandbook of Hardware/Software Codesign10.1007/978-94-017-7358-4_3-1(1-30)Online publication date: 21-Apr-2017
  • (2017)Quartz: A Synchronous Language for Model-Based Design of Reactive Embedded SystemsHandbook of Hardware/Software Codesign10.1007/978-94-017-7267-9_3(29-58)Online publication date: 27-Sep-2017
  • (2016)Towards a verified compiler prototype for the synchronous language SIGNALFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-015-4364-y10:1(37-53)Online publication date: 1-Feb-2016
  • (2015)The challenge of interoperabilityProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2747945(1-6)Online publication date: 7-Jun-2015
  • (2014)Constructive polychronous systemsScience of Computer Programming10.1016/j.scico.2014.04.00996:P3(377-394)Online publication date: 15-Dec-2014
  • (2014)Representation of synchronous, asynchronous, and polychronous components by clocked guarded actionsDesign Automation for Embedded Systems10.1007/s10617-012-9087-918:1-2(63-97)Online publication date: 1-Mar-2014
  • (2013)Embedding Polychrony into SynchronyIEEE Transactions on Software Engineering10.1109/TSE.2012.8539:7(917-929)Online publication date: 1-Jul-2013
  • 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