Article

Causality analysis of synchronous programs with delayed actions

Authors:

T. SchueleAuthors Info & Claims

CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems

Pages 179 - 189

https://doi.org/10.1145/1023833.1023859

Published: 22 September 2004 Publication History

Abstract

Synchronous programs are well-suited for the implementation of real-time embedded systems. However, their compilation is difficult due to the paradigm that microsteps are executed in zero time. This can yield cyclic dependencies that must be resolved to generate single-threaded code. State of the art techniques are based on a fixpoint computation at compile time that 'simulates' the microstep execution. However, existing procedures do not consider delayed actions that have been recently introduced in synchronous languages. In this paper, we show that the analysis of programs with delayed actions can be performed by two fixpoint computations, one for the initialization and one for the transitions of the system. Moreover, we discuss an implementation using BDDs that is based on dual rail encoding.

References

[1]

BENVENISTE, A., CASPI, P., EDWARDS, S., HALBWACHS, N., LE GUERNIC,P., AND DE SIMONE, R. The synchronous languages twelve years later. Proceedings of the IEEE 91, 1 (2003), 64--83.]]

[2]

BERRY, G. A hardware implementation of pure Esterel. In Workshop on Formal Methods in VLSI Design (Miami, Florida, January 1991).]]

[3]

BERRY, G. The constructive semantics of pure Esterel. http://www-sop.inria.fr/esterel.org, July 1999.]]

[4]

BERRY, G. The Esterel v5_91 language primer, June 2000.]]

[5]

BOUSSINOT, F. SugarCubes implementation of causality. Research Report 3487, Institut National de Recherche en Informatique et en Automatique (INRIA), Sophia Antipolis Cedex (France), September 1998.]]

[6]

BRYANT, R. A switch level model and simulator for MOS digital systems. IEEE Transactions on Computers C-33, 2 (February 1984), 160--177.]]

Digital Library

[7]

BRYANT, R. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers C-35, 8 (August 1986), 677--691.]]

Digital Library

[8]

BRZOZOWSKI, J., AND SEGER, C.-J. Asynchronous Circuits. Springer, 1995.]]

[9]

CIMATTI, A., CLARKE, E., GIUNCHIGLIA, F., AND ROVERI, M. NUSMV: A new symbolic model verifier. In Conference on Computer Aided Verification (CAV) (Trento, Italy, 1999), N. Halbwachs and D. Peled, Eds., vol. 1633 of LNCS, Springer, pp. 495--499.]]

Digital Library

[10]

CLAESSEN, K. Safety property verificationof cyclic synchronous circuits. In Synchronous Languages, Applications, and Programming (SLAP) (Porto, Portugal, 2003), vol. 88 of ENTCS, Elsevier.]]

Digital Library

[11]

CLOSSE, E., POIZE, M., PULOU, J., VENIER,P.,AND WEIL, D. SAXO-RT: Interpreting Esterel semantic on a sequential execution structure. In Synchronous Languages, Applications, and Programming (SLAP) (Grenoble, France, 2002), vol. 65 of ENTCS, Elsevier.]]

[12]

EDWARDS, S. Compiling concurrent languages for sequential processors. ACM Transactions on Design Automation of Electronic Systems (TODAES) 8, 2 (2003), 141--187.]]

Digital Library

[13]

EDWARDS, S. Making cyclic circuits acyclic. In Design Automation Conference (DAC) (2003), ACM.]]

Digital Library

[14]

ESTEREL TECHNOLOGY. Website. http://www.esterel-technologies.com.]]

[15]

HALBWACHS, N. Synchronous programming of reactive systems. Kluwer, 1993.]]

Digital Library

[16]

HAREL, D., AND NAAMAD, A. The STATEMATE semantics of statecharts. ACM Transactions on Software Engenieering Methods 5, 4 (1996), 293--333.]]

Digital Library

[17]

HOWARD,W.To H.B. Curry: Essays on Combinatory Logic, Lambda-Calculus and Formalism. Academic, New York, 1980, ch. The formulas-as-types notion of construction, pp. 479--490.]]

[18]

HUFFMAN, D. Combinational circuits with feedback. In Recent Developments in Switching Theory (1971), A. Mukhopadhyay, Ed., Academic Press, pp. 27--55.]]

[19]

KAUTZ, W. The necessity of closed ciruit loops in minimal combinational circuits. IEEE Transactions on Computers C-19 (February 1970), 162--166.]]

Digital Library

[20]

LI, Y.-T., AND MALIK,S.Performance Analysis of Real-Time Embedded Software. Kluwer, 1999.]]

Digital Library

[21]

LOGOTHETIS, G., AND SCHNEIDER, K. Exact high level WCET analysis of synchronous programs by symbolic state space exploration. In Design, Automation and Test in Europe (DATE) (Munich, Germany, March 2003), IEEE Computer Society, pp. 196--203.]]

Digital Library

[22]

MALIK, S. Analysis of cycle combinational circuits. IEEE Transactions on Computer Aided Design 13, 7 (July 1994), 950--956.]]

Digital Library

[23]

MCMILLAN, K. Cadence SMV. http://www-cad.eecs.berkeley.edu/~kenmcmil, 2000.]]

[24]

NAMJOSHI, K., AND KURSHAN, R. Efficient analysis of cyclic definitions. In Conference on Computer Aided Verification (CAV) (Trento, Italy, 1999), N. Halbwachs and D. Peled, Eds., vol. 1633 of LNCS, Springer, pp. 394--405.]]

Digital Library

[25]

RIEDEL, M., AND BRUCK, J. Cyclic combinational circuits: Analysis for synthesis. In International Workshop on Logic and Synthesis (IWLS) (Laguna Beach, California, 2003).]]

[26]

RIEDEL, M., AND BRUCK, J. The synthesis of cyclic combinational circuits. In Design Automation Conference (DAC) (2003), ACM.]]

Digital Library

[27]

RIVEST, R. The necessity of feedback in minimal monotone combinational circuits. IEEE Transactions on Computers C-26, 6 (1977), 606--607.]]

Digital Library

[28]

ROCHETEAU,F.,AND HALBWACHS, N. Pollux, a Lustre-based hardware design environment. In Conference on Algorithms and Parallel VLSI Architectures II (Chateau de Bonas, 1991), P. Quinton and Y. Robert, Eds.]]

Digital Library

[29]

SCHNEIDER, K. A verified hardware synthesis for Esterel. In Workshop on Distributed and Parallel Embedded Systems (DIPES) (SchloB Ehringerfeld, Germany, 2000), F. Rammig, Ed., Kluwer, pp. 205--214.]]

Digital Library

Cited By

El-Zawawy M(2015)A Robust Framework for Asynchronous Operations on a Functional Object-Oriented Model2015 International Conference on Cloud Computing (ICCC)10.1109/CLOUDCOMP.2015.7149623(1-6)Online publication date: Apr-2015
https://doi.org/10.1109/CLOUDCOMP.2015.7149623
Aguado JMendler MHanxleden RFuhrmann I(2015)Denotational fixed-point semantics for constructive scheduling of synchronous concurrencyActa Informatica10.1007/s00236-015-0238-x52:4-5(393-442)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s00236-015-0238-x
Bai YSchneider KFettweis GNebel W(2014)Isochronous networks by constructionProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616797(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616797
Show More Cited By

Index Terms

Causality analysis of synchronous programs with delayed actions
1. Hardware
  1. Integrated circuits
    1. Logic circuits
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

Towards a simple and safe Objective Caml compiling framework for the synchronous language SIGNAL

This paper presents a simple and safe compiler, called MinSIGNAL, from a subset of the synchronous dataflow language SIGNAL to C, as well as its existing enhancements. The compiler follows a modular architecture, and can be seen as a sequence of source-...
Clock-directed modular code generation for synchronous data-flow languages
LCTES '08

The compilation of synchronous block diagrams into sequential imperative code has been addressed in the early eighties and can now be considered as folklore. However, separate, or modular, code generation, though largely used in existing compilers and ...
Times Square --- Marriage of Real-Time and Logical-Time in GALS and Synchronous Languages

In this paper we introduce exact and non-exact real-time waits in the reactive Globally Asynchronous Locally Synchronous (GALS) programming languages and synchronous languages as their subset. The language constructs that allow use of real-time waits ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems

September 2004

324 pages

ISBN:1581138903

DOI:10.1145/1023833

General Chairs:
Mary Jane Irwin
Pennsylvania State University
,
Wei Zhao
Texas Instruments
,
Program Chairs:
Luciano Lavagno
Politecnico di Torino/Cadence Labs
,
Scott Mahlke
University of Michigan, Ann Arbor, MI

Copyright © 2004 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: 22 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CASES04

Sponsor:

CASES04: 2004 International Conference on Compilers, Architectures and Synthesis for Embedded Systems

September 22 - 25, 2004

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
272
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

El-Zawawy M(2015)A Robust Framework for Asynchronous Operations on a Functional Object-Oriented Model2015 International Conference on Cloud Computing (ICCC)10.1109/CLOUDCOMP.2015.7149623(1-6)Online publication date: Apr-2015
https://doi.org/10.1109/CLOUDCOMP.2015.7149623
Aguado JMendler MHanxleden RFuhrmann I(2015)Denotational fixed-point semantics for constructive scheduling of synchronous concurrencyActa Informatica10.1007/s00236-015-0238-x52:4-5(393-442)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s00236-015-0238-x
Bai YSchneider KFettweis GNebel W(2014)Isochronous networks by constructionProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616797(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616797
Brandt JSchneider KBai Y(2014)Passive code in synchronous programsACM Transactions on Embedded Computing Systems10.1145/2544375.254438713:2s(1-25)Online publication date: 27-Jan-2014
https://dl.acm.org/doi/10.1145/2544375.2544387
Aguado JMendler MHanxleden RFuhrmann I(2014)Grounding Synchronous Deterministic Concurrency in Sequential ProgrammingProceedings of the 23rd European Symposium on Programming Languages and Systems - Volume 841010.1007/978-3-642-54833-8_13(229-248)Online publication date: 5-Apr-2014
https://dl.acm.org/doi/10.1007/978-3-642-54833-8_13
(2013)Translating synchronous guarded actions to interleaved guarded actionsProceedings of the Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign10.5555/3041405.3041499(167-176)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.5555/3041405.3041499
Gemünde MBrandt JSchneider K(2013)Clock refinement in imperative synchronous languagesEURASIP Journal on Embedded Systems10.1186/1687-3963-2013-32013:1Online publication date: 10-Apr-2013
https://doi.org/10.1186/1687-3963-2013-3
Brandt JGemunde MSchneider KShukla STalpin J(2013)Embedding Polychrony into SynchronyIEEE Transactions on Software Engineering10.1109/TSE.2012.8539:7(917-929)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1109/TSE.2012.85
Gaffe DRessouche A(2013)Algebraic Framework for Synchronous Language SemanticsProceedings of the 2013 International Symposium on Theoretical Aspects of Software Engineering10.1109/TASE.2013.15(51-58)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1109/TASE.2013.15
Talpin JBrandt JGemünde MSchneider KShukla S(2013)Constructive Polychronous SystemsLogical Foundations of Computer Science10.1007/978-3-642-35722-0_24(335-349)Online publication date: 2013
https://doi.org/10.1007/978-3-642-35722-0_24
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents