分支轉移預測方法
2023-12-03 19:49:01
專利名稱：分支轉移預測方法
技術領域：
本發明屬於微處理器體系結構領域，特別涉及一種微處理器的分支轉移預測方法。
1993年Scott McFarling提出G-share方案(全稱為Global History withIndex Sharing)，這是一種經典的全局歷史記錄表預測方法。該方法被後來的諸多CPU所採用，成為用單預測器預測分支的經典方案。
在93年之後，很多體系結構方面的專家著重於研究多個預測器共同完成對程序中分支的預測，但在實際應用中沒有取得重大的突破。
在現有的處理器中，處理分支預測多採用雙值預測法，G-share方法和混合預測器。
MIPS的R4000中採用暫停取指，直到分支結果產生的方法來處理分支，這種方法明顯會帶來流水線效率降低。
MIPS的R10000中採用的是在分支結果產生之前，按預測的地址取址。這種方法在預測正確時，並不增加延遲，但當猜測錯誤時，取消已經取進的指令並重新取指，從而引起流水線的斷流，增加了很大的延遲。
Alpha的21064、21164採用的是兩位的雙值預測器，Sun的UltraSparcIII採用的是標準G-share預測器(G-share Predictor)；Alpha的21264採用的是混合預測器。
但是上述方法主要有如下缺點有待改進一、雙值預測器由於其命中率較低，不適用於多重循環。
二、G-share方法的全局歷史記錄表中的高位，也就是離當前預測的分支相對而言較遠的分支結果，往往對當前分支的方向指示並不是很強，因此正確率不高。
三、混合預測器過於複雜，而且控制邏輯非常龐大。
本發明一種分支轉移預測方法，包含下列步驟a)當系統遇到分支轉移指令時，從程序計數器PC中獲取當前指令的計數值，並從全局歷史記錄表中獲取歷史記錄；b)利用作業系統對系統空間和用戶空間的嚴格控制，使用程序計數器PC和前述步驟a)中獲得的歷史記錄拼接成新的全局記錄；c)前述步驟中得到的新的全局記錄取代傳統全局歷史預測方法中的全局歷史記錄，協同程序計數器PC進行分支預測。
利用PC中的含有重要信息的位，取代原有全局歷史記錄中的高位，再與原有的全局歷史記錄的剩餘位拼接形成新的全局記錄。
具體實施例方式
請結合參閱圖2，本發明一種分支轉移預測方法，包含下列步驟a)當系統遇到分支轉移指令時，從程序計數器PC中獲取當前指令的計數值，並從全局歷史記錄表中獲取歷史記錄；b)利用作業系統對系統空間和用戶空間的嚴格控制，使用程序計數器PC和前述步驟a)中獲得的歷史記錄拼接成新的全局記錄；c)前述步驟中得到的新的全局記錄取代傳統全局歷史預測方法中的全局歷史記錄，協同程序計數器PC進行分支預測。
利用PC中的含有重要信息的位(如圖2中的PC 31)，取代原有全局歷史記錄中的高位，再與原有的全局歷史記錄的剩餘位拼接形成新的全局記錄。
G-share方法用分支指令的地址作為區分不同分支的重要標誌，將n位地址的高m位與歷史記錄的m位異或，然後再拼成新的n位地址去查尋分支模式表。在圖中，程序計數器的內容是指等待預測的分支指令的PC地址，全局歷史記錄中記錄的是最近發生的分支結果。由於PC本身的最低兩位始終為零，因此選取程序計數器PC的n位(不包括低兩位無意義的0)，用其中m位與全局歷史記錄的m位相異或，在拼接上餘下的(n-m)位，形成n位分支模式表索引，對分支模式表進行查找，決定分支轉移方向。
本發明提出了一種全局分支預測方法，吸收了經典全局表預測器G-share方法的思想，超越了傳統G-share方法。不再只使用全局歷史記錄和低位PC地址進行預測，而是通過對程序運行中所處狀態空間的分析，在預測中加入程序所處狀態的信息，再配以全局歷史記錄和低位PC地址進行預測。
當系統遇到分支轉移指令時，從程序計數器PC中獲取當前指令的計數值，並從全局歷史記錄表中獲取歷史記錄。
首先利用作業系統對系統空間和用戶空間的嚴格控制，使用程序計數器PC和在全局歷史記錄表中獲得的歷史記錄拼接成新的全局記錄。
前述步驟中得到的新的全局記錄取代傳統全局歷史預測方法中的全局歷史記錄，協同程序計數器PC進行分支預測。
其中，新的全局記錄的形成方法是，利用PC中的某些含有重要信息的位，如圖2中的PC 31，取代原有全局歷史記錄中的高位，再與原有的全局歷史記錄的剩餘位拼接形成新的全局記錄。
由於在預測時加入了程序所處狀態空間的有效信息，因此使用本發明的分支預測方法獲得的預測成功率比標準G-share方法有明顯的提高。
有關本發明的詳細原理，下面舉一具體實例，並配合圖2進行說明。
圖2是本發明的分支預測器的示意圖。
針對本發明所應用的龍芯處理器和Linux(Unix)作業系統，可以通過引入PC地址的最高位PC 31來實現前述方法。在圖2中，程序計數器的內容是指等待預測的分支指令的PC地址，全局歷史記錄中記錄的是最近發生的分支結果。選取程序計數器PC的n位(不包括低兩位無意義的0)，用其中m位與全局歷史記錄的m-1位加上PC的最高位PC 31所組成的新m位結果相異或，形成n位分支模式表索引，對分支模式表進行查找，決定分支方向。
因為在這種作業系統中，PC 31是一個很重要的標誌，標誌著一個程序究竟是運行在用戶空間中還是在系統空間中，因此在大多數情況下，他所包含的信息要遠比離當前分支指令較遠的全局分支結果(即全局歷史記錄的高位)更有方向性，對預測更有好處，因此引入PC 31對系統的性能會有很大的提高。而在真實的系統中，由於程序在用戶空間和系統空間之間的切換是很頻繁的，因此作用就更加明顯了。實踐結果也證明了這一點。在實際系統中，本發明的預測準確率比G-share方法有明顯的上升。
在其他作業系統中，在PC地址中也可以找到相應的標記程序空間的信息位，利用上述思想進行預測，同樣可以提高系統的預測準確率。
由前述方法可知，本發明的優點在於不需要增加任何額外的邏輯就可以獲得很好的性能提升，同時可以比正常G-share方法少需要至少一位全局歷史記錄。
權利要求
1.一種分支轉移預測方法，包含下列步驟a)當系統遇到分支轉移指令時，從程序計數器PC中獲取當前指令的計數值，並從全局歷史記錄表中獲取歷史記錄；b)利用作業系統對系統空間和用戶空間的嚴格控制，使用程序計數器PC和前述步驟a)中獲得的歷史記錄拼接成新的全局記錄；c)前述步驟中得到的新的全局記錄取代傳統全局歷史預測方法中的全局歷史記錄，協同程序計數器PC進行分支預測。
2.根據權利要求1所述的分支轉移預測方法，其特徵在於，利用PC中的含有重要信息的位，取代原有全局歷史記錄中的高位，再與原有的全局歷史記錄的剩餘位拼接形成新的全局記錄。
全文摘要
一種分支轉移預測方法，屬於微處理器體系結構領域；一種分支轉移預測方法，包含下列步驟a)當系統遇到分支轉移指令時，從程序計數器PC中獲取當前指令的計數值，並從全局歷史記錄表中獲取歷史記錄；b)利用作業系統對系統空間和用戶空間的嚴格控制，使用程序計數器PC和前述步驟a)中獲得的歷史記錄拼接成新的全局記錄；c)前述步驟中得到的新的全局記錄取代傳統全局歷史預測方法中的全局歷史記錄，協同程序計數器PC進行分支預測。
文檔編號G06F9/42GK1447231SQ0210778
公開日2003年10月8日 申請日期2002年3月22日 優先權日2002年3月22日
發明者馮雷 申請人:中國科學院計算技術研究所