面向非規(guī)則數(shù)據(jù)的差別預(yù)取策略

面向非規(guī)則數(shù)據(jù)的差別預(yù)取策略

1基于訪存流模型的數(shù)據(jù)預(yù)取技術(shù)由于處理器和存儲設(shè)備之間的速度差，存儲墻問題一直是制約處理器性能的重要因素。由于存儲墻問題的存在，cpu的操作能力由于等待內(nèi)存數(shù)據(jù)而浪費，因此現(xiàn)代計算機(jī)系統(tǒng)中強(qiáng)大的處理器性能難以充分利用。數(shù)據(jù)預(yù)取技術(shù)是解決存儲墻問題的重要研究領(lǐng)域之一.基于訪存流模型的數(shù)據(jù)預(yù)取技術(shù)作為傳統(tǒng)數(shù)據(jù)預(yù)取技術(shù)的擴(kuò)展方案,是隱藏非規(guī)則數(shù)據(jù)訪存延遲的常用實現(xiàn)方案.當(dāng)前國內(nèi)外基于訪存流模型的數(shù)據(jù)預(yù)取技術(shù)的研究才剛剛起步,還存在很多不足之處:對存儲空間劃分區(qū)域后再構(gòu)造時空局部性模型,容易把訪存地址規(guī)律而間距大的訪存行為劃分為很多不同的訪存區(qū)域,增加了模式及其識別的復(fù)雜度;對導(dǎo)致Cache訪問失效的指令等同看待,只是部分地重構(gòu)了訪存流;對程序的所有Cache訪問失效數(shù)據(jù)進(jìn)行分析,一方面浪費了空間資源,另一方面有些隨機(jī)的Cache訪問失效會對主要關(guān)注數(shù)據(jù)造成不必要的干擾.因此,如何根據(jù)非規(guī)則計算的特性,基于訪存流構(gòu)建面向復(fù)雜數(shù)據(jù)結(jié)構(gòu)的通用的、高效的預(yù)取模型,是本文研究的重點.2程序?qū)Φ刂沸蛄械脑L問具有非連續(xù)局部性高速緩存Cache和數(shù)據(jù)預(yù)取技術(shù)之所以起到隱藏訪存延遲的作用是因為程序運行時對存儲器數(shù)據(jù)的訪問具有局部性特征,局部用到的數(shù)據(jù)存放在緩存中,提高了緩存命中率.定義1時間局部性(TemporalLocality).指程序在運行時剛剛被訪問過的數(shù)據(jù)很快又被訪問到.當(dāng)程序需要訪問的數(shù)據(jù)不在Cache中時,就把相應(yīng)的內(nèi)容從內(nèi)存取到Cache行中,這樣在下一次訪問它時就不會發(fā)生緩存失效了.定義2空間局部性(SpatialLocality).指在訪問內(nèi)存中一塊數(shù)據(jù)后的極短時間段內(nèi),內(nèi)存中與其鄰接的一塊內(nèi)容也會被訪問到.如果在訪問內(nèi)存中的一個數(shù)據(jù)塊時,順帶把與其鄰接的數(shù)據(jù)塊也取到Cache中,這樣在不久訪問鄰接數(shù)據(jù)塊時就不會發(fā)生緩存失效了.定義3連續(xù)局部性(ContinuousLocality).時間局部性和空間局部性都是指運行程序在極短時間段內(nèi)的數(shù)據(jù)訪問局部性特征,因此,又稱它們?yōu)檫B續(xù)局部性.定義4非連續(xù)局部性(DiscontinuousLocality).指程序在運行時,由于函數(shù)被重復(fù)調(diào)用,存在被重復(fù)訪問的數(shù)據(jù)訪問序列.如果在該數(shù)據(jù)訪問序列被重復(fù)訪問之前,利用數(shù)據(jù)預(yù)取技術(shù)把該數(shù)據(jù)訪問序列要訪問的數(shù)據(jù)提前取到Cache中,這樣在該數(shù)據(jù)訪問序列被重復(fù)訪問時就不會發(fā)生緩存失效了.圖1中顯示的數(shù)據(jù)訪問局部性特征示例說明了時間局部性、空間局部性和非連續(xù)局部性的區(qū)別.圖1中,An表示的是訪存地址,左邊的地址序列Seq1={A1,A2,A7,A5,A3,A1,A2,A4,A6,A8}是程序運行過程中某一時間段的順序訪存流,右邊的地址序列{A1,A2,A3,A4},{A5,A6}和{A7,A8}是該時間段內(nèi)訪問數(shù)據(jù)的幾個連續(xù)存儲空間.根據(jù)定義1,A1,A2是很短時間內(nèi)被重復(fù)訪問的數(shù)據(jù)地址,如果第一次訪問A1,A2時發(fā)生了Cache失效,需要從內(nèi)存中讀取A1,A2的數(shù)據(jù),則當(dāng)下一次訪問A1,A2的數(shù)據(jù)時,就可以直接從Cache而不需訪問內(nèi)存了.因此,程序?qū)?shù)據(jù)地址A1,A2的訪問具有時間局部性特征.同樣地,根據(jù)定義2,{A1,A2,A3,A4},{A5,A6}和{A7,A8}在內(nèi)存中屬于鄰接的數(shù)據(jù)塊,如果在訪問其中一個數(shù)據(jù)塊時(如A7)發(fā)生了Cache失效,需要從內(nèi)存中讀取數(shù)據(jù)(如A7),則當(dāng)不久訪問鄰接數(shù)據(jù)塊(如A8)時就不會發(fā)生緩存失效了.因此,程序?qū)Φ刂沸蛄衶A1,A2,A3,A4},{A5,A6}和{A7,A8}的訪問具有空間局部性特征.最后,假如數(shù)據(jù)訪問地址序列Seq1在程序運行過程中多次重復(fù)出現(xiàn),當(dāng)?shù)谝淮卧L問Seq1時暫時把這個序列保存起來,則第二次訪問Seq1時,利用數(shù)據(jù)預(yù)取技術(shù)提前把Seq1中的數(shù)據(jù)取回到Cache中,這樣就避免了第二次訪問Seq1的Cache失效.因此,程序?qū)Φ刂沸蛄蠸eq1的訪問具有非連續(xù)局部性特征.3差別化預(yù)取對象的選擇基于訪存流模型的數(shù)據(jù)預(yù)取技術(shù)是隱藏非規(guī)則數(shù)據(jù)訪存延遲的有效措施.然而,已有的基于訪存流模型的數(shù)據(jù)預(yù)取技術(shù)不是忽略了訪存流中的時間順序,就是忽略了各訪存指令訪存行為間的差別,造成由過早預(yù)取行為引起的緩存污染或由過晚預(yù)取行為引起的無效預(yù)取.因此,建立能反映時間順序和行為差別的訪存流模型對數(shù)據(jù)預(yù)取的有效性來說至關(guān)重要.為了保證差別預(yù)取策略的有效性,節(jié)約系統(tǒng)資源,本文選擇位于程序關(guān)鍵執(zhí)行路徑上的,且其頻繁緩存失效行為嚴(yán)重影響程序性能的熱點循環(huán)作為差別預(yù)取對象.為了選擇合適的差別預(yù)取對象,本文在應(yīng)用差別預(yù)取策略前先使用動態(tài)剖析工具分析測試程序,并在頻繁發(fā)生緩存失效行為的熱點循環(huán)入口處做標(biāo)記,當(dāng)程序運行到標(biāo)記處時啟動差別預(yù)取策略.3.1訪存指令的預(yù)取和預(yù)取本文采用與文獻(xiàn)中類似的索引表IndexTable和全局歷史表GlobalHistoryBuffer存儲程序運行過程中熱點循環(huán)的數(shù)據(jù)訪問信息,如圖2所示.其中,An,Bn,Cn和Dn分別表示與四條訪存指令PC_A,PC_B,PC_C和PC_D對應(yīng)的訪存信息.由于程序熱點循環(huán)中訪存指令的執(zhí)行順序相似,如PC_A,PC_B,PC_C和PC_A,PC_B,PC_D,因此,與文獻(xiàn)中的IndexTable不同,本文的IndexTable表中直接按熱點循環(huán)中訪存指令的執(zhí)行順序保存各指令的訪存流信息,而無須額外的字段保存訪存指令的執(zhí)行順序.另外,為了根據(jù)其訪存行為特性區(qū)別對待各訪存指令的預(yù)取操作,本文在文獻(xiàn)中的GlobalHistoryBuffer基礎(chǔ)上又增加了一個NextInterval字段,用來保存各訪存指令相鄰兩次訪存之間的距離.例如,PC_A指令在訪問完A1后,要間隔B1,C1,D1這3個訪存操作后才再次訪問A2;PC_D指令在訪問完D3后,要間隔A1,B1,C1,這3個訪存操作后才再次訪問D1(這里假設(shè)GlobalHistoryBuffer中保存的是某單次熱點循環(huán)的數(shù)據(jù)訪問信息,且下次循環(huán)的指令執(zhí)行順序相同),因此,A1和D3相對應(yīng)的NextInterval字段的值都是3.IndexTable表和GlobalHistoryBuffer表的更新機(jī)制如下:①當(dāng)程序執(zhí)行到熱點循環(huán)入口處時,初始化IndexTable表和GlobalHistoryBuffer表,即按執(zhí)行順序把第一次熱點循環(huán)的訪存指令保存到IndexTable表中,按數(shù)據(jù)訪問順序把相應(yīng)的數(shù)據(jù)地址保存到GlobalHistoryBuffer表中,并依次更新NextInterval字段的值.②當(dāng)單次熱點循環(huán)的訪存指令順序沒有發(fā)生改變時,只需更新GlobalHistoryBuffer表中的地址信息.③當(dāng)單次熱點循環(huán)的訪存指令順序改變但沒有增加新的訪存指令時,更新GlobalHistoryBuffer表中的地址信息和NextInterval字段值,并修改IndexTable表中相應(yīng)指針的值.④當(dāng)單次熱點循環(huán)的訪存指令順序改變且增加新的訪存指令時,重新初始化IndexTable表和GlobalHistoryBuffer表.3.2基于les的訪存指令差別預(yù)取操作的執(zhí)行過程如下:(1)根據(jù)當(dāng)前訪存指令索引IndexTable表,找到下一條訪存指令和該指令的上一個訪存地址;(2)根據(jù)GlobalHistoryBuffer表追溯下一條訪存指令的訪存地址信息,確定該訪存指令的預(yù)取度,并按NextInterval字段值確定預(yù)取間隔;(3)把下一條訪存指令作為當(dāng)前指令,重復(fù)步驟(1)和(2),直至到達(dá)IndexTable表末尾.例如在圖2中,當(dāng)前訪存指令是PC_D,當(dāng)前訪存地址是D3,則首先索引IndexTable表找到下一條訪存指令是PC_A和它的上一個訪存地址A3;接著,根據(jù)GlobalHistoryBuffer表追溯PC_A的訪存地址信息A1-A2-A3,確定PC_A的預(yù)取度為3,并按NextInterval字段值確定A1-A2-A3之間的預(yù)取間隔分別為3和1;然后,按同樣的方式處理PC_B和PC_C,確定PC_B和PC_C的預(yù)取度為1,不需考慮預(yù)取間隔,但因為上一條指令PC_A中A1-A2的預(yù)取間隔為3,所以PC_A,PC_B和PC_C處理后預(yù)取操作序列為{A1,B1,C2,A2,A3},且C2-A2與A2-A3之間分別還可插入一個預(yù)取操作;最后,同樣道理處理PC_D,得到最后的預(yù)取操作序列為{A1,B1,C2,D1,A2,D2,A3}.這里A1,A2,B1,B2,D1,D2的值泛指各訪存指令在單次熱點循環(huán)中不同的訪存信息,具體值可根據(jù)情況確定,如使用步長、關(guān)聯(lián)信息等計算得到的訪存地址.從差別預(yù)取操作的執(zhí)行過程可以看出,差別預(yù)取策略不僅可以根據(jù)非規(guī)則計算的特性,把非連續(xù)局部性轉(zhuǎn)換為連續(xù)局部性來提高緩存命中率,而且還根據(jù)各訪存指令相鄰兩次訪存之間的距離調(diào)整預(yù)取度,達(dá)到及時預(yù)取和消除無用預(yù)取的目的.4差別預(yù)取實驗結(jié)果為了本文提出的差別預(yù)取策略的有效性,我們對測試程序的熱點循環(huán)模擬實現(xiàn)了差別預(yù)取策略和文獻(xiàn)提出的StreamChaining預(yù)取策略.實驗中差別預(yù)取策略GlobalHistoryBuffer表中的地址信息為關(guān)聯(lián)地址信息.StreamChaining預(yù)取策略中Ctr字段的閾值設(shè)置為3(即相鄰訪存指令重復(fù)出現(xiàn)超過3次時,認(rèn)為這兩個指令是一對強(qiáng)連接,并把此強(qiáng)連接加入到MissGraph中),預(yù)取度設(shè)為2.本文實驗采用的是SimpleScalar3.0模擬器,模擬器的配置如表1所示.IndexTable表的大小是2KB,在差別預(yù)取策略中可以存儲256條記錄,在StreamChaining預(yù)取策略中可以存儲128條記錄;GlobalHistoryBuffer表的大小是8kB,在差別預(yù)取策略中可以存儲256條記錄,在StreamChaining預(yù)取策略中可以存儲512條記錄.本文根據(jù)在線剖析工具對Olden基準(zhǔn)測試程序的分析結(jié)果,從中選擇熱點循環(huán)所消耗的CPU時鐘周期數(shù)占總時鐘周期數(shù)20%以上的5個非規(guī)則數(shù)據(jù)密集應(yīng)用程序作為測試程序.這5個程序分別是:em3d,mst,tsp,gcc和health.本文中所有的應(yīng)用程序都使用GCC4.1編譯器進(jìn)行編譯,編譯選項為“-O2”.實驗結(jié)果如圖3和圖4所示.圖3中顯示了相對于源程序,應(yīng)用差別預(yù)取和StreamChaining預(yù)取后測試程序L2Cache失效次數(shù)的規(guī)范化數(shù)值.從圖3中可以看出,差別預(yù)取消除了各測試程序熱點循環(huán)中80%以上的L2Cache失效行為,而StreamChaining預(yù)取消除了各測試程序熱點循環(huán)中70%以上的L2Cache失效行為.除TSP和GCC外,其它程序在應(yīng)用差別預(yù)取后的L2Cache失效次數(shù)都比在應(yīng)用StreamChaining預(yù)取后時少.例如,MST在應(yīng)用差別預(yù)取后,其L2Cache失效次數(shù)減少了約82.2%,而在應(yīng)用StreamChaining預(yù)取后,只減少了約79.7%.這主要是由兩個原因造成的.首先,差別預(yù)取策略根據(jù)訪存指令的行為差別采取不同預(yù)取度,減少了無用預(yù)取,提高了預(yù)取及時性和緩存命中率.其次,差別預(yù)取根據(jù)訪存指令相鄰兩次訪存之間的距離確定預(yù)取間隔,避免了過早預(yù)取引起的無用預(yù)取和緩存污染,進(jìn)一步提高了緩存命中率.圖4中顯示了相對于源程序,應(yīng)用差別預(yù)取和StreamChaining預(yù)取后測試程序的CPI規(guī)范化數(shù)值.從圖4中可以看出,在應(yīng)用差別預(yù)取和StreamChaining預(yù)取后,測試程序的CPI都有所降低,差別預(yù)取比StreamChaining預(yù)取取得了更加明顯的效果.尤其對于源熱點循環(huán)所消耗的CPU時鐘周期數(shù)占總時鐘周期數(shù)70%以上的MST,TSP和HEALTH這3個測試程序來說,應(yīng)用StreamChaining預(yù)取后,其CPI降低了25%以上;而應(yīng)用差別預(yù)取后,其CPI