0 引言

    隨著處理部件和存儲部件的性能的持續拉大，高速緩存作為標準配置已廣泛應用于各種處理器設計的存儲層次中。設計者希望通過將經常用到的數據保存在高速緩存中，降低內存時延對處理器執行性能的影響，從而實現較高的性能價格比。因此，緩存的命中率對處理器的整體性能有至關重要的影響。

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

    本文綜合評述了影響預取準確性的關鍵因素，當前主流的預取技術以及各種預取技術的優缺點。并分析了當前多核平臺和眾核平臺對預取技術的影響。在此基礎上，對預取技術的發展方向進行了展望。

1 預取技術

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

1.1 基于空間局部性的預取

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

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

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

1.2 基于時間局部性的預取

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

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

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

1.3 幫助線程

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

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

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

2 面向圖形處理器（GPGPU）的預取技術

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

2.1 GPGPU的預取策略制定

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

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

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

2.2 利用硬件資源的預取策略

    由于GPGPU中預取策略的制定比較單一，因此有部分研究的重點轉移到了預取數據的存放問題。在GPGPU中，預取的數據通常存放在共享內存中。當出現內存替換時，可能會使預取數據被替換出去從而導致預取失效。而在GPGPU執行過程中，通常有大量寄存器長時間閑置^[15]。為了避免預取數據的替換，可以利用空閑的寄存器來存儲預取數據。通過監視寄存器的工作狀態來確定哪些寄存器適合用來存放預取數據，從而避免預取數據被替換出去，提升預取效果。

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

3 預取技術分析和展望

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

    表1是對CPU及GPGPU平臺制定預取策略的依據和具體實現方式的總結。

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

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

4 結語

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

參考文獻

[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，FERDMAN 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.