Temps, événements et causalité en informatique Gérard Berry Chaire Algorithmes, machines et...

Temps, événements et causalitéen informatique

Gérard Berry

Chaire Algorithmes, machines et langages

Collège de France

Leçon inaugurale, 28 mars

2013

G. Berry, Collège de France 28/03/2013 2

Film d’Emilie, 2 ans et 1 semaine,au clavier et à la souris

Comment verrait-elle l’ordinateur comme une nouvelle technologie, alors qu’il est plus vieux qu’elle ?

G. Berry, Collège de France 28/03/2013 3

Pourquoi ce titre de chaire ?

algorithmes

information

machineslangages

science de construction science d’observation mais aussi exploration de nous-mêmes

interfaces

Pourquoi ce titre de cours ?

Þ 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.

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 !

28/03/2013 4G. Berry, Collège de France

G. Berry, Collège de France 28/03/2013 5

Les systèmes embarqués

• XXe siècle : compacts, fonctionnalités claires– contrôle moteur, freinage, etc.– fonctions déterministes et non corrélées

• XXIe siècle : complexes, distribués – fonctions corrélées : freinage, suspension, etc.– et intégrées : conduite automatique de la voiture– et couplées au GPS, connectées à Internet, etc.

Comportements temporels / événementiels

G. Berry, Collège de France 28/03/2013 6

Des circuits aux systèmes sur puces

1980’s : M68000- 68 000 transistors- une fonction- une horloge

2010 : SoCÞ 680 000 000 transistorsÞ beaucoup de fonctionsÞ plusieurs horlogesÞ simulation logicielle rapide

G. Berry, Collège de France 28/03/2013 7

Musique : homme / électronique

Partition algorithmique?

G. Berry, Collège de France 28/03/2013 8

La langue du temps

sur le champà tout bout de champ

se lever dès potron-minetse coucher avec les poules

dans la nuit des tempsau bon vieux temps,c’était le bon tempsjamais, au grand jamais

de mon tempsje prends mon temps

un bout de tempsun bon bout de temps

9G. Berry, Collège de France 28/03/2013

illico prestoen moins de temps qu’il n’en faut pour le dire

on a le temps de tuer un âne à coup de figues (molles)

le temps passe vite unité?de longues minutes montre en main ?

10G. Berry, Collège de France 28/03/2013

Yantra Mandir, Jaipur, ~1730

11G. Berry, Collège de France 28/03/2013

Yantra Mandir, Jaipur, ~1730

G. Berry, Collège de France 28/03/2013 12

La flèche du temps

passé futurprésent

durée

Dans le passé, il y avait plus de futur que maintenantLe Chat

3h15mn 3h15mn

date0

Vous avez dit 0 ? non, le 01/01 à 0h00 !

G. Berry, Collège de France 28/03/2013 13

Le temps continu mathématique

t t t

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

A A AB BA

B B

événements simultanéité

G. Berry, Collège de France 28/03/2013 14

Le temps discret mathématique

n1 n1 n

A A AB BA

B B

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

événements simultanéité

15G. Berry, Collège de France

La causalité est-elle transitive ?

28/03/2013

Précédence et causalité

précède

cause

il pleut donc je prends mon parapluie donc je suis sec

il pleut donc je suis sec

16G. Berry, Collège de France 28/03/2013

Logique temporelle linéaire

le débogage, l’histoire et la biologiescrutent les causalités à partir des précédences

(Pluie BeauTemps)

toujours un jourcause?

prédicats instantanés

Après la pluie, le beau temps

t. Pluie(t) t’>t. BeauTemps(t’)

G. Berry, Collège de France 28/03/2013 17

Amour un jour, amour toujours

( amour) ( amour)

( amour) ( amour)

G. Berry, Collège de France 28/03/2013 18

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

G. Berry, Collège de France 28/03/2013 19

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’

20G. Berry, Collège de France 28/03/2013

1. L’épaisseur de l’instant

2. L’échange temps-espace

3. L’horloge, mécanisme d’abstraction

4. Le temps multiforme

5. Le continu et le discret

G. Berry, Collège de France 28/03/2013 21

L’épaisseur de l’instant

• Charlemagne a été couronné en l’an 800

abc

s

r

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

++

ab

s

cr

oux

ouet

et

et

• Circuits : additionneur 3 bits

G. Berry, Collège de France 28/03/2013 22

L’épaisseur de l’instant

s

r

abc

G. Berry, Collège de France 28/03/2013 23

L’épaisseur de l’instant

s

r

abc

G. Berry, Collège de France

ss

28/03/2013 24

L’épaisseur de l’instant

r

abc r

chemin critique chemin de temps de stabilisation maximal

G. Berry, Collège de France 28/03/2013 25

attente du délai critique équations résolues!circuit machine parallèle vibratoire

à 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

G. Berry, Collège de France 28/03/2013 26

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

G. Berry, Collège de France 28/03/2013 27

Addition dichotomique de von Neumann

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

G. Berry, Collège de France 28/03/2013 28

Addition dichotomique de von Neumann

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:

parallélisme spéculation accélération

G. Berry, Collège de France 28/03/2013

Addition dichotomique de von Neumann

pour n bits,temps log2(n)

optimal

64 64

29

64 6

G. Berry, Collège de France 28/03/2013 30

L’addition dans le temps

++

ab

s

r

a 1 21000000....

b 3 21100000....

tick !

horloge

s ? 2???????....

G. Berry, Collège de France

s ? 2???????....s ? 20??????....

28/03/2013 31

L’addition dans le temps

++

ab

ss

rr

tick ! tick

a 1 21000000....

b 3 21100000....

G. Berry, Collège de France 28/03/2013 32

L’addition dans le temps

++

ab

ss

rr

tick !

a 1 21000000....

b 3 21100000....

s ? 20??????....

G. Berry, Collège de France 28/03/2013 33

L’addition dans le temps

++

ab

ss

rr

tick !

a 1 21000000....

b 3 21100000....

tick

a

s ? 20??????....s ? 200?????....

G. Berry, Collège de France 28/03/2013 34

L’addition dans le temps

++

ab

ss

rr

tick !

a 1 21000000....

b 3 21100000....

ab

s

r

tick

s ? 200?????....s ? 2001????....

G. Berry, Collège de France

sss

s ? 2001????....

28/03/2013 35

L’addition dans le temps

++

ab

rr

tick !

a 1 21000000....

b 3 21100000....

ab

r

Marche pour un nombre quelconque de bits,même infini nombres 2-adiques

G. Berry, Collège de France 28/03/2013 36

Soutraction nombres 2-adiques

++

ab

s

r

a 1 21000000....

b 3 21100000....

tick !

horloge

s 2 2011111....

On a a + b + 1 s + 2rmais b + b 1donc s ab CQFD

G. Berry, Collège de France 28/03/2013 37

Quelques beaux additionneurs

++

++

++

pipeline

++

stéréo

++

++

2 par 2

sans retenue

G. Berry, Collège de France 28/03/2013 38

Temps logique vs.temps physique

temps logique

temps physiquei6

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

i6

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

contrainte d’horloge : pas de recouvrementmême si l’horloge est irrégulière

G. Berry, Collège de France 28/03/2013 39

Circuits synchrones vs. asynchrones

……

entrées sorties

synchronedépendant du tempslogique BooléenneCAO très efficace

très répandu

registers

sortiesentrées

val val

stop prêt

asynchroneindépendant du temps

pas d’horloge, mais fils2logique plus complexe

CAO difficilepeu répandu

Logique

G. Berry, Collège de France 28/03/2013 40

Circuits élastiques

sortiesentrées

valval

stopprêt

filtres d’horloge

J. Cortadella, M. Kishinevsky et. al.

logique Booléenne standard + registres + horloges

logique asynchrone + filtres d’horloge

CAO synchrone standardinsensible à l’horlogeinsensible aux bulles

facile de couper les fils longs

41G. Berry, Collège de France 28/03/2013

Horloges multiples

donnéesh h’

synchronisons nos montres

h et h’ non synchronisables

G. Berry, Collège de France 28/03/2013 42

Métastabilité

0

1

0

1

G. Berry, Collège de France 28/03/2013 43

Le ballon sur la colline

0 1 0 1

44G. Berry, Collège de France 28/03/2013

Le synchroniseur 4 phases – fragile !

donnéesh h’

G. Berry, Collège de France 28/03/2013 45

Temps multiforme hiérarchique

Second

Meter Lap

Step

Hour Morning

HeartBeat HeartAttack

46G. Berry, Collège de France

abort run Slowly when 100 Meter ;

every Morning do

end every

loop

each Lap

abort every Step do run Jump || run Breathe end every when 15 Second ;

trap HeartAttack in

|| CheckHeart

exit HeartAttack

handle HeartAttack fo run RushToHospitalend trap

abort

when 4 Lap

28/03/2013

Le coureur Esterel

abort run Slowly when 100 Meter ;

run FullSpeed

47G. Berry, Collège de France 28/03/2013

Exécution cyclique

lire les entrées

calculer la réaction

générer les sorties

Synchrone délai 0 dans le même cycle

temps logique

i6

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

i6

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

temps physique

WCET

G. Berry, Collège de France 28/03/2013 48

Scade 6 pour l’embarqué certifié

SCADE 6

langage fonctionnelsémantique formellecompilateur certifié

Voir aussi Ptolemy II (Ed Lee), Averest (K. Schneider)

G. Berry, Collège de France 28/03/2013 49

Temps multiforme irrégulier

Thomas Morley1557-1602

Gustav Mahler1860-1911

50G. Berry, Collège de France 28/03/2013

Symphonie d’instruments à ventsIgor Stravinsky

Source Clément Lebrun, Octobre 2012

G. Berry, Collège de France 28/03/2013 51

De la sémantique à l’exécution

Langagemodèle

mathématique

représentationsintermédiaires

C, C++SystemC

VerilogVHDL

embarquésimulateurs

vérification automatiqueSAT, SMT, BDDs

Coqvérification

de théorèmes

G. Berry, Collège de France 28/03/2013 52

Electricité et logique constructive

Hamlet : ToBe ToBe or not ToBe

ToBe

Þ calcule 1 électriquement pour certains délais, mais oscille pour d’autres

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

- calcule vrai (1) en logique classique,mais les électrons ne sont pas au courant !

G. Berry, Collège de France 28/03/2013 54

Deux boules et un mur

v

chocs actions

G. Berry, Collège de France 28/03/2013 55

Deux boules et un mur

Modeleurs actuels OK

G. Berry, Collège de France 28/03/2013 56

Boule collée au mur modeleurs actuels

v

pour certainsmodes d’exécution

G. Berry, Collège de France 28/03/2013 57

Analyse constructive non-standard

v

infinitésimal

58G. Berry, Collège de France 28/03/2013

Pierre Desproges

Tout chercheur plongé dans la sciencesubit une poussée de bas en haut susceptible de lui remonter le moral

59G. Berry, Collège de France 28/03/2013

FIN