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

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

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

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

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

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

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

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