# Very High Speed Integrated Circuit Hardware Description Language/VHDL et machines à états algorithmiques

Tout ce qui a été traité dans conception et VHDL fait partie du niveau de spécification RTL (Register Transfer Level). Le niveau d'abstraction abordé maintenant est appelé ESL (Electronic System level).
Quand la fonction à synthétiser devient complexe, la synthèse doit être décomposée en deux parties : un chemin de données et un séquenceur (ou unité de contrôle) destiné à ordonnancer les opérations sur ce chemin de données. En automatisme le chemin de données est plutôt appelé partie opérative. On utilisera cette terminologie parfois. La synthèse correspondante nécessite alors des raisonnements spécifiques : cette décomposition demande une expérience d'autant plus grande que les parties utilisées se décomposent elles-même en sous-parties... Disons pour simplifier que le niveau simple correspond à ce que l’on fait en schéma logique traditionnel : utiliser des composants simples existants. C'est ce niveau qui va nous intéresser maintenant. Dans ce chapitre nous n'aborderons que superficiellement le sujet, avec des exemples.
Terminologie :
* organigramme de programmation
* algorigrammes : représentation d'un algorithme
Note : Wikipédia ne distingue pas les deux termes.

## Utilisations de compteurs (comme chemin de données)

Le compteur de passages est un exemple utilisant des compteurs séquencés comme chemin de données. Son fonctionnement est le suivant :
* si, d’abord le capteur gauche détecte (une personne), puis le capteur droit détecte (la même personne), on incrémente un compteur.
* dans le cas contraire, si le capteur droit est activé avant le capteur gauche, on décrémente.
Cela permet de connaître, par exemple, le nombre de personnes dans une salle.
En logique traditionnelle, le chemin de données est composé par deux compteurs 74190 et le séquenceur par une machine à états. Le séquenceur peut être réalisé avec des composants programmables simples (SPLD). Donnons-en un schéma de principe :
Dans cette figure, on distingue, à gauche, le séquenceur avec dans sa partie supérieure les entrées et sorties. Il y a deux sorties : H (horloge) et DU (Down/Up = Comptage/décomptage) et 4 entrées : clk (horloge), droite et gauche qui sont reliés aux capteurs et Init qui parle d'elle-même. À droite, le chemin de données est constitué par deux compteurs 74190 cascadés et commandés par le signal H qui compte ou décompte suivant la valeur de DU. Il est inutile de chercher la documentation du 74190 pour comprendre la suite. Cet ensemble est simplement destiné à compter ou décompter en BCD et afficher sur deux afficheurs 7 segments.
Cet exemple n’est pas conforme aux règles d'assemblage du séquentiel. En effet l'horloge H de la partie opérative est réalisée par les actions du séquenceur et donc par du combinatoire ce qui est fortement déconseillé lorsqu'on veut faire une synthèse fiable. Nous avons eu l’occasion de réaliser cet ensemble soit avec un PAL et deux 74190, soit dans un seul composant de type FPGA en utilisant un modèle VHDL du 74190 et pour ces deux réalisations on obtient un aléa de fonctionnement. Nous le présentons donc ici, à seul titre d'exemple, car il a l'avantage d’être simple à comprendre.
Il est très fortement déconseillé dans un montage séquentiel d’utiliser une sortie combinatoire d'une première partie comme entrée d'horloge d'une deuxième partie. En effet le combinatoire est susceptible de réaliser des glitchs qui seront dommageables pour le fonctionnement global.
Pour comprendre le rapport entre cette règle et notre schéma, je vous propose de lire ou relire le chapitre description par graphe d'état du cours de logique séquentielle. Vous y réviserez le fait qu'une sortie ou action est programmée de manière combinatoire. Or pour notre compteur de passage la sortie "H" est réalisée par une action, ... et c’est là qu'est le problème !
Nous allons donc nous intéresser au respect des règles d'assemblage du séquentiel et modifier en conséquence l'exemple ci-dessus du compteur de passages.

### Mise en conformité du compteur de passages

Le principe de base est de changer la partie chemin de données (les compteurs). On lui ajoute une entrée « en_tick » de validation synchrone. Le fonctionnement des compteurs est alors le même qu'un 74190 tant qu'en_tick=1 tandis que le compteur reste figé si en_tick=0. La partie séquenceur est alors chargée de réaliser les deux signaux « UD » et « en_tick » mais pas l'horloge. L'horloge sera commune au séquenceur et au chemin de données, mais pour un bon fonctionnement on s'arrangera pour que ces deux parties soient sensibles à un front différent : par exemple front montant pour le séquenceur et front descendant pour le chemin de données.
C'est une bonne chose lorsqu’il s'agit de faire la séparation entre le séquenceur et le chemin de donnée de considérer que le premier fonctionne sur un type de front d'horloge (par exemple montant) et le deuxième sur le front complément (par exemple descendant).
Lorsque les horloges du chemin de données et celle de la partie commande sont décalées dans le temps les raisonnements sont en général relativement simples. Mais en principe il faut mieux que tout le monde fonctionne sur un même front !
Un moyen simple pour réaliser un décalage dans le temps consiste à concevoir un chemin de données actif sur front descendant et une partie commande active sur front montant. Mais cette façon de faire est considérée, elle aussi, par beaucoup d'auteurs comme déconseillée.

#### Application
##### Exercice 1

Modifier le chemin de données ci-dessus pour qu’il utilise la même horloge que la partie séquenceur. Donner le schéma global correspondant en montrant qu’il faudra ajouter deux états à la machine d'états du séquenceur (que se passe-t-il si l’on reste dans S4 ?).
Voici notre nouveau séquenceur :
Si l’on restait dans S4 pendant plusieurs fronts d'horloge, notre compteur serait validé tout ce temps et notre compteur serait incrémenté. C'est pour cela qu'on sort de S4 aussitôt qu'on y est entré.

##### Exercice 2

La gestion de l'écran VGA déjà présentée en exercice dans un WIKIBOOK Conception et VHDL, utilise deux compteurs ayant chacun son horloge. La deuxième horloge provient d'une comparaison c'est-à-dire d'un circuit combinatoire ce qui ne respecte pas la règle de base de l'assemblage du séquentiel (pas d'horloge provenant de combinatoire). Comment modifier le montage pour avoir un montage complètement synchrone (même horloge pour les deux compteurs) ?
La solution de cet exercice est en fait présentée ailleurs dans ce document : Chapitre précédant
Remarque : la façon de procéder de l'exercice original fonctionne correctement en fait car le combinatoire n’est pas pur mais synchronisé sur front descendant. Cela reste cependant une technique non recommandée. On essaie d'expliquer pourquoi maintenant.
On appelle domaine d'horloge une région géographique du FPGA (ou de l’ASIC) pour lequel tous les composants sont sensibles au même type d'horloge : même vitesse par exemple, et cela peut aller jusqu'à la même sensibilité aux fronts.
Les différents domaines d'horloge doivent absolument être correctement séparés. Vous mettrez d'un côté tout ce qui concerne les horloges rapides et d'un autre tout ce qui concerne les horloges lentes. Vous avez la même chose à réaliser sur les fronts d'horloge, séparer les fronts montants des fronts descendants, mais c’est probablement moins critique.
Le schéma référencé dans l'exercice 2 ne satisfaisait pas cette règle : deux compteurs ayant une horloge différente étaient contigus. Vous pouvez objecter, à juste titre, que le schéma était un schéma de principe et non un schéma d'implantation. Mais dans ce cas, ne pas oublier cette règle quand on implémente. Ne pas oublier aussi que VHDL ne vous aidera guère à respecter cette règle : nous voulons dire qu’il n'y a pas moyen de spécifier en VHDL des localisations de composants... en tout cas pour le VHDL standard et portable, mais chaque fabricant propose ses propres constructeurs pour réaliser ces placements.

## Utilisation de registres (comme chemin de données)

Nous nous trouvons dans la situation suivante : nous disposons de plusieurs registres qui forment ce que l’on appelle notre chemin de données, et nous désirons synthétiser un circuit qui les utilise. Ce circuit peut être combinatoire ou séquentiel. Nous allons appréhender cela avec un exemple de calcul de PGCD. Son calcul est réalisé à l'aide de l’algorithme d'Euclide. Cet algorithme peut être décrit de manière récursive de la façon suivante :
* a et b sont les deux valeurs dont on cherche le PGCD (avec a > b)
* si b = 0 alors le PGCD est a autrement on recherche le PGCD de b et du reste de la division de a par b.
Cet algorithme est décrit par l'organigramme suivant :

## Les FSMD (Finite State Machine with Data path)

Nous avons eu l’occasion de présenter les automates finis (ou machines à états finis ou finite state machine FSM). Nous allons généraliser avec les (en) FSMD (Finite State Machine with Data path). La terminologie française associée est assez variée :
* Automates Finis avec chemin de Données (AFD)
* machines à registres (terme non référencé dans Wikipédia)
* machines algorithmiques ou automates algorithmiques (termes non référencés dans Wikipédia)
Au delà de la terminologie, ce qui nous intéresse est un moyen de décrire le fonctionnement de ces machines. Nous avons appris à spécifier les automates finis à l'aide des graphes d'états (ou parfois des graphes d'évolutions) nous allons présenter maintenant notre manière de spécifier les machines à registres. Cela peut se faire avec des organigrammes dans lesquels on a la possibilité de décrire des transferts ou des opérations entre registres (appelés parfois organigramme fonctionnel).
Revenons sur notre exemple de calcul du PGCD. Il peut être décrit par l'organigramme :
Cet organigramme suppose que l’on sache réaliser l'opération T reçoit A rem B, c'est-à-dire le reste de la division de A par B. Pour comprendre, par l'exemple cet organigramme, prenons au départ A = nb1 = 8 et B = nb2 = 6.
* B étant différent de 0, T <- 2 puis A <- 6 et B <- 2
* B étant différent de 0 ,T <- 0 puis A <- 2 et B <- 0
* c’est fini et le résultat est dans A soit 2.
Tout cela est bien gentil, mais, comme déjà exprimé, nécessite un composant capable de calculer le reste de la division. Si, comme la suite va le supposer, ce n’est pas le cas, il nous faut en plus réfléchir à la réalisation de cette opération. Une simple suite de soustractions fait l'affaire (si l’on s'arrête dès qu'un nombre plus petit que le diviseur est obtenu). Il nous faut donc modifier l'organigramme en conséquence :
Une fois vérifié le fonctionnement de notre algorithme, il nous reste à le matérialiser. La partie chemin de données sera responsable de tous les transferts de registres et des calculs combinatoires (en général). Pour notre exemple, nous avons trois registres (A, B et T), quatre transferts de registres (T <- A, T <- A-B, A <- B et B <- T), un calcul d'une différence (A-B) et deux tests B=0? et T<B?. Voilà donc tout ce que doit être capable de faire la partie chemin de données. Il est temps de passer au concret.

### La partie chemin de données

La partie chemin de données est présentée maintenant :
On a gardé, comme convention de couleurs, le bleu turquoise pour les parties séquentielles, ici les registres. Le vert est toujours réservé aux parties combinatoires : tests et calcul d'une différence. La nouveauté est l'apparition des boutons (en rouge). Ils ont été ajoutés pour pouvoir faire les transferts dans les registres de manière symbolique. Appuyez sur le bouton ArB et le registre A reçoit le contenu du registre B. On peut donc lire ArB : A reçoit B. Il en est de même pour les trois autres boutons, sauf qu'en ce qui concerne D, ce n’est pas vraiment un registre mais une sortie de composant combinatoire.
Nous allons présenter maintenant le programme VHDL réalisant cette partie. Commençons par l'entité :
Le lecteur perspicace aura remarqué la présence de e_A et e_B qui ne sont pas dessinés dans le schéma de la figure ci-dessus. Ces deux entrées sont destinées à mettre initialement des valeurs dans les deux registres A et B.
Intéressons-nous maintenant à l'architecture où l’on retrouve un process par registre et un process par partie combinatoire :
Voila, vous savez tout maintenant sur notre chemin de données.

### La partie séquenceur

La machine d'états doit réaliser le séquencement des opérations pour que le calcul se déroule correctement. La spécification de celui-ci se fait facilement à partir de l'organigramme déjà présenté. Donnons-la à l'aide d'un diagramme d'états :
Le calcul est terminé lorsqu'on arrive dans l'état 6. Pour simplifier on a omis le retour de l'état 6 vers l'état « init »
Le graphe d'états regroupe sur un même dessin l’unité de contrôle et le chemin de donnée, ce dernier étant décrit par les actions.

#### Exercice 3

Réaliser le calcul du PGCD complet en VHDL en reprenant le chemin de données présenté plus haut.
Remarque : La partie séquenceur a été réalisée avec un outil automatique (à partir d'un dessin), d'où sa lourdeur.

#### Exercice 4

On initialise le registre A à 8 et B à 6. Un « start » nous fait passer dans l'état 0 puis dans l'état 1. Réaliser un chronogramme des évènements à l'aide du diagramme d'états du séquenceur (en figure ci-dessus) et à l'aide du schéma du chemin de données.
Nous donnons un chronogramme réalisé avec un outil de simulation du VHDL qui montre clairement que le PGCD de 8 et 6 est 2. Le calcul est en effet terminé lorsque le registre B est à 0, ce qui implique que "Beq0" passe à un. Le résultat est alors dans le registre A (noté "oregA" ici)

## Retour sur les problèmes d'horloge

Cette section est difficile à comprendre. Même si elle ne fait intervenir que des notions du niveau indiqué, il est conseillé d'avoir du recul sur les notions présentées pour bien assimiler ce qui suit. Cependant, ce contenu n'est pas fondamental et peut être sauté en première lecture.
Nous pensons qu’il n’est pas difficile de suivre le calcul du PGCD dans la section précédente car on a choisi de faire fonctionner la partie chemin de données et la partie séquenceur sur des fronts d'horloge différents. Mais qu'en est-il si l’on décide d’utiliser les mêmes fronts d'horloge pour les deux parties ? C'est la question à laquelle on va tenter de répondre dans cette section.
Dans cette section nous utiliserons indifféremment les GRAFCETs et les graphes d'états. L'établissement des équations de récurrences se fait de la même manière dans les deux cas. Elle est présentée dans un autre projet.
Certains auteurs estiment qu’il faut éviter des fronts d'horloge différents dans les montages synchrones. C'est la raison d’être de cette section.
Les problèmes présentés dans cette section ne concernent que les circuits se décomposant en séquenceur et chemin de données avec une horloge rapide, c'est-à-dire pour lesquels on ne peut pas se permettre de perdre une période d'horloge. Le compteur de passages ne rentre pas dans ce cadre car il est relié à des capteurs lents. Par contre le calcul du PGCD rentre dans ce cadre.

### Glissement sémantique

Imaginons une étape (ou un état) réalisant l'incrémentation d'un compteur. Le GRAFCET peut s'interpréter comme (voir figure ci-dessous GRAFCET de gauche) :
* nous arrivons dans l'étape 5
* comme nous sommes dans l'étape 5, nous incrémentons le compteur Cmpt
* et nous quittons l'étape 5
Rappel : nous ne restons jamais dans une étape à cause du "=1" des transitions.
L'utilisation d'une horloge commune pour le séquenceur (ou l'unité de contrôle) et pour les actions (notre action est ici séquentielle puisqu’il s'agit d'un compteur), mais avec des sensibilités différentes aux fronts, permet de garder cette interprétation :
* nous arrivons dans l'étape 5 sur le deuxième front montant (du dessin ci-dessous à droite sur fond blanc)
* comme nous sommes dans l'étape 5, nous incrémentons le compteur Cmpt sur le front descendant (en rouge dans le dessin ci-dessous)
* et nous quittons l'étape 5 sur le troisième front montant (du dessin ci-dessous)
Voici la figure correspondante. Ce qui la caractérise est que le GRAFCET représente le fonctionnement du séquenceur et que l'action représente le fonctionnement du chemin de donnée :
On a représenté, à gauche le GRAFCET étudié (sur fond bleu), et en se déplaçant vers la droite, l'évolution des étapes actives en fonction des fronts de l'horloge (représentée au-dessous des évolutions). On montre aussi que l'incrémentation du compteur se produit sur un front descendant (en rouge).
Une nouvelle interprétation est nécessaire :
* nous arrivons dans l'étape 5 sur le deuxième front montant (du dessin ci-dessous)
* nous quittons l'étape 5 et nous incrémentons le compteur Cmpt sur le troisième front montant (du dessin ci-dessous)
En fait c’est au moment de quitter l'étape 5 qu'on incrémente.
Voici la figure correspondante. Ce qui la caractérise est que le GRAFCET représente le fonctionnement du séquenceur et que l'action représente le fonctionnement du chemin de données tous deux fonctionnant sur une même sensibilité aux fronts d'horloge :
Le principe de cette figure est identique à celle qui précède : à gauche le GRAFCET étudié et en se déplaçant vers la droite, l'évolution de ce GRAFCET.
La différence est minime, pourtant elle peut conduire à des erreurs assez subtiles, particulièrement si l'étape est suivie d'un test. C'est ce que nous nous proposons d'examiner dans la section suivante.
Il ne faut pas prendre trop à la lettre c'est au moment de quitter l'étape 5 qu'on incrémente. Si l’on reste quelques fronts d'horloge dans l'étape 5 (cela ne se ferait qu'en remplaçant le "=1" de la transition qui suit l'étape 5 par autre chose) on incrémentera tant que l’on reste dans l'étape 5. Il n’est pas question ici de changer la sémantique du GRAFCET, mais simplement de régler quelques problèmes.

### Mise à jour suivie d'un test

Avant de présenter le problème un petit détour vers les ambiguïtés d'écriture nous semble utile.
Maintenant le problème du test peut être exprimé facilement. Imaginons qu’il y ait un test cmpt=5 après l'étape 5 de la figure ci-dessus (au lieu du "=1"). Que doit-on tester, cmpt ou $cmpt^{+}$, autrement dit, l'état présent ou l'état futur ?
Si vous vous dites, c’est évidemment cmpt puisqu'on a écrit cmpt=5, eh bien, que vous dire ? Vous avez perdu, c’est $cmpt^{+}$ qu’il faut tester !

#### Cahier des charges d'un exemple

Nous allons traiter un exemple simple maintenant. La figure ci-dessous présente le GRAFCET exemple, à gauche, et le déroulement dans le temps de ce GRAFCET à droite (avec les valeurs du compteur).
Remarquez que quand le compteur passe à 3 on est déjà parti de l'étape 1 mais que le jeton reste bien trois fronts d'horloge dans l'étape une.

#### Programme VHDL

Voici le programme VHDL correspondant :
Pour qu'aucune confusion ne soit possible, il faut mieux séparer le calcul de l'état futur de sa mise à jour. Ici, tout ce qui concerne le futur contient un "f" : xf0 est l'état futur de x0, Cmptf est l'état futur de Cmpt...
L'équation de sortie a été laissée après le if "clk'event" parce qu’elles sont toujours écrites à cette place dans les programmes présentés jusqu'à présent (voir description par graphe d'états dans un autre livre). Elle aurait pu être cependant ramenée dans la partie "calcul des états futurs"
Pour pouvoir faire des tests nous avons ajouté les sorties o0, o1 et o2. En principe, seul le compteur est une sortie puisqu’il s'agit d'une action.

#### Résultat de simulation

Nous présentons maintenant un chronogramme réalisé à l'aide d'un outil de simulation VHDL :
Vous pouvez noter qu'effectivement le compteur passe à 3 quand on quitte l'étape 1. Facile aussi de remarquer que l'initialisation à 0 (du compteur) se fait elle aussi lorsque l’on quitte l'étape 0 (complètement à droite du chronogramme)

### Deux actions différentes manipulent un même registre

Imaginons que deux étapes (d'un GRAFCET) ou mieux, que deux états (d'un graphe d'états) réalisent une transformation différente d'un même registre. Ceux qui ont suivi jusqu'ici nous feront remarquer, à juste titre, que cette situation s'est déjà présentée dans le GRAFCET de la section précédente. Une étape réalisait $cmpt^{+}=cmpt+1$ tandis qu'une autre initialisait le compteur à 0. La solution a été présentée avec un mutiplexeur programmé avec un style "with select when" en VHDL.
Le compteur de passages montre une autre situation : une branche incrémente le compteur avec $cmpt^{+}=cmpt+1$ et l'autre décrémente avec $cmpt^{+}=cmpt-1$. La gestion utiliserait elle aussi un multiplexeur.
Lorsque plusieurs actions sont à réaliser sur un même registre pensez à utiliser un multiplexeur programmé avec un "with select when" sans oublier de programmer ce qui se passe dans le cas où les étapes ne sont pas actives.

### Passons maintenant à la pratique

Nous allons partir de notre calcul de PGCD pour mettre en pratique cette théorie.
Pour la petite histoire, l'exercice du PGCD a été donné comme Devoir Surveillé environ 4 fois ces douze dernières années à des étudiants par un des auteurs... et c’est seulement en mettant ses idées au clair avec la rédaction des deux sections précédentes qu’il lui est apparu que cet exemple est loin d’être optimisé. Aucun test n'est en effet réalisé tout de suite après une mise à jour de registre : il y a toujours un état qui suit la mise à jour et qui laisse le temps de faire le test. On se propose dans cette section de supprimer purement et simplement ces états d'attentes.
Une figure sera plus parlante :
Comme vous pouvez facilement le remarquer on est passé de huit à six états.
Voici donc le calcul du PGCD avec un programme unique qui gère le séquenceur et le chemin de données.
Voici maintenant le résultat d'une simulation :
qu’il n’est pas inutile de comparer à un autre chronogramme déjà donné mais reproduit encore une fois pour faciliter la comparaison :
On s'aperçoit que le résultat est obtenu au bout de 1250 ns dans la première simulation et au bout de 2050 ns dans la deuxième : le tout avec exactement la même horloge. La suppression de l'état 2 de l'ancien séquenceur permet de gagner en vitesse puisqu’il se trouvait dans une boucle. Il est facile de voir sur la simulation que cette boucle s'exécute deux fois plus vite maintenant.
Attention, les états ont été renumérotés dans le nouveau séquenceur pour que les numéros des "bit_vector" x et xf correspondent au dessin !!!
La gestion du registre A nécessite 4 fils (avec "with x(3 downto 0) select") tandis que celle du registre B en nécessite 5 (avec "with x(4 downto 0) select"). Une bonne programmation peut facilement ramener ces deux nombres à 2 en déclarant deux signaux sur 2 bits. Vous avez, en effet, certainement remarqué que seuls deux bits sont utilisés dans les "when"...