Architecture des processeurs extensibles

Télécharger le fichier pdf d’un mémoire de fin d’études

M´ethodologie MESCAL

La m´ethodologie MESCAL [94, 109] propose de concevoir un ASIP autour de cinq el´ements essentiels.
1. El´ement 1 : « Judiciously Using Benchmarking », utiliser les applications de mani`ere judicieuse. Le d´eveloppement d’un ASIP est par d´efinition dirig´e par les applications cibles. La conception est souvent guid´ee par un ensemble d’applications de r´ef´erence, qui doivent ˆetre repr´esentatives du domaine d’applications vis´e.
2. El´ement 2 : « Inclusively Identify the Architectural Space », identifier l’es-pace architectural complet. L’espace de conception d’un ASIP consiste en un large ´eventail de possibilit´es selon plusieurs dimensions. Si l’espace entier n’a pas besoin d’ˆetre consid´er´ pour un domaine d’applications pr´ecis, il est important que la base de conception initiale puisse inclure une large gamme de d´eclinaisons possibles. En effet, ´ecarter d`es le d´ebut un espace de conception peut ´eliminer certaines architec-tures int´eressantes.
3. El´ement 3 : « Efficiently Describe and Evaluate the ASIPs », d´ecrire et ´evaluer efficacement l’ASIP. Pour consid´erer une gamme de d´eclinaisons de l’archi-tecture la plus large possible, il est important de pouvoir d´ecrire et ´evaluer l’ASIP pour les applications consid´er´ees. Les outils logiciels correspondants a` l’ASIP doivent donc ˆetre disponibles.
4. El´ement 4 : « Comprehensively Explore the Design Space », explorer l’espace de conception de mani`ere approfondie. L’exploration de l’espace de conception est un processus it´eratif avec asservissement o`u chaque point de conception est evalu´ selon une m´etrique. L’exploration est r´ealis´ee grˆace a` un environnement qui permet de compiler l’application pour l’architecture et de simuler l’ex´ecution pour obtenir des r´esultats quantitatifs et appr´ecier les performances. L’aspect cl´e est de pouvoir recibler rapidement les outils pour chaque point de conception.
5. El´ement 5 : « Successfully Deploy the ASIP », d´eployer l’ASIP avec succ`es. Un ASIP peut ˆetre ultra performant en proposant une ad´equation excellente entre l’application et l’architecture et a` la fois compl`etement sous exploit´ si il est mal programm´e. Programmer un ASIP directement en assembleur est impensable au-jourd’hui ´etant donn´ee la complexit´ des applications et les temps de d´eveloppement tr`es limit´es. Il est donc important de disposer d’un compilateur suffisamment puis-sant pour exploiter au maximum les capacit´es d’une architecture.
De la mˆeme fa¸con, un compilateur puissant est sous exploit´ si l’architecture est peu adapt´ee a` l’application, et un compilateur et une architecture ne peuvent que faible-ment am´eliorer les performances d’une application mal d´ecrite. La conception d’un ASIP conduit id´ealement a` une ad´equation parfaite entre l’algorithme, l’architecture, et le com-pilateur.
La m´ethode de conception compl`ete propose de g´en´erer un processeur et sa suite d’ou-tils associ´es `a partir d’un mˆeme mod`ele du processeur pour garantir l’ad´equation entre l’architecture et le compilateur. L’application est g´en´eralement d´ecrite dans un langage de haut niveau. Nous avons vu `a travers l’exemple du langage LISA que le processus n’est pas enti`erement automatis´e et qu’il faut toujours mettre en œuvre manuellement certaines parties critiques du processeur pour aboutir `a un processeur optimis´e. Chaque nouveau processeur doit ˆetre v´erifi´ et optimis´e, ce qui entraˆıne des coˆuts d’ing´enierie non r´ecurrents.
Pour r´eduire ces coˆuts, une autre approche de conception d’ASIP vise `a consid´erer un processeur existant et `a concevoir seulement la partie d´edi´ee, c’est la conception partielle qui est maintenant d´ecrite.

Conception partielle d’ASIP

La conception partielle consiste a` partir d’un processeur existant, v´erifi´ et optimis´e, qui poss`ede sa suite d’outils associ´es (compilateur, simulateur, etc), a` le configurer, et a` ´etendre son jeu d’instructions pour le sp´ecialiser en regard des exigences d’une application ou d’un domaine d’applications. Ce type de processeur est configurable a` travers des el´ements comme la file de registres, la profondeur du pipeline, la pr´esence ou non de multiplieurs, etc. Par ailleurs, ce type de processeur dispose de m´ecanismes pour ajouter facilement une nouvelle instruction au jeu d’instructions, et pour qu’elle soit prise en compte par le compilateur. En g´en´eral, cette technique demande au concepteur de fournir une description architecturale de la nouvelle instruction et de modifier manuellement le code applicatif qui fait appel a` la nouvelle instruction. Dans un premier temps, nous donnons un exemple de processeur configurable et extensible, puis nous passons en revue les autres architectures existantes. Ensuite, nous d´ecrivons les m´ethodologies et techniques de compilation qui permettent d’automatiser le processus d’extension de jeu d’instructions.

Exemple

Pour illustrer ce qu’est un processeur configurable et extensible, nous proposons d’´etu-dier le processeur NIOSII. C’est le processeur que nous avons choisi d’utiliser pour valider notre m´ethodologie et nos outils d´evelopp´es pendant cette th`ese. Pr´esenter ce processeur en d´etail permet de bien comprendre les aspects d´ecrits tout au long du document.
Le processeur NIOSII est un processeur RISC (Reduced Instruction Set Computer ) 32 bits d´eclin´ en trois versions : une premi`ere version dite « ´economique », une deuxi`eme dite « standard », et une troisi`eme dite « rapide » (Nios2Fast ). La grande diff´erence entre les trois versions se situe au niveau du nombre d’´etages de pipeline. La d´eclinaison ´economique du NIOSII est un processeur qui poss`ede un seul ´etage de pipeline, et chaque instruction n´ecessite 6 cycles pour ˆetre ex´ecut´ee. Un NIOSII standard a cinq ´etages de pi-peline. Le Nios2Fast en a six. Un processeur NIOSII a une file de registres de 32 registres de 32 bits. Une liste non exhaustive des aspects configurables du processeur NIOSII est donn´ee :
– pr´esence de multiplieurs ou non,
– unit´e de gestion m´emoire (MMU),
– taille du cache et des m´emoires,
– vecteur d’interruptions,
– module de debug JTAG,
– etc.

Architecture des processeurs extensibles

Le processeur NIOSII est un exemple de processeur extensible, mais il existe d’autres solutions architecturales. Nous proposons une classification de ces ASIP a` travers trois crit`eres : le mod`ele d’ex´ecution, le couplage, et la technologie.

Mod`ele d’ex´ecution

Un processeur peut exploiter deux formes de parall´elisme pour acc´el´erer les traite-ments : le parall´elisme temporel, et le parall´elisme spatial. Ces deux formes de parall´elisme sont illustr´ees par la figure 1.11.
Pour ex´ecuter une instruction, un processeur effectue une s´erie de tˆaches : r´ecup´erer l’instruction dans la m´emoire et la charger dans le registre d’instruction, modifier la valeur du compteur ordinal (compteur d’instruction), d´eterminer le genre d’instruction venant d’ˆetre charg´ee, ex´ecuter l’instruction, retourner a` la premi`ere ´etape pour ex´ecuter l’ins-truction suivante. Impl´ementer un chemin de donn´ee qui r´ealise toutes ces tˆaches en un cycle r´esulte en un chemin critique tr`es long qui contraint la vitesse d’horloge du proces-seur. Le parall´elisme temporel, connu sous le nom de technique du pipeline (pipelining ), consiste a` casser le chemin critique en d´ecomposant les instructions en de nombreuses sec-tions el´ementaires, chacune pouvant ˆetre ex´ecut´ee en parall`ele par un composant mat´eriel sp´ecifique. L’architecture ICORE illustr´ee par la figure 1.3 est compos´ee de quatre ´etages de pipeline.
Le parall´elisme spatial est l’ex´ecution en parall`ele et au mˆeme instant de plusieurs instructions non d´ependantes en donn´ees. L’exemple de la figure 1.11 met en exergue l’ex´ecution de deux additions et une multiplication au mˆeme moment, puis de deux mul-tiplications. C’est le parall´elisme au niveau instruction.
Un processeur peut suivre plusieurs mod`eles d’ex´ecution que nous ne d´etaillons pas ici, et un ASIP suit en g´en´eral deux mod`eles d’ex´ecution tr`es r´epandus : le mod`ele d’ex´ecution RISC, et le mod`ele VLIW.
Mod`ele d’ex´ecution RISC. Un processeur RISC (Reduced Instruction Set Compu-ter ) est un processeur poss´edant un jeu d’instructions r´eduit. Son mode d’ex´ecution, aussi appel´ single-issue, est le mode d’ex´ecution le plus simple. Il correspond au mode de fonc-tionnement SISD (Single Instruction Single Data) selon la taxonomie d´efinie par Flynn [76] et est bas´e sur une architecture de Von Neumann. Dans ce mode d’ex´ecution, une seule instruction est ex´ecut´ee a` la fois. De nombreux ASIP suivent ce mode d’ex´ecution : Garp [175], Chimaera [212], OneChip [204], etc. L’exemple de la figure 1.11 illustre ce fonctionnement o`u les instructions sont ex´ecut´ees une par une, et se partagent l’unique unit´e fonctionnelle du processeur.
Mod`ele d’ex´ecution VLIW. Un processeur VLIW (Very Long Instruction Word ) est un processeur comprenant plusieurs slots d’ex´ecution, c’est-a`-dire plusieurs unit´es fonction-nelles capables de s’ex´ecuter en parall`ele. Un processeur VLIW est donc capable d’ex´ecuter en mˆeme temps plusieurs instructions sur plusieurs donn´ees. Pour pouvoir encoder toutes ses informations (instructions a` ex´ecuter et registres op´erandes), le mot de l’instruction doit ˆetre tr`es long, d’o`u le nom de processeur a` mot d’instructions tr`es long (128 bits par exemple au lieu de 32 bits pour un processeur RISC). Un processeur VLIW permet d’exploiter le parall´elisme au niveau instruction. C’est le compilateur qui a la charge de d´etecter le parall´elisme et de g´en´erer le code capable d’exploiter les unit´es fonctionnelles. De nombreux processeurs DSP s’appuient sur ce type de mod`ele d’ex´ecution, comme par exemple le TCI6487 de Texas Instruments [191]. Le nombre de slots d’ex´ecution varie selon l’architecture. Par exemple, le nombre de slots de l’architecture ADRES [151] est param´etrable.
Dans [118], les auteurs pr´esentent une architecture bas´ee sur un processeur VLIW a` quatre PE (Processing Element ), enti`erement mise en œuvre dans un FPGA. Chaque PE contient une UAL et un module qui peut accueillir des instructions sp´ecialis´ees. L’archi-tecture PADDI [213] pr´esente ´egalement un mod`ele d’ex´ecution VLIW o`u chaque slot d’ex´ecution est un nanoprocesseur.

Couplage

La sp´ecialisation partielle consiste a` ajouter un module qui met en œuvre les instruc-tions sp´ecialis´ees. Ce module sp´ecialis´ peut ˆetre int´egr´ a` diff´erents endroits. Les approches architecturales de l’int´egration de la logique sp´ecialis´ee diff`erent selon le degr´ de couplage entre la logique sp´ecialis´ee et le processeur a` usage g´en´eral. Nous distinguons trois degr´es de couplage, illustr´es par la figure 1.12 :
1. Unit´es fonctionnelles – couplage fort
2. Co-processeurs – couplage lˆache
3. Unit´es de traitement attach´ees ou externes – couplage tr`es lˆache
Unit´es fonctionnelles. Dans ce cas de figure, la logique sp´ecialis´ee est fortement coupl´ee au chemin de donn´ees du processeur, en parall`ele de l’UAL du processeur. Cette unit´e est accessible a` travers des instructions sp´ecialis´ees du jeu d’instructions du processeur. Ces ar-chitectures font partie de la classe DEMETER d’apr`es la classification propos´ee par [172]. Un des pionniers en la mati`ere est l’architecture PRISC [175, 174], qui combine un processeur RISC avec des PFU (Programmable Functionnal Unit ). Chaque PFU met en œuvre une fonction combinatoire a` deux entr´ees et produit un r´esultat. L’architecture OneChip [204]

M´ethodologie

L’exemple de l’extension du jeu d’instructions du processeur NIOSII a mis en ´evidence les ´etapes manuelles r´ealis´ees par le concepteur (description de l’architecture de l’instruc-tion et adaptation du code applicatif ). Pour des applications complexes, ce processus est fastidieux et sujet a` erreur. C’est pourquoi il est important de disposer d’une m´ethodologie pour d´etecter automatiquement les portions de code a` d´eporter en mat´eriel, et des outils pour la g´en´eration automatique de l’architecture des instructions sp´ecialis´ees et du code applicatif qui exploite ces instructions.

Granularit´e

La sp´ecialisation peut avoir lieu a` diff´erents niveaux de granularit´e2. Nous distinguons deux niveaux : grain fin et gros grain. La sp´ecialisation a` grain fin op`ere au niveau ins-truction et met en œuvre mat´eriellement un petit ensemble d’op´erations [25, 28, 55]. La sp´ecialisation a` gros grain op`ere au niveau boucle ou proc´edure, et d´eporte une boucle ou une proc´edure enti`ere sur du mat´eriel d´edi´ [31, 90, 101, 174, 203]. Le compilateur C2H d’Altera [17] et l’outil Cascade de CriticalBlue [65] comptent parmi les outils commerciaux qui proposent une solution automatis´ee de synth`ese de co-processeur a` partir d’une fonc-tion ´ecrite en langage C. La communication entre le processeur et le co-processeur ne fait pas appel au m´ecanisme d’extension de jeu d’instructions.
Chacune de ces granularit´es pr´esente des avantages et des inconv´enients. Si la sp´eciali-sation a` gros grain permet d’obtenir d’importantes acc´el´erations, sa flexibilit´ est limit´ee. En effet, il est peu probable que plusieurs applications poss`edent exactement le mˆeme cœur de boucle ou la mˆeme proc´edure. A l’inverse, plus la sp´ecialisation est fine et plus la probabilit´e de trouver une mˆeme suite d’op´erations, dans un ensemble d’algorithmes, est grande. Par exemple, l’op´eration MAC (Multiply-ACcumulate) est tr`es pr´esente dans les applications du traitement du signal.

Automatisation

La figure 1.15 illustre une m´ethodologie g´en´erique appliqu´ee lors d’un processus clas-sique d’extension de jeux d’instructions. Cette m´ethodologie se distingue de la m´ethodologie de conception compl`ete au niveau de l’´etape de g´en´eration du jeu d’instructions. L’exten-sion d’un jeu d’instructions consiste `a g´en´erer un ensemble d’instructions sp´ecialis´ees candi-dates, puis `a s´electionner un sous-ensemble de ces instructions. Comme pour la conception compl`ete, le processus peut ˆetre it´eratif, et le jeu d’instructions est progressivement enrichi de nouvelles instructions. Lorsque le processus n’est pas it´eratif, il s’agit de g´en´erer, en une seule passe, la meilleure architecture possible avec les contraintes de conception appliqu´ees en entr´ee.

Motifs g´en´er´es vs motifs pr´ed´efinis

Un motif est un groupe d’op´erations el´ementaires. L’op´eration MAC (Multiply-Accu-mulate), tr`es pr´esente dans les applications du traitement du signal est un exemple typique de motif.
Les techniques de sp´ecialisation de processeur s’appuient sur deux approches diff´erentes : soit il existe une biblioth`eque de motifs pr´ed´efinis (comme par exemple le MAC), soit cette biblioth`eque est g´en´er´ee a` partir de l’application cible.
Dans le cas o`u une biblioth`eque de motifs est utilis´ee, le processus se r´esume a` l’´etape de s´election d’instructions. Il faut alors analyser l’application pour trouver quelles instructions de la biblioth`eque sont n´ecessaires, c’est-a`-dire trouver les occurrences des motifs dans le graphe d’application. C’est le probl`eme de l’isomorphisme de sous-graphes. Plusieurs approches s’appuient sur l’existence d’une biblioth`eque de motifs [57, 173, 142].
Cependant, afin de disposer d’instructions vraiment adapt´ees a` l’application cible et gagner en performance, la plupart des approches construisent la biblioth`eque en g´en´erant les instructions candidates [29, 44, 48, 86, 167, 217, 219].
Dans le cadre de nos travaux, c’est l’approche qui est retenue.

G´en´eration d’instructions

La g´en´eration d’instructions, l’identification d’instructions, ou la d´ecouverte d’instruc-tions d´esignent le mˆeme processus : la d´etermination des sous-graphes, a` partir d’un graphe d’application cible, candidats potentiels a` une mise en œuvre en mat´eriel. Elle constitue la premi`ere ´etape du processus d’extension de jeu d’instructions. Pour des raisons li´ees a` la prise en compte de l’architecture et de la technologie, cette ´etape est souvent sujette a` des contraintes. Les contraintes les plus courantes concernent le nombre d’entr´ees et de sorties des motifs, la surface, et la consommation d’´energie. De plus, certaines instructions de l’application ne sont pas appropri´ees a` une mise en œuvre mat´erielle. Par exemple, les ins-tructions de contrˆole sont en g´en´eral exclues. Ces nœuds ind´esirables sont appel´es nœuds interdits. De la mˆeme fa¸con, de nombreux travaux excluent les instructions de chargement et de rangement (load,store) [30, 57, 186, 166].

Complexit´ de l’exploration

L’application ´etant repr´esent´ee sous forme de graphe, la g´en´eration d’instructions s’ap-parente au probl`eme de g´en´eration de sous-graphes ou motifs, o`u chaque sous-graphe est un candidat. Dans le cas g´en´eral, chaque nœud du graphe peut faire partie ou non d’un candidat, ce qui entraˆıne un nombre de combinaisons en O(2n), o`u n est le nombre de nœuds du graphe.
L’´enum´eration exhaustive de tous les sous-graphes est en temps exponentiel, et n’est donc pas applicable pour des exemples r´ealistes. Cette complexit´ rend le probl`eme in-traitable. Beaucoup de techniques ont et´e propos´ees pour r´esoudre ce probl`eme, elles sont d´etaill´ees dans la section 2.3. Nous verrons qu’en imposant des contraintes sur les motifs, l’espace de recherche peut ˆetre grandement r´eduit. Une des premi`eres contraintes est la contrainte de connexit´ : un motif peut ˆetre connexe ou non-connexe.

Motif connexe vs non-connexe

Un motif connexe est un motif tel que pour toute paire de nœuds, il existe un chemin entre les deux nœuds. Un motif non-connexe est un motif qui ne satisfait pas cette condi-tion. Les motifs non-connexes font apparaˆıtre plus de parall´elisme au niveau instructions, donc potentiellement de meilleurs gains. Malgr´e les possibilit´es de meilleures acc´el´erations, la plupart des auteurs se limitent a` la g´en´eration de motifs connexes [25, 57, 62]. La fi-gure 2.2 illustre deux motifs, le premier est connexe 2.2(a), et le second non-connexe 2.2(b).

Table des matières

Introduction
1 Conception d’ASIP : m´ethodologies et outils 
1.1 Conception compl`ete d’ASIP
1.1.1 Exemple du langage LISA
1.1.2 M´ethodologie
1.2 Conception partielle d’ASIP
1.2.1 Exemple
1.2.2 Architecture des processeurs extensibles
1.2.3 M´ethodologie
1.2.4 Compilation
1.3 Synth`ese
2 L’extension de jeu d’instructions 
2.1 Quels sont les probl`emes `a r´esoudre ?
2.1.1 Motifs g´en´er´es vs motifs pr´ed´efinis
2.1.2 G´en´eration d’instructions
2.1.3 Limites architecturales et technologiques
2.1.4 S´election d’instructions
2.1.5 Isomorphisme de graphes et de sous-graphes
2.1.6 Exploitation des nouvelles instructions
2.2 Quand les r´esoudre ?
2.2.1 A la conception
2.2.2 A la vol´ee
2.3 Comment les r´esoudre ?
2.3.1 Recherche Tabou
2.3.2 Recuit simul´e
2.3.3 Algorithme g´en´etique
2.3.4 Algorithme de colonies de fourmis
2.3.5 Programmation dynamique
2.3.6 Algorithmes gloutons
2.3.7 Heuristiques
2.3.8 S´eparation et ´evaluation
2.3.9 Programmation lin´eaire par nombres entiers
2.3.10 Programmation par contraintes
2.3.11 Comparaison des approches
2.4 Synth`ese
3 L’identification d’instructions 
3.1 D´efinitions
3.2 Algorithme de g´en´eration de motifs
3.2.1 Expansion d’un motif `a partir d’un nœud graine
3.2.2 Limitation du nombre de motifs : Smart filtering
3.2.3 La contrainte GraphMatch
3.3 Contraintes technologiques et architecturales
3.4 Formalisation pour la programmation par contraintes
3.4.1 Contrainte de connexit´e
3.4.2 Contrainte sur le nombre d’entr´ees et de sorties
3.4.3 Contrainte sur le chemin critique
3.4.4 Contrainte de ressources
3.4.5 Contrainte d’´energie
3.5 R´esultats d’exp´erimentations
3.5.1 Le processeur cible
3.5.2 Environnement d’ex´ecution
3.5.3 Benchmarks
3.5.4 Couverture maximale
3.5.5 Discussion
3.6 Conclusion
4 S´election d’instructions et ordonnancement 
4.1 S´election d’instructions
4.1.1 D´efinition d’une occurrence
4.1.2 D´efinition du probl`eme de s´election d’instructions
4.1.3 Mod´elisation du temps d’ex´ecution d’une occurrence
4.1.4 R´esultats d’exp´erimentation
4.2 Ordonnancement
4.2.1 Placement
4.2.2 Ordonnanceur
4.2.3 Ordonnancement avec recalage d’instructions
4.2.4 Optimisation sur les transferts de donn´ees
4.2.5 R´esultats d’exp´erimentation
4.3 Conclusion
5.1 Architecture de l’extension
5.1.1 Diff´erents types d’instructions sp´ecialis´ees
5.1.2 Mod`eles d’architecture
5.2 Allocation de registres
5.2.1 Contrainte Diff2
5.2.2 Allocation de registres appliqu´ee au mod`ele A
5.2.3 Allocation de registres appliqu´ee au mod`ele B
5.3 G´en´eration des codes d’op´eration et de la description de l’architecture
5.3.1 G´en´eration des codes d’op´erations
5.3.2 G´en´eration du bloc logique sp´ecialis´e
5.3.3 G´en´eration du chemin de donn´ee des instructions sp´ecialis´ees
5.3.4 Fusion du chemin de donn´ees
5.4 G´en´eration du code source modifi´e
5.5 G´en´eration pour la simulation SystemC
5.5.1 SystemC
5.5.2 SoCLib
5.5.3 G´en´eration des instructions sp´ecialis´ees pour le mod`ele du NiosII . 136
5.6 Conclusion
6 D´eroulement du flot appliqu´e `a l’algorithme GOST 139
6.1 Le flot de conception DURASE
6.1.1 Gecos
6.2 L’algorithme de chiffrement GOST
6.3 D´eroulement du flot ´etape par ´etape appliqu´e `a l’algorithme de chiffrement
GOST
6.3.1 Param`etres d’entr´ee
6.3.2 Partie frontale
6.3.3 Cr´eation d’une extension
6.3.4 G´en´eration d’architecture
6.3.5 Adaptation du code
6.3.6 Validation par simulation avec SoCLib
6.3.7 R´esum´e
6.4 Proposition d’architecture
6.5 Conclusion
Conclusion 167
Publications 171
Bibliographie 173

Télécharger le rapport complet