本題鏈接：

https://hdlbits.01xz.net/wiki/Cs450/history_shift

分支預(yù)測(cè)器通常由程序計(jì)數(shù)器和分支歷史記錄索引的計(jì)數(shù)器表組成。分支歷史記錄是來(lái)自最近分支的“taken”或“not taken”結(jié)果的序列。

在硬件中，分支歷史寄存器可以由 N 位移位寄存器來(lái)實(shí)現(xiàn)?。預(yù)測(cè)每個(gè)條件分支方向后，其預(yù)測(cè)方向?qū)?huì)移位到移位寄存器中。因此移位寄存器會(huì)保存最新的 N 個(gè)分支結(jié)果。

由于分支預(yù)測(cè)是由推測(cè)完成的，因此流水線(xiàn)的刷新會(huì)增加額外的復(fù)雜性。當(dāng)發(fā)生分支預(yù)測(cè)錯(cuò)誤時(shí)，處理器狀態(tài)需要立即回滾到錯(cuò)誤的預(yù)測(cè)分支之前的狀態(tài)。這包括回滾全局歷史寄存器，其中可能包含預(yù)測(cè)的分支結(jié)果，這些結(jié)果由比錯(cuò)誤預(yù)測(cè)分支更新的分支移入，但現(xiàn)在需要舍棄。

我們?cè)谶@里假設(shè)分支預(yù)測(cè)器之外的硬件會(huì)記住用于預(yù)測(cè)每個(gè)分支的分支歷史寄存器的狀態(tài)，并將其保存以供用于以后的分支預(yù)測(cè)器訓(xùn)練和流水線(xiàn)刷新。當(dāng)發(fā)生錯(cuò)誤的分支預(yù)測(cè)時(shí)，此硬件會(huì)告知分支預(yù)測(cè)器的分支已預(yù)測(cè)錯(cuò)誤和應(yīng)該采取的分支，這些狀態(tài)與預(yù)測(cè)錯(cuò)誤的分支之前程序中的點(diǎn)相對(duì)應(yīng)。

當(dāng)然，由于處理器重新復(fù)位到錯(cuò)誤預(yù)測(cè)分支后的點(diǎn)，因此流水線(xiàn)刷新后的分支歷史寄存器需要附加錯(cuò)誤預(yù)測(cè)分支的實(shí)際方向。

描述

構(gòu)建一個(gè) 32 位全局歷史移位寄存器，功能包括支持回滾狀態(tài)以響應(yīng)由分支預(yù)測(cè)錯(cuò)誤引起的流水線(xiàn)刷新。

當(dāng)進(jìn)行分支預(yù)測(cè) ?(predict_valid?= 1) 時(shí)，從 LSB 端移入?predict_taken?以更新預(yù)測(cè)分支的分支歷史記錄。（predict_history[0]是最新的分支的方向)

當(dāng)發(fā)生分支錯(cuò)誤預(yù)測(cè) （train_mispredicted = 1） 時(shí)，在錯(cuò)誤預(yù)測(cè)的分支完成后，將分支歷史記錄寄存器與歷史記錄一起加載。這是在錯(cuò)誤預(yù)測(cè)的分支 （train_history） 與分支 （train_taken） 的實(shí)際結(jié)果相連接之前的歷史記錄。

如果同時(shí)發(fā)生預(yù)測(cè)和錯(cuò)誤預(yù)測(cè)，則優(yōu)先錯(cuò)誤預(yù)測(cè)，因?yàn)榱魉€(xiàn)刷新也會(huì)刷新當(dāng)前進(jìn)行預(yù)測(cè)的分支。

predict_history 是分支歷史寄存器的值

areset 是一個(gè)異步復(fù)位，將歷史計(jì)數(shù)器復(fù)位為零

題目

答案

輸出波形

異步復(fù)位

向上計(jì)數(shù)，然后向下計(jì)數(shù)

分支預(yù)測(cè)器（英語(yǔ)：Branch predictor）是一種數(shù)字電路，在分支指令執(zhí)行結(jié)束之前猜測(cè)哪一路分支將會(huì)被執(zhí)行，以提高處理器的指令流水線(xiàn)的性能。

條件分支指令通常具有兩路后續(xù)執(zhí)行分支。即不采?。╪ot taken）跳轉(zhuǎn)，順序執(zhí)行后面緊挨JMP的指令；以及采?。╰aken）跳轉(zhuǎn)到另一塊程序內(nèi)存去執(zhí)行那里的指令。

是否條件跳轉(zhuǎn)，只有在該分支指令在指令流水線(xiàn)中通過(guò)了執(zhí)行階段（execution stage）才能確定下來(lái)。

如果沒(méi)有分支預(yù)測(cè)器，處理器將會(huì)等待分支指令通過(guò)了指令流水線(xiàn)的執(zhí)行階段，才把下一條指令送入流水線(xiàn)的第一個(gè)階段—取指令階段（fetch stage）。這種技術(shù)叫做流水線(xiàn)停頓（pipeline stalled）或者流水線(xiàn)冒泡（pipeline bubbling）或者分支延遲間隙。這是早期的RISC體系結(jié)構(gòu)處理器采用的應(yīng)對(duì)分支指令的流水線(xiàn)執(zhí)行的辦法。

分支預(yù)測(cè)器猜測(cè)條件表達(dá)式兩路分支中哪一路最可能發(fā)生，然后推測(cè)執(zhí)行這一路的指令，來(lái)避免流水線(xiàn)停頓造成的時(shí)間浪費(fèi)。如果后來(lái)發(fā)現(xiàn)分支預(yù)測(cè)錯(cuò)誤，那么流水線(xiàn)中推測(cè)執(zhí)行的那些中間結(jié)果全部放棄，重新獲取正確的分支路線(xiàn)上的指令開(kāi)始執(zhí)行，這招致了程序執(zhí)行的延遲。

在分支預(yù)測(cè)失敗時(shí)浪費(fèi)的時(shí)間是從取指令到執(zhí)行完指令（但還沒(méi)有寫(xiě)回結(jié)果）的流水線(xiàn)的級(jí)數(shù)?，F(xiàn)代微處理器趨向采用非常長(zhǎng)的流水線(xiàn)，因此分支預(yù)測(cè)失敗可能會(huì)損失10-20個(gè)時(shí)鐘周期。越長(zhǎng)的流水線(xiàn)就需要越好的分支預(yù)測(cè)。

一條條件跳轉(zhuǎn)指令第一次遇到，還沒(méi)有任何信息可以去預(yù)測(cè)分支。此后保持這條指令是采取還是不采取跳轉(zhuǎn)的歷史記錄，就可以作為再遇到這條指令時(shí)猜測(cè)最可能的分支。

飽和計(jì)數(shù)器（saturating counter）或者稱(chēng)雙模態(tài)預(yù)測(cè)器（bimodal predictor）是一種有4個(gè)狀態(tài)的狀態(tài)機(jī)：

• 強(qiáng)不選擇（Strongly not taken）

• 弱不選擇（Weakly not taken）

• 弱選擇（Weakly taken）

• 強(qiáng)選擇（Strongly taken）

當(dāng)一個(gè)分支命令被求值，對(duì)應(yīng)的狀態(tài)機(jī)被修改。分支不采納，則向“強(qiáng)不選擇”方向降低狀態(tài)值；如果分支被采納，則向“強(qiáng)選擇”方向提高狀態(tài)值。這種方法的優(yōu)點(diǎn)是，該條件分支指令必須連續(xù)選擇某條分支兩次，才能從強(qiáng)狀態(tài)翻轉(zhuǎn)，從而改變了預(yù)測(cè)的分支。

參考內(nèi)容：

分支預(yù)測(cè)器 - 維基百科，自由的百科全書(shū) (wikipedia.org)：

https://zh.wikipedia.org/zh-cn/%E5%88%86%E6%94%AF%E9%A0%90%E6%B8%AC%E5%99%A8