Project topics and materials
Get Complete Project Material File(s) Now! »
Présentation informelle du langage
Ce chapitre présente le langage de manière informelle. Celui-ci est construit comme une extension de LUSTRE et emprunte certaines constructions à LUCID SYNCHRONE [Pou06] et aux versions récentes de SCADE. Il étend les langages synchrones flots de données avec des primitives temps réel haut-niveau basées sur les horloges strictement périodiques. La sémantique formelle du langage est disponible dans la partie anglaise du mémoire.
Typage polymorphe
Le langage fournit un typage polymorphe, ce qui est désormais une caractéristique relativement cou-rante pour un langage de programmation. Les types des variables du programme peuvent être laissés non-spécifiés, auquel cas ils seront inférés par le compilateur. Par exemple :
node infer(i:int) returns (o)
let o=i; tel
Dans cet exemple, le compilateur infère que le type de o est int.
Un exemple de polymorphisme est donné ci-dessous :
node poly(i,j) returns (o,p)
let o=i; p=j; tel
Le compilateur peut seulement déduire que o et i ont le même type (disons ), et que p et j ont le même type (disons ). Le nœud poly peut être instancié avec différents types, par exemple le programme suivant est correct :
node inst(i:int; j:bool) returns (o,p,q,r)
let
(o,p)=poly(i,j);
(q,r)=poly(j,i);
tel
Le compilateur infère que o a le type int, p a le type bool, q a le type bool et r a le type int.
Primitives temps réel
Le langage a pour but de permettre de spécifier des contraintes temps réel avec un niveau d’abs-traction élevé. Les primitives que nous introduisons sont destinées à spécifier des contraintes relatives à l’environnement du système (des contraintes physiques par exemple) plutôt que des contraintes liées à des considérations d’implémentation. Les entrées et sorties d’un nœud représentent son interface avec l’environnement. Les contraintes temps réel sont donc spécifiées sur les entrées et sorties d’un nœud : ce sont des contraintes venant de l’environnement du système.
La période d’une entrée ou d’une sortie d’un nœud peut être spécifiée de la manière suivante :
node periodic(i: int rate (10,0)) returns (o: int rate (5,0)) let tel
x: rate (n,p) spécifie que l’horloge de x est l’horloge strictement périodique (n; p). Ainsi, i a pour période 10 et o a pour période 5.
Le développeur peut aussi spécifier la phase d’un flot périodique :
node phased(i: int rate (10,1/2)) returns (o: int rate (10,0))
let
…
tel
Dans cet exemple, i a pour période 10 et pour phase 12 , donc sa séquence d’horloge est (5; 15; 25; 35; : : :). Une contrainte d’échéance définit une échéance à respecter pour le calcul d’un flot, relative au début
de la période du flot. Les contraintes d’échéance peuvent être spécifiées sur des sorties de nœuds : node deadline(i: int rate (10,0)) returns (o: int rate (10,0) due 8)
let
…
tel
x: due d spécifie que x a pour contrainte d’échéance d. Si x est présent à la date t, alors x doit être calculé avant la date t + d.
Des contraintes d’échéance peuvent aussi être spécifiées sur des entrées, mais leur signification est alors légèrement différente :
node deadline(i: int rate (10,0) before 2) returns (o: int)
let
…
tel
x: before d spécifie que l’entrée x doit être acquise par le programme avant l’échéance d (ie une échéance pour la « production » de l’entrée). En pratique, cela signifie qu’une opération capteur doit s’effectuer avant cette échéance. Les opérations effectuant des opérations à partir de cette entrée pourront lire la valeur de l’entrée à partir de la sortie du capteur.
Les contraintes d’échéance n’ont pas d’impact sur l’horloge d’un flot et donc sur les contraintes de synchronisation entre flots. Si un flot f a pour horloge (n; p) et pour échéance d et si un flot f0 a pour horloge (n; p) et pour échéance d0 (avec d 6= d0), les flots sont tout de même considérés synchrones et peuvent être combinés car ils sont produits durant les même instants logiques. Les échéances ne sont prises en compte que durant la phase d’ordonnancement du programme.
Opérateurs de transition de rythme
Nous définissons des opérateurs de transition de rythme, basés sur les transformations périodiques d’horloges, servant à gérer les transitions entre flots de rythmes différents. Ces opérateurs permettent de définir des motifs de communication entre nœuds de rythmes différents. Notre objectif est de fournir un ensemble réduit d’opérateur simples, qui peuvent être combinés afin de produire des motifs de commu-nication complexes. La sémantique de ces opérateurs est définie formellement et leur comportement est parfaitement déterministe.
Tout d’abord, il est possible de sous-échantillonner un flot à l’aide de l’opérateur =^ :
node under_sample(i: int rate (5,0))
returns (o: int rate (10,0))
let
o=i/^2;
tel
e=^k ne conserve que la première valeur parmi k valeurs successives de e. Si e a pour horloge , alors e=^k a pour horloge =:k. Ce comportement est illustré Fig. 11.
A l’inverse, il est possible de sur-échantillonner un flot à l’aide de l’opérateur ^
node over_sample(i: int rate (10,0)) returns (o: int rate (5,0)) let
o=i*^2;
tel
e ^k duplique chaque valeur de e, k fois. Si e a pour horloge , alors e ^k a pour horloge : k. Ce comportement est illustré Fig. 12.
Opérateurs de décalage de phase
Nous définissons trois opérateurs basés sur les décalages de phase. L’ensemble des valeurs d’un flot peut être décalée d’une fraction de sa période à l’aide de l’opérateur > :
node offset(i: int rate (10,0))
returns (o: int rate (10,1/2))
let
o=i~>1/2;
tel
Si e a pour horloge , e > q retarde chaque valeur de e de q ( ) (avec q 2 Q+). L’horloge de e > q est !: q. Cet opérateur est le plus souvent utilisé avec q inférieur à 1, mais les valeurs supérieures à 1 sont autorisées. Le comportement de cet opérateur est illustré Fig. 13.
Table of contents :
1 Etat de l’art
1.1 Langages de programmation bas-niveau
1.2 Les langages synchrones
1.3 Matlab/Simulink
1.4 Les langages de description d’architecture (ADL)
1.5 Motivation de notre travail
2 Horloges périodiques temps réel
2.1 Un modèle reliant instants et temps réel
2.2 Horloges Strictement Périodiques
2.3 Horloges strictement périodiques et horloges booléennes
3 Présentation informelle du langage
3.1 Typage polymorphe
3.2 Primitives temps réel
3.3 Retards
3.4 Conditions d’activation
4 Calcul d’horloges
4.1 Types d’horloges
4.2 Inférence d’horloges
4.3 Unification d’horloges
4.4 Subsomption
5 Mode de compilation
5.1 Limitation de la génération de code classique en « boucle simple »
5.2 Génération de code multi-tâche
6 Extraction de tâches dépendante
6.1 Expansion de programme
6.2 Graphe de tâches
6.3 Caractéristiques temps réel
6.4 Conditions d’activation
7 Traduction de tâches dépendantes en tâches indépendantes
7.1 Encodage des précédences
7.2 Analyse d’ordonnançabilité
7.3 Communications inter-tâches
8 Prototype
9 Conclusion
Introduction
Chapter 1 State of the Art
1.1 Low-level programming
1.1.1 Real-time API
1.1.2 Real-time Operating Systems
1.1.3 Towards a higher level of abstraction
1.2 Synchronous Languages
1.2.1 LUSTRE
1.2.2 SIGNAL
1.2.3 ESTEREL
1.2.4 SYNDEX and the AAA methodology
1.2.5 Synchronous Data-Flow (SDF)
1.2.6 Globally Asynchronous Locally Synchronous (GALS) Systems
1.3 Matlab/Simulink
1.4 Architecture description languages
1.4.1 AADL
1.4.2 REACT/CLARA
1.4.3 UML and CCSL
1.4.4 GIOTTO
1.5 Motivation of our work
1.6 Outline of the thesis
Part I Language Definition
Chapter 2 The Synchronous Approach
2.1 Logical time and instants
2.2 Verifying the synchronous hypothesis
2.3 Overview of synchronous languages
2.4 Data-flow synchronous languages, an example: LUSTRE
2.4.1 Basic operators
2.4.2 Clock operators
2.4.3 Nodes
2.4.4 Automated code generation
Chapter 3 Real-Time Periodic Clocks
3.1 A model relating instants to real-time
3.1.1 Multiple logical time scales
3.1.2 Real-time flows
3.2 Strictly Periodic Clocks
3.2.1 Definition
3.2.2 Periodic clock transformations
3.2.3 Integer Strictly Periodic Clocks
3.3 Strictly periodic clocks and Boolean clocks
3.4 Summary
Chapter 4 Language Syntax and Semantics
4.1 Types polymorphism
4.2 Real-time Primitives
4.2.1 Declaring real-time constraints
4.2.2 Rate transition operators
4.2.3 Phase offset operators
4.2.4 Rate transitions on unspecified rates
4.2.5 Sensors and actuators
4.3 Delays
4.4 Activation conditions
4.4.1 Boolean sampling operators
4.4.2 Combining Boolean and strictly periodic clock flow operators
4.5 Syntax
4.6 Synchronous Temporised Semantics
4.6.1 Kahn’s semantics
4.6.2 Semantics of classic synchronous operators
4.6.3 Semantics of strictly periodic clock operators
4.6.4 Denotational semantics
4.7 Summary
Chapter 5 Multi-periodic Communication Patterns
5.1 Sampling
5.2 Queuing
5.3 Mean value
5.4 Non-harmonic periods
5.5 A complete example
5.6 Summary
Chapter 6 Static Analyses
6.1 Causality Analysis
6.2 Typing
6.2.1 Types
6.2.2 Types inference
6.2.3 Types unification
6.2.4 Examples
6.3 Clock Calculus
6.3.1 Clock Types
6.3.2 Clock inference
6.3.3 Clocks unification
6.3.4 Subsumption
6.3.5 Example
6.3.6 Correctness
6.4 About Flows Initialisation
6.5 Summary
Chapter 7 Conclusion on language definition
Part II Compiling into a Set of Real-Time Tasks
Chapter 8 Overview of the Compilation Process
8.1 Limitation of the classic « single-loop » code generation
8.2 Multi-task code generation
8.3 Compilation chain
Chapter 9 Extracting Dependent Real-Time Tasks
9.1 Program Expansion
9.2 Task Graph
9.2.1 Definition
9.2.2 Tasks
9.2.3 Precedences
9.2.4 Intermediate graph
9.2.5 Graph reduction
9.2.6 Task clustering
9.3 Real-time characteristics
9.4 Activation conditions
9.5 Summary
Chapter 10 From Dependent to Independent Tasks
10.1 Scheduling Dependent Tasks
10.1.1 With/without preemption
10.1.2 Dynamic/static priority
10.1.3 Processing precedences before run-time/at run-time
10.2 Encoding Task Precedences
10.2.1 Adjusting real-time characteristics
10.2.2 Definition of task instance precedences
10.2.3 Release dates adjustment in the synchronous context
10.2.4 Deadline calculus
10.2.5 Optimality
10.2.6 Complexity
10.3 Schedulability analysis
10.4 Inter-Task Communications
10.4.1 Ensuring communication consistency
10.4.2 Task instances communications
10.4.3 Communication protocol
10.4.4 Example
10.5 Summary
Chapter 11 Code generation
11.1 Communication buffers
11.2 Task functions
11.3 Task real-time attributes
11.4 Threads creation
11.5 Summary
Chapter 12 Prototype implementation
12.1 The compiler
12.2 Earliest-Deadline-First scheduler with deadline words
12.2.1 Application-defined schedulers in MARTE OS
12.2.2 EDF implementation
12.2.3 Deadline words support
12.3 Summary
Chapter 13 Conclusion on language compilation
Part III Case Study
Chapter 14 The Flight Application Software: Current Implementation
14.1 Hardware architecture
14.2 Software architecture
14.3 Bus communications
14.4 Summary
Chapter 15 Case study Implementation
15.1 System specification
15.2 Implementation overview
15.3 Specific requirements
15.3.1 Slow-to-fast communications
15.3.2 Producing outputs at exact dates
15.3.3 Output with a phase smaller than the related input
15.3.4 End-to-end latency longer than the period
15.4 Results
15.5 Summary
Conclusion
Bibliography
