Upload
tounssi-hor-tounssi-hor
View
179
Download
0
Embed Size (px)
Citation preview
Limites du pipelineNSY 104
Jrme Dupire
Les alasRappel ADD R1,R2, R3 SUB R4, R1, R5 ADD R12, R5, R4 Les problmes viennent des dpendances entre instructions qui empchent leur paralllisation Identification des alas lors de DI
Jrme Dupire
Les alas de donnesCode ADD R1,R2, R3 SUB R4, R1, R5 Sans prcaution, une architecture pipeline permettrait SUB de lire R1 alors que ADD na pas rang son rsultat. Valeur errone Solution (matrielle): lenvoi drivation
Jrme Dupire
Les alas de donnesLa valeur est disponible la fin de EX (tage 3) On cr un moyen pour communiquer ce rsultat en avance chemin matriel Fonctionnement Le rsultat UAL est toujours renvoy aux entres UAL Depuis le registre EX/MEM Depuis le registre MEM/WB La logique de contrle dtecte ce mcanismeet slectionne la valeur envoye plutt que celle lue dans le registre source
Jrme Dupire
Les alas de donnesIF ID EX MEM WB
ADD R1,R2,R3 SUB R4,R1,R5 AND R6,R1,R7 OR R8,R1,R9WB
IF
ID
EX
MEM
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
WB ID Ecriture registre 1re moiti cycle Lecture registre 2me moiti cycleIF ID EX MEM WB
Jrme Dupire
Les alas de donnesCela permet dviter des suspensions du pipeline On peut gnraliser ces chemins vers dautres tages du pipelineADD R1,R2,R3 LD R4,0(R1) SD R4,10(R1)IF ID EX MEM WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
Jrme Dupire
Les alas de donnesCertains alas ne peuvent tre rsolusSuspension du pipeline incontournable ExempleLD R1, 0(R2) SUB R4,R1,R5 AND R6,R1,R7 OR R8,R1,R9
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
Jrme Dupire
Les alas de donnesInsertion dun cycle de suspension (No-Op)IFLD R1, 0(R2) SUB R4,R1,R5 AND R6,R1,R7 OR R8,R1,R9
ID IF
EX ID IF
MEM
WB EX ID IF MEM EX ID WB MEM EX WB MEM WB
Noop Noop Noop
Jrme Dupire
Les alas de contrlePeuvent tre plus pnalisants que les alas de donnes De 10 30% de rduction de performance Le branchementModifie le CP avec autre chose que CP+4 (longueur de linstruction)BRANCHEMENT PRIS Rptition de ltape IFRupture de la squence
Laisse lexcution se drouler en squence (CP+4)BRANCHEMENT NON PRIS Pas de suspensionLinstruction qui a t charge ensuite est la bonne.
Jrme Dupire
Les alas de contrleMinimiser les pnalits des branchementsPar le vidage du pipelineou gel du pipeline Consiste supprimer (suspendre) toutes les instructions aprs le branchement jusqu la connaissance de la destination
IF ID EX M W E B M
N IF ID E X o o p
M W E B M
IF ID EX M W E B M IF ID EX M W E B M
Jrme Dupire
Les alas de contrlePar le schma de prdiction non prisTraite tous les branchements comme non prisChargement en squence
IF ID EX M W E B M IF
Si un branchement pris apparatAnnulation de linstruction charge Chargement de la cible
N N N N o o o o o o o o p p p pIF ID E X M W E B M
IF ID EX M W E B M
Jrme Dupire
Les alas de contrlePar le schma de prdiction prisTraite tous les branchements comme pris Ds que le branchement est dcodOn lit linstruction destination On commence lexcution
Dans notre exemple 5 tagePas dintrt On ne connait pas ladresse de destination avant de savoir sil pris ou non
Dans dautres schmas de pipeline
Jrme Dupire
Paralllisme des instructionsTechniques matrielles ou logicielles pour parallliserTechniques matrielles, dynamiquesmajoriataires
Techniques logicielles, statiquescompilateur informatique enfouie, IA64, Itanium
Paralllisme dans un bloc dinstructions sans branchement est faibleDpendances forte lintrieur du bloc
Pour un MIPS, la frquence moyenne des branchements est de 15 25%Entre 2 branchements, 4 7 instructions en squence
Jrme Dupire
Paralllisme des instructionsOn peut exploiter le paralllisme de boucleParalllisme entre les itrations dune boucle
Pour en dgager un paralllisme dinstructions MthodesDrouler la boucle la compilation Dynamiquement (matriel)
Utilisation dinstructions vectoriellesOprant sur une suite dlments de donnes
Jrme Dupire
DpendancesDtection des dpendances2 instructions parallles peuvent sexcuter dans le pipeline sans crer de suspension 2 instructions dpendantes ne sont pas paralllesElles doivent sexcuter dans lordre Avec un recouvrement partiel possible
3 types de dpendancesde nom de donne de contrle
Jrme Dupire
DpendancesLes dpendances peuvent causer des alas Les alas peuvent causer des suspensions Proprits de lorganisation du pipelineDcoupage des tages par exemple
Une dpendanceIndique la possibilit dun ala Dtermine lordre dexcution des oprations Limite la quantit de paralllisme
Objectifs:Identifier la dpendance et viter lala Eliminer la dpendance (rorganiser le code)
Jrme Dupire
Les dpendances de donnesInterviennent quandUne instruction a utilise le rsultat de linstruction b Une instr. b a une dep. de donne avec linstr. c et que c a une dep. de donne avec a.Transitivit Chaines de dpendances
Peuvent tre difficiles identifierCirculation via des cases mmoires10 (R1) = 20 (R2)
Jrme Dupire
Les dpendances de nomInterviennent quand des instructions indpendantes utilisentle mme nom de registre la mme case mmoire
Anti-dpendance entre 2 instructions a et bQuand b crit dans un emplacement lu par a
Dpendance de sortieQuand a et b crivent dans le mme emplacement
Le renommage permet de contourner ces obstaclesChanger les contenants A la vole ou statiquement, la compilation
Jrme Dupire
Les alas de donnesLAE (lecture aprs criture)Le plus frquent
EAL (criture aprs lecture) EAE (criture aprs criture) LAL (lecture aprs lecture) nest pas un alaPas de modification
Jrme Dupire
Lordonnancement dynamiqueLimitation du pipelineLancement et dexcution ordonns des instructionsSi une instruction est suspendue, tout le pipeline est affect Pas de lancement possible dune instruction suivante
Principe de lordonnancement dynamiqueCasser ce blocage en permettant le lancement dinstructions sans dpendance
out of order (OOO )
ExempleDIV R0, R2, R4 ADD R10, R0, R8 SUB R12, R8, R14
Jrme Dupire
Lordonnancement dynamiqueNouvel aspect grerLe lancement non ordonn entrane une terminaison non ordonne
Apparition des alas qui nexistent pas dans le pipeline ordonnEAL EAE
Division de ltage DI en 2 partiesLancementDcodage de linstruction, test des alas structurels
Lecture oprandesAttente de la fin des alas de donnes, lecture des oprandes
Jrme Dupire
Lordonnancement dynamiquePar tableauToutes les instructions traversent ltage de lancement dans lordre. Elles peuvent passer dans ltage suivantdans lordre, tre suspendue passer lune devant lautreordonnancement dynamique.
La technique du tableau est connue sous le nom de tableau de marques.Le but du tableau est dexcuter les instructions ds que possible. Si une instruction est suspendue, les suivantes peuvent tre excutes conditionquil ny ait pas de dpendance que les ressources ncessaires soient disponibles
Jrme Dupire
Lordonnancement dynamiqueLancementsi une unit fonctionnelle est libre pour linstruction et quaucune autre instruction active na le mme registre destination le tableau lance linstruction vers lunit fonctionnelle
Lecture des oprandesLe tableau de marques contrle la disponibilit des oprandes sources. Un oprande source est disponible si aucune instruction active lance auparavant ne va la modifier en criture ou si aucune unit fonctionnelle active nest en train dcrire loprande dans le registre. Si les oprandes sources respectent cette condition, le tableau indique lunit fonctionnelle quelle peut lire les oprandes et commencer lexcution. Cette tape termine le dcodage de linstruction.
Excutionlunit fonctionnelle commence lexcution la rception des oprandes. Quand le rsultat est prt, elle avertit que lexcution est termine. Cette tape utilise plusieurs cycles du pipeline.
Ecriture du rsultatune fois que le tableau sait que lunit fonctionnelle termin son excution.
Jrme Dupire
Lordonnancement dynamiqueMthode de TomasoluIdentifier les dpendances dinstructionsPermettre lexcution ds que les oprandes sont disponiblesEvite les alas LAE
Renommage des registresEvite les alas EAL et EAE
Bus Commun de Donnes (BCD)
Stations de rservationFournissent le service de renomage de registre Mmorisent les oprandes des instr. en attente de dmarrageDs quil est disponible Ne passe plus par les registres originaux
Jrme Dupire
Lordonnancement dynamiqueMthode de Tomasolu3 tapes pour chaque instructionLancement (Renome les registres limine EAL et EAE)Obtenir linstruction suivante (FIFO) Lancer linstr. une station libre Sinon, attendre la libration dune station (ala structurel) Si les oprandes ne sont pas dans les registres, observer les units fonctionnelles qui vont les produire
ExcutionTous les oprandes sont disponibles: lancer lexcution Sinon, continuer de les attendre (limine LAE)
Ecriture du rsultatRsultat disponible: criture sur le BCD sur le banc de registres dans les stations qui lattendent
Jrme Dupire
Lordonnancement dynamiqueInstruction LD F6, 34(R2) LD F2, 45(R3) MUL F0,F2,F4 SUB F8,F2,F6 DIV F10,F0,F6 ADD F6,F8,F2 Nom Load1 Load2 Add1 Add2 Add3 Mul1 Mul2 Lancement X X X X X X Occup N O O O N O O MUL DIV Reg[F4] Mem[34+reg[R2]] Load2 Mult1 Chargemen t SUB ADD Mem[34+reg[R2]] Load2 Add1 Load2 45+reg[R3] Op Vj Champ Qi F0 Mult1 F2 Load2 F4 F6 Add2 F8 Add1 F10 Mult2 Excution X X Ecriture X
Etat quand le premier chargement est termin et crit
Vk
Qj
Qk
A
Jrme Dupire
La prdiction de branchementRduire les suspensions dues aux dpendances de contrle Solution la plus simple:Tampon de prdiction de branchementTable des historiques des branchements
Petite mmoire indexe par la partie basse de ladresse de linstruction de branchementContient un bit pour indiquer la prise rcente de ce branchement
Jrme Dupire
La prdiction de branchementVersion amliore avec un prdicteur 2 bitsNcessite 2 erreurs conscutives pour tre permut
Prdit Pris 11
Prdit Pris 10
Prdit Non Pris 01
Prdit Non Pris 00
Jrme Dupire
Les processeurs superscalairesPermettent lexcution de plusieurs instructions en mme tempsOn duplique le matriel pour avoir plusieurs chemins de traitement Gnralement combin au pipeline
Jrme Dupire
Les processeurs superscalairesLa nature des limitations est comparable aux architectures prcdentes Degr de paralllisme intrinsque du code Le cot de la logique de contrle Le traitement des instructions de branchement
Optimisation par ordonnancementStatique (compilateur) Dynamique (matriel)
Jrme Dupire
Lapproche VLIWVery Long Instruction WordAlternative au superscalaire pur Sappuie sur les compilateurs pour rorganiser le codeEn groupant des instructions parallles En taggant le dpendances possibles
Longueur de mot de 64 bits et plus Un mot regroupe plusieurs instructions parallles Le matriel dispose de plusieurs units fonctionnelles indpendantes
Jrme Dupire
Lapproche VLIW
Jrme Dupire
Lapproche VLIWCompatibilit du code binaireCompilation trs procheDu jeu dinstruction De la structure pipeline
Diffrents matriel = compilations diffrentes