TACLeBench中內核程序循環級推測并行性分析

孟慧玲，王耀彬*，李 凌，楊 洋，王欣夷，劉志勤

（1.西南科技大學計算機科學與技術學院，綿陽四川 621010；2.四川省計算機研究院，成都 610041）

（*通信作者電子郵箱wangyaobin@foxmail.com）

0 引言

當前多核平臺加速串行程序時，存在數據依賴限制以及資源利用率低等問題［1-2］，線程級推測（Thread-Level Speculation，TLS）技術［3-4］可開發出更多可用的線程級并行性，保證程序正確性的同時，提高程序性能，成為有效利用多核處理器的途徑之一。該技術將需要執行的串行程序分為一個非推測線程和多個推測線程，使多個線程并行執行［5］；同時保持程序的原始順序，打破線程間的數據依賴對線程并行執行造成的影響，減少程序執行時間，提高加速比。

威斯康星大學首次將Multiscalar［6］作為線程級推測方案提出后，各種不同的線程級推測方案開始陸續出現。例如斯坦福大學研發的Hydra 技術方案［7］、Hammond 等［8］提出的TCC（Transactional Coherence and Consistency）技術方案、卡內基梅隆大學提出的STAMPede技術方案［9］等。目前，劉斌等［10］提出了一種基于性能推測的線程循環選擇方法，最終Olden 基準測試集加速比性能平均提升了12.34%；李美蓉等［11］提出了一種自適應的循環并行粒度調節方法，提升了SPEC CPU 基準測試集性能，并減少了推測開銷；Salamanca 等［12］對硬件事務內存（Hardware Transactional Memory，HTM）支持與線程級推測（TLS）的循環并行化的應用進行了詳細分析，并描述了在此類機器中HTM 上實現TLS 的仔細評估，實驗結果表明，某些循環加速比可達到3.8?？梢钥闯?，TLS技術已在多種串行程序并行化工作中得到有效應用。

TACLeBench［13］是來自全球多個不同研究小組和工具供應商的基準測試程序集合。文獻［14］使用TACLeBench 基準，通過仿真多核ARM（Advancd RISC Machine）處理器來驗證mcQEMU 模擬器時間模型，實驗結果表明，與四核NXP i.MX6Quad 處理器相比，mcQEMU 的時間估計誤差平均僅為15%；文獻［15］利用TACLeBench 基準對GCC（GNU Compiler Collection）與LLVM（Low Level Virtual Machine）進行比較，結果顯示，LLVM 在88%的實驗中編譯速度更快，而在51%的實驗中，GCC 與LLVM 產生的二進制大小幾乎相同；文獻［16］利用TACLeBench 基準驗證設計的重用檢測方法，并針對不同數據的訪問進行表征，發現優化后，最壞情況下數據訪問的時間可減少到6.5%。但目前，TACLeBench 內核基準仍未在線程級推測方面得到有效分析。

本文主要目的是分析將TLS 技術應用于TACLeBench 中內核基準程序時，程序循環結構在推測并行化中的性能提升潛能。在TACLeBench 用于實現小型內核功能的基準中，選取7 個具有代表性的程序，設計了一種動態剖析機制，結合核心數據結構計算循環部分讀寫時間，分析程序線程粒度、并行區域覆蓋率、線程間數據依賴特征對程序加速比大小的影響，并綜合程序加速比與資源利用率判斷內核基準程序適宜處理器核心數目范圍。

1 推測模型和剖析機制

1.1 推測模型

線程推測方案對象通常為程序循環結構或子程序。由于循環迭代獨立性較強，可反復執行導致循環結構所需執行時間較長，并且循環結構確定線程的開始和結束相對容易［17］，因此目前推測并行技術主要針對程序循環結構進行分析，本文也針對程序循環結構展開研究。

循環推測［17-18］將每個循環部分分別作為推測對象，循環推測并行執行時，只需維持一個非推測線程，其余推測線程在非推測線程執行結束后，得到非推測權限，從而成為下一個非推測線程來維護程序正確性。圖1 展示了傳統的串行執行方式，程序按照順序依次執行。圖2 為循環結構的推測執行方式，在推測執行過程中，當有線程產生時，頭處理器首先響應該線程，并分發“Loop_Start”的信號告知其他處理器加載循環的各個迭代。當頭處理器處理完當前線程后，邏輯上的下一個處理器成為新的頭處理器繼續處理該線程。當最后一個處理器處理完成后，會發送“Loop_End”信號結束當前線程的循環迭代執行。為保證剖析機制的速度與開銷，以及開發程序線程級推測并行性，本文的推測模型為與平臺無關的理想機器模型，在該模型中，線程的生成、提交和回退沒有開銷。

圖1 串行執行模型Fig.1 Serial execution model

圖2 循環結構推測執行模型Fig.2 Loop structure speculative execution model

1.2 剖析機制

利用剖析技術對程序運行時特征進行剖析操作能提高線程推測的成功率，在一定程度上對程序進行正確性維護，從而保證程序運行的正確性，并提高程序并行效率。該技術在程序預執行后，搜集相關信息并反饋給編譯器，令編譯器進行線程劃分。本文設計了針對程序循環結構的剖析工具Proloop，利用該工具剖析程序可得到程序并行區域覆蓋率、線程粒度、數據間依賴等信息。

本文相關剖析方案如圖3 所示：首先使用GNU Prof 工具對程序進行初始化分析，得到函數運行時間，選取程序運行時間超過5%的部分為候選程序代碼片段，并在其循環結構中插入剖析標識；隨后使用交叉編譯工具對選中的片段進行交叉編譯操作，得到剖析工具可識別的文件；最后利用ProLoop對所選中的片段進行剖析，使用ThreadList鏈保存推測線程相關信息，hash 表保存訪存操作相關信息。結合剖析所得線程粒度、線程間數據依賴程度等數據與程序源碼進行對比分析后，得出綜合分析結果。

圖3 循環結構剖析方案設計Fig.3 Loop structure analysis scheme design

程序循環標識如圖4 所示，在程序循環結構中，插入的兩個循環標識分別為profiling_loop_start 和profiling_loop_end。其中profiling_loop_start 接收循環標識以及循環變量地址，而profiling_loop_end則代表循環結構結束。在程序執行過程中，循環id被保存在4號寄存器中，循環變量地址則保存在5號寄存器中。

圖4 循環標識示意圖Fig.4 Schematic diagram of loop identifier

循環結構剖析的核心數據結構如圖5 所示，首先將程序所有循環分解為iteration_list_entry_t，再將得到的每個iteration_list_entry_t分為多個iteration_t，該數據結構用于存儲程序循環結構中的循環id、循環變量值以及循環展開開始執行與結束時間。剖析中所有熱點循環串行執行的時間，與整個程序串行執行時間的比值，即為程序并行區域覆蓋率。此外，hash_list 記錄存儲器寫入操作，hash_next 記錄下一次循環展開對存儲器操作的地址指針，hash_pre 記錄上一次循環展開對存儲器操作的地址指針。當剖析工具檢索到程序后續代碼讀取某一存儲單元時，會對其進行攔截，對比該程序存儲單元最后一次寫入時間與當前讀取時間，將當前時間設置為其中較大的一個，程序推測時間與該程序串行運行時間的比值即為程序最終加速比。

圖5 循環結構剖析的核心數據結構Fig.5 Core data structures for loop structure analysis

1.3 性能影響因素

TLS 性能影響因素有推測并行區域覆蓋率、線程粒度規模、線程間數據依賴等。根據Amdahl 定律，程序可并行區域覆蓋率越高，最終加速比越好。線程粒度為程序一個循環迭代的指令條數，線程粒度太小會使程序能耗開銷增大，過大又會使處理器緩存溢出。線程間數據依賴也是TLS重要影響因素，文獻［18］將線程間依賴關系看作生產者和消費者之間的關系，如圖6 所示。生產距離為線程開始執行到線程對特定內存單元最后一次寫入操作之間的指令數，消費距離則是線程開始執行到線程對特定內存單元第一次讀操作之間的指令數。通過程序消費距離和生產距離的比值，可以得到線程間數據依賴數值。將消費距離比上生產距離，若比值范圍為（0，0.6］，說明產生了數據依賴沖突，將此時的數據依賴定義為致命依賴，并且數值越小產生的數據依賴沖突越嚴重；若比值在（0.6，1.0］的范圍內，認為此時會發生數據依賴沖突，將該依賴定義為危險依賴；若比值大于1.0，則定義為安全依賴，認為此時不會發生數據依賴沖突。

圖6 生產距離與消費距離Fig.6 Production distance and consumption distance

2 實驗數據分析

選取TACLeBench 的1.9 版本中用于實現小型內核功能的基準中7個具有代表性的程序，所選應用程序如表1所示。

表1 基準測試程序集說明Tab.1 Description of benchmark test programs

本實驗平臺為基于Linux的Ubuntu 14.04開發版本；指令集為Simplescalar工具集中的PISA（Programme for lnternational Student Assessment）指令集；編譯器為Simplescalar 工具集中提供并改進的gcc-2.7.2.3；剖析器為Simplescalar的功能模擬器sim-fast修改擴充版本。

2.1 性能影響因素分析

并行區域覆蓋率如圖7 所示，并行區域覆蓋率越高越利于使用線程級推測分析，由于TACLeBench 內核基準程序的并行區域覆蓋率都為100%，因此并行區域覆蓋率對內核基準程序加速比影響較小。

圖7 并行區域覆蓋率Fig.7 Parallel area coverage

本文所選程序線程粒度如圖8 所示，大小在101～103范圍內，由于Hydra 項目組提出了線程粒度最適宜的范圍是在以102～104條指令為單位的規模為宜，因此設計內核程序的推測多核處理器時，推測緩存容量應比通用設計降低一個量級，以避免增大程序開銷。

圖8 線程粒度Fig.8 Thread granularity

線程間的數據依賴結果如圖9 所示。除filterbank 以及binarysearch 致命依賴較高，其余程序致命依賴都在1%以下，程序致命依賴所占比值越高，最終得到的加速比數值越低，因此，filterbank 以及binarysearch 致命依賴過高是導致其加速比低的重要原因之一。

圖9 線程間數據依賴Fig.9 Data dependency between threads

綜合各程序并行區域覆蓋率、線程粒度以及線程間數據依賴結果分析發現：內核基準大部分程序并行區域覆蓋率較高，線程粒度適中，但大部分程序存在不同程度的致命依賴以及危險依賴。

2.2 加速比分析

本文選取TACLeBench 中7 個具有代表性的內核基準程序，對比程序在2 核、4 核、8 核、16 核、32 核、64 核和無限核下的加速比情況，分析程序在循環級推測并行化中的性能提升潛能。不同核數即為循環設置不同數量的推測線程，由空閑處理器同時加載并運行各個線程。無限核為程序同一循環結構中所有推測線程設置相同的起始時間，使所有線程同步執行。

bsort程序加速比結果如圖10（a）所示，核數從2核增加到64 核時，加速比接近線性增長，64 核時，接近峰值。對其性能影響因素分析可知，程序覆蓋率達到100%，線程粒度較其他程序偏高，但程序致命依賴以及危險依賴占比都為0%，因此最終程序加速比結果非常理想，達到20.79。

對lms進行剖析，所得加速比如圖10（b）所示，核數在4核到64 核之間時，加速比基本穩定在2.4 左右，核數從64 核增加到無限核時，加速比突然提升。由程序源碼可得，lms 運行時間占比最大的循環迭代次數遠超過64 核時提供的最大推測線程數，無限核時，所有迭代才能并行執行，從而避免處理器閑置時間，因此，加速比在利用有限核加速時，加速效果不如無限核加速效果。綜合實驗結果分析發現，該程序并行區域覆蓋率達到100%，程序線程粒度為53，由于程序運行時間占比最大的函數中，存在指針變量以及函數調用，導致程序存在致命依賴，但致命依賴占比較小，并且函數整體循環結構較多，所以該程序最終加速比結果很好。

從圖10（c）可以看出，st的加速比在2核到16核之間增長幅度較大，16 核之后增長緩慢，32 核時加速比接近峰值。通過程序源碼分析發現，st 為計算兩個大小為1 000 的數字數組的總和、均值、方差和標準差，程序總體較為復雜，并且循環迭代次數較多。在程序運行時長稍短的函數中，存在較多指針數據結構，但運行時長占比較大的函數中沒有產生依賴，因此程序沒有產生致命依賴，并且危險依賴比值較少，最終程序加速比結果較好。

cosf程序加速比結果如圖10（d）所示，程序在2 核到32 核之間，加速比增長較快，32 核之后，增長逐漸緩慢，程序并行區域覆蓋率達到100%，線程粒度適中。對程序源碼進行分析發現，程序較為復雜，盡管程序循環較少，但循環部分包含在程序運行時間占比較大的結構中，并且程序不存在指針以及循環嵌套等結構，導致cosf 的致命依賴以及危險依賴占比都為0%，因此最終加速比結果仍達到4.19。

從圖10（e）可得，matrix1 在2 核到16 核之間，加速比呈線性增長，并于16 核時達到程序加速比峰值，考慮資源合理利用，對matrix1 程序應選擇2 核到16 核使用以避免造成資源浪費。通過對程序性能影響因素分析發現，該程序線程粒度大小適中并且不存在致命依賴，因此程序整體加速比表現較好，但由于該程序循環迭代次數較少，16 核時分配的推測線程足以讓所有迭代同步執行，因此在16 核時，便達到了程序的并行執行限度。

filterbank 在不同核數下的加速比如10（f）所示，核數由2核增加到4 核時，加速比得到了最大限度的提升，隨后加速比趨于穩定，雖然該程序并行區域覆蓋率達到100%，程序線程粒度為47，但程序致命依賴過高，通過對程序源碼分析發現，程序循環次數較少，并且程序多個循環結構中存在函數嵌套調用，導致程序危險依賴達到63%，因此4 核之后加速比沒有隨著核數繼續增加。

由圖10（g）可得，隨著核數的增加，binarysearch 的加速比沒有發生改變。通過性能影響因素分析，該程序線程粒度達到515，造成其程序能耗開銷較大，并且該程序致命依賴達到78%，對程序代碼分析可得，該程序為15 個整數元素的二進制搜索，程序整體循環次數較少，函數運行時間占比最大的函數中不存在循環結構，此外，該函數在運行時長較短的函數循環中被調用，導致程序致命依賴嚴重。因此，程序最終加速效果較差。

圖10 程序在不同核數下的加速比Fig.10 Program speedup ratios with different cores

利用TLS 技術對TACLeBench 內核基準程序進行最大潛能挖掘，對比各程序加速比結果，除binarysearch 外，其余程序最大加速比都在2以上，其中bsort程序加速效果最好，最大加速比超過20，通過其他方法對其進行加速［19］，加速結果在5以下，因此，bsort適合利用循環級推測開發并行性。

對程序性能影響因素與加速比綜合分析發現，當程序代碼存在函數嵌套調用等原因造成函數致命依賴嚴重時，即使程序并行區域覆蓋率較高，線程粒度適當，程序最終加速效果也不理想，如filterbank；對致命依賴嚴重，線程粒度過大的程序，使用TLS 技術基本沒有加速效果，如binarysearch；對致命依賴占比較低的程序，最終加速效果也較好，如bsort、lms、st、cosf、matrix1。因此，在程序三個性能影響因素中，數據依賴影響最嚴重。

2.3 數據歸一化分析

對本實驗所有程序加速比進行歸一化分析結果如圖11所示，大部分程序隨著核數的增加，加速比增長幅度逐漸變小。其中binarysearch 程序由于循環結構過少、線程粒度過大并且致命依賴過高導致最終加速效果較差，利用TLS 技術對其進行分析效果不理想，其余大部分程序在4 核到16 核之間加速比提升所占比重較大，因此對內核基準程序進行推測并行分析時，綜合考慮性能提升與資源浪費，核心數目應盡量選擇4核到16核之間。

圖11 程序加速比歸一化分析Fig.11 Normalized analysis of program speedup ratio

3 結語

本文利用TLS 技術對TACLeBench 中內核基準中的部分程序進行循環級線程推測分析，對比各程序加速比結果，除binarysearch 外，其余程序最大加速比都在2以上，綜合加速比與各性能影響因素，總結出以下結論：

1）本文使用線程級循環推測技術可以使TACLeBench 中的內核測試基準程序性能得到較好提升，大部分程序加速結果較好，其中bsort程序加速比最好，能達到20.79。

2）對于TACLeBench，大部分程序核心數目在4核到16核之間時，加速比增加幅度在50%以上，因此內核基準在選擇程序核數來進行分析時，應盡量將核數控制為4 核到16 核以避免造成資源的浪費。

本實驗選取TACLeBench 內核基準中較適合作循環推測的程序進行分析，由于線程級推測也可應用于子程序分析上，因此后續將利用TLS 技術，設計針對子程序的剖析機制對TACLeBench 內核基準進行分析，并將最終加速結果與本文作對比，分析哪種推測并行方式更適合內核基準程序。