FPGA

LE FLOCH OliviaDENIS Guillaume

RAMIREZ GuillaumeSPE D1

Table des matieres

1 Introduction 3

2 Interets des circuits programmables 4

3 Memoires actives programmables 63.1 Circuits numeriques synchrones . . . . . . . . . . . . . . . . . . . . . . . . 6

3.1.1 Modele de la logique synchrone . . . . . . . . . . . . . . . . . . . . 63.1.2 Composants de la logique synchrone . . . . . . . . . . . . . . . . . 63.1.3 Le registre synchrone . . . . . . . . . . . . . . . . . . . . . . . . . . 73.1.4 Assemblage de circuits synchrones . . . . . . . . . . . . . . . . . . . 83.1.5 Realisation physique des composants . . . . . . . . . . . . . . . . . 8

3.2 Definition d’une memoire active programmable . . . . . . . . . . . . . . . . 9

4 Different Composants programmables 114.1 circuit ASIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4.1.1 Les circuits semi personnalises . . . . . . . . . . . . . . . . . . . . . 134.1.2 Les circuits personnalises . . . . . . . . . . . . . . . . . . . . . . . . 154.1.3 Avantages et inconvenient de l’utilisation d’ASIC . . . . . . . . . . 16

4.2 Circuits SPLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.3 Circuits CPLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.4 Circuits FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.4.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.4.2 grain des circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.4.3 Capacite des composants SRAM . . . . . . . . . . . . . . . . . . . . 244.4.4 Comparaison avec les autres technologies . . . . . . . . . . . . . . 254.4.5 Methodologie de synthese . . . . . . . . . . . . . . . . . . . . . . . 274.4.6 Synthese du FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 FPGA a base de LUT 325.1 Presentation du probleme et definitions . . . . . . . . . . . . . . . . . . . 355.2 Synthese combinatoire pour FPGA a base de LUT . . . . . . . . . . . . . 38

6 Annexe 406.1 Abreviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.2 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7 Conclusion 42

2

Chapitre 1

Introduction

Les progres des technologies utilisees dans les systemes d’information permettentd’acceder a des applications demandant de plus en plus de puissance de calcul. Malgre lesnombreux avantages des solutions logicielles, leur cout n’est pas toujours optimal et leursperformances ne sont plus suffisantes.

En 1985, la societe Xilinx introduisait un niveau type de circuit electronique appeleFPGA (Field-Programmable Gate Array) destine a remplacer de petites quantites de lo-gique discrete. Le principe de ces meta-circuits, derives des PLA (Programmable ArrayLogic), est de fournir une certaine quantite de logique entierement programmable ; apresune phase de configuration, le FPGA se comporte comme le circuit decrit par sa program-mation. L’originalite des FPGA Xilinx est de stocker la configuration dans une memoirevive statique (SRAM), permettant ainsi de reprogrammer ces circuits a volonte, y comprisdans un systeme en train de fonctionner. Xilinc a lance le FPGA et est a present le plusgros constructeur du marche, cependant il est concurrence par Altera qui developpent untype de circuits differents.

Il existe de nombreuses architectures de circuits programmables et reprogrammables.La plus populaire aujourd’hui est celle des FPGA. A cote des industries florissantesde la conception logicielle et de circuits, les systemes programmables encore une foisrepresentent une faible partie du marche, mais c’est un domaine en pleine emergence. Toutau long de cet expose, nous allons essayer d’expliciter les avantages et les inconvenientsde l’architecture FPGA affin de comprendre pourquoi cette technologie est la plus avan-tageuse.

3

Chapitre 2

Interets des circuits programmables

Le developpement de nouvelles architectures a pour but d’augmenter les performanceset la rapidite du systeme. Trois approches technologiques existent aujourd’hui pour l’im-plantation des systemes performants, caracterises par leur degre de flexibilite:

> la premiere basee sur les processeurs generalistes> la deuxieme se base sur la definition d’architectures completement dediees> la troisiemes basee sur des circuits programmables

Pour accroıtre la puissance des processeurs generalistes, on a deux possibilites: soitaugmenter la frequence d’horloge ou exploiter le parallelisme. Cependant la puissanceque ces processeurs fournissent ne suffit pas dans le cas d’applications tres gourmandesen termes de calcul, et/ou exigentes en termes de performance, de consommation ou deplace. De plus leur cout financier est relativement important dans le cas d’applicationsspecialisees de large diffusion, ou leur flexibilite n’est pas necessaire.

Les architectures dediees en revanche fournissent la puissance de calcul et les perfor-mances requises. Les applications en traitement du signal sont un exemple type de cetteclasse de circuit. Les ASIC sont des architectures specialisees et font donc partie des archi-tectures dediees. Les circuits ASIC necessitent malheureusement de developpement treseleve ce qui implique un cout eleve; cependant le cout de production unitaire est faible.Le probleme majeur reside surtout dans le temps de developpement, car il entraıne leprobleme de l’evolution rapide des technologies. Le developpement d’un circuit ASIC estdonc une solution pour la production de grande serie de circuits dedies.

Les circuits programmables constituent une solution intermedaire entre les systemesgeneralistes et les architectures dediees et s’appuie sur la technologie en plein essor descircuits programmables, en particulier de type FPGA. Ces circuits offrent une achitecturesa moindre cout, par programme, sans passer par le processus de fonderie long et couteuxdes circuits ASICS. On obtient d’importantes performances, car les calculs sont realisesde maniere cablee et specialisee. De plus ces circuits sont reprogrammable; on parle doncde circuits dedies a une application temporaire.

4

De ce fait ces circuits ont un cout de revient plus eleve que les ASICS. L’avantagedes circuits programmable reside dans la rapidite de mise au point qu’ils procurrent. ilspermettent donc une mise au point rapide et evolutive. Un circuit logique programmableregroupe, sur une meme puce, des composants logiques configurable et des bascules. Desinterconnections programmables relient les ressources logiques entre elles. Des cellules deconfiguration memorisent les fonctions realisees par la logique et la maniere dont celle-cisont interconnectees pour fournir les resultats demandes. Les evolution des architecturesprogrammables permettent aujourd’hui d’integrer jusqu’a 500 000 portes sur un memeFPGA de type SRAM, reconfigurable a volonte.

Trois grandes classes de circuits logiques cohabitent aujourd’hui :

> SPLD> PAL> CPLD

5

Chapitre 3

Memoires actives programmables

3.1 Circuits numeriques synchrones

3.1.1 Modele de la logique synchrone

Selon l’environnement electromagnetique, un meme circuit peut reagir differemment. Ilest donc utile de tirer parti de la complexite de la realite physique et indispensable de seramener, selon les applications, a des circuits au comportement reproductible et facile-ment modelisable. Par propriete, le champs electrique varie continument dans l’espace.Onreduit la complexite spatiale du modele en limitant l’ensemble des points interessants a unnombre fini de variables. Ainsi, on definit differents modeles de circuits comme le circuitsynchrone et le circuit booleen synchrone.

Dans le modele du circuit synchrone, les valeurs evoluent en temps discret.En general,cette representation discrete correspond a des instituts separes par une periode fixe. Uncircuit booleen synchrone a son ensemble des valeurs qui peuvent prendre un nombre finide valeurs qui est 2. Les valeurs representent l’evolution dans le temps d’une grandeurelectrique.

On constate que la definition d’un circuit a logique synchrone est equivalente a celled’un automate fini. Si bien qu’en adjoignant aux circuits synchrones une memoire infinie,et en codant en base 2 les symboles de l’alphabet, on obtient une machine de Turingdeterminee, dont le modele de la logique synchrone herite de toute l’expressivite.

3.1.2 Composants de la logique synchrone

La premiere grande famille composants de la logique synchrone est celle de circuitslogiques purement combinatoires, pour lesquels le nombre de variables d’etat s est nul.Dans ce type de circuits, le temps n’intervient pas, et la valeur des variables de sortiedepend uniquement de celle des variables d’entrees. Toute composition ou jointure decircuits purement combinatoires est un circuit purement combinatoire.

6

Dans ces circuits, on peut se ramener a des applications booleennes. On peut classerles applications booleennes par le nombre n de leurs variables d’entrees arillees. Il existe16 applications binaires, dont les plus classiques sont la conjonction et la disjonction, aussiappelees logique (and) et/ou logique (or). Il existe aussi un operateur standard d’arille 3appele multiplexeur (mux) qui selectionne en sortie la valeur de sa deuxieme ou troisiemeentree en fonction de la premiere.

On utilise les tables de verite pour coder les applications booleennes, ce qui per-met de faire le rapprochement entre l’application et la memoire morte (ROM). La taillede la memoire, associee a une application booleenne a n entrees, est 2n bits. A tresgrande representation, elle ne convient pas. Il existent de nombreuses bases combina-toires qui permettent de representer une application quelconque avec seulement quelquesoperateurs. Les plus utilises proviennent de l’algebre ( algebre de Boole), de la logique oude l’electronique.

3.1.3 Le registre synchrone

Toute la puissance du circuit logique, en dehors de ses capacites purement combina-toires, reside dans deux proprietes temporelles : La premiere est la memoire elle-meme quipermet d’utiliser a un instant donne les valeurs de l’instant precedent, et la deuxieme estle rebouclage. Dans cette deuxieme propriete, les valeurs d’etat dependent de leur proprevaleur au cycle precedent, ceci permet de stocker les donnees indefiniment.

C’est grace au registre synchrone que l’on va pouvoir stocker temporairement ou defacon permanente des donnees

7

3.1.4 Assemblage de circuits synchrones

Grace a la jointure et a la composition de circuits , on peut realiser assez facilementdes applications qui auparavant etaient complexes, a partir d’assemblages de petits blocscomme on peut le constater avec la figure qui suit.

A partir d’une base combinatoire et du registre synchrone, on peut batir des circuitsa etat. L’assemblage de circuits, en utilisant les operations de jointure et de composition,peut creer un graphe oriente acyclique avec les sommets qui sont des circuits.Cependant,cette construction ne permet pas d’atteindre toute l’expressivite d’un circuit. Pour pouvoircomposer n’importe quel circuit a partir d’une base combinatoire et du registre synchrone,il faut donc augmenter les possibilites de combinaisons des circuits, en autorisant les cyclesdans les graphes d ’assemblages. Malheureusement, avec ce type de construction, on peutconstruire d’autres objets que des circuits.

3.1.5 Realisation physique des composants

La base de la realisation physique des circuits presentes dans la section precedente estle transistor.

Les possibilites de l’interrupteur qu’est le transistor ne permettent pas de travaillersur les transitions, mais seulement sur les niveaux. Pour realiser un registre, on utilisedonc les proprietes reelles des transistors : en utilisant des portes logiques, on introduitdes retards dus au temps de chargement et de dechargement des transistors ; en inserantun leger delai dans le signal d’horloge, on obtient une autre horloge legerement decalee.

8

Les transitions d’etat de l’horloge sont repercutees un peu plus tard sur la copie, et encombinant l’horloge et sa copie, on peut obtenir un signal dont l’etat indique la presenced’une transition de l’horloge.

La fabrication d’un circuit integre complet, implantation physique d’un circuit syn-chrone, est une operation tres longue et difficile ; mais on effectue une decomposition dutravail de conception en couches ce qui rend plus facile le developpement d’un circuit.La complexite de la fabrication tient au fait que, si le travail peut etre hierarchise, lesproblemes physiques interviennent a tous les niveaux.

Les circuits a facon (full custom) sont dessines entierement par le concepteur. Ils sontdonc aussi rapides et importants que la technologie peut le permettre, mais leur conceptionest extremement difficile.

Les prediffuses et les mers de portes (gate array et sea of gates) sont des circuits dontla partie logique est standard et bien caracterisee par le constructeur. Le concepteur secontente d’indiquer un reseau de connexion des portes. Cette methode permet des densitesmoindres, mais le travail est facilite car le constructeur a deja regle la plus part des detailselectriques.

Les circuits logiques programmables contiennent des reseaux de portes logiques et d’in-terconnexions programmables. Une couche de memoire volatile ou permanente configureles elements et le circuit physique incarne alors le circuit synchrone correspondant a laconfiguration. La densite est tres faible comparativement aux precedents, mais les circuitssont deja entierement manufactures, et la configuration n’intervient qu’a posteriorie. Lescaracteristiques electriques du circuit sont donc parfaitement maıtrisees par le construc-teur, et peu de problemes sont laisses a l’utilisateur. Ce type de circuit est le plus prochedu modele de la logique synchrone.

3.2 Definition d’une memoire active programmable

Une Memoire Active Programmable (ou PAM) est un circuit logique configurableuniversel, constitue d’un arrangement regulier de cellules logiques elementaires identiques,attache a un ordinateur traditionnel hote en tant que coprocesseur. Cette definition donneles caracteristiques exactes d’une PAM quant a sa nature, son contenu et son utilisation :- Une PAM est un circuit ou un ensemble de circuits speciaux, que l’on peut qualifier devirtuels ou programmables. Ces circuits sont constitues de deux parties : la memoire deconfiguration, a laquelle on accede en ecriture lors de la configuration, puis en lecture lereste du temps, et les elements logiques programmables dont les fonctionnalites dependentde la configuration. Ces circuits ont donc deux modes : le mode de configuration ou lamemoire de configuration est remplie, et le mode d’execution ou le circuit physique incarnele circuit logique decrit par la configuration.

9

En regroupant des FPGA sur une carte, on peut fabriquer un coprocesseur physi-quement fige, mais capable de se comporter comme n’importe quel circuit d’une taillemaximale donnee. Ce coprocesseur materiel reconfigurable nomme Memoire Active Pro-grammable PAM pour Programmable Active Memory, peut etre Utilisee dans de nom-breuses applications.

Les PAM representent une solution intermediaire entre les implementations logicielleset materielles, car ils ne necessitent pas de developpement materiel et que la conceptionde configuration est simple. Il existe differents composants programmable tel que ASIC,SPLD, CPLD, FPGA...

10

Chapitre 4

Different Composantsprogrammables

Nous decrivons dans cette section les differents composants programmables existants,afin d’en montrer la diversite, et d’expliciter l’evolution de ces technologies. Les capacitesd’integration, de plus en plus poussees au fur et a mesure de l’apparition des technologies etde l’evolution des architectures programmables permettent aujourd’hui d’integrer jusqu’a500 000 portes logiques sur un meme FPGA de type SRAM, reconfigurable a volonte. Lesapplications des differents composants ont egalement evolue avec la capacite d’integration.Les circuits qui autrefois permettaient de remplacer quelques composants TTL, peuventaujourd’hui emuler les processeurs generalistes des annees 80.

Les circuits programmables sont principalement caracterisespar la capacite d’integration qu’ils proposent, la technologie utilisee, leur mode de pro-grammation (outil externe, configuration a la volee), le mode de codage des fonctions, etles possibilites de reconfiguration (une fois ou plusieurs, reconfiguration partielle ou non).Le diagramme ci dessous propose une classification sommaire des circuits en fonction deces differents parametres.

11

Un circuit logique programmable (PLD) regroupe, sur une meme puce, des compo-sants logiques configurables et des bascules. Des interconnexions programmables relientles ressources logiques entre elles. Les circuits n’ont pas de fonctionnalite predefinie, maissont specialisables suivant l’application visee. Des cellules de configuration memorisentles fonctions realisees par la logique et la maniere dont celles-ci sont interconnectees pourfournir les resultats demandes. Les cellules de configuration et les interconnexions pro-grammables sont formees a partir de points de programmation, element le plus fin descircuits programmables.

Les technologies et la programmabilite :

Suivant la technologie utilisee pour realiser les points de programmation, le circuit estprogrammable une fois (OTP : One Time Programming ), reprogrammable a l’aide d’unoutil externe (certaines eprom, eeprom, flash) ou reprogramme a chaque mise sous tension(memoires volatiles SRAM ). Les memoires volatiles sont par essence programmablessur site. Certains circuits a base de memoires non volatiles eeprom ou flash incluent lacircuiterie necessaire pour une reprogrammation sur site.

Le mode de codage des fonctions :

Les points de programmation peuvent etre regroupes de plusieurs manieres pour consti-tuer un element de calcul programmable : en commandant un multiplexeur, en realisantune memoire utilisee comme table de verite (Look Up Table : LUT) ou assemblees engrille 2D pour realiser des sommes de monomes de type et/ou. Le mode de codage desfonctions est etroitement associe a l’architecture des circuits.

Les architectures :

La logique configurable est partitionnee en macro-cellules. Une macro-cellule implanteune fonction logique combinatoirea une sortie (fonction booleenne), et peut eventuellement en stocker le resultat dans unebascule. Trois grandes classes de circuits logiques programmables cohabitent aujourd’hui.Les circuits SPLD ( simple PLD ) contiennent une ou deux dizaines de macro-cellules.Les premiers circuits configurables PAL ( Programmable Array logic ), apparus vers 1975,appartiennent a cette categorie. Les circuits CPLD sont conceptuellement des regroupe-ments de 2 a 32 SPLD interconnectes par une matrice d’aiguillage programmable de typecrossbar. Enfin, les circuits FPGA sont composes d’un grand nombre de petites macro-cellules (jusqu’a 5 entrees) disposees en pavage et reliees par un reseau d’interconnexionregulier,souvent complete de ressources de routage supplementaires specifiques.

Historiquement, l’architecture des circuits a evolue avec les capacites d’integration. Nousavons choisi de presenter les composants dans leur ordre d’apparition, qui correspondegalement a la complexite des fonctions qu’ils permettent d’implanter et aussi pour enarriver au FPGA ce qui nous interesse particulierement.

12

4.1 circuit ASIC

Dans un premier temps, nous allons rappeler quelques concepts autour des circuitsintegres pour applications specifiques ASIC. Les circuits ASIC constituent la troisiemegeneration de circuits integres qui a vu le jour au debut des annees 80. En comparaisondes circuits integres standards et figes proposes par les fabricants, l’ASIC presente unepersonnalisation de son fonctionnement, selon l’utilisation, accompagnee d’une reductiondu temps de developpement, d’une augmentation de la densite d’integration et de lavitesse de fonctionnement. En outre sa personnalisation lui confere un autre avantageindustriel, c’est evidemment la confidentialite. Ce concept d’abord developpe autour dusilicium s’est ensuite etendu a d’autres materiaux pour les applications micro-ondes outres rapides (GaAs par exemple).

Par definition, les circuits ASIC regroupent tous les circuits dont la fonction peut etrepersonnalisee d’une maniere ou d’une autre en vue d’une application specifique, par op-position aux circuits standards dont la fonction est definie et parfaitement decrite dans lecatalogue de composants. Les ASIC peuvent etre classes en plusieurs categories selon leurniveau d’integration, en fait un ASIC est defini par sa structure de base (reseau program-mable, cellule de base, matrice, etc.). Sous le terme ASIC deux familles sont regroupees,les semi personnalises et les personnalises.

4.1.1 Les circuits semi personnalises

Les semi personnalises sont des reseaux predefinis de transistors ou de fonctions lo-giques qui necessitent une personnalisation de l’utilisateur pour realiser la fonction desiree.Cette famille comprend :

> les reseaux logiques programmables> les reseaux prediffuses

13

Les reseaux logiques programmables

Ce composant ne necessite aucune etape technologique supplementaire pour etre per-sonnalise. Nous y trouvons les PAL/PLD, ce sont des circuits standards programmablespar l’utilisateur grace a differents outils de developpement. La programmation consiste aetablir des connexions en imposant un courant superieur aux courants de fonctionnementnormaux (claquage de fusibles ou de jonctions). Les circuits logiques programmables in-cluent un grand nombre de solutions, toutes basees sur des variantes de l’architecture desportes ET/OU.

Nous y trouvons :

> PAL matrice ET programmable, matrice OU figee

> PLA matrice ET ou matrice OU programmable

> EPLD (Erasable PLD) effacables par rayons ultraviolet,ils peuvent etre reprogrammer

> EEPLD (Electrically Erasable PLD) programmables eteffacables electriquement, ils peuvent etre reprogrammes sur site.Les limites de l’architecture du PLD resident dans le nombre de bascules,le nombre de signaux d’entrees/sorties, la rigidite du planlogique ET OU et des interconnexions.

Precisons que ces composants tres souples d’emploi sont limites a des fonctionsnumeriques et adaptes a des productions de petites series et ne presentent aucune garantiequant a la confidentialite.

Les reseaux prediffuses

Les reseaux prediffuses sont des circuits partiellement prefabriques. L’ensemble deselements (transistors, diodes, resistances, capacites, etc.) est deja implante sur le circuitsuivant une certaine topologie, mais les elements ne sont pas connectes entre eux (sauf auniveau diffusion). La realisation des connexions dans le but de definir la fonction souhaiteeest la tache du concepteur, pour cela il dispose de bibliotheques de macro-cellules etd’outils logiciels d’aide a la conception. A partir de cette liste d’interconnexions (netlist)le fondeur n’aura que quelques etapes technologiques a effectuer pour achever le circuit,c’est a dire le depot d’une ou plusieurs couches de metallisation.

Cette technique est interessante sur le plan de la conception et de la fabrication, parcontre elle presente l’inconvenient de ne pas permettre une optimisation en terme de den-site de composants puisque les elements de base sont preimplantes et pas forcement utiliseset que leur positionnement a priori n’est pas forcement optimal pour le but recherche.

14

4.1.2 Les circuits personnalises

Ce sont des circuits non prefabriques. Pour chaque application on optimise le circuitintegre, ce qui conduit a la creation de son propre composant.Cette famille comprend :

> les circuits a la demande

> les circuits precaracterises

Les circuits a la demande

Les solutions circuit a la demande (qu’on appelle full custom en anglais) presententl’avantage d’autoriser une meilleure optimisation du placement puisque celui-ci n’est paspredefini. On dispose d’une bibliotheque de modeles mathematiques de comportement etvia un ”compilateur de silicium” logiciel tres sophistique on peut concevoir toute l’ar-chitecture du circuit en faire une validation logicielle (simulation logique) puis dans uneavant derniere etape en deduire le dessin des divers masques de fabrication.

Toutes les operations, de la conception a la fabrication,sont effectuees de facon specifique adaptees aux exigences de l’utilisation. L’ensemble descriteres techniques est au choix du concepteur, que ce soit la taille du composant, lenombre de broches, le placement du moindre transistor. C’est l’ASIC le plus optimise caraucune contrainte ne lui est imposee. Le placement des blocs fonctionnels et le routagedes interconnexions, meme si ces operations sont assistees par ordinateur, sont effectueesavec beaucoup plus d’interventions manuelles pour atteindre l’optimisation au niveau dechaque transistor. Cependant, les phases de mise au point sont longues et onereuses, ilva de soi que la rentabilisation des investissements de developpement necessite un fortvolume de production.

Les circuits precaracterises

Pour la realisation de circuits precaracterises on dispose d’une bibliotheque de circuitselementaires que le fondeur sait fabriquer et dont il peut garantir les caracteristiques eton les associe pour realiser le circuit a la demande. Ici encore on utilisera en fabricationdes masques personnalises pour chacune des couches diffusees et des metallisations.

15

Le concept est tres semblable de celui des circuits a la demande. La seule differencereside dans la realisation du schema puisque l’on accede a une bibliotheque de cellulespredefinies generant de tres nombreuses fonctions elementaires ou elaborees. Cette derniereconstitue un veritable catalogue dans lequel le concepteur se sert pour constituer sonschema. Il existe trois types de cellules :

> les cellules standards (standard cells) correspondent a la logique classique

> les megacellules (megacells) peuvent etre des blocsdu type microprocesseur, peripherique

> les cellules compilees (compilable cells) dont les blocs RAM ou ROM.Il est necessaire de personnaliser completement la diffusion,et par consequent de creer tous les masques. Cependant unavantage evident en decoule : alors qu’il est impossible avecles prediffuses d’utiliser a 100% le reseau de cellules ou portes,ce qui se traduit par une perte de silicium, les precaracterisespermettent d’exploiter completement la surface du circuit.

4.1.3 Avantages et inconvenient de l’utilisation d’ASIC

D’une maniere generale l’utilisation d’un ASIC conduit a de nombreux avantages pro-venant essentiellement de la reduction de la taille des systemes. Il en ressort :

> Reduction du nombre de composants sur le circuit imprime.La consommation et l’encombrement s’en trouvent considerablement reduits

> Le concept ASIC par definition assure une optimisationmaximale du circuit a realiser. Nous disposons alors d’un circuit integrecorrespondant reellement a nos propres besoins

> La personnalisation du circuit donne une confidentialite auconcepteur et une protection industrielle

> Enfin, ce type de composant augmente la complexite du circuit,sa vitesse de fonctionnement et sa fiabilite

L’inconvenient est le frais de developpement eleve a cause du fondeur.

16

4.2 Circuits SPLD

Les premiers circuits programmables ont ete proposes en 1975 par les societes Intersilet Signetics sous le nom de PLA 9 et amelories pour etre diffuses sous forme de PAL parla societe AMD en 1978. L’architecture des circuits SPLD est caracterisee par un nombrefaible de macro-cellules et par le codage sous forme de tableau et/ou des fonctions logiques.Dans un circuit PLA, l’ensemble des macro-cellules est regroupe en un seul tableau et/ou.Chaque fonction booleenne est representee sous forme de sommes de monomes (cubes).Le premier etage du PLA realise un et logique sur les entrees. Le deuxieme etage calculele ou entre les monomes.

Dans un PLA, chaque intersection des matrices et et ou est un point de programmationqui valide ou non une connexion entre une ligne et une colonne. Par contre, dans les PAL, leou n’est pas programmable, afin de gagner en place et performance. Une amelioration estapportee en introduisant un tampon 3 etats sur la (les) broche(s) de sortie et en rebouclantvers les entrees. Cela permet d’utiliser une broche en entree/sortie (voir figure ci-dessous).Une autre amelioration consiste a ajouter une bascule en sortie pour memoriser un resultatet le reutiliser en entree.

17

Les macro-cellules actuelles sont constituees d’un PAL avec une dizaine d’entrees, uneseule sortie, memorisable, et associee a une broche dentree/sortie. Chaque macro-cellulepeut calculer entre 4 et 16 monomes. Les circuits SPLD contiennent quelques dizainesde macro-cellules completement interconnectees. Par exemple, la version AMD du circuitstandard 22V10 fournit 10 broches d’entree/sortie, 12 broches dentree, 10 macro-cellulesavec de 8 a 16 monomes par cellule.

Les premiers SPLD etaient implantes avec une technologie non reprogrammable(fusibles). Les circuits actuels sont generalement reprogrammables par outil externe(memoires non volatiles). Les fabricants incluent : Altera (gamme eprom classic), Lattice(eeprom GAL), Vantis (ancienne AMD, eeprom PAL), Atmel (flash ATF)...

Les SPLD sont rapides, surtout s’ils ne comportent pas de bascules. Ils se pretent a l’im-plantation d’algorithmes de codage/decodage, au remplacement de la logique discrete en sesubstituant a quelques composants TTL. Ils peuvent egalement remplacer des automatessimples. Cependant, leur nombre dentrees/sorties est faible et le nombre de fonctions lo-giques limite que peut realiser une macro-cellule restreint leur application a l’implantationde circuits peu complexes.

18

4.3 Circuits CPLD

Les circuits CPLD (aussi connu sous le vocable EPLD) reprennent l’architecturedes PAL pour l’implantation de la logique combinatoire dans les macro-cellules. Ils sedifferencient de leurs predecesseurs par une capacite beaucoup plus elevee. Un CPLD ty-pique est l’equivalent de 2 a 32 SPLD. Il contient de 18 a 256 macro-cellules, regroupeesen blocs logiques. Un bloc logique contient de 4 a 16 macro-cellules completement inter-connectees. Les blocs logiques sont relies par une matrice d’aiguillages programmables(voir fig. 1.4). La connectivite peut etre totale ou restreinte suivant les circuits.

Les CPLD font generalement appel a des memoires non volatiles de type eprom, eeprom,ou flash. Les plus recents sont programmables sur site. Les fabricants incluent : Xilinx(flash xc9500), Altera (eeprom MAX9000), Lattice (eeprom pLSI6000), Cypress (flashUltra39000), Atmel (eprom ATV), ... Grace a leur nombre d’entrees/sorties eleve et aleurs ressources logiques abondantes, les circuits CPLD sont adaptes a la mise en oeuvred’algorithmes de controle complexes sous forme de machines d’etats par exemple. De plus,leur structure hierarchique garantit un temps de propagation borne pour les signaux.

Architecture des circuits CPLD

Il existe des variations majeures entre les differentes architectures. Certains CPLDpeuvent s’affranchir en partie des limitations sur le nombre de monomes utilisables pourle calcul d’une fonction logique par un mecanisme de partage de monomes : les macro-cellules d’un meme bloc logique peuvent effectuer des calculs en prenant en compte lesmonomes implantes dans des macrocellules adjacentes. Par contre, le partage a pourinconvenient d’allonger les delais de propagation des signaux.

19

Une autre difference majeure concerne la structure de la matrice d’interconnexionprogrammable entre les blocs logiques. Les matrices a connectivite totale sont de plus enplus repandues, mais posent des problemes d’extensibilite. Les matrices partielles posentdes problemes lors de la modification d’un circuit : si l’on souhaite preserver le brochagelors de la redefinition du circuit afin de conserver la compatibilite du support imprime, ilfaut ajouter des contraintes sur la localisation de certaines fonctions pres des broches desortie. Cela n’est pas toujours possible si la connectivite entre les blocs logiques est troprestreinte. Les memes problemes de routage peuvent se poser si le nombre de broches desortie est trop reduit. Enfin, la connectivite partielle rend plus difficile la prediction desdelais de propagation du circuit.

4.4 Circuits FPGA

Les circuits FPGA, inventes en 1985 ( par la societe Xilinx ), sont les plus populairesactuellement. Cela est en partie du a leur grande capacite d’integration (jusqu’a 500000 portes logiques), inegalee dans le domaine des circuits programmables sur site. Lescircuits FPGA reprennent l’idee des macro-cellules en presentant des cellules logiquesprogrammables equivalent a des petits PAL complets ( qui implantent les 2n monomespossible pour un circuit a n entrees ). Mais ils integrent egalement l’idee de tableau decellules presents dans les circuits ASIC prediffuses (un FPGA utilisant la technologie anti-fusibles peut etre vu comme une mer de portes) ou precaracterisees (chaque cellule d’unFPGA utilisant la technologie SRAM peut etre vu comme une cellule standard de taillemoyenne).

Ces FPGA peuvent etre programmes avec des outils de bureau, et evitent donc le pro-cessus long et couteux de fonderie des circuits ASIC. Les circuits a anti-fusibles offrent demeilleures performances en delais que les circuits SRAM, a cause de la finesse de leur pointde programmation. Par contre, ils ont l’inconvenient de ne pas etre reprogrammables etde ne pas beneficier, comme c’est le cas des circuits SRAM, des progres realises dans le do-maine de l’integration des memoires volatiles. Nous nous interessons donc ici uniquementaux circuits utilisant la technologie SRAM.

Nous allons nous interesser a l’architecture des FPGA a base de LUT que nous vouspresenterons plus en detail.

20

4.4.1 Architecture

Les FPGA SRAM sont composes de cellules logiques de type PAL, disposeesgeneralement en matrice 2D, et interconnectees de maniere plus ou moins reguliere pardes ressources de routage elles-meme programmables. Des blocs d’entree/sortie, disposesa la peripherie du circuit, fournissent l’interface avec l’exterieur ( figure ci-dessous ).

Ce type de circuits est particulierement adapte aux fonctions de calcul, grace a sonarchitecture bidimensionnelle, et au nombre eleve de registres permettant l’implantationde circuits tres pipelines. La structure est par ailleurs facile a etendre par l’assemblage decircuits en matrice, ce qui joint les matrices internes des circuits pour donner une uniquematrice de taille arbitrairement grande.

Les cellules : La petite taille des cellules (jusqu’a 2 x 5 entrees, 1 ou 2 sorties) per-met d’implanter les fonctions logiques a l’aide de tables verite (LUT) stockees dans desSRAM. Le stockage sous forme LUT des fonctions boolennes, contrairement aux sommesd’un nombre fixe de monomes utilisees dans les PLA, permet de realiser n’importe quellefonction booleenne a partir de ses entrees.

Le routage : La structure de routage est le plus souvent de type Manhattan dansles circuits a base de SRAM. Des connexions locales rapides entre cellules adjacentessont disponibles; des connexions plus globales, de longueur variable, avec des matricesd’interconnexion programmables permettant la diffusion de signaux au travers de canauxde routage intercales entre les lignes et colonnes de cellules logiques.

Des matrices d’interconnexion (switching box) completement ou partiellement program-mables sont situees a l’intersection de chaque ligne et colonne. Leur programmation permetde definir les connexions entre les differentes ressources de routage adjacentes a l’intersec-tion.

21

4.4.2 grain des circuits

Les architectures a grain fin sont caracterisees par des cellules de tres petite taille(LUT a 2 entrees ou multiplexeur 4:1, une bascule) alors que les architectures a gros grainont une cellule de base composee d’une ou deux LUT a 4-5 entrees et de une ou deuxbascules.

La capacite d’un composant FPGA a implanter des fonctionnalites complexes depend del’equilibre entre les ressources logiques et les ressources de routage. La logique a implanterdoit etre repartie entre les cellules. Les signaux utilises doivent etre propages vers lescellules concernees par les ressources de routage. Une architecture a grain fin maximise letaux d’occupation des cellules mais en augmente le nombre. Cela necessite des facilites deroutage ameliorees. A l’oppose, une architecture a gros grain autorise une integration pluspoussee de la logique dans les blocs. Les capacites des ressources logiques ne sont pas enmoyenne utilisees pleinement, mais leur nombre est reduit, ce qui diminue les ressourcesde routage necessaires. Les architectures basees sur des memoires SRAM, tant pour lalogique que pour la programmation des ressources de routage, autorisent des cellules agros grain (5 vers 1); mais elles imposent une architecture de routage repartie de faibledensite, plutot de type Manhattan, a cause de la difficulte de realisation de matricesd’interconnection SRAM de grande taille.

Les figures suivantes montrent 2 architectures de blocs logiques proposees par la societeXilinx. La premiere, a grain fin, est celle des circuits xc6200. Elle permet le calcul, a l’aidede multiplexeurs, de n’importe quelle fonction boolenne a deux entrees, ou de certainesfonctions a trois entrees. La seconde est celle des circuits xc4000, pouvant calculer deuxfonctions logiques de 4 variables, et certaines fonctions comprenant jusqu’a 9 variables.

22

Architecture cellules signauxxc6200 394 435xc4000 48 137

La table ci dessus montre le nombre de cellules logiques necessaires et le nombre designaux a router pour un circuit combinatoire standard pour les deux architectures.

23

4.4.3 Capacite des composants SRAM

Les capacites des circuits SRAM sont mesurees a la fois en nombre de portes logiques,et par le nombre de bits de configuration. Les equivalences en nombre de portes logiquesavancees par les fournisseurs donne une idee de la capacite d’integration logique, mais sansprendre en compte la flexibilite de l’architecture de routage. La figure ci-dessous montrepar exemple que pour des capacites annoncees du meme ordre de grandeur, la taille de lamemoire de configuration peut varier enormement, ce qui reflete des differences notablesentre les architectures en matiere de ressources de routage specifiques. Pour les circuitsSRAM, il peut etre interessant de mesurer la capacite des circuits en nombre de cellules.Une mesure en terme de cellules logiques peut etre consideree pour la prise en compte a lafois des ressources logiques et des ressources de stockage des circuits. Une cellule logiquecomprend une table de verite a 4 entrees et un registre d’un bit, chacun comptant pourune demi cellule.

Le degre de routabilite du circuit, i.e., le nombre de cellules logiques occupees parrapport au nombre de cellules disponibles dans un circuit routable, peut varier de 50%a 90% ou 100% suivant les capacites de routage de l’architecture. Ce facteur est refletepar la complexite globale de l’architecture par le biais de la taille de sa memoire deconfiguration. Cette taille englobe egalement les specificites de certains circuits (circuitarithmetique supplementaire dans les cellules, possibilites de stockage multiples, cascadesde resultats logiques, ...).

La figure ci-dessous presente les capacites des plus gros circuits programmables actuelsou plannifies pour l’annee 1998. Par souci de lisibilite, le nom des composants n’est indiqueque pour les plus gros dentre eux. Ces circuits proviennent des societes Xilinx (xc4xxx),Altera (gamme Flex10kxx) et Orca (gamme 3cTxx). Les plus gros circuits prevus at-teignent 500 000 portes ou 20 000 cellules logiques, pour une memoire de configuration de5 Mbits. Les capacites d’integration en nombre de portes logiques atteintes correspondent

24

a celles des systemes a microprocesseur des annees 80.

4.4.4 Comparaison avec les autres technologies

Cette section a pour but de fournir des ordres de grandeur concernant les perfor-mances comparees des differentes technologies. Par essence les performances precises d’uncircuit dependent de la nature des applications considerees. De plus, l’evolution rapidedes technologies et des composants rendent rapidement caducs les chiffres presentes. Uncircuit programmable est souvent le resultat d’un compromis entre vitesse et capacited’integration en terme de portes logiques. De maniere generale, plus la taille d’un circuitest importante, moins la vitesse de ce circuit sera elevee. La figure suivante illustre les

25

domaines relatifs d’application des composants SPLD, CPLD et FPGA.

Il existe un ordre de magnitude entre les capacites d’integration en terme de porteslogiques des differentes technologies. Ceci est en particulier du aux choix architecturaux :par exemple les matrices d’interconnexion completes des CPLD ne peuvent etre relieesqu’a un nombre de macro-cellules faible, alors que l’architecture de type Manhattan desFPGA a base de LUT, avec ses ressources de routage locales sont extensibles.

De maniere generale, les circuits programmables les plus complexes sont aussi ceuxayant la vitesse de fonctionnement la plus lente. Les domaines d’utilisation des differentscircuits se recoupent partiellement. Par exemple, les CPLD les plus complexes peuventatteindre une capacite de 50.000 portes, capacite correspondant a celle des FPGA de taillemoyenne. Les FPGA les plus gros atteignent la taille d’un ASIC courant, entre 250.000et 500.000 portes logiques. Les ASIC les plus gros ont une capacite comprises entre 3 et 5millions de portes. La vitesse de fonctionnement moyenne est autour de 50 MHz pour lesapplications a base de FPGA (mais peut depasser les 100 MHz), alors qu’elle est de 200Mhz pour les SPLD, et qu’elle peut atteindre les 400 MHz pour les implantations ASICet 1 GHz pour les circuits a facon ( full custom ).

26

4.4.5 Methodologie de synthese

Les capacites grandissantes des circuits FPGA leur ouvre de nouveaux domaines d’ap-plications. Ils ne sont plus limites, comme les circuits SPLD au remplacement de la logiquediscrete des systemes. Ils peuvent dans certains cas se substituer a de petits composantsASIC. Meme si il existe toujours un ordre de magnitude entre les performances des cir-cuits ASIC et des circuits programmables, les moindres couts et temps de developpementde ces derniers peuvent leur gagner la faveur des concepteurs dans certains cas.

Techniquement, les circuits FPGA a base de LUT peuvent etre programmes tres ra-pidement, a l’aide d’outils de bureau simples. D’autre part, ils peuvent implanter desapplications de taille tres importantes. Ces deux facteurs ont genere de nombreuses re-cherches et developpements pour mettre au point des outils de conception et de syntheseautomatisee pour ce type de circuits, afin de repondre aux besoins suivants des concep-teurs :

> permettre la generation rapide de configuration pour les composants,en automatisant certaines phases de la synthese d’un circuit

> fournir des langages de specification de haut niveau, permettant de decriresimplement des applications complexes, et fournir les outils detraduction associes pour la derivation d’une configuration

> fournir des outils de validation des circuits produits

Les techniques de conception mises au point reprennent les idees developpees pour larealisation de projets logiciels complexes : genericite du code, portabilite, decoupage enmodules hierarchises, appel a des bibliotheques predefinies, reutilisabilite, ... . Le processusde generation de configuration s’apparente a une compilation. Elle se fait a partir d’unlangage de specification de haut niveau, masquant en partie les specificites de l’architecturecible. Des descriptions de plus bas niveau sont generees pour definir plus finement lecircuit, en prenant en compte les specificites de l’architecture programmable cible, demaniere analogue au processus de compilation de logiciel vers un processeur generaliste.

Comme la complexite de la synthese vers les FPGA s’apparente a celle de petitsASIC, et que le processus reprend l’idee de compilation utilisee dans le domaine logiciel,les methodologies de conception sont descendantes et analogues a celles utilisees pourles circuits ASIC. Nous presentons donc tout d’abord de maniere generale et rapide lamethodologie employee pour la generation automatisee de circuits VLSI, avant dexpliciterles phases specifiques a la conception de circuits FPGA a base de LUT.

27

Conception descendante

Le processus de synthese VLSI peut etre vu comme une serie de transformations ap-pliquees a des descriptions comportementales, structurelles puis physiques d’un circuit. Lesdescriptions comportementales decrivent les sorties du circuit en fonction de ses entrees.Par exemple, les descriptions procedurales et booleennes sont des representations com-portementales. Les descriptions structurelles, elles, apprehendent le circuit en termes decomposants et d’interconnexions. Enfin les representations physiques sont caracteriseespar des informations utilisables pour la fabrica tion d’un circuit integre. Ces informationssont principalement de nature geometrique (dessin de masques).

Les differents types de representation sont caracterises par leur nature (comportemen-tale, structurelle ou physique) et par leur niveau d’abstraction. Afin de prendre en compteles evolutions technologiques, qui autorisent la realisation de systemes de plus en plus com-plexes, les outils de synthese automatique ou semiautomatique de circuit integres deriventun systeme materiel a par tir de descriptions d’un niveau d’abstraction de plus en pluseleve. Les outils de CAO tendent a offrir des procedures de synthese de plus en plus au-tomatisees dans le but maitriser la complexite des projets et de reduire les temps et lescouts de production des circuits.

28

29

Le processus de synthese utilise une methodologie de conception descendante, diviseeen phases. La figure ci-dessus illustre de maniere generale les phases successives, regrou-pant chacune une etape de synthese et une etape de verification et analyse du resultat. Lepoint d’entree du processus de sytnhese est une specification comportementale du circuit,generalement concretisee par une description a l’aide d’un langage de description materielde haut niveau (e.g vhdl) de l’application, de ses performances, de son interface, ... . Apartir de cette specification, les phases suivantes sont realisees :

> La generation fonctionnelle, durant laquelle une description fonctionnelleest synthetisee. Le resultat est une description comportementale du circuitcomposee de directives de transfert de registres (RTL) etd’equations booleennes pour la partie combinatoire du circuit.Les outils de simulation comportementale permettent d’analyser le resultatde la synthese et de le comparer a la specification initiale.

> Durant la generation logique, une structure logique, implantantla description fonctionnelle, est produite. Le resultat est typiquement unerepresentation structurelle consistant en une liste de portes logiquesinterconnectees (liste technologique). La verification symbolique de lalogique et/ou sa simulation a l’aide de vecteurs de tests permet de validerle circuit obtenu par comparaison avec les resultatsde la simulation comportementale.

> Les deux dernieres phases de generation de circuit et de masques sontdu domaine de l’electronique. Les portes logiques sont traduites en transistors,capacites puis places et interconnectes sur le substrat. Les delais du circuitpeuvent alors etre testes et analyses, pour verifier si ils sont acceptablespar rapport aux specifications du concepteur.

30

4.4.6 Synthese du FPGA

Le cas de la synthese FPGA est un peu different de celui des circuits ASIC. Celaest du a la specificite de ce type de composants, fortement contraint par leur archi-tecture predefinie. On retrouve, comme dans le cas general de la synthese ASIC (cir-cuits prediffuses, precarac terises), les phases de haut niveau pour la specification et larepresentation comportementale du circuit (qui sont independantes de la technologie),mais les etapes basses de generation de circuit et de dessin de masques sont remplaceespar des etapes de :

> Conversion technologique : la generation d’une liste technologique corresponden fait soit a l’utilisation de portes predefinies extraites d’une bibliotheque,soit au decoupage du circuit en fonctions logiques pouvantetre implantees dans les cellules de base de l’architecture cible

> Le placement de la liste technologique, c’est a dire, le choix d’unemplacement pour chaque composant sur la grillede cellules de base constituant le FPGA.

> Le routage des signaux entre les composants places, reprenantles informations de connectivite de la liste technologique.

Le processus de synthese automatisee peut donc etre vu comme la succession de 3etapes majeures : (a) la synthese de haut niveau; (b) la synthese logique et (c) le placementroutage du circuit. Ce processus est illustre sur la figure ci-dessous.

31

Chapitre 5

FPGA a base de LUT

La technologie FPGA est devenue une alternative interessante au circuits ASIC . Gracea leur reconfigurabilite qui reduit a la fois les temps et les couts de developpement, lescircuits programmables FPGA sont devenus une alternative interessante au circuits ASICpour le prototypage rapide de circuits, les applications en traitement du signal et pourl’emulation cablee.

Un FPGA est une puce VLSI regroupant des elements logiques, des entrees/sorties etdes ressources de routage, tous reprogrammables. Le concepteur peut realiser son circuiten programmant le FPGA directement, evitant de ce fait le processus long et couteuxdes circuits ASIC. La plus repandue des technologies FPGA est celle des FPGA a basede RAM, ou la programmabilite est obtenue en implantant les composants du FPGA al’aide de RAM statique. L’approche la plus courante pour l’implantation d’un composantlogique de base est faite via une memoire de 2k bits, qui peut representer n’importe quellefonction booleenne a K entrees et une sortie.

Un FPGA a base de LUT est un tableau 2D de tables de verite programmables (Look-Up Table, LUT) qui implantent des fonctions logiques combinatoires et sequentielles. Cescellules sont interconnectees par un reseau de ressources de routage egalement configu-rable.

32

Une LUT a k entrees peut calculer n’importe quelle fonction logique d’au plus kvariables. La programmation du circuit correspond a l’ecriture des tables de verite (lookup) des fonctions et des bits de controle des interconnexions dans les differentes cellulesSRAM. De tels FPGA sont disponibles chez tous les grands fabricants de circuits logiquesprogrammables (Altera, ATT, Xilinx).

Specificite de la synthese pour FPGA :

La synthese de circuits FPGA se base sur les techniques plus anciennes de synthesede circuits VLSI. La modelisation traditionnelle sous forme de librairie utilisee par lesoutils de synthese VLSI permet de decrire de facon precise l’architecture cible et sesfonctionnalites.

Cependant, la synthese d’un circuit FPGA sans structure initiale particuliere peut etretres delicate a realiser : la prise en compte de differents criteres d’optimisation commenotamment la vitesse finale du circuit, dependante des phases posterieures que sont leplacement et le routage, complique la tache de synthese. Il est tres difficile de modeliserau niveau logique les temps du circuit. Cela necessite souvent de revenir, apres placement-routage, sur la solution obtenue au niveau de la synthese afin de l’ameliorer en tenantcompte des delais reels obtenus pour le circuit place-route.

33

Les techniques de synthese conventionnelles, basee sur la notion de conversion vers unelibrairie de portes predefinie sont difficilement applicables directement dans le cadre dela synthese pour FPGA. Chaque cellule (LUT) a K-entrees peut implanter 22K

fonctionslogiques differentes, representant un tres grand nombre de reseaux logiques equivalents, sion les exprime a l’aide de portes de base. Ce probleme a motive de nombreuses recherchesdans le cadre de l’optimisation combinatoire, afin de developper des techniques specifiquesa la structure des FPGA.

Classification des methodes de synthese :

Le processus de synthese pour les FPGA est similaire a celui des technologies conven-tionnelles telles que les cellules standard ou les mers de portes. Il consiste en une phasede synthese de haut niveau (synthese d’architecture), une phase de synthese au niveaulogique (synthese logique), et une phase de synthese physique (generation de masques).La phase de synthese logique des FPGA est composee d’une synthese logique sequentielle,qui optimise le choix et l’utilisation des elements de stockage, et d’une synthese logiquecombinatoire, qui optimise les reseaux de portes logiques.

De nombreux algorithmes et systemes de synthese logique combinatoire pour FPGAexistent. Meme si chacun d’entre eux utilise des techniques et concepts specifiques, ils fonttous appel a des methodes de base communes. Plusieurs classifications de ces techniquessont possibles. Deux etapes majeures sont reconnues :

> L’optimisation logique.Elle se fonde sur les proprietes de la logique booleenne pour optimiserla representation fonctionnelle du circuit. Les methodes d’optimisation logiquesont generalement independantes de la technologie cible. Cependant, certainesd’entre elles sont plus particulierement utiles dans le cadre dela synthese logique FPGA. Nous avons restreint notre etude a ces techniques.

> La conversion technologique vers une architecture cible.L’architecture de la cible est modelisee au niveau logique par des contraintesstructurelles simples que doit respecter la description logique du circuit.Dans le cas general, cela correspond a l’affectation pour chaquefonction logique et chaque element memoire, d’un composant extrait d’unelibrairie representant l’architecture cible. Dans le cas des FPGA,les contraintes portent sur le nombre d’entrees de chaque fonction logique.

Au lieu de classer les operations de synthese suivant leur nature fonctionnelle ou struc-turelle, il est possible de considerer plutot les objectifs d’optimisation a atteindre (minimi-sation de la surface, des delais, de la routabilite, de la puissance dissipee, de la testabilite,...). Cependant, en adaptant les fonctions de cout a l’objectif, des techniques de basecommunes sont employees pour ces differents criteres d’optimisation.

34

5.1 Presentation du probleme et definitions

Les parties combinatoires d’un circuit, constitue d’un reseau de portes logiques plus oumoins complexes, comportent deux types d’informations, fonctionnelles et structurelles.

Informations structurelles:

Un circuit combinatoire peut etre vu comme un graphe acyclique oriente G = (V; E),appele aussi reseau booleen (figure (b)), ou chaque sommet v appartenant a V representeune porte logique, et ou un arc e appartenant a E relie le sommet v de V au sommet w deV pour indiquer que la sortie de la porte v est utilisee en entree de la porte w. v est uneentree de w (v appartient a fanin(w)) et w est une sortie de v (w appartient a fanout(v)).Un sommet i tel que fanin(i) = Ø; est une entree primaire (ep) du circuit. Un sommet jtel que fanout(j) = Ø; est une sortie primaire du circuit (sp2).

Les autres sommets sont des sommets internes. Le niveau d’un sommet est la longueurd’un plus long chemin entre ce sommet et l’ensemble des entrees primaires. La profondeurou hauteur du reseau est le maximum des niveaux de ses sorties primaires.

Un sommet v est K-faisable si |fanin(v)| <= K. Si l’on note fanin(H) l’ensemble desentrees distinctes d’un sous-reseau H’ G, H est K-faisable si |fanin(H)| <= K. Si chaquesommet v de G est K-faisable, G est dit K-borne.Si un sommet possede une seule sortie (|fanin(v)| <= 1) , il est dit libre. Si tous lessommets sont libres, le reseau est un arbre (une seule sp) ou une foret (plusieurs sp). Siseules les entrees primaire ont plus d’une sortie, le reseau est un reseau libre.

35

Informations fonctionnelles:

Chaque sommet v du reseau booleen representant le circuit combinatoire est associe aune fonction logique fv ayant comme entrees les signaux resultants des sommets appar-tenant a fanin(v). L’ensemble des variables distinctes (correspondant a ces signaux) estle support de la fonction. fv peut etre une fonction correspondant aux portes logiques debase AND, OR , NOT ou etre une fonction booleenne complexe, mais toujours a une seulesortie. Differentes possiblilites sont presentees ici pour la representation de ces fonctionsbooleennes (figures (a-e)).

Une fonction booleenne a une sortie peut etre caracterisee en partitionnant ses vec-teurs d’entree en trois ensembles, le onset (ONj), le off-set (OFFj) et le dc-set (DCj),correspondant respectivement aux vecteurs pour lesquels la fonction rend 1, 0 et indefinie.

Un literal est une variable logique ou son complement. Un cube (monome) est un pro-duit de literaux non nul (i.e., ou n’apparaıt pas a la fois une variable et son complement).Pour une fonction logique a n entrees, un minterme est un cube a n termes. Un ensemblede vecteurs (on-set, off-set ou dc-set) peut etre represente par la collection complete de sesmintermes de maniere unique (forme dnf ou somme normale disjonctive) (figure (b)). Unecouverture par les cubes (forme sop ou somme de produits) (figure (c)) est une collectionde cubes recouvrant le on-set d’une fonction booleenne, sans intersection avec le dc-set.

36

Les diagrammes de decision sont une autre forme de representation fonctionnelle dela logique. Les diagrammes de d’ecision binaire (figure(d)) sont les premiers a avoir eteutilises. Deux sommets terminaux ne possedent pas d’arcs sortants. Ceux-ci sont respec-tivement les sommets associes aux sorties 0 et 1. Chaque sommet non terminal est associea une variable du support de la fonction booleenne et possede deux arcs sortants, l’unmarque 0, l’autre 1, connectes respectivement aux sommets high(v) et low(v). Un bddrepresente une fonction completement specifiee. La fonction associee a la racine corresponda la fonction booleenne a representer.

A partir de ces bdd simples, on peut construire les bdd ordonnes (obdd), ou l’ordre desvariables est le meme sur n’importe quel chemin menant de la racine aux sommets termi-naux. L’ordre des variables du support est determinant pour le bdd, un ordre different me-nant a un bdd different. Les bdd ordonnes reduits (robdd) compactent la representation,en rendant non redondant l’ensemble des sommets internes du gao. La representation obdda l’avantage d’etre canonique pour un ordre donne du support de la fonction logique, etplus compacte que la representation par cubes dans certains cas (suivant l’ordre choisi).

37

5.2 Synthese combinatoire pour FPGA a base de

LUT

Le processus de synthese combinatoire pour FPGA a base de LUT transforme un reseaumultiniveaux de portes logiques en un reseau de LUT, ou chaque lut n’a pas plus deKentrees . Deux etapes principales realisent cette transformation, l’optimisation logiqueet la conversion technologique. La premiere transforme le reseau de portes logiques en unreseau de portes adaptees a une implantation sous la forme de lut. La seconde couvrel’ensemble des sommets du reseau par un reseau de LUT. Les deux etapes se distinguentpar le type d’informations qu’elles utilisent : l’optimisation logique repose sur les pro-prietes fonctionnelles du reseau, tandis que la conversion technologique s’appuie sur sescaracteristiques structurelles. Le reseau genere lors de l’etape d’optimisation logique estnormalement K-borne. Dans certains systemes de synthese, la conversion technologiquese reduit a une traduction directe des sommets en LUT.

Optimisation logique :

L’optimisation logique est la premiere phase de la synthese logique d’un reseau deportes a prendre en compte, au moins partiellement, la specificite de l’architecture cible.Son but est de transformer le reseau logique initial en un reseau implantable sous formede K-LUT. Le minimum requis est que chaque sommet du reseau resultant possede uncone K-faisable. Dans ce cas, chaque cone possedant au plus Kentrees distinctes, il estimplantable par une LUT. Le reseau est alors K-convertible, i.e., convertible en reseau deLUT. La fonction logique calculee par la lut sera le resultat de la reinjection successivede tous les predecesseurs du sommet v appartenant a Cv dans v.

Comme, pour un reseau donne, il existe de nombreux reseaux convertibles fonctionnel-lement equivalents, le but de l’optimisation logique est de trouver un reseau convertibleinteressant par rapport a un ou plusieurs objectifs d’optimisation. La qualite de la solu-tion n’etant pas calculable a priori , les operations d’optimisation se contentent d’objectifsapproximatifs, comme le nombre de LUT, la profondeur, la largeur du reseau, ou la bonnerepartition des interconnexions .

38

Conversion technologique :

L’optimisation logique, telle qu’elle est definie ci-dessus, transforme un reseau quel-quonque en reseau convertible, i.e., K-borne. Le but de la conversion technologique estde couvrir ce reseau par un reseau de LUT, i.e., assigner chaque sommet du reseau a uneLUT. Plus precisement, pour que la couverture soit valide, les deux conditions suivantesdoivent etre respectees :

> chaque sp ( K varie entre 2 et 5 suivant lesconstructeurs et les architectures ) doit etre la sortie d’une LUT

> si un cone Cv est implante par une LUT LUTv,chaque sommet du fanin de LUTv qui n’est pas une entree primairedoit etre la sortie d’une autre LUT de la couverture. Si aucun sommetn’est duplique dans plusieurs LUT, la couverture est dite irredondante.

Meme si la conversion technologique peut etre vue comme une suite de reinjections desommets dans leurs successeurs, l’aspect fonctionnel de la reinjection n’est pas prise encompte : la logique interne d’ecoulant de l’operation pour les sommets n’est pas consideree.Seule la structure resultante importe, sachant que l’on cherche a ameliorer des criterestels que le nombre de connexions, le nombre de sommets ou la longueur des chemins dansle reseau.

39

Chapitre 6

Annexe

6.1 Abreviation

Abrv Definition

PLD Programmable Logic Device

CLB Configurable Logic Block

EPLD Erasable PLD

CPLD Complex PLD

SPLD Simple PLD

FPGA Field Programmable Gate Array

OTP One Time Programming

IOB Input Output Block

PAL Programmable Array Logic

PLA Programmable Logic Array

PAM Programmable Active Memory

ASIC Application Specific Integer Circuit

VLSI Very Large Scale Integration

RTL Register Transfert Level

TTL Transistor Transistor Logic

LUT Look Up Table

40

6.2 Bibliographie

Nous avons surtout cherhes sur internet et en particulier sur le site Xilinx( http://www.xilinx.com ) et nous avons utilise 2 theses :

> l’une de Laurent Moll : Applications des Memoires Actives Programmableshttp://gambetta.org/moll/laurent/publi/these.pdf

> l’autre de Laurent Lemarchand : Parallelisation par partitionnement pour le syntheselogique combinatoire sur FPGA a base de LUTftp://ftp.irisa.fr/techreports/theses/1999/lemarchand.ps.gz

41

Chapitre 7

Conclusion

Dans cet expose, nous avons presente les circuits de type FPGA dont nous precisonsici les principaux avantages:

> Le premier argument est la souplesse de programmation qui permet l’emploi conjointd’outils de schematique aussi bien que l’exploitation d’un langage de haut niveau telVHDL. Ceci permet de multiplier les essais, d’optimiser de diverses manieres l’archi-tecture developpee, de verifier a divers niveaux de simulation la fonctionnalite de cettearchitecture.

> Le second argument est evidemment la nouvelle possibilite de reconfiguration dyna-mique partielle ou totale d’un circuit ce qui permet d’une part, une meilleure exploitationdu composant, une reduction de surface de silicium employe et donc du cout, et d’autrepart, une evolutivite assurant la possibilite de couvrir a terme des besoins nouveaux sansnecessairement repenser l’architecture dans sa totalite. L’un des points forts de la re-configuration dynamique est effectivement de permettre de reconfigurer en temps reel enquelques microsecondes tout ou une partie du circuit, c’est a dire de permettre de mo-difier la fonctionnalite d’un circuit en temps quasi reel. Ainsi le meme CLB pourra a uninstant donne etre integre dans un processus de filtrage numerique d’un signal et l’instantd’apres etre utilise pour gerer une alarme. On dispose donc quasiment de la souplessed’un systeme informatique qui peut exploite successivement des programmes differents,mais avec la difference fondamentale qu’ici il ne s’agit pas de logiciel mais de configurationmaterielle, ce qui est infiniment plus puissant.

> Notons que ces circuits n’ont pas vocation a concurrencer les super calculateurs,mais plutot a offrir une alternative en fonction de criteres comme l’encombrement, lesperformances et le prix, et sont de ce fait bien adaptes a des applications de qualite dansle domaine des systemes ambulatoires ou nomades.

> Enfin il semble que de plus en plus frequemment les concepteurs de circuits ASICpreferent passer par l’etape intermediaire d’un FPGA ce qui est moins risqueeconomiquement, puis une fois que le modele FPGA est au point, il est alors relativementaise de le retranscrire dans une architecture de type prediffuse ou precaracterise.

42