INF3500 : Conception et implémentation de systèmes numériques Pierre Langlois Cours #11 Performance

INF3500 : Conception et implémentation de systèmes numériques

http://creativecommons.org/licenses/by-nc-sa/2.5/ca/

Pierre Langlois

Cours #11Performance de circuits numériquesPartie 2: optimiser la performance


Implémentation des systèmes numériquesQuatre considérations d’implémentation

2

Précision des calculs

Puissance consommée

Taille du système

Taux de traitement

Aujourd’hui

(notes, section 1.3)

INF3500 : Conception et implémentation de systèmes numériques 3

• Optimisation pour la surface ou le débit (8.6)– latence et débit– comment maximiser le débit– architectures à pipeline– minimiser la latence– minimiser la surface

• Exemple: conception d’un filtre FIR, comparaison de trois designs• Conception pour FPGA: (8.8)• Documentation etc. (8.9 et 8.10)

Plan pour aujourd’hui


La « vitesse » d’horloge

4

(notes, section 8.6.1)

Mieux vaut parler de fréquence ou de période d’horloge, de latence de calcul et de débit d’information!


Latence et débit

• La latence de calcul est le temps nécessaire pour produire un résultat.• Le débit d’information est le nombre de résultats produits par unité de temps.

5


Exemple d’une cafétéria avec 5 stations.Les délais de chaque station sont indiqués.

Suppositions:• un seul client dans la ligne à la fois• chaque client passe par chaque station• un client ne peut pas prendre son cabaret tant que le

client précédent n’a pas fini à la caisse

« Horloge » avec une période de 75 secondes.Latence de 1 cycle = 75 secondes pour servir un client.Débit = 3600 s/h ÷ 75 s/client = 48 clients par heure.

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s


Latence et débit

• Latence:– La latence est le temps entre le moment où une donnée est disponible et le moment

où le résultat qui dépend de cette donnée est disponible à son tour.– Courte latence = meilleure performance.– La latence est souvent exprimée en nombre de cycles d’horloges.– Une fréquence d’horloge plus élevée correspond à une latence plus courte.

• Débit:– Le débit est le nombre de résultats par unité de temps ou par cycle d’horloge.– Grand débit = meilleure performance.– Si le débit est inférieur à un résultat par cycle, on donne plutôt le nombre de coups

d’horloges nécessaires pour produire un résultat.– Quand on calcule le débit, on suppose qu’une quantité suffisante de données est

disponible à l’entrée du système pour le garder actif.– Une fréquence d’horloge plus élevée correspond à un débit plus grand.– Le parallélisme augmente le débit.



Augmenter le débit en augmentant la fréquence d’horloge(1) Réduire le délai sur le chemin critique


cabarets5 s

boissons10 s

plat principal

25 s

bar à salade

15 s

caisse12 s

Cafétéria originale: période d’horloge 75 s, latence 1 cycle, débit 48 clients par heure

Cafétéria modifiée: période d’horloge 67 s, latence 1 cycle, débit 53.7 clients par heure

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s


Augmenter le débit en augmentant la fréquence d’horloge(2) Insérer des registres de pipeline


Avec pipeline naïf: cinq clients sont en ligne à la fois, un seul client par station.Période d’horloge 30 s, latence 5 cycles = 150 s, débit 120 clients par heure

Avec pipeline ajusté: trois clients sont en ligne à la fois.Période d’horloge 30 s, latence 3 cycles = 90 s, débit 120 clients par heure

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s

Original: période d’horloge 75 s, latence 1 cycle, débit 48 clients par heure

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s

Attente25 s

Attente20 s

Attente15 s

Attente15 s

Attente15 s


Questions

• En supposant une très longue file d’attente qui ouvre à 12h00:– À quelle heure mangera le premier client, avec et sans pipeline?– À quelle heure mangera le 2e client, avec et sans pipeline?– À quelle heure mangera le 3e client, avec et sans pipeline?– À quelle heure mangera le 4e client, avec et sans pipeline?

9


heure cabaret et boisson plat salade et caisse manger

12:00:00

12:00:30

12:01:00

12:01:30

12:02:00

12:02:30

12:03:00

(Cas du pipeline ajusté)


Parenthèse: Quelques observations sur le pipeline

• Le pipeline augmente le débit significativement: de 48 à 120 clients par heure.• Pour le premier client, le pipeline n’est pas intéressant, il perd 75 secondes dans

le cas du pipeline naïf et 15 secondes dans le cas du pipeline ajusté.• Pour le 3e client, le pipeline est très intéressant: il pourra manger après 150 s

(cinq coups d’horloge) au lieu de 225 s pour le cas sans pipeline.• Le pipeline n’est intéressant que s’il y a suffisamment de clients pour le remplir.

• Pour plusieurs applications impliquant un flux de données, une latence supplémentaire est sans importance.– Dans le cas d’un lecteur audio, le fait d’avoir quelques cycles de retard est sans effet.

En supposant un taux de données de 44.1 KHz, une latence de 10 cycles d’horloge est inférieure à 250 μs. Ce retard est imperceptible pour un être humain qui vient de lancer la lecture d’un fichier de musique.

• Pour certaines applications, une latence supplémentaire est à éviter.– Communications bidirectionnelles.– Transactions financières en bourse.

10



Augmenter le débit en parallélisant les calculs

• Instancier plusieurs unités de traitement permet de traiter plusieurs données en parallèle et augmenter le débit.

• Exemple: pour un processeur vidéo, on peut décomposer une image en régions indépendantes et associer le traitement de chaque région à un processeur différent.

11


Période d’horloge 75 s, latence 1 cycle, 2 clients simultanés,débit 2 clients/cycle = 96 clients/heure

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s


Augmenter le débit avec pipelineet parallélisation des calculs

12


cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s

Période d’horloge 30 s, latence 3 cycles, 2 clients simultanés,débit 2 clients/cycle = 240 clients/heure

cabarets5 s

boissons10 s

plat principal

30 s

bar à salade

15 s

caisse15 s

Attente15 s


Augmenter le débit avec pipelineet parallélisation des calculs et réduction du délai

13


cabarets5 s

boissons10 s

bar à salade

15 s

Période d’horloge 27 s, latence 3 cycles, 2 clients simultanés,débit 2 clients/cycle = 266.7 clients/heure

cabarets5 s

boissons10 s

bar à salade

15 s

plat principal

25 s

caisse12 s

plat principal

25 s

caisse12 s

Attente2 s

Attente12 s


Augmenter le débit en parallélisant les calculs(cas FPGA extrême …)

14


cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

Période d’horloge 30 s, latence 3 cycles, 20 clients simultanés,débit 20 clients/cycle = 2400 clients par heure

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

cabarets5 s

boissons10 s

plat principal30 s

bar à salade15 s

caisse15 s

Attente15 s


Architecture à pipeline pour circuit numérique

• L’utilisation d’architectures à pipeline est une puissante technique pour augmenter la fréquence d’horloge d’un système et son débit.

• Rappel - la période minimale de l’horloge est donnée par :

• Pour diminuer Tmin, il faut réduire la somme des termes.– td, tsu (délai de propagation et de préparation des bascules):

Ces valeurs sont en général fixes.– tcomb (délai de propagation de la logique combinatoire):

Une architecture à pipeline s’attaque aux délais de la logique combinatoire en décomposant le chemin critique.

– tprop (délai de propagation des interconnexions):Il faut réduire la longueur des interconnexions en disposant judicieusement les composantes du sur le chemin critique.

15


supropcombd ttttT min


Architecture à pipeline pour circuit numérique

16


Supposons (td, tsu, tprop) = (2 ns, 1 ns, 0 ns) supropcombd ttttT min

Tmin = 2 + 8 + 0 + 1 = 11 ns

Tmin1 = 2 + 4 + 0 + 1 = 7 nsTmin2 = 2 + 4 + 0 + 1 = 7 ns

Tmin = 7 ns

** On ne peut pas réduire Tmin de 50%, le pipeline vient avec une pénalité, on ne peut pas diviser ni td ni tsu.

A

D

CLK

Q

F

D

CLK

Q

3 ns

4 ns

4 ns

B

D

CLK

Q

C

D

CLK

Q

2 ns G

D

CLK

Q

A

D

CLK

Q

F

D

CLK

Q

3 ns

4 ns

4 ns

B

D

CLK

Q

C

D

CLK

Q

2 ns G

D

CLK

Q

P1

D

CLK

Q

P2

D

CLK

Q

P3

D

CLK

Q


Le pipeline en pratique

• Le désavantage principal d’une architecture avec pipeline est son coût élevé en matériel.– Quand on introduit un étage de pipeline il faut synchroniser tous les signaux de cet

étage, même s’ils ne sont pas dans le chemin critique (exemple, dans la diapositive précédente, de la bascule C à la porte NON-OU).

– Cependant, pour les FPGAs, la présence d’une très grande quantité de bascules prédéfinies à l’intérieur des blocs de logique programmable rend possible et efficace l’utilisation d’architectures à pipeline.

• On ne peut enlever le délai td ni le temps de préparation tsu aux étages de pipeline.

• Il faut bien balancer les nouveaux chemins. La fréquence maximale d’opération du circuit est limitée par le chemin le plus lent du circuit.



Le pipeline: stratégie

• Pour ajouter un étage de pipeline, on peut suivre la stratégie suivante:1. Représenter le circuit avec les signaux qui vont de gauche à droite.2. Si une boucle de rétroaction est présente, la décomposer en répétant le registre

cible à la droite du registre source.3. Identifier le chemin critique et placer un registre de façon à le couper en formant

deux moitiés avec les délais les plus semblables possible.4. Former une courbe verticale qui traverse le circuit et qui passe à travers du registre

de pipeline ajouté.5. Ajouter un registre de pipeline à chaque intersection de la courbe et d’un signal

horizontal.



A

D

CLK

Q

F

D

CLK

Q2 ns

3 ns

2 ns

1 ns

B

D

CLK

Q

C

D

CLK

Q

tsu = 1ns

td = 2 ns

Exercice de pipeline

19


Pipeliner le circuit.Donner le code VHDL avant et après le pipeline.



20


A

D

CLK

Q

F

D

CLK

Q2 ns

3 ns

2 ns

1 ns

B

D

CLK

Q

C

D

CLK

Q

tsu = 1ns

td = 2 ns

A

D

CLK

Q

F

D

CLK

Q2 ns

3 ns

2 ns

1 ns

B

D

CLK

Q

C

D

CLK

Q

tsu = 1ns

td = 2 ns

A

D

CLK

Q

F

D

CLK

Q2 ns

3 ns

2 ns

1 ns

B

D

CLK

Q

C

D

CLK

Q

tsu = 1ns

td = 2 ns

A

D

CLK

Q

F

D

CLK

Q2 ns

3 ns

2 ns

1 ns

B

D

CLK

Q

C

D

CLK

Q

tsu = 1ns

td = 2 ns



21


A

D

CLK

Q

3 ns

4 ns

3 ns

1 nsB

D

CLK

Q

C

D

CLK

Q

4 ns

2 ns2 ns

2 ns3 ns F

D

CLK

Q

td = 2 ns, tsu = 1ns



22


A

D

CLK

Q

3 ns

4 ns

3 ns

1 nsB

D

CLK

Q

C

D

CLK

Q

4 ns

2 ns2 ns

2 ns3 ns F

D

CLK

Q


A

D

CLK

Q

3 ns

4 ns

3 ns

1 nsB

D

CLK

Q

C

D

CLK

Q

4 ns

2 ns2 ns

2 ns3 ns F

D

CLK

Q



Parenthèse: optimiser le pipeline

(pas dans les notes)

1)(

Sk

TP

Sk

TT

kLGC

p

C: coût du circuit pipelinéG: coût du circuit sans pipelinek: nombre d’étages de pipelineL: coût en registres par étage de pipeline

Tp: délai du circuit avec pipelineT: délai du circuit sans pipelineP: performance du circuit avec pipeline = 1/Tp

S: délai d’un registre de pipeline

C/P: rapport cout/performance

kopt: nombre d’étages de pipelinepour optimiser le rapport coût/performance

Quelle est la valeur de L pour un FPGA?Quel est le kopt correspondant?

S

T

L

Gkk

k

GTLS

k

PCk

GTLSkGSLT

Sk

TkLG

P

C

k

PCopt

0

2

)()(

0tan28a5

66028

0tan9a5

6609

0tan19a5

66019

0tan29a5

66029

0tan9a5

6609

0tan19a5

660190.0E+00

0.2E+04

0.4E+04

0.6E+04

nombre d'étages de pipeline k

rapp

ort d

e pe

rfor

man

ce

C/P


Minimiser la latence (1)

• Certains processeurs ne traitent pas un flux important de données, mais traitent plutôt des données ponctuelles à intervalles irréguliers.

• Dans un tel cas, il est plus important de réduire la latence que le débit.• Stratégies:

– Réduire le délai sur le chemin critique. – Réorganiser l’ordre dans lequel les calculs sont faits.– Paralléliser les calculs sur plusieurs unités.– Éviter le pipeline.



Minimiser la latence (2)

• La façon de répartir les calculs peut avoir une incidence importante sur la latence.

• Par exemple, considérons le problème de l’addition de quatre nombres. Il y a deux façons d’organiser les calculs, chacun avec sa façon de modéliser le circuit en VHDL.

• Dans la version de gauche, l’addition est faite en série. Dans celle de droite, on parallélise le premier calcul. La latence est réduite de 33%.


A

B

C

D

Somme

A

B

C

D

Somme

Somme <= A + B + C + D; Somme <= (A + B) + (C + D);


Minimiser la surface (1)

• Pour minimiser la surface utilisée, on peut utiliser le partage des ressources.• L’exemple montre deux interprétations à un modèle VHDL. La différence entre

les deux est basée sur la sélection d’une somme ou d’un opérande.• Le chemin critique est le même pour les deux, mais la version de droite n’utilise

qu’un seul additionneur.


process (D1, D2, D3, S)begin

if S = '1' thenD5 <= D1 + D2;

elseD5 <= D1 + D3;

end if;end process;

D1

D2

D3

D5

S

D1

D2

D3

D5

S


Minimiser la surface (2)

• Une autre approche consiste à utiliser des stratégies contraires à celles utilisées pour maximiser le débit en éliminant le parallélisme dans les calculs.

• Au lieu d’instancier plusieurs composantes identiques pour effectuer des calculs, on en n’utilise qu’une seule et on en contrôle l’accès à l’aide d’une unité de contrôle qui implémente une machine à états.



Parenthèse: favoriser la surfaceou le délai lors de la synthèse

(pas dans les notes)


Niveaux de compromis de design et leur impact

• En règle générale, plus une décision de design est prise à un haut niveau d’abstraction et plus son impact sera grand sur la performance et la surface d’un système.

• Une bonne décision prise à un bas niveau d’abstraction ne peut pas en général compenser pour une mauvaise décision prise à un haut niveau d’abstraction.


choix de l’algorithme

choix de l’implémentation de l’algorithme(p. ex. parallèle ou sérielle)

choix de la précision des calculs

choix des circuits

Haut niveau d’abstraction

Bas niveau d’abstraction






Exemple de conception:réduction du bruit dans un signal audio à l’aide d’un filtre

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-1

0

1

signal d'entrée

ampl

itude

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-1

0

1

signal de sortie

temps (secondes)

ampl

itude


Exemple: filtre numérique

• Structure d’un filtre numérique à réponse impulsionnelle finie.

M

k

knxkhny0

)()()(


Design #1: forme directe de base

entity fir is generic (

Win : positive := 8;Wout : positive := 20

);port (

reset_n, clk : in std_logic;x : in signed(Win - 1 downto 0);y : out signed(Wout - 1 downto 0)

);end fir;

L’entrée est exprimée sur 8 bits, la sortie sur 20.Au fil des calculs, plus de bits sont nécessaires pour représenter les résultats intermédiaires.Par exemple deux nombres de 8 bits multipliés ensemble donnent un résultat exprimé sur 16 bits.Les coefficients h(i) sont des constantes.

Exercice: donner le code VHDL:a. de la ligne de délai;b. des produits et de leur accumulation.


Design #1: forme directe de basedéfinition de constantes et de types

library IEEE;use ieee.numeric_std.all;

package firpack is

constant Win : integer := 8;constant Wout : integer := 20;

type coefficients is array(natural range <>) of integer range -(2 ** (Win - 1)) to 2 ** (Win - 1);constant h : coefficients := (-12, 8, 17, 4, -20, -11, 47, 107, 107, 47, -11, -20, 4, 17, 8, -12);

type ligneDelais is array(0 to h'length - 1) of signed(Win - 1 downto 0);

type produits is array(0 to h'length - 1) of signed(2 * Win - 1 downto 0);

end firpack;

Il existe des algorithmes pour obtenir la valeur des coefficients en fonction de la réponse en fréquence désirée pour le filtre.Les coefficients montrés ici ont été obtenus à l’aide de MATLAB.


Design #1: forme directe de basecodage de la ligne de délais

-- ligne de délaisprocess(clk)begin

if rising_edge(CLK) thenif (reset_n = '0') then

xDelai <= (others => (others => '0'));else

for k in xDelai'length - 1 downto 1 loopxDelai(k) <= xDelai(k - 1);

end loop;xDelai(0) <= x;

end if;end if;

end process;

La ligne de délai est composée de 16 registres en série pour entreposer des versions retardées de x(n), x(n-1), x(n-2), …, x(n- 15).


Design #1: forme directe de basecodage des produits et de leur accumulation

-- génération et addition des produits, et sortie finale-- y <= h(0) * xDelai(0) + h(1) * xDelai(1) + ... + h(15) * xDelai(15);process(clk)variable somme : integer := 0;begin

if rising_edge(CLK) thenif reset_n = '0' then

y <= (others => '0');else

somme := 0;for k in 0 to xDelai'length - 1 loop

somme := somme + to_integer(h(k) * xDelai(k));end loop;y <= to_signed(somme, y'length);

end if;end if;

end process;

Les produits sont calculés et additionnés tous ensemble. Une boucle simplifie l’écriture mais n’implique pas de séquence de calcul: tout est concurrent.

Latence de 1 registre, 1 cycle.(On ne compte pas le premier registre dans lequel on place la donnée en entrée)


• Ressources utilisées:– Number of Slices: 190 out of 13696 1% – Number of Slice Flip Flops: 148 out of 27392 0% – Number of 4 input LUTs: 270 out of 27392 0% – Number of MULT18X18s: 12 out of 136 8%

• Période minimale d’horloge et chemin critique– Minimum period: 25.436ns (Maximum Frequency: 39.314MHz)– Source: xDelai_0_0 (FF)– Destination: y_19 (FF)– Data Path Delay: 25.436ns (Levels of Logic = 40)

• Latence:– 1 cycle

Design #1: forme directe de baserésultats de synthèse


Filtre numérique

Exercice:Proposer une architecture pour maximiser le débit.


Design #2: forme directe avec les produits pipelinéset un arbre binaire d’additions pipeliné

Chaque produit est placé dans un registre.

Les produits sont accumulés deux à la fois, ce qui correspond aux modules d’addition sur les FPGA.Chaque somme est placée dans un registre.

Dans cette version, le chemin critique est le plus court possible, mais il n’est pas clair à partir du schéma où celui-ci se trouve.

niveau 1

niveau 2

niveau 3

niveau 4: addition finale Latence de 5 registres, 5 cycles.

niveau 0

type addniv1 is array(0 to h'length / 2 - 1) of signed(2 * Win - 1 + 1 downto 0);type addniv2 is array(0 to h'length / 4 - 1) of signed(2 * Win - 1 + 2 downto 0);type addniv3 is array(0 to h'length / 8 - 1) of signed(2 * Win - 1 + 3 downto 0);

Exercice: donner le code VHDLde l’arbre binaire d’additions.





xDelai <= (others => (others => '0'));else



end if;end if;

end process;

-- registres des produitsprocess (clk)begin


lesproduits <= (others => (others => '0'));else

for k in 0 to lesproduits'length - 1 looplesproduits(k) <= h(k) * xDelai(k);

end loop;end if;

end if;end process;

La même ligne de délai que pour le design #1.



-- addition des produits avec un arbre binaire pipeliné et sortie finaleprocess(clk)variable somme : integer := 0;begin

if rising_edge(clk) thenif reset_n = '0' then

lesaddniv1 <= (others => (others => '0'));lesaddniv2 <= (others => (others => '0'));lesaddniv3 <= (others => (others => '0'));

else

for k in 0 to h'length / 2 - 1 looplesaddniv1(k) <= resize(lesproduits(2 * k), lesaddniv1(k)'length)

+ resize(lesproduits(2 * k + 1), lesaddniv1(k)'length);end loop;

for k in 0 to h'length / 4 - 1 looplesaddniv2(k) <= resize(lesaddniv1(2 * k), lesaddniv2(k)'length)

+ resize(lesaddniv1(2 * k + 1), lesaddniv2(k)'length);end loop;

for k in 0 to h'length / 8 - 1 looplesaddniv3(k) <= resize(lesaddniv2(2 * k), lesaddniv3(k)'length)

+ resize(lesaddniv2(2 * k + 1), lesaddniv3(k)'length);end loop;

end if;end if;

somme := to_integer(lesaddniv3(0) + lesaddniv3(1));y <= to_signed(somme, y'length);

end process;

La fonction resize est utilisée pour que les sommes progressent en largeur d’un bit à la fois.

Trois boucles donnent une écriture concise.


• Résultats de la synthèse:– ressources utilisées:

• Number of Slices: 204 out of 13696 1% • Number of Slice Flip Flops: 360 out of 27392 1% • Number of 4 input LUTs: 242 out of 27392 0% • Number of MULT18X18s: 12 out of 136 8%

– période minimale d’horloge et chemin critique• Minimum period: 3.166ns (Maximum Frequency: 315.856MHz)• Source: Mmult_lesproduits_8_mult0000 (MULT)• Destination: lesaddniv1_4_16 (FF)• Data Path Delay: 3.166ns (Levels of Logic = 18)

– latence:• 5 cycles



Sommairecircuit de base vs circuit pipeliné

design détails LUT FF Mul Tmin

(ns)Débit

(cycles/résultat)

Débit(ns/résultat)

Latence(cycles)

Latence(ns)

1 base 270 148 12 24.4 1 24.4 1 24.4

2 pipeliné 242 360 12 3.17 1 3.17 5 15.9


Filtre numérique

Exercice:Proposer une architecture pour minimiser la surface.Conseil: utiliser un seul multiplicateur et un seul additionneur.


Design #3: forme compacte avec machine à étatschemin des données

Un seul multiplicateur.Même ligne de délais que les deux autres designs.Un pointeur permet d’accéder chaque donnée x et chaque coefficient, un à la fois.Une unité de contrôle doit régler la séquence des calculs ainsi que l’échange des données x(n) et y(n) avec le monde extérieur.



xDelai <= (others => (others => '0'));elsif (etat = attente) and (go = '1') then



end if;end if;

end process;


Design #3: forme compacte avec machine à étatstype type_etat is (attente, accumulation);signal etat : type_etat;

-- ...

-- chemin des données intégré à l’unité de contrôlecontrole : process (CLK)variable pointeur : integer range 0 to 15;variable somme : integer;begin

if rising_edge(CLK) thenif reset_n = '0' then

etat <= attente;y <= (others => '0');

elsecase etat is

when attente =>pointeur := 0;somme := 0;if go = '1' then

etat <= accumulation;end if;

when accumulation =>somme := somme+ to_integer(h(pointeur) * xDelai(pointeur));if pointeur = 15 then

etat <= attente;y <= to_signed(somme, y'length);

elsepointeur := pointeur + 1;

end if;when others =>

etat <= attente;end case;

end if;end if;

end process;

pret <= '1' when etat = attente else '0';


• Résultats de la synthèse:– ressources utilisées:

• Number of Slices: 127 out of 13696 0% • Number of Slice Flip Flops: 173 out of 27392 0% • Number of 4 input LUTs: 124 out of 27392 0% • Number of MULT18X18s: 1 out of 136 0%

– période minimale d’horloge et chemin critique• Minimum period: 7.420ns (Maximum Frequency: 134.768MHz)• Source: pointeur_0 (FF)• Destination: y_19 (FF)• Data Path Delay: 7.420ns (Levels of Logic = 11)

– latence:• 17 cycles

Design #3: forme compacte avec machine à états


Sommaire

Design #1

Design #2

Design #3


Sommaire

design détails LUT FF Mul Tmin

(ns)Débit

(cycles/résultat)

Débit(ns/résultat)

Latence(cycles)

Latence(ns)

C/Pv. 1

C/Pv.2

1 base 270 148 12 24.4 1 24.4 1 24.4 6.59 39

2 pipeliné 242 360 12 3.17 1 3.17 5 15.9 0.77 5.7

3 compact 124 173 1 7.42 17 126 17 126.1 15.6 50

Métrique Coût/Performance:On peut prendre Coût = nombre de LUTs (un petit nombre est bon!)et Performance = 1/Débit (un grand nombre est bon!)

On obtient C/P = {6.59K, 0.77K, 15.6K} pour les designs 1, 2, 3.Le design #2 est donc le meilleur selon cette métrique.

Avec C = #LUT + #FF + 100 × #Mul, on obtient C/P = {39K, 5.7K, 50K},ce qui mène à la même conclusion.

La morale: pour les FPGAs, il est très avantageux de pipeliner un design au maximum, à moins d’avoir à rencontrer des contraintes très strictes d’utilisation des ressources.


Niveaux de compromis de design et leur impact

• Pour le problème de l’implémentation d’un filtre, on peut considérer les décisions à prendre aux quatre niveaux vus précédemment:


choix de l’algorithme

choix de l’implémentation de l’algorithme(p. ex. parallèle ou sérielle)

choix de la précision des calculs

choix des circuits

Quel type de filtre?

Forme pipelinée ou compacte?

Combien de bits de précision pour les entrées et pour les résultats intermédiaires?

Quels types d’additionneurs et de multiplicateurs?

Haut niveau d’abstraction

Bas niveau d’abstraction






Sept principes de conception FPGA

• Nous présentons sept principes de conception qui sont applicables principalement aux implémentations sur FPGA.

1. Adopter un style de conception synchrone;2. Utiliser des bascules (flip-flop) plutôt que des loquets (latch);3. Définir un signal d’initialisation globale;4. Utiliser les réseaux de distribution de signaux d’horloge;5. Exploiter toutes les ressources disponibles sur le FPGA;6. Effectuer une disposition manuelle des blocs sur le chemin critique; et,7. Favoriser l’arithmétique en virgule fixe plutôt que flottante.



Principe de conception FPGA #1:conception synchrone

• On obtient en général de biens meilleurs résultats avec un FPGA en adoptant un style de conception synchrone. Les structures asynchrones sont mal adaptées aux FPGAs.

• Il faut aussi éviter de se fier aux délais d’une composante ou du routage d’un signal, surtout si on utilise un synthétiseur et des outils d’implémentation automatiques. Par exemple, on pourrait être tenté de retarder un signal en le faisant passer par deux inverseurs en cascade. Cependant, un synthétiseur aura tôt fait d’éliminer cette structure inutile du point de vue fonctionnel.

• Les signaux d’initialisation des bascules devraient aussi être synchrones.



Principe de conception FPGA #2:bascules vs loquets

• Dans un ASIC sur mesure ou un ASIC à cellules normalisées, les loquets offrent plusieurs avantages. Tout d’abord, ils requièrent la moitié des transistors d’une bascule. En utilisant des techniques spéciales, on parvient à obtenir des circuits fiables et plus rapides qu’avec des bascules.

• Cependant, pour un FPGA le coût est identique entre une bascule et un loquet. Il est donc grandement avantageux de toujours utiliser des bascules.


Xilinx inc., Virtex-5 FPGA User Guide (ug190 v. 5.4), March 2012


Principe de conception FPGA #3:initialisation globale

• Il est avantageux d’utiliser un signal unique pour initialiser toutes les bascules parce que la plupart des FPGAs comportent un chemin spécial pour accomplir cette tâche.



Principe de conception FPGA #4:génération et distribution de l’horloge

• Le routage inadéquat d’un signal d’horloge peut résulter en un déphasage d’horloge et une réduction des performances du circuit.

• Un signal d’horloge généré sur le FPGA devrait être passé à un tampon d’horloge (Xilinx: Global Clock Buffer, un Virtex-5 en contient 32).

• Pour les outils de Xilinx, il faut insérer le symbole « BUFG » à la sortie du générateur d’horloge.



Principe de conception FPGA #5:exploitation de toutes les ressources (1)

• Les ressources en place dans un FPGA sont ‘gratuites’.– Une fois une puce choisie pour un système, il ne coûte ‘rien’ d’utiliser toutes les

ressources qu’elle contient.– Ce raisonnement n’est pas vrai nécessairement pour les autres technologies, comme

pour les ASICs à cellules normalisées.– On néglige ici la consommation de puissance.

• Dans ce cas, il est très avantageux d’utiliser les registres présents dans les blocs logiques en adoptant une architecture à pipeline.– Cette approche peut réduire significativement les délais de propagation sur le

chemin critique et accélérer ainsi le débit de données que le système peut supporter.– Le seul inconvénient est l’augmentation de la latence.– Beaucoup d’applications sont insensibles à une latence de plusieurs dizaines de

cycles d’horloge de 100 MHz ou plus, ce qui rend les architectures à pipeline très intéressantes.




• Un corolaire de ce principe est qu’il est avantageux de placer deux registres supplémentaires dans le chemin de chaque entrée et sortie du système.– Le premier registre est placé dans le bloc d’entrées-sorties du FPGA, diminuant au

minimum le délai pour la saisie du signal.– Le deuxième registre donne beaucoup de flexibilité au placeur et au routeur pour

déterminer l’emplacement optimal du module qui doit traiter ce signal.




• Les délais de propagation peuvent être grandement réduits en limitant la charge à la sortie d’un module.– On peut atteindre ce but en employant un arbre de distribution.– Le principe consiste à faire mener une charge réduite composée d’un groupe de

bascules.– Chacune de ces bascules peut ensuite mener les modules qui doivent recevoir le

signal.– Dans la description du circuit, il s’agit d’utiliser des noms différents pour des signaux

identiques, ce qui devrait empêcher l’outil de synthèse de les combiner.



Principe de conception FPGA #6:disposition manuelle

• Il peut être très avantageux de faire la gestion manuelle de la disposition (floorplanning) pour les parties critiques d’un circuit.

• Les manufacturiers de FPGA offre des outils qui permettent de déterminer la position absolue ou relative de certains registres sur la puce.

• On laisse ensuite les outils automatisés faire la disposition du reste du circuit.• En plaçant manuellement les blocs les plus lents, on facilite la tâche du placeur

automatique et on accélère cette étape.• L’avantage principal, cependant, est qu’on peut en arriver à une solution

réellement optimale (i.e. qui ne peut être améliorée).• L’inconvénient est que ce travail peut être ardu et pénible, et il devrait donc être

réservé uniquement aux parties critiques d’un système.



Principe de conception FPGA #7:arithmétique en virgule flottante ou fixe

• En pratique, on requiert rarement la très grande précision (8 chiffres significatifs et plus) offerte par les calculatrices et les microprocesseurs à usage général.

• À part pour les applications financières et certaines applications scientifiques, de trois à cinq chiffres significatifs suffisent amplement.

• Ceci est spécialement vrai pour les systèmes qui traitent des données provenant de phénomènes naturels comme les sons ou les signaux électromagnétiques.– La voix dans un système téléphonique est échantillonnée avec 8 bits.– Les sons enregistrés sur un CD audio le sont avec 16 bits.– Les pixels sont encodés sur 8 bits.

• Il y a au moins un ordre de grandeur de différence en complexité et en performance entre un circuit arithmétique qui fonctionne en virgule fixe par rapport à un circuit semblable qui fonctionne en virgule flottante.

• Il est utile lors de la modélisation du circuit de tenir compte de ce fait et de mesurer les conséquences d’utiliser un système à virgule fixe.– 10 bits donnent une précision de 3 chiffres significatifs.– 20 bits donnent une précision de 6 chiffres significatifs.



Sept principes de conception FPGA

• Nous présentons sept principes de conception qui sont applicables principalement aux implémentations sur FPGA.

1. Adopter un style de conception synchrone;2. Utiliser des bascules (flip-flop) plutôt que des loquets (latch);3. Définir un signal d’initialisation globale;4. Utiliser les réseaux de distribution de signaux d’horloge;5. Exploiter toutes les ressources disponibles sur le FPGA;6. Effectuer une disposition manuelle des blocs sur le chemin critique; et,7. Favoriser l’arithmétique en virgule fixe plutôt que flottante.







Documentation de systèmes numériques (1)

• La documentation adéquate d’un système numérique est essentielle à toutes les étapes de son cycle de vie.

• Dans la phase de conception et de réalisation, la documentation formalise le processus en assurant que les procédures nécessaires sont suivies. Elle permet de suivre l’évolution du design dans le temps par des balises définies systématiquement. Pour le travail en équipe, la documentation est absolument essentielle.

• Dans la phase de maintenance, la documentation permet de comprendre le fonctionnement du circuit pour le réparer et le mettre à jour. Ceci est vrai autant pour une personne qui doit modifier un système conçu par d’autres que pour le cas où l’on doit modifier son propre systèmes plusieurs mois plus tard.




• Tous les principes de documentation du logiciel s’appliquent à la documentation d’un système numérique. Cependant, elle comporte des éléments différents. On peut noter entre autres les éléments suivants.– Les diagrammes de bloc identifient les modules principaux du système ainsi que les

interfaces entre les modules. Dans un diagramme de bloc, on devrait éviter d’identifier des composantes particulières. Le but de ce diagramme est de donner une vue d’ensemble du système sans nécessairement spécifier son implémentation. Il peut être utile de spécifier les noms des signaux d’interface de haut niveau.

– Une description fonctionnelle du système sous forme de texte narratif permet d’expliquer comment celui-ci doit se comporter dans différentes situations. C’est aussi dans ce genre de document qu’on peut expliquer les particularités du système, la philosophie du design, et les raisons qui ont poussé les concepteurs à choisir certaines options plutôt que d’autres.




• … suite …– Une description des fonctions logiques du système peut être formée d’une

combinaison de schémas logiques, de code HDL et de diagrammes d’états. Pour le travail en équipe, le code HDL doit suivre des directives et conventions acceptées par le groupe. Ces conventions devraient inclure des paramètres aussi diversifiés qu’un format normalisé pour les en-têtes de fichiers, la façon de choisir des identificateurs et la façon d’écrire une structure de sélection. Des conventions doivent aussi être en place pour les schémas logiques et les diagrammes d’états. Il faut éviter que les schémas logiques ressemblent à des spaghettis en limitant le nombre de modules sur un seul schéma en les hiérarchisant. On augmente grandement la lisibilité d’un diagramme en réduisant la longueur des interconnexions et en réduisant le nombre d’angles dans les interconnexions.

– Des diagrammes de synchronisation décrivent les caractéristiques dynamiques du système. On spécifie habituellement trois paramètres : une valeur maximale, une valeur minimale, et une valeur typique. La valeur typique est celle qu’on peut s’attendre d’observer dans la plupart des cas. Les valeurs minimale et maximale doivent être utilisées pour concevoir un système robuste en toute situation.




• … suite …– Les schémas électriques énumèrent les composantes matérielles du système et

identifient les connexions de patte à patte. À partir du schéma, on doit pouvoir dresser la liste des matériaux nécessaires pour construire le circuit (bill of materials – BOM). En fait, il devrait être possible de construire le circuit sans en comprendre le fonctionnement.



Et pour finir, quelques principes généraux de conception (1)

1. De bons outils de conception et d’analyse ne garantissent pas le succès mais facilitent la tâche.

2. Les circuits numériques sont bâtis avec des composantes analogiques et ont donc des caractéristiques analogiques dont il faut tenir compte.

3. Documenter, documenter, documenter. Pour les autres, et pour vous.4. Utiliser des pratiques normalisées de codage et de documentation sauve

beaucoup de temps.5. La conception de machines à états est un art similaire à celui de la

programmation.6. Toujours rechercher la manière la plus efficace d’atteindre le but.7. Le système qui doit être conçu devra éventuellement être fabriqué et testé. On

gagne beaucoup à tenir compte de la testabilité du système pendant sa conception.



Et pour finir, quelques principes généraux de conception (2)

8. La logique programmable est d’une grande utilité à cause de la flexibilité qu’elle offre au concepteur.

9. Éviter les systèmes asynchrones.10. Porter une attention particulière à la synchronisation entre deux systèmes

asynchrones l’un par rapport à l’autre.11. Le débogage d’un système est un art qui repose sur la maîtrise des trois

principes suivants :– la compréhension de la spécification;– le contrôle des entrées du module à déboguer; et,– l’observation des signaux internes, de l’état et des sorties du module à déboguer.



Notions à retenir et maîtriser Importance relative

1. Expliquer les concepts de débit d’information et de latence de calcul, et comment ils sont reliés au délai du chemin critique, à la fréquence d’horloge et au parallélisme. 20

2. Pipeliner un circuit numérique pour en augmenter le débit.a. Synchroniser correctement le pipeline.b. Tenir compte du principe d’équilibre entre les chemins.c. Donner la nouvelle latence de calcul, le nouveau débit et les coûts. d. Expliquer les particularités, avantages et inconvénients du pipeline sur FPGA.

40

3. Nommer et expliquer quatre stratégies pour minimiser la latence de calcul. 154. Nommer et expliquer deux stratégies pour minimiser la surface utilisée. 155. Énumérer et expliquer les principes suivants pour guider l’utilisation de FPGA:conception synchrone, utiliser des bascules plutôt que des loquets, initialisation globale, distribution d’horloge, utilisation des ressources ‘gratuites’, disposition manuelle et calculs en virgule fixe

10

Total 100

Résumé: performance – délai et espace

70

Documents

INF3500 : Conception et implémentation de systèmes numériques Pierre Langlois Cours #11 Performance