Parler du temps, mais de manière formelle Gérard Berry Chaire Algorithmes, machines et langages...

Parler du temps, mais de manière formelle

Gérard Berry

Chaire Algorithmes, machines et langages

gerard.berry@college-de-france.fr

Collège de France

Cours 1, le 2 avril 2013

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

chocs actions

Deux boules et un mur

Modeleurs actuels OK

Boule collée au mur modeleurs actuels

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

choix initial: parallélisme résolu par blocs

Nul: ordonnancement par ordre de création

Compliqué: réordonnancement manuel

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)

• 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’ ]

A A AB BA

é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

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

événements simultanéité

Attention à Zénon !

Le cône du temps

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 ?

cafébof

théhmm

caféhmm

thébof

€ €

café thé

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

théhmm

02/04/2013 39

Machine à café : anglaise ou française ?

€ €

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

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

o7o5o1 o2 o6o4o3

i7i5i4i3i1 i2

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

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

s’ a+b+1n

en parallèle

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+1 0..n-1

0..n-1

s[n..2n]

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;}

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

0, 1 1 1

0 11, 1

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

01234567

ffffffff

if ia ib

Représentation des fonctions

Appliquer f à 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);}

(gof)0

(gof)1

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

c’0 c’’0

mou mou = mou

+ + + + + + + +

+ + + + + +

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

i ji jic a b pour n bits,

taille n2

temps log2(n)

optimal

Agenda

Logique Booléenne constructive

I e et e’ 0

I e’ 0

I e et e’ 0

I e et e’ 1

I e’ 1

I e ou e’ 1

I e’ 1

I e ou e’ 1

I e ou e’ 0

I e’ 0

I non 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

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

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

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

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

cycleF

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

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

Cycle combinatoire !

le cycle est saincar coupé à une porte ou

trouvé correct parla sémantique constructive

Le registre à 1change à chaque cycle

trouvé correct parla sémantique constructive1

Round-Robin Cyclic Scheduler-2

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

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

Parler du temps, mais de manière formelle Gérard Berry Chaire Algorithmes, machines et langages...

Documents

Gérard Berry - Collège de France

Programme UP Berry 2008/ 2009

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

Analyse formelle des protocoles cryptographiques

Quelle éducation formelle et houraye

L’UP Berry a 40 ans

Analyse Formelle des Concepts - CanalBlog

Portes basculantes Berry

Les caractéristiques de l’éducation non formelle

Génétique formelle ou hérédité monofactorielle

Gérard Berry - Sésamath

Spécification, Analyse et Vérification formelle des

Giennois • Puisaye • Berry Berry - Le Renouveau - Des

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

LA QUALITÉ EMBELLIT VOTRE VIE - centraleduparquet.frcentraleduparquet.fr/brochures-telechargeables/berry-wood-2010.pdf · 6 - Berry Floor Berry Floor - 7 1 2 3 1er temps : assemblage

Врати Berry с въртеливо-постъпателен ходstar-2002.com/.../wp-content/uploads/2016/03/85187-Berry-Tore-BG.pdf · в предпочитания цвят

Berry (France)

Comment écrire une lettre formelle ?

Formation formelle vers l'informelle

Akkari berry