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

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

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

【部分圖文】：

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

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

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

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

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



本文編號：3485916