La compilation matérielle et logicielle dEsterel v5 /v7 Gérard Berry Chaire Algorithmes, machines et langages Collège de France Cours 6, 21 mai 2013

La compilation matérielle et logicielle d’Esterel v5 /v7

Gérard Berry

Chaire Algorithmes, machines et langages

Collège de France

Cours 6, 21 mai 2013

G. Berry, Collège de France

1. Clock-gating et weak suspend

2. Optimisation des circuits générés

3. Génération de logiciels efficaces

4. Conclusion et remerciements

21/05/2013 2

Agenda






21/05/2013 3

Agenda

G. Berry, Collège de France 21/05/2013 4

Rappel : suspension logicielle (^Z)

E'E s s s

E 's s

p p',

avec {

k

1? ,2}p' *(; p'p p'

)k,

E

ÑÑ

E's E

EE'

s

,

,

pk

ks p

E

p'

p '

Ñ Ñ1

s E

s sE

p,

p

Ñ Ñ

Alternative : règles directes pour Ñ


Klaus Schneider : suspension faible

,

,:

p p'

p

E 's E

EE '

s sE

p:k

'

k

Ñ Ñ

,

,:

pE '

p'

p

s EE

E

k

' ks p

E:s

Ñ Ñ

clock-gating dans les circuits :La logique combinatoire calcule,

mais l’état ne change pas

Le clock-gating n’est plus seulement une optimisation électrique, il reçoit une vraie sémantique !

s

weak suspend p when [immediate] s s: ps: pÑ


Impémentation logique ou électrique

logique de contrôle

FPGA, logicielvérification formelle

masquage d’horloge

(clock gating)

ASIC

Option du compilateur esterelv7

s

1

0s

7G. Berry, Collège de France 21/05/2013

Project Structure

Automatic Documentation

ProjectManagement

Executable Specification

Exporter

Debugging & Simulation

Formal Verification

DesignVerification

Sequential Equivalence

check

DUT

Optimized for synthesis

DFT-ready

SystemC & RTL flow integrationSystemC RTL Synthesis

.sc .vhd

Architecture

Design Specification Capture

Design Functional

Spec Verification Requirements

ArchitectureDiagram

Editor

Simulator

DesignVerifier

ModelReporter

Code & TestbenchGenerators

Editor

SequentialEquivalence

Checker

IDE

PlayerIDE



I absent

état de départ

état d’arrivéeexécuté


I présent

conservé

non activé


I absent

état de départ

état d’arrivéeexécuté


conservé

non activé

I présent

exécuté






21/05/2013 13

Agenda


Un tronc et quatre branches de compilation

foo.strl bar.strl

foo.eis bar.eis

all.eil

all.ein

VerilogVHDL

vérifieur formelsur Prover SL

langage noyau

Traçabilité complète pour debugging

C / C++SystemC

(équationnel)

C / C++ SystemC

rapide

circuitabstrait

optim


Le circuit d’ABRO – bon compromis logique / registres

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

optimiséloop { await A || await B }; emit Oeach R


Optimisation

• Construction du circuit bon compromis logique / registres, mais un peu gras

• Remplacement de registres par de la logique pas trop, juste le gras !

• Optimisation de la logique combinatoire chemin critique pour implémentation matérielle taille pour simulation logicielle

Simplification par relations statiquesSimplification par l’espace des états atteignables

Implémentation : SIS (Berkeley) + TiGeR


Optimisation du contrôle

Logiquecombinatoire

registres

Optimiser la logique compromis taille / profondeurThéorie et pratique très élaborées, industrie


Optimisation par réduction des entrées

Logiquecombinatoire

prédicatrestreignantles entrées

Exemple : si ( )alors( ) ( )

avec

A B A B A B

A( )moinsB cher

registres

Logiquecombinatoire


Réduction des entrées combinatoires

// relations d’entrées relation S => HS ;relation UL # UR # LL # LR ;

VLogique

combinatoireLogique

combinatoire


Réduction par états atteignables

RSS états atteignables

Exemple : si ( )alors( ) ( )

avec(

R1 R2 R1 R2 R1 R2

R1 R )moins2 cher

registres

Logiquecombinatoire

Logiquecombinatoire


• Calcul explicite– construire un par un les états atteignables avec toutes– leurs transitions : rapidement explosif !

21/05/2013 21

Calculer les états atteignables

• Calcul implicite (symbolique)– construire des prédicats Booléens représentant les– espaces d’états atteignables– représenter ces prédicats par des BDDs – Binary Decision Diagrams : NP-complet, mais – fonctionne bien en pratique quand le contrôle est dominant

Billon (Bull), Bryant (Carnegie-Mellon), Madre / Coudert / Touati (DEC), Somenzi (Boulder),The Art of Computer Programming, D.Knuth vol. 4a


Arbre de Shannon

(A B) (C D)

1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1

A

B B

C C C C

D D D D D D D D


Suppression des feuilles identiques

(A B) (C D)

1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1

A

B B

C C C C

D D D D D D D D



1 0 0 1 1 0 0 1

A

B B

C C C C

D D D D

(A B) (C D)

0 0 0 0



(A B) (C D)

1 0 0 1 1 0 0 1

A

B B

C C C C

D D D D0 0 0 0



(A B) (C D)

1 0 0 1 1 0 0 1

A

B B

C C

D D D D

0 0


Partage de sous-arbres identiques

(A B) (C D)

1 0 0 1 1 0 0 1

A

B B

C C

D D D D

0 0


Partage de sous-arbres identiques

1 0

A

BB

C

D D

(A B) (C D)


BDD Binary Decision Diagram

1 0

A

B B

C

D D

(A B) (C D)


, , : quadratique dans la taille des BDDs

21/05/2013 30

Opérations directes sur BDDs

: linéaire, ou temps 1 (variante des BDD)

f(x) y. P(x,y) : équivalent à P(x,0) P(x,1), quadratique

f(x) y. P(x,y) : équivalent à P(x,0) P(x,1), quadratique

Mais combiner ces opérations peut être exponentiel !exemple: f(x) y1 y2 yn. P(x,y1,y2,,yn)

cofacteurs f [xi 0)] f(x1,x2,,xi-1,0, xi+1, yn), f [xi 1]

linéaires

égalité : temps 1, car comparaison de pointeurs


Ordre des variables : gare à l’exponentielle !(A B) (C D)

A<C<B<DA<B<C<D

0 1

A

C C

B B B B

D D D D

1 0

A

C

B B

D D

Heuristiquesstatiques /

dynamiques


Calcul symbolique des états atteignables

nRSS R

0

0 0

1 1

n n

n

1

2

n+1

n+1

0

( )

( )

...

R

R R

( )

sto

N R

R

p s

R N R

R R N R

R Ri

A chaque étape, utiliser Ri commesimplificateur malin pour N

(Coudert, Madre)

r

ri V i( ) { | . ( ) ( ( ))}N r r' r' C ri,

i

oo ,C r( )iV

r( r,r' C )i

C

( ) { (N R N r r R)| }


ORSS sur-approximmation du RSS

||

||

;

;

p q r s t u v

( p ; q ; (r || s || t))|| (u ; v)


ORSS sur-approximmation du RSS

p q r s t u v

ORSS ( p q (r s t)) ( u v)

p ORSS(p)

p. RSS(p) ORSS(p)

incompatible ( p ; q ; (r || s || t))|| (u ; v)

p q (pq)

p q r (p q r 1)


Suppression des registres redondants

Définition : r redondant s’il peut être remplacé par une fonction des autres registres

Théorème : r0 redondant ssi RSS[r0 1] RSS[r0 0] 0

Alors on peut remplacer r0 par f RSS[r0 1]

ou par f RSS[r0 0]

Calcul seulement quadratique !faire ou ne pas faire selon la taille des cofacteurs

r0 redondant ssi f (r1, r2,, rn) t.q.

(r0, r1, r2,, rn)RSS r0 f (r1, r2,, rn)

r0 peut être remplacé par toute logique calculant f


Multiplexage de registres

||

;

|| (p || q || r) ; (s || t || u)


Multiplexage de registres

||

;

pas toujours une bonne idée,à cause du coût en logique

||démultiplexeur


heuristiques d’optimisation séquentielle

Exemple d’algorithme : calculer ORSS; simplifier la logique par ORSS; itérer jusqu’à point fixe calculer étape de RSS simplifier la logique par le résultat pour l’étape suivante itérer enlever les registres inutiles et simplifier la logique, si avantageux multiplexer les registres et simplifier la logique, si avantageux

Alternance de suppression de registres et de simplification logique, à conduire avec grand soin


L’optimisation séquentielle en pratique

WRISTWATCH nodes = 462 latches = 35 lits = 990 levels = 29initial

optimisation en vitesse (circuit matériel, FPGA)WRISTWATCH nodes = 97 latches = 12 lits = 366 levels = 3

WRISTWATCH nodes = 98 latches = 11 lits = 195 levels = 15optimisation en surface (logiciel équationnel)

Pour éviter l’explosion en taille, optimiser modulepar module (optimisation compositionnelle)






21/05/2013 40

Agenda


Logiciel équationnel : coûteux !

// bootabort pause ; // r1 emit X ; pause ; // r2 emit Y ;when s ;emit Fin ;

Une inefficacité fondamentale en logiciel :on calcule toutes les équations, coût linéaire

int boot 1, r10, r20 ;

void React () { int sel, res ; sel r1 | r2 ; res sel & !s X r1 & res // r1_K0 Y r2 & res // r2_K0 Fin sel & (r2 | s) boot 0; r1 boot ; r2 r1 & res}


• Stephen Edwards : sublinéaire– Synopsys compiler (2000)– Columbia compiler (2001)

• D. Potop– compilation efficace pour Esterel v5, GRC Graph Code

(2002)

• E. Closse, D. Weil et. al.– compilateur Saxo-RT, France Télécom (2000)

• G. Berry, M. Perreaut– compilation efficace dans Esterel v7 (Edwards / Potop)

• Klaus Schneider (Quartz, Averest)

• Partha Roop (microprocesseur spécifique)

• ...

21/05/2013 42

Compilation logicielle efficace


Logiciel impératif efficace

// sc0abort pause ; // sc1 emit X ; pause ; // sc2 emit Y ;when s ;emit Fin ;// sc3

Codage sublinéaire de l’état du programmeutilisation systématique de if-then-else et switch

int sc0 ; // switch count

void React () { XY0 ; switch (sc) case 0 : sc1; break ; case 1 : if (s) { Fin1; sc3; } else { X1; sc2; } break; case 2 : if (!s) Y1; Fin1; sc3; break; }}


Implémentation logicielle sublinéaire

(p ; q ; (r || s || t))|| (u ; v)

||

||

;

;

p q r s t u v

1 2 3

1 2

sc2

sc1



(p ; q ; (r || s || t))|| (u ; v)

||

||

;

;

p q r s t u v

1 2 3

1 2

sc12 | sc21 sc2

sc1



(p ; q ; (r ; s )|| t))|| (u ; v)

||

||

;

;

p q t u v

1 2 3

1 2

sc13 | sc21 | sc32 sc2

sc1

;

r s

1 2

sc3


input I, S;output O, Q;signal R, A in every S do await I; weak abort sustain R when immediate A; emit O || loop pause; pause; present R then emit A end end loop || loop present R then pause; emit Q else pause end end loop end everyend signal

GRC Graph Code



switch deséquenceset pauses



émissions,réceptions et dépendances

de signaux



Forks, Joins,et codes de retour




• Génération de code efficace– codage sublinéaire efficace de l’état (beaucoup de choix)– codage efficace des changements de contextes

21/05/2013 52

Suite de la compilation

• Ordonnancement statique des branches parallèles– nécessité de changement de contextes statiques entre branches– qui émettent et reçoivent des signaux

• Traitement efficace des tableaux de données ou code– expansion ou pas expansion ?– demanderait un exposé à soi tout seul...

Techniques de compilation plus classiques






21/05/2013 53

Agenda


• Esterel : un langage pour parler du temps et des événements– temps multiforme, synchronisme parfait, séquence, multi-horloge ( 2014)– signaux + séquence + parallélisme + préemption + chemins de données– causalité constructive

21/05/2013 54

Conclusion

• Des compilateurs / synthétiseurs de circuits– vers automates, logiciels équationnels, logiciels rapides– vers circuits efficaces (aussi bons ou meilleurs que ceux faits à la main)– intégrés dans des environnements de programmation

• Des systèmes de vérification formelle ( 2015)

Et des utilisateurs académiques et industriels variés

Merci à eux !


• Langages réactifs– F. Boussinot : Reactive C, SugarCubes, Junior, etc.– L. Mandel, M. Pouzet : Reactive ML– M. Serrano, GB, C. Nicolas : Hop / HipHop semaine prochaine !

21/05/2013 55

Successeurs

• Autres langages et systèmes inspirés d’Esterel– V. Saraswat : Timed Concurrent Constraint Programming– K. Schneider : Quartz, Averest– Esterel Technologies : SCADE 6– V. Saraswat, O. Tardieu et. al. : x10

• Formalismes graphiques (Esterel + Statecharts)– F. Maraninchi : ARGOS– C. André : SyncCharts– R. de Simone : profil UML MARTE


RemerciementsEsterel v1-v2 : JP. Rigault, JP. Marmorat, S. Moisan, J. Camerini, L. Cosserat, P. Couronné, G. Gonthier

Esterel v3 : R. Bernhard, F. Boussinot, JM. Tanzi, X. Fornari,

Esterel v4-v6 :, L. Henry-Gréard, D. Potop, H. Toma, J. Vuillemin

SyncCharts, machines d’exécution : Charles André, Daniel Gaffé

Esterel v7 : M. Kishinevsky, B. Pagano, M. Perreaut, L. Arditi, A. Boulan, L. Desnogues, O. Tardieu

Vérification : R. de Simone, D. Vergamini, V. Roy, JC. Madre, O. Coudert, H,. Touati, A. Bouali, K. Sunesen

Environnements : G. Kahn, C. Nahaboo, Y. Bertot, JB Saint, Equipe Esterel Studio

Esterel Technologies : E. Bantegnie, B. Dion, G. Siegel, JF. Baggioni

Collaborateurs internationaux : Ed Lee, S. Edwards, S. Ramesh, RK Shyamasundar, L. Lavagno, M. Mendler, P. Roop, E. Sentovich, R. Sethi, r. Van Hanxleden, L. Zaffallon, etc.

Documents

La compilation matérielle et logicielle dEsterel v5 /v7 Gérard Berry Chaire Algorithmes, machines et langages Collège de France Cours 6, 21 mai 2013