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

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

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