[發(fā)明專利]基于LLVM的科學(xué)計算程序自動性能預(yù)測方法

有效

• 申請?zhí)枺?/td>: 201510578801.0
• 申請日: 2015-09-11
• 公開（公告）號: CN105183650B
• 公開（公告）日: 2018-03-16
• 發(fā)明（設(shè)計）人: 張偉哲;何慧;謝虎成;郝萌;王學(xué)惠;韓碩;魯剛釗
• 申請（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 哈爾濱市松花江專利商標(biāo)事務(wù)所23109
• 代理人: 楊立超

技術(shù)領(lǐng)域

本發(fā)明科學(xué)計算程序自動性能預(yù)測方法，屬于程序性能預(yù)測技術(shù)領(lǐng)域。

背景技術(shù)

高性能計算是計算機(jī)科學(xué)的一個重要的分支，而性能則是高性能計算的關(guān)鍵特征。程序的執(zhí)行時間是用戶最關(guān)心的性能特征，用戶之所以選擇使用成百上千個處理器處理程序，必然是需要在有限的時間內(nèi)得到程序運(yùn)行結(jié)果。因此，預(yù)測并行程序在某個平臺上執(zhí)行的時間得到了越來越多的研究，這種技術(shù)稱為程序性能評測。

性能評測方法可以分為動態(tài)分析和靜態(tài)分析。

所謂動態(tài)分析的方法，就是通過小規(guī)模預(yù)測大規(guī)模，即在小的輸入規(guī)模和并行度下多次測量，將得到的數(shù)據(jù)繪制在一個坐標(biāo)圖上并進(jìn)行曲線擬合或是回歸分析，最后通過曲線擬合得到的公式，就能夠預(yù)測更大規(guī)模和更大并行度下的運(yùn)行時間。

但這種方法的問題在于：

操作繁瑣：因為需要運(yùn)行許多小規(guī)模，同時同一規(guī)模下還需要多次運(yùn)行取平均值，因此需要耗費(fèi)大量的時間來搜集數(shù)據(jù)。而且程序執(zhí)行時多種因素相互影響，平均值很難趨于穩(wěn)定。而且還會要求大量的采樣數(shù)據(jù)，于是更加使得預(yù)測代價增加。

預(yù)測范圍小：在選擇采樣規(guī)模的時候，還必須盡量平均分布其間距。若是為了測量1024并行度，而選擇的采樣規(guī)模范圍只有[0-128]這樣一個小范圍所擬合出來的曲線，很難保證在1024規(guī)模下是合理的。即使擬合函數(shù)在前面一段范圍能很好的重合，也不能保證在大規(guī)模下也能擬合的很好。這樣就限制了預(yù)測的應(yīng)用范圍。而且有的程序的并行度是有要求的，不能連續(xù)變化，這樣，采樣的數(shù)據(jù)點(diǎn)不能做到平均分布。

結(jié)果合理性不足：因為整個擬合過程都是從純數(shù)學(xué)上分析的，忽略了許多程序內(nèi)部的依賴，因此也就忽略了需要程序特征。這種分析出來的結(jié)果即使精度能夠接受，也不能證明對于其他所有情況和實(shí)驗平臺也能夠保持同樣的精度。

對輸入有限制：動態(tài)分析的干凈的表達(dá)式是其優(yōu)點(diǎn)，同樣也是其缺點(diǎn)。首先它需要識別參數(shù)，這一步只能由人工標(biāo)注完成，妨礙了自動化。

靜態(tài)分析就是基于編譯器來分析代碼，獲取程序的一些特征。LLVM就提供了一種靜態(tài)分析的方法，即靜態(tài)分支概率技術(shù)，下面會有相應(yīng)的介紹。但是該方法存在相應(yīng)的問題：

合理性不足：分支概率只是應(yīng)用了先驗概率和分支指令的類型，實(shí)際上并不能代表目標(biāo)程序。

結(jié)果為常數(shù)：無論是多大的輸入規(guī)模和多大的并行度，計算出來的基本塊頻率為常數(shù)，因為使用的先驗概率就是常數(shù)。然而這并不能滿足我們的要求。

發(fā)明內(nèi)容

本發(fā)明為了實(shí)現(xiàn)科學(xué)計算程序的自動化分析，提高靜態(tài)分析的精確性，同時能夠最后給出程序預(yù)測的時間，進(jìn)而提供了一種基于LLVM的科學(xué)計算程序自動性能預(yù)測方法。

本發(fā)明為解決上述技術(shù)問題采取的技術(shù)方案是：

一種基于LLVM的科學(xué)計算程序自動性能預(yù)測方法，所述方法的實(shí)現(xiàn)過程為：

步驟一、將待預(yù)測的源程序轉(zhuǎn)化為LLVM中的中間代碼bitcode；

步驟二、分析中間代碼bitcode，從而獲得識別通訊指令MPI的調(diào)用、循環(huán)次數(shù)、靜態(tài)分支概率；

步驟三、對所述中間代碼bitcode進(jìn)行混合插樁，分別為：進(jìn)行通訊指令MPI的通訊量及通訊類型的插樁，循環(huán)次數(shù)結(jié)合靜態(tài)分支概率獲得基本塊執(zhí)行次數(shù)進(jìn)行插樁；

步驟四、對進(jìn)行混合插樁后的中間代碼bitcode進(jìn)行代碼刪減，并進(jìn)行優(yōu)化處理；

步驟五、運(yùn)行經(jīng)優(yōu)化處理后中間代碼bitcode，得到llvmprof.out文件；

步驟六、分析llvmprof.out文件，并結(jié)合指令時間預(yù)測執(zhí)行時間。

在步驟二中，分析中間代碼bitcode獲得循環(huán)次數(shù)的具體過程為：

根據(jù)公式％tc＝(％end-％start)/％stride獲得循環(huán)次數(shù)％tc，其中，％end表示循環(huán)結(jié)束值，％start表示循環(huán)起始值，％stride表示循環(huán)步進(jìn)；

％end是真退出的終止指令，認(rèn)為是比較指令icmp；

％start是在循環(huán)外離循環(huán)最近的寫入循環(huán)歸納變量的存儲指令；

分析基本塊Header中的phi指令，獲得含有％start、％stride的指令，從而分析得到％stride值。

通訊指令MPI的通訊量及通訊類型的插樁過程為：