Jouer avec le temps Gérard Berry Collège de France Chaire Algorithmes, machines et langages [email protected]

Jouer avec le temps

Gérard Berry

Collège de FranceChaire Algorithmes, machines et langages

http://www.college-de-france.fr/site/[email protected]

Cours 8, 2

avril

2014

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

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

mailto:[email protected]

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))

F

G

C

C

I O

C10

10

10

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

eS

deS

dR R eSchain

dS eT

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

d2

d1

max(d1,d2) s1s2

cas x0i.e. 0x

C s1 d1 x s2 d2 xs1s2

0x0x

d1s1

chain0xs1s2

bool

d2s2

chain

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

join


Logique Booléenne constructive

e 1

e e’ 1

e’ 1

e e’ 1 e e’ 0

e 0 e’ 0

e 1

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

X b

e 0

e e’ 0

e’ 0

e e’ 0 e e’ 1

e 1 e’ 1

e 0

e 1I I(I)I entrée


Exemple de transformation de preuves

max(d1,d2) s1s2

cas x0i.e. 0x


0x0x

d1s1

chain0xs1s2

bool

d2s2

chain

join

x0s11

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

s2 1

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

G

C

C

I O

C10

10

10



F

G

1

O

110

10

10

1

I

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’)

tt, ,

, tttt, tt

, fftt, ff

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

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

ous

en C: e | e’

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

oug

en C : e || e’

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

oud

en C: e’ || e

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

oup


Disjonction Booléenne en logiciel

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

ous

en C: e | e’

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

oug

en C : e || e’

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

oud

en C: e’ || e

oup

Plotkin, 1972Berry, 1977

cf. cours du 09/12/2009


Disjonction Booléenne en circuits

ous

oug oud

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

oup : xy

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

(xx)(yy)(xy)


Ou / et parallèle logique constructive

tt, ,

,tttt,tt

,fftt,ff

ff,

ff,tt

ff,ff

xy

I e 0

I e e’ 0

I e’ 0

I e’ 1

I e e’ 1

I e 1

I e e’ 1

I e ou non e 1

tt


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)

d2

d1


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


Bonus

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

rend le circuit constructif


Ordonnanceur round-robin à jeton

Cycle combinatoire !

ok

reqok



le cycle est saincar coupé à une porte ou

okreq

reqok


okreq

reqok

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



Cycle incorrectsi aucun registre à 1

au départ !

ok

reqok

Condition de constructivitéde la partie cyclique : R1R2

R1

R2

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

N

R0 0

R1 R0 U N(R0)

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

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)

R Rn

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


Echantillonnage par front montant ou descendant


Chemin de données

clk

0 00

10

11

D


0 00

01

11

d

délaiT/4

strobe

resync

clk

ti

ti-1


titi-1

strobe

strobed1

0

data

OK

strobe

strobed11

data

OK

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


titi-1

strobe

strobed 0

data

OK

strobe

strobed11

data

1

1 1 plus tard !

0

OK

OK

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

0


0 00

11

01

clk

ddélai

resync

1ti

ti-1

clk

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


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

http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/s10703-012-0144-6

http://www-sop.inria.fr/members/Gerard.Berry/Papers/BerryShiple.zip

http://65.54.113.26/Publication/51142079/low-latency-and-low-overhead-mesochronous-and-plesiochronous-synchronizers







http://65.54.113.26/Conference/1923/dsd-euromicro-symposium-on-digital-systems-design




http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-72.html

Documents

Jouer avec le temps Gérard Berry Collège de France Chaire Algorithmes, machines et langages [email protected]