TAGE預測器 “A case for (partially) TAgged GEometric history length branch prediction”

結構特點

• 使用幾何級數的曆史長度和部分标記。
• T0是基礎預測器，2-bit 計數器表，Ti由3-bit計數器（pred）、2-bit u、tag-bit組成。
• USE_ALT_ON_NA：在部分程式中，對新配置設定的項使用altpred預測更有效，使用該4-bit計數器在全局上動态監測這一特性。
• 若一項的預測計數器是弱的則認為它是新配置設定的。

預測

• 如果預測計數器不是弱的或者USE_ALT_ON_NA是無效的，則采用正常最長比對的元件進行預測，否則使用altpred。

預測器更新

• Provider component：曆史最長的比對元件；
• Alternate predictor（altpred）：例如如果T2和T4的tag都比對，則T2為altpred。
• 更新u-bit：當altpred不同于最終預測時，更新provider component的u-bit，實際預測正确時遞增否則遞減（即最終預測采用的是provider的預測，是以要更新provider的u-bit ）。此外，需周期性重置u-bit（作為age counter），以避免一些項被一直标記為有效，最高位列全部置為0，一段時間後，最低位列全部置為0（文中周期是每256K個分支）。
• USE_ALT_ON_NA：部分程式中使用altpred預測更為有效。
• 周期性重置u-bit：先重置整列最高位，經過一段時間再重置最低位，以防止使用率不高的項一直儲存再預測器中。
• 更新預測計數器：提供預測的元件的預測計數器被更新。
• 配置設定新項：預測錯誤時需配置設定新項；如果provider component Ti不是使用最長曆史長度的，則選擇在一個Tk（k>M）上配置設定新項。讀取所有Tj(i<j<M)的u-bit，如果存在某個Tk的u-bit=0，則配置設定新項給元件Tk，否則将Tj的u-bit全部遞減，不配置設定新項。新項初始化為預測計數器為弱相關，u-bit 初始化為0。

分支曆史管理：TAGE依賴于使用非常長的全局分支曆史（幾百位），全局分支曆史和路徑曆史是推測性更新的，是以在錯誤預測時需要恢複。通過循環緩沖區（circular buffer）存儲分支曆史來實作。恢複分支曆史和路徑曆史包括恢複頭指針。

具體實作中的問題

A. 預測響應時間：正常需要3個周期

預測響應時間 = 索引計算時間 + 查表時間 + 預測計算邏輯時間

• 索引計算：使用單級 3 項異或門的非常簡單的索引函數可用于索引預測器元件，而不會顯着影響預測精度。（VS 全散列函數）
• 讀預測表：延遲取決于表的大小，tag 計算可以在索引計算和讀表取期間執行而不影響整體預測計算時間。
• 預測計算邏輯：标簽比對，預測選擇，标簽比對計算是對從标簽元件流出的标簽并行執行的。

B. 解決預測響應時間大于一個周期的問題：提前流水線

       在周期 T0-X 處，使用 X 塊提前程式計數器和 X 塊提前全局曆史讀取預測表。同時計算得到

個預測結果，最後X塊用于選擇最後的預測。

        預測計算：假設預測計算過程需要 X-1 個周期，預測計算需如下兩步。

1. T0-X 周期：預測計算用 T0-X 周期時可用的資訊初始化，即 此時的位址和曆史h。除此之外還需要從 T0-X 到 T0 的路徑上的資訊。 X 位的向量 V 包含路徑上的資訊，在T0-X時向量V的值還不知道，是以有

   

   種可能，同時計算

   

   個預測。
2. T0 周期：在T0-1周期結束的時候，

   

   個預測都已經得到，且在T0時，向量V的實際值已經知道，用實際的V去選擇對應的預測結果。 

性能評估

8-元件的預測器，一個64 Kbits的O-GEHL預測器是2.83MPKI，TAGE是2.61；1Mbit 8-元件的O-GEHL是2.27，1 Mbit 8-元件的TAGE是2.05。

一個128 Kbits 8-元件的TAGE（2.36）和一個512 Kbits 8-元件的O-GEHL（2.34）的準組起來差不多。

 曆史長度和TAG寬度的影響：