0 引言

    隨著處理部件和存儲(chǔ)部件的性能的持續(xù)拉大，高速緩存作為標(biāo)準(zhǔn)配置已廣泛應(yīng)用于各種處理器設(shè)計(jì)的存儲(chǔ)層次中。設(shè)計(jì)者希望通過將經(jīng)常用到的數(shù)據(jù)保存在高速緩存中，降低內(nèi)存時(shí)延對(duì)處理器執(zhí)行性能的影響，從而實(shí)現(xiàn)較高的性能價(jià)格比。因此，緩存的命中率對(duì)處理器的整體性能有至關(guān)重要的影響。

    預(yù)取技術(shù)是一種提高緩存命中率的有效方法。通過動(dòng)態(tài)分析程序行為，對(duì)將來可能的數(shù)據(jù)訪問模式進(jìn)行預(yù)測并將可能訪問的數(shù)據(jù)提前讀取到高速緩存中。在處理器需要訪問對(duì)應(yīng)數(shù)據(jù)時(shí)，可以直接在高速緩存中獲得所需的數(shù)據(jù)，從而避免處理器直接訪問高延遲內(nèi)存造成的高延時(shí)。為了達(dá)到好的預(yù)取效果，就需要預(yù)取技術(shù)能精確預(yù)測可能的數(shù)據(jù)訪問，提高預(yù)取的準(zhǔn)確性，避免內(nèi)存帶寬及緩存容量等稀缺資源的浪費(fèi)。

    本文綜合評(píng)述了影響預(yù)取準(zhǔn)確性的關(guān)鍵因素，當(dāng)前主流的預(yù)取技術(shù)以及各種預(yù)取技術(shù)的優(yōu)缺點(diǎn)。并分析了當(dāng)前多核平臺(tái)和眾核平臺(tái)對(duì)預(yù)取技術(shù)的影響。在此基礎(chǔ)上，對(duì)預(yù)取技術(shù)的發(fā)展方向進(jìn)行了展望。

1 預(yù)取技術(shù)

    處理器平臺(tái)運(yùn)行著大量的應(yīng)用，由于這些應(yīng)用的訪存行為各異，也衍生出了大量不同的預(yù)取策略來提高應(yīng)用性能。在預(yù)取的相關(guān)研究中，主要關(guān)注的是如何針對(duì)相關(guān)應(yīng)用制定與實(shí)現(xiàn)高效的預(yù)取策略，其核心是圍繞利用程序執(zhí)行過程中存在的空間局部性與時(shí)間局部性，提升性能。近年來多核平臺(tái)的普及也為預(yù)取技術(shù)的發(fā)展提供了新的機(jī)遇與挑戰(zhàn)。多核平臺(tái)存在許多額外硬件資源，可以為程序的預(yù)取提供便利，從而加速程序的執(zhí)行效率。本節(jié)分別對(duì)基于利用空間局部性的預(yù)取、基于時(shí)間局部性的預(yù)取和多核平臺(tái)的幫助線程相關(guān)研究進(jìn)行分析。

1.1 基于空間局部性的預(yù)取

    空間局部性指的是由于程序的順序執(zhí)行或數(shù)組的順序訪問，程序即將用到的信息可能與目前正在使用的信息物理地址相鄰或鄰近。可以利用這一點(diǎn)來為預(yù)取提供理論依據(jù)從而提高程序執(zhí)行效率，減少內(nèi)存訪問延遲。但繁多的應(yīng)用程序存在著不一樣的程序邏輯，發(fā)掘各類應(yīng)用的空間局部性需要在策略的復(fù)雜度和預(yù)取效率之間進(jìn)行平衡。

    程序每次順序地訪問相鄰物理地址塊是程序空間局部性最直接最簡單的一種形式，Next-Line預(yù)取^[1]正是基于這種想法提出的，即每次預(yù)取當(dāng)前訪問地址塊之后的塊來提升程序性能。其優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，但由于這種情況只能涵蓋一小部分程序邏輯，導(dǎo)致無效預(yù)取指令過多，進(jìn)而影響預(yù)取效率。為了可以處理更為復(fù)雜的程序行為，可以在Next-Line預(yù)取的基礎(chǔ)上添加不同跳轉(zhuǎn)長度的預(yù)取支持^[2]及跳轉(zhuǎn)長度預(yù)測機(jī)制^[3]，為處理更為復(fù)雜的情況提高預(yù)取效率。

    為了進(jìn)一步發(fā)掘程序中的空間局部性關(guān)系來制定預(yù)取策略，可以對(duì)程序的執(zhí)行情況做更為復(fù)雜的分析。一種比較有效的方法是引入統(tǒng)計(jì)的方法對(duì)內(nèi)存訪問流進(jìn)行分析，從而提高預(yù)取的準(zhǔn)確性。如通過統(tǒng)計(jì)最近的內(nèi)存訪問流生成訪問直方圖^[4]。當(dāng)出現(xiàn)對(duì)某一已記錄地址進(jìn)行訪問時(shí)查詢直方圖，從而決定預(yù)取多少條連續(xù)指令?？臻g局部性偵測表^[5]及其變種對(duì)程序局部性行為進(jìn)行分析，通過調(diào)整各個(gè)代碼塊的大小提升代碼執(zhí)行過程中的空間局部性。然而，這類方法需要維護(hù)較大的表來記錄并探尋空間局部性。分析發(fā)現(xiàn)，在商用負(fù)載中通常存在重復(fù)出現(xiàn)的較長的內(nèi)存訪問序列^[6]。為了進(jìn)一步降低預(yù)取預(yù)測所需的存儲(chǔ)空間，可以建立這些序列程序計(jì)數(shù)器與訪問地址的關(guān)聯(lián)，通過只維護(hù)關(guān)聯(lián)關(guān)系，可以在維護(hù)一個(gè)較小的表的情況下，對(duì)眾多商用應(yīng)用上取得良好的預(yù)取效果。

1.2 基于時(shí)間局部性的預(yù)取

    時(shí)間局部性是指訪問過的某些數(shù)據(jù)在不久的將來還會(huì)被訪問到?；跁r(shí)間局部性的預(yù)取主要是通過分析程序的訪問模式，發(fā)現(xiàn)一條或數(shù)條重復(fù)發(fā)生的訪問鏈（即一系列地址按照相同的訪問順序重復(fù)出現(xiàn)）進(jìn)行預(yù)取。當(dāng)該鏈被判斷再次發(fā)生時(shí)，根據(jù)記錄的序列推測下一個(gè)訪問地址。最簡單的時(shí)間局部性預(yù)取策略是基于Markov模型的預(yù)取策略^[7]。該策略通過利用一個(gè)表來記錄給定地址的下一個(gè)潛在訪問對(duì)象來實(shí)現(xiàn)Markov預(yù)取器。

    然而，由于相關(guān)性流的長度可能達(dá)到上百個(gè)，為了利用時(shí)間局部性，可能需要非常大的額外存儲(chǔ)空間來存儲(chǔ)相關(guān)流。因此，如何對(duì)存儲(chǔ)空間進(jìn)行優(yōu)化是基于時(shí)間局部性預(yù)取策略需要解決的重要問題。由于現(xiàn)有高速緩存中命中率（hit rate）遠(yuǎn)遠(yuǎn)高于缺失率（miss rate），因此一種有效優(yōu)化策略是通過記錄緩存缺失的地址來代替記錄整個(gè)訪存行為降低所需的存儲(chǔ)空間^[8]。除了利用地址相關(guān)性，還可以利用地址變化相關(guān)性（delta correlation）來優(yōu)化存儲(chǔ)空間。即通過記錄兩次訪存之間的地址偏移量來訓(xùn)練預(yù)取策略。雖然這種策略會(huì)明顯減少所需存儲(chǔ)空間，但對(duì)于無規(guī)律的訪問，也會(huì)導(dǎo)致覆蓋率和精度的降低。很多情況下反復(fù)出現(xiàn)的指令流是由諸如循環(huán)迭代之類反復(fù)出現(xiàn)的代碼塊產(chǎn)生的^[9]。通過獲取整個(gè)循環(huán)結(jié)構(gòu)的工作集可以在保證精度的情況下精簡預(yù)取所需的額外開銷。通過對(duì)執(zhí)行頻度高的循環(huán)進(jìn)行注釋，預(yù)取器可以追蹤和預(yù)測整個(gè)迭代循環(huán)的工作集，從而在保證精度的情況下降低預(yù)取所需的存儲(chǔ)開銷。

    為了進(jìn)一步減少片上硬件開銷，也可以將預(yù)測信息存儲(chǔ)在片外^[10]，片上只存儲(chǔ)對(duì)片外存儲(chǔ)信息哈希建立的索引，以減少查詢及訪問延遲并利用“概率更新”機(jī)制來減少片外信息的更新頻率，從而可以降低較長的流造成的存儲(chǔ)開銷。

1.3 幫助線程

    近年來，由于能耗墻和存儲(chǔ)墻問題的突出，多核處理器已逐漸代替單核處理器成為主流硬件平臺(tái)。其豐富的并行資源為提高應(yīng)用性能提供了廣闊的前景。并行資源的豐富也為進(jìn)一步提升預(yù)取效率提供了空間。

    基于多核的預(yù)取策略優(yōu)化主要是基于額外硬件資源生成幫助線程來提高預(yù)取效率。其核心思想是基于主線程的執(zhí)行流生成精簡版本作為預(yù)取幫助線程^[11]。主線程與預(yù)取幫助線程同時(shí)執(zhí)行，由于預(yù)取線程執(zhí)行的程序片段為主線程的精簡版本，通常執(zhí)行速度會(huì)快于主線程。因此可以將其執(zhí)行讀取數(shù)據(jù)的結(jié)果通過共享緩存反饋給主線程從而達(dá)到為主線程預(yù)取數(shù)據(jù)，加速主線程執(zhí)行速度的效果。

    另一種幫助線程預(yù)取的策略是通過核間線程遷移基礎(chǔ)上的幫助線程預(yù)取策略^[12]。之前的幫助線程主要是通過共享的緩存來為主線程的預(yù)取提供幫助，而由于共享緩存的速度較慢，無法達(dá)到較好的性能。為了進(jìn)一步提高幫助線程的效果，可以通過核間線程遷移的方式利用高速的私有緩存實(shí)現(xiàn)高效的預(yù)取。在這種策略下，幫助線程仍然為主線程執(zhí)行片段的精簡版本。每個(gè)核運(yùn)行一個(gè)線程，同時(shí)運(yùn)行的線程包括一個(gè)主線程和數(shù)個(gè)幫助線程。當(dāng)運(yùn)行完一段指令后，對(duì)主線程進(jìn)行遷移，即原本運(yùn)行主線程的核開始運(yùn)行幫助線程，而之前運(yùn)行幫助線程的核由于已經(jīng)完成了預(yù)取，主線程將遷移到這個(gè)核上，從而利用存儲(chǔ)在該核私有緩存中的預(yù)取信息而不是共享緩存，提高了效率。

2 面向圖形處理器（GPGPU）的預(yù)取技術(shù)

    圖形處理器由于其強(qiáng)大的計(jì)算能力和對(duì)通用計(jì)算支持的逐步加強(qiáng)，目前越來越多地應(yīng)用于通用計(jì)算領(lǐng)域。因此如何提高其片上存儲(chǔ)部件的效率對(duì)其執(zhí)行性能將產(chǎn)生至關(guān)重要的影響。與通用處理器（CPU）不同，由于GPGPU上各個(gè)硬件核心運(yùn)行的線程訪存模式較為接近，面向GPGPU的預(yù)取策略主要集中在利用空間局部性。除了預(yù)取策略的制定外，還有部分研究是圍繞充分發(fā)掘GPGPU硬件資源來為預(yù)取提供額外支持而展開的，本節(jié)將分別對(duì)這兩部分進(jìn)行介紹。

2.1 GPGPU的預(yù)取策略制定

    GPGPU由于其高并行度的優(yōu)勢，越來越多的被應(yīng)用到通用計(jì)算領(lǐng)域。與通用處理器類似，GPGPU雖然擁有更為豐富的計(jì)算資源，但其性能也受到了內(nèi)存延遲的限制，而預(yù)取技術(shù)正是有效隱藏內(nèi)存延遲的手段之一。

    雖然GPGPU相關(guān)應(yīng)用都具有良好的空間局部性，但由于其自身硬件特點(diǎn)，為了取得性能提升并不能直接套用已有針對(duì)CPU的預(yù)取技術(shù)。高度并行化是GPGPU應(yīng)用與傳統(tǒng)的應(yīng)用的顯著差別之一。正是由于這個(gè)特點(diǎn)，GPGPU上每個(gè)線程的執(zhí)行時(shí)間通常較短，這也意味著線程中如果存在循環(huán)體的話，循環(huán)次數(shù)也非常少。這種情況下針對(duì)線程自身并沒有多少機(jī)會(huì)通過預(yù)取來提高性能。因而面向GPGPU的預(yù)取主要是進(jìn)行線程間的預(yù)取^[13]，即當(dāng)前執(zhí)行的線程組（warp）為下一時(shí)刻將要執(zhí)行的線程組中的線程進(jìn)行預(yù)取，減少了之后執(zhí)行線程的訪存延遲。在GPGPU上執(zhí)行的多個(gè)warp組間通常具有較好的訪存規(guī)律性，若3個(gè)或3個(gè)以上warp中對(duì)應(yīng)線程的訪存偏移量一致，則認(rèn)為偏移量可以應(yīng)用至整體線程組。對(duì)于這種情況，可以針對(duì)每個(gè)warp維護(hù)一個(gè)訪存偏移表，從而為預(yù)取提供依據(jù)。

    然而，在GPGPU線程的實(shí)際執(zhí)行中，會(huì)對(duì)時(shí)間上連續(xù)的warp進(jìn)行調(diào)度。因而如果簡單實(shí)現(xiàn)連續(xù)warp間的預(yù)取會(huì)出現(xiàn)預(yù)取延遲，造成預(yù)取失效。為了克服這種預(yù)取延遲的問題，在GPGPU的warp分配過程中，需要對(duì)訪存連續(xù)的warp的執(zhí)行順序進(jìn)行調(diào)整^[14]，拉大訪存連續(xù)warp的間隔，避免出現(xiàn)正在運(yùn)行的warp和其幫助預(yù)取的warp連續(xù)執(zhí)行的情況，從而使得預(yù)取能及時(shí)生效。

2.2 利用硬件資源的預(yù)取策略

    由于GPGPU中預(yù)取策略的制定比較單一，因此有部分研究的重點(diǎn)轉(zhuǎn)移到了預(yù)取數(shù)據(jù)的存放問題。在GPGPU中，預(yù)取的數(shù)據(jù)通常存放在共享內(nèi)存中。當(dāng)出現(xiàn)內(nèi)存替換時(shí)，可能會(huì)使預(yù)取數(shù)據(jù)被替換出去從而導(dǎo)致預(yù)取失效。而在GPGPU執(zhí)行過程中，通常有大量寄存器長時(shí)間閑置^[15]。為了避免預(yù)取數(shù)據(jù)的替換，可以利用空閑的寄存器來存儲(chǔ)預(yù)取數(shù)據(jù)。通過監(jiān)視寄存器的工作狀態(tài)來確定哪些寄存器適合用來存放預(yù)取數(shù)據(jù)，從而避免預(yù)取數(shù)據(jù)被替換出去，提升預(yù)取效果。

    由于GPGPU中豐富的硬件資源，在GPGPU程序運(yùn)行過程中，不可避免地也會(huì)出現(xiàn)硬件流處理器閑置的情況。因此，可以利用這些閑置的流處理器資源來為預(yù)取提供支持。ISP（Idle Stream Multiprocessors）預(yù)取策略就是基于這種設(shè)想提出的^[16]，通過利用停滯的流處理器來為正在工作的warp預(yù)取數(shù)據(jù)，從而提高程序的執(zhí)行效率。

3 預(yù)取技術(shù)分析和展望

    通用處理器與圖形處理器由于其硬件特性以及其上運(yùn)行的程序特性決定了兩者預(yù)取技術(shù)的相關(guān)研究側(cè)重點(diǎn)不同：CPU由于其上運(yùn)行的程序種類多、程序邏輯復(fù)雜，簡單的預(yù)取策略并不能同時(shí)滿足所有的程序需求。因此相關(guān)研究更多的側(cè)重于設(shè)計(jì)合理的預(yù)取策略，提升預(yù)取策略的覆蓋面。為了充分發(fā)揮GPGPU性能，通常其上運(yùn)行的程序已經(jīng)具有良好的空間局部性，這也就決定了其預(yù)取策略主要圍繞的是空間局部性制定的，主要關(guān)注的是如何高效地實(shí)現(xiàn)這一機(jī)制。

    表1是對(duì)CPU及GPGPU平臺(tái)制定預(yù)取策略的依據(jù)和具體實(shí)現(xiàn)方式的總結(jié)。

    雖然針對(duì)CPU預(yù)取的相關(guān)研究已經(jīng)取得了很好的效果，但仍然面臨著許多挑戰(zhàn)。由于運(yùn)行程序的多樣性，大量應(yīng)用的訪存行為不一致，單一的預(yù)取策略并不能同時(shí)很好地滿足各種應(yīng)用的需求。較為復(fù)雜的策略雖然能保證精度，但會(huì)引入較高的額外開銷。而簡單的預(yù)取策略在訪問不規(guī)律下精度過低，導(dǎo)致效率不足。因此，需要研究自適應(yīng)的預(yù)取策略，根據(jù)當(dāng)前運(yùn)行的程序狀態(tài)，動(dòng)態(tài)選擇合適的預(yù)取策略，從而進(jìn)一步提高程序性能。

    由于GPGPU應(yīng)用的訪存行為較為單一，現(xiàn)階段的主要研究內(nèi)容是如何更高效地實(shí)現(xiàn)預(yù)取，實(shí)現(xiàn)算法也比較簡單。然而，GPGPU的強(qiáng)大性能使得許多原本不熟悉GPGPU特點(diǎn)的編程人員加入了平臺(tái)應(yīng)用的開發(fā)過程中，從而可能會(huì)出現(xiàn)不友好的訪存行為，使得直接利用簡單預(yù)取策略并不能取得理想的效果。同時(shí)，GPGPU上對(duì)預(yù)取的硬件支持也不夠充分。因此，在未來的研究中，需要規(guī)范訪存行為，利用CPU資源來協(xié)同修正GPGPU應(yīng)用的訪存行為，從而使其更規(guī)律，預(yù)取更高效。同時(shí)在GPGPU體系結(jié)構(gòu)設(shè)計(jì)過程中，提供更多的預(yù)取硬件支持，提高預(yù)取效率。

4 結(jié)語

    隨著計(jì)算硬件的迅速發(fā)展，處理器處理速度與內(nèi)存訪問速度的差異越來越大，內(nèi)存訪問延遲成為限制處理器性能的主要問題。預(yù)取技術(shù)作為降低兩者速度差異的重要手段之一已得到廣泛的應(yīng)用。隨著硬件設(shè)計(jì)的并行化，多核乃至眾核硬件逐漸成為硬件平臺(tái)的主流。如何為并行硬件設(shè)計(jì)高效預(yù)取技術(shù)，目前還處于剛剛起步階段,也無法滿足并行環(huán)境提高訪存效率的需要。隨著技術(shù)的不斷進(jìn)步，相信未來針對(duì)并行硬件的預(yù)取技術(shù)將會(huì)逐步得到完善。

參考文獻(xiàn)

[1] SMITH A.Sequential program prefetching in memory hierarchies[J].IEEE Transactions on Computers，1978，11(12)：7-12.

[2] ISHII Y，INABA M，HIRAKI K.Access map pattern matching for high performance data cache prefetch[J].Journal of Instruction-Level Parallelism，2011，13：1-24.

[3] SAIR S，SHERWOOD T，CALDER B.A decoupled predictor-directed stream prefetching architecture[J].IEEE Transactions on Computers，2003，52(3)：260-276.

[4] HUR I，LIN C.Memory prefetching using adaptive stream detection[C].In Proceedings of the 39th International Symposium on Microarchitecture，2006：397-408.

[5] JOHNSON T L，MERTEN M C，HWU W M W.Run-time spatial locality detection and optimization[C].In Proceedings of the 30th Annual ACM/IEEE International Symposium on Microarchitecture，1997：57-64.

[6] SOMOGYI S，WENISCH T F，AILAMAKI A，et al.Spatial memory streaming[C].In ISCA′06：Proceedings of the 33rd Annual International Symposium on Computer Architecture，2006：252-263.

[7] JOSEPH D，GRUNWALD D.Prefetching using Markov predictors[C].In Proceedings of the 24th Annual International Symposium on Computer Architecture，1997：252-263.

[8] NESBIT K J，SMITH J E.Data cache prefetching using a global history buffer[J].IEEE Micro，2005，25(1)：90-97.

[9] FUCHS A，MANNOR S，WEISER U，et al.Loop-Aware memory prefetching using code block working sets[C].Microarchitecture(MICRO)，2014 47th Annual IEEE/ACM International Symposium on.IEEE，2014：533-544.

[10] WENISCH T F，F(xiàn)ERDMAN M，AILAMAKI A，et al.Practical off-chip meta-data for temporal memory streaming[C].In HPCA，2009：79-90.

[11] CHAPPELL R，STARK J，KIM S，et al.Simultaneous subordinate microthreading(ssmt)[C].In Proceedings of the International Symposium on Computer Architecture，May 1999.

[12] JAIN A，LIN C.Linearizing irregular memory accesses for improved correlated prefetching[C].Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture，2013：247-259.

[13] LEE J，LAKSHMINARAYANA N B，KIM H，et al.Manythread aware prefetching mechanisms for GPGPU applications[C].Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture，2010：213-224.

[14] JOG A，KAYIRAN O，MISHRA A K，et al.Orchestrated scheduling and prefetching for GPGPUs[C].Proceedings of the 40th Annual International Symposium on Computer Architecture，2013：332-343.

[15] LAKSHMINARAYANA N B，KIM H.Spare register aware prefetching for graph algorithms on GPUs[C].High Performance Computer Architecture(HPCA)，2014 IEEE 20th International Symposium on.IEEE，2014：614-625.

[16] FALAHATI H，HESSABI S，ABDI M，et al.Power-efficient prefetching on GPGPUs[J].The Journal of Supercomputing，2014：1-22.