The SCCharts language, first publicly presented 2013 at Dagstuhl Seminar 13471 on Synchronous Programming and subsequently at PLDI’14, originated from a collaboration with an industrial partner, National Instruments (NI), as well as other academic researchers, notably Michael Mendler (U Bamberg) and Partha Roop (U Auckland). Simply put, the task put forward by NI was to develop a graphical, Statecharts-like language for hardware synthesis, with a ”clean” semantics. The synchronous model of computation, as embodied in several textual and graphical languages, seemed attractive due to its solid foundation, including deterministic concurrency. However, the policy for shared variable accesses in classical synchronous programming, possibly leading to hard-to-track ”causality errors” at compile time, was seen as rather restrictive.

Abstract In Model-Driven Engineering, editing models is typically not merely a purely textual endeavor, but rather a mix between textual and graphical editors and views. Both have their advantages and use cases where either textual or diagrammatic representations are better suited to edit and understand models. Therefore, a modeling framework offering the best of both worlds can be advantageous. We define the text-first approach to combine the textual and diagrammatic representations by automatically synthesizing the textual model into a diagram. We present the KIELER text-first diagramming framework and its take on current challenges for model visualization and compare it to the diagram-first approach, as exemplified by the GLSP framework.

We introduce a systematic approach for automatically creating a visual diagram, akin to the graphical Safety Critical Application Development Environment (SCADE) model, from a Lustre program. This not only saves tedious manual drawing effort but also enables modeling software to automatically provide the developer with different meaningful views for the same program. We also extend the Sequentially Constructive Charts (SCCharts) language with data-flow constructs that adhere to the Lustre semantics, which permits a translation from Lustre to graphical SCCharts. This allows using the SCCharts code generation, simulation, and visualization tooling also for Lustre programs, in addition to the already existing Lustre compilation techniques. Furthermore, we investigate how the sequentially constructive model of computation, used in SCCharts and other synchronous languages, can be used to conservatively extend Lustre. We have implemented and validated this work with the Eclipse-based open-source Kiel Integrated Environment for Layout Eclipse Rich Client (KIELER) framework.

Complex software systems often feature distinct modes of operation, each designed to handle a particular scenario that may require the system to respond in a certain way. Breaking down system behavior into mutually exclusive modes and discrete transitions between modes is a commonly used strategy to reduce implementation complexity and promote code readability. The work in this paper aims to bring the advantages of working with modal models to mainstream programming languages, by following the polyglot coordination approach of Lingua Franca (LF), in which verbatim target code (e. g., C, C++, Python, Typescript, or Rust) is encapsulated in composable reactive components called reactors. Reactors can form a dataflow network, are triggered by timed as well as sporadic events, execute concurrently, and can be distributed across nodes on a network. With modal models in LF, we introduce a lean extension to the concept of reactors that enables the coordination of reactive tasks based on modes of operation.

System- Theoretic Process Analysis (STPA) is a relatively new hazard analysis technique. Several tools supporting the STPA process already exist. However, they are mostly textual. In this paper we present a Domain Specific Language (DSL) for STPA with an automatic visualization of the STPA components. This combines the advantages of textual and graphical approaches. The DSL is implemented with open source tooling, realized as a Visual Studio Code Extension using Langium for the language server and Sprotty for the visualization. A comparison suggests that the DSL has potential to be a good alternative to other STPA supporting tools.

Abstract In 2010, Fuhrmann et al. argued for enhancing modeler productivity by providing tooling that, put simply, combines the best of textual and graphical worlds. They referred to this as pragmatics , and argued that a key enabler would be the ability to automatically synthesize customized graphical views from a (possibly textual) model. The model would be the “ground truth” used, for example, for downstream code synthesis and simulation; the graphical views would typically be abstractions from the model serving various purposes, including documentation. Twelve years later, we reflect on their proposal, and illustrate the current state with the recently developed polyglot coordination language Lingua Franca (LF). LF has been designed with pragmatics in mind since early on, and some characteristics of LF make it particularly suited for pragmatics-aware programming and modeling. However, the underlying pragmatic principles are broadly applicable, and by now a set of mature open source tools is available for putting them into practice.

Abstract Graphical actor-based models provide an abstract overview of the flow of data in a system. They are well-established for the model-driven engineering(MDE)of complex software systems and are supported by numerous commercial and academic tools, such as Simulink, LabVIEW or Ptolemy. InMDE, engineers concentrate on constructing and simulating such models, before application code (or at least a large fraction thereof) is synthesized automatically. However, a significant fraction of today’s legacy system has been coded directly, often using the C language. High-level models that give a quick, accurate overview of how components interact are often out of date or do not exist. This makes it challenging to maintain or extend legacy software, in particular for new team members. To address this problem, we here propose to reverse the classic synthesis path ofMDEand to synthesize actor-based dataflow models automatically from source code. Here functions in the code get synthesized into nodes that represent actors manipulating data. Second, we propose to harness themodeling-pragmaticapproach, which considers visual models not as static artefacts, but allows interactive, flexible views that also link back to textual descriptions. Thus we propose to synthesize actor models that can vary in level of detail and that allow navigation in the source code. To validate and evaluate our proposals, we implemented these concepts for C analysis in the open source, Eclipse-basedKIELERproject and conducted a small survey.

Software visualization tools can improve the software development process by providing a graphical overview of source code and enhancing collaboration. We here propose a concept to automatically extract mode diagrams from Blech code, an imperative synchronous programming language for embedded, reactive and safety-critical systems. Our main findings are that the visualization is helpful to understand the stateful nature of the source code and that it can enhance the collaboration between developers. It is also found, however, that a good understanding of the precise diagram semantics meaning of the diagram elements is key. Lastly, the findings indicate that preference on different labeling options is highly subjective.

editorial Free Access Share on Introduction to the Special Issue on Specification and Design Languages (FDL 2019) Authors: Alain Girault Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIGView Profile , Reinhard Von Hanxleden Dept. of Computer Science, Kiel University Dept. of Computer Science, Kiel UniversityView Profile Authors Info & Claims ACM Transactions on Embedded Computing SystemsVolume 20Issue 4July 2021 Article No.: 27pp 1–3https://doi.org/10.1145/3458748Online:29 May 2021Publication History 0citation112DownloadsMetricsTotal Citations0Total Downloads112Last 12 Months112Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteView all FormatsPDF

Synchronous programming languages, such as Esterel, Lustre, SCADE or SCCharts, have been developed for designing reactive systems. They abstract from computation times and assume that outputs are synchronous with their inputs. This leads to a deterministic semantics, without race conditions, which makes synchronous languages particularly suitable for safety-critical systems. However, even though synchronous languages have been designed with real-time applications in mind, the handling of physical time is traditionally left to the execution environment. This makes e. g. the expression of arbitrary timeouts difficult and may lead to excessive “busy waiting” computations. The recent proposal of dynamic ticks alleviates this by making physical time a first-class citizen within the synchronous programming model. In this paper, we explore and demonstrate the practical merits of dynamic ticks, including improved timing accuracy and reduced computational requirements, in the context of Timed SCCharts. As demonstration platform, we present a hardware/software platform that involves two stepper motors whose operation must be synchronized at microsecond accuracy to avoid physical damage.

We introduce a systematic approach for automatically creating a visual diagram, akin to a SCADE model, from a Lustre program. This not only saves tedious manual drawing effort but also allows the creation of different views for the same program. Furthermore, we present an extension of the SCCharts language with data-flow constructs that adhere to the Lustre semantics, which in turn permits a translation from Lustre to graphical SCCharts. This allows to use the SCCharts simulation and code synthesis machinery as an alternative to existing Lustre compilation techniques. Finally, we investigate how the sequentially constructive model of computation underlying SCCharts can be used to conservatively extend Lustre, thus providing a deterministic semantics to some Lustre programs that would be rejected under its original semantics. We have implemented and validated this work with the Eclipse-based open-source KIELER framework.

Big software projects often use architectural frameworks for a consistent structure. OSGi is such a framework to create modular Java applications. The architecture of individual projects, however, is often hidden in configuration files. We propose to visualize projects in a modular framework such as OSGi with an approach to allow users to comprehend the connections within a system. We assist this comprehension using filtering and automatically generated, interactive views of the project. We extend the notion of interactive views with a concept to reproduce configured views for arbitrary system revisions to enhance up-to-date documentation. We have implemented this proposal in the publicly available KIELER project, and have validated it with a large software project in the railway domain.

A key to the synchronous principle of reconciling concurrency with determinism is to establish at compile time that a program is causal, which means that there exists a schedule that obeys the rules put down by the language. In practice it can be rather cumbersome for the developer to cure causality problems. To facilitate causality handling, we propose, first, to enrich the scheduling regime of the language to also consider explicit scheduling directives that can be used by either the modeler or model-to-model transformations. Secondly, we propose to enhance programming environments with dedicated causality views to guide the developer in finding causality issues. Our proposals should be applicable for synchronous languages; we here illustrate them for the SCCharts language and its open source development platform KIELER.

Synchronous Programming ( SP ) is a universal computational principle that provides deterministic concurrency. The same input sequence with the same timing always results in the same externally observable output sequence, even if the internal behaviour generates uncertainty in the scheduling of concurrent memory accesses. Consequently, SP languages have always been strongly founded on mathematical semantics that support formal program analysis. So far, however, communication has been constrained to a set of primitive clock-synchronised shared memory ( csm ) data types, such as data-flow registers, streams and signals with restricted read and write accesses that limit modularity and behavioural abstractions. This paper proposes an extension to the SP theory which retains the advantages of deterministic concurrency, but allows communication to occur at higher levels of abstraction than currently supported by SP data types. Our approach is as follows. To avoid data races, each csm type publishes a policy interface for specifying the admissibility and precedence of its access methods. Each instance of the csm type has to be policy-coherent, meaning it must behave deterministically under its own policy—a natural requirement if the goal is to build deterministic systems that use these types. In a policy-constructive system, all access methods can be scheduled in a policy-conformant way for all the types without deadlocking. In this paper, we show that a policy-constructive program exhibits deterministic concurrency in the sense that all policy-conformant interleavings produce the same input-output behaviour. Policies are conservative and support the csm types existing in current SP languages. Technically, we introduce a kernel SP language that uses arbitrary policy-driven csm types. A big-step fixed-point semantics for this language is developed for which we prove determinism and termination of constructive programs.

Synchronous languages, such as the recently proposed SCCharts language, have been designed for the rigorous specification of real-time systems. Their sound semantics, which builds on an abstraction from physical execution time, make these languages appealing, in particular for safety-critical systems. However, they traditionally lack built-in support for physical time. This makes it rather cumbersome to express things like time-outs or periodic executions within the language. We here propose several mechanisms to reconcile the synchronous paradigm with physical time. Specifically, we propose extensions to the SCCharts language to express clocks and execution periods within the model. We draw on several sources, in particular timed automata, the Clock Constraint Specification Language, and the recently proposed concept of dynamic ticks. We illustrate how these extensions can be mapped to the SCChart language core, with minimal requirements on the run-time system, and we argue that the same concepts could be applied to other synchronous languages such as Esterel, Lustre or SCADE.

Sequence diagrams belong to the most commonly used UML diagrams. There is research on desirable aesthetics, but to our knowledge no layout algorithms have been published. This might be due to the rigid specification of sequence diagrams that seems to make laying them out quite easy. However, as we argue here, naive algorithms do not always produce desirable solutions. We present methods to produce compact layouts which we have implemented in a layout algorithm and evaluate them with 50 real-world sequence diagrams.

The synchronous language Esterel provides determinate concurrency for reactive systems. Determinacy is ensured by the signal coherence rule , which demands that signals have a stable value throughout one reaction cycle. This is natural for the original application domains of Esterel, such as controller design and hardware development; however, it is unnecessarily restrictive for software development. Sequentially Constructive Esterel (SCEst) overcomes this restriction by allowing values to change instantaneously, as long as determinacy is still guaranteed, adopting the recently proposed Sequentially Constructive model of computation. SCEst is grounded in the minimal Sequentially Constructive Language ( scl ), which also provides a novel semantic definition and compilation approach for Esterel.

We address the problem of synchronous programs that cannot be easily executed in a classical time-triggered or event-triggered execution loop. We propose a novel approach, referred to as dynamic ticks, that reconciles the semantic timing abstraction of the synchronous approach with the desire to give the application fine-grained control over its real-time behavior. The main idea is to allow the application to dynamically specify its own wake-up times rather than ceding their control to the environment. As we illustrate in this paper, synchronous languages such as Esterel are already well equipped for this; no language extensions are needed. All that is required is a rather minor adjustment of the way the tick function is called.

Implantable medical devices such as cardiac pacemakers have been recalled frequently with safety related issues. This paper proposes a model driven approach for pacemaker design by combining the strengths of two well-known philosophies for safety critical systems. First, we adopt the SCCharts synchronous language for pacemaker specification. Second, we adopt a PRET architecture for the underlying processor which has been modified to include reactive semantics. PRET processors offer an ideal platform for providing timing guarantees. We use automatic code generation combined with static timing analysis during the design phase. Also, we use an existing emulation model of the human heart using a 33-node conduction network for closed loop validation of the designed pacemaker.

Synchronous programming is a paradigm of choice for the design of safety-critical reactive systems. Runtime enforcement is a technique to ensure that the output of a black-box system satisfies some desired properties. This paper deals with the problem of runtime enforcement in the context of synchronous programs. We propose a framework where an enforcer monitors both the inputs and the outputs of a synchronous program and (minimally) edits erroneous inputs/outputs in order to guarantee that a given property holds. We define enforceability conditions, develop an online enforcement algorithm, and prove its correctness. We also report on an implementation of the algorithm on top of the KIELER framework for the SCCharts synchronous language. Experimental results show that enforcement has minimal execution time overhead, which decreases proportionally with larger benchmarks.

Many implantable medical devices, such as pacemakers, have been recalled due to failure of their embedded software. This motivates rethinking their design and certification processes. We propose, for the first time, an additional layer of safety by formalising the problem of run-time enforcement of implantable pacemakers. While recent work has formalised run-time enforcement of reactive systems, the proposed framework generalises existing work along the following directions: (1) we develop bi-directional enforcement, where the enforced policies depend not only on the status of the pacemaker (the controller) but also of the heart (the plant), thus formalising the run-time enforcement problem for cyber-physical systems (2) we express policies using a variant of discrete timed automata (DTA), which can cover all regular properties unlike earlier frameworks limited to safety properties, (3) we are able to ensure the timing safety of implantable devices through the proposed enforcement, and (4) we show that the DTA-based approach is efficient relative to its dense time variant while ensuring that the discretisation error is relatively small and bounded. The developed approach is validated through a prototype system implemented using the open source KIELER framework. The experiments show that the framework incurs minimal runtime overhead.

Most visual languages are not purely graphical but include textual labels to complete the picture. However, in some languages labels tend to become rather long and thereby enlarge diagrams considerably. Since today's state-of-the-art development tools usually display diagrams in full detail, users must often scroll through the diagram or zoom out until the diagram fits inside the available drawing area, but then ceases to be legible. In this paper, we address this problem by examining ways to dynamically shorten the text of labels to keep the size of a diagram manageable. We introduce a number of label shortening strategies, explain ways to integrate them into diagram generation processes based on automatic layout algorithms, and explain their relation to the established focus and context approach which aims at solving a similar problem. We evaluate our strategies based on the SCChart visual language and an open-source, Eclipse-based modeling environment.

The synchronous language Esterel provides determinate concurrency for reactive systems. Determinacy is ensured by the “signal coherence rule,” which demands that signals have a stable value throughout one reaction cycle. This is natural for the original application domains of Esterel, such as controller design and hardware development; however, it is unnecessarily restrictive for software development. Sequentially Constructive Esterel (SCEst) overcomes this restriction by allowing values to change instantaneously, as long as determinacy is still guaranteed, adopting the recently proposed Sequentially Constructive model of computation. SCEst is grounded in the minimal Sequentially Constructive Language, which also provides a novel semantic definition and compilation approach for Esterel.

We present a new visual language, SCCharts, designed for specifying safety-critical reactive systems. SCCharts use a statechart notation and provide determinate concurrency based on a synchronous model of computation (MoC), without restrictions common to previous synchronous MoCs. Specifically, we lift earlier limitations on sequential accesses to shared variables, by leveraging the sequentially constructive MoC. The semantics and key features of SCCharts are defined by a very small set of elements, the Core SCCharts, consisting of state machines plus fork/join concurrency. We also present a compilation chain that allows efficient synthesis of software and hardware.

Visual languages based on node-link diagrams are widely used for systems modeling. As in textual languages, comments can make diagrams easier to understand. In the absence of an explicit attachment between comments and the diagram elements they relate to, that relationship is usually given implicitly by the manual placement of comments near the related elements. While algorithms for the automatic layout of diagrams can make working with diagrams more effective, they usually fail to preserve implicit attachments by placing comments at arbitrary positions. In this paper, we propose a comment attachment algorithm that extracts implicit attachments and makes them accessible to layout algorithms. We implemented the algorithm in an application for browsing Ptolemy diagrams and achieved success rates, i. e. attachments as intended by the user, of up to 90 %.

Pragmatics-aware modeling refers to model-driven engineering with designer productivity in mind. We apply this concept to traditional software development by introducing two exemplary applications for transient views geared at increasing developer productivity: UML class diagram generation and debug state visualization.

A large class of embedded systems is distinguished from general-purpose computing systems by the need to satisfy strict requirements on timing, often under constraints on available resources. Predictable system design is concerned with the challenge of building systems for which timing requirements can be guaranteed a priori . Perhaps paradoxically, this problem has become more difficult by the introduction of performance-enhancing architectural elements, such as caches, pipelines, and multithreading, which introduce a large degree of uncertainty and make guarantees harder to provide. The intention of this article is to summarize the current state of the art in research concerning how to build predictable yet performant systems. We suggest precise definitions for the concept of “predictability”, and present predictability concerns at different abstraction levels in embedded system design. First, we consider timing predictability of processor instruction sets. Thereafter, we consider how programming languages can be equipped with predictable timing semantics, covering both a language-based approach using the synchronous programming paradigm, as well as an environment that provides timing semantics for a mainstream programming language (in this case C). We present techniques for achieving timing predictability on multicores. Finally, we discuss how to handle predictability at the level of networked embedded systems where randomly occurring errors must be considered.

Synchronous languages ensure determinate concurrency but at the price of restrictions on what programs are considered valid, or constructive . Meanwhile, sequential languages such as C and Java offer an intuitive, familiar programming paradigm but provide no guarantees with regard to determinate concurrency. The sequentially constructive (SC) model of computation (MoC) presented here harnesses the synchronous execution model to achieve determinate concurrency while taking advantage of familiar, convenient programming paradigms from sequential languages. In essence, the SC MoC extends the classical synchronous MoC by allowing variables to be read and written in any order and multiple times, as long as the sequentiality expressed in the program provides sufficient scheduling information to rule out race conditions. This allows to use programming patterns familiar from sequential programming, such as testing and later setting the value of a variable, which are forbidden in the standard synchronous MoC. The SC MoC is a conservative extension in that programs considered constructive in the common synchronous MoC are also SC and retain the same semantics. In this article, we investigate classes of shared variable accesses, define SC-admissible scheduling as a restriction of “free scheduling,” derive the concept of sequential constructiveness, and present a priority-based scheduling algorithm for analyzing and compiling SC programs efficiently.

Synchronous languages ensure deterministic concurrency, but at the price of heavy restrictions on what programs are considered valid, or constructive. Meanwhile, sequential languages such as C and Java offer an intuitive, familiar programming paradigm but provide no guarantees with regard to deterministic concurrency. The sequentially constructive model of computation (SC MoC) presented here harnesses the synchronous execution model to achieve deterministic concurrency while addressing concerns that synchronous languages are unnecessarily restrictive and difficult to adopt. In essence, the SC MoC extends the classical synchronous MoC by allowing variables to be read and written in any order as long as sequentiality expressed in the program provides sufficient scheduling information to rule out race conditions. The SC MoC is a conservative extension in that programs considered constructive in the common synchronous MoC are also SC and retain the same semantics. In this paper, we identify classes of variable accesses, define sequential constructiveness based on the concept of SC-admissible scheduling, and present a priority-based scheduling algorithm for analyzing and compiling SC programs.

A key issue in the development of reliable embedded software is the proper handling of reactive control-flow, which typically involves concurrency. Java and its thread concept have only limited provisions for implementing deterministic concurrency. Thus, as has been observed in the past, it is challenging to develop concurrent Java programs without any deadlocks or race conditions. To alleviate this situation, the Synchronous Java (SJ) approach presented here adopts the key concepts that have been established in the world of synchronous programming for handling reactive control-flow. Thus SJ not only provides deterministic concurrency, but also different variants of deterministic preemption. Furthermore SJ allows concurrent threads to communicate with Esterel-style signals. As a case study for an embedded system usage, we also report on how the SJ concepts have been ported to the ARM-based Lego Mindstorms NXT system.

Node-link-diagrams can effectively communicate information, but their creation and maintenance require a lot of manual effort. Therefore we follow the transient views approach that aims at automatically deriving high quality diagrams from arbitrary models. Besides composing diagram structures, this task involves the arrangement of the diagram elements on the canvas, and, on a finer-grained level of detail, the arrangement of the shapes (rectangles, circles, lines, etc.) that form the diagram elements. We show the feasibility of this approach by means of the Kieler Lightweight Diagrams (KLighD) framework that creates diagrams this way. We discuss our overall design objectives in terms of this framework, investigate an alternative way to shape diagram figures, and briefly demonstrate the usage of KLighD in custom modeling environments by means of a case study.

Automatic layout is a key enabler for pragmatics-aware modeling, which refers to model-driven engineering with designer productivity in mind. This showpiece introduces an infrastructure for the integration of graph layout libraries and their configuration with regard to graphical views of modeling applications.

The Kiel Esterel Processor (KEP) is a multithreaded reactive processor designed for the execution of programs written in the synchronous language Esterel. Design goals were timing predictability, minimal resource usage, and compliance to full Esterel V5. The KEP directly supports Esterel's reactive control flow operators, notably concurrency and various types of preemption, through dedicated control units. Esterel allows arbitrary combinations and nesting of these operators, which poses particular implementation challenges that are addressed here. Other notable features of the KEP are a refined instruction set architecture, which allows us to trade-off generality against resource usage, and a Tick Manager that minimizes reaction time jitter and can detect timing over-runs.

SyncCharts are a synchronous Statechart variant to model reactive systems with a precise and deterministic semantics. The simulation and software synthesis for SyncCharts usually involve the compilation into Esterel, which is then further compiled into C code. This can produce efficient code, but has two principal drawbacks: 1) the arbitrary control flow that can be expressed with SyncChart transitions cannot be mapped directly to Esterel, and 2) it is very difficult to map the resulting C code back to the original SyncChart, which hampers traceability. This paper presents an alternative software synthesis approach for SyncCharts that compiles SyncCharts directly into Synchronous C (SC). The compilation preserves the structure of the original SyncChart, which is advantageous for validation and possibly certification. We present a static thread-scheduling scheme that reflects data dependencies and optimizes both the number of used threads as well as the maximal used priorities. This results in SC code with competitive speed and little memory requirements.

Accurate estimation of the tick length of a synchronous program is essential for efficient and predictable implementations that are devoid of timing faults. The techniques to determine the tick length statically are classified as worst case reaction time (WCRT) analysis. While a plethora of techniques exist for worst case execution time (WCET) analysis of procedural programs, there are only a handful of techniques for determining the WCRT value of synchronous programs. Most of these techniques produce overestimates and hence are unsuitable for the design of systems that are predictable while being also efficient. In this paper, we present an approach for the accurate estimation of the exact WCRT value of a synchronous program, called its tight WCRT value, using model checking. For our input specifications we have selected a synchronous C based language called PRET-C that is designed for programming Precision Timed (PRET) architectures. We then present an approach for static WCRT analysis of these programs via an intermediate format called TCCFG. This intermediate representation is then compiled to produce the input for the model checker.

The synchronous model of computation together with a suitable execution platform facilitates system-level timing predictability. This paper introduces an algebraic framework for precisely capturing worst case reaction time (WCRT) characteristics for Esterel-style reactive processors with hardware-supported multithreading. This framework provides a formal grounding for the WCRT problem, and allows to improve upon earlier heuristics by accurately and modularly characterizing timing interfaces.

SyncCharts in C (SC) extends C with control flow operators for deterministic, light-weight concurrency and preemption. SC is based on SyncCharts, a synchronous variant of Statecharts with a sound formal basis. SC implements concurrency via a simulation of multi-threading, inspired by reactive processing. This approach permits very fast context switches and allows to express SC operators with regular, sequential C code. Thus a concurrent SC program requires neither a special compiler nor OS support for concurrency.

Collaborative development, incremental design and revision management require the ability to compare different versions of software artifacts. There are well-established approaches for comparing textual artifacts such as program files. However, the situation is different in graphical modeling. So far there exists little support to compare models visually---graphically in the model diagram itself. This paper presents several possible approaches and explores one of these in further detail.We apply paradigms of visualizing text files side-by-side to graphical diagrams and enhance the views by additional features such as automatic layout, navigation and folding. These means allow to compare even complex models without missing differences or getting lost in text based structure compares.As a proof of concept, the proposal is implemented in KIELER, a prototypical modeling environment based on Eclipse.

The synchronous language Esterel is well-suited for programming control-dominated reactive systems at the system level. It provides non-traditional control structures, in particular concurrency and various forms of preemption, which allow to concisely express reactive behavior. As these control structures cannot be mapped easily onto traditional, sequential processors, an alternative approach that has emerged recently makes use of special-purpose reactive processors. However, the designs proposed so far have limitations regarding completeness of the language support, and did not really take advantage of compile-time knowledge to optimize resource usage.This paper presents a reactive processor, the Kiel Esterel Processor 3a (KEP3a), and its compiler. The KEP3a improves on earlier designs in several areas; most notable are the support for exception handling and the provision of context-dependent preemption handling instructions. The KEP3a compiler presented here is to our knowledge the first for multi-threaded reactive processors. The translation of Esterel's preemption constructs onto KEP3a assembler is straightforward; however, a challenge is the correct and efficient representation of Esterel's concurrency. The compiler generates code that respects data and control dependencies using the KEP3a priority-based scheduling mechanism. We present a priority assignment approach that makes use of a novel concurrent control flow graph and has a complexity that in practice tends to be linear in the size of the program. Unlike earlier Esterel compilation schemes, this approach avoids unnecessary context switches by considering each thread's actual execution state at run time. Furthermore, it avoids code replication present in other approaches.

Modeling systems based on semi-formal graphical formalisms, such as Statecharts, has become standard practice in the design of reactive embedded devices. However, the modeling of realistic applications often results in very large and unmanageable graphics, severely compromising their readability and practical use. To overcome this, we present a methodology to support the easy development and understanding of complex Statecharts. Central to our approach is the definition of a Statechart Normal Form (SNF), which provides a standardized layout that is compact and makes systematic use of secondary notations to aid readability. This concept is extended to dynamic Statecharts.

Esterel and Safe State Machines (SSMs) are synchronous languages dedicated to the modeling of embedded reactive systems. While Esterel is a textual language, SSMs are based on the graphical Statecharts formalism. Statecharts are often more intuitive to understand than their textual counterpart, and their animated simulation can help to visualize subtle behaviors of a program. However, in terms of editing speed, revision management, and meta-modeling, the textual nature of Esterel is advantageous. We present an approach to transform Esterel v5 programs into equivalent SSMs. This permits a design flow where the designer develops a system at the Esterel level, but uses a graphical browser and simulator to inspect and validate the system under development.We synthesize SSMs in two phases. The first phase transforms an Esterel program into an equivalent SSM, using a structural translation that results in correct, but typically not very compact SSMs. The second phase iteratively applies optimization rules that aim to reduce the number of states, transitions and hierarchy levels to enhance readability of the SSM. As it turned out, this optimization is also useful for the traditional, manual design of SSMs. The complete transformation has been implemented in a prototypical modeling environment, which allows to demonstrate the practicality of this approach and the compactness of the generated SSMs.

The concurrent synchronous language Esterel allows programmers to treat reactive systems in an abstract, concise manner. An Esterel program is typically first translated into other, non-synchronous high-level languages, such as VHDL or C, and then compiled further into hardware or software. Another approach that has been proposed recently is the direct execution of Esterel-like instructions with a customized processor, which promises the flexibility of a software solution with an efficiency close to a hardware implementation. However, the instruction sets and implementations of the processor architectures proposed so far still have some limitations regarding their completeness, efficiency, and adherence to the original Esterel semantics. This paper presents a novel reactive processor architecture, the Kiel Esterel Processor, which addresses these shortcomings. In particular, it provides a complete, semantically accurate implementation of the Esterel preemption primitives, most of which can be expressed directly with a single machine instruction.One advantage of the reactive processors--in addition to their high execution speed compared to traditional software implementations--is that control-flow is preserved while compiling Esterel into machine code, and that the execution platform has a very predictable timing behavior. This paper presents a precise and very efficient Worst Case Reaction Time (WCRT) analysis, which is geared towards the Kiel Esterel Processor, but which could be adapted to other reactive processors as well.

Give-N-Take is a code placement framework which uses a generic producer-consumer mechanism. An instance of this could be a communication step between a processor that computes (produces) some data, and other processors that subsequently reference (consume) these data in an expression. An advantage of Give-N-Take over traditional partial redundancy elimination techniques is its concept of production regions , instead of single locations, which can be beneficial for general latency hiding. Give-N-Take also guarantees balanced production, i.e., each production will be started and stopped exactly once. The framework can also take advantage of production coming “for free,” as induced by side effects, without disturbing balance. Give-N-Take can place production either before or after consumption, and it also provides the option to speculatively hoist code out of potentially zero-trip loop (nest) constructs. Give-N-Take uses a fast elimination method based on Tarjan intervals, with a complexity linear in the program size in most cases. We have implemented Give-N-Take as partof a Fortran D compiler prototype, where it solves various communication generation problems associated with compiling data-parallel languages onto distributed-memory architectures.

GIVE-N-TAKE is a code placement framework which uses a general producer-consumer concept. An advantage of GIVE-N-TAKE over existing partial redundancy elimination techniques is its concept of production regions, instead of single locations, which can be beneficial for general latency hiding. GIVE-N-TAKE guaranteed balanced production, that is, each production will be started and stopped once. The framework can also take advantage of production coming “for free,” as induced by side effects, without disturbing balance. GIVE-N-TAKE can place production either before or after consumption, and it also provides the option to hoist code out of potentially zero-trip loop (nest) constructs. GIVE-N-TAKE uses a fast elimination method based on Tarjan intervals, with a complexity linear in the program size in most cases.

Many loop nests in scientific codes contain a parallelizable outer loop but have an inner loop for which the number of iterations varies between different iterations of the outer loop. When running this kind of loop nest on a SIMD machine, the SIMD-inherent restriction to single program counter common to all processors will cause a performance degradation relative to comparable MIMD implementations. This problem is not due to limited parallelism or bad load balance, it is merely a problem of control flow.