CHAPITRE 4 : METHODOLOGIE
4.1 UIntroduction
Le problème de trouver les chemins les plus courts joue
un rôle central dans la conception et l'analyse des réseaux.
Plusieurs problèmes de routage peuvent être résolus comme
des problèmes de recherche du chemin le plus court une fois que le
coût approprié est assigné à chaque lien, en
reflétant par exemple sa bande passante disponible, le délai ou
taux d'échec de bit.
Il existe plusieurs algorithmes de détermination du
chemin le plus court si le coût dans un réseau est
caractérisé par une métrique additive positive. Le plus
populaire algorithme du plus court chemin est bien entendu l'algorithme de
Dijkstra qui est utilisé comme nous l'avons déjà dis dans
le protocole de routage OSPF (Internet's Open Shortest Path First).
Dans les chapitres qui précèdes, nous avons
parlé du routage, des composants FPGA et du langage VHDL, dans ce
chapitre nous allons faire comme une sorte de synthèse
c'est-à-dire que nous allons présenter à partir de tous ce
qui a déjà été dis la méthodologie
d'implémentation de l'algorithme de Dijkstra sur les processeurs
FPGA.
Dans un premier temps, nous allons d'abord présenter
de façon générale la synthèse des circuits en VHDL,
ensuite nous expliquerons le fonctionnement de l'algorithme de Dijkstra,
Et nous terminerons ce chapitre en présentant le
programme complet d'implémentation.
4.2 USynthèse des circuitsU
[12]
4.2.1 ULe synthétiseurU
Le synthétiseur est un compilateur particulier capable,
à partir du langage de descriptions VHDL ou Verilog, de
générer une description structurelle du circuit. A travers le
style d'écriture de la description synthétisable
(niveau RTL Registre Transfer Level), le synthétiseur va
reconnaître un certain nombre de primitives qu'il va
implanter et connecter entre elles. Ce sera au minimum des portes NAND, NOR,
NOT, des bascules D, des buffers d'entrées-sorties, mais cela peut
être aussi un compteur, un multiplexeur, une RAM, un registre, un
additionneur, un multiplieur ou tout autre bloc particulier.
Le VHDL décrit la fonctionnalité
souhaitée et ceci indépendamment de la technologie. Le nombre de
primitives trouvées par le synthétiseur donne une
évaluation de surface (pour un ASIC) ou de remplissage (pour un FPGA).
La technologie choisie apporte toutes les données
temporelles relatives aux primitives, notamment les temps de traversée
de chaque couche logique sont connus. Une première évaluation de
vitesse d'ensemble du circuit peut ainsi être réalisée par
le synthétiseur (en considérant des retards fixes par porte, ce
qui constitue une approximation grossière).
Outre la description VHDL, le concepteur a la
possibilité de fournir au synthétiseur des contraintes
temporelles (réalistes) ou de caractéristiques
électriques des entrées-sorties. Le synthétiseur, par un
certain nombre d'itérations, essaiera d'optimiser le
produit surface-vitesse.
Le synthétiseur idéal est un outil capable
d'avoir jusqu'à la vision physique du circuit projeté. De tels
outils sont en train de sortir sur le marché. De façon plus
classique, l'optimisation du circuit final sera obtenue après avoir fait
remonter les informations temporelles d'après routage au niveau du
synthétiseur et après avoir procédé à
plusieurs itérations.
4.2.2 ULa cible
technologiqueU
4.2.2.1 UAsic et PLDU
Les ASIC (Application Specific Integreted Circuit) sont des
circuits intégrés numériques ou mixtes originaux. En ce
qui concerne l'aspect numérique, on dispose en général
d'une bibliothèque de fonctions pré-caractérisées
c'est à dire optimisées par le fondeur et quant au reste du
Design, le VHDL ou VERILOG ciblera des primitives NAND, NOR, Multiplexeur,
Bascules D, et Mémoires RAM ou ROM.
Avantages de l'ASIC
n Originalité
n Intégration mixte analogique numérique
n Choix de la technologie
n Consommation
Inconvénients
n Coût de développement très
élevés (ne peut être amorti en général que
pour de très grand nombre de circuits)
n Délais de fabrication et de test
n Dépendance vis à vis du fondeur.
Les PLD (Programmable Logic Device) sont des circuits disponibles
sur catalogue mais exclusivement numériques.
Avantages des PLD
n Personnalisation et mise en oeuvre simple
n Outils de développement peu coûteux (souvent
gratuits)
n Pas de retour chez le fabriquant
n Idéal pour le prototypage rapide
Inconvénients des PLD
n Peut être cher pour de grandes séries
n Consommation globale accrue par les circuits de configuration
n Les primitives du fabricant pouvant être complexes, la
performance globale est dépendante pour beaucoup de l'outil
utilisé.
Afin d'annuler en partie les inconvénients des PLD, les
fabricants proposent des circuits au Top de la technologie (ce qui rend encore
plus cher l'ASIC équivalent). Ainsi actuellement on trouve des circuits
en technologie 0,13um tout cuivre basse tension. La consommation est ainsi
réduite et la vitesse augmentée d'autant.
| 
