TD : Conception d'un opérateur synchrone pour un filtre médian¶

Vous allez réaliser une partie opérative de filtre médian. Le filtre médian est utilisé en traitement d'images pour "nettoyer" les images en éliminant certains défauts parasites. L'algorithme du filtrage médian est très simple : chaque pixel de l'image à filtrer est remplacé par la valeur médiane des pixels voisins. L'image est ainsi transformée par le filtre médian en une autre image de même taille.

Pour chaque pixel P de l'image d'origine on crée une liste des pixels situés dans un voisinage 3x3 autour de P. Les 9 pixels de la liste sont ensuite triés dans l'ordre de leurs valeurs numériques. La valeur médiane est celle du pixel situé au milieu de la liste triée. Le pixel P de l'image filtrée prend alors pour valeur la valeur médiane.

Pour cet exercice, nous supposerons que les images sont représentées en 256 niveaux de gris. Les valeurs des pixels sont donc comprises entre 0 (noir) et 255 (blanc).

Considérons la situation représentée par la figure ci-dessous :

Notons [X,Y] le pixel situé à l'intersection de la ligne X et de la colonne Y d'une image. La valeur du pixel [4,5] de l'image filtrée est déterminée en considérant le voisinage 3x3 du pixel [4,5] de l'image source, soit ici les pixels {[3,4],[3,5],[3,6],[4,4],[4,5],[4,6],[5,4],[5,5],[5,6]}.

La liste des valeurs de ces 9 pixels est, dans notre exemple, {122,94,247,78,34,45,207,103,18}.

La liste ordonnée de ces mêmes valeurs devient {18,34,45,78,94,103,122,207,247}. La valeur médiane de cette liste de valeurs est 94. Le pixel de l'image filtrée prendra donc la valeur 94.

Pour filtrer une image complète, il faudra répéter ces étapes (sélection du voisinage, tri). Nous allons supposer que l'extraction du voisinage a déjà été implémentée et nous allons nous concentrer sur le tri et l'extraction de la valeur médiane.

Nous allons concevoir, simuler et faire la synthèse d'un module matériel capable d'extraire la valeur médiane à partir d'une liste de 9 pixels qui vont être transmis en séquentiellement.

L'algorithme de tri:¶

Pour notre opérateur nous avons besoin d'implémenter matériellement un algorithme de tri.

Nous vous proposons d'implémenter un algorithme de tri simple avec un nombre d'itérations constant.

On démarre avec un vecteur non trié V contenant PixNum éléments (les indexs commencent à 0).

for pos in 0 ... PixNum-2
begin
  for pix_idx in pos+1 ... PixNum-1
  begin
    if (V[pos] < V[pix_idx])  Exchange(V[pos],V[pix_idx])
  end
end
med = V[PixNum/2]

La fonction Exchange intervertie deux valeurs dans le vecteur V.

À chaque itération le maximum des valeurs est placé à la position pos.

À la fin la valeur médiane se trouve à la position dont l'indice est médian (PixNum/2) (5e position (pos=4) pour 9 pixels).

Comme nous n'avons besoin que de la valeur médiane, nous pouvons diviser par 2 le nombre d'étapes en s'arrêtant à l'étape PixNum/2. Et comme nous n'avons pas besoin des valeurs supérieures au médian, l'algorithme peut être adapté comme suit:

for iter in 0 ... PixNum/2
begin
  for pix_idx in 1 ... PixNum - iter - 1
  begin
    if (V[0] < V[pix_idx])  Exchange(V[0],V[pix_idx])
  end
 // On écrase V[0] en décalant les pixels
  V[0:PixNum-1] = {V[1:PixNum-1],0}
end
med = V[0]

À la fin de chaque cycle de comparaison, on écrase le maximum, contenu dans V[0], avec le nouveau maximum et on décale toutes les autres valeurs pour que la comparaison se fasse toujours avec l'élément en position 0.

Cet algorithme n'est pas forcément le plus efficace pour une implémentation logicielle, mais il a deux avantages pour une implémentation matérielle:

le nombre d'étapes est constant
les opérations effectuées à chaque cycle sont simples et identiques

Pour implémenter matériellement cet algorithme nous allons passer par les étapes suivantes:

Construire l'opérateur de comparaison et d'échange (MCE) utilisé à chaque étape
Décrire le chemin de données et la façon avec laquelle les pixels sont mémorisés/décalés
Décrire le séquenceur (machine à états finis)

Organisation¶

Préparation des répertoires de travail¶

Les outils utilisés générant de nombreux fichiers, il est fortement conseillé de structurer vos répertoires de travail de la façon suivante:

Créez un répertoire median.
Dans ce répertoire créer un sous-répertoire src. C'est dans ce répertoire que vous créerez vos fichiers source. Vous leur donnerez l'extension ".sv".
Créer un deuxième sous-répertoire : simulation qui servira pour l'outil de simulation QuestaSim
Créer enfin un troisième sous-répertoire : synthese qui servira pour l'outil de synthèse Yosys

IMPORTANT:

Respectez les noms des modules indiqués dans le texte (en respectant la casse majuscule/minuscule).

Chaque module doit être dans un fichier de même nom.

Ne pas ajouter de modules en dehors de ceux indiqués dans le texte.

Pour ne pas versionner les fichiers générés par les différents outils (simulateur ou synthètiseur), pensez à ajouter un fichier .gitignore.

Préparation de l'environnement de simulation¶

L'outil de simulation organise les modules compilés dans une bibliothèque. Par défaut la bibliothèque de travail s'appelle work.

Avant de pouvoir compiler vos fichiers vous devez créer cette bibliothèque. Pour ce fait, dans le répertoire "simulation" exécuter la commande suivante:

vlib work

Un répertoire work est créé qui contiendra le résultat des compilations que vous ferez.

Pour compiler un fichier SystemVerilog, vous devez être dans le répertoire qui contient la bibliothèque work (c'est-à-dire le répertoire simulation). La compilation se fait en utilisant la commande vlog comme suit:

vlog +acc ../src/VOTRE_FICHIER.sv

L'option +acc rend visible tous les objets internes de vos modules au moment de la simulation et évite qu'ils ne disparaissent du fait des optimisations de l'outil.

Pour lancer le simulateur, exécuter la commande vsim.

Vérifier la syntaxe¶

Si vous voulez juste vérifier la syntaxe, sans lancer le simulateur, vous pouvez utiliser l'outil verilator. C'est un outil open source qui permet, entre autres de vérifier la syntaxe. Il suffit pour cela de lancer la commande suivante:

verilator --lint-only src/*.sv

Il est généralement disponible dans les paquets standards des distributions Linux et on peut même l'interfacer avec son éditeur de texte favori ( vim, emacs ou vscode ) pour vérifier la syntaxe durant la frappe.

Il est aussi possible d'utiliser verible qui fournit un language server et un plugin vscode.

Les modules à concevoir¶

Le module de comparaison et d'échange (MCE)¶

Nous allons commencer par concevoir un module de comparaison et d'échange (MCE) dont l'interface est la suivante :

Nom Type Direction Description

A Bus 8 bits Entrée Un pixel B Bus 8 bits Entrée Un autre pixel MAX Bus 8 bits Sortie Le plus grand des deux pixels A et B MIN Bus 8 bits Sortie Le plus petit des deux pixels A et B

Ce module produit combinatoirement le minimum et le maximum des entrées A et B. Il compare les deux pixels arrivant sur les entrées A et B. La valeur du grand se retrouvant sur sa sortie MAX et le plus petit sur sa sortie MIN.

La largeur des données doit être paramétrable avec une valeur par défaut de 8.

Écriture du code SystemVerilog¶

Concevez le module MCE en respectant les règles suivantes:

N'utiliser que des affectations concurrentes de type assign (pas de blocs always ou initial).
Réaliser un module dont la taille des données est paramétrable avec une taille par défaut de 8 bits.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Simulation de MCE¶

Créez un environnement de simulation pour le module MCE (un testbench). Votre environnement devra présenter 1000 couples de valeurs aléatoires en entrée du module MCE. Après avoir présenté chaque couple de valeur il devra laisser s'écouler une unité de temps et vérifier automatiquement que les sorties de MCE sont bien les sorties attendues.

Pour générer les entrées vous aurez besoin de la tâche système $random(). Pour vérifier automatiquement les sorties de MCE vous décrirez l'algorithme de comparaison et d'échange d'une façon différente de celle que vous avez utilisée pour MCE.

La simulation devra s'arrêter automatiquement (tâche système $stop()) lorsque le comportement de MCE n'est pas le comportement attendu. Dans ce cas l'environnement devra afficher un message d'erreur indiquant les valeurs attendues et les valeurs observées (tâche système $display()).

La simulation devra également s'arrêter automatiquement lorsque les 1000 couples de valeurs aléatoires auront été présentés et les sorties de MCE vérifiées (tâche système $finish()).

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Attention, pour gagner du temps vous pouvez utiliser l'environnement de simulation que nous avons préparé pour vous en l'adaptant à vos besoins. Si vous choisissez cette option essayez néanmoins de bien comprendre la solution qui vous est proposée.

Lancer l'outil de simulation en exécutant la commande suivante dans le répertoire simulation

vsim NOM_DU_MODULE_TESTBENCH

La fenêtre du simulateur devrait apparaitre.

Lancez la simulation en utilisant les boutons de contrôle de la simulation ou en entrant dans la console la commande run

run # execute un cycle de simulation
run 20us # executer pour une durée de 20us
run -all # executer jusqu'à la fin

Modifiez votre code pour corriger les erreurs éventuelles à l'exécution.

Pour recompiler, vous pouvez retaper la commande vlog dans la console ou dans l'onglet Library du Workspace, dans la bibliothèque work sélectionner votre module, après un clic droit, un sous-menu apparaît, lancez la commande recompile.

Pour ajouter des signaux dans la fenêtre des chronogrammes, sélectionnez l'instance à laquelle ils appartiennent dans l'onglet Sim du Workspace, les signaux apparaitront dans la fenêtre Objects puis glissez/déposez les dans la fenêtre Wave.

Synthèse et optimisation de MCE¶

Téléchargez l'archive contenant les fichiers nécessaires à la synthèse et copier son contenu dans le répertoire median/synthese
Placez vous dans le répertoire median/synthese et modifiez les variables TOP_MODULE et SOURCE_FILES du fichier Makefile pour l'adapter a votre configuration.
- Dans notre cas, TOP_MODULE=MCE et SOURCE_FILES=MCE.sv (attention, ne pas laisser d'espace à la fin).
Exécutez la synthèse avec la commande make syn.
Observez les éventuels messages d'erreur et corrigez votre code en conséquence.
- Les erreurs peuvent être retrouvées dans le fichier MCE_syn.log.
Observez le schéma équivalent généré par l'outil de synthèse par la commande make show

Le fichier MCE_syn.log contient des informations sur la complexité du design généré. Ces informations se trouvent au paragraphe 6.56 du fichier. Ces informations dépendent de la cible choisie pour la synthèse, ici un circuit FPGA Intel de type CycloneV. Les informations données contiennent, entre autres:

Le nombre LUTs configurées en mode "logique combinatoire" (MISTRAL_ALUTxxx) ou xxx est le nombre d'entrée de la LUT.
Le nombre de LUTs configurées en mode "arithmétique" (MISTRAL_ALUT_ARITH)
Le nombre de bascules D utilisées (MISTRAL_FF)
Et aussi d'autres infos sur des blocs spécifiques (mémoires, buffers d'horloges, entrées/sorties…)

Votre unité de comparaison et d'échange ne devrait pas comporter plus de 23 cellules ALUT de tous type, dont 9 cellules arithmétiques, et évidemment aucune bascule D.

Si tel n'est pas le cas, votre code est sous-optimal, modifiez-le.
ATTENTION : A chaque modification de votre code vous devrez resimuler à nouveau MCE pour vérifier que la fonctionnalité est préservée.

L'opérateur de tri médian (MED)¶

Pour extraire la valeur médiane de 9 pixels nous allons concevoir un opérateur séquentiel utilisant un module MCE (et un seul). Son interface est la suivante :

Nom Type Direction Description

DI Bus 8 bits Entrée Le bus par lequel arrivent les pixels DSI Signal 1 bit Entrée Indique qu'un pixel est présent sur l'entrée DI. Actif à 1 BYP Signal 1 bit Entrée Un signal de commande qui modifie le comportement de l'opérateur (voir plus loin) CLK Signal 1 bit Entrée L'horloge. MED est un opérateur synchrone sur front montant de CLK DO Bus 8 bits Sortie Lorsque MED a terminé son tri ce bus présente la valeur médiane des 9 pixels

Les communications entre MED et le monde extérieur sont de la forme suivante :

Le monde extérieur présente 9 pixels à MED (P0, P1, ..., P8), un pixel par période d'horloge
- Pendant les 9 périodes d'horloges le signal DSI est maintenu à 1.
- Les 9 périodes d'horloge sont nécessairement consécutives.
Après avoir reçu le dernier MED trouve la valeur médiane et la présente sur le bus DO.
- Ce calcul prend plusieurs périodes d'horloge.
Lorsque MED a terminé son calcul et présenté la valeur médiane sur le bus DO.
Le monde extérieur peut alors présenter une nouvelle série de 9 pixels.

On supposera dans toute la suite que le monde extérieur respecte ce protocole et attend réellement la fin du calcul en cours avant de présenter une nouvelle série.

L'architecture de MED est la suivante :

Attention: à l'exception de l'instance du module MCE le reste de la description doit être comportemental et non structurel.

Les éléments suivants doivent être décrits de façon comportementale, sans modules supplémentaires: - les objets nommés MUX qui sont des multiplexeurs de 2 mots de 8 bits vers un mot de 8 bits, - les objets nommés R0, R1,… , R8 qui sont des registres 8 bits.

Étudiez cette architecture et réfléchissez à la façon dont le monde extérieur, en pilotant correctement les entrées DI, DSI et BYP peut obtenir la valeur médiane de 9 pixels.

Écriture du code SystemVerilog¶

Concevez le module MED en respectant les règles suivantes:

La largeur des données doit être paramétrable avec une valeur par défaut de 8.
Le nombre de registres doit aussi être paramétrable avec une valeur par défaut de 9.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Simulation de MED¶

Créez un environnement de simulation pour le module MED en vous inspirant de l'environnement de simulation de MCE.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles. Lancez la simulation et modifiez votre code pour corriger les erreurs éventuelles à l'exécution.

Attention, pour gagner du temps vous pouvez utiliser l'environnement de simulation que nous avons préparé pour vous en l'adaptant à vos besoins. Si vous choisissez cette option essayez néanmoins de bien comprendre la solution qui vous est proposée.

Synthèse et optimisation de MED¶

Placez-vous dans le répertoire median/synthese et modifiez:
les variables TOP_MODULE et SOURCE_FILES du fichier Makefile pour l'adapter a la nouvelle configuration. * i.e. TOP_MODULE = MED et SOURCE_FILES = MCE.sv MED.sv
Lancez la synthèse avec la commande make syn
- Observez les éventuels messages d'erreur et corrigez votre code en conséquence.
A chaque modification de votre code vous devrez simuler à nouveau MED pour vérifier que la fonctionnalité est préservée.
Observez le schéma généré (commande make show) et vérifiez qu'il correspond à ce que vous attendez.
Analyser la complexité obtenue après synthèse.
- Déterminez notamment le nombre de bascules D générées (Registers), et vérifiez la cohérence du résultat avec ce que vous imaginez obtenir. Si tel n'est pas le cas, votre code doit être sous_optimal, voire erroné.

L'opérateur complet (MEDIAN)¶

L'opérateur complet est composé de MED et d'une structure de contrôle pour générer les signaux BYP et DSO. Son interface est la suivante :

Nom Type Direction Description

DI Bus 8 bits Entrée Le bus par lequel arrivent les pixels DSI Signal 1 bit Entrée Indique qu'un pixel est présent sur l'entrée DI. Actif à 1 nRST Signal 1 bit Entrée Signal de réinitialisation asynchrone. Actif à 0 CLK Signal 1 bit Entrée L'horloge. MEDIAN est un opérateur synchrone sur front montant de CLK DO Bus 8 bits Sortie Lorsque MEDIAN a terminé son tri ce bus présente la valeur médiane des 9 pixels DSO Signal 1 bit Sortie Indique que MEDIAN présente la valeur médiane sur DO. Actif à 1

Écriture du code SystemVerilog¶

Concevez le module MEDIAN.

Vous utiliserez une instance du module MED à laquelle vous ajouterez les processus nécessaires à la génération des signaux BYP et DSO. Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Voici une suggestion d'algorithme pour déterminer la valeur médiane (vous pouvez utiliser votre propre algorithme original, ou tenter de l'étendre à une version générique.

Durant le tri (soit après la fin du chargement des registres), le signal BYP doit prendre les états suivants:

Étape 1
- 8 périodes a 0: le max des 9 données est dans le registre R[8]
- 1 période a 1: le max est écrasé,
  - les registres R[1] à R[8] contiennent les 8 données restantes,
  - R[0] ne contient plus de donnée utile.
Étape 2 :
- 7 périodes a 0: le max des 8 données restantes est dans le registre R[8]
- 2 périodes a 1: le max est écrasé,
  - les registres R[2] à R[8] contiennent les 7 données restantes,
  - R[0] et R[1] ne contiennent plus de données utiles.
Étape 3 :
- 6 périodes a 0: le max des 7 données restantes est dans le registre R[8]
- 3 périodes a 1 : le max est écrasé ,
  - les registres R[3] à R[8] contiennent les 6 données restantes,
  - R[0],R[1] et R[2] ne contiennent plus de données utiles.
Étape 4:
- 5 périodes a 0: le max des 6 données restantes est dans le registre R[8]
- 4 périodes a 1 : le max est écrasé,
  - les registres R[4] à R[8] contiennent les 5 données restantes,
  - R[0],R[1],R[2] et R[3] ne contiennent plus de données utiles.
Étape 5:
- 4 périodes a 0: le max des 6 données restantes est dans le registre R[8]: c'est le médian!

À la fin DSO doit passer à l'état haut durant un seul cycle pour indique que le résultat est valide en sortie.

Le nombre de données tratées ne sera pas paramétrable (9).

Vous pouvez implémenter ce contrôleur sous la forme d'une machine à états, d'un ou plusieurs compteurs ou d'une combinaison des deux.

Bien qu'il ne soit pas demandé ici d'être générique, un style de codage permettant de passer simplement à une taille de vecteur différente est un plus.

Simulation de MEDIAN¶

Créez un environnement de simulation pour le module MEDIAN en vous inspirant de l'environnement de simulation de MED.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Lancez la simulation et modifiez votre code pour corriger les erreurs éventuelles à l'exécution.

Attention, pour gagner du temps vous pouvez utiliser l'environnement de simulation que nous avons préparé pour vous en l'adaptant à vos besoins. Si vous choisissez cette option essayez néanmoins de bien comprendre la solution qui vous est proposée.

Synthèse et optimisation de MEDIAN¶

Placez-vous dans le répertoire median/synthese et modifiez:
les variables TOP_MODULE et SOURCE_FILES du fichier Makefile pour l'adapter a la nouvelle configuration. * i.e. TOP_MODULE = MEDIAN et SOURCE_FILES = MCE.sv MED.sv MEDIAN.sv
Lancez la synthèse avec la commande make syn
- Observez les éventuels messages d'erreur et corrigez votre code en conséquence.
A chaque modification de votre code vous devrez simuler à nouveau MEDIAN pour vérifier que la fonctionnalité est préservée.
Observez le schéma généré (commande make show) et vérifiez qu'il correspond à ce que vous attendez.

Placement / Routage de MEDIAN¶

Cette étape consiste à

définir précisément les emplacements dans le FPGA cible des différentes cellules générées par la synthèse
définir les ressources de routage nécessaires
optimiser l'ensemble pour respecter les contraintes demandées (ici une fréquence de fonctionnement de 50Mhz)

À faire:

Lancez le placement/routage (make pr)
Examinez le fichier de rapport MEDIAN_pr.log).

A la ligne Info: Device utilisation, vous trouverez le détail des ressources utilisées dans le FPGA cible (MISTRAL_FF, MISTRAL_COMB). Attention ici MISTRAL_COMB signifie tout type de cellule combinatoire arithmétique ou non.

Enfin examiner les lignes débutant par Info: Max frequency for clock,
- la première indique une estimation de la fréquence de fonctionnement de MEDIAN après le simple placement des cellules,
- la seconde indique une estimation tenant compte de l'impact du routage.
Vérifiez que les 50Mhz demandés sont bien respectés.

Simulation de MEDIAN après synthèse et placement-routage¶

Pour cette simulation vous avez besoin des modèles de simulation pour les cellules de la technologie utilisée.

Pour que QuestaSim puisse la retrouver au moment de la simulation il faut lui ajouter cette information.

Dans le dossier de simulation exécutez:

vlog +acc +define+cyclonev /comelec/softs/opt/yosys/cycloneV_sim_libs/*.v

Cette commande va compiler tous les modèles de simulation des primitives pour les FPGA Intel CycloneV.

Il faut ensuite compiler le fichier résultant de la synthèse et le placement/routage de MEDIAN, en lieu et place de votre module MEDIAN original.

vlog +acc +define+cyclonev ../synthese/MEDIAN_pr.v

Le placement routage a généré, de plus, un fichier de rétro-annotation en temps(format SDF pour standard delay file, destiné à définir précisément les temps de propagation des blocs combinatoires et bascules. Nous pouvons forcer QuestaSim à tenir compte de ce fichier pendant la simulation. Pour cela relancez la simulation en éxecutant la commande suivante

vsim MEDIAN_tb -sdfmax I_MEDIAN=../synthese/MEDIAN_pr.sdf

Que pensez-vous de la durée de la simulation (le vrai temps sur le PC) ?
Observez le signal DO, pendant le chargement des données.

Vous devriez constater que les différents bits de DO ne changent pas d'état au front d'horloge, mais avec un délai (heureusement inférieur à la période d'horloge). De plus les différents bits de DO ne basculent pas au même instant.

Pour connaitre le temps que prend l'exécution d'une commande sur Linux
    time la_commande

Pour lancer modelsim sans l'interface graphique

simulation RTL (recompilez les sources avant):

vsim -c MEDIAN_tb -do 'run -all'

simulation post (recompilez la netlist MEDIAN_pr.v):

vsim -c MEDIAN_tb -sdfmax I_MEDIAN=../synthese/MEDIAN_pr.sdf -do 'run -all'

Simulation de MEDIAN sur une image¶

Pour finir vous pouvez tester votre filtre median sur une véritable image :

Utilisez cet environnement de simulation: MEDIAN_IMAGE_tb.sv
Téléchargez L'image bruitée

Le fichier bogart_bruite.hex doit se trouver dans le répertoire où la simulation est lancée. Compilez le nouveu testbench et lancez la simulation (plus longue que précédement).

Le résultat est visible dans le fichier bogart_filtre.pgm et devrait être similaire à ce qui suit:


Bogart, the original	Bogart bruité	Bogart filtré

TD : Conception d'un opérateur synchrone pour un filtre médian¶

L'algorithme de tri:¶

Organisation¶

Préparation des répertoires de travail¶

Préparation de l'environnement de simulation¶

Vérifier la syntaxe¶

Les modules à concevoir¶

Le module de comparaison et d'échange (MCE)¶

Écriture du code SystemVerilog¶

Simulation de MCE¶

Synthèse et optimisation de MCE¶

L'opérateur de tri médian (MED)¶

Écriture du code SystemVerilog¶

Simulation de MED¶

Synthèse et optimisation de MED¶

L'opérateur complet (MEDIAN)¶

Écriture du code SystemVerilog¶

Simulation de MEDIAN¶

Synthèse et optimisation de MEDIAN¶

Placement / Routage de MEDIAN¶

Simulation de MEDIAN après synthèse et placement-routage¶

Simulation de MEDIAN sur une image¶

Liens rapides¶

Test Bench pour le MCE¶

Test Bench pour le MED¶

Test Bench pour le MEDIAN¶

Test Bench image pour le MEDIAN¶

L'environnement de synthèse¶