基于性能預測的推測多線程循環選擇方法

劉 斌 趙銀亮 韓 博 李玉祥 吉 爍 馮博琴 武萬杰

?

基于性能預測的推測多線程循環選擇方法

劉 斌 趙銀亮*韓 博 李玉祥 吉 爍 馮博琴 武萬杰

(西安交通大學計算機科學與技術系 西安 710049)

線程級推測(Thread-Level Speculation, TLS)是多核上一種加速串行程序的線程級自動并行化技術。循環具有規則的結構并在運行時占有大量的執行時間，因此循環是挖掘并行性的理想對象。然而，選擇哪些循環并行才能提高程序的加速比是一個很難決定的問題。為了解決該問題，該文提出一種基于性能預測的循環選擇方法。基于輸入訓練集獲取程序預執行的剖析信息，同時結合各種推測因素，構建了循環結構的性能預測模型。預測結果定量評估了循環推測并行的加速比并決定該循環在運行時是否適合并行。實驗結果表明，該文提出的方法能有效地預測循環并行時所蘊含的并行性，并依據預測結果準確地選擇具有并行收益的循環推測并行，最終Olden基準測試集加速比性能平均提升了12.34%。

并行處理；線程級推測；循環選擇；性能預測

1 引言

隨著半導體按照摩爾定律的發展，處理器進入了多核時代，如何有效利用豐富的核資源成為當前研究的熱點。當指令級并行在挖掘并行性方面遇到了瓶頸，線程級并行(Thread-Level Parallelism, TLP)逐漸成為更佳的選擇，尤其適合于片上多處理器(Chip MultiProcessor, CMP)[1]。為了提升程序在CMP上的性能，大量非規則程序需要重構以便適合在多核上并行執行，從而提高程序的加速比性能。線程級推測(Thread-Level Speculation, TLS)作為線程級并行的一種重要方法，允許多個線程激進地并行執行以提高程序的加速比，較為典型的代表有Multiscalar[2], Hydra[3], POSH[4], Mitosis[5], DOMORE[6], SEED[7], DOE[8]和Prophet[9]。

循環具有規則的結構并且在程序執行時占有大量的時間，因此循環成為并行執行最理想的對象。目前，大量的研究關注循環并且從循環中提取多線程[10]。文獻[11]結合數據和控制依賴提出一種誤推測代價模型，并基于該模型對循環進行性能評估，然后對循環進行改造并選擇合適的循環并行執行。與本文類似文獻[11]也選擇了具有收益的循環并行。與本文不同的是該方法僅考慮數據和控制依賴構建模型，而本文方法考慮了多種推測因素。文獻[12]為Java語言提出一種動態循環選擇框架。框架采用硬件運行系統提取依賴時間和推測狀態等信息評估了循環的加速比性能。與本文相似的是對循環評估了循環的加速比并反向指導線程劃分。不同之處在于該框架研究的是面向對象的Java程序，而本文研究的是非規則C語言程序，這兩者程序的特征不同所引起的推測開銷也就不同。文獻[13]采用專家經驗手工并行化了SPEC2000基準測試集。文獻[13]的研究工作非常耗時，容易發生錯誤，而本文的研究工作是一種自動并行化的技術。

本文提出一種基于性能預測的循環選擇方法。基于輸入訓練集多次預執行程序獲取反映程序行為的剖析信息。綜合考慮剖析信息和影響推測并行的各種因素，構建了循環推測并行時的性能預測模型，模型的預測結果決定了該循環是否進行推測并行。本文基于Prophet編譯器實現了性能預測模型。使用Olden基準測試集進行了性能測試，并與傳統方法進行了比較和分析。實驗結果表明本文提出的預測模型能有效地預測循環中所蘊含的并行性，并準確地選擇有收益的循環推測并行，最終Olden基準測試集加速比性能平均提升了12.34%。

2 執行模型

TLS將串行程序在多核上并行執行以提高程序的加速比，執行模型如圖1所示，串行程序被一系列的線程激發點-準控制無關點(Spawning Point- Control Quasi-Independent Points, SP-CQIPs)指令對映射成多線程程序。同時按照串行語義順序，在每一時刻只有一個線程提交數據到內存，該線程被稱為確定線程，而其他線程為推測線程。每個推測線程由串行程序代碼片段及預計算片段組成。預計算片段是由編譯器根據切片技術生成的一小段代碼，用來預測推測線程使用的live-ins(推測線程使用但并非由該線程定義的變量值)。如圖1(a)所示，如果忽略SP-CQIPs指令對，推測多線程程序就轉換成串行程序；如圖1(b)所示，當程序執行到確定線程1中的SP時，如果有閑置核資源，將激發一個新推測線程2；當確定線程1執行到CQIP將驗證直接后繼線程2在預計算片段中使用的live-ins。若驗證正確，則確定線程1提交執行結果，將核資源釋放，該核可以執行其他的線程。然后將確定執行的權限傳遞給直接后繼線程；若驗證失敗則會導致推測執行失敗。當出現驗證失敗時，則撤銷推測線程2，跳過預計算片段，串行執行此直接后繼線程2，如圖1(c)所示；當出現讀后寫(Read After Write, RAW)依賴違規時，如圖1(d)所示，則在當前的狀態下重新啟動該線程。

3 性能預測模型

3.1 基本思想

在循環級并行中，現有的方法大多都采用靜態、定性的方法進行性能評估。在本文中，結合程序的剖析信息和各種推測因素，提出一種定量預測并行性能的循環選擇方法。首先，基于輸入訓練集獲取程序在預執行時的剖析信息并以注釋的形式添加到對應的SUIF中間文件(SUIF-IR)中。然后，綜合剖析信息和推測因素，構建了一種性能預測模型。該模型力圖更加精確地預測程序行為和定量地評估各種推測因素對加速比性能的影響，并利用預測結果評判推測執行性能的好壞程度，最終決定是否在程序運行時并行該循環。

3.2 剖析信息

程序剖析是通過收集程序過去運行時的信息，進而動態調整程序將來的執行。理論上講，如果編譯器能預測出精確的程序行為，它能產生出任何平臺下并行性能最好的代碼。然而實際上，編譯器僅能獲取部分精確的程序行為。為了提高程序行為的精確性，本文開發了Profiler剖析器，分析了程序集的輸入特征，根據輸入特征構造了基準程序的輸入訓練集。通過多次預執行程序捕獲了程序運行時的剖析信息，為性能預測模型的構建提供了更為精確的程序行為。

Profiler的工作流程如圖2所示，當一個程序指令被執行時，首先判斷指令的類型，當指令為循環指令時，記錄當前循環的迭代次數和動態指令數。那么循環的平均動態指令數為L= (L-1×(-1)+)/，其中L-1為上一次循環執行時的平均動態指令數。通過多次預執行程序，求其平均值可獲取循環部分的剖析信息并以注釋的形式標注在對應的SUIF-IR文件中。

圖1 推測多線程執行模型

圖2 程序剖析器

3.3 推測并行影響因素

線程粒度、數據依賴、線程分發和激發距離是影響循環并行性能的關鍵影響因素。一般來說這些因素被綜合考慮決定并行性能的好壞。

(1)線程粒度(thread size)是指一個線程的動態指令數。線程分發、線程啟動與重啟、線程沖突和線程間的通信會引起推測并行開銷，所以線程粒度大小是影響推測性能的關鍵因素。線程粒度過小，推測執行中的各種開銷將會抵消掉推測并行所帶來的收益。線程粒度過大，線程間過多的控制和數據依賴將會導致線程沖突的概率增大，進而增加推測并行時的開銷。

(2)數據依賴(data dependence)是指子線程中的指令引用了父線程中定義的變量。數據依賴距離通常用來刻畫線程間依賴的程度。數據依賴距離是指線程推測并行時子線程執行時需要等待的指令數直到它所需要的數據被父線程產生。如果數據依賴距離過小子線程中需要的值還未由父線程產生，會引發額外的推測代價。

(3)線程分發(thread dispatch)是指當激發一個新的線程時，需要分發一個處理器單元執行該線程。線程分發需要復制父線程堆棧的參數和寄存器里的數值，這需要占用一定的開銷。

(4)激發距離是指在父線程中定義的SP點到子線程開始CQIP點之間動態指令數。如果激發距離過長，子線程執行過程中使用的變量還未產生，將會導致數據推測失敗。如果激發距離過小，推測執行所引起的各種開銷將抵消掉推測并行所獲得的收益。

3.4 性能預測

圖3 循環激發示意圖

圖4 推測執行的加速效果

由式(2)，式(6)和式(7)最終得到循環推測并行時預期加速比為

4 實驗結果和性能分析

本文基于SUIF/MACHSUIF[14]開發了Prophet編譯器[15]，并在編譯器中實現了性能預測的循環選擇方法。同時在Prophet模擬器[9]中驗證了方法的有效性，Prophet模擬器是基于Tomasulo[16]算法實現的超標量流水線4核處理器。最后選用了Olden 基準程序集[17]中的子集測試了本文提出的評估方法。

4.1 剖析信息統計

通過分析Olden程序集的輸入特征，程序的輸入參數個數不同但都為整型。根據均勻分布隨機函數構造了程序的訓練輸入集，采用漸進式預執行來獲取程序的剖析信息。隨著程序預執行次數的增加，程序的剖析信息在程序某次執行之后趨于穩定。本文希望在穩定點之后停止預執行，最終每個程序的預執行次數如表1所示，剖析信息統計如圖6(a)所示。從圖6(a)可以看出程序預執行后所獲取的剖析信息，其中橫軸代表了循環的平均迭代次數，縱軸代表了循環平均迭代體大小。圖6(b)為圖6(a)左下角局域放大圖，從中可以看出Olden中89.16%的循環具有中小規模。同時，7.23%的循環是比較大的循環體。從表1可以看出，每個程序預執行次數各不相同，程序mst的執行次數最多，高達1098次，而程序bh僅執行了106次。經過分析，主要原因是每個程序本身的特征不同，從而導致循環剖析信息達到穩定狀態時所執行的次數也就不同。

表1 Olden基準測試集剖析信息統計

圖6 Olden基準測試集循環剖析信息

理論上講，預執行次數越多，所構建的預測模型也就越準確。然而，由于時間的限制，再多的預執行也無法覆蓋所有的執行路徑。這種情況說明剖析方法在實現過程中，剖析信息有可能不夠完全精確。然而，隨著預執行次數的不斷增加，這些輸入的剖析信息會變得更為精確，從而不斷提高預測模型的精確程度。

4.2 加速比性能比較

圖7給出了基于傳統方法[18]和本文改進方法加速比性能的實驗數據。實驗結果顯示，大多數Olden基準測試集的加速比性能都有一定程度的提升。特別是程序em3d, health和bh性能提升較為顯著，而程序mst和tsp 的加速比性能未發生改變。為了定量分析，定義性能增長率為

圖7 加速比性能比較

表2統計了Olden測試集基于傳統的方法和改進的方法在Prophet模擬器中產生的動態信息及性能增長率。由表2中的最右列可以看出，與傳統的方法相比，本文提出的方法使Olden基準測試集的增長率變化范圍由0到107.61%，其平均增長率可達12.34%。實驗數據顯示，本文的改進方法能充分地挖掘程序中的并行性同時獲得了更好的性能改善。此外，表2和表3分別統計了Prophet系統產生的動態線程統計信息。

程序em3d性能提升高達107.61%，原因在于程序em3d中循環蘊含的并行性較大，同時本文采用性能預測方法并行了8個具有并行收益的循環，而傳統方法僅依靠啟發式并行了4個外層循環(表2)。實驗數據表明改進方法從程序em3d中激發出的線程數目是傳統方法的2.41倍，同時改進方法保證了程序em3d激發成功率也有一定程度的提高，最終本文方法允許更多的推測線程參與并行從而提高了加速比性能。程序bh包含83個循環，是循環數最多的程序。傳統方法僅并行了30個外層循環，本文方法選取具有并行收益的69個循環并行執行，并行的循環數量占循環總數的83.13%而傳統方法僅占36.14%(表2)。改進方法雖然導致線程執行的成功率下降，但并行更多的循環使成功激發的線程數目卻增加了，因此性能提升了3.16%。由表2中數據可以看出，程序health和power 執行行為與程序bh相似。本文方法為這兩個程序分別選取了9個和13個具有并行收益的循環推測并行。雖然激發成功率都降低了(表2)，但成功激發的線程數目增加了，其加速比性能各自提升了6.39%和0.93%。實驗結果表明本文方法能激發更多的推測線程參與并行從而提高程序的加速比性能。

程序voronoi有18個循環體，但循環較小同時蘊含的并行有限。由表2可見，相比傳統方法，雖然本文方法并行循環數增加了1個，但程序voronoi成功激發的線程數目與傳統方法幾乎相近，所以性能提升了，但提升的程度較為有限。程序mst和tsp加速比性能沒有發生任何變化。對于程序mst，由表2可見，循環體數有12個，傳統方法和本文的改進方法都選取了6個循環并行。雖然并行的循環數相同，但本文改進方法選擇了具有并行收益的循環和傳統方法所選擇的最外層循環并不相同，最終導致成功激發的線程數目相差不大。同樣，針對程序tsp，改進方法選取了5個循環并行化。由表2中可見，雖然激發的線程數目增加了，但是相應的線程激發的成功率卻降低了，結果顯示成功激發的線程數目和傳統方法激發的線程數基本一樣，由此可見，加速比性能不僅與線程數目相關而且還與每個線程對并行性能的貢獻相關。最終由于本文方法所獲取的收益與傳統方法所獲取的收益一致導致性能未發生變化。因此程序mst和tsp的加速比性能保持了原來的性能。

表2 Olden基準測試集動態信息統計

表3 Olden基準測試集線程信息統計

改進方法線程粒度平均值與方差均小于傳統方法(表3)，說明Olden基準測試集更適合細粒度并行。同時，改進方法產生的Live-ins變量比傳統方法要多。實驗結果表明本文方法有效的減少了推測并行時的開銷，提升了有效工作時間比例，從而提高了程序的加速比性能。

5 結束語

該文提出和驗證了一種基于性能預測的循環選擇方法。該文主要創新在于：(1)基于程序的輸入訓練集獲取了程序預執行的剖析信息，相比靜態分析方法更加精確地預測了程序執行行為。(2)研究了影響線程級推測的關鍵因素。(3)提出一種性能預測模型。基于性能預測Olden基準測試集加速比性能平均提升了12.34%。實驗表明，該文提出的性能預測方法能夠有效地評估循環推測并行時所蘊含的并行性，并依據評估結果選擇具有并行收益的循環推測并行從而提高程序的加速比性能。

[1] Yang L and Zhai A. Dynamically dispatching speculative threads to improve sequential execution[J]., 2012, 9(3): 13:1-13:31.

[2] Vijaykumar T N and Sohi G S. Task selection for a multiscalar processor[C]. Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture, Dallas, 1998: 81-92.

[3] Hammond L, Hubbert B A, Siu M,The stanford hydra cmp[J]., 2000, 20(2): 71-84.

[4] Liu W, Tuck J, Ceze L,POSH: a TLS compiler that exploits program structure[C]. Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, New York, 2006: 158-167.

[5] Madriles C, García-Qui?ones C, Sánchez J,Mitosis: a speculative multithreaded processor based on precomputation slices[J]., 2008, 19(7): 914-925.

[6] Jialu H, Jablin T B, Beard S R,Automatically exploiting cross-invocation parallelism using runtime information[C]. Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, Shenzhen, 2013: 1-11.

[7] Gao L, Li L, Xue J,SEED: a statically greedy and dynamically adaptive approach for speculative loop execution[J]., 2013, 62(5): 1004-1016.

[8] Sharafeddine M, Jothi K, and Akkary H. Disjoint out-of-order execution processor[J]., 2012, 9(3): 19:1-19:32.

[9] 宋少龍, 趙銀亮, 馮博琴, 等. 支持推測多線程的擴展多核模擬器Prophet+[J]. 西安交通大學學報, 2010, 44(10): 13-17.

Song Shao-long, Zhao Yin-liang, Feng Bo-qin,Prophet+: an extended multicore simulator for speculative multithreading[J]., 2010, 44(10): 13-17.

[10] Wang S Y, Yew P C, and Zhai A. Code transformations for enhancing the performance of speculatively parallel threads[J]., 2012, 21(2): 1-23,

[11] Du Z H, Lim C C, Li X F,A cost-driven compilation framework for speculative parallelization of sequential programs[J]., 2004, 39(6): 71-81.

[12] Chen M and Olukotun K. TEST: a tracer for extracting speculative threads[C]. Proceedings of the 2003 International Symposium on Code Generation and Optimization, San Francisco, 2003: 301-312.

[13] Prabhu M K and Olukotun K. Exposing speculative thread parallelism in SPEC2000[C]. Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, 2005: 142-152.

[14] Smith M D and Holloway G. An introduction to machine suif and its portable libraries for analysis and optimization[OL]. http://www.eecs.harvard.edu/hube/software/nci/overview. html, 2013.

[15] Chen Z, Zhao Y L, Pan X Y,.. An Overview of Prophet[M]. Berlin: German, Springer, 2009: 396-407.

[16] Hennessy J L and Patterson D A. Computer Architecture: A Quantitative Approach [M]. Amsterdam, Elsevier, 2012: 176-183.

[17] Carlisle M C, and Rogers A. Software caching and computation migration in olden[J]., 1996, 38(2): 248-255.

[18] Pan X Y, Zhao Y L, Chen Z,A thread partitioning method for speculative multithreading[C]. Proceedings of the 8th International Conference on Scalable Computing and Communications,Piscataway, 2009: 285-290.

劉 斌： 男，1981年生，博士生，研究方向為并行計算與機器學習.

趙銀亮： 男，1960年生，教授，博士生導師，研究方向為程序語言與編譯系統、大數據并行處理及挖掘.

韓 博： 男，1975年生，高級工程師，研究領域為軟件編程方法學、信息管理學.

A Loop Selection Approach Based on Performance Prediction for Speculative Multithreading

Liu Bin Zhao Yin-liang Han Bo Li Yu-xiang Ji Shuo Feng Bo-qin Wu Wan-jie

(,’,’710049,)

Thread-Level Speculation (TLS) is a thread-level automatic parallelization technique to accelerate sequential programs on multi-core. Loops are usually regular structures and programs spent significant amounts of time executing them, thus loops are ideal candidates for exploiting the parallelism of programs. However, it is difficult to decide which set of loops should be parallelized to improve overall program performance. In order to solve the problem, this paper proposes a loop selection approach based on performance prediction. Basing on the input training set, the paper gathers profiling information during program pre-execution. Combining profiling information associated with the program and various speculative execution factors, the paper establishes a performance prediction model for loops. Then, based on the result of prediction, the paper can quantitatively estimate the speedup of loops and decide which loops should be parallelized on runtime. The experimental results show that the proposed approach effectively predicts the parallelism of loops when speculative execution and accurately selects beneficial loops for speculative parallelization according to the predicted results, finally Olden benchmarks reach 12.34% speedup performance improvement on average speedup.

Parallel processing; Thread-Level Speculation (TLS); Loop selection; Performance prediction

TP314

A

1009-5896(2014)11-2768-07

10.3724/SP.J.1146.2013.01879

趙銀亮 zhaoy@mail.xjtu.edu.cn

2013-12-02收到，2014-03-21改回

國家自然科學基金(61173040)，國家“863”計劃項目(2012AA011003)和博士學科點專項科研基金(20130201110012)資助課題