23
Gei 431 Architecture des ordinateurs II – Frédéric Mailhot Synthèse logique: Quelques algorithmes et techniques La synthèse logique consiste en un très grand nombre d’opérations diverses, qui doivent produire un circuit performant (délai, puissance, taille, etc). Dans ce qui suit, nous examinerons les Binary Decision Diagrams (BDD), leur utilisation dans un problème de couverture, et nous inventerons un algorithme de création d’arbres de buffers.

Synthèse logique: Quelques algorithmes et techniques

  • Upload
    yachi

  • View
    35

  • Download
    1

Embed Size (px)

DESCRIPTION

Synthèse logique: Quelques algorithmes et techniques. La synthèse logique consiste en un très grand nombre d’opérations diverses, qui doivent produire un circuit performant (délai, puissance, taille, etc). - PowerPoint PPT Presentation

Citation preview

Page 1: Synthèse logique: Quelques algorithmes et techniques

Gei

431

Architecture des ordinateurs II – Frédéric Mailhot

Synthèse logique:Quelques algorithmes et techniques

La synthèse logique consiste en un très grand nombre d’opérations diverses, qui doivent produire un circuit performant (délai, puissance, taille, etc).

Dans ce qui suit, nous examinerons les Binary Decision Diagrams (BDD), leur utilisation dans un problème de couverture, et nous inventerons un algorithme de création d’arbres de buffers.

Page 2: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Les BDD

• Les Binary Decision Diagrams (BDD) ont été proposés en 1986 par Randy Bryant, pour représenter efficacement les fonctions booléennes.

• Problème: soit une fonction booléenne de N variables. Sa représentation par un tableau de vérité (ou un tableau de Karnaugh, qui est équivalent) requière 2^N bits. Lorsque N est grand (N>30), cette taille devient prohibitive.

Page 3: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Les BDD (suite)

• Idée: Représenter les fonctions logiques à l’aide d’un graphe qui

permet de réutiliser des parties communes. Plus spécifiquement, utiliser la décomposition de Boole (aussi

appelée décomposition de Shannon), ce qui produit tout simplement un réseau de multiplexeurs contrôlés par les variables d’entrée de la fonction:

• F(…, x, …) = x * Fx + x’ * Fx’

• Exemple: f = a + b cF = a * fa + a’ * fa’

F = a * 1 + a’ * (b c)F = a + a’ * (b c)

Page 4: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Exemple simple de BDD

• Exemple: f = a + b cF = a * fa + a’ * fa’

F = a * 1 + a’ * (b c)

F = a * 1 + a’ * ( b * (c) + b’ * 0)

F = a * 1 + a’ * (b * (c * 1 + c’ * 0) + b’ * 0)

a

b

c0

0 1

1

0 1

0 1

0 1

F

Page 5: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Les BDD – autres règles de création

• Autres règles: La décomposition de Boole doit se faire avec le même

ordre de variables dans tous les chemins entre les entrées et les sorties. On dit dans ce cas que le BDD est ordonné (Ordered Binary Decision Diagram, ou OBDD)

Les sous-circuits identiques doivent être partagés. On dit alors que le BDD est réduit

Page 6: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Exemple de BDD ordonné, et non-ordonné

• Exemple: f = a (b + c) + a’ b’ c

a

c

b0

1 0

0 1

0 1

0 1

F

0 1 b

0 1

0 1

1c

Non-ordonné (mauvais)

a

b

c

0 1

0 1

0 1

0 1

F

0 1 b

0 1

0 1

1c

Ordonné (bon)

0

Page 7: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Exemple de BDD simutanément ordonné et réduit

• Exemple: f = a (b + c) + a’ b’ c

Ordonné et réduit

a

b

c

0 1

0 1

0 1

0 1

F

0 1 b

10

a

b

c

0 1

0 1

0 1

0 1

F

0 1 b

0 1

0 1

1c

Ordonné

0

Page 8: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Représentation du ROBDD

• Exemple: f = a (b + c) + a’ b’ c

F

a

bb

c

10

a

b

c

0 1

0 1

0 1

0 1

F

0 1 b

10

1

1

1

1

0

0

0

0

Page 9: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Pourquoi les BDD sont-ils intéressants?

• Pour un ordre de variables donné, les BDD sont canoniques, c’est-à-dire que leur représentation est unique pour une fonction booléenne donnée.

• Exemple: Est-ce que F = a (b + c) + a’ b’ c

et G = a b + b’ c

sont des fonctions équivalentes?

Difficile à dire sans établir la table de vérité… mais leurs BDD respectifs sont identiques.

Page 10: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Pourquoi les BDD sont-ils intéressants? (2)

• Pour la plupart des fonctions logiques intéressantes, les BDD correspondants sont petits, même pour des fonctions ayant un très grand nombre de variables.

• Parmi les quelques ombres au tableau: Multiplicateurs

• Pour plus de renseignements et le code source d’un gestionnaire de BDD, voir CUDD de Fabio Somenzi (University of Colorado, Boulder)

Page 11: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering

• Problème: l’extraction de noyaux, qui est très efficace pour réduire la taille des circuits lors de la synthèse logique, crée des portes avec de très grands « fanouts », ce qui ralentit beaucoup le circuit.

Page 12: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Délais

• Nous utiliserons un modèle simple de délai: Chaque porte logique aura:

• Un délai intrinsèque, • Une résistance interne, • Une capacité à l’entrée,

Pour une porte donnée « P », qui est connectée à une capacité à la sortie S, alors le délai DP est:

DP = P + P * S

Page 13: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering

• Dans un problème réel, si une porte a un très grand fanout, il est probable que les charges des différentes portes de son fanout soient inégales.

• Ce problème est complexe, alors nous le simplifierons: Nous supposerons que toutes les charges sont

identiques. Nous supposerons de plus que les charges peuvent être divisées autant que l’on veut.

Page 14: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (2)

T

1

1

0

1

D = 0 * 1 + 1 + 1 * T

Page 15: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (3)

T

1

1

0

1

D = 0 1 n1 + 1 + 1 n2 2 + 2 + 2 T

2

22

2

22

n1

n2

n1 n2

Page 16: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (4)

D = 0 1 n1 + 1 + 1 n2 2 + 2 + 2 T

n1 n2

Nous cherchons le minimum pour D.D’ou:

d D = 0 1 - 2 T 0

n12

n2d n1

d D = 1 2 - 2 T 0

n22

n1d n2

Page 17: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (5)

Dopt = 3 ( 0 1 2 1 2 T)1/3 + 1 + 2

Des équations précédentes, on tire:

n1 = 1 2 2 T

0 2 1

2

3

n2 = 0 2 1 T

1 2 2

2

3

Page 18: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (6)

Dopt = (k + 1) ( 0 1 … k 1 2 … k T)1/(k+1) + i

Les résultats obtenus étaient pour 2 niveaux de buffers,mais nous ignorons combien il devrait y en avoir idéalement:

Soit k la quantité idéale de niveaux, alors:

D = 0 1 n1 + 1 + 1 n2 2 + … + k T

n1 n2 … nk-1

Page 19: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (7)

Dopt = (k + 1) ( b b )k 0 T)1/(k+1) + k b

Puisque Dopt doit être aussi petit que possible, et que les et les vont de pair, alors il doit y avoir un buffer idéal b pour lequel le produit ( ) est minimum. Si on utilise ce buffer b, on obtient:

Mais… on ne connaît toujours pas k…

Page 20: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Buffering (8)

Dmin = ln 0 T - b

Il s’agit donc tout simplement de dériver par rapport à k…Puis il ne reste qu’à solutionner pour k en égalant la dérivée à zéro. On obtient alors:

b b

Avec = b b exp( 1 + b / )

Page 21: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Algorithme de buffering

• Nous avons maintenant une formule qui nous donne le délai minimum qu’on peut espérer pour un problème de buffering donné. En quoi cela nous est-il utile?

Page 22: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Algorithme de buffering – branch and bound

• On peut utiliser cette formule dans un algorithme « branch and bound »: On commence avec la porte de départ, et sa charge

totale. On calcule le délai total entre la porte et les charges. On utilise cette valeur comme notre meilleur délai pour le moment

On ajoute les buffers de notre bibliothèque de cellules, un type à la fois, pour tenter d’ajouter un étage de buffer. Il doit y avoir au minimum un buffer, et au maximum le fanout de départ.

Pour chaque cas, on calcule le délai entre la porte de départ et le nouvel étage de buffers, puis on calcule le délai entre le nouvel étage de buffers et la charge totale en utilisant notre formule. Il est certain qu’on ne peut faire mieux avec les vrais buffers.

Page 23: Synthèse logique: Quelques algorithmes et techniques

© 2001 Frédéric Mailhot Université de Sherbrooke

Le

VH

DL

Branch and bound (2)

On élimine les solutions qui donnent des résultats moindre que le meilleur résultat jusqu’à présent, et on tente d’ajouter un nouvel étage pour les solutions qui sont bonnes jusqu’à maintenant

En début de chaque nouvelle exploration, on tente de brancher la charge totale directement à l’étage de buffer courant. Si le délai obtenu est plus petit que le meilleur résultat en mémoire, on met celui-ci à jour.

On continue ce manège jusqu’à ce qu’il ne reste aucune solution avec un bon potentiel.

La meilleure solution est utilisée lorsque l’algorithme se termine.