Hé! Vous semblez être en United States, souhaitez-vous utiliser notre site English ?
Switch to English site
Skip to main content

Comment implémenter des machines d'état dans votre FPGA

Les machines d'état sont souvent l’épine dorsale du développement FPGA. Choisir la bonne architecture et les méthodes d’implémentation appropriées vous garantira l’obtention d’une solution optimale. 

On fait souvent appel aux FPGA pour réaliser des actions séquentielles et contrôlées comme l’implémentation d’un protocole de communication simple. Pour un designer, la meilleure façon de réaliser ces actions et séquences est d’utiliser une machine d'état. Les machines d'état sont des éléments logiques passant par un nombre fini d’états. Une machine d'état ne sera dans un certain état qu’à un moment précis dans le temps. Cependant, elle va passer d’un état à l’autre en fonction d’un certain nombre de mécanismes de déclenchement.

En théorie, les machines d'état sont divisées en deux classes simples (Moore et Mealy) qui diffèrent l’une de l’autre seulement par la façon dont elles génèrent les résultats de la machine d'état. Pour le type Moore, les résultats de la machine d'état dépendent uniquement de l’état présent. Un compteur en est un exemple classique. Pour une machine d'état Mealy, les résultats dépendent de l’état présent et des entrées. Le Richards controller (voir http://en.wikipedia.org/wiki/Richards_controller) en est un exemple classique.

Définition d’une machine d'état

Lorsqu’il est nécessaire de définir une machine d'état, la première étape consiste à développer un diagramme d’état. Un diagramme d’état montre les états, les transitions entre les états et les résultats de la machine d'état. La figure 1 montre deux diagrammes d’état, un pour une machine d'état Moore (gauche) et l’autre pour une machine d'état Mealy.

Si vous aviez à transcrire ces diagrammes en composants physiques (comme les ingénieurs le faisaient avant l’apparition des FPGA), vous commenceriez par générer les tables d’états-transitions puis par trouver la logique nécessaire pour implémenter la machine d'état. Néanmoins, comme nous utiliserons un FPGA pour l’implémentation, nous pouvons travailler directement à partir du diagramme de transitions d’état.

Diagrammes d’état algorithmiques

Bien que de nombreuses machines d'état soient conçues à l’aide du diagramme d’état présenté dans la figure 1, une autre façon de décrire le comportement d’une machine d'état est le diagramme d’état algorithmique. Ce diagramme ASM (figure 2) est plus proche en apparence d'un diagramme de process de génie logiciel. Il se compose de trois éléments de base :

  1. Boîte d’état : elle est associée au nom de l’état et contient une liste des sorties d'état (Moore)
  2. Boîte de décision : elle vérifie si une condition est vraie et permet la détermination de l’état suivant
  3. Boîte de résultat conditionnel : elle permet à la machine d'état de décrire les résultats de la machine d'état Mealy en fonction de l’état actuel et des entrées

Certains ingénieurs pensent qu’une machine d'état décrite au format ASM est plus facile à préparer pour l’implémentation dans un langage de description matériel comme VHDL.

Moore vs Mealy : que choisir ?

La décision d’implémenter une machine Moore ou Mealy dépendra de la fonction que la machine d'état doit réaliser selon certains temps de réaction spécifiés. La principale différence entre les deux est la façon dont les machines d'état réagissent aux entrées. Une machine Moore aura toujours un décalage d’un cycle d’horloge entre une entrée et la mise en œuvre du résultat. Cela signifie qu’une machine Moore est incapable de réagir immédiatement à un changement d’entrée, comme cela est clairement visible dans la figure 3. Cette capacité de la machine Mealy à réagir immédiatement aux entrées signifie souvent que les machines Mealy nécessitent moins d’états que les machines Moore pour implémenter la même fonction. Cependant, l’inconvénient d’une machine Mealy est qu’en cas de communication avec une autre machine d'état, il y a un risque de conditions de course qui intervient lorsque le résultat dépend essentiellement et de manière inattendue de la séquence ou du timing d’autres évènements.

Bien sûr, une machine d'état n’est pas obligée d’être Moore or Mealy. Il est possible de créer une machine d'état hybride utilisant les deux styles pour réaliser une implémentation plus efficace de la fonction requise. Par exemple, une machine d'état utilisée pour recevoir des données de série RS232 peut être hybride.

Implémentation de la machine d'état

En utilisant un langage de haut niveau comme VHDL, il est facile d’implémenter une machine d'état directement à partir du diagramme d’état. VHDL prend en charge les types énumérés et vous permet de définir les noms d’état. Voici un exemple :

TYPE state IS (idle, led_on, led_off) ;

La description de type ci-dessus correspond aux diagrammes d’état présentés dans la figure 1 pour une machine qui allume et éteint une diode électroluminescente lorsque l’on appuie sur un bouton.

Il existe de nombreuses méthodes pour implémenter une machine d'état. Cependant, les choix se divisent en deux catégories. La première technique basique utilise une approche "one shot" contenant tout dans un process unique. L’alternative est une approche à deux process séparant la logique combinatoire et séquentielle.

En règle générale, la plupart des ingénieurs préfèrent implémenter une machine d'état à process unique. Ce type de machine présente plusieurs avantages par rapport à l’approche à deux process traditionnellement enseignée :

  • Elles suppriment le risque de couverture incomplète des signaux dans le process combinatoire en créant des mécanismes de verrouillage.
  • Les résultats des machines d'état sont réglés sur l’horloge.
  • Elles sont généralement plus faciles à déboguer que celles d’une implémentation à deux process.

Peu importe l'approche que vous décidez d’utiliser pour l’implémentation de votre machine d'état, vous évaluerez la détermination de l’état suivant et de tout résultat à l’aide d’une instruction CASE, comme observé dans la figure 4. La figure présente une comparaison côte à côte entre une machine Moore (gauche) et une machine Mealy utilisant une approche à process unique.

Encodage de la machine d'état

La variable d’état est stockée entre des bascules, qui sont mises à jour avec l’état suivant à l’impulsion d’horloge suivante (même s’il n’y a pas de changement d’état). La façon dont vous utilisez ces bascules pour représenter la valeur d’état dépend du nombre d’états et du fait que vous choisissiez d’utiliser une méthode particulière pour votre outil de synthèse. Les trois types les plus courants d’encodage d’état sont les suivants :

  • Séquentiel : l’encodage des états suit la séquence binaire traditionnelle pour les états.
  • Gray : similaire au schéma d’encodage séquentiel à l’exception du fait que l’encodage d’état utilise du code de Gray, dans lequel seul un bit est modifié entre les encodages d’état.
  • One-Hot : cette technique affecte une bascule par état au sein de la machine à état. Seule une bascule est actuellement en position haute et le reste est en position basse, d’où le nom "one-hot".

Le schéma d'encodage séquentiel et le schéma d'encodage de Gray nécessiteront tous les deux un certain nombre de bascules que vous pouvez déterminer par l’équation ci-dessous.

Bascules = Ceil [LOG10(États)/LOG10(2)] 

En revanche, les schémas d’encodage one-hot nécessitent le même nombre d’états que de bascules.

L’affectation automatique de l’encodage d’état dépend du nombre d’états que la machine d'état contient. Bien que cela dépende de l’outil de synthèse que vous avez choisi, vous pouvez utiliser cette règle générale pour l’encodage :

  • Séquentiel : moins de 5 états
  • One-hot : 5 à 50 états
  • Gray : plus de 50 états

Bien souvent, vous ne penserez pas nécessairement à l’encodage d’état à utiliser et laisserez plutôt le moteur de synthèse déterminer la bonne implémentation. Vous n’interviendrez que si le style choisi pose un problème. Cependant, si vous aviez besoin de prendre les choses en main et de définir l’encodage d’état, il n’est pas nécessaire de le faire manuellement en définissant les constantes de chaque état à l’aide de l’encodage d’état. Au lieu de cela, vous pouvez utiliser un attribut au sein du code pour forcer l’outil de synthèse à choisir un style d’encodage particulier, comme démontré ci-dessous :

TYPE state IS (idle, led_on, led_off) ;

SIGNAL current_state : state := idle;

ATTRIBUTE syn_encoding STRING;

ATTRIBUTE syn_encoding OF current_state : SIGNAL IS “sequential”;

où “sequential” peut aussi être “gray” et “onehot.” Vous pouvez également combiner ces trois choix avec l’attribut "safe" pour vous assurer que la machine d'état puisse revenir à un état valide si elle venait à entrer dans un état invalide.

De plus, vous pouvez aussi utiliser l’attribut syn_encoding pour définir directement les valeurs de l’encodage d’état. Par exemple, supposons que vous souhaitiez encoder une machine à trois états à l’aide de l’encodage d’état suivant : Idle = "11," led_on = "10," led_off = "01," par opposition à la séquence plus traditionnelle "00," "01" et "10".

TYPE state IS (idle, led_on, led_off) ;

SIGNAL current_state : state := idle;

ATTRIBUTE syn_encoding STRING;

ATTRIBUTE syn_encoding OF current_state : SIGNAL IS “sequential”;

En tant qu’ingénieur, vous êtes chargé d’utiliser les bons paramètres dans l’outil de synthèse pour vous assurer que l’outil n’ignore aucun attribut. Par exemple, l’outil Xilinx® XST nécessite que vous définissiez l’option FSM sur USER, alors que le Synplify de Synopsys nécessite que le compilateur FSM soit désactivé. 

L’équation donnée plus tôt détermine le nombre de bascules nécessaires pour l’implémentation d’une machine d'état. Étant donné que toutes les machines d'état ne sont pas des multiples de deux, cela signifie que certains états ne seront pas utilisés pour cette conception. En tant qu’ingénieur implémentant la machine d'état, vous êtes chargé de vous assurer que ces états non utilisés sont correctement traités pour cette conception. Il existe plusieurs techniques de base à implémenter qui s’appliqueront à un grand nombre de conception pour atteindre cet objectif, et d’autres techniques plus avancées à employer si vous travaillez dans des domaines pour lesquels la fiabilité et la sécurité sont essentielles. (Voir Xilinx Xcell Journal numéro 73 pour un article en profondeur intitulé "Using FPGA in Mission-Critical Systems" s’intéressant à la protection des machines à état.)

Cependant, pour la plupart des applications, vous devrez simplement vous assurer que votre machine d'état gère correctement les états non utilisés et qu’elle se rétablit si elle entre dans un état invalide. Il existe deux méthodes principales pour ceci. La première méthode consiste à implémenter une machine d'état sûre à l’aide de l’outil de synthèse. L’outil ajoutera généralement un élément logique supplémentaire pour détecter un état invalide et permettre à la machine d'état de revenir à un état valide. La seconde méthode, qui vous donne plus de contrôle sur l’élément logique implémenté, consiste à déclarer tous les états 2n et à utiliser un autre attribut pour s’assurer qu’ils ne sont pas optimisés bien que n’ayant pas de condition d’entrée. Cela signifie que la machine d'état n’entre dans cet état sous aucune condition sauf en cas d’erreur (accident, etc.). Le code ci-dessous présente l’utilisation d’attributs pour éviter la suppression de ces états non utilisés :

TYPE state IS (idle, led_on, led_off) ;

SIGNAL current_state : state := idle;

ATTRIBUTE syn_keep BOOLEAN;

ATTRIBUTE syn_keep OF current_state : 
SIGNAL IS TRUE”;

Pour résumer, la conception sûre et efficace de machines d'état est une compétence clé pour tout ingénieur travaillant sur des FPGA. Le choix parmi des machines Moore, Mealy voire hybrides dépend des besoins de votre système global. Quel que soit le type de machines d'état que vous choisissiez, comprendre les outils et techniques d’implémentation disponibles vous permettra d’obtenir la solution optimale.

par Adam Taylor

Ingénieur principal

EADS Astrium

aptaylor@theiet.org

DesignSpark Electrical Logolinkedin