Le temps de routage pour FPGA : importance,

réduction par réplication

E. Fabiani

Projet COSI

Séminaire COSI ‘ 01

E. Fabiani 2

Plan

ContexteExpérimentations de placement structurelLa réplication du routageExemple pour Xilinx VirtexConclusion

E. Fabiani 3

Contexte

L’implémentation de réseaux réguliers sur circuits reconfigurables

Méthode choisie : Placement structurelpour réduction du temps de placement routageet amélioration de la fréquence d ’horloge

E. Fabiani 4

Contexte

Génération des formesde processeurs

FRAP : Fpga Regular Array Placer

Placement du réseau en serpentin

Placement internedes processeurs

description structurelle

avec placement

bibliothèqued'opérateurs

technologie du FPGA ciblé

description structurelle

sans placement

E. Fabiani 5

ExpérimentationsExpérimentations sur circuits FPGAs Xilinx XC40250 et XCV800

2 types de FPGAs Xilinx : •XC40250 : famille 4000XV, 92x92 CLBs (16928 LUTs)

•XCV800 : famille Virtex, 56x84 CLBs (18816 LUTs)

Réseaux réguliers:•convolution unidirectionnelle avec multiplieur constant (4, 8, 16 bits)•samba (comparaison de séquences ADN)•algorithme k-means pour images hyperspectrales

Mesures : placement/routage avec ou sans contraintes de placement •temps de placement•temps de routage •temps total•fréquence d ’horloge

E. Fabiani 6

Expérimentations

Gains en temps de placement

0

5

10

15

20

25

conv4 conv8 conv16 samba kmean

XCV800

XC40250

Gains en fréquence d’horloge

0

0.5

1

1.5

2

2.5

3

3.5

conv4 conv8 conv16 samba kmean

XCV800

XC40250

E. Fabiani 7

Expérimentations

Gains en temps de routage

0

0.5

1

1.5

2

2.5

3

3.5

conv4 conv8 conv16 samba kmean

XCV800

XC40250

Gains en temps deplacement/routage

0

1

2

3

4

5

6

7

conv4 conv8 conv16 samba kmean

XCV800

XC40250

E. Fabiani 8

ExpérimentationsExpérimentations avec contraintes de délai critique sur Virtex 800

0

1

2

3

4

5

6

7

conv4 conv8 conv16 samba kmean

ntc

3

2

1.75

1.5

1.25

1.125

1

Gains en temps de placement/routage

0

0.5

1

1.5

2

2.5

3

conv4 conv8 conv16 samba kmean

ntc

3

2

1.75

1.5

1.25

1.125

1

Gains en fréquence d’horloge

E. Fabiani 9

Expérimentations

•Evolution des outils : le temps de placement/routage est devenu un argument de vente•Meilleur compromis des outils entre temps de placement/routage et fréquence

Exemple : avec contraintes de délai : + 50% pour la fréquence, + 300% pour le temps de placement/routage

•Temps de routage pas diminué systématiquement, voire plus long•FRAP : nombre maximal de processeurs, unidirectionnel : congestion ? •Autres raisons ?

Amélioration de la fréquence d ’horloge mais diminution limitée du temps de placement/routage

Pourquoi?

•Soient Tp1 et Tr1 : temps de placement et routage sans contraintes Tp2 et Tr2 : temps de placement et routage avec contraintes

gain de temps g = (Tp1+Tr1)/(Tp2+Tr2)•Si on suppose : Tp1 >>> Tp2 et Tr1<= Tr2

alors g <= 1 + Tp1/Tr1

Observations

Quantifier le ratio Tp1/Tr1

E. Fabiani 10

Expérimentations

•L ’importance du temps de routage limite le gain de temps potentiel•cela semble s ’accentuer avec l ’évolution technologique

2 solutions :•faire un placement tenant compte de la congestion•répliquer le routage quand c’est possible

0

1

2

3

4

5

6

7

8

ntc

3

2

1.75

1.5

1.25

1.125

1

conv4 conv8 conv16 samba kmean

Ratio temps de placement/ temps de routage

E. Fabiani 11

Réplication de routage

... ...

1.Trouver un routage intra-processeur et le répliquer

2.Trouver un routage inter-processeurs et le répliquer

Principe

•outils pour la réplication •architecture du FPGA•routage sans conflits

Limitations :

E. Fabiani 12

Réplication de routage

Limitations : architecture du FPGA

L ’Architecture de routagedoit être régulière = mêmes ressources de routage accessibles en tout point du FPGA

Architecture de routage

E. Fabiani 13

Réplication de routage

Limitations : architecture du FPGA

contre-exemple

E. Fabiani 14

Réplication de routage

Granularité des blocslogiques reconfigurables

Limitations : architecture du FPGA

Perte de surface

E. Fabiani 15

Réplication de routage

Limitations : conflits de routage

Il y a conflit si :•un routage sort du périmètre des BLs utilisés•cette ressource de routage est utilisée par le PE voisin

Solutions :• considérer le périmètre de routage comme périmètre du processeur• empêcher tout routage en dehors d ’un périmètre pré-défini (cf thèse R. Tessier)• autoriser le routage en dehors du périmètre, en contrôlant l ’absence de conflit

E. Fabiani 16

Exemple pour Virtex

Architecture : •routage OK sauf lignes transversales (long lines)•granularité : 1 BL = 2x2 (Lut + registre)

Conflits de routage :•pas de possibilité de contraindre le routage dans une zone

(contrairement au placement)=> prendre le périmètre de routage comme limite

Outil de réplication de routage :•pas de moyen technique direct=> pistes :

•avec fpga_editor•avec XDL (Xilinx Design Language)•avec JBits

.vhd

.edf

.ncd

.bit

placement/routage

bitgen

.xdl

JBits

fpga_editor

E. Fabiani 17

Exemple pour Virtexdéfinition de modules pré-routés par fpga_editor

placement/routage

Un module (avec entrées/sorties) défini en VHDL

.edf

.ncd

.xdl

Extraction d'informations :nom des nets et blocs d'E/Spérimètre du module

nom et placement des ports d'E/S fichier VHDL pour encapsuler le module

script pour fpga_editor

module pré-placé et pré-routé (.nmc)fpga_editor

Instanciation du module dans fichier VHDL

E. Fabiani 18

Exemple pour VirtexExemple : conv16 sur Virtex

Description .ncd Description .nmc

•Elimination des nets d’E/S•Elimination des blocs d’E/S•Définition des ports externes•Définition du BL de référence

Problème : PAR n ’arrive pas à router les modules dans certaines zones du FPGA

E. Fabiani 19

Exemple pour Virtex

XDL : Xilinx design langage

Méthode : sauvegarder le module au format XDL et construire un fichier XDL avec le routage répliqué

Problème : passage de xdl a ncd avec routage : plus long que placement/routage !

Exemple :

net "Ytrans<65><8>" , cfg "_MACRO::hset" , outpin "Ytrans<65><8>" XQ , inpin "Ytrans<66><8>" F2 , pip R12C39 S1_XQ -> OUT1 , pip R12C39 OUT1 -> W5 , pip R12C38 E5 == W5 , pip R12C37 E5 -> E_P5 , pip R12C37 E_P5 -> S1_F_B2 ,

inst "Xinby119p01<13>" "SLICE" , placed R81C6 CLB_R81C6.S0 , module "hset" "hset" "Xinby119p01<13>" ,cfg "YUSED::0 XUSED::0 F:kcm01_pm/BU13:#LUT:D=((~A2*((~A1*A3)+A1))@A4) G:kcm01_pm/BU12:#LUT:D=((~A3*((~A1*A4)+A1))@A2) GYMUX::G FXMUX::F _MACRO:hset:-1 ;

Description d ’une configuration sous forme textuelle

E. Fabiani 20

Exemple pour VirtexJBits

Classes Java pour la lecture et l’écriture directe de bitstream

Exemple :

…private static final int[] INVERTER1 = Util.InvertIntArray(Expr.F_LUT(« ~F1 »));…Bitstream.set(row,col, LUT.SLICE0_F, INVERTER1);Bitstream.set(row,col, S0Control.X.X, S0Contol.X.FOUT);…Bitstream.set(row,col, OUT4.OUT4, OUT4.S0_XQ);Bitstream.set(row,col, HexNorth2.HexNorth2, HexNorth2.OUT4);Bitstream.set(row,col, HexNorth2.OUTPUT, HexNorth2.ON);Bitstream.set(row+6,col, HexSouth2.OUTPUT, HexSouth2.OFF);Bitstream.set(row+6,col, BiHexToSingle.SINGLE_EAST12_TO_HEX_SOUTH2, BiHexToSingle.ON);Bitstream.set(row+6,col, S0F1.SF1, S0F1.SINGLE_EAST12);

E. Fabiani 21

Exemple pour Virtex

Un module (avec entrées/sorties) défini en VHDL

.edf

.ncd

placement/routage

.xdl

Extraction d'informations :nom des nets et blocs d'E/Spérimètre du module

nom et placement des ports d'E/S

script pour fpga_editor

interface du module

.ncd (modifié)fpga_editor

corps du module

.bit

JBits

Core JBits instanciable

Méthode : extraction de module placé/routé à partir du bistream

E. Fabiani 22

Exemple pour Virtex

Routage inter-processeurs

2 possibilités :•Méthode similaire au routage interne :

faire une description de 2 processeurs de routage identique,isoler le routage inter-proceseurs et le sauvegarder sous forme JBits

•Utiliser JRoute pour router les connexions entre 2 macros(processeurs) et répliquer le routage trouvé

E. Fabiani 23

La phase de routage ne peut plus être négligée La réplication de routage est techniquement faisable, résultats

à expérimenter Méthode pour extraire un module pré-placé et pré-routé de

n ’importe quelle configuration (.ncd) Notion de module pré-routé également utile pour :

bibliothèque de modules pré-routés pour réduire temps de routage et avoir estimation de performance plus précise.

reconfiguration partielle : insertion de modules pré-routés sans risque de conflit de routage

Perspectives : connexion aux outils de L. Lagadec, routeur confiné.

Conclusion