Traditionally, synchronous languages, such as Esterel, have been compiled into hardware, where timing analysis is relatively easy. When compiled into software - e.g., into sequential C code very conservative estimatio...
详细信息
ISBN:
(纸本)9781605584973
Traditionally, synchronous languages, such as Esterel, have been compiled into hardware, where timing analysis is relatively easy. When compiled into software - e.g., into sequential C code very conservative estimation techniques have been used, where the focus has only been on obtaining safe timing estimates and not on the cost of the implementation. While this was acceptable in avionics, efficient implementations and hence tight timing estimates are needed in more cost-sensitive application domains. Lately, a number of advances in Worst-Case Execution Time (WCET) analysis techniques, coupled with the growing use of software in domains such as automotives, have led to a considerable interest in timing analysis of code generated from Esterel specifications. In this paper we propose techniques to obtain tight estimates on the processing time of input events by sequential C code generated from Esterel programs. Execution of an Esterel program as in all other synchronous languages is logically made up of a sequence of clock ticks. In reality, they take non-zero time which depends on the generated C code as well as the underlying hardware platform on which this code is executed. Apart from exploiting the specific structure of this C code to obtain tight WCET estimates, we capture program-level contexts across ticks in order to obtain tight estimates on response times of events whose processing spans across multiple clock ticks. Such tighter estimates immediately translate into more cost-effective implementations. Our experimental results with realistic case studies show 30% reduction in timing estimates when program level context information is taken into account.
We demonstrate how TransLucid can be used as a reactive system by introducing sets and privileged dimensions for time and port in the language. At each instant, there is a set of active ports, where sets of equations,...
详细信息
ISBN:
(纸本)9781424445257
We demonstrate how TransLucid can be used as a reactive system by introducing sets and privileged dimensions for time and port in the language. At each instant, there is a set of active ports, where sets of equations, demands and threads are all registered. Each thread defines a sequence of (state, demand) pairs, and threads may interact through the overall set of equations. The en tire system remains fully declarative.
We are interested in the programming of real-time embedded control systems, such as in robotic, automotive or avionic systems. They are designed with multiple tasks, each with multiple modes. It is complex to design t...
详细信息
We are interested in the programming of real-time embedded control systems, such as in robotic, automotive or avionic systems. They are designed with multiple tasks, each with multiple modes. It is complex to design task handlers that control the switching of activities in order to insure safety properties of the global system. We propose a model of tasks in terms of transition systems, designed especially with the purpose of applying existing discrete controller synthesis techniques. This provides us with a systematic methodology, for the automatic generation of safe task handlers, with the support of synchronous languages and associated tools.
This paper presents the language Lutin and its operational semantics. This language specifically targets the domain of reactive systems, where an execution is a (virtually) infinite sequence of input/output reactions....
详细信息
This paper presents the language Lutin and its operational semantics. This language specifically targets the domain of reactive systems, where an execution is a (virtually) infinite sequence of input/output reactions. More precisely, it is dedicated to the description and the execution of constrained random scenarios. Its first use is for test sequence specification and generation. It can also be useful for early simulation of huge systems, where Lutin programs can be used to describe and simulate modules that are not yet fully developed. The programming style mixes relational and imperative features. Basic statements are input/output relations, expressing constraints on a single reaction. Those constraints are then combined to describe non deterministic sequences of reactions. The language constructs are inspired by regular expressions, and process algebra (sequence, choice, loop, concurrency).Moreover, the set of statements can be enriched with user defined operators. A notion of stochastic directive is also provided, in order to finely influence the selection of a particular class of scenarios.
As code generation for synchronous programs requires strong safety properties to be satisfied, composition-ality becomes a difficult goal to achieve. Most synchronous languages, such as Esterel, Lustre or Signal requi...
详细信息
As code generation for synchronous programs requires strong safety properties to be satisfied, composition-ality becomes a difficult goal to achieve. Most synchronous languages, such as Esterel, Lustre or Signal require a given module or compilation unit to be insensitive to latency that communication with its environment may incur. In Lustre or Signal, for instance, a compilation unit must satisfy the so-called property of endochrony. To preserve endochrony in an asynchronous environment, an ad-hoc protocol is synthesized to interface the module. However, endochrony is not preserved by composition. Consequently, the protocol has to be rebuilt every time a new module is added in the environment. We propose a methodology and code generation scheme which simplifies this concern. It consists of weakening the global objective of globally preserving endochrony. Instead, we aim at the preservation of a more liberal and compositional objective, weak endochrony [14], which is compositional and much closer from the expected requirement of insensitivity to communication latency. As a result, our code generation scheme supports true separate compilation: a locally compiled synchronous module does not require its synthesized interface with the environment to be rebuilt once composed with another module.
We study the implementation of a synchronous program as a set of multiple tasks running on the same computer, and scheduled by a real-time operating system using some preemptive scheduling policy, such as fixed priori...
详细信息
We study the implementation of a synchronous program as a set of multiple tasks running on the same computer, and scheduled by a real-time operating system using some preemptive scheduling policy, such as fixed priority or earliest-deadline first. Multitask implementations are necessary, for instance, in multiperiodic applications, when the worst-case execution time of the program is larger than its smallest period. In this case, a single-task implementation violates the schedulability assumption and, therefore, the synchrony hypothesis does not hold. We are aiming at semantics-preserving implementations, where, for a given input sequence, the output sequence produced by the implementation is the same as that produced by the original synchronous program, and this under all possible executions of the implementation. Straightforward implementation techniques are not semantics-preserving. We present an intertask communication protocol, called DBP, that is semantics-preserving and memory-optimal. DBP guarantees semantical preservation under all possible triggering patterns of the synchronous program: thus, it is applicable not only to time-, but also event-triggered applications. DBP works under both fixed priority and earliest-deadline first scheduling. DBP is a nonblocking protocol based on the use of intermediate buffers and manipulations of write-to/read-from pointers to these buffers: these manipulations happen upon arrivals, rather than executions of tasks, which is a distinguishing feature of DBP. DBP is memory-optimal in the sense that it uses as few buffers as needed, for any given triggering pattern. In the worst case, DBP requires, at most, N + 2 buffers for each writer, where N is the number of readers for this writer.
New design methodologies at higher abstraction levels are necessary to deal with the increasing complexity of modem embedded systems. As a consequence, new design paradigms must supersede traditional design methods to...
详细信息
ISBN:
(纸本)9780791848050
New design methodologies at higher abstraction levels are necessary to deal with the increasing complexity of modem embedded systems. As a consequence, new design paradigms must supersede traditional design methods to bridge the abstraction gap which often exists between specification and implementation. This paper examines several examples which evaluate the applicability of Esterel, a language with well-defined semantics for specification and verification of reactive control systems. Implementation size, performance and design effort were selected as measures to assess the benefits of this design approach in comparison to a traditional one.
We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an exi...
详细信息
ISBN:
(纸本)9781605581040
We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an existing synchronous dataflow programming language with primitives allowing the description of a distributed architecture and the localization of some expressions onto some processors. We also present a distributed semantics to formalize the distributed execution of synchronous programs. Our second contribution is to provide a type system, in order to infer the localization of non-annotated values by means of type inference and to ensure, at compilation time, the consistency of the distribution. Our third contribution is to provide a type-directed projection operation to obtain automatically, from a centralized typed program, the local program to be executed by each computing resource. The type system as well as the automatic distribution mechanism has been fully implemented in the compiler of an existing synchronous data-flow programming language.
We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an exi...
详细信息
We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an existing synchronous dataflow programming language with primitives allowing the description of a distributed architecture and the localization of some expressions onto some processors. We also present a distributed semantics to formalize the distributed execution of synchronous programs. Our second contribution is to provide a type system, in order to infer the localization of non-annotated values by means of type inference and to ensure, at compilation time, the consistency of the distribution. Our third contribution is to provide a type-directed projection operation to obtain automatically, from a centralized typed program, the local program to be executed by each computing resource. The type system as well as the automatic distribution mechanism has been fully implemented in the compiler of an existing synchronous data-flow programming language.
We study the implementation of a synchronous program as a set of multiple tasks running on the same computer, and scheduled by a real-time operating system using some preemptive scheduling policy, such as fixed priori...
详细信息
We study the implementation of a synchronous program as a set of multiple tasks running on the same computer, and scheduled by a real-time operating system using some preemptive scheduling policy, such as fixed priority or earliest-deadline first. Multitask implementations are necessary, for instance, in multiperiodic applications, when the worst-case execution time of the program is larger than its smallest period. In this case, a single-task implementation violates the schedulability assumption and, therefore, the synchrony hypothesis does not hold. We are aiming at semantics-preserving implementations, where, for a given input sequence, the output sequence produced by the implementation is the same as that produced by the original synchronous program, and this under all possible executions of the implementation. Straightforward implementation techniques are not semantics-preserving. We present an intertask communication protocol, called DBP, that is semantics-preserving and memory-optimal. DBP guarantees semantical preservation under all possible triggering patterns of the synchronous program: thus, it is applicable not only to time-, but also event-triggered applications. DBP works under both fixed priority and earliest-deadline first scheduling. DBP is a nonblocking protocol based on the use of intermediate buffers and manipulations of write-to/read-from pointers to these buffers: these manipulations happen upon arrivals, rather than executions of tasks, which is a distinguishing feature of DBP. DBP is memory-optimal in the sense that it uses as few buffers as needed, for any given triggering pattern. In the worst case, DBP requires, at most, N + 2 buffers for each writer, where N is the number of readers for this writer.
暂无评论