多核環(huán)境下針對不規(guī)則應用程序的非投機并行策略.pdf

1、多核處理器成為主流的通用處理器，具有計算能力強、功耗低和設計復雜度低等優(yōu)點。不規(guī)則應用程序中含有大量復雜的控制流和數(shù)據(jù)流，難以充分利用多核處理器帶來的寶貴資源。自動并行化技術可有效地解決這一問題，將串行程序轉換為可以并發(fā)執(zhí)行的多線程程序，發(fā)揮多核潛能。投機并行是自動并行化技術的一個研究熱點。研究人員通過在程序中加入投機因素，增加并行的機會。然而，投機并行需要花費額外的代價處理誤投機。因此，非投機并行成為新的研究熱點。
　　目前，非

2、投機并行可以從不規(guī)則應用程序中提取獨立多線程、流水線多線程以及環(huán)型多線程。但是，當前技術經(jīng)常面臨處理器負載不均衡、擴展性差以及線程間通信延遲敏感等問題。而且，非投機并行主要采用靜態(tài)分析(編譯器)，應用程序中由指針別名引起的問題難以解決影響并行程序的執(zhí)行效率。為了解決上述問題，提出一系列新的措施和解決方案：
　　針對傳統(tǒng)環(huán)型多線程技術對線程間通信延遲敏感的問題，提出一個自動并行化算法DOcyclical。DOcyclical利用基于

3、優(yōu)先權的動態(tài)調度策略降低線程間通信頻率，避免通信延遲出現(xiàn)在并行程序執(zhí)行的關鍵路徑，增強程序對通信延遲的抵抗性。此外，DOcyclical將基于優(yōu)先權的動態(tài)調度與節(jié)點融合策略相結合還可以保持處理器負載盡可能均衡。為了驗證DOcyclical算法的有效性，利用兩套標準測試程序(SPEC CPU2006和StreamIt)分別在二、四、六核處理器進行測試，實驗結果表明DOcyclical算法對線程間通信延遲極不敏感。而且，DOcyclical

4、算法可以超過當前經(jīng)典算法，如DSWP、PS-DSWP和HELIX，平均21-50％、16-27%、15-25%的性能。
　　針對靜態(tài)分析不能消除程序中冗余的依賴關系且難以對程序執(zhí)行重用性分析的問題，提出一個動態(tài)分析框架DSspirit。DSspirit利用基于哈希的策略消除程序中冗余的數(shù)據(jù)依賴關系，利用基于值的策略分析程序的重用性，確定經(jīng)常引起緩存缺失(cache misses)的指令，并向編譯器提供可預取的對象。為了驗證DSsp

5、irit的有效性，利用三套標準測試應用程序(SPEC CPU2006、MPI2007和OMP2012)在Intel i7-4700處理器進行測試。實驗結果表明DSspirit可以克服靜態(tài)分析的缺陷，消除程序中冗余的依賴關系，并提供有預取價值的對象。而且，自動并行化技術中利用動態(tài)分析框架DSspirit可以獲取平均20%的性能提升。
　　針對緩存缺失(cache misses)總是影響并行程序執(zhí)行效率的問題，提出一個基于動態(tài)分析的預

6、取算法，該算法利用運行時環(huán)境確定經(jīng)常引起緩存缺失的指令，并根據(jù)指令的訪問特征制定不同的預取方案。為了驗證預取算法的有效性，利用兩套標準測試程序(SPEC CPU2006和MPI2007)在Intel i7-4700處理器進行測試。實驗結果表明預取算法可以明顯地提升并行程序的緩存命中率，縮短程序的總體執(zhí)行時間。
　　為了保證多線程程序對通信延遲不敏感且具有較高的緩存命中率，設計一個自動并行化系統(tǒng)HSparallel，該系統(tǒng)首先利用動

7、態(tài)分析框架DSspirit確定具有預取價值的對象，然后利用自動并行化算法DOcyclical避免通信延遲出現(xiàn)在并行程序執(zhí)行的關鍵路徑，同時利用預取算法提高程序的緩存命中率。為了驗證HSparallel的有效性，利用兩套標準測試程序(SPEC CPU2006和MPI2007)在Intel i7-4700處理器進行測試。實驗結果表明HSparallel可以帶來顯著的性能提升。而且，HSparallel超過當前主流算法，如Paralax和文獻