Wikilivres frwikibooks https://fr.wikibooks.org/wiki/Accueil MediaWiki 1.47.0-wmf.24 first-letter Média Spécial Discussion Utilisateur Discussion utilisateur Wikilivres Discussion Wikilivres Fichier Discussion fichier MediaWiki Discussion MediaWiki Modèle Discussion modèle Aide Discussion aide Catégorie Discussion catégorie Transwiki Discussion Transwiki Wikijunior Discussion Wikijunior TimedText TimedText talk Module Discussion module Event Event talk 0 5099 775393 773962 2026-10-18T20:19:52Z ~2026-50998-65 124625 /* Giseigo */ 775393 wikitext text/x-wiki [[Image:Books-aj.svg aj ashton 01.svg|right|70px]] Une ''onomatopée'' (オノマトペ) est un son pour imiter un bruit (animal, voiture…) ou pour exprimer une émotion (étonnement, peur), un état, une action. Les onomatopées japonaises sont classées en deux groupes principaux : ''giseigo'' (擬声語) et ''gitaigo'' (擬態語). == Giseigo == C'est un son fait pour imiter un bruit. {| {{tableau_japonais}} ! Français ! [[Japonais/Kana|Kana]] ! [[Japonais/Romaji|Rōmaji]] |- | Applaudissement | パチパチ | Pachi-pachi |- | Atchoum (éternuement) | ハクション、 クシャン | Hakushon, Kushan |- | Baahaha (éléphant) | パオー | Paō |- | Bêê-bêê (caprin, ovin) | メーメー | Mē-mē |- | Bloub-bloub (poisson) | プクプク | Puku-puku |- | Bzzz-bzzz (abeille, guêpe, etc.) | ブンブン | Bun-bun |- | Chute d'eau, goutte de pluie | ポツポツ | Potsu-potsu |- | Cocorico (coq) | コケコッコ | Kokekokko |- | Cot-cot-codec (poule) | コッコッコ | Kokkokko |- | Hiii-hiii (cheval, zèbre) | ヒーン | Hīn |- | Iiiik (lapin) | ピョンピョン | Pyon-pyon |- | Miaou-miaou (félidé) | ニャニャ、 ニャンニャン | Nya-nya, Nyan-nyan |- | Ouaf-ouaf (chien) | ワンワン | Wan-wan |- | Pluie forte | ザーザー | Zā-zā |- | Coa-coa (crapeau, grenouille) | ケロケロ | Kero-kero |- | Crôa-crôa (corbeau) | カーカー | Kā-kā |- | Coin-coin (canard) | ガーガー | Gā-gā |- | Hi-han (âne) | グーヒー | Gūhī |- | Hou-hou (hibou) | ホーホー | Hō-hō |- | Groin-groin (porcin) | ブーブー | Bū-bū |- | Cui-cui (oiseau) | ピーピー | Pī-pī |- | Pof (écrasement) | ドスン | Dosun |- | Hooou (loup) | ウオォォン | Uoōn |- | Meuh (bovin) | モー | Mō |- | Piou-piou (poussin) | ピヨピヨ | Piyo-piyo |- | Prout (flatulence) | ブー、 プー、 プゥー | Bū, Pū, Puū |- | Rouar (lion, tigre, etc.) | ガオー | Gaō |- | Rou-rou (pigeon, colombe, tourterelle) | ポッポポッポ | Poppo-poppo |- | Ssssss (serpent) | シュルシュル | Shuru-shuru |- | Hii Hii (singe) | ウキウキ | Uki-uki |- | Wouif (renard) | コンコン | Kon-kon |- | Couic (rat, souris) | チュウ | Chuu |- |Tsing (épée (croisement des fers)) | ザァァッ | Zaātsu |- | Burp (éructation) | ゲップ | Geppu |- | Pin-pon (sirène de pompiers) | ビーボビーボ | Bībo-bībo |- |Smack (baiser) | チュー | Chū |- | Dring dring (téléphone) | リンリン、プルルル | Rin-rin, Purururu |- |Tagadam (train roulant sur les rails) |カタンコトン、 ガタンゴトン |Katan-koton, Gatan-goton |- |Craquement de la neige sous les pieds |サクサク |Saku-saku |- |Hum ! |ン！ |N! |- |Pan-pan (fessée) |ペンペン |Pen-pen |- |Ouin (pleurs) |シクシク |Shiku-shiku |- |Pan (pistolet) |ドキューン、 ズキューン |Dokyūn, Zukyūn |- |Reum (cerf, chevreuil, daim, etc.) | | |- | (panda roux) |ピィー ピィー |Piī-Piī |- | (chien viverrin) |キューンキューン |Kyūn-kyūn |- |Nihin (tortue) |ム |Mu |- |Kiakiakiakia (pic vert) |カカカカカ |Kaka-kaka-ka |- |Tic tac (horloge) |チクタク、 カチカチ |Chiku-taku, Kachi-kachi |- |Feu qui crépite |メラメラ |Mera-mera |- |Eau qui se soulève en vagues |ジャブジャブ |Jabu-jabu |- |Bois qui claque |モクモク |Moku-moku |- |Métal frappé |キンキラ |Kin-kira |- |Terre qui gronde |ドンドン |Don-don |- |Rythme cardiaque |チックチック |Chikku-chikku |- |Rythme cardiaque rapide |ドキドキ |Doki-doki |- |Miam miam |モグモグ |Mogu-mogu |- |Ding dong (signal de réponse correcte à une question) |ピンポン |Pin-pon |- |Hum (doute) |フフン |Fu-fun |- |Bang |バン |Ban |- |Boum |ブン、キュン |Bun (explosion), Kyun (cœur) |- |Ronron (félidé) |ゴロゴロ |Goro-goro |- |Tétine |チューチュー |Chū-chū |- |Hummm (girafe) |キリンキリ |Kirin-kiri |- |Iiik (lapin) | | |- |Bip-bip |ピコピコ |Piko-piko |- |Tchou-tchou |シュポーッ (train à vapeur)<br>ビュンビュン (train électrique) |Shuppō<br>Byun-byun |- |Plouf |ドンブラコ |Donburako |- |Tagada |パカパカ |Paka-paka |- |Hou-hou (hibou, chouette) |ホーホー |Hōhō |- |} == Gitaigo == C'est un son fait pour exprimer une action, un état, une émotion. {|{{tableau_japonais}} ! Français ! [[Japonais/Kana|Kana]] ! [[Japonais/Romaji|Rōmaji]] |- |Basculer sans arrêt entre sommeil et éveil |ウツラウツラ |Utsura-utsura |- |Enfant qui joue |ワイワイ |Wai-wai |- |Être négligent ou distrait |ウカウカ |Uka-uka |- |Flirter devant d'autres personnes sans se soucier de leur présence |イチャイチャ |Icha-icha |- |Sauter |ウハウハ |Uha-uha |- |Se sentir incommodé |オドオド |Odo-odo |- |Somnoler |ウトウト |Uto-uto |- |Manger |ムシャムシャ |Musha-musha |- |Mastiquer |ガブガブ |Gabu-gabu |- |Tourner en rond |イソイソ |Iso-iso |- |Être à l'aise |ノビノビ |Nobi-nobi |- |Être tendre et moelleux |フワフワ |Fuwa-fuwa |- |Gargouiller |ペコペコ |Peko-peko |- |Sourire |ニコニコ |Niko-niko |- |Être silencieux |シイーン |Shiīn |- |Scintiller |ピカピカ |Pika-pika |- |Regarder intensément |ジロジロ |Jiro-jiro |- |Être prostré |グズグズ |Guzu-guzu |- |Jeter un coup d'œil à la dérobée |チラ |Chira |- |Se brosser les dents |ゴシゴシ、 チャカチャカ |Goshi-goshi, Chaka-chaka |- |Rire |ハゥハゥハゥ、 ハハハ、 ククク (rire maléfique) |Hu-hu-hu, Ha-ha-ha, Ku-ku-ku |- |Pleurnicher |メソメソ |Meso-meso |- |Pleurer fort |ワーワー |Wā-wā |- |Avoir le cafard |クサクサ |Kusa-kusa |- |Yoyoter de la touffe |クルクルパ |Kuru-kurupa |- |Donner le tournis |クラクラ |Kura-kura |- |Marcher sans but, flâner |ブラブラ |Bura-bura |- |Être trempé (tout mouillé) |ビショビショ |Bisho-bisho |- |Faire quelque chose de justesse |ギリギリ |Giri-giri |- |Être radin |ケチケチ |Kechi-kechi |- |Regarder autour de soi avec effarement ou curiosité |キョロキョロ |Kyoro-kyoro |- |Faire les gros yeux, rouler des yeux |ギョロギョロ |Gyoro-gyoro |- |Avoir une érection pénienne |モッコリ |Mokkori |- |S'élever rapidement |ムクムク |Muku-muku |- |Être distant, morose, mordant |ツンツン |Tsun-tsun |- |Être ramolli d'amour |デレデレ |Dere-dere |- |Se hâter |セカセカ |Seka-seka |- |Se mouiller |グショグショ |Gusho-gusho |- |Briller |キラキラ |Kira-kira |- |Marcher lentement |ノロノロ |Noro-noro |- |Lécher |ペロペロ |Pero-pero |- |Être distrait |ウカウカ |Uka-uka |- |Être hésitant |イジイジ |Iji-iji |- |Être excité |ワクワク |Waku-Waku |- |Perdre patiente |イライラ |Ira-ira |- |Flâner sans but |ウロウロ |Uro-uro |- |Être timide |モジモジ |Moji-moji |- |Être rugueux |ザラザラ |Zara-zara |- |Être glissant |スベスベ |Sube-sube |- |Être doux |サラサラ |Sara-sara |- |Être soyeux |ツルツル |Tsuru-tsuru |- |Être énervé |カッカ |Kakka |- |Être angoissant, malaisant (situation) |ザワザワ |Zawa-zawa |} {{Glossaires_de_Japonais}} [[Catégorie:Glossaires de Japonais]] jvl85twkdlxgvr1vj64e0qu8iladtat 0 17755 775367 654973 2026-10-18T14:07:52Z OpenDataMage 124750 coquille 2 mots synonymes 775367 wikitext text/x-wiki <noinclude>{{Programmation informatique}}</noinclude> Une instruction est une opération de base du processeur ou d'un langage de programmation, une opération que le programmeur demande à la machine d'exécuter. Une instruction est une opération élémentaire, c'est à dire l'ordre le plus basique que peut comprendre un ordinateur. Fondamentalement, elle comporte deux éléments : l'action que le processeur va effectuer et les éléments sur laquelle l'action va être effectuée. Par exemple une instruction demandant l'addition des nombres ''a'' et ''b'' fera intervenir l'opérateur d'addition et les valeurs identifiées par les noms ''a'' et ''b''. == Les instructions typiques == Les sections suivantes présentent les instructions typiques de la plupart des langages de programmation. === Déclaration === La déclaration permet à un compilateur ou interpréteur de connaitre à quoi correspond un identifiant. En général on déclare : * les variables : en général un type précis est associé à l'identifiant. Exemple : A:ENTIER ''' EN BASIC :''' Dim A as String * 5 [''qui affecte une zone de mémoire à la variable A pour une chaine de caractère comportant 5 caractères''] * les fonctions : l'identifiant est associé à une fonction retournant un résultat d'un type spécifié, et prenant comme arguments ceux qui sont spécifiés. Exemple : FONCTION MAX(A:ENTIER, B:ENTIER) RETOURNE ENTIER <!-- SI A &gt; B ALORS RETOURNE A SINON RETOURNE B FIN_FONCTION --> * les classes : en programmation objet, une classe définit un nouveau type de données auquel peut s'appliquer un certain nombre de fonctions (appelées méthodes). Exemple : CLASSE VEHICULE <!-- MARQUE: CHAINE; KILOMETRAGE: ENTIER; CONSOMMATION_CARBURANT_PAR_KM: ENTIER; FONCTION CONSOMMATION_TOTALE() RETOURNE ENTIER RETOURNE KILOMETRAGE * CONSOMMATION_CARBURANT_PAR_KM; FIN_FONCTION FIN_CLASSE --> * d'autres entités qui dépendent du langage de programmation utilisé. Certains langage n'ont pas besoin de déclarer les variables au préalable. D'autres ne définissent pas le type des variables. Dans ce cas là, le type est celui de la valeur à laquelle on l'affecte. === Affectation === L'instruction d'affectation permet de stocker le résultat d'une expression ou la valeur d'une constante dans une variable. Exemples : A ← 5 A ← A + 2 === Expressions === Une expression contrairement à une instruction peut être affectée. Typiquement <code>int a = <TEST> ? <VALEUR A> : <VALEUR B>;</code> est légal mais <code>int a = if <TEST> <VALEUR A> else <VALEUR B>;</code> n'est pas légal car <code>if</code> est une '''instruction''' et non une '''expression''' même si les deux construction seraient fondamentalement identiques autrement. ==== Arithmétique ==== Une expression arithmétique fait appel au cœur logique du processeur. ADD A, B ==== Comparaison ==== Simplification de l'opération de soustraction. si on soustrait deux opérandes, selon que le résultat soit inférieur, égal ou supérieur à zéro, on peut connaitre la différence entre deux opérandes. CMP A, B ==== Appel de fonction ==== CALL === Bloc d'instruction === Plusieurs instructions peuvent être regroupées en une seule en les encadrant par des accolades, ou par deux mots-clés du langage de programmation utilisé. Exemple : DEBUT TMP ← B B ← A A ← TMP FIN Le bloc tout entier est alors considéré comme une seule instruction et peut être utilisé pour définir une fonction, ou l'utiliser avec une instruction de contrôle d'exécution. === Contrôle d'exécution === Les instructions contrôlant l'[[#Ordre d'exécution des instructions|ordre d'exécution]] sont les suivantes : * La condition : l'instruction qui suit n'est exécutée que si une condition est remplie. Exemple : SI A < 0 ALORS A ← 0 :On peut ajouter une instruction à exécuter dans le cas contraire : SINON A ← 1 * Une boucle permet de répéter un certain nombre de fois une même instruction. Exemple : POUR I DE 1 À 10 FAIRE A ← A + I FIN_POUR == Ordre d'exécution des instructions == Sauf instruction contraire, l'ordre d'exécution des instructions est celui de la lecture du code source : de la gauche vers la droite, de haut en bas. Exemple : A ← 5 ; B ← A + 2 ; A ← 6 ; B ← A + 4 ; L'ordre d'exécution des instructions de cet exemple est le suivant : #<code>A ← 5 ;</code> La variable A contient la valeur 5. #<code>B ← A + 2 ;</code> La variable B contient la valeur 7 (5+2). #<code>A ← 6 ;</code> La variable A contient maintenant la valeur 6. #<code>B ← A + 4 ;</code> La variable B contient maintenant la valeur 10 (6+4). Les instructions qui utilisent un ordre d'exécution différent sont des instructions de [[#Contrôle d'exécution|contrôle d'exécution]]. b7q61ucyo8yesp5d10e74lcl438a4it 0 18906 775361 597606 2026-10-18T12:10:05Z Cdang 1202 simplification 775361 wikitext text/x-wiki {{livre de cuisine}} ==Soupe à la citrouille à la crème et aux herbes== == Ingrédients == * 1 kg de chair de {{i|courge}} * 1 pot de [[Catégorie:Recettes de cuisine à base de crème fraîche|crème]] épaisse * Une bonne poignée d'herbes hachées (persil plat, cerfeuil…) * 1 pincée de {{i|sucre}} * 100 g de comté râpé * Sel, poivre, {{i|noix de muscade}} == Recette == # Découper en gros dés la chair du potiron, et la faire cuire durant 20 minutes environ dans de l'eau salée ; # Bien égoutter, et en faire une [[purée]] à l'aide d'un [[moulin à légumes]] ; # Mettre cette purée dans une casserole ; #Faire chauffer en remuant constamment en ajoutant la crème, un peu de sucre, le sel, le {{i|poivre}} et la noix de muscade ; # Saupoudrer d'herbes hachées au moment de servir ; #Rajouter dans l'assiette des croûtons de {{i|pain}} grillé et du comté râpé. == Soupière de citrouille aux graines == === Ingrédients === * Une petite {{i|citrouille}} de 2 kg environ * 1 demi-litre de bouillon de poule * 1 {{i|'=oui|oignon}} * Sel, poivre, herbes ciselées * [[Catégorie:Recettes de cuisine à base de gruyère|Gruyère]] râpé et croûtons selon les goûts. === Recette === # Enlevez le dessus de la citrouille pour en faire un couvercle; # La videz à l'aide d'une cuiller en laissant à l'intérieur une petite paroi de chair et La mettre de côté. # Découpez la chair en cube, la cuire avec le bouillon, l'oignon au préalable coloré à la poêle, le sel et le poivre. ==== Passer au moulin à légumes ==== # Versez ce potage dans la citrouille évidée, la refermer, et mettre le tout au four durant 40 minutes. ===== Pendant ce temps: ===== #Dégagez les graines des filaments, et les faire griller à la poêle. # Utilisez la citrouille comme soupière. Juste avant de servir; #Rajoutez peu de crème épaisse et les herbes ciselées; #Ajustez le sel et le poivre; #Enlevez un peu de chair de la paroi avec chaque louche de potage servie. Chacun pourra agrémenter ce très joli potage d'un peu de gruyère, de croûtons, et de graines. == La version minceur == === Ingrédients === * 500 grammes de chair de {{i|potiron}} * 1 oignon * 1 gousse d'{{i|'=oui|ail}} * 2 branches de [[céleri]] * Un peu de [[thym]] et une feuille de laurier. * 1 litre de bouillon de poule * 2 cuillères à soupe de {{i|fromage}} blanc * 1 cuiller à soupe de {{i|lait}} écrémé en poudre * Des herbes fraîches ciselées ({{i|persil}} plat, [[cerfeuil}}...) === Recette === # Détailler les légumes en morceaux ; #Étuver l'oignon, l'ail hachés, puis les légumes, le thym et le laurier dans un peu de beurre, pendant une dizaine de minutes à feu doux ; # Ajouter le bouillon, et laisser cuire pendant 20 minutes ; #Retirer le thym et la feuille de laurier ; # Saler, poivrer ; #Ajouter le fromage blanc, le lait en poudre puis passer au mixer ; Servir aussitôt, et parsemer d'herbes fraîches. [[Catégorie:Soupes|Citrouille Soupe]] [[Catégorie:Recettes de tous les jours|Citrouille Soupe]] 7jedtbqsonhpy6b2pkdwq9ubherfz3m 775362 775361 2026-10-18T12:13:22Z Cdang 1202 mise en forme, correction 775362 wikitext text/x-wiki {{livre de cuisine}} ==Soupe à la citrouille à la crème et aux herbes== === Ingrédients === * 1 kg de chair de {{i|courge}} * 1 pot de [[Catégorie:Recettes de cuisine à base de crème fraîche|crème]] épaisse * Une bonne poignée d'herbes hachées (persil plat, cerfeuil…) * 1 pincée de {{i|sucre}} * 100 g de comté râpé * Sel, poivre, {{i|noix de muscade}} === Recette === # Découper en gros dés la chair du potiron, et la faire cuire durant 20 minutes environ dans de l'eau salée ; # Bien égoutter, et en faire une [[purée]] à l'aide d'un [[moulin à légumes]] ; # Mettre cette purée dans une casserole ; #Faire chauffer en remuant constamment en ajoutant la crème, un peu de sucre, le sel, le {{i|poivre}} et la noix de muscade ; # Saupoudrer d'herbes hachées au moment de servir ; #Rajouter dans l'assiette des croûtons de {{i|pain}} grillé et du comté râpé. == Soupière de citrouille aux graines == === Ingrédients === * Une petite {{i|citrouille}} de 2 kg environ * 1 demi-litre de bouillon de poule * 1 {{i|'=oui|oignon}} * Sel, poivre, herbes ciselées * [[Catégorie:Recettes de cuisine à base de gruyère|Gruyère]] râpé et croûtons selon les goûts. === Recette === # Enlevez le dessus de la citrouille pour en faire un couvercle; # La videz à l'aide d'une cuiller en laissant à l'intérieur une petite paroi de chair et La mettre de côté. # Découpez la chair en cube, la cuire avec le bouillon, l'oignon au préalable coloré à la poêle, le sel et le poivre. # Passer au moulin à légumes # Versez ce potage dans la citrouille évidée, la refermer, et mettre le tout au four durant 40 minutes. === Pendant ce temps: === # Dégagez les graines des filaments, et les faire griller à la poêle. # Utilisez la citrouille comme soupière. Juste avant de servir; # Rajoutez peu de crème épaisse et les herbes ciselées; # Ajustez le sel et le poivre; # Enlevez un peu de chair de la paroi avec chaque louche de potage servie. Chacun pourra agrémenter ce très joli potage d'un peu de gruyère, de croûtons, et de graines. == La version minceur == === Ingrédients === * 500 grammes de chair de {{i|citrouille}} * 1 oignon * 1 gousse d'{{i|'=oui|ail}} * 2 branches de [[céleri]] * Un peu de [[thym]] et une feuille de laurier. * 1 litre de bouillon de poule * 2 cuillères à soupe de {{i|fromage}} blanc * 1 cuiller à soupe de {{i|lait}} écrémé en poudre * Des herbes fraîches ciselées ({{i|persil}} plat, [[cerfeuil}}...) === Recette === # Détailler les légumes en morceaux ; # Étuver l'oignon, l'ail hachés, puis les légumes, le thym et le laurier dans un peu de beurre, pendant une dizaine de minutes à feu doux ; # Ajouter le bouillon, et laisser cuire pendant 20 minutes ; # Retirer le thym et la feuille de laurier ; # Saler, poivrer ; # Ajouter le fromage blanc, le lait en poudre puis passer au mixer ; Servir aussitôt, et parsemer d'herbes fraîches. [[Catégorie:Soupes|Citrouille Soupe]] [[Catégorie:Recettes de tous les jours|Citrouille Soupe]] r21bhropocwxlyw7uq6yose5y432v9g 14 44462 775360 326785 2026-10-18T12:09:09Z Cdang 1202 courge 775360 wikitext text/x-wiki {{Autres projets|w=Potiron|wikt=potiron}} [[Catégorie:Recettes de cuisine à base de courge|Potiron]] kgvkmlu23cv9jkk3xobtywk0iykupw3 0 65955 775384 774873 2026-10-18T16:11:42Z Mewtow 31375 /* La prédiction de l'adresse de retour d'une fonction */ 775384 wikitext text/x-wiki Les branchements sont pris en charge par plusieurs étages du pipeline. Exécuter un branchement demande de savoir deux choses : s'il est pris ou non, quelle est l'adresse de destination. L'adresse de destination est localisée grâce au mode d'adressage du branchement. Avec le mode d'adressage direct, elle est extraite de l'instruction par le séquenceur. Avec l'adressage indirect, elle est lue dans un registre. Avec les branchements relatifs, elle est calculée via un additionneur, qui additionne un décalage au ''program counter''. L'additionneur peut être soit dans l'étage de ''PC Update'', soit dans l'unité de calcul de l'étage d'exécution. Passons maintenant au résultat du branchement, à savoir s'il est pris ou non. Pour savoir si le branchement est pris, il faut distinguer les branchements conditionnels et inconditionnels. Pour rappel, les branchements inconditionnels regroupent les appels de fonction, les simples instructions de saut, et quelques autres. Ils sont toujours pris, ils s'exécutent toujours. À partir du moment où le décodeur a décodé un branchement inconditionnel, il sait que le branchement est pris. Pour les branchements conditionnels, ils sont pris seulement si une condition précise est respectée. On sait s'ils sont exécutés une fois que la condition est calculée par l'unité de calcul, ou par une unité de branchement spécialisée. [[File:Gestion des branchements sur un pipeline.png|centre|vignette|upright=2.0|Gestion des branchements conditionnels sur un pipeline.]] Sur le schéma précédent, les branchements inconditionnels ne sont pas montrés. Pour cela, il faudrait rajouter une connexion du décodeur vers le multiplexeur de branchement. De plus, il faudrait aussi rajouter de quoi retarder l'exécution du branchement seulement une fois que l'adresse est connue. Par exemple, elle est connue un cycle d'horloge plus si l'adresse est lue depuis les registres, comparé à un branchement direct. ==Les branchements et les exceptions imprécises/précises== Un branchement est censé altérer le ''program counter'' immédiatement, en un cycle d'horloge. Mais sur un pipeline, Le branchement fait bien reprendre le processeur au bon endroit, mais avec du retard. La raison est qu'un branchement met plusieurs cycles pour s'exécuter. Il faut plusieurs cycles pour déterminer quelle est l'adresse de destination, temps qui dépend de là où est lue l'adresse. Et on sait si le branchement est pris seulement au niveau du décodeur, voire au niveau de l'unité de calcul. Le branchement doit traverser plusieurs étages avant qu'on connaisse son résultat. Il y a bien 3 à 4 cycles avant cela. Et pendant ce temps de trajet, des instructions seront chargées dans le pipeline, potentiellement à tort. Si le branchement n'est pas pris, ce n'est pas grave : les instructions n'ont pas été chargées à tort. Mais dans le cas contraire, les instructions n'auraient pas dû rentrer dans le pipeline. Le problème est similaire à celui observé avec les exceptions précises/imprécises. La différence est que les branchements sont des instructions machines, pas les exceptions matérielles. Mais le problème des instructions chargées à tort est le même dans les grandes lignes. Une différence est que les branchements sont résolus plus ou moins au même étage, alors que les exceptions peuvent survenir dans tout le pipeline. Une autre différence, bien plus importante, est que les branchements non-pris ne chargent pas d'instructions à tort et qu'il faut faire la différence entre branchement pris et non-pris. Dans la suite, nous parlerons d'instructions fautives pour parler des instructions chargées à tort. Pour corriger ce problème, il existe une solution logicielle. Le compilateur fait suivre les branchements par des instructions qui ne font rien, des NOP (No OPeration) : c'est ce qu'on appelle un '''délai de branchement'''. L'idée est que toutes les instructions chargées à tort sont des NOPs, qui ne font rien. Mais le nombre de NOP à ajouter dépend du pipeline du processeur, ce qui peut poser des problèmes de compatibilité. Mais d'autres solutions, matérielles cette fois, sont utilisées de nos jours. ===L'annulation des instructions au décodage=== Les branchements inconditionnels sont dans un cas plus favorable : ils sont identifiés dans l'unité de décodage et sont toujours pris. D'autres branchements sont dans ce cas : les appels de fonctions, les interruptions logicielles. Avec eux, le décodeur annule les instructions fautives, il les remplace par des instructions NOP. L'étage de décodage sait que les instructions suivant un branchement inconditionnel ont été chargées à tort. Précisément N instructions, avec N le nombre d'étages entre le chargement et le décodage (inclus). Les N instructions suivantes sont tout simplement annulés, elles sont remplacées par des NOPs. L'implémentation demande juste un simple compteur et quelques circuits annexes. Cependant, la technique ne marche pas du tout pour les branchements conditionnels. En effet, on ne sait pas s'ils sont pris ou non à l'étage de décodage. Du moins pas avec un pipeline normal. Mais certains processeurs, basés sur le pipeline RISC classique, calculaient les branchements pendant l'étape de décodage, dans une ALU spécialisée qui travaille en parallèle de l'unité de décodage. Le défaut de cette technique est que l'ALU en question doit lire les registres. Pour rappel, sur ce pipeline, l'étape de décodage effectue la lecture des opérandes dans les registres, en parallèle de l'unité de décodage. Mais ce qu'on n'a pas dit dans le chapitre précédent, c'est qu'elle effectue aussi le calcul des branchements dans une mini-ALU séparée ! Ce faisant, le résultat du branchement est connu dès la fin de l'étape de décodage. ===L'usage du système d'exceptions précises pour les branchements conditionnels=== La solution gère le problème en empêchant les instructions chargées à tort d'enregistrer leurs résultats, afin qu'elles n'aient pas le moindre effet sur l'état du processeur. Le hardware pour les exceptions précises, décrit quelques paragraphes avant, est réutilisé pour cela. Les branchements conditionnels peuvent être pris ou non-pris et on doit tenir compte de ces deux cas. Si le branchement n'est pas pris, les instructions n'ont pas été chargées à tort, elles peuvent enregistrer leur résultat dans les registres. Par contre, ce n'est pas le cas pour les branchements pris, les mécanismes d'exceptions précise doivent alors d'activer. Pour cela, la meilleure solution est que l'unité de calcul génère un indicateur d'exception si le branchement n'est pas pris. L'ALU effectue la comparaison et génère ou non l'indicateur d'exception adéquat suivant le résultat de celle-ci. L'idée est d'utiliser un indicateur d'exception particulier, qui précise qu'un branchement a été pris, signe que des instructions ont été chargées à tort. L'indicateur est propagé dans le pipeline, jusqu'à atteindre l'étage d'enregistrement dans les registres. Cet étage décide s'il faut autoriser ou non les écritures qu'il recoit, pour annuler les instructions chargées à tort. Le ''program counter'' est corrigé immédiatement, simplement en exécutant le branchement. Reste à savoir qui génère cet indicateur d'exception de branchement pris. Diverses optimisations visent à éliminer les instructions chargées à tort, à faire en sorte que des instructions utiles soient chargées. Le chapitre suivant va détailler ces optimisations dans le détail, qui sont regroupées sous le terme de prédiction de branchement. Elles ne fonctionnent pas pour les exceptions précises, seulement les branchements. ===La prédiction de branchement=== Les techniques précédentes ont pour défaut que de nombreux cycles d'horloge sont gâchés à cause des instructions fautives. Pour éviter ce gâchis, les concepteurs de processeurs ont inventé l'''exécution spéculative de branchement'', qui consiste à deviner l'adresse de destination du branchement et charger les bonnes instructions dès le départ. Le but est de ne pas charger d'instruction à tort, en prédisant quelles seront les bonnes instructions à charger. Et cela demande de résoudre trois problèmes : * reconnaître les branchements ; * savoir si un branchement sera exécuté ou non : c'est la '''prédiction de branchement''' ; * dans le cas où un branchement serait exécuté, il faut aussi savoir quelle est l'adresse de destination : c'est la '''prédiction de l'adresse de destination''' d'un branchement, aussi appelée ''branch target prediction''. Pour résoudre le second problème, le processeur contient un circuit qui déterminer si le branchement est pris (on doit brancher vers l'adresse de destination) ou non pris (on poursuit l’exécution du programme immédiatement après le branchement) : c'est l''''unité de prédiction de branchement'''. La prédiction de direction de branchement est elle aussi déléguée à un circuit spécialisé : l’'''unité de prédiction de direction de branchement'''. C'est l'unité de prédiction de branchement qui autorise l'unité de prédiction de destination de branchement à modifier le ''program counter''. Dans certains processeurs, les deux unités sont regroupées dans le même circuit. [[File:Relation entre prédiction de branchement et de direction de branchement.png|centre|vignette|upright=2|Relation entre prédiction de branchement et de direction de branchement.]] : Au lieu de parler d'unité de prédiction de branchement, j'utiliserais parfois le terme '''prédicteur''', sous-entendu ''prédicteur de branchement''. Avant de poursuivre, faisons une remarque très importante. J'ai parlé d'unité de prédiction de branchement, comme s'il n'y en avait qu'une seule. Mais en réalité, n'en avoir qu'une seule est l'exception. La règle est d'avoir plusieurs unités de branchements spécialisées. Un processeur moderne utilise plusieurs prédicteurs séparés, chacun prédisant un type de branchement bien précis. Il y a pas exemple un prédicteur spécialisé pour les boucles, un autre pour les instructions de retour de fonctions, un autre pour les branchements directs, un autre pour les branchements indirects. Les processeurs modernes utilisent une prédiction de branchement à deux niveaux. Un premier prédicteur fournit des résultats rapides et peu précis, un second a des résultats plus précis après quelques cycles d'horloge. Le prédicteur rapide envoit l'adresse prédite au cache d'instruction, pour charger les instructions prédites et mettre à jour le ''program counter''. Le prédicteur lent envoient leurs résultats au décodeur d'instruction, histoire d'annuler des branchements considérés à tort comme pris/non-pris. Il y a donc des prédicteurs rapides, dont le résultat est corrigé par des prédicteurs plus lents. La seconde unité a le dernier mot, elle corrige ou annule les prédictions de la première. Ce qui lui vaut le nom, en anglais, d'''overiding predictor''. La correction se fait simplement en corrigeant le ''program counter'' et en forçant le décodeur à émettre des NOPs pendant quelques cycles, le temps d'éliminer les instructions chargées à tort. Ce détail aura rapidement son importance. ==Les erreurs de prédiction de branchement== Le processeur peut parfaitement se tromper en faisant ses prédictions, ce qui charge des instructions par erreur dans le pipeline. Dans ce cas, on parle d''''erreur de prédiction'''. Les erreurs de prédiction sont corrigées par le système d'exception précises, ou un équivalent. En clair, les instructions chargées à tort se propagent jusqu'à la sortie du pipeline, où leurs résultats sont alors annulés. N'importe quelle technique de gestion des exceptions précise fait le travail, mais les processeurs modernes utilisent un tampon de réordonnancement (''reorder buffer'') qu'on détaillera dans quelques chapitres. Détecter les erreurs de prédiction demande d'ajouter un circuit dans le processeur : l’''unité de vérification de branchement'' (''branch verification unit''). Elle génère un indicateur d'exception, qui est géré par le système d'exception précise. Pour générer l'indicateur, elle compare l'adresse de destination prédite et celle calculée en exécutant le branchement. Pour cela, l'adresse prédite doit être propagée dans le pipeline jusqu’à ce que l'adresse de destination du branchement soit calculée. [[File:Unité de vérification de branchement.png|centre|vignette|upright=2|Unité de vérification de branchement]] ===La pénalité de mauvaise prédiction=== Le temps pour vider le pipeline des instructions fautives dépend du pipeline. La dernière instruction à être chargée dans le pipeline le sera en même temps qu'on détecte l'erreur de prédiction. Il faudra attendre que cette instruction quitte le pipeline, et donc qu'elle traverse tous les étages. Il y a donc un temps d'attente pour collecter les résultats de ces instructions et la décision de ne pas enregistrer leurs résultats dans les registres Le nombre d'instructions chargées à tort dépend de où est détectée l'erreur de prédiction. Plus le résultat du branchement est connu tard, plus le nombre d'instructions chargées à tort sera grand, et plus le nombre de cycles d'horloge gâchés le sera aussi. Le nombre de cycles gâchés s'appelle la '''pénalité de mauvaise prédiction'''. Elle correspond précisément au nombre de cycles/étages entre le premier étage du pipeline, et l'étage où le branchement est résolu (on connait l'adresse à laquelle brancher). Plus celui-ci est éloigné du début du pipeline, plus la pénalité est importante. [[File:MIT 6.823 Computer System Architecture, Fall 2005 - P-3 vs. P-4 Pipelines - 4473425702.jpg|centre|vignette|upright=2.5|Comparaison de la pénalité de mauvaise prédiction entre le Pentium 3 et le Pentium 4 d'Intel.]] Elle est généralement d'autant plus longue que le pipeline lui-même est long. Les concepteurs de processeurs font donc face à un compromis : un pipeline long permet d'exécuter plus d'instructions en parallèle, mais cela augmente aussi la pénalité de mauvaise prédiction. Un pipeline de 10-15 étapes est un bon compromis. Les pipelines plus longs ont besoin d'une prédiction de branchement élaborée pour fonctionner correctement. Plus la prédiction de branchement est performante, plus le pipeline peut être long. Les pénalités de mauvaise prédiction seront plus importantes, mais les mauvaises prédictions seront plus rares, ce qui compense complétement. ===La ''minimal control dependency''=== En utilisant une technique du nom de ''minimal control dependency'', seules les instructions qui dépendent du résultat du branchement sont supprimées du pipeline en cas de mauvaise prédiction, les autres n'étant pas annulées. Sans ''minimal control dependency'', toutes les instructions qui suivent un branchement dans notre pipeline sont annulées. Pourtant, certaines d'entre elles pourraient être utiles. Prenons un exemple : supposons que l'on dispose d'un processeur de 31 étages (un Pentium 4 par exemple). Supposons que l'adresse du branchement est connue au 9éme étage. On fait face à un branchement qui envoie le processeur seulement 6 instructions plus loin. Si toutes les instructions qui suivent le branchement sont supprimées, les instructions en rouge sont celles qui sont chargées incorrectement. On remarque pourtant que certaines instructions chargées sont potentiellement correctes : celles qui suivent le point d'arrivée du branchement. Elles ne le sont pas forcément : il se peut qu'elles aient des dépendances avec les instructions supprimées. Mais si elles n'en ont pas, alors ces instructions auraient dûes être exécutées. Il serait donc plus efficace de les laisser enregistrer leurs résultats au lieu de les ré-exécuter à l’identique un peu plus tard. Ce genre de choses est possible sur les processeurs qui implémentent une technique du nom de ''Minimal Control Dependancy''. En gros, cette technique fait en sorte que seules les instructions qui dépendent du résultat du branchement soient supprimées du pipeline en cas de mauvaise prédiction. [[File:Minimal cntrol dependency.png|centre|vignette|upright=2|Minimal control dependency]] ==La reconnaissance des branchements== Pour prédire des branchements, le processeur doit faire la différence entre branchements et autres instructions, dès l'étage de chargement. Or, un processeur « normal », sans prédiction de branchement, ne peut faire cette différence qu'à l'étage de décodage, et pas avant. Les chercheurs ont donc dû trouver une solution. La première solution se base sur les techniques de prédécodage vues dans le chapitre sur le cache. Pour rappel, ce prédécodage consiste à décoder partiellement les instructions lors de leur chargement dans le cache d'instructions et à mémoriser des informations utiles dans la ligne de cache. Dans le cas des branchements, les circuits de prédécodage peuvent identifier les branchements et mémoriser cette information dans la ligne de cache. Une autre solution mémorise les branchements déjà rencontrés, dans un cache dédié. Ce cache mémorise l'adresse (le ''program counter'') des branchements déjà rencontrés : il s'appelle le '''tampon d’adresse de branchement''' (''branch adress buffer''). Il est intégré à l'unité de prédiction de branchement, mais est alimenté par le décodeur d'instruction. Reconnaitre un branchement demande l'implication du décodeur d'instruction, qui sait si l'instruction qu'il vient de décoder est un branchement ou non. Il peut même savoir si le branchement est conditionnel, inconditionnel, un appel de retour de fonction, etc. Lorsque le décodeur d'instruction reconnait un branchement, il ajoute ce branchement dans le cache Le tapon d'adresse de branchement contient une adresse mémoire par branchement, et éventuellement d'autres informations. Et pour comprendre quelle adresse est mémorisée, il faut faire attention à un détail. Les explications qui vont suivre vont faire intervenir deux adresses. * La première est l''''adresse de destination''' du branchement, à savoir l'adresse à laquelle le processeur doit reprendre son exécution si le branchement est pris. * L'autre adresse est l''''adresse du branchement''' lui-même. Elle correspond à sa position en mémoire RAM. L'adresse du branchement est la valeur du ''program counter'' quand le branchement est chargé dans le cache, alors que l'adresse de destination est celle du ''program Counter'' une fois le branchement exécuté. Il faudra faire bien attention à ne pas confondre les deux adresses dans ce qui suit. L'adresse du branchement est celle qui est utilisée pour la reconnaissance du branchement. Le tampon d'adresse de branchement mémorise, pour chaque branchement, son adresse de branchement (d'où son nom). À chaque cycle d'horloge, l'unité de chargement envoie le ''program counter'' en entrée du tampon d’adresse de branchement. Un succès dans ce cache indique qu'un branchement déjà rencontré est ré-executé, on peut utiliser la prédiction de branchement. Dans le cas contraire, la prédiction de branchement n'est pas utilisée, et l'instruction est chargée normalement. ==La prédiction de l'adresse de destination== La '''prédiction de l'adresse de destination d'un branchement''' détermine l'adresse de destination d'un branchement. Rappelons qu'il existe plusieurs modes d'adressage pour les branchements et que chacun d'entre eux précise l'adresse de destination à sa manière. Suivant le mode d'adressage, l'adresse de destination est soit dans l'instruction elle-même (adressage direct), soit calculée à l’exécution en additionnant un ''offset'' au ''program counter'' (adressage relatif), soit dans un registre du processeur (branchement indirect), soit précisée de manière implicite (retour de fonction, adresse au sommet de la pile). : Histoire de simplifier la terminologie, je parlerais parfois de '''prédiction de destination''' pour parler de la ''prédiction de l'adresse de destination d'un branchement''. Pour rappel, les branchements se classent en trois types : * les branchements directs pour lequel l'adresse de destination est toujours la même ; * les branchements indirects où l'adresse de destination est dans un registre et peut changer ; * les instructions de retour de fonction. Les branchements directs sont facilement prévisibles, vu que l'adresse vers laquelle il faut brancher est toujours la même. La prédiction des branchements directs et relatifs se fait globalement de la même manière, ce qui fait que nous ferons la confusion dans ce qui suit. Pour les instructions de retour de fonction, une prédiction parfaite est possible. Et c'est ce qui explique qu'elles sont traitées à part, par une unité de branchement dédiée. Pour les branchements indirects, vu que cette adresse change, la prédire celle-ci est particulièrement compliqué (quand c'est possible). Les branchements indirects sont eux aussi traités par une unité de prédiction dédiée rien que pour eux. ===La prédiction de destination pour les branchements directs=== Lorsqu'un branchement est exécuté, on mémoriser l'adresse de destination et la réutiliser lors d'exécutions ultérieures du branchement. Cette technique marche à la perfection pour les branchements directs, pour lesquels cette adresse est toujours la même, mais donne des résultats mitigés pour les branchements indirects. Pour mémoriser l'adresse de destination, on utilise un cache qui mémorise les correspondances entre l'adresse du branchement et l'adresse de destination. Ce cache est appelé le '''''branch target buffer''''' en anglais, qui sera abrévié en BTB dans ce qui suit. Le BTB est une amélioration du tampon d'adresse de branchement vu plus haut, auquel on aurait ajouté les adresses de destination des branchements. Le BTB est utilisé comme suit : on envoie en entrée l'adresse du branchement, le BTB répond au cycle suivant en précisant : s’il reconnaît l'adresse d'entrée, et quelle est l'adresse de destination si c'est le cas. Le BTB peut être un cache totalement associatif, associatif par voie, ou directement adressé, mais ces derniers sont les plus fréquents. Les BTB sont généralement des caches de type directement adressés, où seuls les bits de poids faible de l'adresse du branchement adressent le cache, le reste de l'adresse est tout simplement ignoré. Il existe aussi des BTB qui sont construits comme les caches associatifs à plusieurs voies, mais ceux-ci impliquent généralement la présence de ''tags'', ce qui fait qu'ils sont un peu moins fréquents. [[File:Branch target buffer directement adressé.png|centre|vignette|upright=2|Branch target buffer directement adressé.]] Comme pour tous les caches, un accès au BTB peut entraîner un défaut de cache, c’est-à-dire qu'un branchement censé être dans le BTB n'y est pas. Comme pour les autres caches, les défauts de cache peuvent se classer en trois types : les défauts de cache à froid (''cold miss'') causés par la première exécution d'un branchement, les défauts liés à la capacité du BTB/cache, et les défauts par conflit d'accès au cache. Les défauts liés à la capacité du BTB sont les plus simples à comprendre. La capacité limitée du BTB fait que d'anciens branchements sont éliminées pour laisser la place à de nouveaux. En conséquence, ces branchements peuvent donner des erreurs de prédiction si leur correspondance a été éliminée du cache. On peut réduire des défauts en augmentant la taille du BTB. Les défauts liés aux conflits d'accès au BTB sont eux beaucoup plus intéressants, car la conception du BTB est assez spéciale dans la manière dont sont gérés ce genre de défauts. Le BTB est un cache partiellement associatif, ce qui fait que des défauts de cache par conflit d'accès peuvent avoir lieu. Pour rappel, les défauts par conflit d'accès ont lieu quand deux adresses mémoires se voient attribuer la même ligne de cache. Pour un BTB, cela correspond au cas où deux branchements se voient attribuer la même entrée dans le BTB, ce qui porte le nom d’''aliasing''. Ne pas détecter ce genre de situation sur un cache normal entraînerait des problèmes : la donnée lue/écrite ne serait pas forcément la bonne. Les caches normaux utilisent un système de tags pour éviter ce problème et on s'attendrait à ce que les BTB fassent de même. Mais pour un BTB, l'absence de ''tags'' n'est pas un problème : la seule conséquence est une augmentation du taux de mauvaises prédictions, dont les conséquences en termes de performance peuvent être facilement compensées. Les BTB peuvent donc se passer de tags, ce qui a de nombreux avantages : le circuit est plus rapide, prend moins de portes logiques, consomme moins d'énergie, etc. Ces économies de portes logiques et de performances peuvent être utilisées pour augmenter la taille du BTB, ce qui compense, voire surcompense les mauvaises prédictions induites par l’''aliasing''. Mais ce n'est pas systématique : d'autres BTBs utilisent des ''tags'' pour améliorer le taux de prédiction. Nous ferons donc la différence entre '''BTB tagués''' et '''BTB non-tagués'''. Des processeurs se passent de BTB. À la place, ils mémorisent les correspondances entre branchement et adresse de destination dans les bits de contrôle du cache d'instructions. Mais nous verrons cela en détail dans le chapitre suivant. Plus haut, j'ai dit qu'un processeur moderne utilisait à la fois un prédicteurs rapide et imprécis, avec un prédicteur lent mais précis. Le prédicteur lent a le dernier mot, il corrige ou annule les prédictions du prédicteur rapide. Ce qui lui vaut le nom, en anglais, d'''overiding predictor''. La correction se fait simplement en corrigeant le ''program counter'' et en forçant le décodeur à émettre des NOPs pendant quelques cycles, le temps d'éliminer les instructions chargées à tort. [[File:Double BTB sur les CPU modernes.png|centre|vignette|upright=2|Double BTB sur les CPU modernes.]] Les deux unités de prédiction utilisent des BTB séparés, de taille différente, au moins deux. Vu que les BTB sont des caches, on les appelle des '''BTB de niveau L1 et L2'''. Par exemple, les processeurs Bulldozer d'AMD disposent de deux BTBs : un BTB L1 de 512 entrées, et un BTB L2 de 5120 entrées. Le BTB de niveau L2 est souvent un cache de victime, qui mémorise les branchements retirés de la BTB de niveau L1. La BTB pour les branchements indirects vient en plus de ces deux BTBs, elle complète souvent la BTB de niveau L2. Le ''return stack predictor'' vient en plus des BTB L1 et L2, mais sa petite taille et sa rapidité font qu'il complète l'unité/BTB de niveau L1. Quelques processeurs ont trois niveaux de BTB, avec un niveau L0, L1 et L2. La BTB L0 aliment le cache d'instruction, alors que la L1 et la L2 préviennent les décodeurs d'instruction. La différence entre la L1 et la L2 est que la L2 met plus de temps à prévenir les décodeurs. Les branchements peuvent donc être annulés/forcés à deux étages de décodage différents. Pour donner quelques exemples, les processeurs Zen d'AMD disposent de plusieurs BTBs, avec des niveaux L0, L1 et L2. Le tableau ci-dessous vous donne la taille et la latence de chaque niveau de BTB. La BTB de niveau L0 alimente le cache d'instruction, la L1 permet d'annuler les instructions au premier cycle de décodage, la BTB L2 annule les instructions vers le milieu/fin du décodage. {|class="wikitable" |- ! rowspan="3" | Zen 2 | 16 || 0 |- | 512 || 1 |- | 7168 || 4 |- ! rowspan="3" | Zen 3 | 16 || 0 |- | 1024 || 1 |- | 6656 + 1536 (branchements indirects)|| 4 |} ===La prédiction de destination pour les branchements indirects=== Un BTB classique peut fonctionner pour les branchements indirects. Son seul défaut est qu'il mémorisera la dernière adresse de destination prise par le branchement. Et cela peut fonctionner pour les branchements indirects fortement biaisés, qui ont presque toujours la même adresse de destination. Mais la majorité des branchements indirects change d'adresse de destination régulièrement. Tous les processeurs commerciaux datant d'avant le Pentium M utilisaient un BTB normal pour prédire les branchements indirects. Les processeurs qui les ont suivi sont capables de prédire l'adresse de destination d'un branchement indirect. , grâce à une '''unité de prédiction des branchements indirects''', séparée de l'unité de prédiction de branchement normale. Elle utilise un BTB amélioré, qui mémorise plusieurs adresses de destination pour un seul branchement, en compagnie d'informations pour prédire laquelle est la bonne. Il est possible d'utiliser un BTB unique, pour tous types de branchements, appelé un '''BTB unifié'''. Un BTB unifié a plusieurs adresse de destination par entrée du BTB. Mais une seule est utilisée pour les branchements directs. Vu que les branchements directs sont majoritaires, cela fait beaucoup d'entrées inutilisées. En conséquence, elle est tout sauf optimale, et n'est presque jamais utilisée en pratique. {|class="wikitable" |+ Branch Target Buffer unifié |- ! Adresse du branchement !! Informations de prédiction !! Adresse de destination !! Seconde adresse de destination |- | 0x54462146 || 11101011 || 0x52495674 || 0x24987461 |- | 0x54142446 || 11101101 || 0x15646956 || x0x4158746 |- | 0x25456542 || 10011101 || 0x52495674 || 0x24157461 |- | 0x15455855 || 11010101 || 0x52485754 || 0x24024511 |- | ... || ... || ... || ... |- | ... || ... || ... || ... |- | 0x54462146 || 1001101 || 0x52495674 || 0x24987461 |} Une seconde solution utilise un BTB séparé, distinct du BTB pour les branchements directs. En séparant les deux, on a un BTB simple qui ne mémorise qu'une adresse de destination par branchement, et un BTB pour branchements indirects avec plusieurs adresses de destination par branchement. [[File:BTB avec prédiction de branchements indirects.png|centre|vignette|upright=2.5|BTB avec prédiction de branchements indirects.]] L'idée est que l'on économise des circuits à nombre d'entrées égales. Par exemple, comparons ce que cela donne avec 64 entrées. D'un côté, on a un BTB à 64 entrées, capable de gérer deux adresse de destination par branchement. En pratique, la majorité des branchements sont des branchements directs, qui n'utiliseraient qu'une seule case mémoire. Les circuits du BTB seraient donc sous-utilisés. De l'autre, on a un BTB à 48 entrées pour branchements directs, et un second BTB avec 16 entrées, capable de mémoriser deux adresses par branchements. Le premier BTB utilise moins de circuits, et est utilisé à pleine capacité, il ne gaspille pas de circuits pour mémoriser des adresses de destination vides. Par contre, on perd un peu en flexibilité. L'organisation précédente marche bien si 1/4 des branchements rencontrés sont des branchements indirects. Mais si le ratio est différent, la performance est légèrement sous-optimale. Attention, cela ne veut pas dire qu'il y aura des entrées vides dans un BTB, non. Simplement, le premier BTB risque de manquer de place pour les branchements directs récents, alors que les branchements indirects seront eux bien prédits, même les anciens. À l'opposé, un BTB unique permet de mémoriser les 64 derniers branchements, peu importe qu'ils soient indirects ou non. En clair : un BTB unique est plus flexible, ce qui donne un gain de performance dans certaines situations. Cependant, cet avantage théorique ne tient pas compte de l'économie en circuits, qui peut être utilisée pour faire grossir le BTB pour branchements directs. Par exemple, à budget à transistor équivalent, on a le choix entre BTB à 64 entrées uniques, et un BTB pour branchements directs de 80 entrées avec un BTB indirect de 16 entrées. Le fait qu'un BTB soit plus gros permet des gains de performances qui compensent la perte de flexibilité. On peut ainsi avoir le meilleur des deux monde, à savoir une économie de circuits et les gains en performance qui en découlent, malgré une petite perte de flexibilité. Une troisième solution utilise un BTB normal, mais réserve plusieurs entrées pour un branchement indirect. Par exemple, un branchement indirect qui a trois adresses de destination prendra trois entrées : une par adresse de destination. Mais quelques difficultés surviennent alors. Comment placer trois copies d'un même branchement, alors que ces trois copies ont le même ''program counter'' ? Et que faire pour savoir quelle copie sera prise ? Que faire si l'unité de prédiction de branchement prédit les trois copies comme prises ? La technique du '''''Program Counter'' virtuel''' (''Virtual Program Counter'') résoud ces problèmes d'une manière assez élégante. L'idée est la même que précédemment, à savoir qu'il y a une copie du branchement par adresse de destination, dans le BTB. Mais ces copies n'ont pas exactement le même ''Program counter''. Chaque copie se voit attribuer un ''Program Counter'' virtuel. Et comprendre pourquoi demande de comprendre l'idée sous-jacente. La technique a été inspirée par une optimisation des compilateurs, qui transforme un branchement indirects en une séquence de branchements conditionnels. Par exemple, un branchement indirects qui peut brancher vers les adresses A, B et C est transformé en trois branchements conditionnels : un qui branche vers A, un autre qui branche vers B et un autre vers C. Elle ne marche pas pour tous les branchements indirects, elle demande des circonstances particulières pour fonctionner. Mais l'idée est adaptée pour le ''design'' de l'unité de prédiction de branchement. L'idée est qu'un branchement indirect est déroulé en plusieurs branchements dans le BTB. Les branchements sont traités en séquence : l'unité de prédiction prédit si le premier branchement est pris ou non. S'il est pris, son adresse de destination est envoyée au cache d'instruction. S'il n'est pas pris, l'unité de prédiction tester la seconde copie du branchement, et rebelote. Il teste toutes les copies, une par une, et s’arrête quand il tombe sur un branchement pris. Si aucune copie n'est prise, alors le branchement est prédit comme non-pris. Première remarque : il s'agit d'un processus itératif, où on test un branchement à la fois. Et oui, c'est une prédiction par cycle d'horloge. Prédire un branchement indirect peut donc demander plusieurs cycles d'horloge. Mais ce n'est pas un problème, car le prédicteur peut servir d'''overriding predictor'', d'unité de prédiction lente mais précise. La prédiction peut être utilisée par l'unité de décodage, pour annuler les instructions chargées à tord. Deuxième remarque : comment passer d'un branchement à l'autre ? La première copie a un ''program counter'' normal, qui correspond à l'adresse du branchement. La seconde a un ''program counter'' qui est calculé à partir de cette première adresse, la troisième copie a une adresse calculée à partir de la seconde, etc. Concrètement, n'importe quelle fonction un tant soit peu simple suffit, tant qu'elle est déterministe. L'article qui a proposé cette techniques (''Virtual Program Counter (VPC) Prediction : Very Low Cost Indirect Branch Prediction Using Conditional Branch Prediction Hardware'') se contenait de faire un XOR entre l'adresse précédente et une constante, avec une constante différente par itération. Troisième remarque : l'algorithme demande de faire une parenthèse dans le fonctionnement normal du BTB. Quand un branchement indirect est détecté, il lance une succession de prédiction pour prédire un branchement. L'incrémentation du ''program counter'' normale cesse pendant ce processus. Et cela ne doit être fait que quand un branchement indirect est détecté. Pour cela, le BTB mémorise le type de chaque branchement, sans l'entrée du BTBT : est-ce qu'il est conditionnel, inconditionnel, mais aussi direct ou indirect. Et le type est accesible en sortie du BTB, sur une sortie de quelques bit. Quand l'unité de prédiction remarque qu'un branchement indirect vient de sortir du BTB, alors elle lance le processus. [[File:Virtual program counter.png|centre|vignette|upright=2.5|Virtual program counter]] L'avantage de cette technique est qu'elle s’implémente facilement, son cout en transistors est faible. Elle demande juste d'ajouter quelques circuits autour d'un BTB classique. Elle utilise l'unité de prédiction classique, pas besoin d'une unité de prédiction séparée. Vu qu'il y a un seul BTB, on n'a pas les désavantages d'un BTB séparé pour les branchements indirects. Les entrées du BTB sont réparties entre branchements directs et indirects de manière optimale. Niveau performance, elle est un peu moins bonne que les unités de prédiction ITTAGE qu'on détaillera dans la suite du chapitre. Mais elle est suffisante pour être utilisée sur certains processeurs commerciaux. ===La prédiction de l'adresse de retour d'une fonction=== Presque tous les processeurs conçus après les années 2000 peuvent prévoir l'adresse à laquelle il faudra reprendre lorsqu'une fonction/sous-programme a fini de s’exécuter. Ils font de la '''prédiction de retour de fonction'''. Pour cela, ils possèdent pour une unité de prédiction de branchement spécialisée, appelée le ''return stack predictor'', ou '''''pile de prédiction de retour de fonction'''''. Le terme ''return stack predictor'' étant plus court, nous l'utiliserons dans la suite du cours. Le ''return stack predictor'' est capable de reconnaitre les instructions de retour de fonction, et de prédire l'adresse de retour. Pour comprendre comment elle fait, rappelez-vous le chapitre sur la pile d'appel. Dans ce chapitre, j'avais introduit le concept de ''pile d'adresse de retour'', à savoir une pile d'appel très simplifiée, qui ne contient que les adresses de retour des fonctions en cours d'exécution. Le ''return stack predictor'' est essentiellement composé d'une telle pile d'adresse de retour, avec des circuits pour empiler et dépiler les adresses de retour. Le ''return stack predictor'' doit reconstruire une pile d'adresses de retour, à partir du programme exécuté. La pile d'adresse est mémorisée dans le ''return stack predictor'', elle est totalement séparée de la pile d'appel normale. Le programme exécuté continue d'utiliser la même pile d'appel qu'avant, ce qui fait que les adresses de retour sont dispersées dans la pile d'appel, parfois dans des registres spéciaux du processeur. Mais cela ne pose pas de problèmes pour le processeur, qui reconstruit la pile d'adresse de retour avec l'aide du décodeur. La reconstruction se fait à partir des instructions d'appel et de retour de fonction. Une instruction d'appel de fonction empile une adresse de retour, une instruction de retour de fonction la dépile. Lorsque le décodeur d'instruction reconnait une instruction d'appel de fonction, il extrait l'adresse de retour et l'envoie au ''return stack predictor''. L'adresse de retour est alors empilée, ce qui fait qu'elle se retrouve au sommet de la pile d'adresse de retour. Dépiler une adresse de retour revient à prédire un branchement. Lorsque le ''return stack predictor'' détecte une instruction de retour de fonction, il dépile l'adresse au sommet de la pile. L'adresse est alors envoyée du cache d'instruction, pour l'ire l'instruction adéquate, et le ''program counter'' est mis à jour avec cette adresse. Toute la difficulté revient à détecter les instructions de retour de fonction, sans quoi on ne sait pas quand dépiler l'adresse. La documentation là-dessus n'est pas très fournie, il est difficile de savoir ce qui est fait dans les processeurs modernes. Mais on peut faire quelques suppositions. La première possibilité est l'usage du ''prédécodage'', une technique qui décode partiellement les instructions lors de leur chargement dans le cache d'instruction. Elle sera vue dans le chapitre suivant, mais parlons-en rapidement. Le prédécodage ajoute quelques bits au début de chaque instruction pour préciser si c'est un branchement conditionnel, inconditionnel, un retour de fonction. On peut ainsi savoir rapidement quand dépiler : dès qu'une instruction est lue dans le cache d'instruction, le ''return stack predictor'' vérifie les bits ajoutés et agit en fonction. La seconde possibilité est que le BTB reconnait l'instruction de retour de fonction. Pour chaque branchement, il mémorise non seulement son adresse de retour, mais aussi son type. Par type, on veut dire : si c'est un branchement conditionnel, inconditionnel, un retour de fonction. Les retours de fonction sont donc reconnus à condition qu'ils aient été exécutés auparavant. Il est aussi possible d'avoir un BTB spécialisé dans les retours de fonction, qui est alimenté par les décodeurs. Dès que le décodeur reconnait une instruction de retour de fonction, il ajoute son ''program counter'' dans ce BTB spécialisé. Une dernière possibilité est que le ''return stack predictor'' agit une fois l'instruction partiellement décodée. Le décodeur d'instruction reconnait les instructions de retour de fonction rapidement, en un cycle, et consulte alors le ''return stack predictor''. L'adresse est dépilée, et le décodeur sait où brancher. Il n'a pas besoin de devoir lire l'adresse de retour en mémoire, il la lit depuis le ''return stack predictor'', directement. La prédiction se fait donc assez tard dans le pipeline, quelques instructions ont été chargées à tort. Mais le décodeur peut les annuler, comme il le ferait avec un branchement inconditionnel mal prédit. Le ''return stack predictor'' se base sur les appels et retour de fonctions. Sur un processeur sans prédiction de branchement, tout appel de fonction est couplé à un retour de fonction. Mais avec prédiction de branchement, il se peut que ce ne soit pas le cas. Il arrive qu'un appel de fonction soit placé après un branchement pris/non-pris. S'il est exécuté à tort, l'appel/retour de fonction sera exécuté à tort. Et il peut modifier le ''return stack predictor''. Il y a donc corruption du ''return stack predictor'' par des appels/retour spéculatifs. Le ''return stack predictor'' utilise des mécanismes pour réparer sa pile d'adresse de retour. ==La prédiction de branchement locale== La prédiction de branchement tente de prédire si un branchement sera pris ou non-pris, et décide quelle adresse envoyer au cache en fonction du résultat. Si on prédit qu'un branchement est non pris, on laisse le ''program counter'' faire son travail. À l'inverse si le branchement est prédit comme étant pris, l'adresse de destination est envoyée au cache d'instruction et au ''program counter''. La prédiction de branchement assigne une probabilité qu'un soit branchement soit pris en fonction de ces informations : si la probabilité est de plus de 50%, le branchement est considéré comme pris. La prédiction de branchement se base avant tout sur des statistiques, c’est-à-dire qu'elle détermine la probabilité d’exécution d'un branchement en fonction d'informations assez diverses. La prédiction de branchement n'a d'intérêt que si les prédictions sont suffisamment fiables pour valoir le coup. Rappelons que la pénalité lors d'une mauvaise prédiction est importante, d'autant plus coûteuse que le pipeline est long. Il est généralement admis qu'il faut au minimum un taux de réussite proche de 90%, voire plus sur les processeurs modernes. Heureusement, la plupart des branchements sont des '''branchements biaisés''', c’est-à-dire qu'ils sont presque toujours pris ou presque toujours non-pris, sauf en de rares occasions. De tels branchements font que la prédiction des branchements est facile, bien qu'ils posent paradoxalement quelques problèmes, comme nous le verrons plus bas. Un autre point important est que les unités de prédiction de branchement doivent être très rapides. Idéalement, elles doivent fournir leur prédiction en un seul cycle d'horloge. Un seul cycle d'horloge est un temps très court, surtout sur les ordinateurs avec une fréquence élevée. Les techniques de prédiction dynamique ne peuvent donc pas utiliser des méthodes statistiques extraordinairement complexes. Cela va à l'encontre du fait que le taux de mauvaises prédictions doit être très faible, idéalement inférieur à 1% sur les processeurs modernes. Vous comprenez donc aisément que concevoir une unité de prédiction de branchement est un véritable défi d’ingénierie électronique qui requiert des prouesses technologiques sans précédent. Suivant la nature des informations utilisées, on peut distinguer plusieurs types de prédiction de branchement : locale, globale, dynamique, statique, etc. Nous allons d'abord voir les méthodes statiques avant de voir les méthodes dynamiques. La '''prédiction locale''' prédit chaque branchement indépendamment les uns des autres. Elle sépare bien les statistiques/moyennes pour chaque branchement. Et c'est autant un point fort qu'un point faible. En effet, elle n'exploite pas les corrélations entre branchements, à savoir le fait que l'exécution d'un branchement a tendance à déborder sur les suivants. Dans ce qui suit, nous allons voir les techniques de prédiction locales. ===Les ''branch hints''=== Dans son implémentation la plus explicite, la prédiction est inscrite dans le branchement lui-même. Quelques bits de l'opcode du branchement précisent si le branchement est majoritairement pris ou non pris. Ils permettent d'influencer les règles de prédiction de branchement et de passer outre les réglages par défaut. Ces bits sont appelés des '''suggestions de branchement''' (''branch hint''). Mais tous les processeurs ne gèrent pas cette fonctionnalité. Et de plus, cette solution marche assez mal. La raison est que le programmeur ou le compilateur doit déterminer si le branchement est souvent pris ou non-pris, mais qu'il n'a pas de moyen réellement fiable pour cela. Une solution possible est d’exécuter le programme sur un ensemble de données réalistes et d'analyser le comportement de chaque branchement, afin de déterminer les suggestions de branchement adéquates, mais c'est une solution lourde et peu pratique, qui a de bonnes chances de donner des résultats peu reproductibles d'une exécution à l'autre. ===La prédiction statique de branchement=== La '''prédiction statique''' prédit le résultat du branchement en fonction de caractéristiques fixes du branchement lui-même, comme son adresse, son mode d'adressage, l'adresse de destination, la position du branchement en mémoire, si le branchement est direct ou indirect, etc. Les informations en question sont connues une fois le branchement décodé, il n'y a pas besoin de mémoriser la moindre information supplémentaire. Une première implémentation, assez évidente, fait la différence entre les branchements inconditionnels toujours pris, et les branchements conditionnels au résultat variable. L'idée est de prédire les branchements inconditionnels comme toujours pris alors que les branchements conditionnels sont prédits comme non-pris (ce qui est une approximation). L'implémentation est relativement simple : on utilise un BTB qui ne mémorise que les branchements inconditionnels, et basta ! Les branchements conditionnels sont simplement ignorés, traités comme n'importe quelle autre instruction. Cette méthode est particulièrement inefficace pour les branchements de boucle, où la condition est toujours vraie, sauf en sortie de boucle ! Il a donc fallu affiner légèrement l'algorithme de prédiction statique. Une implémentation plus subtile fait la différence entre les branchements des boucles et les autres. Reste à identifier ceux-ci d'une manière ou d'une autre. Et un bon moyen est de regarder si le branchement revient en arrière ou au contraire saute une portion de code. Un programme s'exécute des adresses basses vers les adresses hautes, les instructions vont naturellement dans le sens croissant des adresses. Un branchement de boucle fait revenir en arrière, histoire de répéter un morceau de code, pas les autres branchements (du moins pas forcément). Et cela nous amène à faire la distinction entre les branchements conditionnels ascendants et descendants. Un '''branchement conditionnel ascendant''' est un branchement qui demande au processeur de reprendre plus loin dans la mémoire : l'adresse de destination est supérieure à l'adresse du branchement. Un branchement '''conditionnel descendant''' a une adresse de destination inférieure à l'adresse du branchement : le branchement demande au processeur de reprendre en arrière dans la mémoire, avant le branchement. Les branchements ascendants sont rarement pris (ils servent dans les conditions de type SI…ALORS), contrairement aux branchements descendants (qui servent à fabriquer des boucles). On peut ainsi modifier l’algorithme de prédiction statique comme suit : * les branchements inconditionnels sont toujours pris ; * les branchements descendants sont toujours pris ; * les branchements ascendants ne sont jamais pris. L'implémentation demande d'élargir le BTB. Le BTB n'a pas seulement à mémoriser l'adresse du branchement et son adresse de destination, mais aussi le type du branchement. En général, il se contente de deux bits, qui indiquent si le branchement est conditionnel, inconditionnel, ou un retour de fonction. Les retours de fonction sont traités à part, histoire de profiter du ''return stack predictor''. {|class="wikitable" |+ BTB avec prédiction de branchement statique évoluée |- ! Adresse du branchement !! Adresse de destination !! Type du branchement |- | 0x4165485 || 0x14657445541 | style="background: #F0F000" | Conditionnel |- | ... || ... | style="background: #F0F000" | Inconditionnel |- | ... || ... | style="background: #F0F000" | Conditionnel |- | ... || ... | style="background: #F0F000" | Conditionnel |- | ... || ... | style="background: #F0F000" | Retour de fonction |- | ... || ... | style="background: #F0F000" | Inconditionnel |- | ... || ... | style="background: #F0F000" | Inconditionnel |- | ... || ... | style="background: #F0F000" | Conditionnel |- | ... || ... || ... |} ===La prédiction avec des compteurs à saturation=== Les méthodes de prédiction de branchement statique sont intéressantes, mais elles montrent rapidement leurs limites. Pour plus de performances, il faut utiliser la '''prédiction dynamique''', qui extrait des statistiques sur l’exécution des branchements. Pour le reste du chapitre, toutes les techniques utilisent la prédiction dynamique, qu'elles soient locales ou globales. Sa version la plus simple se contente de mémoriser ce qui s'est passé lors de l’exécution précédente du branchement. Si le branchement a été pris, alors on suppose qu'il sera pris la prochaine fois. De même, s'il n'a pas été pris, on suppose qu'il ne le sera pas lors de sa prochaine exécution. Pour cela, chaque entrée du BTB contient un bit qui mémorise la dernière exécution du branchement : 1 s'il a été pris, 0 s'il n'a pas été pris. C'est ce qu'on appelle la '''prédiction de branchements sur 1 bit'''. Au vu de sa simplicité, il ne faut pas s'attendre à des miracles. La méthode fonctionne bien pour les branchements des boucles et les branchements inconditionnels, mais elle n'est pas assez performante. Une forme plus élaborée de prédiction utilise des '''compteurs à saturation'''. Un compteur à saturation est un compteur qui est incrémenté à chaque fois qu'un branchement est pris, décrémenté s'il est non-pris. Le compteur est initialisé à la moitié de sa valeur maximale, ce qui correspond à une probabilité proche de 50%. Les compteurs à saturation sont très utilisés et pas seulement pour de la prédiction locale, les méthodes globales en utilisent aussi. Pour faire la prédiction, l'unité de prédiction regarde le bit de poids fort du compteur. Le branchement est considéré comme pris si ce bit de poids fort est à 1, et non pris s'il vaut 0. En clair : on considère que le branchement est pris si le compteur indique une probabilité supérieure à 50%. [[File:Compteur à saturation.png|centre|vignette|upright=2|Compteur à saturation.]] : Pour la culture générale : le compteur à saturation du Pentium 1 était légèrement bogué, ce qui fait que sa prédiction de branchement était sous-optimale. La plupart des processeurs utilisent un compteur à saturation par branchement, ce qui veut dire un compteur à saturation par entrée dans le BTB. Vu chaque compteur est associé à une entrée du BTB, le phénomène d’''aliasing'' mentionné plus haut peut perturber les prédictions de branchement. Deux branchements peuvent se voir associés à la même entrée du BTB, et agir sur le même compteur à saturation, ce qui entraine l'apparition d''''interférences entre branchements'''. L'interférence peut avoir des effets positifs, neutres ou négatifs, suivant la corrélation entre les deux branchements. L’''aliasing'' n'est pas un problème si les deux branchements sont fortement corrélés, par exemple si les deux sont tout le temps pris ou tout le temps non-pris. Si les deux branchements vont dans le même sens, l'interférence est neutre, voire légèrement positive. Mais si l'un est souvent pris et l’autre souvent non-pris, l'interférence est négative. Les deux branchements vont se marcher dessus sans vergogne, chacun interférant sur les prédictions de l'autre ! Il est rare que l’''aliasing'' ait un impact significatif sur les unités de prédiction des deux paragraphes précédents. Il se manifeste surtout quand la BTB est très petite et la seule solution est d'augmenter la taille du BTB. ===La prédiction avec un historique local=== La prédiction avec des compteurs à saturation est très simple, mais il est possible de créer une implémentation alternative, très proche, avec des avantages et désavantages différents. Un compteur à saturation enregistre l'historique d'un branchement, à savoir ses dernières exécutions. L''''historique''' d'un branchement dit quel a été son résultat dans le passé, pour ses exécutions précédentes. Et il est possible d'enregistrer cet historique et l'utiliser pour faire des prédictions. Par exemple, prenons un branchement sont ses 6 dernières exécutions sont "pris, non-pris, pris, pris, pris, non-pris". Le processeur peut encoder cet historique sur 6 bits. Un branchement pris correspond à un bit à 1, un branchement non-pris correspond à un 0. Le bit de poids fort correspond à l'exécution la plus ancienne, le bit de poids faible à l'exécution la plus récente. Par exemple, si l'historique contient 010, cela veut dire que le branchement a été non pris, puis pris, puis non pris. L'historique d'un branchement est appelé son '''historique local''', mais nous parlerons simplement l'historique. Le processeur peut mémoriser l'historique de chaque branchement. Pour cela, il réserve n bits par branchements, pour mémoriser ses n exécutions précédentes. L'historique d'un branchement est mémorisé dans son entrée du BTB. Et plus précisément dans un champ séparé qui est alimentée comme un registre à décalage. Reste à exploiter cet historique local pour faire des prédictions. Une idée assez simple serait de l'utiliser pour calculer une moyenne des N exécutions précédentes. Si la probabilité d'être pris est supérieure à 50 %, le branchement est considéré comme pris. Dans le cas contraire, il est considéré comme non pris. Le calcul de la moyenne utilise une simple porte à majorité, qui prend en entrée tous les bits de l'historique. Cependant, cette méthode est équivalente à utiliser un compteur à saturation par branchement. La sortie de la porte à majorité est équivalente à ce qu'on aurait dans un compteur à saturation. La seule différence : le cout en circuit et la simplicité de conception. Prenons l'exemple des premiers processeurs PA RISC. Ils mémorisaient, pour chaque branchement, les trois dernières exécutions du branchement, avec trois bits par entrée du BTB. La prédiction était réalisée avec une porte à majorité, dont le résultat était utilisé comme prédiction. Ces processeurs ont préféré utiliser un historique de 3 bits, car il était plus simple à concevoir qu'un compteur à saturation équivalent de deux bits. Il suffisait d'alimenter un registre à décalage avec un bit, pas besoin d'incrémenter ou de décrémenter un compteur, pas besoin de signaux d'incrémentation/décrémentation séparés, etc. Mais pour des historiques plus longs, la donne s'inverse et des compteurs à saturation de deux-trois bits l’emportent. Un défaut de la méthode précédente, qui est partagée avec les compteurs à saturation, est qu'elle marche mal pour les branchements qui suivent un ''pattern''. Je veux dire par là que l'exécution d'un branchement suit un cycle, par exemple pris, pris, non-pris, pris, pris, non-pris, et ainsi de suite en boucle. Notons que l'apparition de tels motifs correspond le plus souvent à la présence de boucles dans le programme. Quand une boucle s’exécute, les branchements qui sont à l'intérieur tendent à exprimer de tels motifs. Avec de tels motifs, les compteurs à saturation feront des prédictions incorrectes, là où les prédicteurs qu'on va voir font des prédictions parfaites. Par exemple, prenons un branchement qui suit le ''pattern'' pris, pris, pris, non-pris. Si l'historique local vaut 1110, le branchement est censé refaire une boucle et être pris. Et certes, on a supposé que l'historique faisait 4 bits. Mais le''pattern'' sera visible tant que l'historique fait plus de 4 bits. Par exemple, le ''pattern'' serait 01110 pour un historique local de 5 bits, 101110 pour un historique local de 6 bits, 1101110 pour un historique local de 7 bits, etc. Un ''pattern'' correspond donc à une valeur bien précise de l'historique local. L'historique local permet de voir ces cycles, reste à les exploiter. Prédire correctement les ''pattern'' demande simplement d'associer un compteur à saturation à chaque valeur possible de l'historique local. Le compteur à saturation dira, quand tel pattern est rencontré, si le branchement sera pris ou non-pris par la suite. Au total, il faut donc un registre d'historique local de n bits couplé à 2^n compteurs à saturation. Et ce pour chaque branchement possible. Les compteurs à saturation sont regroupés dans une '''''Pattern History Table''''', que nous noterons PHT dans ce qui suit. Le résultat est une '''unité de prédiction à deux niveaux locale''', qui contient plusieurs registres d'historique et tout autant de PHT locales. En tout, il y a une PHT et un historique par branchement, donc par entrée du BTB. Quand un branchement est exécuté, son historique local indique quel compteur à saturation choisir dans la PHT locale. En général, l'historique local est mémorisé dans le BTB, reste à gérer la PHT. [[File:Unité de prédiction à deux niveaux purement locale.png|centre|vignette|upright=2.5|Unité de prédiction à deux niveaux avec des historiques et des PHT locales.]] Une unité de prédiction locale à deux niveaux contient plusieurs PHT, reste à savoir quelle PHT correspond à tel branchement. La correspondance se fait idéalement à partir de l'adresse du branchement, mais c'est là une implémentation idéale, qui demande beaucoup de circuits. Généralement, l'unité de prédiction n'utilise que les bits de poids faible de l'adresse du branchement, ce qui permet de faire un choix correct, mais avec une possibilité d'''aliasing''. Il est aussi possible de séparer l'historique local du BTB. Les historiques locaux sont alors mémorisés dans une mémoire RAM dédiée, appelé la '''''Branch History Table''''', ou encore la '''table des historiques locaux''', que nous noterons BHT dans ce qui suivra. Chaque byte de la BHT contient l'historique local associé à un branchement. Pour récupérer l'historique local voulu, l'adresse du branchement est envoyée à la BHT, sur les entrées d'adresse de la BHT, directement. Seuls les bits de poids faible de l'adresse sont utilisés. L'historique local est ensuite envoyé à la PHT adéquate, choisie en fonction des mêmes bits de poids faible du PC. Un bon moyen pour cela est d'accéder à toutes les PHT en parallèle, mais de sélectionner la bonne avec un multiplexeur, ce dernier étant commandé par les bits de poids faible du PC. [[File:Table des historiques locaux.jpg|centre|vignette|upright=2|Table des historiques locaux]] Un défaut des unités de prédiction purement locales de ce type est leur cout en termes de circuits. Utiliser un registre d'historique et une PHT par branchement a un cout en transistor élevé, avec tous les défauts que ca implique en termes de consommation électrique et thermique. Elles ont aussi des temps de calcul un peu plus important que les unités purement globales, mais pas de manière flagrante. Les gains en performance avec un historique local s'observent surtout pour les branchements qui sont dans des boucles ou pour les branchements utilisés pour concevoir des boucles, alors que l'implémentation globale marche bien pour les if..else (surtout quand ils sont imbriqués). Les deux sont donc complémentaires. Dans les faits, elles sont rarement utilisées seules du fait de leurs défauts, au profit d'unités de prédiction hybrides, qui mélangent historiques et PHT locaux et globaux. ==La prédiction de branchement globale/mixte== Utiliser un historique local avec une PHT est très puissant. Mais le cout en circuit est très important. Cependant, on peut adapter l'idée pour faire de la prédiction globale. La '''prédiction globale''' fait des prédictions holistiques, qui tiennent compte de tous les branchements, sans les traiter séparément. Elle ne sépare pas les branchements, tous sont mis dans le même panier. La prédiction globale fait donc le compromis inverse : elle exploite les corrélations entre branchements, mais perd les informations statistiques précise pour chaque branchement. L'idée est qu'au lieu d'utiliser un historique par branchement, on utilise un '''historique global''' qui mémorise les exécutions de tous les branchements conditionnels. L'historique enregistre les N exécutions de branchements conditionnels. L'historique global est mémorisé dans un registre unique, appelé le '''registre d'historique global'''. C'est un registre à décalage mis à jour à chaque fois que le processeur exécute un branchement : on fait rentrer un 1 si le branchement est pris, et un 0 sinon. Une unité de prédiction globale utilise cet historique pour faire sa prédiction. L'unité de prédiction globale utilise un compteur à saturation pour chaque valeur possible du registre d'historique. En clair, pour un registre de N bits, elle utilise 2^n compteurs à saturation. Là encore, les compteurs à saturation sont regroupés dans une ''Pattern History Table''. Nous parlerons de '''PHT globale''' pour désigner une PHT commandée par un historique global, de ''PHT locale'' si elle est adressée par un historique local. [[File:Prédiction dynamique à deux niveaux.png|centre|vignette|upright=2|Prédiction dynamique à deux niveaux.]] Il est admis que l'historique global donne de meilleures prédictions que l'historique local. Mais les deux sont complémentaires, ce qui fait qu'il existe des approches hybrides. Les approches hybrides exploitent à la fois les statistiques pour chaque branchement et les corrélations entre branchements. Les prédicteurs hybrides ont de meilleures performances que les prédicteurs purement globaux ou locaux. Avec un historique global, la prédiction tient compte d'éventuelles corrélations entre branchements consécutifs/proches pour faire les prédictions. C'est un avantage pour les applications qui enchaînent des if...else ou qui contiennent beaucoup de if...else imbriqués les uns dans les autres, qui s’exécutent plusieurs fois de suite. Le résultat de chaque if...else dépend généralement des précédents, ce qui rend l'utilisation d'un historique global intéressant. Par contre, ils sont assez mauvais pour le reste des branchements. Mais cette qualité devient un défaut quand elle détecte des corrélations fortuites ou parasites, inutiles pour la prédiction (corrélation n'est pas causalité, même pour prédire des branchements). Du fait de ce défaut, la prédiction globale a besoin de registres d'historiques globaux très larges, de plusieurs centaines de bits au mieux. [[File:2 level branch predictor.svg|centre|vignette|upright=2|Unités de prédiction de branchement à deux niveaux avec une seule PHT.]] Le circuit précédent a cependant un problème : si deux branchements différents s'exécutent et que l'historique est le même, le processeur n'y verra que du feu. Il y a alors une interférence, à savoir que les deux branchements vont agir sur le même compteur à saturation. On se retrouve alors dans une situation conceptuellement identique à l’''aliasing'' dans le BTB ou avec des compteurs à saturation. Sauf que les interférences sont alors beaucoup plus nombreuses et qu'elles sont clairement un problème pour les performances ! Mitiger les interférences devient alors bien plus important qu'avec les unités de prédiction précédentes. Heureusement, si augmenter la taille de la PHT peut mitiger le problème, d'autres solutions sont possibles sur les unités de prédiction globales. Elles sont au nombre de deux : mitiger les interférences liées aux branchements biaisés, ajouter des informations qui discriminent les branchements. Voyons ces solutions dans le détail. ===La mitigation des interférences par usage de l'adresse de branchement=== La première solution pour réduire l'impact de l’''aliasing'' est d'augmenter la taille de la PHT et de l'historique. Plus l'historique et la PHT sont grands, moins l’''aliasing'' est fréquent. Mais avoir des historiques et des PHT de très grande taille n'est pas une mince affaire et le cout en termes de performances et de portes logiques est souvent trop lourd. Une autre solution consiste à utiliser, en plus de l'historique, des informations sur le branchement lui-même pour choisir le compteur à saturation à utiliser. Typiquement, on peut utiliser l'adresse du branchement en plus de l'historique, pour choisir le compteur à saturation adéquat. Pour être précis, on n'utilise que rarement l'adresse complète du branchement, mais seulement les bits de poids faible. La raison est que cela fait moins de bits à utiliser, donc moins de circuits, mais l’''aliasing'' est juste atténué, pas éliminé. Des branchements différents ont beau avoir des adresses différentes, les bits de poids faible de leurs adresses peuvent être identiques. Des confusions sont donc possibles, mais sont assez rares pour que cela suffise en pratique. Une unité de prédiction de ce type est illustrée ci-dessous. Il y a plusieurs PHT séparées, donc plusieurs ensembles de 2^n compteurs à saturation. Le choix de la PHT est réalisé par l'adresse du branchement, alors que le choix du compteur à saturation est réalisé par l'historique. Les compteurs à saturation d'un branchement sont mis à jour seulement quand le branchement s'est chargé pendant que l'historique associé était dans le registre d'historique. Cette méthode a cependant le défaut de gâcher énormément de transistors. [[File:Unité de prédiction de branchement basée sur des compteurs à saturation sélectionnés par l'historique global.jpg|centre|vignette|upright=2|Unité de prédiction de branchement basée sur des compteurs à saturation sélectionnés par l'historique global]] D'autres unités de prédiction fonctionnent sur le même principe que l'unité précédente, sauf que les différentes PHTs sont fusionnées en une seule grosse PHT. C'est ce que font les unités de prédiction '''''gshare''''' et '''''gselect''''', ainsi que leurs dérivées. Avec les unités de prédiction '''''gselect''''', on concatène les bits de poids faible de l'adresse du branchement et l'historique pour obtenir le numéro du compteur à saturation à utiliser. [[File:Prédiction « gselect ».png|centre|vignette|upright=2|Prédiction « gselect ».]] Avec les unités de prédiction '''''gshare''''', on fait un XOR entre le registre d'historique et les bits de poids faible de l'adresse du branchement. Le résultat de ce XOR donne le numéro du compteur à utiliser. Avec cette technique, on utilise une PHT globale et un historique global, mais le registre d'historique est manipulé de manière à limiter l'''aliasing''. [[File:Prédiction « gshare ».png|centre|vignette|upright=2|Prédiction « gshare ».]] Intuitivement, on pourrait croire que les unités de prédiction gselect ont de meilleures performances. C'est vrai que les unités gshare combinent l'adresse du branchement et l'historique d'une manière qui fait perdre un peu d'information (impossible de retrouver l'adresse du branchement et l'historique à partir du résultat du XOR), alors que les unités gselect conservent ces informations. Mais il faut prendre en compte le fait que les deux unités doivent se comparer à PHT identique, de même taille. Prenons par exemple une PHT de 256 compteurs, adressée par 8 bits. Avec une unité gselect, les 8 bits sont utilisés à la fois pour l'historique et pour les bits de poids faible de l'adresse du branchement. Alors qu'avec une unité gshare, on peut utiliser un historique de 8 bits et les 8 bits de poids faible de l'adresse du branchement. L'augmentation de la taille de l'historique et du nombre de bits utilisés fait que l’''aliasing'' est réduit, et cela compense le fait que l'on fait un XOR au lieu d'une concaténation. Les unités précédentes réduisent l'''aliasing'' en segmentant la PHT : telles entrées sont allouées à un branchement, telles entrées à tel autre branchement, etc. Cependant, l'historique local n'est pas utilisé. Mais quitte à allouer des entrées à un branchement, autant en profiter pour leur associer son historique local. Il s'agit alors d'approches hybrides. Par exemple, on peut citer la '''prédiction mixte''' (''alloyed predictor''). Avec celle-ci, la table des compteurs à saturation est adressée avec la concaténation : de bits de l'adresse du branchement, du registre d'historique global et du registre d'historique local adressé par l'adresse du branchement. [[File:Prédiction mixte.jpg|centre|vignette|upright=2|Prédiction mixte.]] Une version optimisée de ce circuit permet d’accéder à la PHT et à la BHT en parallèle. Avec elle les bits de poids faible de l'adresse du branchement sont concaténés avec l'historique global. Le résultat est ensuite envoyé à plusieurs PHT locales distinctes, en parallèle. Les différences PHT envoient leurs résultats à un multiplexeur, commandé par l'historique local, qui sélectionne le résultat adéquat. L'inconvénient de cette mise en œuvre est que le circuit est assez gros, notamment en raison de la présence de plusieurs PHT séparées. [[File:Alloyed predictor optimisé.jpg|centre|vignette|upright=2|''Alloyed predictor'' optimisé]] ===La mitigation des interférences par la structuration en caches des PHTs=== Les techniques précédentes utilisent les bits de poids faible de l'adresse pour sélectionner la PHT adéquate, ou pour sélectionner le compteur dans la PHT. Mais le reste de l'adresse n'est pas utilisé. Cependant, il est théoriquement possible de conserver les bits de poids fort, afin d'identifier le branchement associé à un compteur. Pour cela, chaque compteur à saturation se voit associé à un ''tag'', qui mémorise le reste de l'adresse du branchement associé au compteur, comme pour les mémoires caches. Lorsque l'unité de prédiction démarre une prédiction, elle récupère les bits de poids fort de l'adresse du branchement et compare ceux-ci avec le ''tag''. S’il y a un ''match'', c'est signe que le compteur est bien associé au branchement à prédire. Dans le cas contraire, c'est signe qu'on fait face à une situation d’''aliasing'' et le compteur n'est pas utilisé pour la prédiction. Le résultat transforme la PHT en une sorte de cache assez particulier, qui associe un compteur à saturation à chaque couple adresse-historique. La technique du paragraphe précédent peut être encore améliorée afin de réduire l’''aliasing''. L’''aliasing'' sur une unité de prédiction de branchement est similaire aux conflits d'accès au cache, où deux données/adresses atterrissent dans la même ligne de cache. Une PHT peut formellement être vue comme un cache directement adressé. Une solution pour limiter ces conflits d'accès à de tels, est de les transformer en un cache associatif à n voies. On peut faire la même chose avec les unités de prédiction de branchement, ce qui revient à dupliquer les PHT, de manière à ce que les bits de poids faible de l'adresse se voient attribuer à plusieurs compteurs à saturation, un par branchement possible. Ce faisant, on réduit les interférences entre branchements. Mais cette technique augmente la quantité de circuits utilisés et la consommation d'énergie, ainsi que le temps d'accès, sans compter qu'elle requiert d'utilisation de ''tags'' pour fonctionner à la perfection. Pour les unités de prédiction de branchement, les mesures à ce sujet ne semblent pas montrer un impact réellement important sur les performances, comparé à une organisation de type directement adressé. Il est possible de pousser la logique encore plus loin en ajoutant des caches de victime et d'autres mécanismes courant sur les caches usuels. ===La mitigation des interférences liées aux branchements biaisés=== L’''aliasing'' a un impact négatif quand deux branchements aliasés (qui sont attribués au même compteur à saturation) vont dans des sens différents : si l'un est non-pris, l'autre a de bonnes chances d'être pris (ou inversement). Or, la plupart des branchements sont biaisés, à savoir très fortement orientés dans une direction qu'une autre (presque toujours pris ou presque toujours non-pris, à plus de 90/99% de chances). Plus un branchement a une probabilité élevée d' être pris ou non-pris, plus sa capacité à interférer avec les autres est forte. Le pire des cas est quand deux branchements sont biaisés mais dans des directions inverses : l'interférence est maximale. En conséquence, les branchements biaisés ou quasi biaisés sont les plus problématiques pour l’''aliasing''. Or, il est possible de concevoir des prédicteurs de branchements qui atténuent fortement les interférences des branchements biaisés ou quasi biaisés. C’est le cas de l’''agree predictor'' et de l'unité de prédiction bimodale, que nous allons voir dans ce qui suit. Les branchements très souvent pris vont interférer très fortement avec les branchements très souvent non-pris, et inversement. Par contre, les branchements très souvent pris n'interféreront pas entre eux, de même que les branchements non-pris iront bien ensemble. D'où l'idée de séparer ces deux types de branchements dans des PHT séparées, pour éviter le mauvais ''aliasing''. L''''unité de prédiction bimodale''' part d'une unité gshare, et sépare la PHT globale en deux : une PHT dédiée aux branchements qui sont très souvent pris et une autre pour les branchements très peu pris. Les deux PHT fournissent chacune une prédiction. La bonne prédiction est choisie par un multiplexeur commandé par une unité de sélection, qui se charge de déduire quelle unité a raison. Cette unité de sélection est une unité de prédiction basée sur des compteurs à saturation de 2 bits. On peut encore améliorer l'unité de sélection de prédiction en n'utilisant non pas des compteurs à saturation, mais une unité de prédiction dynamique à deux niveaux, ou toute autre unité vue auparavant. [[File:Prédiction bimodale.jpg|centre|vignette|upright=2|Prédiction bimodale.]] La '''prédiction par consensus''' (''agree predictor'') combine une unité de prédiction à historique global (idéalement de type gshare ou gselect, mais une unité normale marche aussi) et des compteurs à saturation. Il s'agit techniquement d'une technique de prédiction mixte, à la fois globale et locale. Le BTB intègre un compteur à saturation de un bit, qui indique la direction privilégiée du branchement. L'unité à historique global a un fonctionnement changé : elle calcule non pas la probabilité que le branchement soit pris ou non-pris, mais la probabilité que le résultat du branchement soit compatible avec le résultat de l'unité de prédiction de 1 bit. La prédiction finale vérifie que ces deux circuits sont d'accord, en faisant un NXOR entre les résultats des deux unités de prédiction de branchement. [[File:Prédiction par consensus.png|centre|vignette|upright=2|Prédiction par consensus.]] Des calculs simples de probabilités montrent que l'''agree predictor'' a des résultats assez importants. Ses résultats sont d'autant meilleurs que les branchements sont biaisés et penchent fortement vers le côté pris ou non-pris. ==La prédiction de branchement avec des perceptrons== Les méthodes précédentes utilisent au moins un compteur à saturation par historique possible. Sachant qu'il y a 2^n valeurs possibles pour un historique de n bits, le nombre de compteurs à saturation augmente exponentiellement avec la taille de l'historique. Ce qui limite grandement la taille de l'historique, alors qu'on aurait au contraire besoin d'un historique assez large pour faire des prédictions excellentes. Pour contourner le problème, des alternatives basées sur des techniques d'apprentissage artificiel (''machine learning'') existent. Un exemple est celui des unités de prédiction de branchement dites de ''neural branch prediction'', basée sur des perceptrons. Dans ce qui suit, nous les appelerons des '''unités perceptron'''. Les perceptrons sont un algorithme d'apprentissage automatique très simple, ce qui fait que les explications qui vont suivre devraient être simples. En théorie, il est possible d'utiliser des techniques d'apprentissage automatique plus élaborées, mais cela n'est pas possible en pratique. Rappelons qu'une unité de prédiction de branchement doit idéalement fournir sa prédiction en un cycle d'horloge. L'implémentation d'un perceptron est déjà problématique de ce point de vue, car elle demande d'utiliser beaucoup de circuits arithmétiques complexes (multiplication et addition). Autant dire que les autres techniques de ''machine learning'', encore plus gourmandes en calculs, ne sont pas praticables. ===Les perceptrons et leur usage en tant qu'unité de prédiction de branchements=== L'idée derrière les unités perceptron est que certains bits de l'historique sont plus importants que d'autres. En soi, ce genre de situation est réaliste. Il arrive que certains branchements soient pris uniquement si les deux branchements précédents ne le sont pas, ou que si l'avant-dernier branchement est lui aussi pris. Mais les autres résultats de branchement présents dans l'historique ne sont pas utiles. En conséquence, deux historiques semblables, qui ne sont différents que d'un ou deux bits, peuvent donner des prédictions presque identiques. Dans ce cas, on peut faire la prédiction en n'utilisant que les bits identiques entre ces historiques, ou du moins en leur donnant plus d'importance qu'aux autres. On exploite alors des corrélations avec certains bits de l'historique, plutôt qu'avec l'historique entier lui-même. Pour coder ces corrélations, on associe un coefficient à chaque bit de l'historique, qui indique à quel point ce bit est important pour déterminer le résultat final. Ce coefficient est proportionnel à la corrélation entre le bit de l'historique associé, et le résultat du branchement à prédire. Les coefficients sont des nombres entiers qui peuvent être positifs, nuls ou négatifs. Un coefficient positif signifie que si le branchement associé a été pris, alors le branchement à prédire a de bonnes chances de l'être aussi (et inversement). Un coefficient nul signifie que les deux branchements sont indépendants et que le bit de l'historique associé n'est pas à prendre en compte. Pour un coefficient négatif, cela signifie que si le branchement associé a été pris, alors le branchement à prédire a de bonnes chances d'être non-pris (et inversement). Les coefficients en question sont généralement compris entre -1 et 1. Une fois qu'on connait ces coefficients de corrélations, on peut calculer la probabilité que le branchement à prédire soit pris, avec des calculs arithmétiques simples. Dans les calculs qui vont suivre, un branchement pris est codé par un 1, alors qu'un branchement non-pris est codé par un -1 ! Ce détail permet de simplifier grandement les calculs. Dans sa version la plus simple, le perceptron calcule un nombre Z qui est positif ou nul si le branchement est pris, négatif s'il ne l'est pas. Tous les coefficients <math>p_i</math> sont alors des nombres relatifs, pouvant être positifs, nuls ou négatifs. Ils sont généralement compris entre -1 et 1. La formule devient donc celle-ci : : <math>Z = w_0 + \sum_i (h_i \times w_i)</math> [[File:ArtificialNeuronModel francais.png|centre|vignette|upright=2|Perceptron.]] : Sur le plan mathématique, le perceptron effectue un produit scalaire entre deux vecteurs : l'historique et le vecteur des poids. Choisir les coefficients adéquats est le but de l'algorithme du perceptron. L'unité de prédiction part de poids par défaut, qui sont mis à jour à chaque bonne ou mauvaise prédiction. Toute la magie de cet algorithme tient dans la manière dont sont mis à jour les poids. L'idée est de prendre le vecteur des poids, puis d'ajouter ou soustraire l'historique suivant le résultat du branchement. Les poids évoluent ainsi à chaque branchement, améliorant leurs prédictions d'une exécution à l'autre. La règle de mise à jour des poids est donc la suivante : : <math>w_i \leftarrow w_i + t \times h_i</math>, avec t = 1 pour un branchement pris, -1 pour un branchement non-pris. ===L'implémentation matérielle des perceptrons et ses optimisations=== Les calculs réalisés par un perceptrons sont simples, juste des multiplications et des additions et cela se sent dans la conception du circuit. L'unité perceptron utilise un perceptron par entrée du BTB, un par branchement pour simplifier. Pour cela, on utilise une mémoire SRAM qui mémorise les poids de chaque perceptron. La SRAM est adressée par les bits de poids faible du ''program counter'', de l'adresse du branchement. Une fois les poids récupérés, ils sont envoyés à un circuit de calcul de la prédiction, composé de circuits multiplieurs suivis par un additionneur multi-opérande. Le circuit de mise à jour des poids récupère la prédiction, les poids du perceptron, mais aussi le résultat du branchement. La mise à jour étant une simple addition, le circuit est composé d'additionneurs/soustracteurs, couplés à des registres pour mémoriser la prédiction et les poids du perceptron en attendant que le résultat du branchement soit disponible. Vu qu'il y a un délai de quelques cycles avant que le résultat du branchement soit disponible et que les prédictions doivent continuer pendant ce temps, les poids du perceptron et la prédiction sont stockés dans des FIFOs lues/écrites à chaque cycle. [[File:Unité de prédiction de branchement basée sur des perceptrons.png|centre|vignette|upright=2|Unité de prédiction de branchement basée sur des perceptrons]] Rien de bien compliqué sur le principe, mais rappelons que le perceptron doit fournir un résultat en moins d'un cycle d'horloge, et cela tient compte de l'accès au BTB. C'est un temps très court, surtout pour un circuit qui implique des multiplications. Les multiplications prennent facilement deux à trois cycles d'horloge. Autant dire que si on ajoute le temps d'accès à une petite SRAM, pour récupérer le perceptron, c'est presque impossible. Mais quelques optimisations simples permettent de rendre le calcul plus rapide. Premièrement, la taille de la SRAM est réduite grâce à quelques économies assez simples. Notamment, le perceptron utilise des poids codés sur quelques bits, généralement un octet, parfois 7 ou 5 bits, guère plus. Les poids sont encodés en complément à 1 ou en complément à 2, là où les perceptrons normaux utilisent des nombres flottants. Rien que ces deux choix simplifient les circuits et les rendent plus rapides. Le désavantage d'utiliser peu de bits par poids est une perte mineure en termes de taux de prédiction, qui est plus que compensée par l'économie en portes logiques, qui permet d'augmenter la taille de la SRAM. D'autres optimisations portent sur le circuit de calcul. Par exemple, la multiplication <math>h_i \times w_i</math> est facultative. Vu que l'historique contient les valeurs 1 et -1, il suffit d'additionner le poids associé si la valeur est 1 et de le soustraire s'il vaut -1. On peut même simplifier la soustraction et se limiter à une complémentation à un (une inversion des bits du poids). En faisant cela, les circuits multiplieurs disparaissent et le circuit de prédiction se résume à un simple additionneur multi-opérande couplé à quelques inverseurs commandables. Certains perceptrons prennent en compte à la fois l'historique global et l'historique local pour faire leur prédiction. Les deux historiques sont simplement concaténés et envoyés en entrée du perceptron. Cela marche assez bien, car les perceptrons peuvent utiliser des historiques de grande taille sans problèmes. Par contre, il y a besoin d'ajouter une ''branch history table'' au circuit, ce qui demande des portes logiques en plus, mais aussi un temps de calcul supplémentaire (l'accès à cette table n'est pas gratuit). ===Les avantages et inconvénients des perceptrons pour la prédiction de branchements=== L'avantage des unités perceptron est qu'elles utilisent un nombre de portes logiques qui est proportionnel à la taille de l'historique, et non pas exponentiel. Cela permet d'utiliser un historique de grande taille, et donc d'obtenir un taux de bonnes prédictions très élevé. Leur désavantage est que leurs performances de prédiction sont moins bonnes à historique équivalent. Les unités perceptrons ont des taux de prédiction élevés, mais seulement quand certaines conditions mathématiques sont respectées par les historiques. La condition en question est que les historiques correspondants à un branchement pris et les historiques où ce même branchement est non-pris doivent être linéairement séparables. Heureusement, les branchements des programmes informatiques sont une majorité à respecter la condition de séparation linéaire, ce qui rend les perceptrons parfaitement adaptés à la prédiction de branchements. La notion de linéairement séparable est un peu difficile à comprendre. Pour l'expliquer, imaginez que les N bits de l'historique forme un espace à N-dimensions discrets. Chaque historique est un point dans cet espace N-dimensionnel et chaque bit sert de coordonnée pour se repérer dans cet espace. Une fonction est linéairement séparable si l'espace N-dimensionnel peut être coupé en deux par un hyperplan : d'un côté de ce plan se trouvent les historiques des branchements pris, de l'autre se trouvent les historiques des branchements non-pris. Cet hyperplan est défini par l'ensemble des points qui respecte l'équation suivante : : <math>w_0 + \sum_i (h_i \times w_i) = 0</math> Un exemple où cette condition est respectée est quand le résultat d'une prédiction se calcule avec un ET entre plusieurs branchements de l'historique. Si un branchement est pris quand plusieurs branchements de l’historique sont tous pris ou tous non-pris, la condition est respectée et le perceptron donnera des prédictions correctes. Un exemple où cette condition n'est pas respectée est un banal XOR. Prenons l'exemple d'un historique global de 2 bits. Imaginons que le branchement à prédire soit pris : soit quand le premier branchement de l'historique est pris et le second non-pris, soit quand le premier est non-pris et le second pris. Concrètement, la prédiction exacte se calcule en faisant un XOR entre les deux bits de l'historique. Dans ce cas, la condition "linéairement séparable" n'est pas respectée et le perceptron n'aura pas des performances optimales. Les unités perceptron utilisent idéalement un perceptron par branchement. Cela demande d'associer, l'adresse du branchement pour chaque perceptron, généralement en donnant un perceptron par entrée du BTB. Mais une telle organisation n'est pas possible en pratique, car elle demanderait d'ajouter un ''tag'' à chaque perceptron/entrée du BTB, ce qui demanderait beaucoup de circuits et de ressources matérielles. Dans les faits l'association entre un branchement et un perceptron se fait en utilisant les bits de poids faible de l'adresse de branchement. Mais faire cela entrainera l'apparition de phénomènes d'''aliasing'', comme pour les unités de prédiction à deux niveaux. Les techniques vues précédemment peuvent en théorie être adaptées sur les unités à perceptrons, dans une certaine mesure. Notons que les perceptrons sont des algorithmes ou des circuits qui permettent de classer des données d'entrée en deux types. Ici, la donnée d'entrée est l'historique global et la sortie du perceptron indique si le branchement prédit est pris ou non-pris. Ils ne sont donc pas adaptés à d'autres tâches de prédiction, comme pour le préchargement des lignes de cache ou la prédiction de l'adresse de destination d'un branchement, ou toute autre tâche d'exécution spéculative un tant soit peu complexe. Leur utilisation reste cantonnée à la prédiction de branchement proprement dit, guère plus. Par contre, les autres techniques vues plus haut peuvent être utilisées pour le préchargement des lignes de cache, ou d'autres mécanismes de prédiction plus complexes, que nous aborderons dans la suite du cours. ==La prédiction des branchements des boucles== Les boucles sont à part, pour ce qui est de la prédiction de branchement. Rappelons qu'une boucle FOR/WHILE répète une série d'instruction N fois, le nombre N étant appelé le '''compteur de boucle'''. Ce qui fait que les branchements d'une boucle FOR sont pris n − 1 fois, la dernière exécution étant non prise. La conséquence est que les unités de prédiction usuelles sont assez mauvaises pour prédire les branchements des boucles. Par contre, la prédiction statique marche particulièrement bien comparé au reste. La prédiction statique prédit que les branchements des boucles sont toujours pris, ce qui donne des prédictions qui sont d'autant meilleures que la boucle est répétée un grand nombre de fois. Reste à gérer les branchements des boucles au mieux, en sachant cela. L'idée est d'utiliser plusieurs unités de prédiction séparées : une spécialisée dans les boucles et d'autres unités de prédiction. Uen unité de méta-prédiction se charge d'activer l'unité de prédiction des boucles dès qu'une boucle est détéctée. Les unités de prédiction modernes essayent de détecter les branchements des boucles afin de les mettre à part. En soi, ce n'est pas compliqué les branchements des boucles sont presque toujours des branchements descendants et réciproquement. De plus, ces branchements sont pris à chaque répétition de la boucle, et ne sont non-pris que quand on quitte la boucle. Le compteur de boucle analyse l'exécution des branchements, pour détecter les branchements des boucles. Un branchement est considéré comme un branchement de boucle si : il est pris N fois, avant de ne pas être pris une fois. Au moment où le branchement n'est plus pris, le ''Loop Predictor'' lui attribue une entrée dédié. L'entrée mémorise mémorise le nombre de fois que ce branchement a été pris, à savoir N, et est associée à un compteur. Le compteur est incrémenté/décrémenté à chaque exécution du branchement, et sa valeur est comparée à la valeur N. Quand le compteur atteint N+1, il est réinitialisé. Il s'agit d'une implémentation simple, mais est visiblement proche de celle utilisée sur le Pentium M, si j'en crois l'article "The Intel Pentium M Processor : Microarchitecture and Performance". Il faut noter que la boucle doit s'exécuter au moins une fois pour être détectée, et seules les exécutions suivantes sont prédites correctement. La boucle doit donc s'exécuter plusieurs fois, ce qui implique qu'elle est elle-même dans une boucle plus grande qu'elle. Une telle unité est donc capable de prédire spécifiquement les branchements de boucles FOR imbriquées, à savoir où une boucle FOR est dans une autre boucle FOR. Concrètement, cela permet de répéter la première boucle FOR plusieurs fois de suite, souvent un grand nombre de fois. Avec les boucles imbriquées, le compteur de boucle peut changer d'une répétition à l'autre, mais ce n'est que rarement le cas. Dans de nombreux cas, le compteur de boucle reste le même d'une répétition à l'autre. Ce qui fait qu'une fois la boucle exécutée une première fois, on peut prédire à la perfection les exécutions suivantes. Pour cela, il suffit de déterminer le compteur de boucle après la première exécution de la boucle, puis de le mémoriser dans un compteur. Lors des exécutions suivantes de la boucle, on compte le nombre de fois que le branchement de la boucle s'exécute : il est prédit comme pris tant que le compteur est différent du compteur de boucle, mais non-pris en cas d'égalité. ==La prédiction avec plusieurs unités de branchement distinctes== Il est possible de combiner plusieurs unités de prédiction de branchement différentes et de combiner leurs résultats en une seule prédiction. On peut par exemple combiner une unité de prédiction spécialisée dans les boucles, une unité de prédiction 2 bits basée sur des compteurs à saturation, une unité de prédiction statique et une unité ''gshare''. Tout le problème est de décider quelle unité a fait la bonne prédiction, comment combiner les résultats des différentes unités de prédiction. Soit on choisit un résultat qui parait plus fiable que les autres, soit on combine les résultats pour faire une sorte de moyenne des prédictions. La méthode la plus simple de choisir le résultat d'une unité de prédiction parmi toutes les autres. Pour implémenter le tout, il suffit d'un multiplexeur qui effectue le choix de la prédiction. Reste à commander le multiplexeur, ce qui demande un '''circuit méta-prédicteur''' qui sélectionne la bonne unité de prédiction. Il arrive que le circuit méta-prédicteur soit conçu avec les mêmes techniques que les unités de prédiction de branchement elle-mêmes. Dans le cas le plus simple, il s'agit d'un simple compteur à saturation, mis à jour suivant la concordance des prédictions avec le résultat effectif du branchement. Mais c'est loin d'être systématique. Une autre solution combine le résultat des différentes unités de prédiction avec une fonction mathématique adéquate. Avec un nombre impair d'unités de prédiction, une méthode assez efficace est de simplement prendre le résultat majoritaire. Si une majorité d'unités pense que le branchement est pris, alors on le considère comme pris, et comme non pris dans le cas contraire. Par contre, avec un nombre pair d'unités, cette méthode simple ne marche pas, il y a un risque d'égalité. L'unité de prédiction de branchement « '''''e-gskew''''' » utilise trois unités gshare et combine leurs résultats avec un vote à majorité. Les trois unités gshare utilisent des XOR légèrement différents, dans le sens où les bits de l'adresse du branchement choisi ne sont pas les mêmes dans les trois unités, sans compter que le résultat du XOR peut subir une modification qui dépend de l'unité de prédiction choisie. Autrement dit, la fonction de hachage qui associe une entrée à un branchement dépend de l'unité. [[File:Unité de prédiction « e-gskew ».png|centre|vignette|upright=2|Unité de prédiction « e-gskew ».]] Enfin, une dernière solution est que certaines unités de prédiction ont la priorité sur toutes les autres. Par exemple, prenons un processeur avec un ''return stack predictor'', une unité qui détecte les boucles et une unité de prédiction avec un historique. Si le ''return stack predictor'' détecte une instruction de retour de fonction, sa prédiction passera avant toutes les autres unités de prédiction. Et dans ce qui va suivre, c'est cette solution qui sera utilisé pour les unités de prédiction qu'on va étudier. ===Le prédicteur L-TAGE=== Il est possible d'utiliser plusieurs unités de prédiction, chacune utilisant des historiques de taille différente. Pour donner un exemple simple, on pourrait avoir une unité avec un historique de 2 bits, une autre avec un historique de 3 bits, une autre de 4 bits, etc. Une méta-unité de branchement prédit alors quelle taille d'historique donne les meilleurs résultats. Il est fréquent que les tailles d'historiques utilisées suivent une formule mathématique précise, appelée suite géométrique, ce qui est un mot bien barbare pour dire que l'on passe d'un historique au suivant en multipliant sa taille par une constante bien précise. Par exemple, on pourrait avoir des historiques de taille 2, 4, 8, 16, 32. C'est d'ailleurs le principe derrière les '''unités de branchement TAGE (''TAgged GEometric length predictor'')'''. Elles utilisent plusieurs registres d'historiques, chacun avec sa propre PHT, dont la taille suit une suite géométrique. Avec cette méthode, les branchements qui ont un motif répétitif sont alors parfaitement détectés, peu importe sa taille. Par exemple, un branchement avec un historique dont le cycle est pris, non-pris, non-pris, sera parfaitement prédit avec un historique de 3 bits, 6 bits, ou de 3*n bits, mais pas forcément avec un historique de 4 ou 8 bits. De ce fait, utiliser plusieurs unités de branchement avec plusieurs tailles d'historique fonctionne plutôt bien. Le prédicteur TAGE a été raffiné avec le temps, sur plusieurs points, que je ne vais pas détailler dans ce qui suit. Précisons cependant que les PHT sont structurées en caches, afin d'éliminer les phénomènes d'''aliasing''. L'ajout d'une unité de prédiction pour les boucles, a donné le '''prédicteur L-TAGE''', qui a lui-même été amélioré par la suite. Les unités de branchement TAGE sont les plus utilisées au moment où j'écris ces lignes (2026), et la majorité des processeurs x86 commerciaux utilisent une variante de ce prédicteur, à quelques exceptions près. Le '''prédicteur ITTAGE''' peut être adapté pour prédire des branchements indirects. La seule différence est que chaque table d'historique est associée non seulement à une prédiction pris/non-pris, mais aussi à une adresse de destination. L'idée derrière l'ITTAGE est que l'adresse de destination dépend de l'historique. L'adresse de destination dépend de ce qui se passe avant qu'on exécute le branchement indirect, donc de l'historique global. Il est donc fréquent que des historiques différents donne un résultat différent, que ce soit pour la prédiction pris/non-pris, mais aussi pour l'adresse de destination. L'ITTAGE associe donc une adresse de destination par ''pattern'' prédit. ==Les optimisations de la prédiction de branchements== La prédiction de branchement est complexe et toute économie est bonne à prendre. Pour améliorer les performances, ou simplement améliorer l'utilisation du BTB et des PHT, diverses techniques ont été inventées. Ces techniques marchent quel que soit l'unité de prédiction prise en compte. Elles peuvent s'appliquer aussi bien aux unités basées sur des perceptrons, que sur des unités à deux niveaux ou des unités de prédiction dynamique en général. Ces techniques sont assez variés : certaines profitent du fait que de nombreux branchements sont biaisés, d'autres tentent de réduire les interférences entre branchements sans utiliser l'historique global/local, etc. ===Le filtrage de branchements=== Une première optimisation permet d'économiser l'usage des différentes ressources matérielles, comme la BTB ou les PHT, en les réservant aux branchements non-biaisés. Idéalement, les branchements biaisés peuvent être prédits en utilisant des techniques très simples. D'où l'idée d'utiliser deux unités de prédiction spécialisées : une pour les branchements biaisés et une autre plus complexe. L'unité de prédiction pour les branchements biaisés est une unité de prédiction à 1 bit qui indique si le branchement est pris ou non, ce qui suffit largement pour de tels branchements. Cette technique s'appelle le '''filtrage de branchement''' et son nom est assez parlant. On filtre les branchements biaisés pour éviter qu'ils utilisent des PHT et d'autres ressources qui gagneraient à être utilisées pour des branchements plus difficiles à prédire. Appliquer cette idée demande de reconnaître les branchements fortement biaisés d'une manière ou d'une autre, ce qui est plus facile à dire qu'à faire. Une solution similaire enregistre quels branchements sont biaisés dans le BTB, et utilise cette information pour faire des prédictions. ===L'usage de fonctions de hashage pour indexer les diverses SRAM/tables=== Plus haut, nous avons vu que les unités de prédiction de branchement contiennent des structures qui sont adressées par l'adresse de branchement. Tel est le cas du ''Branch Target Buffer'', de certaines PHT globales ou locales, de la ''Branch History Table'' qui stocke les historiques locaux, ou encore de la SRAM des poids des unités à base de perceptrons. En pratique, ces structures sont adressées non pas par l'adresse de branchement complète, mais pas les bits de poids faible de cette adresse. Cela a pour conséquence l'apparition d'un ''aliasing'' lié au fait que ces structures vont confondre deux branchements pour lesquels les bits de poids faible de l'adresse sont identiques. Il est possible d'utiliser autre chose que les bits de poids faible de l'adresse du branchement, afin de limiter les interférences. Et les possibilités sont multiples. Les possibilités en question s'inspirent des traitements effectués sur les adresses des banques dans les mémoires évoluées. Une première solution serait de faire un XOR entre les bits de poids faible de l'adresse du branchement, et d'autres bits de cette même adresse. Ainsi, deux branchements éloignés en mémoire donneraient des résultats différents, même si leurs bits de poids faible sont identiques. Une autre possibilité serait de diviser l'adresse du branchement par un nombre et de garder le reste. Ce calcul de modulo n'est en soi pas très différent du fait de conserver seulement les bits de poids faible. Conserver les N bits de poids faible consiste en effet à prendre le modulo par 2^N de l'adresse. Ici, l'idée serait de faire un modulo par un nombre P, qui serait un nombre premier proche de 2^N. Le fait que le nombre soit premier limite les cas où deux adresses différentes donneraient le même reste, ce qui réduit l'''aliasing''. Le fait de prendre un nombre proche de 2^N pour une entrée de N bits est que le résultat reste assez proche de ce qu'on obtiendrait en gardant les bits de poids faible, cette dernière étant une solution pas trop mauvaise. D'autres possibilités similaires se basent sur des réductions polynomiales ou d'autres astuces impliquant des nombres premiers. L'efficacité de ces méthodes dépend grandement de la taille de la SRAM/table considérée, des adresses des branchements et de beaucoup d'autres paramètres. La réduction des interférences par telle ou telle méthode dépend aussi de l'unité de prédiction considérée. Les résultats ne sont pas les mêmes selon que l'on parle d'une unité à perceptrons ou d'une unité à deux niveaux ou d'unités à base de compteurs à saturation, ou que l'on parle du BTB. Par contre, toutes les méthodes ne sont pas équivalentes en termes de temps de calcul ou de portes logiques. Autant la première solution avec un XOR ajoute un temps de calcul négligeable et quelques portes logiques, autant les autres méthodes requièrent l'ajout d'un diviseur très lent et gourmand en portes logiques pour calculer des modulos. Elles ne sont généralement pas praticables pour ces raisons, le temps de calcul serait trop élevé. <noinclude> {{NavChapitre | book=Fonctionnement d'un ordinateur | prev=Le pipeline | prevText=Le pipeline | next=Les optimisations du chargement des instructions | nextText=Les optimisations du chargement des instructions }} </noinclude> kl18wweydks1xcubcw6wit6baobxs5v 775385 775384 2026-10-18T16:22:53Z Mewtow 31375 /* La prédiction de l'adresse de retour d'une fonction */ 775385 wikitext text/x-wiki Les branchements sont pris en charge par plusieurs étages du pipeline. Exécuter un branchement demande de savoir deux choses : s'il est pris ou non, quelle est l'adresse de destination. L'adresse de destination est localisée grâce au mode d'adressage du branchement. Avec le mode d'adressage direct, elle est extraite de l'instruction par le séquenceur. Avec l'adressage indirect, elle est lue dans un registre. Avec les branchements relatifs, elle est calculée via un additionneur, qui additionne un décalage au ''program counter''. L'additionneur peut être soit dans l'étage de ''PC Update'', soit dans l'unité de calcul de l'étage d'exécution. Passons maintenant au résultat du branchement, à savoir s'il est pris ou non. Pour savoir si le branchement est pris, il faut distinguer les branchements conditionnels et inconditionnels. Pour rappel, les branchements inconditionnels regroupent les appels de fonction, les simples instructions de saut, et quelques autres. Ils sont toujours pris, ils s'exécutent toujours. À partir du moment où le décodeur a décodé un branchement inconditionnel, il sait que le branchement est pris. Pour les branchements conditionnels, ils sont pris seulement si une condition précise est respectée. On sait s'ils sont exécutés une fois que la condition est calculée par l'unité de calcul, ou par une unité de branchement spécialisée. [[File:Gestion des branchements sur un pipeline.png|centre|vignette|upright=2.0|Gestion des branchements conditionnels sur un pipeline.]] Sur le schéma précédent, les branchements inconditionnels ne sont pas montrés. Pour cela, il faudrait rajouter une connexion du décodeur vers le multiplexeur de branchement. De plus, il faudrait aussi rajouter de quoi retarder l'exécution du branchement seulement une fois que l'adresse est connue. Par exemple, elle est connue un cycle d'horloge plus si l'adresse est lue depuis les registres, comparé à un branchement direct. ==Les branchements et les exceptions imprécises/précises== Un branchement est censé altérer le ''program counter'' immédiatement, en un cycle d'horloge. Mais sur un pipeline, Le branchement fait bien reprendre le processeur au bon endroit, mais avec du retard. La raison est qu'un branchement met plusieurs cycles pour s'exécuter. Il faut plusieurs cycles pour déterminer quelle est l'adresse de destination, temps qui dépend de là où est lue l'adresse. Et on sait si le branchement est pris seulement au niveau du décodeur, voire au niveau de l'unité de calcul. Le branchement doit traverser plusieurs étages avant qu'on connaisse son résultat. Il y a bien 3 à 4 cycles avant cela. Et pendant ce temps de trajet, des instructions seront chargées dans le pipeline, potentiellement à tort. Si le branchement n'est pas pris, ce n'est pas grave : les instructions n'ont pas été chargées à tort. Mais dans le cas contraire, les instructions n'auraient pas dû rentrer dans le pipeline. Le problème est similaire à celui observé avec les exceptions précises/imprécises. La différence est que les branchements sont des instructions machines, pas les exceptions matérielles. Mais le problème des instructions chargées à tort est le même dans les grandes lignes. Une différence est que les branchements sont résolus plus ou moins au même étage, alors que les exceptions peuvent survenir dans tout le pipeline. Une autre différence, bien plus importante, est que les branchements non-pris ne chargent pas d'instructions à tort et qu'il faut faire la différence entre branchement pris et non-pris. Dans la suite, nous parlerons d'instructions fautives pour parler des instructions chargées à tort. Pour corriger ce problème, il existe une solution logicielle. Le compilateur fait suivre les branchements par des instructions qui ne font rien, des NOP (No OPeration) : c'est ce qu'on appelle un '''délai de branchement'''. L'idée est que toutes les instructions chargées à tort sont des NOPs, qui ne font rien. Mais le nombre de NOP à ajouter dépend du pipeline du processeur, ce qui peut poser des problèmes de compatibilité. Mais d'autres solutions, matérielles cette fois, sont utilisées de nos jours. ===L'annulation des instructions au décodage=== Les branchements inconditionnels sont dans un cas plus favorable : ils sont identifiés dans l'unité de décodage et sont toujours pris. D'autres branchements sont dans ce cas : les appels de fonctions, les interruptions logicielles. Avec eux, le décodeur annule les instructions fautives, il les remplace par des instructions NOP. L'étage de décodage sait que les instructions suivant un branchement inconditionnel ont été chargées à tort. Précisément N instructions, avec N le nombre d'étages entre le chargement et le décodage (inclus). Les N instructions suivantes sont tout simplement annulés, elles sont remplacées par des NOPs. L'implémentation demande juste un simple compteur et quelques circuits annexes. Cependant, la technique ne marche pas du tout pour les branchements conditionnels. En effet, on ne sait pas s'ils sont pris ou non à l'étage de décodage. Du moins pas avec un pipeline normal. Mais certains processeurs, basés sur le pipeline RISC classique, calculaient les branchements pendant l'étape de décodage, dans une ALU spécialisée qui travaille en parallèle de l'unité de décodage. Le défaut de cette technique est que l'ALU en question doit lire les registres. Pour rappel, sur ce pipeline, l'étape de décodage effectue la lecture des opérandes dans les registres, en parallèle de l'unité de décodage. Mais ce qu'on n'a pas dit dans le chapitre précédent, c'est qu'elle effectue aussi le calcul des branchements dans une mini-ALU séparée ! Ce faisant, le résultat du branchement est connu dès la fin de l'étape de décodage. ===L'usage du système d'exceptions précises pour les branchements conditionnels=== La solution gère le problème en empêchant les instructions chargées à tort d'enregistrer leurs résultats, afin qu'elles n'aient pas le moindre effet sur l'état du processeur. Le hardware pour les exceptions précises, décrit quelques paragraphes avant, est réutilisé pour cela. Les branchements conditionnels peuvent être pris ou non-pris et on doit tenir compte de ces deux cas. Si le branchement n'est pas pris, les instructions n'ont pas été chargées à tort, elles peuvent enregistrer leur résultat dans les registres. Par contre, ce n'est pas le cas pour les branchements pris, les mécanismes d'exceptions précise doivent alors d'activer. Pour cela, la meilleure solution est que l'unité de calcul génère un indicateur d'exception si le branchement n'est pas pris. L'ALU effectue la comparaison et génère ou non l'indicateur d'exception adéquat suivant le résultat de celle-ci. L'idée est d'utiliser un indicateur d'exception particulier, qui précise qu'un branchement a été pris, signe que des instructions ont été chargées à tort. L'indicateur est propagé dans le pipeline, jusqu'à atteindre l'étage d'enregistrement dans les registres. Cet étage décide s'il faut autoriser ou non les écritures qu'il recoit, pour annuler les instructions chargées à tort. Le ''program counter'' est corrigé immédiatement, simplement en exécutant le branchement. Reste à savoir qui génère cet indicateur d'exception de branchement pris. Diverses optimisations visent à éliminer les instructions chargées à tort, à faire en sorte que des instructions utiles soient chargées. Le chapitre suivant va détailler ces optimisations dans le détail, qui sont regroupées sous le terme de prédiction de branchement. Elles ne fonctionnent pas pour les exceptions précises, seulement les branchements. ===La prédiction de branchement=== Les techniques précédentes ont pour défaut que de nombreux cycles d'horloge sont gâchés à cause des instructions fautives. Pour éviter ce gâchis, les concepteurs de processeurs ont inventé l'''exécution spéculative de branchement'', qui consiste à deviner l'adresse de destination du branchement et charger les bonnes instructions dès le départ. Le but est de ne pas charger d'instruction à tort, en prédisant quelles seront les bonnes instructions à charger. Et cela demande de résoudre trois problèmes : * reconnaître les branchements ; * savoir si un branchement sera exécuté ou non : c'est la '''prédiction de branchement''' ; * dans le cas où un branchement serait exécuté, il faut aussi savoir quelle est l'adresse de destination : c'est la '''prédiction de l'adresse de destination''' d'un branchement, aussi appelée ''branch target prediction''. Pour résoudre le second problème, le processeur contient un circuit qui déterminer si le branchement est pris (on doit brancher vers l'adresse de destination) ou non pris (on poursuit l’exécution du programme immédiatement après le branchement) : c'est l''''unité de prédiction de branchement'''. La prédiction de direction de branchement est elle aussi déléguée à un circuit spécialisé : l’'''unité de prédiction de direction de branchement'''. C'est l'unité de prédiction de branchement qui autorise l'unité de prédiction de destination de branchement à modifier le ''program counter''. Dans certains processeurs, les deux unités sont regroupées dans le même circuit. [[File:Relation entre prédiction de branchement et de direction de branchement.png|centre|vignette|upright=2|Relation entre prédiction de branchement et de direction de branchement.]] : Au lieu de parler d'unité de prédiction de branchement, j'utiliserais parfois le terme '''prédicteur''', sous-entendu ''prédicteur de branchement''. Avant de poursuivre, faisons une remarque très importante. J'ai parlé d'unité de prédiction de branchement, comme s'il n'y en avait qu'une seule. Mais en réalité, n'en avoir qu'une seule est l'exception. La règle est d'avoir plusieurs unités de branchements spécialisées. Un processeur moderne utilise plusieurs prédicteurs séparés, chacun prédisant un type de branchement bien précis. Il y a pas exemple un prédicteur spécialisé pour les boucles, un autre pour les instructions de retour de fonctions, un autre pour les branchements directs, un autre pour les branchements indirects. Les processeurs modernes utilisent une prédiction de branchement à deux niveaux. Un premier prédicteur fournit des résultats rapides et peu précis, un second a des résultats plus précis après quelques cycles d'horloge. Le prédicteur rapide envoit l'adresse prédite au cache d'instruction, pour charger les instructions prédites et mettre à jour le ''program counter''. Le prédicteur lent envoient leurs résultats au décodeur d'instruction, histoire d'annuler des branchements considérés à tort comme pris/non-pris. Il y a donc des prédicteurs rapides, dont le résultat est corrigé par des prédicteurs plus lents. La seconde unité a le dernier mot, elle corrige ou annule les prédictions de la première. Ce qui lui vaut le nom, en anglais, d'''overiding predictor''. La correction se fait simplement en corrigeant le ''program counter'' et en forçant le décodeur à émettre des NOPs pendant quelques cycles, le temps d'éliminer les instructions chargées à tort. Ce détail aura rapidement son importance. ==Les erreurs de prédiction de branchement== Le processeur peut parfaitement se tromper en faisant ses prédictions, ce qui charge des instructions par erreur dans le pipeline. Dans ce cas, on parle d''''erreur de prédiction'''. Les erreurs de prédiction sont corrigées par le système d'exception précises, ou un équivalent. En clair, les instructions chargées à tort se propagent jusqu'à la sortie du pipeline, où leurs résultats sont alors annulés. N'importe quelle technique de gestion des exceptions précise fait le travail, mais les processeurs modernes utilisent un tampon de réordonnancement (''reorder buffer'') qu'on détaillera dans quelques chapitres. Détecter les erreurs de prédiction demande d'ajouter un circuit dans le processeur : l’''unité de vérification de branchement'' (''branch verification unit''). Elle génère un indicateur d'exception, qui est géré par le système d'exception précise. Pour générer l'indicateur, elle compare l'adresse de destination prédite et celle calculée en exécutant le branchement. Pour cela, l'adresse prédite doit être propagée dans le pipeline jusqu’à ce que l'adresse de destination du branchement soit calculée. [[File:Unité de vérification de branchement.png|centre|vignette|upright=2|Unité de vérification de branchement]] ===La pénalité de mauvaise prédiction=== Le temps pour vider le pipeline des instructions fautives dépend du pipeline. La dernière instruction à être chargée dans le pipeline le sera en même temps qu'on détecte l'erreur de prédiction. Il faudra attendre que cette instruction quitte le pipeline, et donc qu'elle traverse tous les étages. Il y a donc un temps d'attente pour collecter les résultats de ces instructions et la décision de ne pas enregistrer leurs résultats dans les registres Le nombre d'instructions chargées à tort dépend de où est détectée l'erreur de prédiction. Plus le résultat du branchement est connu tard, plus le nombre d'instructions chargées à tort sera grand, et plus le nombre de cycles d'horloge gâchés le sera aussi. Le nombre de cycles gâchés s'appelle la '''pénalité de mauvaise prédiction'''. Elle correspond précisément au nombre de cycles/étages entre le premier étage du pipeline, et l'étage où le branchement est résolu (on connait l'adresse à laquelle brancher). Plus celui-ci est éloigné du début du pipeline, plus la pénalité est importante. [[File:MIT 6.823 Computer System Architecture, Fall 2005 - P-3 vs. P-4 Pipelines - 4473425702.jpg|centre|vignette|upright=2.5|Comparaison de la pénalité de mauvaise prédiction entre le Pentium 3 et le Pentium 4 d'Intel.]] Elle est généralement d'autant plus longue que le pipeline lui-même est long. Les concepteurs de processeurs font donc face à un compromis : un pipeline long permet d'exécuter plus d'instructions en parallèle, mais cela augmente aussi la pénalité de mauvaise prédiction. Un pipeline de 10-15 étapes est un bon compromis. Les pipelines plus longs ont besoin d'une prédiction de branchement élaborée pour fonctionner correctement. Plus la prédiction de branchement est performante, plus le pipeline peut être long. Les pénalités de mauvaise prédiction seront plus importantes, mais les mauvaises prédictions seront plus rares, ce qui compense complétement. ===La ''minimal control dependency''=== En utilisant une technique du nom de ''minimal control dependency'', seules les instructions qui dépendent du résultat du branchement sont supprimées du pipeline en cas de mauvaise prédiction, les autres n'étant pas annulées. Sans ''minimal control dependency'', toutes les instructions qui suivent un branchement dans notre pipeline sont annulées. Pourtant, certaines d'entre elles pourraient être utiles. Prenons un exemple : supposons que l'on dispose d'un processeur de 31 étages (un Pentium 4 par exemple). Supposons que l'adresse du branchement est connue au 9éme étage. On fait face à un branchement qui envoie le processeur seulement 6 instructions plus loin. Si toutes les instructions qui suivent le branchement sont supprimées, les instructions en rouge sont celles qui sont chargées incorrectement. On remarque pourtant que certaines instructions chargées sont potentiellement correctes : celles qui suivent le point d'arrivée du branchement. Elles ne le sont pas forcément : il se peut qu'elles aient des dépendances avec les instructions supprimées. Mais si elles n'en ont pas, alors ces instructions auraient dûes être exécutées. Il serait donc plus efficace de les laisser enregistrer leurs résultats au lieu de les ré-exécuter à l’identique un peu plus tard. Ce genre de choses est possible sur les processeurs qui implémentent une technique du nom de ''Minimal Control Dependancy''. En gros, cette technique fait en sorte que seules les instructions qui dépendent du résultat du branchement soient supprimées du pipeline en cas de mauvaise prédiction. [[File:Minimal cntrol dependency.png|centre|vignette|upright=2|Minimal control dependency]] ==La reconnaissance des branchements== Pour prédire des branchements, le processeur doit faire la différence entre branchements et autres instructions, dès l'étage de chargement. Or, un processeur « normal », sans prédiction de branchement, ne peut faire cette différence qu'à l'étage de décodage, et pas avant. Les chercheurs ont donc dû trouver une solution. La première solution se base sur les techniques de prédécodage vues dans le chapitre sur le cache. Pour rappel, ce prédécodage consiste à décoder partiellement les instructions lors de leur chargement dans le cache d'instructions et à mémoriser des informations utiles dans la ligne de cache. Dans le cas des branchements, les circuits de prédécodage peuvent identifier les branchements et mémoriser cette information dans la ligne de cache. Une autre solution mémorise les branchements déjà rencontrés, dans un cache dédié. Ce cache mémorise l'adresse (le ''program counter'') des branchements déjà rencontrés : il s'appelle le '''tampon d’adresse de branchement''' (''branch adress buffer''). Il est intégré à l'unité de prédiction de branchement, mais est alimenté par le décodeur d'instruction. Reconnaitre un branchement demande l'implication du décodeur d'instruction, qui sait si l'instruction qu'il vient de décoder est un branchement ou non. Il peut même savoir si le branchement est conditionnel, inconditionnel, un appel de retour de fonction, etc. Lorsque le décodeur d'instruction reconnait un branchement, il ajoute ce branchement dans le cache Le tapon d'adresse de branchement contient une adresse mémoire par branchement, et éventuellement d'autres informations. Et pour comprendre quelle adresse est mémorisée, il faut faire attention à un détail. Les explications qui vont suivre vont faire intervenir deux adresses. * La première est l''''adresse de destination''' du branchement, à savoir l'adresse à laquelle le processeur doit reprendre son exécution si le branchement est pris. * L'autre adresse est l''''adresse du branchement''' lui-même. Elle correspond à sa position en mémoire RAM. L'adresse du branchement est la valeur du ''program counter'' quand le branchement est chargé dans le cache, alors que l'adresse de destination est celle du ''program Counter'' une fois le branchement exécuté. Il faudra faire bien attention à ne pas confondre les deux adresses dans ce qui suit. L'adresse du branchement est celle qui est utilisée pour la reconnaissance du branchement. Le tampon d'adresse de branchement mémorise, pour chaque branchement, son adresse de branchement (d'où son nom). À chaque cycle d'horloge, l'unité de chargement envoie le ''program counter'' en entrée du tampon d’adresse de branchement. Un succès dans ce cache indique qu'un branchement déjà rencontré est ré-executé, on peut utiliser la prédiction de branchement. Dans le cas contraire, la prédiction de branchement n'est pas utilisée, et l'instruction est chargée normalement. ==La prédiction de l'adresse de destination== La '''prédiction de l'adresse de destination d'un branchement''' détermine l'adresse de destination d'un branchement. Rappelons qu'il existe plusieurs modes d'adressage pour les branchements et que chacun d'entre eux précise l'adresse de destination à sa manière. Suivant le mode d'adressage, l'adresse de destination est soit dans l'instruction elle-même (adressage direct), soit calculée à l’exécution en additionnant un ''offset'' au ''program counter'' (adressage relatif), soit dans un registre du processeur (branchement indirect), soit précisée de manière implicite (retour de fonction, adresse au sommet de la pile). : Histoire de simplifier la terminologie, je parlerais parfois de '''prédiction de destination''' pour parler de la ''prédiction de l'adresse de destination d'un branchement''. Pour rappel, les branchements se classent en trois types : * les branchements directs pour lequel l'adresse de destination est toujours la même ; * les branchements indirects où l'adresse de destination est dans un registre et peut changer ; * les instructions de retour de fonction. Les branchements directs sont facilement prévisibles, vu que l'adresse vers laquelle il faut brancher est toujours la même. La prédiction des branchements directs et relatifs se fait globalement de la même manière, ce qui fait que nous ferons la confusion dans ce qui suit. Pour les instructions de retour de fonction, une prédiction parfaite est possible. Et c'est ce qui explique qu'elles sont traitées à part, par une unité de branchement dédiée. Pour les branchements indirects, vu que cette adresse change, la prédire celle-ci est particulièrement compliqué (quand c'est possible). Les branchements indirects sont eux aussi traités par une unité de prédiction dédiée rien que pour eux. ===La prédiction de destination pour les branchements directs=== Lorsqu'un branchement est exécuté, on mémoriser l'adresse de destination et la réutiliser lors d'exécutions ultérieures du branchement. Cette technique marche à la perfection pour les branchements directs, pour lesquels cette adresse est toujours la même, mais donne des résultats mitigés pour les branchements indirects. Pour mémoriser l'adresse de destination, on utilise un cache qui mémorise les correspondances entre l'adresse du branchement et l'adresse de destination. Ce cache est appelé le '''''branch target buffer''''' en anglais, qui sera abrévié en BTB dans ce qui suit. Le BTB est une amélioration du tampon d'adresse de branchement vu plus haut, auquel on aurait ajouté les adresses de destination des branchements. Le BTB est utilisé comme suit : on envoie en entrée l'adresse du branchement, le BTB répond au cycle suivant en précisant : s’il reconnaît l'adresse d'entrée, et quelle est l'adresse de destination si c'est le cas. Le BTB peut être un cache totalement associatif, associatif par voie, ou directement adressé, mais ces derniers sont les plus fréquents. Les BTB sont généralement des caches de type directement adressés, où seuls les bits de poids faible de l'adresse du branchement adressent le cache, le reste de l'adresse est tout simplement ignoré. Il existe aussi des BTB qui sont construits comme les caches associatifs à plusieurs voies, mais ceux-ci impliquent généralement la présence de ''tags'', ce qui fait qu'ils sont un peu moins fréquents. [[File:Branch target buffer directement adressé.png|centre|vignette|upright=2|Branch target buffer directement adressé.]] Comme pour tous les caches, un accès au BTB peut entraîner un défaut de cache, c’est-à-dire qu'un branchement censé être dans le BTB n'y est pas. Comme pour les autres caches, les défauts de cache peuvent se classer en trois types : les défauts de cache à froid (''cold miss'') causés par la première exécution d'un branchement, les défauts liés à la capacité du BTB/cache, et les défauts par conflit d'accès au cache. Les défauts liés à la capacité du BTB sont les plus simples à comprendre. La capacité limitée du BTB fait que d'anciens branchements sont éliminées pour laisser la place à de nouveaux. En conséquence, ces branchements peuvent donner des erreurs de prédiction si leur correspondance a été éliminée du cache. On peut réduire des défauts en augmentant la taille du BTB. Les défauts liés aux conflits d'accès au BTB sont eux beaucoup plus intéressants, car la conception du BTB est assez spéciale dans la manière dont sont gérés ce genre de défauts. Le BTB est un cache partiellement associatif, ce qui fait que des défauts de cache par conflit d'accès peuvent avoir lieu. Pour rappel, les défauts par conflit d'accès ont lieu quand deux adresses mémoires se voient attribuer la même ligne de cache. Pour un BTB, cela correspond au cas où deux branchements se voient attribuer la même entrée dans le BTB, ce qui porte le nom d’''aliasing''. Ne pas détecter ce genre de situation sur un cache normal entraînerait des problèmes : la donnée lue/écrite ne serait pas forcément la bonne. Les caches normaux utilisent un système de tags pour éviter ce problème et on s'attendrait à ce que les BTB fassent de même. Mais pour un BTB, l'absence de ''tags'' n'est pas un problème : la seule conséquence est une augmentation du taux de mauvaises prédictions, dont les conséquences en termes de performance peuvent être facilement compensées. Les BTB peuvent donc se passer de tags, ce qui a de nombreux avantages : le circuit est plus rapide, prend moins de portes logiques, consomme moins d'énergie, etc. Ces économies de portes logiques et de performances peuvent être utilisées pour augmenter la taille du BTB, ce qui compense, voire surcompense les mauvaises prédictions induites par l’''aliasing''. Mais ce n'est pas systématique : d'autres BTBs utilisent des ''tags'' pour améliorer le taux de prédiction. Nous ferons donc la différence entre '''BTB tagués''' et '''BTB non-tagués'''. Des processeurs se passent de BTB. À la place, ils mémorisent les correspondances entre branchement et adresse de destination dans les bits de contrôle du cache d'instructions. Mais nous verrons cela en détail dans le chapitre suivant. Plus haut, j'ai dit qu'un processeur moderne utilisait à la fois un prédicteurs rapide et imprécis, avec un prédicteur lent mais précis. Le prédicteur lent a le dernier mot, il corrige ou annule les prédictions du prédicteur rapide. Ce qui lui vaut le nom, en anglais, d'''overiding predictor''. La correction se fait simplement en corrigeant le ''program counter'' et en forçant le décodeur à émettre des NOPs pendant quelques cycles, le temps d'éliminer les instructions chargées à tort. [[File:Double BTB sur les CPU modernes.png|centre|vignette|upright=2|Double BTB sur les CPU modernes.]] Les deux unités de prédiction utilisent des BTB séparés, de taille différente, au moins deux. Vu que les BTB sont des caches, on les appelle des '''BTB de niveau L1 et L2'''. Par exemple, les processeurs Bulldozer d'AMD disposent de deux BTBs : un BTB L1 de 512 entrées, et un BTB L2 de 5120 entrées. Le BTB de niveau L2 est souvent un cache de victime, qui mémorise les branchements retirés de la BTB de niveau L1. La BTB pour les branchements indirects vient en plus de ces deux BTBs, elle complète souvent la BTB de niveau L2. Le ''return stack predictor'' vient en plus des BTB L1 et L2, mais sa petite taille et sa rapidité font qu'il complète l'unité/BTB de niveau L1. Quelques processeurs ont trois niveaux de BTB, avec un niveau L0, L1 et L2. La BTB L0 aliment le cache d'instruction, alors que la L1 et la L2 préviennent les décodeurs d'instruction. La différence entre la L1 et la L2 est que la L2 met plus de temps à prévenir les décodeurs. Les branchements peuvent donc être annulés/forcés à deux étages de décodage différents. Pour donner quelques exemples, les processeurs Zen d'AMD disposent de plusieurs BTBs, avec des niveaux L0, L1 et L2. Le tableau ci-dessous vous donne la taille et la latence de chaque niveau de BTB. La BTB de niveau L0 alimente le cache d'instruction, la L1 permet d'annuler les instructions au premier cycle de décodage, la BTB L2 annule les instructions vers le milieu/fin du décodage. {|class="wikitable" |- ! rowspan="3" | Zen 2 | 16 || 0 |- | 512 || 1 |- | 7168 || 4 |- ! rowspan="3" | Zen 3 | 16 || 0 |- | 1024 || 1 |- | 6656 + 1536 (branchements indirects)|| 4 |} ===La prédiction de destination pour les branchements indirects=== Un BTB classique peut fonctionner pour les branchements indirects. Son seul défaut est qu'il mémorisera la dernière adresse de destination prise par le branchement. Et cela peut fonctionner pour les branchements indirects fortement biaisés, qui ont presque toujours la même adresse de destination. Mais la majorité des branchements indirects change d'adresse de destination régulièrement. Tous les processeurs commerciaux datant d'avant le Pentium M utilisaient un BTB normal pour prédire les branchements indirects. Les processeurs qui les ont suivi sont capables de prédire l'adresse de destination d'un branchement indirect. , grâce à une '''unité de prédiction des branchements indirects''', séparée de l'unité de prédiction de branchement normale. Elle utilise un BTB amélioré, qui mémorise plusieurs adresses de destination pour un seul branchement, en compagnie d'informations pour prédire laquelle est la bonne. Il est possible d'utiliser un BTB unique, pour tous types de branchements, appelé un '''BTB unifié'''. Un BTB unifié a plusieurs adresse de destination par entrée du BTB. Mais une seule est utilisée pour les branchements directs. Vu que les branchements directs sont majoritaires, cela fait beaucoup d'entrées inutilisées. En conséquence, elle est tout sauf optimale, et n'est presque jamais utilisée en pratique. {|class="wikitable" |+ Branch Target Buffer unifié |- ! Adresse du branchement !! Informations de prédiction !! Adresse de destination !! Seconde adresse de destination |- | 0x54462146 || 11101011 || 0x52495674 || 0x24987461 |- | 0x54142446 || 11101101 || 0x15646956 || x0x4158746 |- | 0x25456542 || 10011101 || 0x52495674 || 0x24157461 |- | 0x15455855 || 11010101 || 0x52485754 || 0x24024511 |- | ... || ... || ... || ... |- | ... || ... || ... || ... |- | 0x54462146 || 1001101 || 0x52495674 || 0x24987461 |} Une seconde solution utilise un BTB séparé, distinct du BTB pour les branchements directs. En séparant les deux, on a un BTB simple qui ne mémorise qu'une adresse de destination par branchement, et un BTB pour branchements indirects avec plusieurs adresses de destination par branchement. [[File:BTB avec prédiction de branchements indirects.png|centre|vignette|upright=2.5|BTB avec prédiction de branchements indirects.]] L'idée est que l'on économise des circuits à nombre d'entrées égales. Par exemple, comparons ce que cela donne avec 64 entrées. D'un côté, on a un BTB à 64 entrées, capable de gérer deux adresse de destination par branchement. En pratique, la majorité des branchements sont des branchements directs, qui n'utiliseraient qu'une seule case mémoire. Les circuits du BTB seraient donc sous-utilisés. De l'autre, on a un BTB à 48 entrées pour branchements directs, et un second BTB avec 16 entrées, capable de mémoriser deux adresses par branchements. Le premier BTB utilise moins de circuits, et est utilisé à pleine capacité, il ne gaspille pas de circuits pour mémoriser des adresses de destination vides. Par contre, on perd un peu en flexibilité. L'organisation précédente marche bien si 1/4 des branchements rencontrés sont des branchements indirects. Mais si le ratio est différent, la performance est légèrement sous-optimale. Attention, cela ne veut pas dire qu'il y aura des entrées vides dans un BTB, non. Simplement, le premier BTB risque de manquer de place pour les branchements directs récents, alors que les branchements indirects seront eux bien prédits, même les anciens. À l'opposé, un BTB unique permet de mémoriser les 64 derniers branchements, peu importe qu'ils soient indirects ou non. En clair : un BTB unique est plus flexible, ce qui donne un gain de performance dans certaines situations. Cependant, cet avantage théorique ne tient pas compte de l'économie en circuits, qui peut être utilisée pour faire grossir le BTB pour branchements directs. Par exemple, à budget à transistor équivalent, on a le choix entre BTB à 64 entrées uniques, et un BTB pour branchements directs de 80 entrées avec un BTB indirect de 16 entrées. Le fait qu'un BTB soit plus gros permet des gains de performances qui compensent la perte de flexibilité. On peut ainsi avoir le meilleur des deux monde, à savoir une économie de circuits et les gains en performance qui en découlent, malgré une petite perte de flexibilité. Une troisième solution utilise un BTB normal, mais réserve plusieurs entrées pour un branchement indirect. Par exemple, un branchement indirect qui a trois adresses de destination prendra trois entrées : une par adresse de destination. Mais quelques difficultés surviennent alors. Comment placer trois copies d'un même branchement, alors que ces trois copies ont le même ''program counter'' ? Et que faire pour savoir quelle copie sera prise ? Que faire si l'unité de prédiction de branchement prédit les trois copies comme prises ? La technique du '''''Program Counter'' virtuel''' (''Virtual Program Counter'') résoud ces problèmes d'une manière assez élégante. L'idée est la même que précédemment, à savoir qu'il y a une copie du branchement par adresse de destination, dans le BTB. Mais ces copies n'ont pas exactement le même ''Program counter''. Chaque copie se voit attribuer un ''Program Counter'' virtuel. Et comprendre pourquoi demande de comprendre l'idée sous-jacente. La technique a été inspirée par une optimisation des compilateurs, qui transforme un branchement indirects en une séquence de branchements conditionnels. Par exemple, un branchement indirects qui peut brancher vers les adresses A, B et C est transformé en trois branchements conditionnels : un qui branche vers A, un autre qui branche vers B et un autre vers C. Elle ne marche pas pour tous les branchements indirects, elle demande des circonstances particulières pour fonctionner. Mais l'idée est adaptée pour le ''design'' de l'unité de prédiction de branchement. L'idée est qu'un branchement indirect est déroulé en plusieurs branchements dans le BTB. Les branchements sont traités en séquence : l'unité de prédiction prédit si le premier branchement est pris ou non. S'il est pris, son adresse de destination est envoyée au cache d'instruction. S'il n'est pas pris, l'unité de prédiction tester la seconde copie du branchement, et rebelote. Il teste toutes les copies, une par une, et s’arrête quand il tombe sur un branchement pris. Si aucune copie n'est prise, alors le branchement est prédit comme non-pris. Première remarque : il s'agit d'un processus itératif, où on test un branchement à la fois. Et oui, c'est une prédiction par cycle d'horloge. Prédire un branchement indirect peut donc demander plusieurs cycles d'horloge. Mais ce n'est pas un problème, car le prédicteur peut servir d'''overriding predictor'', d'unité de prédiction lente mais précise. La prédiction peut être utilisée par l'unité de décodage, pour annuler les instructions chargées à tord. Deuxième remarque : comment passer d'un branchement à l'autre ? La première copie a un ''program counter'' normal, qui correspond à l'adresse du branchement. La seconde a un ''program counter'' qui est calculé à partir de cette première adresse, la troisième copie a une adresse calculée à partir de la seconde, etc. Concrètement, n'importe quelle fonction un tant soit peu simple suffit, tant qu'elle est déterministe. L'article qui a proposé cette techniques (''Virtual Program Counter (VPC) Prediction : Very Low Cost Indirect Branch Prediction Using Conditional Branch Prediction Hardware'') se contenait de faire un XOR entre l'adresse précédente et une constante, avec une constante différente par itération. Troisième remarque : l'algorithme demande de faire une parenthèse dans le fonctionnement normal du BTB. Quand un branchement indirect est détecté, il lance une succession de prédiction pour prédire un branchement. L'incrémentation du ''program counter'' normale cesse pendant ce processus. Et cela ne doit être fait que quand un branchement indirect est détecté. Pour cela, le BTB mémorise le type de chaque branchement, sans l'entrée du BTBT : est-ce qu'il est conditionnel, inconditionnel, mais aussi direct ou indirect. Et le type est accesible en sortie du BTB, sur une sortie de quelques bit. Quand l'unité de prédiction remarque qu'un branchement indirect vient de sortir du BTB, alors elle lance le processus. [[File:Virtual program counter.png|centre|vignette|upright=2.5|Virtual program counter]] L'avantage de cette technique est qu'elle s’implémente facilement, son cout en transistors est faible. Elle demande juste d'ajouter quelques circuits autour d'un BTB classique. Elle utilise l'unité de prédiction classique, pas besoin d'une unité de prédiction séparée. Vu qu'il y a un seul BTB, on n'a pas les désavantages d'un BTB séparé pour les branchements indirects. Les entrées du BTB sont réparties entre branchements directs et indirects de manière optimale. Niveau performance, elle est un peu moins bonne que les unités de prédiction ITTAGE qu'on détaillera dans la suite du chapitre. Mais elle est suffisante pour être utilisée sur certains processeurs commerciaux. ===La prédiction de l'adresse de retour d'une fonction=== Presque tous les processeurs conçus après les années 2000 peuvent prévoir l'adresse à laquelle il faudra reprendre lorsqu'une fonction/sous-programme a fini de s’exécuter. Ils font de la '''prédiction de retour de fonction'''. Pour cela, ils possèdent pour une unité de prédiction de branchement spécialisée, appelée le ''return stack predictor'', ou '''''pile de prédiction de retour de fonction'''''. Le terme ''return stack predictor'' étant plus court, nous l'utiliserons dans la suite du cours. Le ''return stack predictor'' est capable de reconnaitre les instructions de retour de fonction, et de prédire l'adresse de retour. Pour comprendre comment elle fait, rappelez-vous le chapitre sur la pile d'appel. Dans ce chapitre, j'avais introduit le concept de ''pile d'adresse de retour'', à savoir une pile d'appel très simplifiée, qui ne contient que les adresses de retour des fonctions en cours d'exécution. Le ''return stack predictor'' est essentiellement composé d'une telle pile d'adresse de retour, avec des circuits pour empiler et dépiler les adresses de retour. Le ''return stack predictor'' doit reconstruire une pile d'adresses de retour, à partir du programme exécuté. La pile d'adresse est mémorisée dans le ''return stack predictor'', elle est totalement séparée de la pile d'appel normale. Le programme exécuté continue d'utiliser la même pile d'appel qu'avant, ce qui fait que les adresses de retour sont dispersées dans la pile d'appel, parfois dans des registres spéciaux du processeur. Mais cela ne pose pas de problèmes pour le processeur, qui reconstruit la pile d'adresse de retour avec l'aide du décodeur. La reconstruction se fait à partir des instructions d'appel et de retour de fonction. Une instruction d'appel de fonction empile une adresse de retour, une instruction de retour de fonction la dépile. Lorsque le décodeur d'instruction reconnait une instruction d'appel de fonction, il extrait l'adresse de retour et l'envoie au ''return stack predictor''. L'adresse de retour est alors empilée, ce qui fait qu'elle se retrouve au sommet de la pile d'adresse de retour. Dépiler une adresse de retour revient à prédire un branchement. Lorsque le ''return stack predictor'' détecte une instruction de retour de fonction, il dépile l'adresse au sommet de la pile. L'adresse est alors envoyée du cache d'instruction, pour l'ire l'instruction adéquate, et le ''program counter'' est mis à jour avec cette adresse. Toute la difficulté revient à détecter les instructions de retour de fonction, sans quoi on ne sait pas quand dépiler l'adresse. La documentation là-dessus n'est pas très fournie, il est difficile de savoir ce qui est fait dans les processeurs modernes. Mais on peut faire quelques suppositions. La première possibilité est l'usage du ''prédécodage'', une technique qui décode partiellement les instructions lors de leur chargement dans le cache d'instruction. Elle sera vue dans le chapitre suivant, mais parlons-en rapidement. Le prédécodage ajoute quelques bits au début de chaque instruction pour préciser si c'est un branchement conditionnel, inconditionnel, un retour de fonction. On peut ainsi savoir rapidement quand dépiler : dès qu'une instruction est lue dans le cache d'instruction, le ''return stack predictor'' vérifie les bits ajoutés et agit en fonction. La seconde possibilité est que le BTB reconnait l'instruction de retour de fonction. Pour chaque branchement, il mémorise non seulement son adresse de retour, mais aussi son type. Par type, on veut dire : si c'est un branchement conditionnel, inconditionnel, un retour de fonction. Les retours de fonction sont donc reconnus à condition qu'ils aient été exécutés auparavant. Il est aussi possible d'avoir un BTB spécialisé dans les retours de fonction, qui est alimenté par les décodeurs. Dès que le décodeur reconnait une instruction de retour de fonction, il ajoute son ''program counter'' dans ce BTB spécialisé. Une dernière possibilité est que le ''return stack predictor'' agit une fois l'instruction partiellement décodée. Le décodeur d'instruction reconnait les instructions de retour de fonction rapidement, en un cycle, et consulte alors le ''return stack predictor''. L'adresse est dépilée, et le décodeur sait où brancher. Il n'a pas besoin de devoir lire l'adresse de retour en mémoire, il la lit depuis le ''return stack predictor'', directement. La prédiction se fait donc assez tard dans le pipeline, quelques instructions ont été chargées à tort. Mais le décodeur peut les annuler, comme il le ferait avec un branchement inconditionnel mal prédit. Le ''return stack predictor'' se base sur les appels et retour de fonctions. Sur un processeur sans prédiction de branchement, tout appel de fonction est couplé à un retour de fonction. Mais avec prédiction de branchement, il se peut que ce ne soit pas le cas. Il arrive qu'un appel de fonction soit placé après un branchement pris/non-pris. S'il est exécuté à tort, l'appel/retour de fonction sera exécuté à tort. Et il peut modifier le ''return stack predictor''. Il y a donc corruption du ''return stack predictor'' par des appels/retour spéculatifs. Heureusement, le ''return stack predictor'' utilise des mécanismes pour réparer sa pile d'adresse de retour. Le mécanisme le plus simple part du principe que le ''return stack predictor'' est fabriqué avec une SRAM est un compteur. Nous avons vu il y a de cela pas mal de chapitres, comment fabriquer une mémoire LIFO (une pile, donc), avec une SRAM et un registre ''sommet de la pile''. Le registre ''sommet de la pile'' indique où se situe le sommet de la pile dans la mémoire SRAM. Le mécanisme de réparation se contente de sauvegarder le registre ''sommet de la pile'', à chaque fois que le processeur effectue une prédiction de branchement. Il dispose pour cela d'une '''pile de récupération''' où il empile les registres "sommet de la pile" à chaque prédiction de branchement. Quand le résultat d'un branchement est connu, il dépile un "sommet de la pile", et soit l'ignore en cas de bonne prédiction, soit l'utilise pour réparer le ''return stack predictor'' en cas de mauvaise prédiction. ==La prédiction de branchement locale== La prédiction de branchement tente de prédire si un branchement sera pris ou non-pris, et décide quelle adresse envoyer au cache en fonction du résultat. Si on prédit qu'un branchement est non pris, on laisse le ''program counter'' faire son travail. À l'inverse si le branchement est prédit comme étant pris, l'adresse de destination est envoyée au cache d'instruction et au ''program counter''. La prédiction de branchement assigne une probabilité qu'un soit branchement soit pris en fonction de ces informations : si la probabilité est de plus de 50%, le branchement est considéré comme pris. La prédiction de branchement se base avant tout sur des statistiques, c’est-à-dire qu'elle détermine la probabilité d’exécution d'un branchement en fonction d'informations assez diverses. La prédiction de branchement n'a d'intérêt que si les prédictions sont suffisamment fiables pour valoir le coup. Rappelons que la pénalité lors d'une mauvaise prédiction est importante, d'autant plus coûteuse que le pipeline est long. Il est généralement admis qu'il faut au minimum un taux de réussite proche de 90%, voire plus sur les processeurs modernes. Heureusement, la plupart des branchements sont des '''branchements biaisés''', c’est-à-dire qu'ils sont presque toujours pris ou presque toujours non-pris, sauf en de rares occasions. De tels branchements font que la prédiction des branchements est facile, bien qu'ils posent paradoxalement quelques problèmes, comme nous le verrons plus bas. Un autre point important est que les unités de prédiction de branchement doivent être très rapides. Idéalement, elles doivent fournir leur prédiction en un seul cycle d'horloge. Un seul cycle d'horloge est un temps très court, surtout sur les ordinateurs avec une fréquence élevée. Les techniques de prédiction dynamique ne peuvent donc pas utiliser des méthodes statistiques extraordinairement complexes. Cela va à l'encontre du fait que le taux de mauvaises prédictions doit être très faible, idéalement inférieur à 1% sur les processeurs modernes. Vous comprenez donc aisément que concevoir une unité de prédiction de branchement est un véritable défi d’ingénierie électronique qui requiert des prouesses technologiques sans précédent. Suivant la nature des informations utilisées, on peut distinguer plusieurs types de prédiction de branchement : locale, globale, dynamique, statique, etc. Nous allons d'abord voir les méthodes statiques avant de voir les méthodes dynamiques. La '''prédiction locale''' prédit chaque branchement indépendamment les uns des autres. Elle sépare bien les statistiques/moyennes pour chaque branchement. Et c'est autant un point fort qu'un point faible. En effet, elle n'exploite pas les corrélations entre branchements, à savoir le fait que l'exécution d'un branchement a tendance à déborder sur les suivants. Dans ce qui suit, nous allons voir les techniques de prédiction locales. ===Les ''branch hints''=== Dans son implémentation la plus explicite, la prédiction est inscrite dans le branchement lui-même. Quelques bits de l'opcode du branchement précisent si le branchement est majoritairement pris ou non pris. Ils permettent d'influencer les règles de prédiction de branchement et de passer outre les réglages par défaut. Ces bits sont appelés des '''suggestions de branchement''' (''branch hint''). Mais tous les processeurs ne gèrent pas cette fonctionnalité. Et de plus, cette solution marche assez mal. La raison est que le programmeur ou le compilateur doit déterminer si le branchement est souvent pris ou non-pris, mais qu'il n'a pas de moyen réellement fiable pour cela. Une solution possible est d’exécuter le programme sur un ensemble de données réalistes et d'analyser le comportement de chaque branchement, afin de déterminer les suggestions de branchement adéquates, mais c'est une solution lourde et peu pratique, qui a de bonnes chances de donner des résultats peu reproductibles d'une exécution à l'autre. ===La prédiction statique de branchement=== La '''prédiction statique''' prédit le résultat du branchement en fonction de caractéristiques fixes du branchement lui-même, comme son adresse, son mode d'adressage, l'adresse de destination, la position du branchement en mémoire, si le branchement est direct ou indirect, etc. Les informations en question sont connues une fois le branchement décodé, il n'y a pas besoin de mémoriser la moindre information supplémentaire. Une première implémentation, assez évidente, fait la différence entre les branchements inconditionnels toujours pris, et les branchements conditionnels au résultat variable. L'idée est de prédire les branchements inconditionnels comme toujours pris alors que les branchements conditionnels sont prédits comme non-pris (ce qui est une approximation). L'implémentation est relativement simple : on utilise un BTB qui ne mémorise que les branchements inconditionnels, et basta ! Les branchements conditionnels sont simplement ignorés, traités comme n'importe quelle autre instruction. Cette méthode est particulièrement inefficace pour les branchements de boucle, où la condition est toujours vraie, sauf en sortie de boucle ! Il a donc fallu affiner légèrement l'algorithme de prédiction statique. Une implémentation plus subtile fait la différence entre les branchements des boucles et les autres. Reste à identifier ceux-ci d'une manière ou d'une autre. Et un bon moyen est de regarder si le branchement revient en arrière ou au contraire saute une portion de code. Un programme s'exécute des adresses basses vers les adresses hautes, les instructions vont naturellement dans le sens croissant des adresses. Un branchement de boucle fait revenir en arrière, histoire de répéter un morceau de code, pas les autres branchements (du moins pas forcément). Et cela nous amène à faire la distinction entre les branchements conditionnels ascendants et descendants. Un '''branchement conditionnel ascendant''' est un branchement qui demande au processeur de reprendre plus loin dans la mémoire : l'adresse de destination est supérieure à l'adresse du branchement. Un branchement '''conditionnel descendant''' a une adresse de destination inférieure à l'adresse du branchement : le branchement demande au processeur de reprendre en arrière dans la mémoire, avant le branchement. Les branchements ascendants sont rarement pris (ils servent dans les conditions de type SI…ALORS), contrairement aux branchements descendants (qui servent à fabriquer des boucles). On peut ainsi modifier l’algorithme de prédiction statique comme suit : * les branchements inconditionnels sont toujours pris ; * les branchements descendants sont toujours pris ; * les branchements ascendants ne sont jamais pris. L'implémentation demande d'élargir le BTB. Le BTB n'a pas seulement à mémoriser l'adresse du branchement et son adresse de destination, mais aussi le type du branchement. En général, il se contente de deux bits, qui indiquent si le branchement est conditionnel, inconditionnel, ou un retour de fonction. Les retours de fonction sont traités à part, histoire de profiter du ''return stack predictor''. {|class="wikitable" |+ BTB avec prédiction de branchement statique évoluée |- ! Adresse du branchement !! Adresse de destination !! Type du branchement |- | 0x4165485 || 0x14657445541 | style="background: #F0F000" | Conditionnel |- | ... || ... | style="background: #F0F000" | Inconditionnel |- | ... || ... | style="background: #F0F000" | Conditionnel |- | ... || ... | style="background: #F0F000" | Conditionnel |- | ... || ... | style="background: #F0F000" | Retour de fonction |- | ... || ... | style="background: #F0F000" | Inconditionnel |- | ... || ... | style="background: #F0F000" | Inconditionnel |- | ... || ... | style="background: #F0F000" | Conditionnel |- | ... || ... || ... |} ===La prédiction avec des compteurs à saturation=== Les méthodes de prédiction de branchement statique sont intéressantes, mais elles montrent rapidement leurs limites. Pour plus de performances, il faut utiliser la '''prédiction dynamique''', qui extrait des statistiques sur l’exécution des branchements. Pour le reste du chapitre, toutes les techniques utilisent la prédiction dynamique, qu'elles soient locales ou globales. Sa version la plus simple se contente de mémoriser ce qui s'est passé lors de l’exécution précédente du branchement. Si le branchement a été pris, alors on suppose qu'il sera pris la prochaine fois. De même, s'il n'a pas été pris, on suppose qu'il ne le sera pas lors de sa prochaine exécution. Pour cela, chaque entrée du BTB contient un bit qui mémorise la dernière exécution du branchement : 1 s'il a été pris, 0 s'il n'a pas été pris. C'est ce qu'on appelle la '''prédiction de branchements sur 1 bit'''. Au vu de sa simplicité, il ne faut pas s'attendre à des miracles. La méthode fonctionne bien pour les branchements des boucles et les branchements inconditionnels, mais elle n'est pas assez performante. Une forme plus élaborée de prédiction utilise des '''compteurs à saturation'''. Un compteur à saturation est un compteur qui est incrémenté à chaque fois qu'un branchement est pris, décrémenté s'il est non-pris. Le compteur est initialisé à la moitié de sa valeur maximale, ce qui correspond à une probabilité proche de 50%. Les compteurs à saturation sont très utilisés et pas seulement pour de la prédiction locale, les méthodes globales en utilisent aussi. Pour faire la prédiction, l'unité de prédiction regarde le bit de poids fort du compteur. Le branchement est considéré comme pris si ce bit de poids fort est à 1, et non pris s'il vaut 0. En clair : on considère que le branchement est pris si le compteur indique une probabilité supérieure à 50%. [[File:Compteur à saturation.png|centre|vignette|upright=2|Compteur à saturation.]] : Pour la culture générale : le compteur à saturation du Pentium 1 était légèrement bogué, ce qui fait que sa prédiction de branchement était sous-optimale. La plupart des processeurs utilisent un compteur à saturation par branchement, ce qui veut dire un compteur à saturation par entrée dans le BTB. Vu chaque compteur est associé à une entrée du BTB, le phénomène d’''aliasing'' mentionné plus haut peut perturber les prédictions de branchement. Deux branchements peuvent se voir associés à la même entrée du BTB, et agir sur le même compteur à saturation, ce qui entraine l'apparition d''''interférences entre branchements'''. L'interférence peut avoir des effets positifs, neutres ou négatifs, suivant la corrélation entre les deux branchements. L’''aliasing'' n'est pas un problème si les deux branchements sont fortement corrélés, par exemple si les deux sont tout le temps pris ou tout le temps non-pris. Si les deux branchements vont dans le même sens, l'interférence est neutre, voire légèrement positive. Mais si l'un est souvent pris et l’autre souvent non-pris, l'interférence est négative. Les deux branchements vont se marcher dessus sans vergogne, chacun interférant sur les prédictions de l'autre ! Il est rare que l’''aliasing'' ait un impact significatif sur les unités de prédiction des deux paragraphes précédents. Il se manifeste surtout quand la BTB est très petite et la seule solution est d'augmenter la taille du BTB. ===La prédiction avec un historique local=== La prédiction avec des compteurs à saturation est très simple, mais il est possible de créer une implémentation alternative, très proche, avec des avantages et désavantages différents. Un compteur à saturation enregistre l'historique d'un branchement, à savoir ses dernières exécutions. L''''historique''' d'un branchement dit quel a été son résultat dans le passé, pour ses exécutions précédentes. Et il est possible d'enregistrer cet historique et l'utiliser pour faire des prédictions. Par exemple, prenons un branchement sont ses 6 dernières exécutions sont "pris, non-pris, pris, pris, pris, non-pris". Le processeur peut encoder cet historique sur 6 bits. Un branchement pris correspond à un bit à 1, un branchement non-pris correspond à un 0. Le bit de poids fort correspond à l'exécution la plus ancienne, le bit de poids faible à l'exécution la plus récente. Par exemple, si l'historique contient 010, cela veut dire que le branchement a été non pris, puis pris, puis non pris. L'historique d'un branchement est appelé son '''historique local''', mais nous parlerons simplement l'historique. Le processeur peut mémoriser l'historique de chaque branchement. Pour cela, il réserve n bits par branchements, pour mémoriser ses n exécutions précédentes. L'historique d'un branchement est mémorisé dans son entrée du BTB. Et plus précisément dans un champ séparé qui est alimentée comme un registre à décalage. Reste à exploiter cet historique local pour faire des prédictions. Une idée assez simple serait de l'utiliser pour calculer une moyenne des N exécutions précédentes. Si la probabilité d'être pris est supérieure à 50 %, le branchement est considéré comme pris. Dans le cas contraire, il est considéré comme non pris. Le calcul de la moyenne utilise une simple porte à majorité, qui prend en entrée tous les bits de l'historique. Cependant, cette méthode est équivalente à utiliser un compteur à saturation par branchement. La sortie de la porte à majorité est équivalente à ce qu'on aurait dans un compteur à saturation. La seule différence : le cout en circuit et la simplicité de conception. Prenons l'exemple des premiers processeurs PA RISC. Ils mémorisaient, pour chaque branchement, les trois dernières exécutions du branchement, avec trois bits par entrée du BTB. La prédiction était réalisée avec une porte à majorité, dont le résultat était utilisé comme prédiction. Ces processeurs ont préféré utiliser un historique de 3 bits, car il était plus simple à concevoir qu'un compteur à saturation équivalent de deux bits. Il suffisait d'alimenter un registre à décalage avec un bit, pas besoin d'incrémenter ou de décrémenter un compteur, pas besoin de signaux d'incrémentation/décrémentation séparés, etc. Mais pour des historiques plus longs, la donne s'inverse et des compteurs à saturation de deux-trois bits l’emportent. Un défaut de la méthode précédente, qui est partagée avec les compteurs à saturation, est qu'elle marche mal pour les branchements qui suivent un ''pattern''. Je veux dire par là que l'exécution d'un branchement suit un cycle, par exemple pris, pris, non-pris, pris, pris, non-pris, et ainsi de suite en boucle. Notons que l'apparition de tels motifs correspond le plus souvent à la présence de boucles dans le programme. Quand une boucle s’exécute, les branchements qui sont à l'intérieur tendent à exprimer de tels motifs. Avec de tels motifs, les compteurs à saturation feront des prédictions incorrectes, là où les prédicteurs qu'on va voir font des prédictions parfaites. Par exemple, prenons un branchement qui suit le ''pattern'' pris, pris, pris, non-pris. Si l'historique local vaut 1110, le branchement est censé refaire une boucle et être pris. Et certes, on a supposé que l'historique faisait 4 bits. Mais le''pattern'' sera visible tant que l'historique fait plus de 4 bits. Par exemple, le ''pattern'' serait 01110 pour un historique local de 5 bits, 101110 pour un historique local de 6 bits, 1101110 pour un historique local de 7 bits, etc. Un ''pattern'' correspond donc à une valeur bien précise de l'historique local. L'historique local permet de voir ces cycles, reste à les exploiter. Prédire correctement les ''pattern'' demande simplement d'associer un compteur à saturation à chaque valeur possible de l'historique local. Le compteur à saturation dira, quand tel pattern est rencontré, si le branchement sera pris ou non-pris par la suite. Au total, il faut donc un registre d'historique local de n bits couplé à 2^n compteurs à saturation. Et ce pour chaque branchement possible. Les compteurs à saturation sont regroupés dans une '''''Pattern History Table''''', que nous noterons PHT dans ce qui suit. Le résultat est une '''unité de prédiction à deux niveaux locale''', qui contient plusieurs registres d'historique et tout autant de PHT locales. En tout, il y a une PHT et un historique par branchement, donc par entrée du BTB. Quand un branchement est exécuté, son historique local indique quel compteur à saturation choisir dans la PHT locale. En général, l'historique local est mémorisé dans le BTB, reste à gérer la PHT. [[File:Unité de prédiction à deux niveaux purement locale.png|centre|vignette|upright=2.5|Unité de prédiction à deux niveaux avec des historiques et des PHT locales.]] Une unité de prédiction locale à deux niveaux contient plusieurs PHT, reste à savoir quelle PHT correspond à tel branchement. La correspondance se fait idéalement à partir de l'adresse du branchement, mais c'est là une implémentation idéale, qui demande beaucoup de circuits. Généralement, l'unité de prédiction n'utilise que les bits de poids faible de l'adresse du branchement, ce qui permet de faire un choix correct, mais avec une possibilité d'''aliasing''. Il est aussi possible de séparer l'historique local du BTB. Les historiques locaux sont alors mémorisés dans une mémoire RAM dédiée, appelé la '''''Branch History Table''''', ou encore la '''table des historiques locaux''', que nous noterons BHT dans ce qui suivra. Chaque byte de la BHT contient l'historique local associé à un branchement. Pour récupérer l'historique local voulu, l'adresse du branchement est envoyée à la BHT, sur les entrées d'adresse de la BHT, directement. Seuls les bits de poids faible de l'adresse sont utilisés. L'historique local est ensuite envoyé à la PHT adéquate, choisie en fonction des mêmes bits de poids faible du PC. Un bon moyen pour cela est d'accéder à toutes les PHT en parallèle, mais de sélectionner la bonne avec un multiplexeur, ce dernier étant commandé par les bits de poids faible du PC. [[File:Table des historiques locaux.jpg|centre|vignette|upright=2|Table des historiques locaux]] Un défaut des unités de prédiction purement locales de ce type est leur cout en termes de circuits. Utiliser un registre d'historique et une PHT par branchement a un cout en transistor élevé, avec tous les défauts que ca implique en termes de consommation électrique et thermique. Elles ont aussi des temps de calcul un peu plus important que les unités purement globales, mais pas de manière flagrante. Les gains en performance avec un historique local s'observent surtout pour les branchements qui sont dans des boucles ou pour les branchements utilisés pour concevoir des boucles, alors que l'implémentation globale marche bien pour les if..else (surtout quand ils sont imbriqués). Les deux sont donc complémentaires. Dans les faits, elles sont rarement utilisées seules du fait de leurs défauts, au profit d'unités de prédiction hybrides, qui mélangent historiques et PHT locaux et globaux. ==La prédiction de branchement globale/mixte== Utiliser un historique local avec une PHT est très puissant. Mais le cout en circuit est très important. Cependant, on peut adapter l'idée pour faire de la prédiction globale. La '''prédiction globale''' fait des prédictions holistiques, qui tiennent compte de tous les branchements, sans les traiter séparément. Elle ne sépare pas les branchements, tous sont mis dans le même panier. La prédiction globale fait donc le compromis inverse : elle exploite les corrélations entre branchements, mais perd les informations statistiques précise pour chaque branchement. L'idée est qu'au lieu d'utiliser un historique par branchement, on utilise un '''historique global''' qui mémorise les exécutions de tous les branchements conditionnels. L'historique enregistre les N exécutions de branchements conditionnels. L'historique global est mémorisé dans un registre unique, appelé le '''registre d'historique global'''. C'est un registre à décalage mis à jour à chaque fois que le processeur exécute un branchement : on fait rentrer un 1 si le branchement est pris, et un 0 sinon. Une unité de prédiction globale utilise cet historique pour faire sa prédiction. L'unité de prédiction globale utilise un compteur à saturation pour chaque valeur possible du registre d'historique. En clair, pour un registre de N bits, elle utilise 2^n compteurs à saturation. Là encore, les compteurs à saturation sont regroupés dans une ''Pattern History Table''. Nous parlerons de '''PHT globale''' pour désigner une PHT commandée par un historique global, de ''PHT locale'' si elle est adressée par un historique local. [[File:Prédiction dynamique à deux niveaux.png|centre|vignette|upright=2|Prédiction dynamique à deux niveaux.]] Il est admis que l'historique global donne de meilleures prédictions que l'historique local. Mais les deux sont complémentaires, ce qui fait qu'il existe des approches hybrides. Les approches hybrides exploitent à la fois les statistiques pour chaque branchement et les corrélations entre branchements. Les prédicteurs hybrides ont de meilleures performances que les prédicteurs purement globaux ou locaux. Avec un historique global, la prédiction tient compte d'éventuelles corrélations entre branchements consécutifs/proches pour faire les prédictions. C'est un avantage pour les applications qui enchaînent des if...else ou qui contiennent beaucoup de if...else imbriqués les uns dans les autres, qui s’exécutent plusieurs fois de suite. Le résultat de chaque if...else dépend généralement des précédents, ce qui rend l'utilisation d'un historique global intéressant. Par contre, ils sont assez mauvais pour le reste des branchements. Mais cette qualité devient un défaut quand elle détecte des corrélations fortuites ou parasites, inutiles pour la prédiction (corrélation n'est pas causalité, même pour prédire des branchements). Du fait de ce défaut, la prédiction globale a besoin de registres d'historiques globaux très larges, de plusieurs centaines de bits au mieux. [[File:2 level branch predictor.svg|centre|vignette|upright=2|Unités de prédiction de branchement à deux niveaux avec une seule PHT.]] Le circuit précédent a cependant un problème : si deux branchements différents s'exécutent et que l'historique est le même, le processeur n'y verra que du feu. Il y a alors une interférence, à savoir que les deux branchements vont agir sur le même compteur à saturation. On se retrouve alors dans une situation conceptuellement identique à l’''aliasing'' dans le BTB ou avec des compteurs à saturation. Sauf que les interférences sont alors beaucoup plus nombreuses et qu'elles sont clairement un problème pour les performances ! Mitiger les interférences devient alors bien plus important qu'avec les unités de prédiction précédentes. Heureusement, si augmenter la taille de la PHT peut mitiger le problème, d'autres solutions sont possibles sur les unités de prédiction globales. Elles sont au nombre de deux : mitiger les interférences liées aux branchements biaisés, ajouter des informations qui discriminent les branchements. Voyons ces solutions dans le détail. ===La mitigation des interférences par usage de l'adresse de branchement=== La première solution pour réduire l'impact de l’''aliasing'' est d'augmenter la taille de la PHT et de l'historique. Plus l'historique et la PHT sont grands, moins l’''aliasing'' est fréquent. Mais avoir des historiques et des PHT de très grande taille n'est pas une mince affaire et le cout en termes de performances et de portes logiques est souvent trop lourd. Une autre solution consiste à utiliser, en plus de l'historique, des informations sur le branchement lui-même pour choisir le compteur à saturation à utiliser. Typiquement, on peut utiliser l'adresse du branchement en plus de l'historique, pour choisir le compteur à saturation adéquat. Pour être précis, on n'utilise que rarement l'adresse complète du branchement, mais seulement les bits de poids faible. La raison est que cela fait moins de bits à utiliser, donc moins de circuits, mais l’''aliasing'' est juste atténué, pas éliminé. Des branchements différents ont beau avoir des adresses différentes, les bits de poids faible de leurs adresses peuvent être identiques. Des confusions sont donc possibles, mais sont assez rares pour que cela suffise en pratique. Une unité de prédiction de ce type est illustrée ci-dessous. Il y a plusieurs PHT séparées, donc plusieurs ensembles de 2^n compteurs à saturation. Le choix de la PHT est réalisé par l'adresse du branchement, alors que le choix du compteur à saturation est réalisé par l'historique. Les compteurs à saturation d'un branchement sont mis à jour seulement quand le branchement s'est chargé pendant que l'historique associé était dans le registre d'historique. Cette méthode a cependant le défaut de gâcher énormément de transistors. [[File:Unité de prédiction de branchement basée sur des compteurs à saturation sélectionnés par l'historique global.jpg|centre|vignette|upright=2|Unité de prédiction de branchement basée sur des compteurs à saturation sélectionnés par l'historique global]] D'autres unités de prédiction fonctionnent sur le même principe que l'unité précédente, sauf que les différentes PHTs sont fusionnées en une seule grosse PHT. C'est ce que font les unités de prédiction '''''gshare''''' et '''''gselect''''', ainsi que leurs dérivées. Avec les unités de prédiction '''''gselect''''', on concatène les bits de poids faible de l'adresse du branchement et l'historique pour obtenir le numéro du compteur à saturation à utiliser. [[File:Prédiction « gselect ».png|centre|vignette|upright=2|Prédiction « gselect ».]] Avec les unités de prédiction '''''gshare''''', on fait un XOR entre le registre d'historique et les bits de poids faible de l'adresse du branchement. Le résultat de ce XOR donne le numéro du compteur à utiliser. Avec cette technique, on utilise une PHT globale et un historique global, mais le registre d'historique est manipulé de manière à limiter l'''aliasing''. [[File:Prédiction « gshare ».png|centre|vignette|upright=2|Prédiction « gshare ».]] Intuitivement, on pourrait croire que les unités de prédiction gselect ont de meilleures performances. C'est vrai que les unités gshare combinent l'adresse du branchement et l'historique d'une manière qui fait perdre un peu d'information (impossible de retrouver l'adresse du branchement et l'historique à partir du résultat du XOR), alors que les unités gselect conservent ces informations. Mais il faut prendre en compte le fait que les deux unités doivent se comparer à PHT identique, de même taille. Prenons par exemple une PHT de 256 compteurs, adressée par 8 bits. Avec une unité gselect, les 8 bits sont utilisés à la fois pour l'historique et pour les bits de poids faible de l'adresse du branchement. Alors qu'avec une unité gshare, on peut utiliser un historique de 8 bits et les 8 bits de poids faible de l'adresse du branchement. L'augmentation de la taille de l'historique et du nombre de bits utilisés fait que l’''aliasing'' est réduit, et cela compense le fait que l'on fait un XOR au lieu d'une concaténation. Les unités précédentes réduisent l'''aliasing'' en segmentant la PHT : telles entrées sont allouées à un branchement, telles entrées à tel autre branchement, etc. Cependant, l'historique local n'est pas utilisé. Mais quitte à allouer des entrées à un branchement, autant en profiter pour leur associer son historique local. Il s'agit alors d'approches hybrides. Par exemple, on peut citer la '''prédiction mixte''' (''alloyed predictor''). Avec celle-ci, la table des compteurs à saturation est adressée avec la concaténation : de bits de l'adresse du branchement, du registre d'historique global et du registre d'historique local adressé par l'adresse du branchement. [[File:Prédiction mixte.jpg|centre|vignette|upright=2|Prédiction mixte.]] Une version optimisée de ce circuit permet d’accéder à la PHT et à la BHT en parallèle. Avec elle les bits de poids faible de l'adresse du branchement sont concaténés avec l'historique global. Le résultat est ensuite envoyé à plusieurs PHT locales distinctes, en parallèle. Les différences PHT envoient leurs résultats à un multiplexeur, commandé par l'historique local, qui sélectionne le résultat adéquat. L'inconvénient de cette mise en œuvre est que le circuit est assez gros, notamment en raison de la présence de plusieurs PHT séparées. [[File:Alloyed predictor optimisé.jpg|centre|vignette|upright=2|''Alloyed predictor'' optimisé]] ===La mitigation des interférences par la structuration en caches des PHTs=== Les techniques précédentes utilisent les bits de poids faible de l'adresse pour sélectionner la PHT adéquate, ou pour sélectionner le compteur dans la PHT. Mais le reste de l'adresse n'est pas utilisé. Cependant, il est théoriquement possible de conserver les bits de poids fort, afin d'identifier le branchement associé à un compteur. Pour cela, chaque compteur à saturation se voit associé à un ''tag'', qui mémorise le reste de l'adresse du branchement associé au compteur, comme pour les mémoires caches. Lorsque l'unité de prédiction démarre une prédiction, elle récupère les bits de poids fort de l'adresse du branchement et compare ceux-ci avec le ''tag''. S’il y a un ''match'', c'est signe que le compteur est bien associé au branchement à prédire. Dans le cas contraire, c'est signe qu'on fait face à une situation d’''aliasing'' et le compteur n'est pas utilisé pour la prédiction. Le résultat transforme la PHT en une sorte de cache assez particulier, qui associe un compteur à saturation à chaque couple adresse-historique. La technique du paragraphe précédent peut être encore améliorée afin de réduire l’''aliasing''. L’''aliasing'' sur une unité de prédiction de branchement est similaire aux conflits d'accès au cache, où deux données/adresses atterrissent dans la même ligne de cache. Une PHT peut formellement être vue comme un cache directement adressé. Une solution pour limiter ces conflits d'accès à de tels, est de les transformer en un cache associatif à n voies. On peut faire la même chose avec les unités de prédiction de branchement, ce qui revient à dupliquer les PHT, de manière à ce que les bits de poids faible de l'adresse se voient attribuer à plusieurs compteurs à saturation, un par branchement possible. Ce faisant, on réduit les interférences entre branchements. Mais cette technique augmente la quantité de circuits utilisés et la consommation d'énergie, ainsi que le temps d'accès, sans compter qu'elle requiert d'utilisation de ''tags'' pour fonctionner à la perfection. Pour les unités de prédiction de branchement, les mesures à ce sujet ne semblent pas montrer un impact réellement important sur les performances, comparé à une organisation de type directement adressé. Il est possible de pousser la logique encore plus loin en ajoutant des caches de victime et d'autres mécanismes courant sur les caches usuels. ===La mitigation des interférences liées aux branchements biaisés=== L’''aliasing'' a un impact négatif quand deux branchements aliasés (qui sont attribués au même compteur à saturation) vont dans des sens différents : si l'un est non-pris, l'autre a de bonnes chances d'être pris (ou inversement). Or, la plupart des branchements sont biaisés, à savoir très fortement orientés dans une direction qu'une autre (presque toujours pris ou presque toujours non-pris, à plus de 90/99% de chances). Plus un branchement a une probabilité élevée d' être pris ou non-pris, plus sa capacité à interférer avec les autres est forte. Le pire des cas est quand deux branchements sont biaisés mais dans des directions inverses : l'interférence est maximale. En conséquence, les branchements biaisés ou quasi biaisés sont les plus problématiques pour l’''aliasing''. Or, il est possible de concevoir des prédicteurs de branchements qui atténuent fortement les interférences des branchements biaisés ou quasi biaisés. C’est le cas de l’''agree predictor'' et de l'unité de prédiction bimodale, que nous allons voir dans ce qui suit. Les branchements très souvent pris vont interférer très fortement avec les branchements très souvent non-pris, et inversement. Par contre, les branchements très souvent pris n'interféreront pas entre eux, de même que les branchements non-pris iront bien ensemble. D'où l'idée de séparer ces deux types de branchements dans des PHT séparées, pour éviter le mauvais ''aliasing''. L''''unité de prédiction bimodale''' part d'une unité gshare, et sépare la PHT globale en deux : une PHT dédiée aux branchements qui sont très souvent pris et une autre pour les branchements très peu pris. Les deux PHT fournissent chacune une prédiction. La bonne prédiction est choisie par un multiplexeur commandé par une unité de sélection, qui se charge de déduire quelle unité a raison. Cette unité de sélection est une unité de prédiction basée sur des compteurs à saturation de 2 bits. On peut encore améliorer l'unité de sélection de prédiction en n'utilisant non pas des compteurs à saturation, mais une unité de prédiction dynamique à deux niveaux, ou toute autre unité vue auparavant. [[File:Prédiction bimodale.jpg|centre|vignette|upright=2|Prédiction bimodale.]] La '''prédiction par consensus''' (''agree predictor'') combine une unité de prédiction à historique global (idéalement de type gshare ou gselect, mais une unité normale marche aussi) et des compteurs à saturation. Il s'agit techniquement d'une technique de prédiction mixte, à la fois globale et locale. Le BTB intègre un compteur à saturation de un bit, qui indique la direction privilégiée du branchement. L'unité à historique global a un fonctionnement changé : elle calcule non pas la probabilité que le branchement soit pris ou non-pris, mais la probabilité que le résultat du branchement soit compatible avec le résultat de l'unité de prédiction de 1 bit. La prédiction finale vérifie que ces deux circuits sont d'accord, en faisant un NXOR entre les résultats des deux unités de prédiction de branchement. [[File:Prédiction par consensus.png|centre|vignette|upright=2|Prédiction par consensus.]] Des calculs simples de probabilités montrent que l'''agree predictor'' a des résultats assez importants. Ses résultats sont d'autant meilleurs que les branchements sont biaisés et penchent fortement vers le côté pris ou non-pris. ==La prédiction de branchement avec des perceptrons== Les méthodes précédentes utilisent au moins un compteur à saturation par historique possible. Sachant qu'il y a 2^n valeurs possibles pour un historique de n bits, le nombre de compteurs à saturation augmente exponentiellement avec la taille de l'historique. Ce qui limite grandement la taille de l'historique, alors qu'on aurait au contraire besoin d'un historique assez large pour faire des prédictions excellentes. Pour contourner le problème, des alternatives basées sur des techniques d'apprentissage artificiel (''machine learning'') existent. Un exemple est celui des unités de prédiction de branchement dites de ''neural branch prediction'', basée sur des perceptrons. Dans ce qui suit, nous les appelerons des '''unités perceptron'''. Les perceptrons sont un algorithme d'apprentissage automatique très simple, ce qui fait que les explications qui vont suivre devraient être simples. En théorie, il est possible d'utiliser des techniques d'apprentissage automatique plus élaborées, mais cela n'est pas possible en pratique. Rappelons qu'une unité de prédiction de branchement doit idéalement fournir sa prédiction en un cycle d'horloge. L'implémentation d'un perceptron est déjà problématique de ce point de vue, car elle demande d'utiliser beaucoup de circuits arithmétiques complexes (multiplication et addition). Autant dire que les autres techniques de ''machine learning'', encore plus gourmandes en calculs, ne sont pas praticables. ===Les perceptrons et leur usage en tant qu'unité de prédiction de branchements=== L'idée derrière les unités perceptron est que certains bits de l'historique sont plus importants que d'autres. En soi, ce genre de situation est réaliste. Il arrive que certains branchements soient pris uniquement si les deux branchements précédents ne le sont pas, ou que si l'avant-dernier branchement est lui aussi pris. Mais les autres résultats de branchement présents dans l'historique ne sont pas utiles. En conséquence, deux historiques semblables, qui ne sont différents que d'un ou deux bits, peuvent donner des prédictions presque identiques. Dans ce cas, on peut faire la prédiction en n'utilisant que les bits identiques entre ces historiques, ou du moins en leur donnant plus d'importance qu'aux autres. On exploite alors des corrélations avec certains bits de l'historique, plutôt qu'avec l'historique entier lui-même. Pour coder ces corrélations, on associe un coefficient à chaque bit de l'historique, qui indique à quel point ce bit est important pour déterminer le résultat final. Ce coefficient est proportionnel à la corrélation entre le bit de l'historique associé, et le résultat du branchement à prédire. Les coefficients sont des nombres entiers qui peuvent être positifs, nuls ou négatifs. Un coefficient positif signifie que si le branchement associé a été pris, alors le branchement à prédire a de bonnes chances de l'être aussi (et inversement). Un coefficient nul signifie que les deux branchements sont indépendants et que le bit de l'historique associé n'est pas à prendre en compte. Pour un coefficient négatif, cela signifie que si le branchement associé a été pris, alors le branchement à prédire a de bonnes chances d'être non-pris (et inversement). Les coefficients en question sont généralement compris entre -1 et 1. Une fois qu'on connait ces coefficients de corrélations, on peut calculer la probabilité que le branchement à prédire soit pris, avec des calculs arithmétiques simples. Dans les calculs qui vont suivre, un branchement pris est codé par un 1, alors qu'un branchement non-pris est codé par un -1 ! Ce détail permet de simplifier grandement les calculs. Dans sa version la plus simple, le perceptron calcule un nombre Z qui est positif ou nul si le branchement est pris, négatif s'il ne l'est pas. Tous les coefficients <math>p_i</math> sont alors des nombres relatifs, pouvant être positifs, nuls ou négatifs. Ils sont généralement compris entre -1 et 1. La formule devient donc celle-ci : : <math>Z = w_0 + \sum_i (h_i \times w_i)</math> [[File:ArtificialNeuronModel francais.png|centre|vignette|upright=2|Perceptron.]] : Sur le plan mathématique, le perceptron effectue un produit scalaire entre deux vecteurs : l'historique et le vecteur des poids. Choisir les coefficients adéquats est le but de l'algorithme du perceptron. L'unité de prédiction part de poids par défaut, qui sont mis à jour à chaque bonne ou mauvaise prédiction. Toute la magie de cet algorithme tient dans la manière dont sont mis à jour les poids. L'idée est de prendre le vecteur des poids, puis d'ajouter ou soustraire l'historique suivant le résultat du branchement. Les poids évoluent ainsi à chaque branchement, améliorant leurs prédictions d'une exécution à l'autre. La règle de mise à jour des poids est donc la suivante : : <math>w_i \leftarrow w_i + t \times h_i</math>, avec t = 1 pour un branchement pris, -1 pour un branchement non-pris. ===L'implémentation matérielle des perceptrons et ses optimisations=== Les calculs réalisés par un perceptrons sont simples, juste des multiplications et des additions et cela se sent dans la conception du circuit. L'unité perceptron utilise un perceptron par entrée du BTB, un par branchement pour simplifier. Pour cela, on utilise une mémoire SRAM qui mémorise les poids de chaque perceptron. La SRAM est adressée par les bits de poids faible du ''program counter'', de l'adresse du branchement. Une fois les poids récupérés, ils sont envoyés à un circuit de calcul de la prédiction, composé de circuits multiplieurs suivis par un additionneur multi-opérande. Le circuit de mise à jour des poids récupère la prédiction, les poids du perceptron, mais aussi le résultat du branchement. La mise à jour étant une simple addition, le circuit est composé d'additionneurs/soustracteurs, couplés à des registres pour mémoriser la prédiction et les poids du perceptron en attendant que le résultat du branchement soit disponible. Vu qu'il y a un délai de quelques cycles avant que le résultat du branchement soit disponible et que les prédictions doivent continuer pendant ce temps, les poids du perceptron et la prédiction sont stockés dans des FIFOs lues/écrites à chaque cycle. [[File:Unité de prédiction de branchement basée sur des perceptrons.png|centre|vignette|upright=2|Unité de prédiction de branchement basée sur des perceptrons]] Rien de bien compliqué sur le principe, mais rappelons que le perceptron doit fournir un résultat en moins d'un cycle d'horloge, et cela tient compte de l'accès au BTB. C'est un temps très court, surtout pour un circuit qui implique des multiplications. Les multiplications prennent facilement deux à trois cycles d'horloge. Autant dire que si on ajoute le temps d'accès à une petite SRAM, pour récupérer le perceptron, c'est presque impossible. Mais quelques optimisations simples permettent de rendre le calcul plus rapide. Premièrement, la taille de la SRAM est réduite grâce à quelques économies assez simples. Notamment, le perceptron utilise des poids codés sur quelques bits, généralement un octet, parfois 7 ou 5 bits, guère plus. Les poids sont encodés en complément à 1 ou en complément à 2, là où les perceptrons normaux utilisent des nombres flottants. Rien que ces deux choix simplifient les circuits et les rendent plus rapides. Le désavantage d'utiliser peu de bits par poids est une perte mineure en termes de taux de prédiction, qui est plus que compensée par l'économie en portes logiques, qui permet d'augmenter la taille de la SRAM. D'autres optimisations portent sur le circuit de calcul. Par exemple, la multiplication <math>h_i \times w_i</math> est facultative. Vu que l'historique contient les valeurs 1 et -1, il suffit d'additionner le poids associé si la valeur est 1 et de le soustraire s'il vaut -1. On peut même simplifier la soustraction et se limiter à une complémentation à un (une inversion des bits du poids). En faisant cela, les circuits multiplieurs disparaissent et le circuit de prédiction se résume à un simple additionneur multi-opérande couplé à quelques inverseurs commandables. Certains perceptrons prennent en compte à la fois l'historique global et l'historique local pour faire leur prédiction. Les deux historiques sont simplement concaténés et envoyés en entrée du perceptron. Cela marche assez bien, car les perceptrons peuvent utiliser des historiques de grande taille sans problèmes. Par contre, il y a besoin d'ajouter une ''branch history table'' au circuit, ce qui demande des portes logiques en plus, mais aussi un temps de calcul supplémentaire (l'accès à cette table n'est pas gratuit). ===Les avantages et inconvénients des perceptrons pour la prédiction de branchements=== L'avantage des unités perceptron est qu'elles utilisent un nombre de portes logiques qui est proportionnel à la taille de l'historique, et non pas exponentiel. Cela permet d'utiliser un historique de grande taille, et donc d'obtenir un taux de bonnes prédictions très élevé. Leur désavantage est que leurs performances de prédiction sont moins bonnes à historique équivalent. Les unités perceptrons ont des taux de prédiction élevés, mais seulement quand certaines conditions mathématiques sont respectées par les historiques. La condition en question est que les historiques correspondants à un branchement pris et les historiques où ce même branchement est non-pris doivent être linéairement séparables. Heureusement, les branchements des programmes informatiques sont une majorité à respecter la condition de séparation linéaire, ce qui rend les perceptrons parfaitement adaptés à la prédiction de branchements. La notion de linéairement séparable est un peu difficile à comprendre. Pour l'expliquer, imaginez que les N bits de l'historique forme un espace à N-dimensions discrets. Chaque historique est un point dans cet espace N-dimensionnel et chaque bit sert de coordonnée pour se repérer dans cet espace. Une fonction est linéairement séparable si l'espace N-dimensionnel peut être coupé en deux par un hyperplan : d'un côté de ce plan se trouvent les historiques des branchements pris, de l'autre se trouvent les historiques des branchements non-pris. Cet hyperplan est défini par l'ensemble des points qui respecte l'équation suivante : : <math>w_0 + \sum_i (h_i \times w_i) = 0</math> Un exemple où cette condition est respectée est quand le résultat d'une prédiction se calcule avec un ET entre plusieurs branchements de l'historique. Si un branchement est pris quand plusieurs branchements de l’historique sont tous pris ou tous non-pris, la condition est respectée et le perceptron donnera des prédictions correctes. Un exemple où cette condition n'est pas respectée est un banal XOR. Prenons l'exemple d'un historique global de 2 bits. Imaginons que le branchement à prédire soit pris : soit quand le premier branchement de l'historique est pris et le second non-pris, soit quand le premier est non-pris et le second pris. Concrètement, la prédiction exacte se calcule en faisant un XOR entre les deux bits de l'historique. Dans ce cas, la condition "linéairement séparable" n'est pas respectée et le perceptron n'aura pas des performances optimales. Les unités perceptron utilisent idéalement un perceptron par branchement. Cela demande d'associer, l'adresse du branchement pour chaque perceptron, généralement en donnant un perceptron par entrée du BTB. Mais une telle organisation n'est pas possible en pratique, car elle demanderait d'ajouter un ''tag'' à chaque perceptron/entrée du BTB, ce qui demanderait beaucoup de circuits et de ressources matérielles. Dans les faits l'association entre un branchement et un perceptron se fait en utilisant les bits de poids faible de l'adresse de branchement. Mais faire cela entrainera l'apparition de phénomènes d'''aliasing'', comme pour les unités de prédiction à deux niveaux. Les techniques vues précédemment peuvent en théorie être adaptées sur les unités à perceptrons, dans une certaine mesure. Notons que les perceptrons sont des algorithmes ou des circuits qui permettent de classer des données d'entrée en deux types. Ici, la donnée d'entrée est l'historique global et la sortie du perceptron indique si le branchement prédit est pris ou non-pris. Ils ne sont donc pas adaptés à d'autres tâches de prédiction, comme pour le préchargement des lignes de cache ou la prédiction de l'adresse de destination d'un branchement, ou toute autre tâche d'exécution spéculative un tant soit peu complexe. Leur utilisation reste cantonnée à la prédiction de branchement proprement dit, guère plus. Par contre, les autres techniques vues plus haut peuvent être utilisées pour le préchargement des lignes de cache, ou d'autres mécanismes de prédiction plus complexes, que nous aborderons dans la suite du cours. ==La prédiction des branchements des boucles== Les boucles sont à part, pour ce qui est de la prédiction de branchement. Rappelons qu'une boucle FOR/WHILE répète une série d'instruction N fois, le nombre N étant appelé le '''compteur de boucle'''. Ce qui fait que les branchements d'une boucle FOR sont pris n − 1 fois, la dernière exécution étant non prise. La conséquence est que les unités de prédiction usuelles sont assez mauvaises pour prédire les branchements des boucles. Par contre, la prédiction statique marche particulièrement bien comparé au reste. La prédiction statique prédit que les branchements des boucles sont toujours pris, ce qui donne des prédictions qui sont d'autant meilleures que la boucle est répétée un grand nombre de fois. Reste à gérer les branchements des boucles au mieux, en sachant cela. L'idée est d'utiliser plusieurs unités de prédiction séparées : une spécialisée dans les boucles et d'autres unités de prédiction. Uen unité de méta-prédiction se charge d'activer l'unité de prédiction des boucles dès qu'une boucle est détéctée. Les unités de prédiction modernes essayent de détecter les branchements des boucles afin de les mettre à part. En soi, ce n'est pas compliqué les branchements des boucles sont presque toujours des branchements descendants et réciproquement. De plus, ces branchements sont pris à chaque répétition de la boucle, et ne sont non-pris que quand on quitte la boucle. Le compteur de boucle analyse l'exécution des branchements, pour détecter les branchements des boucles. Un branchement est considéré comme un branchement de boucle si : il est pris N fois, avant de ne pas être pris une fois. Au moment où le branchement n'est plus pris, le ''Loop Predictor'' lui attribue une entrée dédié. L'entrée mémorise mémorise le nombre de fois que ce branchement a été pris, à savoir N, et est associée à un compteur. Le compteur est incrémenté/décrémenté à chaque exécution du branchement, et sa valeur est comparée à la valeur N. Quand le compteur atteint N+1, il est réinitialisé. Il s'agit d'une implémentation simple, mais est visiblement proche de celle utilisée sur le Pentium M, si j'en crois l'article "The Intel Pentium M Processor : Microarchitecture and Performance". Il faut noter que la boucle doit s'exécuter au moins une fois pour être détectée, et seules les exécutions suivantes sont prédites correctement. La boucle doit donc s'exécuter plusieurs fois, ce qui implique qu'elle est elle-même dans une boucle plus grande qu'elle. Une telle unité est donc capable de prédire spécifiquement les branchements de boucles FOR imbriquées, à savoir où une boucle FOR est dans une autre boucle FOR. Concrètement, cela permet de répéter la première boucle FOR plusieurs fois de suite, souvent un grand nombre de fois. Avec les boucles imbriquées, le compteur de boucle peut changer d'une répétition à l'autre, mais ce n'est que rarement le cas. Dans de nombreux cas, le compteur de boucle reste le même d'une répétition à l'autre. Ce qui fait qu'une fois la boucle exécutée une première fois, on peut prédire à la perfection les exécutions suivantes. Pour cela, il suffit de déterminer le compteur de boucle après la première exécution de la boucle, puis de le mémoriser dans un compteur. Lors des exécutions suivantes de la boucle, on compte le nombre de fois que le branchement de la boucle s'exécute : il est prédit comme pris tant que le compteur est différent du compteur de boucle, mais non-pris en cas d'égalité. ==La prédiction avec plusieurs unités de branchement distinctes== Il est possible de combiner plusieurs unités de prédiction de branchement différentes et de combiner leurs résultats en une seule prédiction. On peut par exemple combiner une unité de prédiction spécialisée dans les boucles, une unité de prédiction 2 bits basée sur des compteurs à saturation, une unité de prédiction statique et une unité ''gshare''. Tout le problème est de décider quelle unité a fait la bonne prédiction, comment combiner les résultats des différentes unités de prédiction. Soit on choisit un résultat qui parait plus fiable que les autres, soit on combine les résultats pour faire une sorte de moyenne des prédictions. La méthode la plus simple de choisir le résultat d'une unité de prédiction parmi toutes les autres. Pour implémenter le tout, il suffit d'un multiplexeur qui effectue le choix de la prédiction. Reste à commander le multiplexeur, ce qui demande un '''circuit méta-prédicteur''' qui sélectionne la bonne unité de prédiction. Il arrive que le circuit méta-prédicteur soit conçu avec les mêmes techniques que les unités de prédiction de branchement elle-mêmes. Dans le cas le plus simple, il s'agit d'un simple compteur à saturation, mis à jour suivant la concordance des prédictions avec le résultat effectif du branchement. Mais c'est loin d'être systématique. Une autre solution combine le résultat des différentes unités de prédiction avec une fonction mathématique adéquate. Avec un nombre impair d'unités de prédiction, une méthode assez efficace est de simplement prendre le résultat majoritaire. Si une majorité d'unités pense que le branchement est pris, alors on le considère comme pris, et comme non pris dans le cas contraire. Par contre, avec un nombre pair d'unités, cette méthode simple ne marche pas, il y a un risque d'égalité. L'unité de prédiction de branchement « '''''e-gskew''''' » utilise trois unités gshare et combine leurs résultats avec un vote à majorité. Les trois unités gshare utilisent des XOR légèrement différents, dans le sens où les bits de l'adresse du branchement choisi ne sont pas les mêmes dans les trois unités, sans compter que le résultat du XOR peut subir une modification qui dépend de l'unité de prédiction choisie. Autrement dit, la fonction de hachage qui associe une entrée à un branchement dépend de l'unité. [[File:Unité de prédiction « e-gskew ».png|centre|vignette|upright=2|Unité de prédiction « e-gskew ».]] Enfin, une dernière solution est que certaines unités de prédiction ont la priorité sur toutes les autres. Par exemple, prenons un processeur avec un ''return stack predictor'', une unité qui détecte les boucles et une unité de prédiction avec un historique. Si le ''return stack predictor'' détecte une instruction de retour de fonction, sa prédiction passera avant toutes les autres unités de prédiction. Et dans ce qui va suivre, c'est cette solution qui sera utilisé pour les unités de prédiction qu'on va étudier. ===Le prédicteur L-TAGE=== Il est possible d'utiliser plusieurs unités de prédiction, chacune utilisant des historiques de taille différente. Pour donner un exemple simple, on pourrait avoir une unité avec un historique de 2 bits, une autre avec un historique de 3 bits, une autre de 4 bits, etc. Une méta-unité de branchement prédit alors quelle taille d'historique donne les meilleurs résultats. Il est fréquent que les tailles d'historiques utilisées suivent une formule mathématique précise, appelée suite géométrique, ce qui est un mot bien barbare pour dire que l'on passe d'un historique au suivant en multipliant sa taille par une constante bien précise. Par exemple, on pourrait avoir des historiques de taille 2, 4, 8, 16, 32. C'est d'ailleurs le principe derrière les '''unités de branchement TAGE (''TAgged GEometric length predictor'')'''. Elles utilisent plusieurs registres d'historiques, chacun avec sa propre PHT, dont la taille suit une suite géométrique. Avec cette méthode, les branchements qui ont un motif répétitif sont alors parfaitement détectés, peu importe sa taille. Par exemple, un branchement avec un historique dont le cycle est pris, non-pris, non-pris, sera parfaitement prédit avec un historique de 3 bits, 6 bits, ou de 3*n bits, mais pas forcément avec un historique de 4 ou 8 bits. De ce fait, utiliser plusieurs unités de branchement avec plusieurs tailles d'historique fonctionne plutôt bien. Le prédicteur TAGE a été raffiné avec le temps, sur plusieurs points, que je ne vais pas détailler dans ce qui suit. Précisons cependant que les PHT sont structurées en caches, afin d'éliminer les phénomènes d'''aliasing''. L'ajout d'une unité de prédiction pour les boucles, a donné le '''prédicteur L-TAGE''', qui a lui-même été amélioré par la suite. Les unités de branchement TAGE sont les plus utilisées au moment où j'écris ces lignes (2026), et la majorité des processeurs x86 commerciaux utilisent une variante de ce prédicteur, à quelques exceptions près. Le '''prédicteur ITTAGE''' peut être adapté pour prédire des branchements indirects. La seule différence est que chaque table d'historique est associée non seulement à une prédiction pris/non-pris, mais aussi à une adresse de destination. L'idée derrière l'ITTAGE est que l'adresse de destination dépend de l'historique. L'adresse de destination dépend de ce qui se passe avant qu'on exécute le branchement indirect, donc de l'historique global. Il est donc fréquent que des historiques différents donne un résultat différent, que ce soit pour la prédiction pris/non-pris, mais aussi pour l'adresse de destination. L'ITTAGE associe donc une adresse de destination par ''pattern'' prédit. ==Les optimisations de la prédiction de branchements== La prédiction de branchement est complexe et toute économie est bonne à prendre. Pour améliorer les performances, ou simplement améliorer l'utilisation du BTB et des PHT, diverses techniques ont été inventées. Ces techniques marchent quel que soit l'unité de prédiction prise en compte. Elles peuvent s'appliquer aussi bien aux unités basées sur des perceptrons, que sur des unités à deux niveaux ou des unités de prédiction dynamique en général. Ces techniques sont assez variés : certaines profitent du fait que de nombreux branchements sont biaisés, d'autres tentent de réduire les interférences entre branchements sans utiliser l'historique global/local, etc. ===Le filtrage de branchements=== Une première optimisation permet d'économiser l'usage des différentes ressources matérielles, comme la BTB ou les PHT, en les réservant aux branchements non-biaisés. Idéalement, les branchements biaisés peuvent être prédits en utilisant des techniques très simples. D'où l'idée d'utiliser deux unités de prédiction spécialisées : une pour les branchements biaisés et une autre plus complexe. L'unité de prédiction pour les branchements biaisés est une unité de prédiction à 1 bit qui indique si le branchement est pris ou non, ce qui suffit largement pour de tels branchements. Cette technique s'appelle le '''filtrage de branchement''' et son nom est assez parlant. On filtre les branchements biaisés pour éviter qu'ils utilisent des PHT et d'autres ressources qui gagneraient à être utilisées pour des branchements plus difficiles à prédire. Appliquer cette idée demande de reconnaître les branchements fortement biaisés d'une manière ou d'une autre, ce qui est plus facile à dire qu'à faire. Une solution similaire enregistre quels branchements sont biaisés dans le BTB, et utilise cette information pour faire des prédictions. ===L'usage de fonctions de hashage pour indexer les diverses SRAM/tables=== Plus haut, nous avons vu que les unités de prédiction de branchement contiennent des structures qui sont adressées par l'adresse de branchement. Tel est le cas du ''Branch Target Buffer'', de certaines PHT globales ou locales, de la ''Branch History Table'' qui stocke les historiques locaux, ou encore de la SRAM des poids des unités à base de perceptrons. En pratique, ces structures sont adressées non pas par l'adresse de branchement complète, mais pas les bits de poids faible de cette adresse. Cela a pour conséquence l'apparition d'un ''aliasing'' lié au fait que ces structures vont confondre deux branchements pour lesquels les bits de poids faible de l'adresse sont identiques. Il est possible d'utiliser autre chose que les bits de poids faible de l'adresse du branchement, afin de limiter les interférences. Et les possibilités sont multiples. Les possibilités en question s'inspirent des traitements effectués sur les adresses des banques dans les mémoires évoluées. Une première solution serait de faire un XOR entre les bits de poids faible de l'adresse du branchement, et d'autres bits de cette même adresse. Ainsi, deux branchements éloignés en mémoire donneraient des résultats différents, même si leurs bits de poids faible sont identiques. Une autre possibilité serait de diviser l'adresse du branchement par un nombre et de garder le reste. Ce calcul de modulo n'est en soi pas très différent du fait de conserver seulement les bits de poids faible. Conserver les N bits de poids faible consiste en effet à prendre le modulo par 2^N de l'adresse. Ici, l'idée serait de faire un modulo par un nombre P, qui serait un nombre premier proche de 2^N. Le fait que le nombre soit premier limite les cas où deux adresses différentes donneraient le même reste, ce qui réduit l'''aliasing''. Le fait de prendre un nombre proche de 2^N pour une entrée de N bits est que le résultat reste assez proche de ce qu'on obtiendrait en gardant les bits de poids faible, cette dernière étant une solution pas trop mauvaise. D'autres possibilités similaires se basent sur des réductions polynomiales ou d'autres astuces impliquant des nombres premiers. L'efficacité de ces méthodes dépend grandement de la taille de la SRAM/table considérée, des adresses des branchements et de beaucoup d'autres paramètres. La réduction des interférences par telle ou telle méthode dépend aussi de l'unité de prédiction considérée. Les résultats ne sont pas les mêmes selon que l'on parle d'une unité à perceptrons ou d'une unité à deux niveaux ou d'unités à base de compteurs à saturation, ou que l'on parle du BTB. Par contre, toutes les méthodes ne sont pas équivalentes en termes de temps de calcul ou de portes logiques. Autant la première solution avec un XOR ajoute un temps de calcul négligeable et quelques portes logiques, autant les autres méthodes requièrent l'ajout d'un diviseur très lent et gourmand en portes logiques pour calculer des modulos. Elles ne sont généralement pas praticables pour ces raisons, le temps de calcul serait trop élevé. <noinclude> {{NavChapitre | book=Fonctionnement d'un ordinateur | prev=Le pipeline | prevText=Le pipeline | next=Les optimisations du chargement des instructions | nextText=Les optimisations du chargement des instructions }} </noinclude> agk9ynsk3eu5maup4ae1207tc0l4rlx 0 76120 775368 685479 2026-10-18T14:30:24Z Xhungab 23827 775368 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|x_euler.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as x_euler.h */ /* ---------------------------------- */ double Euler_s_Method( double a, double b, double n, double y0, double (*P_f)(double x,double y) ) { double i = 0; double h = ((b-a)/n); double xp = a; double yp = y0; for(i=1; i<=n; i++) { yp += h*(*P_f)(xp,yp); xp += h; } return(yp); } /* --------------------------------- */ /* --------------------------------- */ void p_Euler_s_Method( double a, double b, double n, double y0, double (*P_f)(double x,double y) ) { double i = 0; double h = ((b-a)/n); double xp = a; double yp = y0; printf(" k | x_k | y_k \n"); printf(" --------------------------\n"); printf(" %3.f | %.3f | %+.10f\n",i,xp,yp); for(i=1; i<=n; i++) { yp += h*(*P_f)(xp,yp); xp += h; printf(" %3.f | %.3f | %+.10f\n",i,xp,yp); } printf("\n\n"); } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} 5g5iw81upwd23sjasmo2jnwx1oe2onl 0 76121 775374 685480 2026-10-18T15:08:32Z Xhungab 23827 775374 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fa.h|largeur=70%|info=utilitaire|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fa.h */ /* ---------------------------------- */ double Y( double x, double y) { return(1.0 + ((y-x)*(y-x))); } /* --------------------------------- */ char Yeq[] = "1.0 + (y-x)**2"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} jjp0vhphp28c2zhj2cisdkm6irqak1o 0 76122 775375 685481 2026-10-18T15:09:36Z Xhungab 23827 775375 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fb.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fb.h */ /* ---------------------------------- */ double Y( double x, double y) { return(1 + y/x ); } /* --------------------------------- */ char Yeq[] = "1 + y/x"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} g52kf0fsgdzwqsroviyu1oh2b5t0qm5 0 76123 775376 685482 2026-10-18T15:10:37Z Xhungab 23827 775376 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fc.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fc.h */ /* ---------------------------------- */ double Y( double x, double y) { return( -(y+1)*(y+3) ); } /* --------------------------------- */ char Yeq[] = "-(y+1)*(y+3)"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} 0iwt6gfao99end9i93u7fdkyjeecbs4 0 76124 775369 735990 2026-10-18T14:33:29Z Xhungab 23827 775369 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19| Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1a.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1a.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fa.h" /* --------------------------------- */ int main(void) { double n; double a; double b; double y0; n = 10.0; a = 1.0; b = 2.4; y0 = 1.59; clrscrn(); printf(" Euler's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Euler_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); clrscrn(); n = 10000000.0; printf(" Euler's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1.0 + (y-x)**2 pour 1 < x < 2.4 avec comme condition initial y0 = 1.59 quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Euler's method to approximate the solution of the differential equation. y' = 1.0 + (y-x)**2 k | x_k | y_k -------------------------- 0 | 1.000 | +1.5900000000 1 | 1.140 | +1.7787340000 2 | 1.280 | +1.9758513572 3 | 1.420 | +2.1836406328 4 | 1.560 | +2.4052812150 5 | 1.700 | +2.6453112616 6 | 1.840 | +2.9104171349 7 | 1.980 | +3.2108281329 8 | 2.120 | +3.5629194379 9 | 2.260 | +3.9944017485 10 | 2.400 | +4.5555426680 y_n = 4.5555426680 The exact value is y = 5.790805 Press return to continue. Euler's method to approximate the solution of the differential equation y' = 1.0 + (y-x)**2, with n = 10000000 y_n = 5.7908017783 The exact value is y = 5.790805 Press return to continue. </syntaxhighlight> ---- {{AutoCat}} fbiek3t3hkevcc0z296r2zvs0yg1p4x 775372 775369 2026-10-18T14:41:27Z Xhungab 23827 775372 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19| Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1a.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1a.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fa.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 1.0; double b = 2.4; double y0 = 1.59; clrscrn(); printf(" Euler's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Euler_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); clrscrn(); n = 10000000.0; printf(" Euler's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1.0 + (y-x)**2 pour 1 < x < 2.4 avec comme condition initial y0 = 1.59 quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Euler's method to approximate the solution of the differential equation. y' = 1.0 + (y-x)**2 k | x_k | y_k -------------------------- 0 | 1.000 | +1.5900000000 1 | 1.140 | +1.7787340000 2 | 1.280 | +1.9758513572 3 | 1.420 | +2.1836406328 4 | 1.560 | +2.4052812150 5 | 1.700 | +2.6453112616 6 | 1.840 | +2.9104171349 7 | 1.980 | +3.2108281329 8 | 2.120 | +3.5629194379 9 | 2.260 | +3.9944017485 10 | 2.400 | +4.5555426680 y_n = 4.5555426680 The exact value is y = 5.790805 Press return to continue. Euler's method to approximate the solution of the differential equation y' = 1.0 + (y-x)**2, with n = 10000000 y_n = 5.7908017783 The exact value is y = 5.790805 Press return to continue. </syntaxhighlight> ---- {{AutoCat}} at2aow1s6c3rffhkcwvj0ynqxgf4al8 0 76125 775370 735991 2026-10-18T14:36:30Z Xhungab 23827 775370 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1b.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1b.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fb.h" /* --------------------------------- */ int main(void) { double n; double a; double b; double y0; n = 10.0; a = 1.0; b = 2.0; y0 = 3.0; clrscrn(); printf(" Euler's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Euler_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); clrscrn(); n = 100000; printf(" Euler's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1 + y/x pour 1 < x < 2 avec comme condition initial y0 = 3. quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Euler's method to approximate the solution of the differential equation. y' = 1 + y/x k | x_k | y_k -------------------------- 0 | 1.000 | +3.0000000000 1 | 1.100 | +3.4000000000 2 | 1.200 | +3.8090909091 3 | 1.300 | +4.2265151515 4 | 1.400 | +4.6516317016 5 | 1.500 | +5.0838911089 6 | 1.600 | +5.5228171828 7 | 1.700 | +5.9679932567 8 | 1.800 | +6.4190516836 9 | 1.900 | +6.8756656660 10 | 2.000 | +7.3375428064 y_n = 7.3375428064 The exact value is y = 7.38629 Press return to continue. Euler's method to approximate the solution of the differential equation y' = 1 + y/x, with n = 100000 y_n = 7.3862893611 The exact value is y = 7.38629 Press return to continue. </syntaxhighlight> {{AutoCat}} 8wan2sl79id3irkn9i82h8ttk0slnsw 775373 775370 2026-10-18T14:42:55Z Xhungab 23827 775373 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1b.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1b.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fb.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 1.0; double b = 2.0; double y0 = 3.0; clrscrn(); printf(" Euler's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Euler_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); clrscrn(); n = 100000; printf(" Euler's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1 + y/x pour 1 < x < 2 avec comme condition initial y0 = 3. quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Euler's method to approximate the solution of the differential equation. y' = 1 + y/x k | x_k | y_k -------------------------- 0 | 1.000 | +3.0000000000 1 | 1.100 | +3.4000000000 2 | 1.200 | +3.8090909091 3 | 1.300 | +4.2265151515 4 | 1.400 | +4.6516317016 5 | 1.500 | +5.0838911089 6 | 1.600 | +5.5228171828 7 | 1.700 | +5.9679932567 8 | 1.800 | +6.4190516836 9 | 1.900 | +6.8756656660 10 | 2.000 | +7.3375428064 y_n = 7.3375428064 The exact value is y = 7.38629 Press return to continue. Euler's method to approximate the solution of the differential equation y' = 1 + y/x, with n = 100000 y_n = 7.3862893611 The exact value is y = 7.38629 Press return to continue. </syntaxhighlight> {{AutoCat}} d5rwphl3sg0b6y38o3zkc5nfja6pi93 0 76126 775371 735992 2026-10-18T14:40:24Z Xhungab 23827 775371 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c19|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1c.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1c.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fc.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 0.0; double b = 2.0; double y0 = -1.5; clrscrn(); printf(" Euler's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Euler_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = -1.012136331\n\n"); stop(); clrscrn(); n = 10000000.0; printf(" Euler's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Euler_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = -1.012136331\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = -(y+1)*(y+3) pour 0 < x < 2 avec comme condition initial y0 = -1.5 quand x = 0 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Euler's method to approximate the solution of the differential equation. y' = -(y+1)*(y+3) k | x_k | y_k -------------------------- 0 | 0.000 | -1.5000000000 1 | 0.200 | -1.3500000000 2 | 0.400 | -1.2345000000 3 | 0.600 | -1.1516980500 4 | 0.800 | -1.0956212897 5 | 1.000 | -1.0592014600 6 | 1.200 | -1.0362218386 7 | 1.400 | -1.0219955075 8 | 1.600 | -1.0132940649 9 | 1.800 | -1.0080117854 10 | 2.000 | -1.0048199090 y_n = -1.0048199090 The exact value is y = -1.012136331 Press return to continue. Euler's method to approximate the solution of the differential equation y' = -(y+1)*(y+3), with n = 10000000 y_n = -1.0121363227 The exact value is y = -1.012136331 Press return to continue. </syntaxhighlight> {{AutoCat}} j0koqsr1noac0rrt0at1kh7t6qfb83v 0 76130 775377 685489 2026-10-18T15:35:11Z Xhungab 23827 775377 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|x_heun.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as x_heun.h */ /* ---------------------------------- */ void p_Heun_s_Method( double a, double b, double n, double y0, double (*P_f)(double x,double y) ) { double i = 0; double h = ((b-a)/n); double xp = a; double yp = y0; double T; printf(" k | x_k | y_k \n"); printf(" --------------------------\n"); printf(" %+3.f | %+.3f | %+.10f\n",i,xp,yp); for(i=1; i<=n; i++) { T = (*P_f)(xp,yp); yp += (h/2.)*( T + (*P_f)(xp+h, yp+h*T)); xp += h; printf(" %+3.f | %+.3f | %+.10f\n",i,xp,yp); } } /* --------------------------------- */ /* --------------------------------- */ double Heun_s_Method( double a, double b, double n, double y0, double (*P_f)(double x,double y) ) { double i = 0; double h = ((b-a)/n); double xp = a; double yp = y0; double T; for(i=1; i<=n; i++) { T = (*P_f)(xp,yp); yp += (h/2.)*( T + (*P_f)(xp+h, yp+h*T)); xp += h; } return(yp); } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} 8lvihwxr0tmn9o2adg0b3l116eljecr 0 76131 775378 685490 2026-10-18T15:36:15Z Xhungab 23827 775378 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fa.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fa.h */ /* ---------------------------------- */ double Y( double x, double y) { return(1.0 + ((y-x)*(y-x))); } /* --------------------------------- */ char Yeq[] = "1.0 + (y-x)**2"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} ijt27ffx0xo3ooi6jao7zk5bpm5y8u7 0 76132 775379 685491 2026-10-18T15:37:08Z Xhungab 23827 775379 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fb.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fb.h */ /* ---------------------------------- */ double Y( double x, double y) { return(1 + y/x ); } /* --------------------------------- */ char Yeq[] = "1 + y/x"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} opncqep5vghrimg2zj9zg4xy8s3g2wt 0 76133 775380 685492 2026-10-18T15:38:06Z Xhungab 23827 775380 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fc.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fc.h */ /* ---------------------------------- */ double Y( double x, double y) { return( -(y+1)*(y+3) ); } /* --------------------------------- */ char Yeq[] = "-(y+1)*(y+3)"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} 5lx5aotkso07cqme3amcol5ww5ppxtw 0 76134 775381 735993 2026-10-18T15:40:30Z Xhungab 23827 775381 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1a.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1a.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fa.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 1.0;; double b = 2.4; double y0 = 1.59; clrscrn(); printf(" Heun's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Heun_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Heun_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); clrscrn(); n = 10000.0; printf(" Heun's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Heun_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); return 0; } /* ---------------------------------- */ /* ---------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1.0 + (y-x)**2 pour 1 < x < 2.4 avec comme condition initial y0 = 1.59 quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Heun's method to approximate the solution of the differential equation. y' = 1.0 + (y-x)**2 k | x_k | y_k -------------------------- +0 | +1.000 | +1.5900000000 +1 | +1.140 | +1.7829256786 +2 | +1.280 | +1.9862383884 +3 | +1.420 | +2.2033120261 +4 | +1.560 | +2.4391496429 +5 | +1.700 | +2.7014939903 +6 | +1.840 | +3.0029808154 +7 | +1.980 | +3.3656740723 +8 | +2.120 | +3.8316934726 +9 | +2.260 | +4.4919519386 +10 | +2.400 | +5.5813521807 y_n = 5.5813521807 The exact value is y = 5.790805 Press return to continue. Heun's method to approximate the solution of the differential equation y' = 1.0 + (y-x)**2, with n = 10000 y_n = 5.7908042822 The exact value is y = 5.790805 Press return to continue. </syntaxhighlight> {{AutoCat}} h9dnx747aeabwuhq8v6lwweu11thi54 0 76135 775382 735994 2026-10-18T15:43:11Z Xhungab 23827 775382 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1b.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1b.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fb.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 1.0; double b = 2.0; double y0 = 3.0; clrscrn(); printf(" Heun's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Heun_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Heun_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); clrscrn(); n = 100.0; printf(" Heun's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Heun_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); return 0; } /* ---------------------------------- */ /* ---------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1 + y/x pour 1 < x < 2 avec comme condition initial y0 = 3. quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Heun's method to approximate the solution of the differential equation. y' = 1 + y/x k | x_k | y_k -------------------------- +0 | +1.000 | +3.0000000000 +1 | +1.100 | +3.4045454545 +2 | +1.200 | +3.8182162534 +3 | +1.300 | +4.2402470951 +4 | +1.400 | +4.6699913771 +5 | +1.500 | +5.1068955231 +6 | +1.600 | +5.5504802246 +7 | +1.700 | +6.0003264152 +8 | +1.800 | +6.4560645703 +9 | +1.900 | +6.9173664031 +10 | +2.000 | +7.3839383191 y_n = 7.3839383191 The exact value is y = 7.38629 Press return to continue. Heun's method to approximate the solution of the differential equation y' = 1 + y/x, with n = 100 y_n = 7.3862695068 The exact value is y = 7.38629 Press return to continue. </syntaxhighlight> {{AutoCat}} 4ctb2dp7erox9zp8q5btkufd5qi4dge 0 76136 775383 735995 2026-10-18T15:45:34Z Xhungab 23827 775383 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c20|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1c.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1c.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fc.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 0.0; double b = 2.0; double y0 = -1.5; clrscrn(); printf(" Heun's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_Heun_s_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", Heun_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = -1.012136331\n\n"); stop(); clrscrn(); n = 10000.0; printf(" Heun's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", Heun_s_Method(a, b, n, y0, Y) ); printf(" The exact value is y = -1.012136331\n\n"); stop(); return 0; } /* ---------------------------------- */ /* ---------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = -(y+1)*(y+3) pour 0 < x < 2 avec comme condition initial y0 = -1.5 quand x = 0 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Heun's method to approximate the solution of the differential equation. y' = -(y+1)*(y+3) k | x_k | y_k -------------------------- +0 | +0.000 | -1.5000000000 +1 | +0.200 | -1.3672500000 +2 | +0.400 | -1.2639392952 +3 | +0.600 | -1.1866271617 +4 | +0.800 | -1.1304109773 +5 | +1.000 | -1.0903665254 +6 | +1.200 | -1.0622511611 +7 | +1.400 | -1.0427086592 +8 | +1.600 | -1.0292188780 +9 | +1.800 | -1.0199513980 +10 | +2.000 | -1.0136053555 y_n = -1.0136053555 The exact value is y = -1.012136331 Press return to continue. Heun's method to approximate the solution of the differential equation y' = -(y+1)*(y+3), with n = 10000 y_n = -1.0121363321 The exact value is y = -1.012136331 Press return to continue. </syntaxhighlight> {{AutoCat}} 32luqgnull7d4orwgwvgzkrzc1cjct6 0 76140 775386 685501 2026-10-18T16:32:32Z Xhungab 23827 775386 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|x_runge.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as x_runge.h */ /* ---------------------------------- */ double RungeKutta_Method( double a, double b, double n, double y0, double (*P_f)(double x,double y) ) { double i = 0; double h = ((b-a)/n); double xp = a; double yp = y0; double K1,K2,K3,K4; for(i=1; i<=n; i++) { K1 = h * (*P_f)(xp, yp ); K2 = h * (*P_f)(xp + .5*h,yp + .5*K1); K3 = h * (*P_f)(xp + .5*h,yp + .5*K2); K4 = h * (*P_f)(xp + h,yp + K3); yp = yp +(1/6.)*(K1+2*K2+2*K3+K4); xp +=h; } return(yp); } /* ---------------------------------- */ void p_RungeKutta_Method( double a, double b, double n, double y0, double (*P_f)(double x,double y) ) { double i = 0; double h = ((b-a)/n); double xp = a; double yp = y0; double K1,K2,K3,K4; printf(" k | xp | y_k \n"); printf(" --------------------------\n"); printf(" %+3.f | %+.3f | %+.4f\n",i,xp,yp); for(i=1; i<=n; i++) { K1 = h * (*P_f)(xp, yp ); K2 = h * (*P_f)(xp + .5*h,yp + .5*K1); K3 = h * (*P_f)(xp + .5*h,yp + .5*K2); K4 = h * (*P_f)(xp + h,yp + K3); yp = yp +(1/6.)*(K1+2*K2+2*K3+K4); xp +=h; printf(" %+3.f | %+.3f | %+.4f\n",i,xp,yp); } } /* ---------------------------------- */ /* ---------------------------------- */ </syntaxhighlight> {{AutoCat}} 1gnuatfpxvfddis29cjbif73q8ws2nz 0 76141 775387 685502 2026-10-18T16:33:25Z Xhungab 23827 775387 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fa.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fa.h */ /* ---------------------------------- */ double Y( double x, double y) { return(1.0 + ((y-x)*(y-x))); } /* --------------------------------- */ char Yeq[] = "1.0 + (y-x)**2"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} nynzqxk8tt6a0utark46r4af2hw95hb 0 76142 775388 685503 2026-10-18T16:34:08Z Xhungab 23827 775388 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fb.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fb.h */ /* ---------------------------------- */ double Y( double x, double y) { return(1 + y/x ); } /* --------------------------------- */ char Yeq[] = "1 + y/x"; /* --------------------------------- */ /* ---------------------------------- */ </syntaxhighlight> {{AutoCat}} 8hpwfi0bqh0k3hma0ox7wqd2au5ug4f 0 76143 775389 685505 2026-10-18T16:34:48Z Xhungab 23827 775389 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer ce fichier dans votre répertoire de travail. {{Fichier|fc.h|largeur=70%|info=|icon=Crystal Clear mimetype source h.png}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as fc.h */ /* ---------------------------------- */ double Y( double x, double y) { return( -(y+1)*(y+3) ); } /* --------------------------------- */ char Yeq[] = "-(y+1)*(y+3)"; /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> {{AutoCat}} q2jipkwcx3wc2cjqwtn8psfgozbucd3 0 76144 775390 735996 2026-10-18T16:36:44Z Xhungab 23827 775390 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] : [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1a.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1a.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fa.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 1.0; double b = 2.4; double y0 = 1.59; clrscrn(); printf(" Runge Kutta's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_RungeKutta_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", RungeKutta_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); clrscrn(); n = 50.0; printf(" Runge Kutta's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", RungeKutta_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 5.790805\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1.0 + (y-x)**2 pour 1 < x < 2.4 avec comme condition initial y0 = 1.59 quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Runge Kutta's method to approximate the solution of the differential equation. y' = 1.0 + (y-x)**2 k | xp | y_k -------------------------- +0 | +1.000 | +1.5900 +1 | +1.140 | +1.7831 +2 | +1.280 | +1.9868 +3 | +1.420 | +2.2044 +4 | +1.560 | +2.4411 +5 | +1.700 | +2.7051 +6 | +1.840 | +3.0097 +7 | +1.980 | +3.3787 +8 | +2.120 | +3.8593 +9 | +2.260 | +4.5590 +10 | +2.400 | +5.7889 y_n = 5.7889039379 The exact value is y = 5.790805 Press return to continue. Runge Kutta's method to approximate the solution of the differential equation y' = 1.0 + (y-x)**2, with n = 50 y_n = 5.7908008408 The exact value is y = 5.790805 Press return to continue. </syntaxhighlight> {{AutoCat}} o9b1i235719ycxaybdxoc8h890me3vw 0 76145 775391 735997 2026-10-18T16:41:46Z Xhungab 23827 775391 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1b.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1b.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fb.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 1.0; double b = 2.0; double y0 = 3.0; clrscrn(); printf(" Runge Kutta's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_RungeKutta_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", RungeKutta_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); clrscrn(); n = 9.0; printf(" Runge Kutta's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", RungeKutta_Method(a, b, n, y0, Y) ); printf(" The exact value is y = 7.38629\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = 1 + y/x pour 1 < x < 2 avec comme condition initial y0 = 3. quand x = 1 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Runge Kutta's method to approximate the solution of the differential equation. y' = 1 + y/x k | xp | y_k -------------------------- +0 | +1.000 | +3.0000 +1 | +1.100 | +3.4048 +2 | +1.200 | +3.8188 +3 | +1.300 | +4.2411 +4 | +1.400 | +4.6711 +5 | +1.500 | +5.1082 +6 | +1.600 | +5.5520 +7 | +1.700 | +6.0021 +8 | +1.800 | +6.4580 +9 | +1.900 | +6.9195 +10 | +2.000 | +7.3863 y_n = 7.3862928864 The exact value is y = 7.38629 Press return to continue. Runge Kutta's method to approximate the solution of the differential equation y' = 1 + y/x, with n = 9 y_n = 7.3862921293 The exact value is y = 7.38629 Press return to continue. </syntaxhighlight> {{AutoCat}} 8bibp527y9ckzc88frq42p8cuurgfgm 0 76146 775392 735998 2026-10-18T16:44:16Z Xhungab 23827 775392 wikitext text/x-wiki [[Catégorie:Mathc initiation (livre)]] [[Mathc_initiation/Fichiers_h_:_c21|Sommaire]] Installer et compiler ces fichiers dans votre répertoire de travail. {{Fichier|c1c.c|largeur=70%|info=|icon=Crystal128-source-c.svg}} <syntaxhighlight lang="c"> /* ---------------------------------- */ /* save as c1c.c */ /* ---------------------------------- */ #include "x_hfile.h" #include "fc.h" /* --------------------------------- */ int main(void) { double n = 10.0; double a = 0.0; double b = 2.0; double y0 = -1.5; clrscrn(); printf(" Runge Kutta's method to approximate the solution\n" " of the differential equation.\n\n" " y' = %s\n\n",Yeq); p_RungeKutta_Method(a, b, n, y0, Y); printf(" y_n = %.10f\n\n", RungeKutta_Method(a, b, n, y0, Y) ); printf(" The exact value is y = -1.012136331\n\n"); stop(); clrscrn(); n = 100.0; printf(" Runge Kutta's method to approximate the solution\n" " of the differential equation\n\n" " y' = %s,\n\n with n = %.0f \n\n",Yeq, n); printf(" y_n = %.10f\n\n", RungeKutta_Method(a, b, n, y0, Y) ); printf(" The exact value is y = -1.012136331\n\n"); stop(); return 0; } /* --------------------------------- */ /* --------------------------------- */ </syntaxhighlight> Calculons la solution numérique de l'équation y' = -(y+1)*(y+3) pour 0 < x < 2 avec comme condition initial y0 = -1.5 quand x = 0 '''Exemple de sortie écran 1 :''' <syntaxhighlight lang="C"> Runge Kutta's method to approximate the solution of the differential equation. y' = -(y+1)*(y+3) k | xp | y_k -------------------------- +0 | +0.000 | -1.5000 +1 | +0.200 | -1.3653 +2 | +0.400 | -1.2605 +3 | +0.600 | -1.1825 +4 | +0.800 | -1.1261 +5 | +1.000 | -1.0864 +6 | +1.200 | -1.0587 +7 | +1.400 | -1.0398 +8 | +1.600 | -1.0268 +9 | +1.800 | -1.0181 +10 | +2.000 | -1.0121 y_n = -1.0121464689 The exact value is y = -1.012136331 Press return to continue. Runge Kutta's method to approximate the solution of the differential equation y' = -(y+1)*(y+3), with n = 100 y_n = -1.0121363318 The exact value is y = -1.012136331 Press return to continue. </syntaxhighlight> {{AutoCat}} i0bkzn1rgn8oran1t3afhv3f330jqje 4 78643 775366 774751 2026-10-18T13:23:50Z Alexis Jazz 81580 Updating gadget usage statistics from [[Special:GadgetUsage]] ([[phab:T121049]]) 775366 wikitext text/x-wiki {{#ifexist:Project:GUS2Wiki/top|{{/top}}|This page provides a historical record of [[Special:GadgetUsage]] through its page history. To get the data in CSV format, see wikitext. To customize this message or add categories, create [[/top]].}} Les données suivantes sont en cache et ont été mises à jour pour la dernière fois le 2026-10-16T06:35:08Z. {{PLURAL:5000|1=Un seul résultat|5000 résultats}} au maximum {{PLURAL:5000|est disponible|sont disponibles}} dans le cache. {| class="sortable wikitable" ! Gadget !! data-sort-type="number" | Nombre d’utilisateurs !! data-sort-type="number" | Utilisateurs actifs |- |AncreTitres || 34 || 0 |- |ArchiveLinks || 13 || 0 |- |Barre de luxe || 36 || 1 |- |BoutonsLiens || 42 || 0 |- |CategoryAboveAll || 20 || 0 |- |CategorySeparator || 23 || 0 |- |CoinsArrondis || 100 || 1 |- |CollapseSidebox || 36 || 0 |- |CouleurContributions || 33 || 0 |- |CouleursLiens || 26 || 0 |- |DeluxeAdmin || 6 || 1 |- |DeluxeEdit || 36 || 1 |- |DeluxeHistory || 47 || 2 |- |DeluxeImport || 19 || 1 |- |DeluxeRename || 16 || 1 |- |DeluxeSummary || 37 || 1 |- |DevTools || 18 || 1 |- |DirectPageLink || 26 || 1 |- |Emoticons || 45 || 0 |- |EmoticonsToolbar || 46 || 0 |- |FastRevert || 37 || 1 |- |FixArrayAltLines || 23 || 1 |- |FlecheHaut || 67 || 1 |- |GoogleTrans || 28 || 0 |- |HotCats || 81 || 2 |- |JournalDebug || 22 || 1 |- |JournalEnTable || 3 || 1 |- |LeftPaneSwitch || 6 || 0 |- |ListeABordure || 30 || 1 |- |LiveRC || 30 || 0 |- |LocalLiveClock || 27 || 1 |- |Logo || 42 || 0 |- |MobileView || 18 || 1 |- |NavigAdmin || 39 || 0 |- |OngletEditCount || 45 || 0 |- |OngletEditZeroth || 67 || 1 |- |OngletGoogle || 29 || 1 |- |OngletPurge || 57 || 1 |- |OptimizedSuivi || 18 || 0 |- |Popups || 61 || 1 |- |RenommageCategorie || 7 || 2 |- |RestaurationDeluxe || 12 || 1 |- |RevertDiff || 35 || 4 |- |ScriptAutoVersion || 17 || 1 |- |ScriptSidebox || 32 || 0 |- |ScriptToolbar || 43 || 0 |- |SisterProjects || 18 || 0 |- |SkinPreview || 4 || 0 |- |Smart patrol || 2 || 1 |- |SourceLanguage || 24 || 0 |- |SousPages || 57 || 2 |- |SpaceToolbar || 30 || 0 |- |TableUnicode || 56 || 0 |- |Tableau || 67 || 2 |- |TitreDeluxe || 56 || 1 |- |TitreHierarchique || 17 || 0 |- |UTCLiveClock || 27 || 0 |- |UnicodeEditRendering || 29 || 1 |- |WikEd || 30 || 0 |- |autonum || 2 || 0 |- |massblock || 3 || 1 |- |monBrouillon || 20 || 0 |- |perpagecustomization || 17 || 0 |- |recentchangesbox || 15 || 0 |- |searchFocus || 19 || 0 |- |searchbox || 30 || 1 |} * [[Spécial:GadgetUsage]] * [[m:Meta:GUS2Wiki/Script|GUS2Wiki]] <!-- data in CSV format: AncreTitres,34,0 ArchiveLinks,13,0 Barre de luxe,36,1 BoutonsLiens,42,0 CategoryAboveAll,20,0 CategorySeparator,23,0 CoinsArrondis,100,1 CollapseSidebox,36,0 CouleurContributions,33,0 CouleursLiens,26,0 DeluxeAdmin,6,1 DeluxeEdit,36,1 DeluxeHistory,47,2 DeluxeImport,19,1 DeluxeRename,16,1 DeluxeSummary,37,1 DevTools,18,1 DirectPageLink,26,1 Emoticons,45,0 EmoticonsToolbar,46,0 FastRevert,37,1 FixArrayAltLines,23,1 FlecheHaut,67,1 GoogleTrans,28,0 HotCats,81,2 JournalDebug,22,1 JournalEnTable,3,1 LeftPaneSwitch,6,0 ListeABordure,30,1 LiveRC,30,0 LocalLiveClock,27,1 Logo,42,0 MobileView,18,1 NavigAdmin,39,0 OngletEditCount,45,0 OngletEditZeroth,67,1 OngletGoogle,29,1 OngletPurge,57,1 OptimizedSuivi,18,0 Popups,61,1 RenommageCategorie,7,2 RestaurationDeluxe,12,1 RevertDiff,35,4 ScriptAutoVersion,17,1 ScriptSidebox,32,0 ScriptToolbar,43,0 SisterProjects,18,0 SkinPreview,4,0 Smart patrol,2,1 SourceLanguage,24,0 SousPages,57,2 SpaceToolbar,30,0 TableUnicode,56,0 Tableau,67,2 TitreDeluxe,56,1 TitreHierarchique,17,0 UTCLiveClock,27,0 UnicodeEditRendering,29,1 WikEd,30,0 autonum,2,0 massblock,3,1 monBrouillon,20,0 perpagecustomization,17,0 recentchangesbox,15,0 searchFocus,19,0 searchbox,30,1 --> opbxeirh7ac8cf7nyohmqkxftqyb8r9 0 84594 775359 2026-10-18T12:08:25Z Cdang 1202 Page créée avec « {{livre de cuisine}} ==Ingrédients== * ¼ de {{i|potiron}} ; une autre courge peut convenir (potimarron, citrouille…) ; * 1 {{i|oignon}} ; * {{unité|250|ml}} de {{i|crème fraîche}} liquide, ou 4 cuillers à soupe de crème épaisse ; * sel, poivre, {{i|noix de muscade}} en poudre ; * un peut d’huile ; * éventuellement du persil. == Préparation == # Couper la chair de la courge en gros dés. # Couper l’oignon en lamelles. # Faire revenir l’oignon... » 775359 wikitext text/x-wiki {{livre de cuisine}} ==Ingrédients== * ¼ de {{i|potiron}} ; une autre courge peut convenir (potimarron, citrouille…) ; * 1 {{i|oignon}} ; * {{unité|250|ml}} de {{i|crème fraîche}} liquide, ou 4 cuillers à soupe de crème épaisse ; * sel, poivre, {{i|noix de muscade}} en poudre ; * un peut d’huile ; * éventuellement du persil. == Préparation == # Couper la chair de la courge en gros dés. # Couper l’oignon en lamelles. # Faire revenir l’oignon dans une cocotte avec un fond d’huile. Ajouter la courge et continuer à faire revenir. # Ajouter de l’eau pour couvrir la courge, sans plus. # Couvrir et laisser bouillir ¾ d’h à {{unité|1|h}} ; une fourchette ou une point d ecouteau doit rentrer facilement dans un dé de courge. # Mixer. # Mettre la crème. Assaisonner selon les goûts : saler, poivrer, mettre de la noix de muscade. # Mettre du persil ciselé au moment de servir. {{DEFAULTSORT:Veloute de potiron}} [[Catégorie:Recettes végétariennes]] [[Catégorie:Soupes|Potiron veloute]] sprw3eltcb6l0bok61z7m3jghzu9frh 775364 775359 2026-10-18T12:16:02Z Cdang 1202 /* Ingrédients */ corr. 775364 wikitext text/x-wiki {{livre de cuisine}} ==Ingrédients== * ¼ de {{i|potiron}} ; une autre courge peut convenir (potimarron, citrouille…) ; * 1 {{i|'=oui|oignon}} ; * {{unité|250|ml}} de {{i|crème fraîche}} liquide, ou 4 cuillers à soupe de crème épaisse ; * sel, poivre, {{i|noix de muscade}} en poudre ; * un peut d’huile ; * éventuellement du persil. == Préparation == # Couper la chair de la courge en gros dés. # Couper l’oignon en lamelles. # Faire revenir l’oignon dans une cocotte avec un fond d’huile. Ajouter la courge et continuer à faire revenir. # Ajouter de l’eau pour couvrir la courge, sans plus. # Couvrir et laisser bouillir ¾ d’h à {{unité|1|h}} ; une fourchette ou une point d ecouteau doit rentrer facilement dans un dé de courge. # Mixer. # Mettre la crème. Assaisonner selon les goûts : saler, poivrer, mettre de la noix de muscade. # Mettre du persil ciselé au moment de servir. {{DEFAULTSORT:Veloute de potiron}} [[Catégorie:Recettes végétariennes]] [[Catégorie:Soupes|Potiron veloute]] 64v5ve48n9l8uhubyz14ji8n80jpi66 14 84595 775363 2026-10-18T12:14:13Z Cdang 1202 Page créée avec « [[Catégorie:Recettes de cuisine à base de légume]] » 775363 wikitext text/x-wiki [[Catégorie:Recettes de cuisine à base de légume]] r04ea7yackhk481mqk6nmp1ss2eims2 775365 775363 2026-10-18T12:17:50Z Cdang 1202 775365 wikitext text/x-wiki {{suppression Immédiate|faute d'orthographe|cdang}} omv6lua9y8y9m8ogvhmy290rb9dnvnz 0 84596 775394 2026-10-19T02:06:05Z ~2026-55818-61 124753 yo 775394 wikitext text/x-wiki Phsychoritiapios 55qqb7bs6b4e6vqvkw2gynbnq02plet 0 84597 775395 2026-10-19T10:44:39Z ~2026-55818-61 124753 Tutoriel utile 775395 wikitext text/x-wiki comment faire des escrent dans une toilette. D'abord, va dans la toilette et ouvre la cuvette des toilettes. Ensuite, baisse tes pantalons et assie tout.Finalement, sors l'escrement et quand tu a finis, tu peut te laver les mains. 542d9ebthqh12h5wicdrbl51mzjekf5