Parler du temps, mais de manière formelle Gérard Berry Chaire Algorithmes, machines et langages [email protected] Collège de France Cours

Parler du temps, mais de manière formelle

Gérard Berry

Chaire Algorithmes, machines et langages

[email protected]

Collège de France

Cours 1, le 2 avril 2013

mailto:[email protected]

G. Berry, Collège de France 02/04/2013 2

Agenda

1. Pourquoi parler du temps

2. Bugs et mauvais designs liés au temps

3. La question du temps

4. Circuits et échanges temps-espace

5. Circuits et logique constructive

Pourquoi parler du temps et des événements

Þ Systèmes embarqués temps-réelÞ Circuits et systèmes sur puces (SoCs)Þ Simulation de systèmes physiquesÞ Orchestration de services WebÞ Composition et interprétation musicaleÞ Neurosciences, Biologie systémique, etc.

3G. Berry, Collège de France 02/04/2013

La gestion du temps et des événementsest essentielle dans les systèmes du XXIe siècle

Mais l’informatique classique n’en parle pas !


Les systèmes embarqués du XXe siècle

• Compacts, fonctionnalités claires – centrées données : contrôle continu, traitement du signal– centrées contrôle : protocoles, écrans, gestion de modes

• Comportement déterministe– automatique fondée sur le temps– gestion déterministe des réactions à l’environnement– qui est lui non-déterministe, bien sûr

–


Les systèmes embarqués du XXe siècle

Implémentation manuellemaths manuellesspecs textuelles

codage ASM, C, ADAcompilation standard

test exhaustif

Implémentation formellemodélisation par ODEspécification formelle

codage de haut niveaucodegen automatique

vérification formelle

InfrastructurePLCs

P, ECUsOS embarqués

IHM simples


Les systèmes embarqués du XXIe siècle

• Bien plus complexes, distribués, déterministes– plusieurs fonction sur chaque SoC ou ECU, plusieurs horloges– coordination des sous-systèmes– réseaux embarqués : NoC, PAN, LAN, Time-Triggered, etc.

• Mélange de styles– contrôle continu + automates, syatèmes distribué, moins déterministes– GALS, temps continu + discret. etc.

• Interfaces asynchrones best effort depuis le Web


Les circuits du XXe siècle

• Fonctionnalité simple• Horloge unique• Physique sans souci• Pas de gestion d’énergie


Les circuits du XXIe siècle

• Nécessité de niveaux de simulation multiples Construire le logiciel avant le chip simulation TLM (Transaction Level Modeling)

• IPs multiples, horloges multiples, réseaux (NoCs) protocoles de communication et gestion d’énergie complexes


La musique du XXe siècle


La musique du XXIe siècle

Antescofo : suivi temps-réelPartition algorithmique

G. Berry, Collège de France

• Comprendre ce qui s’est passé– debugging, histoire, paléontologie, etc.– établissement des datations– recherche des causalités et des corrélations

02/04/2013 11

Objectifs

• Organiser l’avenir– prévoir ce qui peut se passer– restreindre ce qui pourra se passer– spécifier ce qui devra se passer– programmer pour que ça se passe comme spécifié– analyser et vérifier ce qu’on a spécifié et programmé

(synchronisations, timings, etc.)

Le rôle de l’historien est de prévoir le passé Henry Laurens


Agenda







Un beau bug de temps

• Lecteur MP3 / video Zune, 31 décembre 2008

year = ORIGINYEAR; /* = 1980 */while (days > 365){ if (IsLeapYear(year)) { if (days > 366) { days -= 366; year += 1; } } else { days -= 365; year += 1; }}


Un beau bug de temps

• Lecteur MP3 / video Zune, 31 décembre 2008

year = ORIGINYEAR; /* = 1980 */while (days > 365){ if (IsLeapYear(year)) { if (days > 366) { days -= 366; year += 1; } } else { days -= 365; year += 1; }}

Damned !

Fix: enlever la batterie ou attendre 24h


• Bug de la Sony (fat) PS3, 28 février 1er mars 2010– bug dans le firmware d’un processeur auxiliaire– date 1e janvier 2000 – état des jeux inaccessible ou inconsistant etc.– problème connu et déjà corrigé ailleurs !

Fix: enlever la batterie ou attendre 24h

• Bugs de l’iPhone, 2010 / 2011– heure d’hiver 2010 : correction automatique de l’heure,– mais pas du réveil ! – Le lendemain : panne de réveil !


• Dharan, 25 févier 1991, bug des missiles Patriot– les arrondis dégradent la précision de l’heure– après 110h, l’erreur est de 0.34 s– le Patriot manque le Scud– 28 soldats morts, 98 blessés

Fix: rebooter le systèmes toutes les quelques heures


Débordement de buffer

Un programme qui plante un jour par semaine


Débordement de buffer

M o n d a y

T u e s d a y

W e d n e s d a y y

Un programme qui plante un jour par semaine


Deux boules et un mur

v

chocs actions


Deux boules et un mur

Modeleurs actuels OK


Boule collée au mur modeleurs actuels

v

pour certainsmodes d’exécution


Esterel v7 pour les circuits données + contrôle


Scade 6 pour embarqué certifié : CC+FSM

SCADE 6Unifie FSM & CC

totalement mélangeables

langage fonctionneltableaux fonctionnelssémantique formellecompilateur certifié

preuve formellecompilateur prouvé?

Voir aussi Ptolemy II, Ed Lee, UC Berkeley


Nul: ordonnancement par position graphique

12

3

4

51 2

3

1

2

choix initial: parallélisme résolu par blocs


Nul: ordonnancement par ordre de création

31

5

2

41 3

2

1

2


Compliqué: réordonnancement manuel

24

1

5

31 3

2

1

2

plein de règles de renumérotationpriorités volages, cut & paste imconpréhensible, etc.


Mais pourquoi utiliser des priorités ?Le parallélisme doit être par construction

associatif, commutatif, et modulaire!

Pollution: Le parallélisme au niveau du bloc asservit les dépendances causales aux dépendances d’implémentation

La sémantique et l’implémentation doivent traiter le parallélisme, pas l’utilisateur !

Cf. Lustre, Esterel, SyncCharts, SCADE 6, Ptolemy II,...


La devise du cours

La sémantique doit suivre l’intuitionL’implémentation doit suivre la sémantique

Ne jamais dévier !


Agenda







• Perception et représentation du temps– imprécises, ambiguës, variables selon les civilisations (cf leçon inaugurale)Þ langue fleurie mais remarquablement incompétente

02/04/2013 30

Perception et langue du temps

Manifeste pour la réhabilitation du pavillon des poids et mesuresG. BerryViridis Candela, Correspondancier du Collège de ‘Pataphysique, no 1, pages 33-60 (2007)

http://www-sop.inria.fr/members/Gerard.Berry/Pataphysique/BerryPoidsEtMesures.pdf

http://www-sop.inria.fr/members/Gerard.Berry/Pataphysique/BerryPoidsEtMesures.pdf


• La nature du temps– temps physique / temps logique– temps continu / temps discret– temps plat / temps hiérarchique– temps absolu / temps multiforme

02/04/2013 31

La question du temps

• Les concepts temporels– instants, intervalles– passé, présent, futur– événements sur instants ou intervalles– précédence, causalité, corrélation– l’épaisseur de l’instant– l’épaisseur de l’action



• Le partage du temps

– comparaison ou partage du temps dans l’espace– synchronisme / asynchronisme des actions

– comment réaliser le synchronisme ?– comment synchroniser l’asynchronisme ?– comment marier les deux ?

• Le destin du futur– déterminisme / confluence / non-déterminisme– prévisibilité / imprévisibilité

• Le rapport temps/ espace– codage spatial vs. temporel de l’information– échange temps / espace dans les circuits et logiciels– rapport temps / espace dans les systèmes distribués



• Les formalismes du temps– la droite réelle de la physique classique– l’arbre de Peano des nombres 2-adiques– les logiques temporelles– les langages de spécification temporels– les langages de programmation temporels– les structures d’événements temporelles

Un domaine de recherche largement ouvert

• la vérification formelle temporelle– les outils de model-checking– la représentation du temps en Coq


• En physique, le temps est-il continu ou discret?– ça dépend de la physique !– discret est une approximation de continu, et l’inverse !

02/04/2013 34

Le temps physique

• Les instants ont-il une épaisseur ?– mesure du temps moyennage statistique

• Peut-on agir en temps zéro ?– ça dépend de la physique !

•Comment comparer le temps d’acteurs différents ?– La loooongue histoire de la mesure du temps 5 1018

– rendue très complexe par les relativités : GPS– synchronisations possibles mais chères (cf. GPS, neutrinos)– sert de base à d’autres mesures (longueurs, masses)


Le temps continu classique

t t t

] t, t’ [ [ t, t’ ]

A A AB BA

B B

événements simultanéité

Les nombres réels ne sont pas calculables

Propriétés d’instants ou d’intervalles?


Le temps discret classique

n1 n1 n

A A AB BA

B B

] n, n’ [ [ n, n’ ]

événements simultanéité

Attention à Zénon !


Le cône du temps

A B

C

DE

Sachant que j’ai déjà fait A :

si je fais B, j’aurai C

mais si je fais D, j’aurai E

Logiques temporelles arborescentes


Machine à café : anglaise ou française ?

Laquelle préférez-vous ?

€

c t

cafébof

théhmm

€

c t

caféhmm

thébof

€ €

c t

café thé

Equivalentes pour les traces linéaires (€.c.café €.t.thé)*


théhmm

02/04/2013 39

Machine à café : anglaise ou française ?

€

c t

€

c t

€ €

c t

Pas équivalentes en logiques arborescentesAG(€ EF(coffee) EF(tea))

OUI NON

café thé cafébof

caféhmm

thébof


Le double cône du temps

A B

C

B’E

Si j’avais su, j’aurais dû faire A’ au lieu de A

j’aurais eu C sans même faire B

et, en faisant B’, j’aurais eu E’, meilleur que E !

E’A’


Agenda







Circuits : confluence / synchronisme

circuit machine vibratoire parallèle confluenteà résoudre les équations parallèles synchrones

s

r

abc

s

r

s a oux b oux c r (a et b) ou (b et c) ou (c et a)

a, b, c s, r


Temps logique vs. temps physique

i6

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

i6

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

temps logique

temps physique

cycle d’horloge OK pas de recouvrement(voltage et horloge peuvent être irréguliers)


L’addition dans l’espace

++

a0b0

s0

++1

a

1b

1s

r 1

++2a

2b2s

2r

3r

r = 00

pour n bits,temps ntrop cher


Addition dichotomique de von Neumann

Spéculation :perdre de l’espace pour gagner du temps.

propager les retenues par dichotomie

a

b

s a+b

s’ a+b+1n

n

n+1

n+1

en parallèle



n

n

n+1

n+1a[n..2n-1]

b[n..2n-1]

a[0..n-1]

b[0..n-1]

s[0..n-1]

s’[0..n-1]n

n

n+1

n+1 0..n-1

0..n-1

s[n..2n]

n

01

n

s’[n..2n]01

Pour 2n bits:

Spéculation microprocesseurs



pour n bits,temps log2(n)

optimal


L’additionneur de von Neumann en Jazz

vNAdd1 (a, b) = (s : net [2], s' : net [2]) { s’[0] = a ^ b; s'[0] = ~ s [0]; s’[1] = a & b; s'[1] = a | b;}

ab

s

s’1

1

2

2


vNAdd (n) (a : net [n], b : net [n]) = (s : net [n+1], s' : net [n+1]) { if (n==1) { (s, s') = vNAdd1(a [0], b [0]); } else { // Lower half n' = n div 2; (l, l') = vNAdd (n') (a [0..n'-1], b [0..n'-1]) ; // Upper half n'' = n - n'; (h, h') = vNAdd (n'') (a [n'..n-1], b [n'..n-1]) ; // Get the low bits out s’[0..n'-1] = l’ [0..n'-1]; s'[0..n'-1] = l’ [0..n'-1]; // Get the high bits out, muxed on l[n'] or l'[n'] for (k <= n'') {

local k' = n' + k; // n’ <= k' < n s[k'] = mux (l [n'], h’ [k], h [k]); s'[k'] = mux ( l’ [n'], h’ [k], h’ [k]);

} }}


Addition par composition

Fonction de propagation de retenue pour 2 bits a et b

0 00, 0

1 0

1, 0 0 0

0, 1 1 1

0 11, 1

1 1

a b

a b

a b

a b


Soit la fonction de propagation pour et La retenue entrante à la position i+1 se calcule par

On calcule la composition dichotomiquementet en parallèle

))()(())()(( 01234567 ffffffff

)0)((

))))))))0((((((((

01234567

01234567

ffffffff

ffffffff

if ia ib


Représentation des fonctions

Appliquer f à x :

01

f0f1

f(x)

x

Apply (f, x) y { (f0, f1) f y mux(x, f1, f0)}

f f0 valeur f(0)f1 valeur f(1)

{


Composer

comp (f, g) (h0, h1) { (f0, f1) f; h0 app (g, f0); h1 app (g, f1);}

01

g0g1

(gof)0

01

g0g1

f0

f1

(gof)1


comp

app


Addition par composition en Jazz

CompAdd (n) (a : net[n], b : net[n], c) = (s : net[n], f) { if (n == 1) { s[0] = a[0] ^ b[0] ^ c; f0 = a[0] & b[0]; // carry out if carry in is 0 f1 = a[0] | b[0]; // carry out if carry in is 1 f = (f0, f1); // carry propagation function } else { n' = n div 2; (s[0..n'-1], fl) = CompAdd (n') (a[0..n'-1], b[0..n'-1], c); (s[n'..n-1], fh) = CompAdd (n-n') (a[n'..n-1], b[n'..n-1], c'); f = comp (fl, fh); c'= app (fl, c); }}


Addition sans retenue (base molle)

Nombre mou a (a’, a") valeur de a : |a| a'+a"

0 (0,0)1 (1,0) (0,1)2 (2,0) (1,1) (0,2)3 (3,0) (2,1) (1,2) (0,3)4 (4,0) (3,1) (2,2) (1,3) (0,4)

L'addition des nombres mous se fait en temps constantquel que soit le nombre de bits


mou dur = mou

+ + + + + + + +

c a ba mou, b dur

c' c'' = a' a'' b

a’0 a’’0 b0 a’1 a’’1 b1 a’2 a’’2 b2 a’3 a’’3 b3

c’1 c’’1 c’2 c’’2 c’3 c’’3 c’4 c’’4

00

c’0 c’’0


mou mou = mou

+ + + + + + + +

+ + + + + +

0

c a b c' c'' a' a'' b' b''

0 0 0 0a' a'' b' b'' 1 1 1 1a' a'' b' b'' 2 2 2 2a' a'' b' b'' 3 3 3 3a' a'' b' b''

0 0c' c'' 1 1c' c'' 2 2c' c'' 3 3c' c'' 4 4c' c''


Multiplication en temps logarithmique

3 2 1 03 3 3 3

3 2 1 02 2 2 2

3 2 1 01 1 1 1

3 2 1 00 0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

vNAdd

+

+

+

mou

i ji jic a b pour n bits,

taille n2

temps log2(n)

optimal


Agenda







Logique Booléenne constructive

I e 0

I e et e’ 0

I e’ 0

I e et e’ 0

I e 1

I e et e’ 1

I e’ 1

I e 1

I e ou e’ 1

I e’ 1

I e ou e’ 1

I e 0

I e ou e’ 0

I e’ 0

I e 0

I non e 1

I e 1

I non e 0

• Vecteur d’entrées : I entrées → {0,1}

• Formules : I e b

I I I(I)

X e I e b

I X b


Constructive Pas de tiers exclu !

I e ou non e 1

ssi I e 0 ou I e 1

I e ou non e 1


Circuit réseau de preuves constructives

ss

r

abc r

Chaque exécution déroule son arbre de preuve

Le circuit regroupe tous les arbres en un DAG

Cf. correspondance de Curry-Howard


Temps logique vs. temps constructif

Temps logiqueo6

i7i5i1 i2 i6i4i3

o7o5o4o3o1 o2

Temps constructif

o6

i7i5i1 i2 i6i4i3

o7o5o4o3o1 o2


Partage de ressources cycles combinatoires

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

Trouvé correct par la sémantique constructivePour F, G, H, etc, la version cyclique

est linéaire mais la version acyclique exponentielle en taille

F

G

C

C

I O

C10

10

10



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

cycleF

G

C

C

I O

C10

10

10



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



F

G

0

I O

010

10

10

0

Le cycle ne pose ni problème logique,ni problème électrique !

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


Scheduler cyclique round-robin-4

okreq

req

ok

req

ok

reqok



Cycle combinatoire !

okreq

reqok



le cycle est saincar coupé à une porte ou

okreq

reqok

1

trouvé correct parla sémantique constructive



okreq

reqok

Le registre à 1change à chaque cycle

trouvé correct parla sémantique constructive1


Round-Robin Cyclic Scheduler-2

okreq

reqok

Le cycle est malsain sitous les registres sont à 0

trouvé incorrect parla sémantique constructive


Les trois sortes de circuits cycliques

2. Electriquement et logiquement malsainsX XX non X

ex. : round-robin cyclique avec tous les registres à 0

1. Electriquement et logiquement sains, éventuellement sous restrictions d’entrées ou invariants temporels des registres (voir les exemples précédents)


Analyse des circuits cycliques

Quand un circuit se stabilise-t-il pour tous délais des fils et portes?

Comment relier le temps discret de la logique au temps continu de l’électricité?


Circuits cycliques constructifs

Hamlet : ToBe ToBe or not ToBe

ToBe

• Se stabilise à 1 pour certains délais des portes et fils, mais oscille pour d’autres délais

• Calcule 1 en logique classique, mais ne calcule rien en logique constructive

Théorème (Mendler-Shiple-Berry 2001-2012) : calcule 1 électriquement pour tous délais calcule vrai en logique constructive (tiers exclu)


La logique constructive UN


Le circuit ABRO (réseau de preuve)

loop abort { await A || await B }; emit O ; halt when Rend loop

supprimépar optimisation


A suivre...

Documents

Parler du temps, mais de manière formelle Gérard Berry Chaire Algorithmes, machines et langages [email protected] Collège de France Cours