Jouer avec le temps Gérard Berry Collège de France Chaire Algorithmes, machines et langages ...

Jouer avec le temps

Gérard Berry

Collège de FranceChaire Algorithmes, machines et langages

http://www.college-de-france.fr/site/gerard-berrygerard.berry@college-de-france.fr

Cours 8, 2

G. Berry, Collège de France

1. Calcul de la constructivité des circuits

2. Synchroniseurs mésochrones et plésiochrones

3. Ptides : programmation temps-réel distribuée

02/04/2014 2

Agenda

02/04/2014 3

Agenda

G. Berry, Collège de France 02/04/2014 4

Partage de ressources cycles combinatoires

O if C then F(G(I)) else G(F(I))

Sharad Malik, Analysis of Cyclic Combinational CircuitsIEEE Transactions on Computer-Aided Design of Integrated

Circuits and Systems, VOL. 13, NO. 7, JULY 1994

Les règles de déduction

true d1

booldR d e RS

dR R eSchain

maxd,eS∩Tjoin rassemble les entrées d’une porte

affaiblissement

+ règles booléennes pour les régions (valables car appliquées à des signaux stables)+ opérations arithmétiques sur les délais

pour C,I fixé, C,I ⊢ ... implicite partout

chaîne les transitionsy e x x ey)x ey

6G. Berry, Collège de France 02/04/2014

max(d1,d2) s1s2

cas x0i.e. 0x

C s1 d1 x s2 d2 xs1s2

chain0xs1s2

x0 région s1s2 atteinte en temps max(d1,d2)

Logique Booléenne constructive

e e’ 1

e’ 1

e e’ 1 e e’ 0

e 0 e’ 0

• Circuit C, vecteur d’entrées : I entrées → {0,1}

• Formules : I ⊢ e b, abrégées en e b si I constant

X : e C e b

e e’ 0

e’ 0

e e’ 0 e e’ 1

e 1 e’ 1

e 1I I(I)I entrée

Exemple de transformation de preuves

max(d1,d2) s1s2

cas x0i.e. 0x

chain0xs1s2

I(x)0 ⊢ x0xs1s2 1s1x C s2 xs1s

UN-logic

Constructive Boolean Logic

s11 s21

10G. Berry, Collège de France

• Pour des délais fixés, la UN-prouvabilité vs. ⊢ est une

CNS pour la UN-stabilisation vs. ⊨

02/04/2014

On arrive au bout !

• Mais toute preuve avec délais peut être transcrite en preuve Booléenne constructive sans délais, et réciproquement !

Autrement dit : la prouvabilité en logique booléenne constructive sans délais caractérise exactement la UN-constructivité uniforme (pour n’importe quels délais)

Bonus: les algorithmes de simulation par preuve calculent le temps maximum de réaction du circuit pour chaque vecteur d’entrée

O if C then F(G(I)) else G(F(I))

cycle F

C 1 O if C then F(G(I)) else G(F(I))

Chaque porte est utilisée au plus une fois pour une entrée donnée,

interprétation en temps linéaire(option –I d’Esterel v5)

Ordre d’information : la logique ternaire de Scott

tt ff ^ tt^ ff

B : booléens de Scott

indéfini je ne sais pas je ne veux pas savoir moins défini que

(x,y) (x’,y’ ) ssi x x’ et y y’i.e. (x,y) moins défini que (x’,y’)

, tttt, tt

, fftt, ff

ff, tt

ff, ff

B B (vu d’avion)

Fonctions croissantes

• Plus on en donne, plus on en récupère ! f : <D,,> <D’,’,’ > croissante

ssi x, y. x y f(x) ’ f(y)

• Fonction constante :

x, y. f(x) f(y)

• Attention :

{tt, tttt, fftt } : B B constante

{, tttt, fftt } : B B stricte, pas constante !

• Ordre des fonctions : f f’ ssi f partout moins définie que f’ f f’ ssi x. f(x) f’(x)

Disjonction Booléenne

,tttt,tt

,fftt,ff

en C: e | e’

,tttt,tt

,fftt,ff

en C : e || e’

,tttt,tt

,fftt,ff

en C: e’ || e

,tttt,tt

,fftt,ff

Disjonction Booléenne en logiciel

,tttt,tt

,fftt,ff

en C: e | e’

,tttt,tt

,fftt,ff

en C : e || e’

,tttt,tt

,fftt,ff

en C: e’ || e

Plotkin, 1972Berry, 1977

cf. cours du 09/12/2009

Disjonction Booléenne en circuits

oug oud

,tttt,tt

,fftt,ff

oup : xy

(xx)(xy) (yy)(xy)

(xx)(yy)(xy)

Ou / et parallèle logique constructive

,tttt,tt

,fftt,ff

I e e’ 0

I e’ 0

I e’ 1

I e e’ 1

I e ou non e 1

Théorème de point fixe

• Soit <D,,> et f : D D croissante pour Un point fixe de f est un xD tel que f (x) x

Théorème 2 : si D est fini (ou D complet et f continue),

Théorème 2 : alors Y(f ) Un>0 f n()

Algorithme : calculer y1 f (), y2 f (y1), ..., yn+1 f (yn)

Algorithme : s’arrêter dès que yn+1 yn

Algorithme : alors Y(f) yn

cf. cours lambda-calcul du 9 décembre 2009

Théorème 1 : f admet un plus petit point fixe Y(f ) tel que f(Y(f)) Y(f ) et x. f (x) x Y(f ) x

Application aux circuits cycliques (S. Malik)

1. x 0 : f s1,s2 tt,tt

2. x 1 : f s1,s2 ff, s1s22. x 1 : f , ff,

2. x 1 : f ff, ff,tt2. x 1 : f ff,tt ff,tt résultat final s1s2

1. x 0 : f , tt,tt ) f tt,tt résultat final s1s2

le circuit est constructif pour toute entrée

• Question : au lieu de traiter les vecteurs entrées un par un, ne peut-on pas les traiter tous en même temps ?

02/04/2014 21

Evaluation symbolique

• Réponse : si, par évaluation symbolique– représentation des ensembles, fonctions et images directes ou

inverses par des expressions booléennes– codages efficaces de ces expressions (ex. BDDs) – algorithmes d’itération de point fixe sur BDD formels pour la

constructivité

Implémenté dans Esterel v5 (option –causal)en utilisant le système de BDDs TiGeR

Merci à T. Shiple, O. Coudert, J-C. Madre et H. Touati

• Codage d’un Booléen de Scott par deux Booléens standards :–x (xd,xv) avec (ff,ff), tt (tt,tt) et ff (tt,ff)–notation : xtt

pour xdxv , xff pour xdxv

02/04/2014 22

Codages Dual Rail

• Codage d’un ensemble par sa fonction caractéristique :–ex. { (x,y) | x et yff } xdyff

• Codage d’une fonction par une expression : –ex. : xy ( xttytt(xffyff) , xttytt )

• Codage de l’image d’un ensemble par une fonction : –ex. : si E B

2 et f : B2 B

2 – alors f(E) { (x’,y’) | (x,y)E. (x’,y’) f(x,y) }– avec (x,y).P(x,y) P(ff,ff,ff,ff)P(tt,tt,ff,ff)P(tt,ff,ff,ff)

P(ff,ff,tt,tt)... P(tt,ff,tt,ff)Gare auxexponentielles !

Algorithme itératif symbolique

(y,z) (x, xyz) (yd,yv,zd,zv,) (xd , xff ,

xffyffztt(xttyttzff) , xffyffztt)

Y() (xd , xff , xd , xd) uniformément constructif

(ff,ff,ff,ff,) (xd , xff , xd , xff)

(xd , xff , xd , xff) (xd , xff , xd , xd)

(, ) (x, x)

(x, x) (x, xxx) (x, xx)

Version acyclique : C s1 x s2 1

Importance des relations d’entrée

input TOP_HORLOGE, INDICATEUR_ON ;relation TOP_HORLOGE # INDICATEUR_ON ;signal FIN, REARMEMENT in abort await TOP_HORLOGE ; emit FIN end when REARMEMENT|| abort every INDICATEUR_ON ; emit REARMEMENT when FINend signal

TOP_HORLOGE # INDICATEUR_ON FIN # REARMEMENT

E. Ledinot, Dassault aviation, séminaire du 16/04/2013

L’algorithme symbolique de constructivitécalcul le prédicat d’entrée maximal qui

rend le circuit constructif

Ordonnanceur round-robin à jeton

Cycle combinatoire !

le cycle est saincar coupé à une porte ou

Le registre à 1change à chaque cycle,le point de coupure avec

Cycle incorrectsi aucun registre à 1

au départ !

Condition de constructivitéde la partie cyclique : R1R2

Doit être vraie à l’instant initialet préservée dans l’exécution

calcul des états atteignables (vs. le temps de l’horloge)

Calcul symbolique des états atteignables

R1 R0 U N(R0)

R2 R1 U N(R1)...Rn+1 Rn U N(Rn)

• Calculer les Ri en utilisant des BDDs - mais .... BDD(F) explose !

• Utiliser chaque Ri comme simplifieur pour BDD(F)

• Puis utiliser R comme optimiseur pour l’implémentation de F

(Madre, Coudert, Touati)

Vérifier pour tout i que Ri rend le circuit combinatoire constructif

02/04/2014 32

Agenda

Low-Latency and Low-Overhead Mesochronous and Plesiochronous Synchronizers

Jean Michel Chabloz et Ahmed Hemani, KTH StockholmEuromicro 2011

02/04/2014 33

Synchroniseurs mésochrones et plésiochrones

Horloges multiples

Même fréquence

synchrones même phase

mésochrones : décalage de phase constant

plésiochrones : décalage de phase variable

Fréquences différentes

harmoniques rapports rationnels

asynchrones rapports inconnus / variables

Echantillonnage par front montant ou descendant

Chemin de données

délaiT/4

strobe

resync

titi-1

strobe

strobed1

strobe

strobed11

0 à ti-1et 1 à ti front montant1 à ti-1et 1 à ti front descendant

titi-1

strobe

strobed 0

strobe

strobed11

1 1 plus tard !

0 à ti-1et 1 à ti front montant1 à ti-1et 1 à ti front descendant

ddélai

resync

strobe

Horloges multiples

Même fréquence

synchrones même phase

mésochrones : décalage de phase constant

plésiochrones : décalage de phase variable

Fréquences différentes

harmoniques rapports rationnels

asynchrones rapports inconnus / variables

Idée : l’émetteur inverse strobe à chaque ticket le récepteur prévoit le front montant ou descendant

à utiliser dans 2 coups d’horloge

02/04/2014 44

Agenda

Ptides (E. Lee et. al) : Programming Temporally Integrated Distributed Systems

les messages portent des timestamps précis

Les acteurs spécifient les calculs

synchro d’horloge bornée (PTP)

la synchronisationdonne un sens global

aux timestamps

messages traités dans l’ordre

des timestamps

Synchronisation d’horloges

timestamp temps limite

timestamp = date de mesure

capteurs acteurs

actuateurs acteurs

actuateurs : timestamps

date de l’action

Maîtrise des latences

La latence globale des capteurs aux actionneurs est calculable,ce qui rend la correction et la performance du système analysable

maîtrise des latences par calcul

des timestamps

retour au monde physique

Conséquence : déterminisme !

délai du réseauborné d

un événement de timestamp t peut être sorti au tempst + s + d + e – d2

hypothèse: erreur d’horloge bornée e

hypothèse : délai des capteurs borné s

application:latence d2

Note : Il faut des bornes aux interfaces réseau pour garantir l’ordre temporel indépen-damment de l’ordre d’exécution des acteurs.

Implémentation de Ptides

RéférencesConstructive Boolean Circuits and the Exactness of Timed Ternary Simulation M. Mendler, T. Shiple et G. Berry. Formal Methods in System Design, Vol.40, No.3, pp. 283-329, Springer (2012).

Constructive Analysis of Cyclic CircuitsT. Shiple, G. Berry et H. Touati. Proc. Int. Design and Testing Conference IDTC'96, Paris, France (1996).

Low-Latency and Low-Overhead Mesochronous and Plesiochronous Synchronizers Jean Michel Chabloz, Ahmed Hemani Conference: Euromicro Symposium on Digital Systems Design - DSD , 2011

On the Schedulability of Real-Time Discrete Event SystemsE. Matsikoudis, C. Stergiou, E.A. Lee. Proc EMSOFT 2013.

PTIDES: A Programming Model for Distributed Real-Time Embedded Systems P. Derler, T. Huining Feng, E.A. Lee, S. Matic, H.D.Patel, YangZ hao, Jia Zou Report EECS-2008-72, EECS Department, University of California, Berkeleyhttp://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-72.html

Jouer avec le temps Gérard Berry Collège de France Chaire Algorithmes, machines et langages ...

Documents

Berry CM - Edmond About - L'homme à l'oreille casséeekladata.com/litteratureprimaire.eklablog.com/perso/berry cm pdf/berry... · mené à Fontainebleau chez les Renault où le docteur

Revue - acpr.banque-france.fr

ITTINÉRRAIRRES bbbis · en Berryen Berry Liste des marchés en Berry : Ils animent nos bourgs, places et halles toute l’année ! Même si tout n’est pas tout le temps 100% Berry,

Giennois • Puisaye • Berry Berry - Le Renouveau - Des

1 Les langages de programmation Chaire d'innovation technologique Liliane Bettencourt Collège de France 8 février 2008 Gérard Berry Gerard.Berry@college-de-france.fr

Juillet 2021 - banque-france.fr

KLASIK - aeria-france.fr

REFERENSI Black Tapai Berry Ice Sherbet

Polynômes - maths-france.fr

Gérard Berry (@college-de-france.fr) Laurent Thénié ... · GET_TOKEN PASS_TOKEN . OK = REQ and GO PASS = not REQ and GO ... • Type et taille de cache ? ... • Comment profiter

CF - rollingcenter-france.fr

UP Berry 2014/2015

Cours - college-de-france.fr

REMERCIEMENTS - pepite-france.fr

Le Bas-Berry insolite

Gérard Berry - Sésamath

Portes basculantes Berry - hormann.fr

SOMMAIRE Giennois • Puisaye • Berry Berry

Tablette Berry Instructions

Portes basculantes Berry