梯度學(xué)習(xí)的參數(shù)控制幫助線程預(yù)取模型*

裴頌文，張俊格，寧 靜

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

?

梯度學(xué)習(xí)的參數(shù)控制幫助線程預(yù)取模型*

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

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

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

數(shù)據(jù)預(yù)取;幫助線程;多核系統(tǒng);訪存延遲;梯度下降

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 參數(shù)控制的預(yù)取模型

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

2.1 預(yù)取參數(shù)的定義

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

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

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

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

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

2.2 參數(shù)控制預(yù)取模型

基于梯度學(xué)習(xí)的參數(shù)控制預(yù)取模型主要由兩部分組成，即熱點分析和代價函數(shù)的構(gòu)造。預(yù)取算法的基本流程如圖1所示。

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

2.2.1 確定程序的熱點部分

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

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

2.2.2 構(gòu)造代價函數(shù)

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

1)K個數(shù)據(jù)塊的訪存與計算；

2)P個數(shù)據(jù)塊的計算。

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

幫助線程負責(zé)的任務(wù)為：P個數(shù)據(jù)塊的預(yù)取，可記做PTm。

為了能更準確反映高等學(xué)校資產(chǎn)負債情況，《政府會計制度》在《高等學(xué)校會計制度》單一會計基礎(chǔ)“收付實現(xiàn)制”的基礎(chǔ)上，引入了“權(quán)責(zé)發(fā)生制”，要求高等學(xué)校采用“雙會計基礎(chǔ)”，即財務(wù)會計核算采用權(quán)責(zé)發(fā)生制，預(yù)算會計核算采用收付實現(xiàn)制。

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

(1)

的絕對值最小。

假設(shè)給主線程分配的訪存任務(wù)為m0，根據(jù)經(jīng)驗可知，隨著K的增加，m0也增加。K，m0的關(guān)系可設(shè)為:

K=θ0·m0

(2)

假設(shè)幫助線程分配的訪存任務(wù)為m1，同樣，根據(jù)經(jīng)驗可知，隨著P的增加，m1也增加。P，m1關(guān)系可設(shè)為：

P=θ1·m1

(3)

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

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

根據(jù)上述推斷，可知代價函數(shù)為:

(4)

2.2.3 計算最優(yōu)的K，P

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

通過m0+m1=M，即

K/θ0+P/θ1=M

(5)

又有

K+P=B

(6)

2.2.4 構(gòu)造幫助線程

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

3 實驗分析

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

表1 Benchmark 參數(shù)配置表

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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] 裴頌文， 吳小東， 唐作其, 等. 異構(gòu)千核處理器系統(tǒng)的統(tǒng)一內(nèi)存地址空間訪問方法[J]. 國防科技大學(xué)學(xué)報， 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] 張建勛, 古志民.幫助線程預(yù)取技術(shù)研究綜述[J]. 計算機科學(xué)， 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

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

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

TN95

A

1001-2486(2016)05-059-05