我認爲斯科特McFarling以下文件提供了詳細的解答:
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf
讓我用你的代碼來解釋。
unsigned char tab[1<<TABLE_BITS];
是模式歷史表。選項卡中的每個條目都保留一個2位飽和計數器。條件分支的方向最終由計數器的MSB確定:
u.direction_prediction (tab[u.index] >> 1);
爲什麼我們使用兩個或多個位,而不只是一個位的計數器的原因是爲了使圖案,以減少錯誤預測較不敏感。例如,
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
...
}
}
當內循環的下一次執行時,一個比特計數器將誤預測分支而2位計數器,可以防止它。
接下來是如何在模式歷史記錄表中找到正確的模式。
天真的方法是使用分支地址作爲索引。但它忽略了不同分支之間的相關性。這就是爲什麼全球分支機構歷史記錄介紹(更多詳情請參閱http://www.eecg.utoronto.ca/~moshovos/ACA06/readings/two-level-bpred.pdf)。
在你的代碼,
unsigned int history;
是分支歷史寄存器存儲的全局分支歷史。
然後一些人發現,結合全局分支歷史和分公司地址爲指標可能會導致更準確的預測比只用其中的一個。原因是全局分支歷史和分支地址都會影響分支模式。 如果忽略其中的一個,可能會將不同分支模式散列到模式歷史記錄表的相同位置,從而導致碰撞問題。
在提議Gshare之前,有一種稱爲Gselect的解決方案,它使用全局分支歷史和分支地址的串聯作爲模式歷史表的索引。
由Gshare提供的解決方案是
index = branch_addr XOR branch_history
哈希函數這是什麼下面的代碼的意思是:
u.index = (history << (TABLE_BITS - HISTORY_LENGTH))^(b.address & ((1<<TABLE_BITS)-1));
斯科特McFarling的論文提供了一個很好的例子,說明如何Gshare作品優於Gselect:
- Branch Address = 1111_1111 Global Branch History = 0000_0000
個
- 分公司地址= 1111_1111全局分支歷史= 1000_0000
假設我們用下面的G選擇策略,以防止偏差:
index = { {branch_addr[7:4]}, {branch_history[3:0]} }
然後G選擇會產生兩種情況1111_0000而Gshare可以區分不同的模式。
據我所知,Gshare證明是迄今爲止解決碰撞的最佳解決方案。