迭代計算特征識別的方法研究

目錄摘要（關(guān)鍵詞） 11 引言 21.1 研究背景與意義 21.2 國內(nèi)外研究現(xiàn)狀 21.3 本文的研究內(nèi)容 31.4 本文的組織結(jié)構(gòu) 42 程序階段檢測分類技術(shù)與動態(tài)二進(jìn)制插樁 52.1 基于動態(tài)二進(jìn)制插樁的pin程序分析技術(shù) 52.1.1 動態(tài)二進(jìn)制插樁技術(shù)的優(yōu)勢 52.1.2 IntelPin-動態(tài)二進(jìn)制插樁框架 62.2 本章小結(jié) 8【參考文獻(xiàn)】 8第PAGEPAGE迭代計算特征識別的方法研究【摘要】為了應(yīng)對網(wǎng)絡(luò)空間信息服務(wù)面臨的海量空間數(shù)據(jù)發(fā)布和大規(guī)模用戶并發(fā)訪問的挑戰(zhàn)，現(xiàn)如今的大數(shù)據(jù)應(yīng)用對內(nèi)存容量和性能提出了更高的要求，完成高性能計算系統(tǒng)功能優(yōu)化的研究顯得尤為重要。而高性能計算應(yīng)用往往具有迭代計算的特征，應(yīng)用的計算和訪存特征一般都與正在執(zhí)行的指令密切相關(guān)，因此識別一次迭代中不同的執(zhí)行代碼區(qū)域，以及識別出程序迭代發(fā)生過程會有助于更準(zhǔn)確地分析和預(yù)測應(yīng)用執(zhí)行特征。不同的代碼區(qū)域?qū)?yīng)著不同的執(zhí)行階段，HPC應(yīng)用的迭代中一般具有多個不同的執(zhí)行階段。以常見的卷積神經(jīng)網(wǎng)絡(luò)訓(xùn)練為例，一次訓(xùn)練迭代中包含卷積層、池化層、全連接層等多個執(zhí)行階段。不同的執(zhí)行階段具有截然不同的計算和訪存特征，所以識別出一次迭代中不同的執(zhí)行階段，并對各個階段的計算和訪存特征進(jìn)行刻畫是至關(guān)重要的。為了從性能上優(yōu)化這些具有普遍迭代計算特征的高性能計算系統(tǒng)，本文將通過程序階段識別技術(shù)，利用Scarphase程序階段分類方法實現(xiàn)分析和識別典型應(yīng)用程序中的迭代計算過程和階段信息，并在此基礎(chǔ)上成功識別出計算機應(yīng)用程序在執(zhí)行中發(fā)生迭代計算過程的時間片段，并使用IntelPin動態(tài)二進(jìn)制插樁框架,同時為了減少開銷時間對其Pintools中算法進(jìn)行優(yōu)化，采集其中迭代計算過程中的訪存地址特征，以達(dá)到以更好地通過資源調(diào)度分配或者數(shù)據(jù)預(yù)取等手段提高系統(tǒng)性能的目的?！娟P(guān)鍵詞】高性能應(yīng)用；程序階段分類；迭代計算；內(nèi)存訪存特征；基本塊向量引言研究背景與意義在大數(shù)據(jù)時代和高性能應(yīng)用廣泛的今天，高性能應(yīng)用如人工智能，機器學(xué)習(xí)，深度學(xué)習(xí)等應(yīng)用往往存在明顯的迭代計算特征，即周期性地執(zhí)行特定的代碼指令。舉一個高性能應(yīng)用中比較經(jīng)典的例子：機器學(xué)習(xí)。機器學(xué)習(xí)的廣泛應(yīng)用離不開迭代計算的執(zhí)行過程。在機器學(xué)習(xí)實踐的應(yīng)用中，機器學(xué)習(xí)系統(tǒng)的一般流程包括了數(shù)據(jù)源獲取、預(yù)處理數(shù)據(jù)、驗證、最終投入運用預(yù)估等內(nèi)容，在這之中模型訓(xùn)練的過程中存在普遍的迭代計算特征，為了達(dá)到所預(yù)期的機器學(xué)習(xí)模型，并且提升機器學(xué)習(xí)模型的識別率和準(zhǔn)確性，通常需要大量數(shù)據(jù)集對模型進(jìn)行訓(xùn)練，訓(xùn)練數(shù)據(jù)，再根據(jù)訓(xùn)練結(jié)果調(diào)整選擇的模型所暴露的一些參數(shù)，然后再次回到訓(xùn)練過程，根據(jù)訓(xùn)練結(jié)果調(diào)整模型參數(shù)，不斷重復(fù)，最終經(jīng)過海量的迭代訓(xùn)練得到最終模型，這個過程具有明顯迭代計算特征，而這整個訓(xùn)練模型的迭代階段幾乎是整個應(yīng)用系統(tǒng)中最耗費時間和性能的過程。因此，識別迭代計算過程的方法研究也會為高性能應(yīng)用的性能提升優(yōu)化指出新的方向。從識別迭代運算的方法展開研究，對迭代計算典例合理分析和識別，針對下一次的迭代運算、訪存特性展開描述。通過前幾輪迭代的信息來預(yù)測下一輪迭代的計算和訪存數(shù)據(jù)區(qū)域，據(jù)此充分利用預(yù)取、復(fù)用、局部性等優(yōu)化方法，提升HPC應(yīng)用訪存性能，相鄰迭代中往往具有相同的執(zhí)行階段，相同執(zhí)行階段具有類似的計算和訪存特征。從硬件層面上，利用前幾輪迭代的信息來預(yù)測下一輪迭代的計算和訪存密度關(guān)系，依此提前對硬件資源進(jìn)行合理的調(diào)度，提高硬件資源利用率，迭代計算階段識別與訪存特征對于實現(xiàn)計算機設(shè)備硬件方面可以提供有效的技術(shù)數(shù)據(jù)參考，根據(jù)這些特征理論上設(shè)計專門面向高性能計算的存儲器設(shè)備和應(yīng)用，對內(nèi)存的性能，硬件開銷，功耗等設(shè)計進(jìn)行優(yōu)化。從軟件層面上，通過獲取迭代計算階段識別和訪存特征，可以對程序進(jìn)行迭代計算分析和優(yōu)化，利用迭代計算的規(guī)律，在進(jìn)行一個迭代程序階段時，根據(jù)上一次迭代循環(huán)的訪存特征去預(yù)測下一次迭代過程的訪存情況，減少緩存命中時間，降低緩存的失效率，從而提升訪存平均時間，維持相較低的運行開銷。除此之外，在涉及迭代計算的多個高性能應(yīng)用領(lǐng)域中，識別程序執(zhí)行過程中的迭代計算過程，獲取到的迭代計算特征與訪存特征將為進(jìn)一步提升高性能應(yīng)用系統(tǒng)的性能和內(nèi)存預(yù)測方法提供重要數(shù)據(jù)依據(jù)和支撐。國內(nèi)外研究現(xiàn)狀在國內(nèi)外目前的研究方向中，提升高性能應(yīng)用的運算速度以及性能的方法主要分為大體著重于硬件或軟件實現(xiàn)。從硬件方面上實現(xiàn)對高性能應(yīng)用的計算速度提升的方法一般有優(yōu)化硬件中的結(jié)構(gòu)設(shè)計或者專門設(shè)計面向適配高性能計算特征計算過程的計算機硬件組件，隨著大數(shù)據(jù)和高性能應(yīng)用的持續(xù)普及化，針對更高性能存儲器的要求也愈發(fā)急切，例如近幾年比較新的存儲器技術(shù)的提出：DCGilmer等人[1]研發(fā)的NRAM技術(shù)，是一個新型高性能存儲器技術(shù)，具備眾多優(yōu)點同時繼承了FRAM（ferroelectricRandomAccessMemory）的高速寫入、高讀寫耐久性，又具備與相當(dāng)?shù)拇笕萘浚崿F(xiàn)很低的功耗。著重使用軟件實現(xiàn)的技術(shù)一般會對程序適當(dāng)分析和識別，整體提升程序數(shù)據(jù)、指令存在的局限性，讓內(nèi)存緩存失效率有所降低，劃分主要有軟件預(yù)取、循環(huán)變換等方式，運用程序分析方式，能夠獲取下一步程序具體的訪問數(shù)據(jù)或是指令，由此能夠在信息之上代入現(xiàn)代處理器所支持的一些非阻塞指令。對比所謂的硬件預(yù)取，軟件預(yù)取能夠更輕易的按照軟件自身的特性合理擬定。早些時候，軟件預(yù)取技術(shù)集中焦點在密集性內(nèi)存操作程序，對此應(yīng)用程序分析技術(shù)[4-5]，就能夠獲悉之后程序執(zhí)行時可能應(yīng)用到的相關(guān)數(shù)據(jù)信息，由此預(yù)取數(shù)據(jù)。比如Wu,Youfeng[6]通過分析程序的步幅模式（StridePattern）來實現(xiàn)數(shù)據(jù)預(yù)取，BeylsK和CongJ等人[7-8]分析程序?qū)?shù)據(jù)訪問的復(fù)用距離（ReuseDistance）對程序執(zhí)行過程進(jìn)行分析來實現(xiàn)數(shù)據(jù)預(yù)取。ChilimbiTM等人[9]研發(fā)了一項動態(tài)軟件預(yù)取框架對軟件之中存在的熱數(shù)據(jù)流加以分析，轉(zhuǎn)而完成指針之上的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)預(yù)取作業(yè)。Cong，Json等人[10]利用循環(huán)變換針對迭代空間變換、調(diào)度等操作完成數(shù)據(jù)訪問局部性的提升。應(yīng)用循環(huán)變換技術(shù)，既能夠讓指令局部性特點有所提升，也可以讓指令轉(zhuǎn)變執(zhí)行順序而讓數(shù)據(jù)的局部性獲得提升。而本文使用的方法可以歸類為上述軟件實現(xiàn)方法，通過識別出迭代計算的過程以及識別迭代計算過程中的內(nèi)存訪問模式，對下一次迭代計算進(jìn)行預(yù)測，并研究如何提高識別的準(zhǔn)確性和維持系統(tǒng)較低的開銷，進(jìn)而可以提高運算效率。本文的研究內(nèi)容本課題的目的是設(shè)計一種有能力識別例如機器學(xué)習(xí)模型等的典型高性能應(yīng)用在運行過程中的迭代計算過程的識別技術(shù)方法，并學(xué)習(xí)采集其在進(jìn)行迭代計算任務(wù)的訪存地址數(shù)據(jù)和性能指標(biāo)，對之后下一次迭代計算提供所需數(shù)據(jù)和訪存特征提供參考，以達(dá)到提高系統(tǒng)預(yù)測準(zhǔn)確率與減少系統(tǒng)開銷的目的。本課題的主要工作內(nèi)容展示如圖1-1所示，針對于目前少有能直接識別程序執(zhí)行中迭代計算過程的框架和應(yīng)用，因此為了實現(xiàn)識別程序迭代計算過程的目的，需要先使用程序階段分類技術(shù)，對程序執(zhí)行過程中相同階段內(nèi)出現(xiàn)的特征值進(jìn)行收集，分類出程序階段信息，然后設(shè)計迭代識別算法對程序階段信息進(jìn)行識別，確定應(yīng)用程序迭代計算階段的執(zhí)行具體分布，本文提出了一種基于Scarphase程序階段分類方法的識別迭代解決方案，并且借助基于動態(tài)二進(jìn)制插樁技術(shù)的程序分析工具IntelPin采集由上一步中識別出來的程序迭代計算過程中的訪存地址和性能指標(biāo)，總結(jié)出高性能迭代計算的訪存特征。本課題工作具體可以劃分為兩部分：識別計算應(yīng)用程序迭代過程以及采集其中迭代計算任務(wù)的訪存地址和性能指標(biāo)。第一部分詳細(xì)地闡述了我們提出的Scarphase方法識別迭代解決方案的具體步驟和原理，以及每一步驟的實現(xiàn)方法和算法優(yōu)化，實現(xiàn)對計算機應(yīng)用程序執(zhí)行過程中的迭代計算過程識別。第二部分描述了我們?nèi)绾胃鶕?jù)第一部分程序中識別出來的迭代計算階段的時段分布，利用我們優(yōu)化改進(jìn)過的程序分析工具，采集此階段的內(nèi)存訪存數(shù)據(jù)和性能指標(biāo)，并最終總結(jié)出迭代計算的訪存特征。圖1-1本文主要工作內(nèi)容展示本文的組織結(jié)構(gòu)本文一共劃分為五個章節(jié)，本文的第一章主要介紹了高性能應(yīng)用計算優(yōu)化的具體發(fā)展實況，對高性能應(yīng)用迭代計算全過程予以識別，了解其對于計算優(yōu)化相關(guān)的研究背景、研究意義，讓高性能應(yīng)用的功能、計算速度等提升的研究現(xiàn)狀加以介紹，對本文研究內(nèi)容也有簡單介紹。第二章側(cè)重于對本文工作背景相關(guān)技術(shù)，程序階段分類模型，程序分析工具以及內(nèi)存預(yù)測技術(shù)等相關(guān)背景技術(shù)展開介紹。第三章我們將具體闡述本文提出的Scarphase識別迭代過程解決方案的具體實現(xiàn)步驟細(xì)節(jié)以及原理，該方案借助程序階段分類技術(shù)，識別程序迭代過程算法等技術(shù)實現(xiàn)了對程序中迭代計算過程的識別，并得出迭代過程在整個程序執(zhí)行中的執(zhí)行分布以及性能信息。第四章介紹本文的實驗環(huán)境與配置，并展示我們的實驗結(jié)果，并分析總結(jié)迭代過程中的訪存與性能特征。第五章總結(jié)全文并探討了未來可能的研究方向。程序階段檢測分類技術(shù)與動態(tài)二進(jìn)制插樁基于動態(tài)二進(jìn)制插樁的pin程序分析技術(shù)Pin是Intel公司在2012年推出的一種動態(tài)二進(jìn)制檢測框架，主要應(yīng)用的是IA-32、x86-64和MIC指令集架構(gòu)，能夠構(gòu)建起一種動態(tài)程序分析工具，對包括Linux，macOS和Windows等在內(nèi)的操作系統(tǒng)以及可執(zhí)行程序予以支持。Pin為之提供相對豐富的API，能夠?qū)⒌讓又噶罴卣鞒橄蟪鰜?，?zhǔn)許進(jìn)程寄存器數(shù)據(jù)等信息能夠當(dāng)做是參數(shù)所傳遞出的代碼。Pin是一種寄存器，能夠在代碼覆蓋上自動存儲、重置，由此能夠恢復(fù)程序以便繼續(xù)運行，針對符號、調(diào)試信息等能夠有一定的訪問權(quán)限。動態(tài)二進(jìn)制插樁技術(shù)的優(yōu)勢程序插樁技術(shù)顧名思義就是確保被測試的程序保證原本的邏輯完整性，基于此能夠在程序里插進(jìn)部分探針，也就是一種探測儀。究其本質(zhì)就是對信息進(jìn)行采集的一種代碼段，能夠為賦值語句或是采集覆蓋信息相對的函數(shù)調(diào)用，從探針執(zhí)行、拋出程序運行等特性數(shù)據(jù)操作中，對相關(guān)數(shù)據(jù)展開分析，由此能夠獲得程序的管控流、數(shù)據(jù)流等數(shù)據(jù)，對于程序運行的動態(tài)上下信息都有所收集，轉(zhuǎn)而達(dá)成測試最終目的的一種方式。根據(jù)插樁對象的區(qū)別，能夠劃分為兩種，一種是源代碼插樁，一種是二進(jìn)制插樁。源代碼插樁（SourceCodeInstrumentation，SCI)：將額外代碼添加到程序源代碼里。意思是，源代碼插樁就是源文件實現(xiàn)完整詞法和語法的分析，基于此展開運行。如此就能夠確保源文件插樁可以達(dá)成較高的精度和針對性。不過源代碼插樁可以和源代碼接觸，讓工作量有所加大，因為編碼語言、版本區(qū)別等需要適當(dāng)改動，源插樁對于軟件應(yīng)用程序的源代碼掌握有所要求，不然就不能操作插樁。二進(jìn)制插樁（BinaryInstrumentation，BI）區(qū)別于源代碼插樁技術(shù)，二進(jìn)制插樁對于被分析的應(yīng)用程序源代碼沒有獲取需求，反而是針對額外插樁分析代碼適當(dāng)添加到二進(jìn)制可執(zhí)行文件里，對于二進(jìn)制插樁，理論上可以與任何軟件應(yīng)用程序一起使用?；诙M(jìn)制插樁，它能夠劃分為兩類狀況：其一是對于沒有執(zhí)行的目標(biāo)代碼進(jìn)行插樁，也就是靜態(tài)插樁，由始至終將測試代碼插入，而后執(zhí)行程序。此等模式適合應(yīng)用到需要完成完整系統(tǒng)或是仿真的時候的代碼覆蓋操作測試；其二是對于運行中的程序進(jìn)行測試代碼插入操作，從而對程序在特殊時間的運行狀態(tài)信息加以檢測。向正在運行的程序插人測試代碼，即動態(tài)二進(jìn)制插樁（dynamicbinaryinstrumentation,DBI）技術(shù)，由于其易用性和靈活性使其在編程語言、軟件測試和安全研究中得到了廣泛的應(yīng)用。兩者主要區(qū)別有：靜態(tài)插樁：該項技術(shù)主要是程序執(zhí)行之前將額外的代碼、數(shù)據(jù)插入，由此成為一個永久變化的可執(zhí)行文件，涵蓋的有簡單手動插樁，基于編譯器/匯編器的插樁，以及鏈接時或鏈接后的可執(zhí)行文件編輯。動態(tài)二進(jìn)制插樁（dynamicbinaryinstrumentation,DBI）進(jìn)行程序運行的時候動態(tài)的將額外代碼、數(shù)據(jù)一一插入，自此可執(zhí)行文件毫無永久變動。動態(tài)插樁技術(shù)的實現(xiàn)往往比靜態(tài)的更復(fù)雜，但可以跟蹤動態(tài)鏈接的庫和間接分支，而這些是靜態(tài)插樁難以處理的。圖2-2插樁技術(shù)分類所謂動態(tài)二進(jìn)制插樁技術(shù)，能夠保證不影響程序動態(tài)執(zhí)行結(jié)果之下，嚴(yán)格遵照用戶的需求分析，進(jìn)行程序執(zhí)行的時候?qū)⑻囟ǖ姆治龃a插入，完成對于程序動態(tài)執(zhí)行全過程的分析和監(jiān)控。大部分動態(tài)二進(jìn)制插樁框架都存在著三式執(zhí)行形式，分別是解釋模式、探測模式和JIT模式?，F(xiàn)階段，動態(tài)二進(jìn)制分析平臺應(yīng)用十分廣泛，涵蓋的內(nèi)容有Pin，DynamoRIO和Frida，此外諸如動態(tài)二進(jìn)制插樁以及別的框架等。IntelPin-動態(tài)二進(jìn)制插樁框架Pin是一項動態(tài)二進(jìn)制插樁檢測框架，整個檢測過程就是在運行的時候針對編譯二進(jìn)制文件合理執(zhí)行。所以，它不能對源代碼重新編譯，同時能夠?qū)討B(tài)生成代碼的檢測程序予以支持。Pin能夠從別的Pintools應(yīng)用在程序執(zhí)行時候動態(tài)的插入代碼到可執(zhí)行文件中，同時也能夠在正在執(zhí)行的進(jìn)程里有所運行。此外，作為一個閉源框架，Pin是它的本體和工具所組成。在其內(nèi)部存在API，用戶用此編寫插件，利用Pin調(diào)用動態(tài)鏈接庫模式，也就是Pintool。具體的Pin大致框架和組成詳見下圖。圖2-2Pin的基本架構(gòu)和原理（1）Pin的基本架構(gòu)與原理從上圖就能夠了解到，Pin主要是進(jìn)程級虛擬機、代碼緩存、給用戶的插樁檢測API等構(gòu)成。對于其虛擬機則是涵蓋了JIT編譯器、模擬執(zhí)行單元、代碼調(diào)度內(nèi)容，在這之中重點就是JIT編譯器。一旦Pin對待插樁程序進(jìn)行加載謀求控制權(quán)后，協(xié)調(diào)好調(diào)度器之后，編譯器對二進(jìn)制文件指令負(fù)責(zé)插樁，完成動態(tài)編譯之后的代碼涵蓋的內(nèi)容有用戶定義下的插樁代碼。等到編譯之后的代碼需要保存在代碼緩存里，從調(diào)度完成交付。在程序運行的時候，Pin就會對于可執(zhí)行代碼的首段指令有所攔截，自此在后續(xù)的指令序列支持下生成新代碼，生成的新代碼也就是遵照用戶定義的具體插樁規(guī)則基于原始指令之上添加到用戶代碼，從種種代碼能夠讓運行的信息被拋出。而后讓控制權(quán)給到新生成的指令序列中，進(jìn)而在虛擬機之中合理運行。一旦程序轉(zhuǎn)到新分支的時候，Pin能夠重新抓到控制權(quán)，由此在新分支指令序列之上誕生新代碼。理解Pin就是一種JIT編譯器，不過其中的輸入并非字節(jié)碼，屬于一種可執(zhí)行文件。Pin能夠?qū)⒖蓤?zhí)行文件中的第一條指令攔截住，而后對于該項指令起始到后續(xù)的指令序列做好新的代碼重新編譯，自此控制權(quán)限也就發(fā)展到新生代碼上。它會和原始代碼相一致，不過Pin能夠確保分支退出以后的代碼序列能夠再次獲得控制權(quán)限。把控到控制權(quán)之后，Pin能夠根據(jù)分支生成較多的代碼，保持運行。Pin讓全部生成的代碼都能夠存儲在內(nèi)存里，如此就能夠重用代碼。此等JIT模式下，執(zhí)行的是一種生成的代碼，僅僅以原始代碼作為一種參考。一旦代碼生成，Pin就會給到用戶自身執(zhí)行的代碼機會。Pin針對具體執(zhí)行的代碼完成插樁，不需要管代碼究竟是在哪個區(qū)域里。（2）Pintool的介紹與使用Pin在操作系統(tǒng)上工作的時候，能夠?qū)⒂脩艏墑e指令捕捉到。對于插樁程序運行，需要同時完成3個程序運行，分別是應(yīng)用程序自身、Pin、Pintool。Pin屬于一種引擎，能夠?qū)?yīng)用程序完成插樁，Pintool之中蘊含了插樁指令，能夠視為是Pin的一個庫。三者能夠共享一個地址空間，不能夠共享庫，需要規(guī)避可能的沖突。要通過插樁完成對目標(biāo)程序的分析，需要了解插樁的位置以及插入的代碼，也就是插樁部分和分析代碼部分。這兩部分在Pin中被集成到了一類可執(zhí)行程序中，也就是Pintool。因此使用Pintool時，我們需要關(guān)注插樁機制（instrumentationcode）：具體在何位置將代碼插入。分析代碼（analysiscode）針對插樁點完成代碼執(zhí)行。Pintool的插樁機制主要有四種模式（即四種插樁粒度）：instructioninstrumentation指令粒度：令I(lǐng)NS表示的是一種指令對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，它是最小的一種粒度。INS代碼插樁就是對指令執(zhí)行前后添加的一些附加代碼，Pintool能夠在可執(zhí)行文件的各個指令支持下完成插樁，此等模式能夠讓開發(fā)者對trace中的迭代循環(huán)指令不會過多投入關(guān)注，包含循環(huán)的指令可能產(chǎn)生多次。會導(dǎo)致程序執(zhí)行緩慢traceinstrumentation蹤跡粒度：TRACE代表的是單入口、多出口的一種指令序列數(shù)據(jù)結(jié)構(gòu)。Pin能夠?qū)RACE劃分為一些基本塊，其中BLL就是單入口、單出口的一種指令序列。對于TRACE就是需要在指令出現(xiàn)跳轉(zhuǎn)的時候插入，深入展開基礎(chǔ)塊分析，多是應(yīng)用在記錄程序執(zhí)行序列routineinstrumentation例程粒度：RTN能夠代表過程程序語言編譯器生成的函數(shù)或是過程。其中Pin運用符號表對例程進(jìn)行查找，也就是對應(yīng)的插入位置，應(yīng)當(dāng)將內(nèi)置的初始化表函數(shù)調(diào)用。imageinstrumentation鏡像粒度：