Parallélisme et machines séquentielles

L’esprit humain est familier de la programmation séquentielle. Il nous est en effet naturel de décrire un traitement sous la forme d’un enchaînement d’opérations à effectuer dans un ordre pré-établi.
Le matériel est, par essence, parallèle. Dans un circuit intégré, tous les composants sont actifs simultanément.

De ces deux considérations on déduit que la forme la plus probable des langages fonctionnels de description de matériel comportera des aspects séquentiels et des aspects parallèles. En d’autres termes, un modèle de composant électronique sera composé de l’assemblage de plusieurs programmes séquentiels, s’exécutant en parallèle. Le concepteur partitionnera son problème en modules assez simples pour être décrits sous la forme de programmes séquentiels classiques, puis il assemblera ces modules que le simulateur exécutera en parallèle.

Le problème, car problème il y a, naît de ce que le simulateur est, en général, installé sur une machine séquentielle, capable d’exécuter une instruction à la fois, donc un programme à la fois. Il ne pourra donc pas paralléliser réellement les différents programmes. Il faut donc trouver un moyen d’émuler le parallélisme sur une machine séquentielle. Comment faire ?

Emulation du parallélisme

L’émulation du parallélisme repose sur une idée très simple et très efficace : pour que chaque programme séquentiel, qu’on appellera désormais processus, s’exécute “comme si” le parallélisme était réel, il faut que son environnement (ses variables d’entrée) ne change pas pendant l’exécution des autres processus. Ainsi, l’ordre d’exécution des processus n’a plus d’importance et tout se passe comme s’ils s’exécutaient en parallèle.

Pour parvenir à ce résultat, il faut que les variables partagées entre processus conservent leur valeur jusqu’à ce que tous les processus aient fini leur exécution. En quelque sorte, on simule pas à pas et, à chaque pas :

1. le simulateur exécute tous les processus dans un ordre quelconque (plus précisément, un ordre défini comme étant arbitraire)
2. toute instruction modifiant la valeur d’une variable partagée verra son exécution différée ; on se contentera d’enregistrer la nouvelle valeur dans une zone temporaire, la variable partagée conservant son ancienne valeur
3. lorsque tous les processus ont été exécutés, on modifie toutes les variables partagées en allant chercher leur nouvelle valeur dans la zone temporaire
4. et on recommence un nouveau pas en prenant en compte les nouveaux états des entrées /sorties des blocs

Les variables partagées ou globales doivent donc être traitées d’une façon particulière. On appelle ces variables des signaux, pour les distinguer des variables classiques.

La gestion du temps

Un simulateur / langage HDL doit avoir une notion du temps, quelle que soit son échelle / unité :

• les concepteurs aimeraient typiquement bien exprimer les stimuli de test ainsi : "a vaut 0 initialement, puis 1 au bout de 10ns, puis 0 au bout de 35 ns, puis..."
• un système doit pouvoir générer des horloges de fréquences différentes, donc avoir une notion (au moins relative) du temps physique
• il faut pouvoir éventuellement modéliser des temps de propagation

Un simulateur doit donc maintenir un compteur de temps, le temps physique courant, et attribuer une date physique à chaque événement au sein de la simulation.

Pour pouvoir modéliser des portes idéales et des conducteurs parfaits (temps de propagation nuls), il faut décorréler les pas de simulation du temps physique : prenons l'exemple d'un inverseur parfait, dont le temps de propagation est nul. Si son entrée change au temps t, sa sortie changera aussi au temps t. Pourtant les deux événements (simultanés) n'auront pas lieu lors du même pas de simulation.

Autrement dit, un pas de simulation n'a pas de valeur temporelle physique intrinsèque. C'est un intervalle de temps virtuel, appelé delta, dont la durée est nulle, qui ne sert qu'à ordonner les événements "simultanés", c'est-à-dire à déterminer lequel a provoqué lequel. Pendant un delta, le temps physique ne s'écoule pas.

Se pose alors le problème suivant : quand faire avancer le temps courant, quelle est la relation entre ce compteur (temps physique courant) et les pas de simulation ?

La simulation

La solution à ce problème est simple et élégante, et possède pour une fois la bonne propriété d’accélérer considérablement les simulations.

1. Chaque événement possède une date complète, comprenant une date physique (1h, 17minutes, 43secondes, ...) et une date symbolique (... 4 deltas).
   Lorsqu’une affectation de signal ne comporte pas de précision sur la date physique à laquelle l’événement doit avoir lieu, il est sous-entendu que la date sera la date à laquelle l’affectation a été exécutée augmentée d’un delta.
   Lorsque la date physique est précisée, la date de l’événement est exactement cette date physique.
   Notons que les synthétiseurs logiques n’utilisent pas le temps physique. Seul l’ordre des opérations que subissent les données sont pertinentes pour la synthèse. Le temps symbolique est donc le seul que les synthétiseurs comprennent.
   
2. Le simulateur maintient un échéancier des requêtes pour chaque signal. Une requête est le résultat d'une affectation; elle est composée de la valeur que doit prendre le signal et de la date complète (date physique + date symbolique) du futur événement. Lorsque tous les processus ont été exécutés et que toutes les requêtes ont été enregistrées, le simulateur peut ainsi déterminer quel signal doit changer de valeur lors du prochain pas de simulation. Il modifie donc les signaux en question et avance le temps d’un pas (1 delta), puis il recommence l’exécution des processus.
   
3. Afin de réduire les temps de simulation on optimise la stratégie du simulateur. Les exécutions inutiles sont supprimées. Avant de commencer un nouveau pas, le simulateur consulte l'échéancier, détermine la date du prochain événement, ainsi que la liste des signaux devant changer de valeur à cette date, et saute directement à cette date-là :
   • soit en restant au même temps physique, mais en augmentant le delta courant
   • soit en sautant directement au temps physique correct; le delta courant est alors remis à 0.
   Cette analyse permet :
   • de relancer l’exécution aux seuls instants « intéressants » ;
   • de ne réveiller que les processus concernés : ainsi, si les deux entrées d’un processus décrivant une porte ET n’ont pas changé, il est inutile de relancer son exécution puisque la sortie conserverait la même valeur
   • de pouvoir faire avancer le temps d’une valeur quelconque. Parmi tous les événements à venir, le simulateur détermine le ou les plus proches, les réalise effectivement et positionne la date courante en conséquence. Il fait ainsi l’économie de pas de simulation inutiles

En fait, cette optimisation est même indispensable puisque la durée physique d’un delta est nulle. Les durées symboliques ont pour seule fonction d’ordonner les événements les uns par rapport aux autres. Si le simulateur ne faisait avancer le temps que d’un delta à la fois, le temps physique n’avancerait pas.

Fonctionnement interne des processus

L’aspect séquentiel est conservé à l’intérieur des processus. Ils obéissent aux règles très classiques de la programmation séquentielle. On trouve les mêmes instructions et les mêmes structures de contrôle qu’en langage C, en Pascal ou en Ada.
La seule exception à l’exécution séquentielle des processus concerne l’affectation des signaux (voir ci-dessous).

De plus, chaque processus est une boucle infinie. Il doit donc comporter au moins un point de synchronisation (appelé aussi point d'arrêt). Faute de quoi, le simulateur est dans l’obligation de l’exécuter indéfiniment (temps physique et temps symbolique n’évoluent pas, il s’agit d’un processus cyclique sans point d’arrêt).
Ce point d'arrêt est soit :

• implicite : le processus est déclaré avec une liste de sensibilité, généralement une partie ou la totalité des entrées du bloc. Il ne sera exécuté que si l'événement en cours porte sur un des signaux présent dans cette liste de sensibilité.
• explicite : à l'aide d'une instruction de type wait(..); comportant une condition sur un ou plusieurs des signaux du processus. Le processus ne reprend son exécution que si cette condition est vraie.

Lorsqu'un processus a atteint un point d'arrêt, le simulateur passe au processus suivant. S'ils ont tous été traités, le simulateur fait avancer le temps (symbolique ou physique, selon l'échéancier).

Attention, la condition de réveil associée au point d'arrêt (implicite ou explicite) ne doit pas être toujours vraie, sinon seul le temps symbolique évolue.
Les processus cycliques sans point d’arrêt sont un grand piège des langages fonctionnels de description de matériel (surtout en VHDL).

On peut considérer les processus comme des threads d'un OS multitâche, sachant que l'OS en question est non-préemptif : chaque thread doit rendre la main au scheduler. C'est le rôle des points d'arrêt. 

Variables locales et globales (signaux)

Les variables globales (signaux) servent à la communication entre les processus (cf. ci-dessus). Elles modélisent les fils électriques (même si ce n'est pas la seule façon de les modéliser).
On a déjà vu que leur affectation doit être traitée de façon spéciale (déférée à la fin du delta courant). Lors de l'affectation des signaux, une instruction d’affectation spéciale est créée. Lorsqu’une telle instruction est exécutée, elle ne prend pas effet immédiatement. Elle est “enregistrée” par le simulateur, qui la traitera effectivement lorsque tous les processus auront été exécutés.
C’est un piège classique des langages fonctionnels de description de matériel que de croire l’affectation de signal instantanée. Le paradoxe apparent provient du fait qu’après une telle affectation le signal n’a pas changé de valeur ...

Les variables locales aux processus sont traitées comme dans tout langage de programmation classique. A la différence des signaux, elles sont modifiées dès l’exécution d’une instruction d’affectation qui les concerne. Ces variables locales ne sont, en général, pas visibles de l’extérieur du processus où elles sont déclarées. Un autre processus ne peut ni les lire, ni les modifier. Elles ne sont pas réinitialisées d’une exécution à l’autre du processus ; elles conservent leur valeur, comme si le processus était en fait une boucle infinie dans un langage de programmation classique.

La différence entre variable locale et signal dépend du langage utilisé :

En VHDL :

la différence entre signal et variable locale est déterminée directement par le type (signal ou variable).

En SystemC :

la différence entre signal et variable locale est aussi déterminée par le type (sc_signal ou type C normal : int, bool, ...)

En Verilog :

une difficulté habituelle vient du fait que les deux ont le même type (généralement reg). C'est la façon dont est écrite l'affectation qui détermine si elle doit avoir lieu instantanément (la variable devrait alors être locale), ou être déférée à la fin du delta courant (la variable est alors un signal de communication entre processus). Nous verrons plus tard que

- une affectation immédiate (dite bloquante) s'écrit ainsi : a = b;
- une affectation déférée à la fin du delta courant (dite non-bloquante) s'écrit ainsi : a <= b;

Plutôt que de contraindre les utilisateurs à utiliser un type ou l'autre, Verilog fait confiance à l'intelligence des concepteurs pour utiliser la bonne affectation. Cela permet une souplesse accrue, au prix d'un risque de se tromper si on n'y a pas pris garde. Nous reviendrons là-dessus plus tard.

Back to Top