降低函數調用分支別名的神經網絡預測器

摘 要:通過對程序調用過程中分支預測空間特性的分析，發現傳統神經網絡算法在不同函數調用相同子函數時容易出現別名效應，進而提出了一種基于子函數權重索引離散的神經網絡分支預測器。該預測器通過調用信息堆棧記錄函數調用中的父函數的路徑信息，并用該信息離散子函數權重索引，有效降低了由于不同父函數調用相同子函數造成的別名效應。實驗結果顯示，基于該方法的神經網絡分支預測器的預測錯誤率降低1%~10%。

關鍵詞:神經網絡; 別名效應; 權重索引離散

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2047-04

doi:10.3969/j.issn.1001-3695.2010.06.014

Neural branch prediction with alias reducing between function calls

SHA Zi-yan， MENG Jian-yi， YAN Xiao-lang， GE Hai-tong

(Institute of VLSI Design， Zhejiang University， Hangzhou 310027， China)

Abstract:With the spatial property analysis of the branch prediction， found the traditional neural branch prediction method had alias effect between function calls. Proposed a new receptor accessing mechanism with index dispersing in sub-function. It saved the path information in function calling stack for functions and dispersed the receptor index with the path information in branch prediction. It would differentiate the branch of sub-function in different function calling and could eliminate the prediction alias effect between function calls. Experiment shows that the neural prediction with alias reducing can decrease the misprediction rate by 1%～10%.

Key words:neural prediction; prediction alias; index dispersing

0 引言

隨著應用對處理器性能需求日益提高，超標量和深流水線已經成為當前嵌入式處理器的主流技術[1]。但程序中普遍存在的條件分支是破壞超標量和深流水線連續運行的主要原因，由條件分支指令造成的流水線性能損失已經成為制約處理器性能提升的主要瓶頸[1]，為了減少條件分支造成的流水線性能損失，現代處理器普遍采用分支預測技術。

分支預測本質是在分支條件尚未確定的情況下利用已知分支歷史信息預測當前分支跳轉狀態的一種機制。分支預測器主要經歷了2位分支預測器、全局/局部歷史分支預測器，以及神經網絡分支預測器三個階段的發展演化[2~4]。早期的2位分支預測器只通過前續分支歷史一種信息預測分支結果[2]，預測準確率較低。全局/局部歷史預測器采用分支地址和分支歷史兩種信息進行預測[3，4]，有效減少了由于歷史信息相同而造成的分支歷史別名[5]，提高了分支預測的準確率。但全局/局部兩級分支預測器需要通過增加分支地址和歷史的信息長度來提高預測率，預測器硬件資源的開銷以信息位呈2的指數倍增加。神經網絡預測器則將神經網絡算法引入分支預測領域，通過感受器預測分支跳轉，使分支預測具有自學習的特性，有效提高了分支預測的準確性。傳統的神經網絡預測器在記錄分支歷史信息的基礎上，通過調整各個分支歷史的權重進行學習，并采用權重與歷史的點乘預測當前分支指令的跳轉狀態，準確率一般可以達到90%以上[6]。由于神經網絡預測器通過感受器記錄預測信息，其硬件資源與分支歷史位寬呈線性關系，大大降低了提高分支歷史長度帶來的硬件開銷。神經網絡預測器以其低的硬件開銷和高的預測準確率等特征，成為嵌入式處理器分支預測機制的主要研究內容。

本文首先通過分析程序邏輯結構和動態運行特征，發現了神經網絡預測器在函數調用過程中出現的分支別名現象，進而提出了一種通過離散子函數的權重索引降低函數調用別名效應的方法。該方法通過調用信息堆棧記錄父函數分支路徑特征信息，并將該信息引入到子函數分支預測的信息索引產生過程中。由于子函數權重索引被不同父函數的分支路徑信息離散，相同子函數內的分支在不同的函數調用中獲得不同的感受器資源，從而有效降低子函數內分支預測的別名效應。實驗表明，基于該方法的神經網絡分支預測器可以在較小的硬件代價下，降低分支預測錯誤率1%~10%。

1 神經網絡分支預測器

1.1 基本結構

神經網絡分支預測器將分支跳轉歷史信息作為感受器的輸入，通過在預測中不斷調整相應感受器的權重，學習分支指令跳轉的規律，預測分支指令的跳轉狀態。式(1)顯示了神經網絡預測器的基本數學模型[6]。其中，{ W0，W1，W2，W3，…，Wn-1，Wn}是當前索引得到的分支歷史的權重向量;{H0，H1，H2，H3，…，Hn-1，Hn}是分支歷史向量，對于其中的任意元素Hi，1表示跳轉，-1表示不跳轉，H0恒為1。當SUM為正時，預測結果為跳轉;反之則為不跳轉。在預測失誤或者SUM小于閾值sita時，權重向量需要被訓練。假設預測考慮的歷史長度為h，根據經驗[6]，sita=1.93h+14。

SUM=∑Wi×Hi(1)

與普通預測器類似，神經網絡預測器也是通過前續分支信息索引權重向量，因此也容易產生潛在的別名效應。本文所指的別名效應指兩個在時間、空間不同的分支在預測時訪問同一個信息存儲空間，并由此造成信息讀取和更新錯誤的情況。分支別名效應的直接后果是降低分支預測準確率。降低分支預測別名效應的常用方法有兩種:a)簡單地提高信息索引范圍，這樣會帶來比較大的硬件開銷;b)在不提高信息索引范圍的情況下，使用復雜的算法作為信息索引機制來避免信息的錯誤訪問[7，8]，但是這樣會導致設計復雜度的成倍提高。分支別名效應是神經網絡分支預測機制進一步提高預測準確率的主要障礙。

1.2 函數調用中的別名效應

現有降低分支別名效應的神經網絡預測算法都是將分支歷史信息直接送入神經網絡感受器，通過神經網絡的統一學習機制，給出當前分支跳轉與各個歷史之間的關系以及當前分支跳轉的預測結果。但通過分析程序的執行過程，發現分支不僅在不同的函數中具有不同的屬性，而且相同函數內的分支在不同函數調用過程中也是有差別的。

圖1顯示了程序執行過程中函數之間的調用關系。其中，A1、A2和C1、C2分別表示兩個不同層次父函數的兩部分代碼;B表示被A和C調用的相同子函數。子函數B分別在A1和C1執行完畢后被調用兩次。在傳統神經網絡分支預測機制中，由于子函數B僅根據自己函數內部的分支歷史進行預測，在兩次調用中容易出現相同的分支歷史，從而造成分支別名現象。本文重點針對函數調用過程中的分支別名問題展開深入的研究并形成相應的解決方法。

在函數調用過程中，父函數通過參數傳遞控制子函數的分支跳轉行為。這種隱式的控制信息的傳遞過程容易導致子函數中的分支歷史提取出現錯誤。現有分支預測器，本質上通過無差別的記錄并分析分支歷史，確定當前分支指令與某次分支歷史一致。這種算法由于無法通過記錄的信息辨別分支所屬于子函數與函數之間的調用關系，從而也無法精確區分不同父函數對子函數的調用關系，直接導致每次子函數內的分支均出現信息提取的沖突。對于神經網絡分支預測器，在不同父函數調用同一個子函數時，子函數分支指令在預測時將訪問同一區域的感受器，當父函數對該分支產生相反影響時(如父函數A調用子函數B時訓練為跳轉，但父函數C調用子函數B時訓練為不跳轉)，感受器訓練的信息將會相互干擾，從而產生了函數調用過程中的別名效應。

由此可見，在不區分分支的空間特性下，僅提取分支指令的歷史權重信息時會出現較為嚴重的函數調用別名效應，影響分支預測的準確性。函數調用關系越復雜，分支別名效應的機率就越大。為了取得更高的分支預測準確率，本文提出了一種通過引入父函數空間特征信息，并通過空間特征信息離散子函數分支歷史的方法，降低函數調用過程中的出現別名效應的概率。

2 子函數權重索引離散算法研究

函數調用中的別名效應本質上是本次子函數調用訪問了上次不同的父函數調用時訪問的信息記錄空間，造成感受器信息的錯誤預取或錯誤訓練。本文解決這種分支別名問題的主要思路是將子函數按照父函數調用關系加以區分，不同父函數調用的子函數獨享感受器硬件資源，從而實現各次函數調用中的子函數分支預測互不干擾。本文重點研究一種通過父函數的分支路徑離散子函數預測索引的方法，有效解決了子函數分支在不同調用的重疊問題。定義new_index是經過離散后的感受器索引，old_index是傳統分支預測的索引，info是從父函數的繼承的空間特征信息，mix是信息離散函數，因此基于子函數分支索引離散的數學模型為

new_index = mix (old_index，info)(2)

從式(2)可知，基于子函數分支索引離散方法的本質是找到一種合適的父函數特征信息和一種高效的離散算法。

在對父函數的特征信息進行選擇中，分支預測算法只能獲得各個分支的地址以及分支狀態(跳轉或不跳轉)。這兩種信息及它們的組合包括單分支地址、單分支跳轉狀態、組合的分支歷史、組合的分支路徑等。組合的分支歷史(單分支跳轉狀態的組合)在同一個函數進行多次調用時，其信息可能不相同，這樣在子函數被同一個父函數多次調用時預測過程無法參考上次的分支預測信息，反而可能造成預測準確率的下降。分支跳轉狀態(單個分支)由于只有跳轉和不跳轉兩種狀態，在不同父函數調用子函數時狀態相同的概率比較高，不能有效地離散子函數調用中的別名效應。排除分支歷史和單分支跳轉狀態(單個分支)兩種選擇，滿足本文離散子函數索引要求的父函數特征信息只有分支地址和分支路徑。

信息混合函數mix也有多種方案，考慮到硬件電路的實現簡易，本文選擇AND(按位與)、OR(按位或)、XOR(按位異或)、FA(全加)四種邏輯電路列入選擇。四種邏輯運算的真值表如下:

AND: 11=1，10=0， 00=0， 01=0

OR:0|1=1， 1|0=1，0|0=0，1|1=1

XOR: 1∧0=10∧1=11∧1=0 0∧0=0

FA: 0+1=11+0=10+0=0 1+1=(1)0

由真值表可見，AND邏輯存在0與任何值運算都是0的性質，導致混合后的新索引信息的各位是0的可能性加大。假設所有位在信息混合前的狀態完全隨機，這樣新的索引方式在索引預測信息時會傾向于訪問少數信息空間，從而引入新的別名效應，所以AND邏輯不是最佳的信息混合函數。基于同樣的原理，OR邏輯，由于存在1與任何值運算都是1的性質，也同樣不適于成為信息混合函數。根據真值表的結果，全加器和按位異或運算不會產生額外的別名效應，因而均滿足信息混合函數的基本要求，但是全加器的位數也會隨著分支預測歷史長度的加長而相應增長，在硬件上造成電路的復雜度提高，時序性能的逐漸變差;而按位異或邏輯則不會出現分支歷史變長造成的種種弊端，所以在硬件實現上相對全加邏輯更有優勢。

基于以上分析，本文將重點研究比較以地址或路徑作為父函數特征信息，以XOR和FA作為混合函數的子函數離散算法。

3 算法實現

為了實現子函數離散算法，本文對傳統的path-base神經網絡分支預測算法的權重索引機制進行基于子函數權重索引離散算法的改造，在原有算法中加入了父函數特征信息儲存和索引信息混合(產生新的權重索引向量)的關鍵邏輯用于產生新的權重索引向量。

為了記錄函數調用的父函數特征信息，并且在預測中進行有效的管理，本文在原來的算法模塊中加入了調用信息堆棧。調用信息堆棧在函數調用時進行壓棧操作，將特征信息加以記錄。在函數返回時，恢復原有特征信息。其中，函數調用和返回的相關信息來自處理器本身對函數調用和返回相關指令的識別。本文采用CKCORE指令集架構，函數調用采用jsri和jsr指令，函數返回采用jmp r15指令。處理器在jsri、jsr指令執行完畢后，則通知分支預測器的調用信息堆棧進行了函數調用操作。執行jmp r15指令后，通知調用信息堆棧執行函數返回操作。

在預測過程中，調用信息堆棧取出當前指針所指地址的信息作為本次預測對應的函數調用特異信息，與原有索引信息進行信息混合后，成為新權重索引向量用于索引當前預測過程的權重。信息調用堆棧的功能用偽代碼描述如下:

function fuction_call_return_manage;begin//初始化時通過系統復位信號，使棧頂指針復位initial{ func_ptr=0; }//函數調用時，執行入棧操作，棧頂指針加1if(function_call){ func_ptr=func_ptr+1 entry[func_ptr]=information; }//函數返回時，執行出棧操作，棧頂指針減1if(function_return0){ func_ptr=fun-1;}endfunctionfunction get_weight;new_index=old_index mix entry[func_ptr];

weight=weight_entry[new_index];endfunction

其中:func_ptr為函數指針，表示調用信息堆棧的棧頂指針;數組entry[]表示調用信息堆棧的信息存放入口;weight_entry為權重信息的存放入口。在系統初始化時棧頂指針復位，每次函數調用時指針加1并存儲空間信息，在函數返回時清除函數對應的空間信息，指針減1。其中，

預測中父函數特征信息與原有索引向量進行信息混合，得到新的權重索引向量。

改進后的path-base預測器的權重索引機制硬件實現如圖2所示。

4 實驗與結論

4.1 實驗環境介紹

本文選擇嵌入式基準程序PowerStone進行算法的模擬實驗，研究采用不同離散算法下的分支預測準確率和基于子函數權重索引離散的神經網絡分支預測器的預測準確率。表1給出了PowerStone所包含的測試程序的總指令條數及其分支的比例。

表1 PowerStone測試基準簡介

測試程序總指令條數條件跳轉指令條數測試程序總指令條數條件跳轉指令條數

jpeg9 071 462234 152engine749 78533 692

v425 305 923366 649compress283 37514 806

fir3 156 662191 699qurt200 76710 976

g3fax2 775 967168 251

實驗首先利用CKCORE工具鏈和CKCORE處理器行為模型(ISA)編譯運行相關BenchMark，記錄輸出分支跳轉信息，然后編寫相關分支預測器軟件模型，在分支預測器仿真模擬中讀取分支跳轉信息對分支預測算法進行仿真。

4.2 四種離散算法的結果比較

為了更加有效地進行子函數離散，本文通過實驗對特征信息和混合函數進行進一步分析。備選的父函數特征信息有分支地址(ADDR)和分支路徑(PATH)兩種，備選的信息混合函數包括XOR和FA。實驗中分別采用四種離散子函數分支預測算法，四種算法的特征信息和混合函數分別是(ADDR，XOR)、(PATH，XOR)、(ADDR，FA)、(PATH，FA)。

使用分支地址作為特征信息時，采用函數調用指令的指令pc;使用分支路徑作為特征信息時，由于各個分支地址的位數較多，考慮到程序執行過程中高位地址不易改變，可以截取低位拼成特征信息。本文采用相同的硬件開銷(感受器存儲空間32 KB，歷史長度32 bit)進行模擬，四種算法在PowerStone下預測失誤率如圖3所示。

從圖3結果顯示，采用分支路徑信息與采用分支地址信息作為父函數特征信息效果相當，因而出于硬件設計簡單的原因可以采用地址作為父函數特征信息。結果還顯示在信息混合函數中FA邏輯比XOR邏輯略好。這是由于按位異或邏輯是簡化的無進位的全加邏輯，離散效果比全加邏輯略差;但是XOR的硬件實現簡單，仍然是信息混合函數的理想選擇。

4.3 分支預測準確率分析

對path-base分支預測算法進行改造，加入調用信息堆棧管理父函數特征信息(地址)，并使用XOR函數離散子函數索引，與原來的path-base算法預測準確率對比如表2所示(硬件開銷32 KB，歷史長度32 bit)。

表2 預測錯誤率模擬比較結果

測試程序傳統預測錯誤率/%改進后預測錯誤率/%預測錯誤率降低比例/%

jpeg4.554.510.89

v425.895.781.87

fir7.197.101.25

engine4.904.002.25

compress8.938.218.06

qurt11.4310.0512.07

表2結果顯示，在算法中加入離散相關功能后，通過對子函數權重索引的離散實現子函數在不同的調用中具有不同的感受器索引，消除函數調用過程中的別名效應。從數據來看，分支預測失誤率大概下降了1%~10%。不同函數由于調用關系復雜度不一樣，其性能改進也不一樣，如調用關系簡單的jpeg，每個子函數都被一個父函數調用，其改進也越小(它們的降低來自于庫函數的調用);與此相對的qurt應用中，qurt子函數被多個函數調用，其采用改進后的預測算法對于性能提升也就越明顯。通常情況下，函數調用關系越復雜，應用本文提出的降低函數調用分支別名神經網絡感受器預測準確率也就越高。

5 結束語

本文通過對程序執行過程的分析，發現了函數調用中出現的別名效應，提出了離散子函數索引的分支預測算法，并對算法中的離散函數和父函數特征信息進行了理論和實驗兩個層次上的深入研究。離散子函數索引算法的相關實驗結果表明，采用XOR算法和路徑信息可以有效地解決函數調用過程中產生的別名效應，使分支預測的失誤率明顯下降，取得了預期的效果。

參考文獻:

[1]PATT Y N， PATEL S J， FRIENDLY D H， et al. One billion transistors， one uniprocessor， one chip[C]//Proc of IEEE Computer.1997:51-57.

[2]SMITH J E. A study of branch prediction strategies[C]//Proc of the 8th International Symposium. Computer Architecture.1981.

[3]PAN S， SO K， RAHMEH J T. Improving the accuracy of dynamic branch prediction using branch correlation[C]//Proc of the 5th In-ternational Conference on Architectural Support for Programming Languages and Operating Systems.1992:76-84.

[4]YEH T Y， PATT Y N. Two-level adaptive branch prediction[C]//Proc of the 24th ACM/IEEE International Symposium Microarchitecture.1991.

[5]YEH T Y， PATT Y N. Alternative implementations of two-level adaptive branch prediction[C]//Proc of the 19th Annual International Symposium. Computer Architecture.1992:124-134.

[6]JIMENEZ D A， LIN C. Neural methods for dynamic branch prediction[J]. ACM Trans on Computer Systems，2002，20(4):369-397.

[7]JIMENEZ D A. Fast path-based neural branch prediction[C]//Proc of the 36th International Symposium on Microarchitecture.2003.

[8]TARJAN D， SKADRON D. Merging path and gshare indexing in perception branch prediction[J]. ACM Trans on Architecture and Code Optimization，2005，2(3):280-300.