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

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 ?


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


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


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


Musique : homme / électronique

Partition algorithmique?


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 ?


Yantra Mandir, Jaipur, ~1730


Yantra Mandir, Jaipur, ~1730


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 !


Le temps continu mathématique

t t t

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

A A AB BA

B B

événements simultanéité


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


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


Amour un jour, amour toujours

( amour) ( amour)

( amour) ( amour)


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


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’


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


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



s

r

abc



s

r

abc

G. Berry, Collège de France

ss

28/03/2013 24


r

abc r

chemin critique chemin de temps de stabilisation maximal


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


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

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:

parallélisme spéculation accélération

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


pour n bits,temps log2(n)

optimal

64 64

29

64 6


L’addition dans le temps

++

ab

s

r

a 1 21000000....

b 3 21100000....

tick !

horloge

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


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

28/03/2013 31


++

ab

ss

rr

tick ! tick

a 1 21000000....

b 3 21100000....



++

ab

ss

rr

tick !

a 1 21000000....

b 3 21100000....

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



++

ab

ss

rr

tick !

a 1 21000000....

b 3 21100000....

tick

a

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



++

ab

ss

rr

tick !

a 1 21000000....

b 3 21100000....

ab

s

r

tick

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


sss

s ? 2001????....

28/03/2013 35


++

ab

rr

tick !

a 1 21000000....

b 3 21100000....

ab

r

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


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


Quelques beaux additionneurs

++

++

++

pipeline

++

stéréo

++

++

2 par 2

sans retenue


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


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


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


Horloges multiples

donnéesh h’

synchronisons nos montres

h et h’ non synchronisables


Métastabilité

0

1

0

1


Le ballon sur la colline

0 1 0 1


Le synchroniseur 4 phases – fragile !

donnéesh h’


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


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


Scade 6 pour l’embarqué certifié

SCADE 6

langage fonctionnelsémantique formellecompilateur certifié

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


Temps multiforme irrégulier

Thomas Morley1557-1602

Gustav Mahler1860-1911


Symphonie d’instruments à ventsIgor Stravinsky

Source Clément Lebrun, Octobre 2012


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


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 !


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


Analyse constructive non-standard

v

infinitésimal


Pierre Desproges

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


FIN

Documents

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