【摘要】：多核架構(gòu)已成為當(dāng)今的主流,而大量傳統(tǒng)的串行程序和遺留軟件無法充分利用多核處理器的并行計(jì)算性能.人工改寫這些遺留軟件工作量繁重、成本高昂,自動(dòng)實(shí)現(xiàn)程序并行化的技術(shù)成為學(xué)術(shù)和工業(yè)界研究的熱點(diǎn).該文提出了一種新穎的面向一般程序的for循環(huán)優(yōu)化和非規(guī)則代碼段的粗粒度半自動(dòng)并行化方法.該方法通過程序動(dòng)態(tài)分析,根據(jù)程序的控制流和數(shù)據(jù)依賴信息將源程序代碼映射成可計(jì)算單元(CU)圖,從中提取出可并行執(zhí)行的非規(guī)則代碼段.同時(shí)針對(duì)程序中for循環(huán)部分,提出了一種基于局部性分析的分塊收益模型,有效地選擇具有收益的循環(huán)代碼實(shí)施循環(huán)分塊優(yōu)化;提出了一種基于cache均勻映射的最優(yōu)分塊因子大小選擇算法UMC-TSS,以生成優(yōu)化的分塊代碼,充分利用cache性能并實(shí)現(xiàn)分塊的粗粒度并行.該文實(shí)現(xiàn)了一個(gè)基于LLVM編譯架構(gòu)的C/C++源碼到Intel TBB并行源碼轉(zhuǎn)換的半自動(dòng)化工具,它在AST上進(jìn)行深度代碼重構(gòu),只需少量的人工干預(yù)即可生成高效的并行代碼.為了驗(yàn)證該文方法的有效性,從4組不同的基準(zhǔn)測(cè)試集上選取18個(gè)具有代表性的測(cè)試程序在一臺(tái)Intel Xeon多核服務(wù)器上進(jìn)行了一系列實(shí)驗(yàn),在循環(huán)級(jí)和任務(wù)級(jí)并行性能上分別獲得平均10.95和4.45的加速比.和目前最先進(jìn)的一種最優(yōu)分塊大小算法相比,UMC-TSS算法平均提升了4%的分塊代碼性能.實(shí)驗(yàn)結(jié)果還表明由源到源代碼轉(zhuǎn)換工具生成的Intel TBB并行代碼具有良好的并行性和可擴(kuò)展性.
【圖文】：

ｏｖｅｒｃｎｔ＋＋；３３．ｅｎｄｉｆ３４．ｅｎｄｆｏｒ３５．ｉｆｔｅｍｐ＜ｔｕｐｌｅ．ｖａｌｔｈｅｎ／／記錄最�。眨椭担瘜�(duì)應(yīng)的分塊大�。常叮簦酰穑欤澹觯幔欤剑簦澹恚�；３７．ｔｕｐｌｅＩ．＝Ｉ／ＣＬＳ×ＣＬＳ；／／空間局部性優(yōu)化３８．ｔｕｐｌｅ．Ｋ＝Ｋ；３９．ｔｕｐｌｅ．Ｊ＝Ｊ；４０．ｅｎｄｉｆ４１．ｅｎｄｆｏｒ４２．ｐｏｉｎｔｅｒ＋＋；４３．ｅｎｄｗｈｉｌｅ４４．Ｏｕｔｐｕｔ（ｔｕｐｌｅＩ．，ｔｕｐｌｅ．Ｋ，ｔｕｐｌｅ．Ｊ）；圖４粗粒度半自動(dòng)并行化模型的工作流程ＰＬｕＴｏ不提供ＴＳＳ算法，每層循環(huán)默認(rèn)采用３２作為分塊因子．將ＵＭＣ－ＴＳＳ算法集成到本文實(shí)現(xiàn)的源到源并行代碼轉(zhuǎn)換工具中，在調(diào)用ＰＬｕＴｏ對(duì)ｆｏｒ循環(huán)進(jìn)行分塊優(yōu)化時(shí)啟動(dòng)，將計(jì)算出的最優(yōu)分塊大小寫到ｔｉｌｅ．ｓｉｚｅｓ文件中供ＰＬｕＴｏ生成相應(yīng)的優(yōu)化代碼．需要注意的是，盡管該算法計(jì)算最優(yōu)分塊大小時(shí)所需的軟硬件參數(shù)均可自動(dòng)獲得，但式（３）和算法１、２僅適用于包含類似矩陣乘法循環(huán)結(jié)構(gòu)的科學(xué)計(jì)算ｋｅｒｎｅｌ，如ＢＬＡＳ３庫(kù)中的Ｍａｔｍｕｌ、Ｄｓｙｒｋ、ＬＵ等以及Ｊａｃｏｂｉ迭代和Ｓｅｉｄｅｌ方程等．對(duì)于一般程序中的ｆｏｒ循環(huán)語句，，用戶可以根據(jù)表１和表２所總結(jié)的數(shù)組數(shù)據(jù)在Ｌ１和Ｌ２ｃａｃｈｅ中的工作集大小對(duì)式（３）中左側(cè)工作集和ＵＭＣ－ＴＳＳ算法中工作集的模擬映射代碼進(jìn)行修改．表中第１列和第１行分別表示數(shù)組的行和列下標(biāo)．表１中工作集大小的計(jì)算前提假設(shè)是塊內(nèi)循環(huán)順序?yàn)椋�，ｊ，�?

點(diǎn)用來執(zhí)行計(jì)算，邊表示結(jié)點(diǎn)之間的依賴關(guān)系．ｆｌｏｗｇｒａｐｈ在邏輯拓?fù)渖吓cＴａｓｋ圖非常相似．源到源并行代碼轉(zhuǎn)換工具根據(jù)粗粒度任務(wù)的Ｔａｓｋ圖進(jìn)行相應(yīng)的ｆｌｏｗｇｒａｐｈ代碼重構(gòu)和封裝．以圖１中ＣＵ?qǐng)D為例，經(jīng)過合并轉(zhuǎn)換后生成的Ｔａｓｋ圖如圖６所示．其中，Ｔａｓｋ０是一個(gè)虛擬任務(wù)，不進(jìn)行任何計(jì)算，只負(fù)責(zé)傳遞消息給后繼節(jié)點(diǎn)．Ｔａｓｋ圖生成后，直接調(diào)用源到源代碼轉(zhuǎn)換工具生成ｆｌｏｗｇｒａｐｈ并行代碼，其具體實(shí)現(xiàn)可參考文獻(xiàn)［４６］．圖６Ｔａｓｋ圖示例粗粒度任務(wù)的ｆｌｏｗｇｒａｐｈ代碼轉(zhuǎn)換的過程主要分為３步．第１步：確定每個(gè)Ｔａｓｋ對(duì)應(yīng)的代碼段．對(duì)Ｔａｓｋ圖中每個(gè)任務(wù)Ｔａｓｋｉ（包括Ｔａｓｋ０），遍歷ＣｌａｎｇＡＳＴ．當(dāng)ＡＳＴ結(jié)點(diǎn)的源代碼行號(hào)存在于Ｔａｓｋｉ中時(shí)，ＩｄｅｎｔｉｆｙｉｎｇＣｏｄｅＳｅｃｔｉｏｎｓ模塊將其作為字符串存儲(chǔ)在任務(wù)對(duì)應(yīng)的對(duì)象中．第２步：生成ｆｌｏｗｇｒａｐｈ結(jié)點(diǎn)的源代碼．ＳｏｕｒｃｅＣｏｄｅＲｅｗｒｉｔｉｎｇ模塊將根據(jù)３種不同的情況，分別生成ｆｌｏｗｇｒａｐｈ結(jié)點(diǎn)的源代碼．（１）當(dāng)前任務(wù)Ｔａｓｋｉ有一條或者零條入邊，多條出邊．如果它的后繼結(jié)點(diǎn)都接受相同的數(shù)據(jù)（即依賴于同一變量），那么ＳｏｕｒｃｅＣｏｄｅＲｅｗｒｉｔｉｎｇ模塊插入一個(gè)ＩｎｔｅｌＴＢＢ的ｂｒｏａｄｃａｓｔ＿ｎｏｄｅ結(jié)點(diǎn)，否則插入一個(gè)ＩｎｔｅｌＴＢＢ的ｓｐｌｉｔ＿ｎｏｄｅ結(jié)點(diǎn)．ｓｐｌｉｔ＿ｎｏｄｅ結(jié)點(diǎn)能夠?qū)⒉煌愋偷臄?shù)據(jù)傳遞給對(duì)應(yīng)的后繼結(jié)點(diǎn)．如圖６
【作者單位】： 西安交通大學(xué)電信學(xué)院計(jì)算機(jī)系;
【基金】：國(guó)家自然科學(xué)基金(91630206,91330117) 國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFB0201800) 陜西省社會(huì)發(fā)展科技攻關(guān)項(xiàng)目(2016SF-428)資助~~
【分類號(hào)】：TP332

【相似文獻(xiàn)】

相關(guān)期刊論文 前1條

1 趙捷;趙榮彩;韓林;許瑾晨;;循環(huán)攜帶反依賴的MPI自動(dòng)并行化研究[J];計(jì)算機(jī)科學(xué);2012年06期

相關(guān)重要報(bào)紙文章 前1條

1 陳文光 鄭緯民;高性能計(jì)算的三大研究領(lǐng)域[N];計(jì)算機(jī)世界;2006年

相關(guān)博士學(xué)位論文 前1條

1 于海榮;多核環(huán)境下針對(duì)不規(guī)則應(yīng)用程序的非投機(jī)并行策略[D];華中科技大學(xué);2016年

相關(guān)碩士學(xué)位論文 前2條

1 蔡達(dá);基于OpenACC的自動(dòng)并行化技術(shù)研究[D];中國(guó)礦業(yè)大學(xué);2016年

2 沈勤華;可擴(kuò)展的自動(dòng)并行化編譯系統(tǒng)Agassiz[D];復(fù)旦大學(xué);2008年

本文編號(hào)：2520310