Synchronous Languages
Lecture Notes
Real-Time and Embedded Systems Group
Wintersemester 2013
Lecturer: Reinhard v. Hanxleden
The slides+notes version is 4-up, includes notes, and uses a
printer-friendly coloring scheme. To save paper, empty
notes are eliminated, except when they are necessary to place
subsequent (non-empty) notes below the slide to which they belong.
The slides version of the lectures is as shown in class, without
animation (only one page per slide).
The animated version of the lectures is as shown in class,
including animation (may be multiple pages per slide).
The bottom of this page contains further notes.
- Lecture 1, 28 October 2013: Introduction
(posted 28 Okt 2013, 18:03 hrs
)
- Lecture 2, 31 October 2013: Esterel I - Overview
(posted 11 Nov 2013, 18:04 hrs
)
- Lecture 3, 11 November 2013: Esterel II - Pragmatics
(posted 11 Nov 2013, 18:01 hrs
)
- Lecture 4, 14 November 2013: Esterel III - The Logical Semantics
(posted 14 Nov 2013, 17:54 hrs
)
- Lecture 5, 18 November 2013: Esterel IV - The Constructive Semantics
(posted 28 Nov 2013, 11:08 hrs
)
- Lecture 6, 2 December 2013: Esterel V - The Constructive Circuit Semantics
(posted 02 Dez 2013, 15:31 hrs
)
- Lecture 7, 5 Dec 2013: Schizophrenia Problems
(posted 02 Dez 2013, 15:32 hrs
)
- Lecture 8, 12 December 2013: Esterel Compilation
(posted 16 Dez 2013, 10:56 hrs
)
- Lecture 9, 16 December 2013: Analysing Constructiveness
(posted 09 Jan 2014, 13:16 hrs
)
- Lecture 10, 12 December 2013: SyncCharts
(posted 09 Jan 2014, 13:16 hrs
)
- Lecture 20, 13 January 2013: SCCharts - Sequentially Constructive Statecharts for Safety-Critical Applications
(posted 31 Jan 2014, 9:00 hrs
)
- Lecture 21, 16 January 2013: Code Generation for Sequential Constructiveness
(posted 31 Jan 2014, 9:02 hrs
)
- Lecture 22, 23 January 2014: Sequentially Constructive Concurrency
(posted 31 Jan 2014, 9:02 hrs
)
- Lecture 23, 27 January 2014: Sequentially Constructive Concurrency II
(posted 04 Feb 2014, 16:32 hrs
)
- Lecture 24a, 3 Feburary 2013: Choosing Your Thesis Topic
(posted 06 Feb 2014, 11:51 hrs
)
- Lecture 24, 3 February 2013: Current/Future Work
(posted 06 Feb 2014, 11:49 hrs
)
- Lecture 25, February 6, 2014: Pragmatics and Graph Drawing
(posted 06 Feb 2014, 11:47 hrs
)
- About this Class
- About this class and related classes
- Practicalities
- Literature
- Introduction to System Design
- Embedded and reactive systems
- Advanced design languages
- Main Concepts
- Introduction
- Signals and Synchrony
- The multiform notion of time
- A Preview of Esterel
- A Tour through Esterel
- The ABRO Example
- The SPEED Example, Signals and Variables
- Weak and Strong Abortion
- Modules
- Further Esterel Statements
- Further Basic Statements
- Process Suspension
- Variants of Discussed Statements, Trap vs. Abort
- Host Language
- The Kernel Language
- To Go Further
- G'erard Berry, The Foundations of Esterel, Proof, Language and Interaction: Essays in Honour of Robin Milner, G. Plotkin, C. Stirling and M. Tofte, editors, MIT Press, Foundations of Computing Series, 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6221
- G'erard Berry, The Esterel v5 Language Primer, Version v5_91, 2000 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.8212
- Examples
- People Counter Example
- Vending Machine Example
- Tail Lights Example
- Traffic-Light Controller Example
- Interfacing with the Environment
- Available Alternatives
- Handling Inconsistent Outputs
- Events vs. State
- Logical Correctness
- Causality issues
- The logical coherence law
- Logical reactivity and determinism
- Instantaneous Feedback
- The Logical Behavioral Semantics
- Notation and Definitions
- The Basic Broadcasting Calculus
- Transition Rules
- Reactivity and Determinism
- To Go Further
- Gérard Berry, The Constructive Semantics of Pure Esterel, Draft book, current version 3.0, Dec. 2002 http://www-sop.inria.fr/members/Gerard.Berry/Papers/EsterelConstructiveBook.zip
- Gérard Berry, Preemption in Concurrent Systems, In Proceedings FSTTCS 93, Lecture Notes in Computer Science 761, pages 72-93, Springer-Verlag, 1993,http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1557
- The Constructive Semantics
- External Justification vs. Self-Justification
- The Constructive Behavioral Semantics
- The Constructive Operational Semantics
- To Go Further
- Albert Benveniste, Paul Caspi, Stephen A. Edwards, Nicolas Halbwachs, Paul Le Guernic, Robert De Simone, The synchronous languages 12 years later, Proceedings of the IEEE, Jan. 2003 vol. 91, issue 1, pages 64-83, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.1117
- The Circuit Semantics
- Constructive circuits
- The basic circuit translation
- Translating the Esterel kernel
- To Go Further
- Schizophrenia and Reincarnation
- The Problem
- Solving the Reincarnation Problem
- Tardieu and de Simone (2004)
- To Go Further
- G'erard Berry, The Constructive Semantics of Pure Esterel, Draft book, current version 3.0, Dec. 2002, Chapter 12, http://www-sop.inria.fr/members/Gerard.Berry/Papers/EsterelConstructiveBook.zip
- Klaus Schneider and M. Wenz, A New Method for Compiling Schizophrenic Synchronous Programs, CASES 2001, http://es.cs.uni-kl.de/publications/datarsg/ScWe01.pdf
- Oliver Tardieu and Robert de Simone, Curing Schizophrenia by Program Rewriting in Esterel, MEMOCODE 2004 http://www1.cs.columbia.edu/~tardieu/papers/memocode04.pdf
- Esterel Compilation
- Automata-Based Compilation
- Netlist-Based Compilation
- Control-Flow Graph-Based Compilation
- Experimental Comparison
- To Go Further
- Stephen A. Edwards. Tutorial: Compiling Concurrent Languages for Sequential Processors. ACM Transactions on Design Automation of Electronic Systems (TODAES), 8(2):141-187, April 2003. http://www1.cs.columbia.edu/~sedwards/papers/edwards2003compiling.pdf
- Stephen A. Edwards and Jia Zeng. Code Generation in the Columbia Esterel Compiler. EURASIP Journal on Embedded Systems, vol. 2007, Article ID 52651, 31 pages, 2007. http://dx.doi.org/10.1155/2007/52651
- Dumitru Potop-Butucaru, Stephen A. Edwards, and Gérard Berry. Compiling Esterel. Springer-Verlag, New York, 2007. ISBN 9780387706269
- Jan Lukoschus and Reinhard von Hanxleden.Removing Cycles in Esterel Programs.EURASIP Journal on Embedded Systems, Special Issue on Synchronous Paradigms in Embedded Systems.http://www.hindawi.com/getarticle.aspx?doi=10.1155/2007/48979, 2007.
- Introduction
- Motivation
- Logic circuits
- Well-behaved Cyclic Circuits
- Constructive Circuits
- Analysis of Circuits without Latches
- Breaking Circuit Cycles
- Three-Valued Logic
- Malik's Procedure
- Shiple et al.
- Analysis of Circuits with Latches
- Latches
- Constructiveness Algorithm
- Application to Esterel
- Quick Conservative Causality Analysis
- To Go Further
- Francois Bourdoncle,Efficient chaotic iteration strategies with widenings,In em Formal Methods in Programming and Their Applications: International Conference Proceedings, volume 735 of em Lecture Notes in Computer Science. Springer, June 1993.
- Sharad Malik,Analysis of cyclic combinational circuits,em IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(7):950-956, July 1994.
- Thomas R. Shiple, Ga'erard Berry, and Herva'e Touati,Constructive Analysis of Cyclic Circuits,In em Proc. International Design and Test Conference ITDC 98, Paris, France, March1996.ftp://ftp-sop.inria.fr/meije/esterel/papers/ConstructiveAnalysis.pdf
- K. Schneider and J. Brandt and T. Schuele,Causality Analysis of Synchronous Programs with Delayed Actions,Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES),179-189, Sept. 2004.http://rsg.informatik.uni-kl.de/publications/data/ScBS04b.pdf
- Ellen M. Sentovich,Quick conservative causality analysis,In em ISSS '97: Proceedings of the 10th International Symposium on System Synthesis, pages 2-8, Washington, DC, USA, 1997. IEEE Computer Society.
- SyncCharts (Safe State Machines)
- Comparison with Harel's Statecharts
- Simple Automata, Hierarchy, Concurrency/Parallelism
- A Tour of SyncCharts
- From Esterel to SyncCharts
- Step 1: Transform Esterel to SyncChart
- Step 2: Reduce to Fully Graphical SyncChart
- Step 3: Optimizations
- From SyncCharts to Esterel
- Examples
- Structural Translation
- Ordering States
- Motivation
- Contribution
- Overview
- SCCharts Overview
- Overview
- Features
- Core Transformations
- Extended SCCharts $rightarrow$ Core SCCharts
- Connector
- Signal
- Strong Abort
- Normalizing Core SCCharts & Implementation
- Compilation / Normalization
- Modelling SCharts
- Conclusion
- To Go Further
- SCG Mapping & Dependency Analysis
- Compilation Overview
- The SC Graph
- Map to SC Graph
- Dependency Analysis
- Code Generation Approaches
- Circuit-based Approach
- Priority-based Approach
- Approach Comparison
- SCCharts Benefits
- To Go Further
- Motivation
- C, Java vs. Synchronous Programming
- Example
- A Sequentially Constructive Program
- Sequential Constructiveness (SC)
- Sequentially Constructive Schedulability
- Concurrent Variable Accesses
- Sequential Admissibility
- Analyzing SC
- Conservative Static Approximation
- Acyclic Sequential Constructiveness (ASC)
- Conclusion
- To Go Further
- Static Concepts
- The SC Language (SCL) and the SC Graph (SCG)
- Thread Terminology
- Thread / Statement Reincarnation
- Run-Time Concepts
- Micro/Macroticks, Runs, Traces
- Free Scheduling
- Confluence
- Sequential Constructiveness
- Scheduling Relations
- Sequential Admissibility
- SC-admissibility vs. Determinism
- To Go Further
- Choosing Your Thesis Topic
- The Employer's View
- Schizophrenic Signals
- Schizophrenic Synchronizers
- An Alternative Definition of SC
- Pragmatics
- Observations
- Textual vs.@ Graphical
- Pragmatics
- Graph Drawing
- Layer-Based
- Force-Based
- Planarity-Based
- Master Theses
- Layering Algorithms
- Routing Splines
- Compound Graphs
- Port Constraints
- Hybrid Graph Drawing
- To Go Further
- The notes here are typically posted right before or after
class. If you are curious about the whole curriculum of this class,
you can have a look at the lecture notes from the last
time this class was held.
- The lecture notes are generated with LaTeX and the beamer
class. The process of generating the various PDFs and the
following HTML overview and of uploading everything to the web server
is largely automated - which is convenient, but makes it easy to
overlook things that have gone wrong in the process. Hence, if
something appears to have gone wrong, please drop a note to Reinhard v. Hanxleden.