Emmanuelle Encrenaz-Tiphène Laboratoire d’Informatique de Paris VI

E. Encrenaz-Tiphène LIP6 – séminaire LSV 1/06/04

Vérification par modèle de parties de SoCExpérimentations et enrichissement d’outils de vérification

existants

Emmanuelle Encrenaz-Tiphène

Laboratoire d’Informatique de Paris VI

Architecture des Systèmes Informatiques et Micro-électroniques

En collaboration avec

Cédric Roux, Vincent Beaudenon, Cécile Braunstein, Hervé Charlery,

Jean-Lou Desbarbieux, Sami Taktak


Qu’est-ce qu’un SoC (System on Chip) ?

Intégration d’une application complexe sur un unique circuit

– Un ou plusieurs processeurs exécutant des programmes (implantant un micro-noyau)

– Des coprocesseurs

– Des mémoires

– Des media de communication

– Des parties reconfigurables (FPGA)

– Des parties analogiques (RF, CAN/CNA)

– …

Avec des contraintes temps-réel, de surface, de consommation, …


Exemple : téléphone portable


Flot de conception d’un SoC

• Extraire le parallélisme de contrôle de l’application

– Modélisation sous forme de processus concurrents (mieux : réseaux de Kahn)

– Exploration architecturale

– Implanter certaines tâches en matériel et d’autres en logiciel

– Simulation / profiling / évaluation de surface et consommation

• Choix de composants existants / synthèse des composants matériels

• Placement / routage / simulation bas niveau

• Construction des masques / fonderie / tests des circuits


Idées fortes

• Cycle de développement très court

• Utilisation de composants pré-existants (modèles fonctionnels (transactionnels / précis au cycle) modèles synthétisables)

• Effort de standardisation des interfaces

• Développement en vue de la réutilisation

• Énormes problèmes de productivité

– Complexité des systèmes à construire

– Méthodes et outils de CAO à redéfinir


Vérification fonctionnelle des SoC

• Vérification de chaque composant puis de l’intégration

• Simulations presque exclusivement

• Equivalence-Checking pour des blocs combinatoires / RTL

• Symbolic Model-Checking pour des petits blocs (10 KG)

• Méthodes « semi-formelles » prennent le pas sur SMC

– LTL sur séquences bornées simulation

– CTL à profondeur bornée déroulement explicite de l’arbre d’exécution

• Démonstrations assistées (architectures spécifiques / traitement du signal)


Plan de l’exposé

• Protocoles de communication décrits en réseaux de Kahn

– Vérification avec SPIN de trois systèmes : ZCSP / ANI / RSPIN

– Extension de SPIN avec un model-checker symbolique à base de DDD

• Méthode incrémentale de conception de convertisseur de protocoles

– Incrément

– Transformation de propriétés


Protocole de communication / SPIN : ZCSP

Sliding-window avec stockage des messages non encore acquittés

Protocole d’envoi de données entre 2 processus, court-circuitant les couches système, avec acquittement de chaque message émis. Un message dont un des paquets n’a pas été acquitté doit être intégralement retransmis.

[Beaudenon, Encrenaz, Desbarbieux, ACSD 2003]



Table des messages non

encore acquittés

Index

indéterminisme



Propriétés : - tout message finira par quitter la table- s’il n’y a plus de nouveau message, la table sera vidée

Property Liveness Liveness Ending

PO reduction No Yes Yes

Transitions (10^6) 1928 455 835

Depth Reached 160265 68948 68948

Memory used (Mbyte) 115 232 243

CPU time 35h09 12h55 19h25

Validation Result Valid Valid Valid


Protocole de communication / SPIN : ANIAnneau unidirectionnel tronçonné avec circulation d’un jeton par tronçon

REQ

DATA

TâcheMaître

TâcheMaître

TâcheMaître

TâcheEsclave

TâcheEsclave

Interface Bus - M

Interface Bus - M

Interface Bus - M

Interface Bus - E

Interface Bus - E

[Taktak, Desbarbieux,2003]


Protocole de communication / SPIN : ANI

• Un message est composé de plusieurs paquets

• Jeton REQ : < libre , REQ/REP , nseq , @m , @e , CMD>

CMD = LOCK/UNLOCK/SET/CLEAR/READ/WRITE/RW

• Jeton DATA : <libre , nseq , @dest, data>

• Interface BUS-M : 5 états

• Interface Bus-E : 3 états


Protocole de communication / SPIN : ANI

Propriétés : - Une tâche peut émettre une infinité de requêtes - Toute requête finira par être transmise

Abstraction des domaines des variables

Plateforme avec :1 jeton, 1 maître et 1 esclave : ~ 10s (400 000 états)2 jetons, 2 maîtres et 2 esclaves : trop gros


Protocole de communication / SPIN : réseau SPIN à interface VCI

Réseau multi-étage « fat tree » de degré 4Routage adaptatif sur les liens montants / chemin unique sur les liens descendantsPas d’ordonnancement global (algorithme de routage local)Un message est composé de n paquets REQUETE et n paquets REPONSE

… …

R0 R1 R2 R3

R4 R5 R6 R7

WI WT

Protocole VCI

Réseau SPIN


VCI-SPIN : le deadlock

VCI-SPIN

wrappers

SPIN

network

I3 I4 T3 T4

[Charlery Encrenaz, 2002-2003]


VCI-SPIN : la correction du deadlock

VCI-SPIN

wrappers

SPIN

network

I3 I4 T3 T4

Eviter le partage des liens descendants pour les REQ et les REP


VCI-SPIN : vérification avec SPIN

• Dégradation du modèle

– Suppression des FIFOs de recyclage interne

– 2 routeurs 2 x 2 au lieu de 8 routeurs 4 x 4

• Dégradation de l’environnement

– Configuration figée des initiateurs et cibles

– Taille des messages figée (6 paquets REQ + 6 paquets REP)

• Résultats (1GHz, 1Mo RAM, avec réduction d’ordre partiel)

– Taille < 6 : pas de deadlock

– Taille 6 : la distinction de sous-réseaux REQ et REP disjoints corrige le deadlock

• Deadlock : 56h / Absence de deadlock : 10h

– Taille 7 : pas de deadlock si 2 sous-réseaux (10h)


Un model-checker symbolique pour ProMeLa

Structure de donnée pour représenter les ensembles d’états : DDD (LIP6 / LaBRI): arbres partagés.

• Variables décisionnelles de type fini• Représentation des chemins menant à 1 ou T• Exploitation du partage des sous-arbres isomorphes• Opérations ensemblistes : parcours attelé des 2 DDD (polynômial) • Modification « la plus locale possible » : itérateur parcourant le DDD

Représentation de systèmes dynamiques bornés (la borne n’est pasconnue a priori) : variables entières / canaux de communication / run


DDD : Structure

• Nœuds : variables• Arcs : valeur dans les entiers• Contrainte: un seul arc d’une étiquette donnée en sortie d’un nœud

Interprétation : ensemble de mots (affectations) menant au nœud 1Efficacité : partage

a

a b

b

1

11

1 2

1 2 1

1

a

a

b

1

12

1

2

1

partage

[Couvreur Encrenaz Poitrenaud Paviot Wacrenier, DGA 2000-2001, ATPN 2002]


DDD : Normalisation

• Les chemins invalides ne sont pas représentés • Conséquence : domaine des variables inconnu a priori• Représentation de l’ensemble vide nœud terminal 0

• Représentation canonique des DDD (classe d’équivalence)

a

a b

b

1

11

1 2

1 2 1

1

a

a

b

1

12

1

2

1

normalisation

0

0

0

0

partage


DDD : Approximation• Contrainte : un seul arc d’une étiquette donnée en sortie d’un nœud• Conséquence : des opérations peuvent conduire à des résultats

indéterminés• Représentation de l’approximation nœud terminal T

• Bonnes propriétés algébriques des opérations

a

a

b

1

1

1 2

1 2

1

T

• DDD bien défini : absence de nœud terminal T

• Relation « mieux-défini » :relation d’ordre sur les DDD


DDD : Opérations ensemblistes• Un DDD est un ensemble de mots : Opérations ensemblistes + * \

• Un DDD est un ensemble de mots : Opération de concaténation .

Exemple :

A

A . B

...

v0

1

...

v1

1

...

v0

...

v1

1B


DDD : Homomorphisme•Définition : d, d’ deux DDD bien définisUn homomorphisme est une fonction telle que :

(0) = 0 (d) + (d’) = (d + d’)

•Exemples : d * IdId \ dId . d1 + 2

1 o 2

•Cas général : d, d’ deux DDD (0) = 0

(d) + (d’) (d + d’)d d’ (d) (d’)


DDD : Homomorphismes inductifs (1)

• Famille d’homomorphismes i définis localementi (0) = 0i (T) = Ti (1) = ci (une constante)i (d) = définition locale à la racine de d et à ses valuations

• Exemple

SetCst(var, val)(1) = T

SetCst(var, val)(e, x) =

e — Id si e = var

e — SetCst(var,val) sinon

val

x



SetCst(b,2)

a

b c

1

1 2

0 1

= SetCst(b,2) (a — b — 1 ) +

SetCst(b,2) (a — c — 1 ) 1

0

2

1

SetCst(b,2) (a — b — 1 ) = a — SetCst(b,2)(b — 1 )

= a — b — Id(1)

= a — b — 1

01 1

1

1

0

2

2

SetCst(b,2) (a — c — 1 ) = a — SetCst(b,2)(c — 1 )

= a — c — SetCst(b,2)(1)

= a — c — T

12 2

2

2

1

1

1



SetVar(var1, var2)(1) = 1

SetVar(var1, var2)(e, x) =

Down(var1, var2) si e = var1

e — SetCst(var1, x) si e = var2

e — SetVar(var1, var2) sinon

x

x

Down(var1, var2)(1) = T

Down(var1, var2)(e, x) = var1 — e — Id si e = var2

Up(e, x) o Down(var1, var2) sinon

x x

Up(var, val)(1) = T

Up(var, val)(e, x) = e — var — Id x val

Exemple : var1 = var2 SetVar

Down

Up



SetVar(b, d) (a — b — c — d — 1)

a — SetVar(b, d) (b — c — d — 1)

a — Down(b, d) (c — d — 1)

a — Up(c, 3) o Down(b, d) (d — 1)

a — Up(c, 3) (b — d — Id(1))

a — Up(c, 3) (b — d — 1)

a — b — c — d — 1

1 2 3 4

1 2 3 4

1 3 4

41

1 4 4

1 4 4

1 4 43

Exemple d’exécution de SetVar : b = d


DDD pour les programmes promela

Instruction promela = construction de deux homomorphismes• Post : SetCst(pc,new_val) o SetVarExpr(var,expr) o SelCst(pc,cur_val)

• Pré : élargissement puis restriction aux états accessibles (2 à 3 passes)itérateur ad-hoc en 1 passe

Un état du programme :• variables globales• chaque processus en cours d’exécution

• son compteur ordinal• ses variables locales

Etat initial = concaténation de toutes les variables dans un ordre figé

[Beaudenon Encrenaz 2003-…]


Premiers résultats

# états SPIN SPIN DDD DDD DDD_ordreDDD_ordre

temps (s) mem (Mo) temps (s) mem (Mo) temps(s) mem (Mo)

sliding window400 000 1 8 1950 27

philo 8 6 000 1 5,7 9 9,5

philo 10 60 000 6 37 41 25

philo 13 1.5 e6 260 393 388 168 63 27

philo 15 1.4 e7 *** *** 165 642 121 42

philo 20 3.4 e9 *** *** *** *** 406 95

philo 40 *** *** *** *** 6780 754

Calcul de l’ensemble des états accessibles


Model-checker symbolique intégré à SPIN

• Comparaison avec les BDD en cours • a = a + b (borne connue a priori)

• construire 1 additionneur (ripple carry : gros bdd sur poids forts)• substituer à ses entrées l’expression de a et de b (non évaluée)• connecter la sortie de l’additionneur à la variable a : xnor

• réordonnancement dynamique des variables

• Influence de l’ordre des variables (pas de réordonnancement dynamique)• Affectation d’une expression non évaluée DDD hiérarchiques• Systèmes dynamiques

[Taktak Beaudenon 2004]


Méthode de conception incrémentale

• Réutilisabilité des composants

– Standardisation des interfaces (VCI)

– Ajout/suppression de fonctionnalités

• Convertisseurs de protocoles

– VCI : protocole point à point de transaction.

• Une transaction : un paquet requête et un paquet réponse. Chaque paquet est composé de cellules. Chaque cellule est acquittée.

– PI / AMBA : protocole de bus système (entre processeurs et mémoire)

• Tranfert 1 mot (ou une rafale de mots) de façon pipelinée

– Toutes les configurations de VCI / PI ne sont pas toujours nécessaires

[CERME 2000; Encrenaz Braunstein 2002-…]


décodeur MPEG : Représentation des wrappers


Flot de données du wrapper maître

FSM

Chemin de données REP

Chemin de données CMD

DonnéesAdresses

Données

Contrôle de flux bus

REP

CMD

Ctrl flux REP VCI

Ctrl flux CMD VCI

Objectif : contrôle de flux

PI ou AMBAVCI


Ordre sur les wrappers

A A_prime

B B_prime

C C_prime

Target is always ready

Target may send WAIT

Target may send RETRY

Initiator is always ready Initiator introduces wait states


Architecture Wrapper maitre


De Wi à Wi+1

a a

aa

...

s3s2

s1

ab ab

ab

bb

ab b

......

s1

s3s2

s4

...ab

b

B est le signal d’incrément, b est la valeur silencieuse et b la valeur active

Une machine de Moore déterministe et complète Wi

Un incrément : < I+, O+, S+, R+>Wi+1


De Wi à K(Wi)

...

s3.as2.a

s1.a

...

s3.a

s1.a

s2.a

a a

aa

...

s3s2

s1

Les entrées (gardes des transitions) sont incorporées dans l’état source

De la machine de Moore à la structure de Kripke


De K(Wi) à K(Wi+1)

Le sous-graphe représentant K(Wi) est inclus dans le graphe K(Wi+1).

C’est le sous-graphe maximal accessible à partir de l’état initial, tel que chaque état comprend le signal d’incrément à une de ses valeurs par défaut (ici b).

b

b b

bb

b b

b

b

b

b

b

b

b

b

b

b

b

b


Règles de transformation

Soit s' K(Wi+1) enrichissant s K(Wi) par b = val_qt,

• K(Wi),s |= p K(Wi+1),s' |= p

• K(Wi),s |= EX f K(Wi+1),s' |= (b = val_qt) => EX f'

• K(Wi),s |= EF f K(Wi+1),s' |= E ( (b = val_qt) U f')

• K(Wi),s |= EG f K(Wi+1),s' |= EG ( (b = val_qt) f')

• K(Wi),s |= E f U g K(Wi+1),s' |= E ( (b = val_qt) f' ) U g'

• K(Wi),s |= AX f K(Wi+1),s' |= (b = val_qt) => AX f'

• K(Wi),s |= AF f K(Wi+1),s' |= A ( (b val_qt) U f')

• K(Wi),s |= AG f K(Wi+1),s' |= A ( (b = val_qt) f' ) W (b val_qt)

• K(Wi),s |= A f U g K(Wi+1),s' |= A ( (b = val_qt) f' ) U (b val_qt) g'

• K(Wi),s |= A f W g K(Wi+1),s' |= A f' W (b val_qt) g'


Expérimentation avec VIS

VCI-PImasterwrapper

VCI-PIslave wrapper

BCU

PI-bus

VCIinitiator

VCItarget

1

2

3a

3b

4 4 5

6778



Sans reord Window-3

Reach+Prop Prop Reach+Prop Prop

Propriété 1 42.77s 21.07s 7.77s 1.79s

Propriété 2 43.25s 19.96s 7.92s 1.8s

Propriété 3 44.01s 23.59s 8.09s 1.97s

Propriété 1’ - - 23.22s 19.97s

Propriété 2’ - - 23.26s 19.79s

Propriété 3’ - - 29.2s 27.17s

nb de var : 305 états accessibles : 115405 bdd size : 3705

nb de var : 333 états accessibles : 1.4 107 bdd size : 12349

Plate-forme avec un initiateur et une cible VCI – modèles B et B’



Sans reord Window-3

Reach Prop Reach Prop

Propriété 1 - - 6.6s

Propriété 2 - - 23.01s 6.5s

Propriété 3 - - 7.2s

Propriété 1’ - - 26.5

Propriété 2’ - - 22h23 25.8

Propriété 3’ - - 53.6

nb de var : 478états accessibles : 2.9 * 107

bdd size :5586

nb de var : 528états accessibles : 9.3 * 1011

bdd size :990 000

Plate-forme avec deux initiateurs et une cible VCI – modèles B et B’


Nouvelles transformations

ab ab

ab

ab

b

b

ab

ab b

...

...

Introduction de cycles d’attente Blocage partiel de pipeline

Prise en compte de la structure particulière des incréments

bloque l’étage 1 uniquement

bloque les étages 1 et 2

bloque tous les étages


Conclusions

• Il reste beaucoup à faire …

• Améliorer les techniques existantes

– Représentation symbolique

– Réduction / Abstraction des composants à assembler

• Réutilisation de la vérification d’un composant dans un autre contexte

– Transformation de propriétés

– Vérification de type « Assume-Guaranty »

• Considérer les versions paramétrées des exemples

• Couplage vérification / émulation (accélérateur matériel)


Amélioration de CTL – MC (BDD)

Machines de Moore complètes, déterministes et synchronesRéduire les machines, indépendamment les unes des autres, en

fonction de la propriété CTL à vérifier[Shiple CAV 94 : pas indépendamment / jamais implanté]

Bisimulation forte sur les signaux de sortie et les atomes de la prop

Algo de Lin (91) : minimisation de machines de Moore (avantage sur Bouajjani ou Lee/Yannakakis : pas de représentation explicite de la liste des parties).Nouvel algo de Piazza (2002) ?


Amélioration de CTL - MC

Algo de réduction (mettre en évidence les quantifications)


Amélioration de CTL - MC

Gain par rapport au BDD monolithiquePerte par rapport à la méthode partitionnée (sur l’exemple)

pas de combinaison simple avec la méthode partitionnée Pb des systèmes clôts (pas de réduction de l’interface (exemple de req/gnt)

clustering de machines (internaliser les interfaces)? automatisation du clustering ? )

Pour des systèmes avec des gros modules (ou beaucoup de modules Clusterisables), dont l’ensemble est représentable sur bien plus de500 variables, mais dont le modèle réduit tient sur 500 variables)


To do : perf vincent / tel portable / noms des participants a Chaque etape, prop sur pipeline

Documents

Emmanuelle Encrenaz-Tiphène Laboratoire d’Informatique de Paris VI