Optimisation Ressources FPGA

[invite513e0102]

Bonjour,

Je voudrais implémenter du code VHDL sur la carte Zynq-7 de la famille Xilinx.
Cette carte ne possède que 17000 LUTs et 60 RAM de 36Kbits.
Mon code VHDL demande plus de 17000 ressources, l'implémentation ne marche donc pas.
Je sais quel partie de mon code demande le plus de ressources mais je ne vois pas comment faire pour diminuer le nombre.

Voici la partie du code :

calcul_M : for i in 0 to 255 generate 

Proc_calcul_M : process (reset_n, clk)
  --A chaque coup d'horloge on compare un niveau de la CDF ref avec tous les niveaux de la CDF src
  --On conserve la position 'cpt' du niveau de la CDF ref le plus proche de chaque niveau 'i' de la CDF src dans un autre tableau M à la position 'i'
  --En 256 coups d'horloge on a notre tableau M fini
  begin
    if(reset_n = '0') then
      test(i) <= (others =>'1'); --Signal de test, initialisé tout à 1 pour effectuer des comparaisons successives et trouver une valeur minimum
	  M(i) <= (others =>'0');
    elsif rising_edge(clk) then
      if(cpt_running = '1' and cpt_max = '0') then -- On effectue une opération à chaque coup d'horloge en synchro avec le compteur
        if(std_logic_vector(abs(signed(unsigned(src_cdf(i)) - unsigned(ref_cdf(to_integer(s_cpt)))))) < test(i)) then  --Si la différence est inférieure au signal test
          test(i) <= std_logic_vector(abs(signed(unsigned(src_cdf(i)) - unsigned(ref_cdf(to_integer(s_cpt)))))); --on actualise Test
          M(i) <= s_cpt;
        end if;	
      end if;
    end if;
  end process Proc_calcul_M; 
  
end generate calcul_M;

A chaque coup d'horloge, je soustrais toutes les valeurs du tableau src_cdf à une valeur du tableau ref_cdf. Le signal s_cpt est incrémenté à chaque coup d'horloge jusqu'à la valeur 255, valeur qui correspond à la taille des 2 tableaux.
Le signal test me permet de garder en mémoire la soustraction pour le coup d'horloge suivant.
Je suis contrainte de garder le generate car cela me prendrait trop de coups d'horloge pour remplir mon tableau M (Il me faut dejà 256 coups d'horloge pour le compléter).
Les signaux M et test sont de cette forme :

type M_tab is array (0 to 255) of unsigned(7 downto 0);
type tab is array (0 to 255) of std_logic_vector(20 downto 0);
signal M             : M_tab;
signal test          : tab;

J'ai essayé de remplacer mon tableau M avec des RAM mais cela n'a pas vraiment eu d'effets sur le nombre de ressources. De plus la carte ne possède que 60 BRAM, ce qui me limite grandement.

Est-ce que quelqu’un aurait une idée pour que mon code utilise beaucoup moins de ressources ?

Merci !
-----

[bobflux]

Apparemment tu génères 256 circuits parallèles, donc ça prend de la place.

Quel est le but de la manip ? Quelles sont les contraintes ? Tout cela est un peu vague...

[vincent66]

Bonsoir...

Si j'ai bien compris la conception des zynq la partie fpga est minuscule et destinée quasi uniquement à l'interfaçage avec la mémoire...

Donc ce que tu souhaites faire le serait plus efficacement par un coeur arm7 intégré...

Belle soirée...!

[jiherve]

Bonsoir,
comme le compilo n'est pas forcement très malin donc éviter cette écriture:

 if(std_logic_vector(abs(signed(unsigned(src_cdf(i)) - unsigned(ref_cdf(to_integer(s_cpt)))))) < test(i)) then  --Si la différence est inférieure au signal test
          test(i) <= std_logic_vector(abs(signed(unsigned(src_cdf(i)) - unsigned(ref_cdf(to_integer(s_cpt)))))); --on actualise Test

car cela peut peut être générer le double de cellules
par contre avec une variable testv (à declarer) on pourrait écrire:

 testv(i) := std_logic_vector(abs(signed(unsigned(src_cdf(i)) - unsigned(ref_cdf(to_integer(s_cpt))))));
if testv(i) < test(i) then test(i) <= testv(i);

ce qui est tout de même plus lisible!
ne pas hésiter à utiliser des variables sans oublier pour autant leur spécificités.
ceci dit les changements de type à répétition ne sont pas de bon aloi!
JR

[A voir en vidéo sur Futura]

[invite513e0102]

Oui je génère 256 circuits en parallèle.

Je vais essayer d'être plus clair.

Les tableaux src_cdf et ref_cdf sont des tableaux en entrée de mon bloc qui représente respectivement le tableau source et référence.
Leur type est

type tab is array (0 to 255) of std_logic_vector(20 downto 0);

Pour chaque valeur du tableau source, je veux récupérer l'indice du tableau ref pour lequel la valeur correspondante à cet indice soit la plus proche possible de la valeur du tableau source.
Il faut le faire pour chaque valeur du tableau source.
Il faut donc comparer chaque valeur du tableau source avec toutes les valeurs du tableau ref pour récupérer l'indice et le mettre dans le tableau M.
Si je n'utilise pas de generate, il me faudrait 65536 coups d'horloge pour comparer toutes les valeurs des 2 tableaux.
Avec le generate, au premier coup d'horloge, je compare la première valeur (s_cpt) du tableau ref avec toutes les valeurs du tableau source. Je garde en mémoire dans le tableau test la différence entre ses valeurs.
Au prochain coup d'horloge, je compare la deuxième valeur du tableau ref avec toutes les valeurs du tableau source. Si la différence est plus petite, on met à jour le tableau test avec les nouvelles valeurs.
Le signal s_cpt est incrémenté de 1 à chaque coup d'horloge jusqu'à 256 pour parcourir tout le tableau ref.
Au bout de 256 coup d'horloge, toutes les valeurs des 2 tableaux ont été comparés et on a notre tableau M fini.

La contrainte est d'avoir le tableau M en moins de 256 coups d'horloge, mon code respecte bien cette contrainte mais il prend trop de ressources au niveau du FPGA.

J'ai essayé avec une variable dans mon process mais cela ne diminue pas le nombre de LUTs.

[jiherve]

Bonjour,
Ref+Src+test = 256*3*21+ 256*8 = 18176 registres donc déjà la moitié des CLB.
si tu dépasses 6 variables par bit alors il faudra 2 lut 6 or une soustraction c'est au moins 3 entrées , une comparaison aussi c'est foutu sauf peut être en pipelinant soustraction et comparaison si cela ne rentre pas alors c'est que ton FPGA est trop petit!
la condition (cpt_running = '1' and cpt_max = '0') peut être réduite à un signal seulement
JR

[bobflux]

Si je comprends bien, tous les 256 cycles tu vas avoir un nouveau tableau source à traiter, donc il faut que le précédent soit fini. Correct ?

Quelle est la fréquence d'horloge ? Si il est possible de l'augmenter, on peut utiliser moins de circuits travaillant plus vite.

L'un des tableaux (source ou référence) est-il une constante, ou bien une quasi-constante qui ne varie que rarement ? Si oui, il est possible de précalculer le truc.

[invite513e0102]

Ouai, au niveau des registres c'est pas le top non plus mais j'arrive quand même à ne pas dépasser le nombre max de registres avec le reste du design.

Comment on fait pour pipeliner la soustraction et la comparaison dans mon cas?

[invite513e0102]

@bobflux

Oui après les 256 cycles d'horloge je vais avoir un nouveau tableau source à traiter et il faut également que le précédent soit fini.
La fréquence d'horloge est 200MHz.
Le tableau référence varie rarement en effet.

[jiherve]

Re
pour pipeliner tu calcules la différence au cycle n et tu compares au cycle n+1 c'est un jeu d'index dans les boucles par contre il faudra 257 cycles et attention à l'initialisation du process.
JR

[bobflux]

> La fréquence d'horloge est 200MHz.

OK donc on a pas trop de possibilité de faire 2 op par cycle...

> Oui après les 256 cycles d'horloge je vais avoir un nouveau tableau source à traiter et il faut également que le précédent soit fini.

Comme on a 256 valeurs source tous les 256 cycles, c'est équivalent à traiter une valeur par cycle.

> Pour chaque valeur du tableau source, je veux récupérer l'indice du tableau ref pour lequel la valeur correspondante à cet indice soit la plus proche possible de la valeur du tableau source.

> Le tableau référence varie rarement en effet.

OK, donc je reformule ton problème :

A chaque cycle d'horloge, on a une valeur "source". On doit trouver l'indice de la valeur la plus proche dans le tableau constant "ref".

Ton problème est de choisir le bon algorithme. Solution :

Comme "ref" est constant, on le trie. Pour rechercher la valeur la plus proche de "source" dans un tableau de 256 valeurs triées dans l'ordre, on utilise la bonne vieille méthode de la dichotomie qui nous prend 8 comparaisons par recherche et non pas 256. On a donc divisé le besoin en ressources par 32, donc ça tiendra dans ta FPGA sans souci.

Pour retrouver l'indice original, on stocke les tuples (valeur, indice original) ce qui prend 8 bits en plus par valeur.

Cependant il faut quand même faire 8 comparaisons par cycle, et bien sûr chaque comparaison nécessite de lire la valeur à comparer dans le tableau "ref". Comme on n'a pas de mémoire capable de faire 8 lectures aléatoires par cycle, on voit qu'on va devoir instancier plusieurs copies de "ref" et les faire bosser en parallèle. Il nous faudra aussi un mécanisme pour mettre "ref" à jour, bon ça c'est pas compliqué donc je squeeze.

Déjà il faut choisir une stratégie.

1) Un module qui traite une valeur en 8 cycles par recherche dichotomique itérative. Il prend une valeur source, recherche dans le tableau ref, et sort la réponse 8 cycles plus tard. Pour traiter une valeur par cycle il faudra instancier 8 modules identiques, on met une gearbox 1 entrée 8 sorties devant pour répartir le flux source entre les modules et puis on les réunit à la sortie.

2) Un module qui effectue une seule itération de l'algo sur les 8 nécessaires, et au lieu de reboucler il passe ses variables d'état au module suivant. On a donc un pipeline de 8 modules identiques qui effectuent chacun une comparaison.

Perso je sens mieux le deuxième car son avantage est que seule la dernière itération a besoin de toutes les valeurs de "ref", l'avant dernière n'utilise que les indices multiples de 2, celle d'avant les multiples de 4..... et la première comparaison ne compare QUE avec l'indice 128. Donc on voit immédiatement que cette option 2 va utiliser moitié moins de mémoire pour stocker toutes les copies de "ref" que l'option 1 au dessus, et elle va aussi utiliser bien moins de flops et de LUT et de signaux car le nombre de bits utilisés dans les variables d'indice dépend de l'itération, par exemple la première itération n'utilise que le MSB de l'indice, donc le compilateur va dégager les autres...

Autrement dit tu vas stocker "ref" dans des flops pour les premières itérations, et dans des BRAM pour les dernières. La frontière entre les deux sera à définir en fonction de ce qui utilise le moins de ressources. Une BRAM 18 bits dual port peut lire 36 bits par cycle donc on peut stocker dedans des valeurs de 36 bits, il suffit de rentrer les bonnes adresses. Tes valeurs font 21b de data + 8b pour retrouver l'indice original, donc 29 bits, ça passe.

Pour ce qui est du timing, pour chaque itération il faut une addition pour trouver l'indice au milieu de l'intervalle de recherche, une lecture mémoire sur cet indice, puis une comparaison. Tout ça devrait prendre au minimum 1 cycle (pour la lecture BRAM) mais plus probablement 3 cycles, donc on pipeline pour que ça traite une valeur par cycle.

Bon, voilà, en gros tu prends l'algo de dichotomie itérative et tu déroules la boucle.

[jiherve]

Re
cela suppose tout de même qu'il ai trié/ordonné au préalable les valeurs ref et le stockage en RAM est problématique pour une structure // car une RAM ne sort qu'une valeur à la fois.
par ailleurs amha le tri dichotomique te dira seulement que CDF ref n< CDF src<CDF ref n+1 pas qu'elle est la valeur la plus proche.
JR

[bobflux]

> cela suppose tout de même qu'il ai trié/ordonné au préalable les valeurs ref

oui, le cpu ARM peut le faire

> et le stockage en RAM est problématique pour une structure // car une RAM ne sort qu'une valeur à la fois.

oui, il faudra plusieurs mémoires

> par ailleurs amha le tri dichotomique te dira seulement que CDF ref n< CDF src<CDF ref n+1 pas qu'elle est la valeur la plus proche.

en effet, j'avais oublié ! il faudra ajouter cette opération à la fin...

[invite513e0102]

Pour trier le tableau ref, j'ai fait le code suivant :

Proc_ref_cdf_sort : process (reset_n, clk)
variable sort_array : tab;
variable temp : std_logic_vector(20 downto 0);
begin
  sort_array := ref_cdf;
  if (reset_n = '0') then
    sort_ref_cdf <= (others=>(others=>'0'));
  elsif rising_edge(clk) then
	for j in tab'left to tab'right -1 loop
          for i in tab'left to tab'right-1-j loop
	    if(sort_array(i) > sort_array(i+1))then
		  temp := sort_array(i);
		  sort_array(i) := sort_array(i+1);
		  sort_array(i+1) := temp;
	     end if;
          end loop;	  
	end loop;
	sort_ref_cdf <= sort_array;
  end if;
end process Proc_ref_cdf_sort;

Mais cela n'est pas synthétisable.
Tu entends quoi par utiliser le CPU ARM ?

[jiherve]

bonjour,
je réponds à sa place : le ARM servirait a trier ordonner les valeurs de référence.
on peut faire un tri bestial en stockant les valeurs ordonnées de la ref dans une memoire et ensuite on balaye les 256 adresses qui donc fourniront les 256 valeurs sur le bus de sortie arrosant 256 comparateurs/soustracteurs simples (CDF src versus CDF ref) la transition <= vers > donne, comme pour le tri dichotomique, 2 candidats qui faut départager ensuite par simple (nonobstant la gestion du signe) comparaison
Mais j'ai une question : quelle est le véritable cahier des charges, qu'est ce qui contraint à faire çà en 256 CK ?
JR

[bobflux]

> Tu entends quoi par utiliser le CPU ARM ?

Le Zynq embarque un processeur tout à fait compétent, il peut trier un tableau en soft.

Tu vas probablement vouloir modifier le tableau "ref" de temps en temps, sous contrôle du processeur. Enfin je suppose que tu vas utiliser le processeur, sinon pourquoi avoir choisi un Zynq? Donc puisque le proc va mettre à jour le contenu du tableau, ça coûte pas plus cher de le trier en même temps...

> Mais j'ai une question : quelle est le véritable cahier des charges

En effet