Lélectricité est constructive : un modèle intuitionniste de la stabilisation électrique des circuits cycliques Gérard Berry Collège de France Chaire Algorithmes,

L’électricité est constructive :un modèle intuitionniste de la stabilisation

électrique des circuits cycliques

Gérard Berry

Collège de FranceChaire Algorithmes, machines et langages

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

Cours 7, 26 mars 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. Pourquoi les circuits cycliques

2. Les trois sortes de cycles

3. La logique temporelle UN

4. Codage des circuits dans UN

5. Déductions et simulations

6. Les théorèmes

7. Débarrassons-nous du temps !

26/03/2014 2







6. Les théorèmes


26/03/2014 3

G. Berry, Collège de France 26/03/2014 5

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



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



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


Ordonnanceur round-robin à jeton

okreq

req

ok

req

ok

reqok



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


• Buffer circulaire 16 octets arrivant aléatoirement

• Longueur dépendant du premier octet puis des suivants

• Longueur potentiellement quelconque

• Design naturellement cyclique et dur à rendre acyclique

26/03/2014 14

ILD Instruction Length Decoder

1

2

3

5

4

6







6. Les théorèmes


26/03/2014 15


• Mauvais : pas de stabilisation électrique, pas de solution logique unique X X X X

26/03/2014 16

Les trois sortes de circuits cycliques

• Bons : stabilisation électrique, solution logique unique exemples précédents

X

• Bizarres : solution logique unique, mais stabilisation électrique dépendant des délais des fils et portes X X X

DE

pas de stabilisation électriqueen partant de X0 avec D2 et E5


• Calcule 1 en logique classique mais pas en logique constructive (sans tiers exclu) !

26/03/2014 17

Electricité Logique constructive ?

Hamlet : ToBe ToBe or not ToBe

ToBe

Peut-on caractériser logiquement les « bons circuits », i.e.,ceux qui se stabilisent électriquement à cause de la propagation toute bête des signaux des entrées jusqu’aux sorties ?


• Etudier de façon vraiment formelle la relation entre une vision « raisonnablement électrique » et une vision logique

• Modéliser la stabilisation, en faisant l’impasse sur les transitoires et autres phénomènes électriques non pertinents pour le besoin

• Aller de la théorie aux algorithmes pratiques : détection de correction, construction d’un circuit acyclique équivalent, vérification formelle par rapport à un autre circuit

26/03/2014 18

Notre objectif

Théorème (Mendler-Shiple-Berry):circuit constructif sorties électriquement stable vers une valeur unique pour tous délais Û sorties calculable vers 0 ou 1 en logique constructiveÛ sorties 0 ou 1 dans le point fixe en logique ternaire {, 0, 1} algorithmes pour tester la stabilité électrique


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


• Règles dérivables :

26/03/2014 20

Intuitionnisme absence de tiers exclu

I ⊢ e 1

I ⊢ e e 1

• Règle non dérivable – le vrai tiers exclu :

• Fait électrique :– l’électricité est intuitionniste,– car les électrons ne sont pas au courant du tiers exclu !

• Principe intuitionniste : pour prouver e e’, il faut prouver e ou prouver e’

I ⊢ e 0

I ⊢ e e 1

I ⊢ e e 1







6. Les théorèmes


26/03/2014 21


• Portes logiques : délai nul, groupement possible– notation polynomiale : y1 x, s2 s1xs2 s1xs2

• Nœuds explicites pour les délais

• Au minimum un délai par cycle

26/03/2014 22

Circuits avec délais

d2

d1


Histoires « électriques »

Histoire : h : ℝ+→ Bn continue à droite (avec B {0,1})

1

0

0

Intervalle semi-ouvert : t,u , t u { | t u } souvent noté t,u

t u

Tranche d’histoire : ht,u : la partie de h dans l’intervalle [t,u

Tranche d’histoire : h0,∞ h

Satisfaction d’un prédicat P par une tranche : ht,u ⊨ P

modèle

u


Délai « électrique » UN et stabilité d

d

d

d

Délai UN : dℝ+

h

h’

t td

ht,ub et td u h’td,ub

• Une histoire h est stable à b après un délai d si hd,∞ b• Sinon, h est dite instable ou oscillante


Circuits UN-constructifs

Définition : un circuit est UN-constructif pour des d’entrées stables et un jeu de délais si toutes ses sorties se stabilisent vers les mêmes valeurs dans toute exécutionDéfinition : un circuit est uniformément UN-constructif pour des entrées stables s’il est UN-constructif pour tout jeu de délais.

Définition : un circuit est uniformément UN-constructif s’il est uniformément UN-constructif pour toutes entrées stables


Les prédicats UN et le modèle temporel

ht,u ⊨ R : si t,u. hR i.e., l’histoire h reste dans la région R entre t et u

: R d

R Bn : région prédicat booléen à n variables booléennes ex. : x y y z ou encore Ø (vide, faux) (n.b. : symboles utilisés pour les prédicats)

ht,u ⊨ x y dans h, x est stable à 1 et y stable à 0 ht,u ⊨ x y entre t et u

ht,u ⊨ x dans h, x est stable à 1 entre t et u

ht,u ⊨ x dans h, x est stable à 0 entre t et u


Conjonction, disjonction et délai

ht,u ⊨ ssi ht,u ⊨ et ht,u ⊨ ht,u ⊨ ssi ht,u ⊨ ou ht,u ⊨

ht,u ⊨ d ssi td u et htd,u ⊨ est constamment satisfait après un délai d dans t,u

t u u

ht,u ⊨ dx

td

ht,u ⊨ x

1

0

0


• Objectif : représenter la porte not– x stable à 1 : ht,u ⊨ x– opposé logique : ht,u ⊨ x– mais l’opposé logique est satisfait par tout signal

instable– or nous voulons x stable à 0, i.e. x x, ce qui est

différent!

26/03/2014 28

La négation constructive

ht,u ⊨ ssi t’,u’t,u. ht’,u’ ⊨ n’est jamais satisfaite par h sur t,u différent de n’est pas satisfaite par h !

1

0

0 t uni ht,u) ⊨ x ni ht,u) ⊨ x


• Implication notée pour éviter la confusion avec doit utiliser les sous-intervalles, car x x Ø

26/03/2014 29

Implication, équivalence

ht,u ⊨ si t’,u’t,u. ht’,u’ ⊨ ht’,u’ ⊨


30G. Berry, Collège de France 26/03/2014

Résumé des règles de la logique UN

ht,u ⊨ si ht,u ⊨ et ht,u ⊨

ht,u ⊨ si ht,u ⊨ ou ht,u ⊨

ht,u ⊨ R si t,u. hR


ht,u ⊨ si t’,u’t,u. ht’,u’ ⊨


ht,u ⊨ d si td u et htd,u ⊨

Notation : ⊨ ssi h,t,u. ht,u ⊨ ht,u ⊨


Propriétés de la logique UN

x stable dans ht,u ht,u ⊨ x x

• La logique exprime bien la stabilité :

noté x

• Le tiers exclu est faux en général ex. : h[t,u ⊨ x x si h instable pour x dans [t,u• La disjonction est intuitionniste : elle choisit son camp

ht,u ⊨ ht,u ⊨ globalement

ou ht,u ⊨ globalement







6. Les théorèmes


26/03/2014 32


• Principes : coder les circuits par des formules– coder les valeurs d’une entrée par 0x pour 1 et 0x pour 0– coder les portes directement par les opérateurs booléens– coder les délais par des « affectations à retard » :

26/03/2014 33

Codage des circuits

• Exemple :

zx

ys1de s2

z x y y s1 s2 s1 d y s2 e y

s1 d s1s2

s2 e s1 s2 : forme normale

des délais

stabiliser les délais stabilise tous les fils !

y d x défini par x dy yx ou équivalent x dy)x dy


circuit C avec x1 : (C,x C 0x

circuit C avec x0 : C,x C 0x

cas général : circuit C avec valeurs d’entrées I : C,I

d2

d1

C s1 d1 x s2 d2 xs1s2


Théorème 1: bonne représentation des circuits une histoire h est UN-correcte pour C et les entrées I ssi h ⊨ C,I

Corollaire : caractérisation UN de la constructivité Un circuit C est constructif pour les délais donnés et une entrée I ssi il existe une unique valeur S des variables d’état et un délai d tels que C,I ⊨ dS







6. Les théorèmes


26/03/2014 36


Formules du calcul déductif : ⊢ vs. ⊨

Région temporisée : dR

Région temporisée : kK k pour K fini ou infini

kK k?

C,I ⊨ modèle :

C,I ⊢

• Séquents syntaxiques

sS s d e)

xI1 0x yI0 0y

clauses de Horn ⊢


Calculs déductions (Curry Howard)

1. C,I ⊢ dR

ssi il existe une séquence d0R0, d1R1,..., dnRn dR

telle que, pour tout i, di est dans (i.e., une entrée)

ou dérivable des dj, ji par une règle de déduction

2. C,I ⊢ kK k

ssi il existe un kK tel que C,I ⊢ k


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


d2

d1

max(d1,d2) s1s2

cas x0i.e. 0x


0x0x

d1s1

chain0xs1s2

bool

d2s2

chain

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

join


cas x1i.e. 0x

0xchain

d1xs1s2bool

d1d2s2

chain

joind1s1

0xchain

d1s1

max(d1, d1d2) s1s2

d2

d1


x1 région s1s2 atteinte en temps d1d2







6. Les théorèmes


26/03/2014 42


• Théorème 2 : équivalence de ⊨ et ⊢ pour les circuits

26/03/2014 43

Les théorèmes centraux

C,I,. C,I ⊨ C,I ⊢

• Théorème 3 : Intuitionnisme de ⊨

C,I,. C,I ⊨ . C,I ⊨

Une disjonction, même infinie, ne peut être validéeque par un de sens membres (résulte immédiatementdu théorème 2 et de la définition de C,I ⊢ )


Corollaire : déterminisme de la stabilisationSoit s un délai de C et I un vecteur d’entrées. Alors les histoires h de s dans C,I ont deux comportements possibles :

1. tous les h se stabilisent à la même valeur2. il existe au moins une histoire oscillante

un circuit est constructif ssi ses sorties ne peuvent pas osciller

Preuve : soit 1s 1s 2s 2s 3s 3s ...Preuve ::alors (infini) dit que s se stabilise un jour

cas 1 : C,I ⊨ . Alors C,I ⊨ k pour un k par thm.3

(intuitionnisme), par exemple k ms.

Donc h. h ⊨ C,I h ⊢ ms, tout h devient stable à 1cas 2 : C,I ⊨ . Alors h. h ⊨ C,I h ⊨ est impossible,

donc h. h ⊨ C,I h ⊨ , et cet h oscille pour s

Le résultat central







6. Les théorèmes


26/03/2014 45


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

48G. Berry, Collège de France

• Pour des délais fixés, la UN-prouvabilité vs. ⊢ est une

CNS pour la UN-stabilisation vs. ⊨

26/03/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

49G. Berry, Collège de France

• Etude complète de la stabilisation des circuits cycliques

dans le modèle de délais UN, en reliant modèle ⊨ et

déduction syntaxique ⊢, et en ignorant transitoires, oscillations, métastabilité etc. (qu’on peut aussi étudier)

26/03/2014

Conclusion

• stabilisation électrique prouvabilité constructive booléenne

(avec délais) des sorties (sans délais)

• A suivre au prochain cours : – constructivité pour toutes entrées– constructivité des circuits séquentiels (avec registres)– algorithmes efficaces de calcul de la constructivité


Références

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

Asynchronous CircuitsJ. Brzozowski et C-J. Seger.Springer-Verlag (1995).

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

Documents

Lélectricité est constructive : un modèle intuitionniste de la stabilisation électrique des circuits cycliques Gérard Berry Collège de France Chaire Algorithmes,