梯度學習的參數控制幫助線程預取模型*

裴頌文，張俊格，寧 靜

(1.上海理工大學 光電信息與計算機工程學院， 上海 200093；2.上海理工大學 上海市現代光學系統重點實驗室， 上海 200093)

?

梯度學習的參數控制幫助線程預取模型*

裴頌文1,2，張俊格1，寧 靜1

(1.上海理工大學 光電信息與計算機工程學院， 上海 200093；2.上海理工大學 上海市現代光學系統重點實驗室， 上海 200093)

對于非規則訪存的應用程序，當某個應用程序的訪存開銷大于計算開銷時，傳統幫助線程的訪存開銷會高于主線程的計算開銷，從而導致幫助線程落后于主線程。于是提出一種改進的基于參數控制的幫助線程預取模型，該模型采用梯度下降算法對控制參數求解最優值，從而有效地控制幫助線程與主線程的訪存任務量，使幫助線程領先于主線程。實驗結果表明，基于參數選擇的線程預取模型能獲得1.1～1.5倍的系統性能加速比。

數據預取;幫助線程;多核系統;訪存延遲;梯度下降

在微處理器的發展進入多核時代[1-2]之后，處理器和存儲器之間的速度差距進一步拉大，存儲墻[3]問題仍然是制約微處理器性能提升的一個重要瓶頸。數據預取技術[4]是緩解存儲墻問題的重要手段之一，數據預取利用程序訪存和計算的重疊，在處理器訪問數據之前提前發出訪存請求，隱藏因Cache缺失而引起的訪存延遲。

傳統的數據預取可分為硬件預取[5]和軟件預取[6]兩種。硬件預取在預取引擎的控制下，根據訪存歷史，對程序訪存的模式進行識別和預測，通過硬件機制來預測可能發生的Cache失效，自動進行預取。但是，此種預取方式增加了硬件復雜性。軟件預取是指由程序員或編譯器在代碼中插入預取指令，提前將數據取入 Cache，從而避免在計算時由于數據缺失導致的執行暫停。

幫助線程預取技術[7]實質上是一種Leader/Follower結構，幫助線程是去除了原程序計算任務的“精簡版本”，它往往比主線程運行得快，因此幫助線程可提前于主線程發出訪存請求，從而加速程序執行速度。幫助線程僅僅起到預取的作用，不修改主線程的體系結構狀態，因此不會引起程序的錯誤執行。在理想的情況下，主線程需要某個數據的時候，幫助線程恰好能將需要的數據預取到末級緩存(Last-Level Cache，LLC)。但是，如果訪存開銷和計算開銷差別較大的時候，幫助線程并不能每次領先主線程，導致預取的數據不能及時到達，造成Cache污染。根據不同的程序中訪存開銷和計算開銷的規模，可將程序劃分為以下三種類別。設程序的訪存時間為Tm，計算時間為Tc。

1)計算開銷與訪存開銷大小相當，即Tm≈Tc。此時幫助線程能很好地發揮作用。

2)計算開銷大于訪存開銷，即Tc>Tm。此時要控制好幫助線程的預取時機，防止預取時機過早，從而導致真正使用的時候數據已被替換出去。

3)計算開銷小于訪存開銷，即Tc

對于非規則數據訪存的應用程序，其數據結構通常使用圖、樹或者鏈表等組成。此類應用程序的訪存行為呈現非規則性，訪存模式難以在靜態編譯階段進行準確的預測[8]。由于其可利用的局部性受到限制，使得傳統的軟件和硬件預取方法失效，其訪存模式只能通過執行代碼本身來進行預測。由于非規則訪存密集型程序往往帶來大量的訪存開銷，并且遠遠大于計算開銷，因此本文著重針對第三種類別，提出參數控制的幫助線程預取方法。幫助線程負責訪存任務，主線程負責計算任務。幫助線程提前將主線程所需的數據預取到LLC，從而達到隱藏訪存延遲的目的。

1 相關工作

幫助線程技術可以通過硬件與軟件的方法實現[9]。硬件方法通過指令窗口動態生成幫助線程，硬件復雜度較高。軟件方法是對程序的源代碼進行剖析，由編譯器顯式插入預取線程代碼，易于實現。

Kim等[10]利用Unravel切片工具和斯坦福大學SUIF編譯框架在源代碼級完成了幫助線程的自動構造。利用預取轉換(Prefetch Conversion,PC)操作來進行主線程和幫助線程之間的同步，通過設置主線程與幫助線程計數器的方式來控制幫助線程的執行速度。只有當兩個線程計數器之差大于一個特定的閾值PD(預取距離)時，幫助線程才繼續運行。Song等[11]在SUNSPARC平臺上基于編譯實現了幫助線程的構造方法，該方法通過判斷幫助線程的收益來進行構造。Ou等[12]提出的基于線程的預取方法，通過在處理器上添加動態預取線程構造邏輯和控制邏輯，對程序的訪存特點進行分析，并從主線程的執行行蹤中提取數據預取線程，使用空閑的線程和主線程并行執行。Yu等[13]提出了一種線程感知的自適應的數據預取方法，根據線程動態反饋信息將線程進行分類，從硬件層面控制線程的競爭，但是需要物理模塊的支持。

以上面向幫助線程預取的研究大多集中于主線程和幫助線程的構造與同步機制。但是，對于實際的應用程序，在計算開銷很小的情況下，幫助線程不一定總快于主線程，此時就會頻繁產生同步操作，導致程序性能下降。因此，如何能夠合理分配一定比例的訪存任務由主線程完成，使得幫助線程與主線程協同工作，從而有效提高系統訪存和計算性能，是本文研究的重點。

2 參數控制的預取模型

通過以上分析，幫助線程的訪存開銷分為兩種：①對于計算密集型的應用程序，幫助線程承擔全部的訪存任務；②對于訪存密集型的應用程序，幫助線程承擔部分的訪存任務。如果讓幫助線程取得較好的性能，必須根據程序不同的訪存開銷與計算開銷來調整幫助線程預取數據量的大小。幫助線程應從熱點程序入口處開始跳過K個數據塊之后才開始推送P個數據塊，從而提高幫助線程預取數據的有效性與及時性。在預取的時候，一方面要保證幫助線程能夠及時地預取主線程所需要的數據，另一方面要保證幫助線程不會落后或超前于主線程太長的距離，從而替換掉主線程所需的有用數據，造成多核平臺的最后一級緩存污染。

2.1 預取參數的定義

采用Zhang等[14]提出的KPB(skip-push-block)參數，在考慮原程序計算訪存工作量的前提下，通過動態調整K，P，B三個參數值，使得幫助線程的性能達到最優。將熱點模塊按照循環數分成等長的 Block，一次循環所需數據稱作一個數據塊。

1)K即skip，表示幫助線程跳過多少個數據塊，即主線程負責K個數據塊的訪存，其他的訪存任務由幫助線程來完成，此參數主要用于控制幫助線程預取的觸發時機。若程序的計算開銷遠遠大于仿存量，此時K=0，與傳統的幫助線程預取機制一樣，幫助線程承擔全部的訪存工作。

2)P即push，表示幫助線程給主線程推送多少個數據塊，即幫助線程預取的數據量。此參數用于控制幫助線程預取工作量的大小。

3)B即block，表示幫助線程與主線程多長時間同步一次。一般情況下B=K+P。此參數用于控制幫助線程與主線程的同步頻次，采用文獻[10]所述的線程同步機制。

目前參數的選取大多都是通過枚舉實驗來獲取，設RP=P/(K+P)，其中Rp為預取率，0

2.2 參數控制預取模型

基于梯度學習的參數控制預取模型主要由兩部分組成，即熱點分析和代價函數的構造。預取算法的基本流程如圖1所示。

圖1 參數控制的預取模型流程圖Fig.1 Flow chart of pre-fetching model based on control parameters

2.2.1 確定程序的熱點部分

主要面向的測試對象為非規則訪存應用程序，其數據結構一般是非線性的鏈式結構，相對規則訪存程序的訪存時間局部性和空間局部性較差。在運行過程中，非規則訪存程序產生訪問Cache缺失的概率比較高，對測試程序的總體執行性能影響較大。首先使用Intel性能分析工具Vtune[15]對此類程序進行離線Profiling，收集CPU的時鐘周期和共享Cache的缺失信息，然后找出引起Cache缺失的長延遲訪存指令，確定要進行預取的熱點循環部分。熱點循環要滿足以下兩個基本條件：

1)熱點循環中包含長延遲的間址訪存指令；

2.2.2 構造代價函數

通過Vtune工具，分析熱點程序的訪存任務量M(訪存所消耗的時間)與計算任務量C(計算所消耗的時間)的大小。為確保程序性能最優，將滿足的條件設為代價函數，記作J(θ)。根據預取模型，主線程負責的任務是：

1)K個數據塊的訪存與計算；

2)P個數據塊的計算。

可記作K(Tc+Tm)+PTc。其中：Tm為單次循環的訪存時間，Tc為單次循環的計算時間。

幫助線程負責的任務為：P個數據塊的預取，可記做PTm。

為了能更準確反映高等學校資產負債情況，《政府會計制度》在《高等學校會計制度》單一會計基礎“收付實現制”的基礎上，引入了“權責發生制”，要求高等學校采用“雙會計基礎”，即財務會計核算采用權責發生制，預算會計核算采用收付實現制。

理想情況下，幫助線程與主線程完全并行，此時程序性能達到最優，即

(1)

的絕對值最小。

假設給主線程分配的訪存任務為m0，根據經驗可知，隨著K的增加，m0也增加。K，m0的關系可設為:

K=θ0·m0

(2)

假設幫助線程分配的訪存任務為m1，同樣，根據經驗可知，隨著P的增加，m1也增加。P，m1關系可設為：

P=θ1·m1

(3)

將式(2)、式(3)代入式(1)得：

θ0·m0(Tc+Tm)+θ1·m1(Tc-Tm)

根據上述推斷，可知代價函數為:

(4)

2.2.3 計算最優的K，P

梯度學習作為一種求解最優參數的迭代算法，廣泛應用于機器學習各式model參數的求解中。梯度下降算法是一種迭代方法，利用負梯度方向來決定每次迭代的新的搜索方向，使得每次迭代能使待優化的目標函數逐步減小。因此，選擇梯度下降算法進行最優值的求解，通過選擇不同的m0，m1的樣本值，可以訓練出滿足代價函數J(θ)最小的θ0，θ1。

通過m0+m1=M，即

K/θ0+P/θ1=M

(5)

又有

K+P=B

(6)

2.2.4 構造幫助線程

利用Vtune確定熱點循環，然后構造有效的、輕量級的幫助線程。通過切片工具從熱點循環中提取不包含計算部分的代碼，編譯器根據profile文件信息將要預取的訪存指令標記為關鍵指令，將計算指令標記為非關鍵指令。最終，將關鍵指令抽取出來，形成幫助線程的代碼塊。幫助線程與主線程之間通過共享變量的方式進行同步和通信。幫助線程每跳過K個數據塊，預取P個數據塊后，就要和主線程同步一次。

3 實驗分析

實驗選取的測試程序為Olden Benchmark中用于科學計算的測試程序 EM3D、MST，SPEC CPU 2006中的MCF進行幫助線程預取性能的評估。處理器是 Intel?CoreTM2 Q6600 四核處理器，該處理器共有8 MB二級高速緩存，每對核共享4 MB二級高速緩存。通過Vtune的分析，選取的熱點模塊以及輸入集見表1，分別為EM3D中的Fill_from_field，MST中的Hashlookup，MCF中的Refresh_potential。

表1 Benchmark 參數配置表

如圖2所示，EM3D，MST和MCF測試程序采用傳統幫助線程(幫助線程負責全部的訪存任務)、參數枚舉法和基于梯度學習的參數控制方法(參數學習法)相對于串行執行(不使用幫助線程的源程序)時的性能加速比，其中參數學習法獲得了1.1～1.5倍的最高加速比。MST的Hashlookup模塊屬于訪存密集型程序，使用傳統的幫助線程方法與原串行程序相比加速比反而降低了4.8%；使用參數學習方法，性能提升了近50%。EM3D 的Fill_from_fields模塊屬于計算量較大的程序，使用參數學習方法與傳統幫助線程方法獲得的加速比相當，僅提高了4.9%。由于參數枚舉法取決于經驗與啟發式實驗，枚舉粒度的大小直接影響到結果的準確性。粒度過小，需要進行大量的重復試驗；粒度過大，可能錯過最優值。因此，參數枚舉法并不總能得到最優解。參數學習法不依賴于經驗，而是通過機器學習的方法獲取最優值，比參數枚舉法效率更高。

圖2 性能加速比Fig.2 Performance speedup

圖3給出了測試程序在使用傳統的幫助線程、參數枚舉法和參數學習法情況下各自Cache缺失率的歸一化相對值。其中，MST，EM3D，MCF的熱點程序的Cache缺失率相對于采用傳統幫助線程的情況下分別減少了12%，10%，27%。MST，EM3D相對于參數枚舉法分別減少了2.5%，1.7%。因此，通過機器學習的梯度下降算法取得K，P的最優值比參數枚舉法效率更高。

圖3 Cache缺失率Fig.3 Cache missing rate

預取的準確率等于幫助線程有效預取的次數與其發出的全部預取次數的比例。對比串行執行的Cache缺失率與采用參數學習的幫助線程預取技術后的Cache缺失率，評估預取的準確率與覆蓋率。如圖4所示，相對于原串行執行的方法，基于參數學習的幫助線程預取算法對數據預取的效果是明顯的，降低了數據Cache的缺失率。

圖4 Cache缺失率對比Fig.4 Comparison of Cache missing rate

由于活動計算核數量的增加以及對資源的競爭，采用幫助線程的程序執行相比于串行程序執行，將會在一定程度上增加功耗。如果幫助線程的收益大于額外增加的功耗，則體現了幫助線程的有效性。幫助線程額外增加的功耗表示相對于串行程序執行功耗[16]的比例。幫助線程收益表示相對于串行程序執行時間所減少的比例。如圖5所示，幫助線程的平均收益大于平均功耗。其中，MST、MCF的收益均大于功耗，因此幫助線程能有效提升MST、MCF的執行性能。因為EM3D 屬于計算量較大的程序，訪存量較小，幫助線程反而帶來了很大的同步開銷，不足以彌補幫助線程帶來的收益，所以，幫助線程對提高EM3D執行性能有限。

圖5 幫助線程功耗和收益比Fig.5 Comparison between energy overhead ratio and performance gain of helper thread

4 結論

通過分析傳統的幫助線程不能有效地控制預取實時性和覆蓋率缺陷，以及對訪存密集型的程序預取效率低的劣勢，提出了一種基于梯度學習的參數控制幫助線程預取模型。通過采用機器學習的梯度下降算法確定K，P的值，根據K，P的值選擇性地預取部分數據，使得幫助線程與主線程的工作量相對均衡，從而使程序的執行性能達到最優。

由于幫助線程與主線程同時訪存，可能會引起帶寬的競爭。因此，下一步的工作將考慮幫助線程對帶寬的影響，具體分析程序的訪存地址，適當增加預取步長，將預取相鄰地址的預取指令進行合并，以減少預取次數，從而可以降低帶寬的競爭，提高執行性能，降低額外功耗。

References)

[1] Pei S W， Kim M S， Gaudiot J L. Extending amdahl′s law for heterogeneous multicore processor with consideration of the overhead of data preparation[J]. IEEE Embedded Systems Letters， 2016， 8(1): 26-29.

[2] 裴頌文， 吳小東， 唐作其, 等. 異構千核處理器系統的統一內存地址空間訪問方法[J]. 國防科技大學學報， 2015(1): 28-33.

PEI Songwen， WU Xiaodong, TANG Zuoqi, et al. An approach to accessing unified memory address space of heterogeneous kilo-cores system[J]. Journal of National University of Defense Technology, 2015(1): 28-33. (in Chinese)

[3] Wilkes M V. The memory wall and the CMOS end-point[J]. ACM Sigarch Computer Architecture News, 1995， 23(4): 4-6. [4] Vanderwiel S P， Lilja D J. Data prefetch mechanisms[J]. ACM Computing Surveys， 2000， 32(2): 174-199.

[5] Ganusov I，Burtscher M. Future execution: a hardware prefetching technique for chip multiprocessors[C]//Proceedings of Parallel Architectures and Compilation Techniques Conference， 2005: 350-360.

[6] Dudás ， Juhász S， Schrádi T. Software controlled adaptive pre-execution for data prefetching[J]. International Journal of Parallel Programming， 2012， 40(4): 381-396.

[7] Lee J， Jung C， Lim D， et al. Prefetching with helper threads for loosely coupled multiprocessor systems[J]. IEEE Transactions on Parallel & Distributed Systems，2009， 20(9): 1309-1324.

[8] Huang Y，Tang J，Gu Z M，et al. The performance optimization of threaded prefetching for linked data structures[J]. International Journal of Parallel Programming， 2011， 40(2): 141-163.

[9] 張建勛, 古志民.幫助線程預取技術研究綜述[J]. 計算機科學， 2013， 40(7): 19-23.

ZHANG Jianxun, GU Zhimin.Survey of helper thread prefetching[J]. Computer Science， 2013， 40(7): 19-23.(in Chinese)

[10] Kim D， Yeung D. A study of source-level compiler algorithms for automatic construction of pre-execution code[J]. ACM Transactions on Computer Systems， 2004， 22(3): 326-379.[11] Song Y, Kalogeropulos S, Tirumalai P.Design and implementation of a compiler framework for helper threading on multi-core processors[C]//Proceedings of the International Conference on Parallel Architectures and Compilation Techniques， 2005: 99-109 .

[12] Ou G D， Zhang M X. Thread-based data prefetching[J]. Computer Engineering & Science， 2008， 30(1): 119-122.

[13] Yu J Y， Liu P. A thread-aware adaptive data prefetcher[C]//Proceedings of Computer Design， Seoul， 2014: 278-285.[14] Zhang J X， Gu Z M， Huang Y， et al. Helper thread prefetching control framework on chip multi-processor[J]. International Journal of Parallel Programming， 2013， 43(2): 180-202.

[15] Intel VTune performance analyzer for linux [EB/OL]. [2012-12-10]. http://www.intel.com/ support/performacetools/vtune/linux.[16] Singh K， Bhadauria M， Mckee S A. Prediction-based power estimation and scheduling for CMPs[C]//Proceedings of International Conference on Supercomputing，2009: 501-502.

Helper thread pre-fetching model based on learning gradients of control parameters

PEI Songwen1,2, ZHANG Junge1, NING Jing1

(1. School of Optical Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China;2. Shanghai Key Laboratory of Modern Optical System, University of Shanghai for Science and Technology, Shanghai 200093, China)

(1. School of Optical Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China;2. Shanghai Key Laboratory of Modern Optical System, University of Shanghai for Science and Technology, Shanghai 200093, China)

To the applications with irregular accessing memory, if the overhead of accessing memory for a given application is much greater than that of computation, it will make the helper thread lag behind the main thread. Hereby, an improved helper thread pre-fetching model by adding control parameters was proposed. The gradient descent algorithm is one of the most popular machine learning algorithms, which was adopted to determine the optimal control parameters. The amount of the memory access tasks was controlled by the control parameters effectively, which makes the helper thread be finished ahead of the main thread. The experiment results show that the speedup of system performance is achieved by 1.1 times to 1.5 times.

data pre-fetch; helper thread; multi-core system; memory latency; gradient descent

10.11887/j.cn.201605010

http://journal.nudt.edu.cn

2015-11-16

上海市自然科學基金資助項目(15ZR1428600)；計算機體系結構國家重點實驗室開放資助項目(CARCH201206)；上海市浦江人才計劃資助項目(16PJ1407600)

裴頌文(1981—)，男，湖南邵東人，副教授，博士，碩士生導師，Email: swpei@usst.edu.cn

TN95

A

1001-2486(2016)05-059-05