Branch target predictor (original) (raw)
In computer architecture, a branch target predictor is the part of a processor that predicts the target of a taken conditional branch or an unconditional branch instruction before the target of the branch instruction is computed by the execution unit of the processor. Branch target prediction is not the same as branch prediction which attempts to guess whether a conditional branch will be taken or not-taken (i.e., binary). This predictor reduces the recurrence above to:
| Property | Value |
|---|---|
| dbo:abstract | In computer architecture, a branch target predictor is the part of a processor that predicts the target of a taken conditional branch or an unconditional branch instruction before the target of the branch instruction is computed by the execution unit of the processor. Branch target prediction is not the same as branch prediction which attempts to guess whether a conditional branch will be taken or not-taken (i.e., binary). In more parallel processor designs, as the instruction cache latency grows longer and the fetch width grows wider, branch target extraction becomes a bottleneck. The recurrence is: * Instruction cache fetches block of instructions * Instructions in block are scanned to identify branches * First predicted taken branch is identified * Target of that branch is computed * Instruction fetch restarts at branch target In machines where this recurrence takes two cycles, the machine loses one full cycle of fetch after every predicted taken branch. As predicted branches happen every 10 instructions or so, this can force a substantial drop in fetch bandwidth. Some machines with longer instruction cache latencies would have an even larger loss. To ameliorate the loss, some machines implement branch target prediction: given the address of a branch, they predict the target of that branch. A refinement of the idea predicts the start of a sequential run of instructions given the address of the start of the previous sequential run of instructions. This predictor reduces the recurrence above to: * Hash the address of the first instruction in a run * Fetch the prediction for the addresses of the targets of branches in that run of instructions * Select the address corresponding to the branch predicted taken As the predictor RAM can be 5–10% of the size of the instruction cache, the fetch happens much faster than the instruction cache fetch, and so this recurrence is much faster. If it were not fast enough, it could be parallelized, by predicting target addresses of target branches. (en) 分岐先予測（英: Branch target prediction）とは、CPU内で分岐命令の分岐先アドレスを事前（命令キャッシュから命令をフェッチする前）に予測することである。 分岐先予測と分岐予測は異なる概念である。分岐予測は単に分岐するかしないかを予測することを指す。分岐先予測は、分岐命令を解析して分岐先アドレスが判明する前に、そのアドレスを予測することである。 近年では、命令キャッシュのキャッシュミス時のペナルティが大きくなり、フェッチ幅が大きくなってきている。このため、分岐先の決定がボトルネックになりつつある。このあたりの処理は次のようになる。 1. * 命令キャッシュがブロック単位で命令列をフェッチする。 2. * そのブロック内の命令が走査され、分岐を特定する。 3. * 分岐予測で分岐すると予測されている最初の分岐命令を特定する。 4. * その分岐命令の分岐先アドレスを計算する。 5. * そのアドレスを含むブロックを命令キャッシュにフェッチする。 この処理に2サイクルかかるとしたら、分岐すると予測された命令がみつかる度に1サイクルを無駄にしてしまうことになる。一般に10命令に一回分岐すると予測される命令があるとされ、フェッチ帯域幅が実質的に減少することになる。命令キャッシュのレイテンシが大きいマシンでは、さらに損失が大きくなる。これを何とかするため、一部のマシンでは分岐先予測を行う。これは、分岐命令自体のアドレスから分岐先アドレスを予測するものである。このとき、予測アドレスを格納しておく領域をBTB（Branch Target Buffer）と呼ぶ。もっと積極的な予測方法として、現在実行している逐次命令列の先頭アドレスから、次に実行する逐次実行命令列の先頭アドレスを予測する方式もある。 これによって、上記の処理が以下のように削減される。 1. * 実行する最初の命令のアドレスのハッシュ値を生成 2. * そのハッシュ値に対応した分岐先予測アドレスのリストをフェッチ 3. * その中から、分岐予測で分岐すると予測されているアドレスを選択する。 予測器が使うRAMは命令キャッシュの5%から10%のサイズであり、そのフェッチは命令キャッシュのフェッチよりもかなり前に行われる。そのため、分岐先の命令キャッシュへのフェッチを前倒しできる。これでも不十分な場合は、分岐先アドレスのリストを並列処理する場合もある。 (ja) Nell'architettura dei microprocessori la branch target predictor è un'unità funzionale dedicata alla predizione dell'indirizzo di arrivo di una diramazione condizionata o di un salto non condizionato prima che l'istruzione sia stata caricata dalla cache istruzioni. La cache istruzioni è una cache specializzata. La branch target predictor non va confusa con l'unita di predizione delle diramazioni dato che questa unità cerca di predire se la diramazione varra seguita o no. In molti processori paralleli la cache istruzioni ha una latenza relativamente elevata e quindi l'individuazione dell'indirizzo di arrivo del salto rappresenta un collo di bottiglia. Il procedimento per la sua individuazione esegue le seguenti operazioni: * La cache istruzioni fornisce un blocco di istruzioni * Il blocco di istruzioni viene analizzato alla ricerca delle diramazioni * L'unità di predizione delle diramazioni individua il primo salto che dovrebbe essere eseguito * Viene calcolato l'indirizzo di arrivo del salto * Vengono caricate le istruzioni a partire da quell'indirizzo In molti processori queste operazioni richiedono due cicli di clock e quindi il processore perde un ciclo di clock completo per caricare le nuove istruzioni dopo ogni salto predetto. Dato che mediamente un salto predetto è presente ogni dieci istruzioni eseguite la perdita di prestazioni può essere significativa. Alcuni processori hanno una latenza elevata della cache istruzioni e quindi il degrado delle prestazioni è ancora più elevato. Per ridurre la perdita di prestazione molti processori includono un'unità di branch target predictor, dato l'indirizzo del salto questa unità predice la destinazione del salto. Un miglioramento dell'idea predice l'inizio delle istruzioni sequenziali a partire dall'indirizzo del precedente blocco di istruzioni sequenziali. La predizione riduce le operazioni da eseguire che diventano: * Hash dell'indirizzo della prima istruzione sequenziale * Caricamento dal predittore dell'indirizzo dei salti presenti nel blocco di istruzioni in esecuzione * Selezione dell'indirizzo di arrivo del primo salto predetto Il predittore occupa circa il 5-10% dello spazio della cache istruzioni ma il caricamento delle istruzioni dopo il salto viene velocizzato notevolmente. Se non fosse sufficientemente veloce si potrebbe parallelizzare la predizione degli indirizzi dei salti e la predizione dei salti. La percentuale di predizione di un salto si aggira intorno al 93% di successi. (it) |
| dbo:wikiPageExternalLink | http://www-ee.eng.hawaii.edu/~tep/EE461/Notes/ILP/buffer.html http://www.agner.org/optimize/microarchitecture.pdf |
| dbo:wikiPageID | 1638477 (xsd:integer) |
| dbo:wikiPageLength | 3060 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1118050578 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Computer_architecture dbc:Instruction_processing dbr:Indirect_branch_control dbr:Indirect_branch_prediction_barrier dbr:Indirect_branch_restricted_speculation dbr:Instruction_cache dbr:Single_thread_indirect_branch_predictor dbr:Parallel_processor dbr:Conditional_branch dbr:Branch_prediction dbr:Instruction_fetch dbr:Jump_target_(computing) |
| dbp:date | March 2017 (en) |
| dbp:inaccurate | yes (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_web dbt:Comp-sci-stub dbt:Refimprove dbt:Update |
| dct:subject | dbc:Instruction_processing |
| gold:hypernym | dbr:Part |
| rdf:type | yago:WikicatMicroprocessors yago:Artifact100021939 yago:Chip103020034 yago:Conductor103088707 yago:Device103183080 yago:Instrumentality103575240 yago:Microprocessor103760310 yago:Object100002684 yago:PhysicalEntity100001930 yago:SemiconductorDevice104171831 yago:Whole100003553 |
| rdfs:comment | In computer architecture, a branch target predictor is the part of a processor that predicts the target of a taken conditional branch or an unconditional branch instruction before the target of the branch instruction is computed by the execution unit of the processor. Branch target prediction is not the same as branch prediction which attempts to guess whether a conditional branch will be taken or not-taken (i.e., binary). This predictor reduces the recurrence above to: (en) Nell'architettura dei microprocessori la branch target predictor è un'unità funzionale dedicata alla predizione dell'indirizzo di arrivo di una diramazione condizionata o di un salto non condizionato prima che l'istruzione sia stata caricata dalla cache istruzioni. La cache istruzioni è una cache specializzata. La branch target predictor non va confusa con l'unita di predizione delle diramazioni dato che questa unità cerca di predire se la diramazione varra seguita o no. La predizione riduce le operazioni da eseguire che diventano: (it) 分岐先予測（英: Branch target prediction）とは、CPU内で分岐命令の分岐先アドレスを事前（命令キャッシュから命令をフェッチする前）に予測することである。 分岐先予測と分岐予測は異なる概念である。分岐予測は単に分岐するかしないかを予測することを指す。分岐先予測は、分岐命令を解析して分岐先アドレスが判明する前に、そのアドレスを予測することである。 近年では、命令キャッシュのキャッシュミス時のペナルティが大きくなり、フェッチ幅が大きくなってきている。このため、分岐先の決定がボトルネックになりつつある。このあたりの処理は次のようになる。 1. * 命令キャッシュがブロック単位で命令列をフェッチする。 2. * そのブロック内の命令が走査され、分岐を特定する。 3. * 分岐予測で分岐すると予測されている最初の分岐命令を特定する。 4. * その分岐命令の分岐先アドレスを計算する。 5. * そのアドレスを含むブロックを命令キャッシュにフェッチする。 これによって、上記の処理が以下のように削減される。 1. * 実行する最初の命令のアドレスのハッシュ値を生成 2. * そのハッシュ値に対応した分岐先予測アドレスのリストをフェッチ 3. * その中から、分岐予測で分岐すると予測されているアドレスを選択する。 (ja) |
| rdfs:label | Branch target predictor (en) Branch target predictor (it) 分岐先予測 (ja) |
| owl:sameAs | freebase:Branch target predictor wikidata:Branch target predictor dbpedia-it:Branch target predictor dbpedia-ja:Branch target predictor dbpedia-tr:Branch target predictor https://global.dbpedia.org/id/AecT |
| prov:wasDerivedFrom | wikipedia-en:Branch_target_predictor?oldid=1118050578&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Branch_target_predictor |
| is dbo:wikiPageRedirects of | dbr:Branch_Target_Buffer dbr:Branch_target_buffer |
| is dbo:wikiPageWikiLink of | dbr:Branch_Target_Buffer dbr:Branch_target_buffer dbr:Instruction_unit dbr:Branch_predictor dbr:Classic_RISC_pipeline dbr:IBM_System/390 dbr:Re-order_buffer |
| is foaf:primaryTopic of | wikipedia-en:Branch_target_predictor |