底層虛擬機(jī)（LLVM）是一個(gè)廣泛使用的編譯框架,其中間表示（IR）中包含有豐富的程序分析信息,眾多以LLVM為平臺(tái)的相關(guān)工作均以IR為基礎(chǔ)開展。數(shù)據(jù)依賴關(guān)系在錯(cuò)誤檢測、定位及程序調(diào)試等領(lǐng)域有著重要應(yīng)用,基于IR的數(shù)據(jù)依賴關(guān)系計(jì)算多采用串行迭代方式,但在應(yīng)對(duì)較大規(guī)模IR文件時(shí)可擴(kuò)展性不夠理想。對(duì)此進(jìn)行了數(shù)據(jù)依賴關(guān)系計(jì)算中指令讀寫的可并行性挖掘,結(jié)合圖形處理器并行計(jì)算優(yōu)勢,提出一種基于LLVM IR的數(shù)據(jù)依賴關(guān)系并行計(jì)算方法 DRPC。以IR為輸入,采用CPU-GPU雙端協(xié)同方式實(shí)現(xiàn)程序數(shù)據(jù)依賴關(guān)系的高效計(jì)算。實(shí)驗(yàn)結(jié)果表明,針對(duì)基準(zhǔn)程序集SPEC,DRPC分別在直接及傳遞數(shù)據(jù)依賴關(guān)系計(jì)算上最高獲得了3. 48x和4. 91x的加速比。 

【文章來源】：計(jì)算機(jī)應(yīng)用研究. 2020,37(02)北大核心CSCD

【文章頁數(shù)】：6 頁

【部分圖文】：

加速比數(shù)據(jù)

圖2給出了LLVM編譯框架的構(gòu)成，主要包含前端、優(yōu)化器及后端三個(gè)部分。LLVM自定義的中間表示IR是該框架的重要組成部分。IR不僅是LLVM優(yōu)化及后端相關(guān)工作的基礎(chǔ)，也是基于LLVM程序分析的各種應(yīng)用的主要輸入。IR一般有可讀匯編形式、二進(jìn)制碼形式及內(nèi)存中間表示形式。LLVM IR內(nèi)容文本通常以指令集形式提供包含函數(shù)聲明、基本塊、變量聲明及函數(shù)調(diào)用等在內(nèi)的各項(xiàng)程序分析信息。LLVM典型的指令集類別包括內(nèi)存訪問指令、終端指令、二進(jìn)制指令、按位二進(jìn)制指令以及其他指令等。在圖1(b)中給出了圖1(a)所示代碼片段的IR文本內(nèi)容示例。

本文主要圍繞三個(gè)影響數(shù)據(jù)依賴并行計(jì)算的可擴(kuò)展性問題，即非規(guī)則存取帶來的帶寬資源浪費(fèi)問題、CPU-GPU雙端的高效協(xié)同問題、線程不同步破壞傳遞數(shù)據(jù)依賴計(jì)算的動(dòng)態(tài)性問題，提出基于LLVM IR的數(shù)據(jù)依賴關(guān)系并行計(jì)算框架(data dependence relation parallel computation framework,DRPC)。如圖3所示，主要由IR特征指令匹配及信息提取(Pre＿M(jìn)atch＿Extract)、數(shù)據(jù)適配存儲(chǔ)映射(Info＿Storage)、直接依賴關(guān)系計(jì)算(Direct＿DepCal)、傳遞依賴關(guān)系計(jì)算(Trans＿DepCal)和并行優(yōu)化(Parallel＿Opt)及數(shù)據(jù)依賴關(guān)系應(yīng)用輸出(Dep Output＿for App)幾個(gè)部分組成。其中，Pre＿M(jìn)atch＿Extract主要負(fù)責(zé)基于特征制導(dǎo)的關(guān)鍵指令匹配及相關(guān)程序分析信息的提取;Info＿Storage主要負(fù)責(zé)根據(jù)直接依賴關(guān)系及傳遞依賴關(guān)系計(jì)算需要，實(shí)現(xiàn)CPU端及GPU端的數(shù)據(jù)信息映射;Pre＿M(jìn)atch＿Extract和Info＿Storage是DRPC的基礎(chǔ)性組成。在適應(yīng)性數(shù)據(jù)映射完成后，由Direct＿DepCal和Trans＿DepCal共同負(fù)責(zé)完成各類數(shù)據(jù)依賴關(guān)系的并行計(jì)算。其中，Direct＿DepCal主要負(fù)責(zé)直接數(shù)據(jù)依賴關(guān)系的并行計(jì)算，Trans＿DepCal負(fù)責(zé)在直接數(shù)據(jù)依賴關(guān)系計(jì)算完成的基礎(chǔ)上繼續(xù)完成傳遞數(shù)據(jù)依賴關(guān)系的并行計(jì)算。在數(shù)據(jù)依賴關(guān)系的并行計(jì)算過程中，Parallel＿Opt會(huì)負(fù)責(zé)實(shí)施進(jìn)一步的性能優(yōu)化，最后由Dep Output＿forApp根據(jù)后續(xù)應(yīng)用需求對(duì)數(shù)據(jù)依賴關(guān)系進(jìn)行組織和輸出。同時(shí)，本文使用CUDA作為DRPC的GPU并行計(jì)算環(huán)境。CUDA的線程模型被劃分為線程格(grid)、線程塊(block)以及線程(thread)三個(gè)層次。每個(gè)線程格內(nèi)包含一定數(shù)量的線程塊，每個(gè)線程塊內(nèi)包含一定數(shù)量的線程，并且每個(gè)線程、線程塊和線程格都有編號(hào)。相同線程塊中的線程可訪問同一個(gè)共享內(nèi)存區(qū)域，所有線程都可以訪問全局內(nèi)存。在進(jìn)行數(shù)據(jù)依賴關(guān)系計(jì)算時(shí)，DRPC將待計(jì)算數(shù)據(jù)按線程數(shù)量劃分，并利用線程編號(hào)進(jìn)行數(shù)據(jù)索引，讓多個(gè)線程同時(shí)進(jìn)行數(shù)據(jù)依賴關(guān)系計(jì)算。

【參考文獻(xiàn)】：
期刊論文
[1]軟件漏洞靜態(tài)檢測模型及檢測框架[J]. 王濤,韓蘭勝,付才,鄒德清,劉銘.  計(jì)算機(jī)科學(xué). 2016(05)
[2]軟件錯(cuò)誤自動(dòng)定位關(guān)鍵科學(xué)問題及研究進(jìn)展[J]. 王克朝,王甜甜,蘇小紅,馬培軍.  計(jì)算機(jī)學(xué)報(bào). 2015(11)
[3]一種基于異常傳播分析的依賴性分析方法[J]. 姜淑娟,徐寶文,史亮,周曉宇.  軟件學(xué)報(bào). 2007(04)
[4]實(shí)用數(shù)據(jù)依賴分析方法[J]. 高念書,張兆慶,喬如良.  計(jì)算機(jī)學(xué)報(bào). 1995(04)

碩士論文
[1]基于LLVM的C程序的動(dòng)態(tài)數(shù)據(jù)依賴分析工具的設(shè)計(jì)與實(shí)現(xiàn)[D]. 吳憂.吉林大學(xué) 2016



本文編號(hào)：3485916