游 心 楊海龍 雷克倫 孔祥浩 徐 筠 欒鐘治 錢德沛

1（北京航空航天大學(xué)計(jì)算機(jī)學(xué)院 北京 100191）

2（北京仿真中心航天系統(tǒng)仿真重點(diǎn)實(shí)驗(yàn)室 北京 100854）

如今，無論是生產(chǎn)軟件還是科學(xué)計(jì)算應(yīng)用都變得越來越復(fù)雜，其中軟件包含的大量庫依賴項(xiàng)以及復(fù)雜的控制和數(shù)據(jù)流使得軟件效率難以得到保證.并且，如此高的復(fù)雜性很容易導(dǎo)致意料之外的低執(zhí)行效率，從而阻礙軟件達(dá)到最佳性能.軟件效率低下往往涉及冗余操作，例如從內(nèi)存中反復(fù)加載相同的值[1]、寫入從未使用過的值[2]、使用從未使用過的中間值來覆蓋同一位置的值[3]以及重復(fù)計(jì)算相同的值[4-5].此外，大量的應(yīng)用將稀疏數(shù)據(jù)作為輸入，而使用稠密數(shù)據(jù)結(jié)構(gòu)處理該稀疏數(shù)據(jù)將會(huì)導(dǎo)致資源的大量浪費(fèi)[6-8].以往的研究已經(jīng)證明上述低效率的根本原因之一是一些指令和數(shù)據(jù)結(jié)構(gòu)經(jīng)常處理冗余零[9].

目前已經(jīng)有大量的真實(shí)應(yīng)用報(bào)告了大量冗余零的存在并對(duì)其進(jìn)行針對(duì)性優(yōu)化來達(dá)到更好的效果.例如在深度神經(jīng)網(wǎng)絡(luò)領(lǐng)域，研究人員[7-8]已經(jīng)提出了軟件或者硬件的優(yōu)化方法來實(shí)現(xiàn)對(duì)神經(jīng)網(wǎng)絡(luò)中稀疏性的自動(dòng)檢測(cè)以及特定的稀疏優(yōu)化來達(dá)到更好的性能；在視頻編碼領(lǐng)域，研究人員[6]提出了一些全0 塊（all-zero block）檢測(cè)方法來跳過這些塊的計(jì)算從而達(dá)到更高的性能.而這些方法都是針對(duì)特定領(lǐng)域上的工作，并不能對(duì)其他領(lǐng)域的應(yīng)用提供冗余零的檢測(cè)或優(yōu)化指導(dǎo).

此外，現(xiàn)代編譯器優(yōu)化無法識(shí)別訪存和計(jì)算操作中涉及的冗余零以進(jìn)行進(jìn)一步的代碼優(yōu)化.而諸如perf[10],HPCToolkit[11],VTune[12],Gprof[13],CrayPat[14],Oprofile[15]這些性能分析工具也不會(huì)識(shí)別與冗余零相關(guān)的低效率行為，從而無法提供相應(yīng)的優(yōu)化指導(dǎo).ZeroSpy[9]雖然能夠正確識(shí)別冗余零相關(guān)的低效行為并給出相應(yīng)的指導(dǎo)建議，其檢測(cè)方法仍然局限于Intel 平臺(tái)，且不支持目前逐漸流行的ARM 計(jì)算平臺(tái).此外，ZeroSpy 的高性能開銷也大大加劇了真實(shí)應(yīng)用的性能分析開銷.而目前ARM 架構(gòu)在高性能領(lǐng)域已經(jīng)越來越受到重視，在Top500 中取得世界第一性能的富岳超級(jí)計(jì)算機(jī)[16]的中央處理器就是基于ARMv8架構(gòu)設(shè)計(jì)的，而目前并沒有一款編譯器或性能分析工具可以在ARM 平臺(tái)識(shí)別冗余零相關(guān)的低效行為，從而錯(cuò)失大量潛在的性能優(yōu)化機(jī)會(huì).

因此，本文提出了DrZero[17]，它是一款基于冗余零檢測(cè)的可跨平臺(tái)的、具有更低分析開銷的性能分析工具.DrZero 實(shí)現(xiàn)了一種檢測(cè)應(yīng)用程序執(zhí)行過程中冗余零的方法，包括：1）識(shí)別由于數(shù)據(jù)結(jié)構(gòu)使用不當(dāng)、數(shù)據(jù)寬度過大以及無用計(jì)算造成的冗余零；2）提示冗余零發(fā)生的源代碼行與執(zhí)行上下文來提供直觀的優(yōu)化指導(dǎo)；3）依據(jù)應(yīng)用檢測(cè)出的冗余零信息進(jìn)行針對(duì)性優(yōu)化顯著提高應(yīng)用的執(zhí)行性能或能效.此外，DrZero 基于Dynamorio 二進(jìn)制動(dòng)態(tài)插樁框架[18]實(shí)現(xiàn)，并通過基于數(shù)據(jù)流分析的數(shù)據(jù)類型推斷來識(shí)別ARM訪存指令讀取的數(shù)據(jù)類型，以及實(shí)現(xiàn)在線細(xì)粒度緩存跡分析方法來進(jìn)一步減少性能開銷.相較于ZeroSpy，DrZero 支持跨平臺(tái)的冗余零檢測(cè)，并擁有更低的開銷以及更加友好的報(bào)告界面來提示足夠充分的冗余零信息以及對(duì)應(yīng)的優(yōu)化建議.

1 冗余零的定義與來源

類似文獻(xiàn)[9]中所提出的冗余零定義，本文也使用冗余映射（redmap）以及冗余零比例（redundant zeros fraction）作為冗余零的檢測(cè)目標(biāo).其中，冗余零為指令讀取值的高位0 值，因此理論上完全消除冗余零對(duì)值的表達(dá)與計(jì)算的正確性不會(huì)造成任何影響.因此高冗余零比例表示具有較大的優(yōu)化空間，冗余映射則展現(xiàn)讀取值的模式，從而為優(yōu)化策略的設(shè)計(jì)提供參考.其中，冗余零主要來自3 個(gè)方面：數(shù)據(jù)寬度過大、數(shù)據(jù)結(jié)構(gòu)使用不當(dāng)以及0 值相關(guān)的無用計(jì)算.

1）數(shù)據(jù)寬度過大是造成訪存過程中某個(gè)指令或者從某個(gè)數(shù)據(jù)對(duì)象讀取的值中高位字節(jié)總是為0 的主要原因之一.例如，訪存指令頻繁地從內(nèi)存讀取64b整型值（占8B），且該值的高7B 總是為0，即該訪存指令訪問了大量的冗余零.造成該冗余零現(xiàn)象的主要原因就是數(shù)據(jù)寬度過大，該數(shù)據(jù)使用8b 整型（占1B）即可保證數(shù)值的等價(jià)性，而不必使用過長的64b整型來存儲(chǔ)、訪問該數(shù)據(jù).這些冗余零會(huì)造成有限的多級(jí)緩存資源的浪費(fèi)，從而造成潛在的性能損失.

2）使用不當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也會(huì)造成大量的冗余零，從而造成大量的資源浪費(fèi).如圖1 所示，使用稠密數(shù)據(jù)結(jié)構(gòu)與稠密算法對(duì)該稀疏數(shù)據(jù)進(jìn)行處理會(huì)造成大量的完全冗余零.而如果應(yīng)用稀疏數(shù)據(jù)結(jié)構(gòu)以及對(duì)應(yīng)的稀疏算法會(huì)大幅度減少存儲(chǔ)、訪存開銷，并避免大量無用的0 值相關(guān)的計(jì)算，從而得到更好的性能.

Fig.1 An illustration of software inefficiency by inappropriate use of data structure圖 1 使用不當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)導(dǎo)致的軟件低效行為示例

3）0 值相關(guān)的無用計(jì)算則是另一類常見的冗余零來源.圖2 展示了bwaves 應(yīng)用程序中0 值相關(guān)的無用計(jì)算示例代碼.通過DrZero 檢測(cè)以及人工插樁等細(xì)致分析后，該示例代碼中u,v,w這3 個(gè)變量常常讀取完全冗余零（0 值），從而進(jìn)一步造成在計(jì)算mu變量值時(shí)引入繁重的0 值相關(guān)的無用計(jì)算.0 值相關(guān)的無用計(jì)算并不是所有的冗余零都值得進(jìn)行優(yōu)化，原則上高冗余零比例的、復(fù)雜且高計(jì)算開銷的操作更加值得進(jìn)一步優(yōu)化.

Fig.2 An example of zero-agonistic computation圖 2 0 值相關(guān)的無用計(jì)算示例

2 相關(guān)工作

值得注意的是，傳統(tǒng)的基于硬件計(jì)數(shù)器的性能分析工具[10-15,18]往往由于其中存在的大量冗余訪存與計(jì)算反而會(huì)充分利用硬件資源，從而得到較好的性能結(jié)果.因此，若含有大量冗余零的訪存、計(jì)算操作浪費(fèi)了大量資源，基于硬件計(jì)數(shù)器的性能分析工具并不能有效地識(shí)別類似冗余零的資源浪費(fèi)導(dǎo)致的軟件低效行為，從而無法給出有效的優(yōu)化建議.

值分析器（value profiler）的開發(fā)是為了查明軟件中含有的冗余計(jì)算.值分析器最早由Calder 等人[19]提出，它可以檢測(cè)程序代碼并查明存儲(chǔ)在寄存器或存儲(chǔ)器中的不變變量或半不變變量.其后續(xù)研究提出了此值分析器的一種變體[20].Wen 等人[4]開發(fā)了一種細(xì)粒度的探查器（RedSpy）來識(shí)別靜默寫入（scilent writes）并給出相關(guān)指導(dǎo)優(yōu)化.RedSpy 不但檢測(cè)到計(jì)算結(jié)果以及數(shù)據(jù)移動(dòng)中的冗余，還可以通過報(bào)告調(diào)用上下文及其在源代碼中的位置來報(bào)告冗余，從而精確定位冗余代碼區(qū)域.此外，Su 等人[1]開發(fā)了另一個(gè)細(xì)粒度的探查器LoadSpy，以識(shí)別軟件中的冗余負(fù)載，他們聲稱，在軟件的指令中加載相同的值效率很低.LoadSpy 跟蹤每個(gè)加載指令以查明這些冗余負(fù)載，并報(bào)告涉及冗余負(fù)載的指令對(duì).此外，Tan 等人[21]開發(fā)了CIDetector，并證明即使使用現(xiàn)代的優(yōu)化編譯器，無效操作和冗余操作仍然存在.ZeroSpy[9]可以查明與零相關(guān)的冗余算術(shù)和內(nèi)存操作，但ZeroSpy 基于Intel Pin[22]實(shí)現(xiàn)，且ARM 指令集與x86 指令集不同，訪存與計(jì)算是分離的，所以不能通過指令來識(shí)別訪問內(nèi)存數(shù)據(jù)的類型.因此，ZeroSpy 的檢測(cè)方法與實(shí)現(xiàn)手段都局限在Intel 平臺(tái)，不能直接應(yīng)用在跨平臺(tái)冗余零檢測(cè)中.

另外，有一些方法致力于通過減少數(shù)據(jù)類型的長度來利用冗余零.Stephenson 等人[23]提出了一種位寬分析方法來靜態(tài)標(biāo)識(shí)變量的最大所需位寬，從而盡可能減少數(shù)據(jù)類型的長度.當(dāng)在目標(biāo)FPGA 平臺(tái)上進(jìn)行評(píng)估時(shí)，他們的方法可能對(duì)面積、速度和功耗產(chǎn)生積極影響.另一方面，Precimonious[24]工具可用來權(quán)衡浮點(diǎn)精度和性能.這些方法與工具都只能檢測(cè)數(shù)據(jù)長度中的冗余，而DrZero 還可以檢測(cè)不適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)以及零相關(guān)導(dǎo)致的冗余計(jì)算.此外，DrZero 也不需要任何源代碼即可進(jìn)行冗余零檢測(cè).

3 冗余零檢測(cè)方法

本文提出并實(shí)現(xiàn)了針對(duì)冗余零的跨平臺(tái)細(xì)粒度性能分析工具DrZero.具體來講，DrZero 基于Dynamorio動(dòng)態(tài)二進(jìn)制插樁框架[25]實(shí)現(xiàn).相較ZeroSpy 選用的Intel Pin[22]，Dynamorio 具有可跨平臺(tái)（支持x86 與ARM）、支持細(xì)粒度的分析與插樁、開源等特性，從而可以支持跨平臺(tái)更加細(xì)粒度的插樁、分析工具.Dynamorio框架是基于事件來觸發(fā)分析與插樁過程，例如線程啟動(dòng)和終止、基礎(chǔ)塊載入等事件.當(dāng)事件發(fā)生時(shí)，Dynamorio會(huì)觸發(fā)初始化時(shí)注冊(cè)的回調(diào)函數(shù)來對(duì)目標(biāo)事件進(jìn)行分析、插樁.其中，當(dāng)基礎(chǔ)塊載入事件發(fā)生時(shí)，Dynamorio可以獲取該基礎(chǔ)塊將要執(zhí)行的所有指令，因此DrZero基于各個(gè)基礎(chǔ)塊對(duì)所有包含內(nèi)存讀取操作的指令進(jìn)行分析，并進(jìn)行基礎(chǔ)塊級(jí)別的動(dòng)態(tài)二進(jìn)制插樁.DrZero的跨平臺(tái)冗余零檢測(cè)技術(shù)總覽如圖3 所示，包含：①基于數(shù)據(jù)流分析的數(shù)據(jù)類型推斷；②細(xì)粒度緩存跡插樁與在線分析.其中，根據(jù)檢測(cè)目標(biāo)的不同，在線分析又分為以代碼為中心的分析模式和以數(shù)據(jù)為中心的分析模式.在目標(biāo)程序執(zhí)行完畢后，DrZero 會(huì)生成一系列報(bào)告文件，并通過定制的VSCode 擴(kuò)展來將冗余零報(bào)告可視化，并基于檢測(cè)結(jié)果提供優(yōu)化建議.下文將對(duì)DrZero 的各個(gè)核心技術(shù)進(jìn)行詳細(xì)講解.

3.1 基于數(shù)據(jù)流的數(shù)據(jù)類型推斷

與x86 指令集不同，ARM 指令集集中訪存與計(jì)算為不同的指令，即計(jì)算操作不能直接訪問內(nèi)存，而同一訪存指令可能讀取整型值或浮點(diǎn)值.此外，通用寄存器除了保存整型值以外，也可能保存浮點(diǎn)值并在計(jì)算時(shí)移動(dòng)到浮點(diǎn)寄存器來進(jìn)行浮點(diǎn)計(jì)算，因此也不能只通過內(nèi)存讀取操作的目標(biāo)寄存器類型來判斷讀取值是浮點(diǎn)值還是整型值.為了解決上述挑戰(zhàn)，DrZero 采用基于數(shù)據(jù)流的數(shù)據(jù)類型推斷來盡可能推斷出讀取值的數(shù)據(jù)類型，從而可以采用對(duì)應(yīng)的冗余零分析策略來獲取冗余映射以及冗余零比例.

Fig.3 An overview of the cross-platform redundant zeros detection techniques of DrZero圖 3 DrZero 跨平臺(tái)冗余零檢測(cè)技術(shù)總覽

基于數(shù)據(jù)流的數(shù)據(jù)類型推斷算法如算法1 所示.由于數(shù)據(jù)類型中的數(shù)據(jù)寬度可以直接由訪存寬度直接獲取，因此算法1 的主要目的在于推斷該指令讀取值是否為浮點(diǎn)數(shù).首先，算法1 根據(jù)目標(biāo)寄存器類型推斷是否為浮點(diǎn)指令（行①）.如果目標(biāo)寄存器為浮點(diǎn)寄存器則推斷為浮點(diǎn)指令，返回真值.由于本文主要關(guān)注訪存指令中存在的冗余零現(xiàn)象，因此只在指令讀取內(nèi)存中的值時(shí)才進(jìn)一步基于數(shù)據(jù)流進(jìn)行推斷（行②）.若該指令讀取內(nèi)存值，算法則枚舉所有目標(biāo)寄存器對(duì)象，并對(duì)每個(gè)目標(biāo)寄存器對(duì)象查找該基礎(chǔ)代碼塊中在該指令后執(zhí)行的所有指令的源寄存器中是否存在定義-使用關(guān)系（行③～?），若存在，則返回使用目標(biāo)寄存器的指令的類型（行?）.如果上述數(shù)據(jù)流分析過程都沒有找到定義-使用關(guān)系，則返回先前推斷的instr指令類型（行?）.

算法1.數(shù)據(jù)類型推斷算法.

在ARM 平臺(tái)上，算法1 可以有效地識(shí)別大部分浮點(diǎn)數(shù)內(nèi)存訪問指令，從而應(yīng)用適當(dāng)?shù)娜哂嗔惴治龇椒▉斫⑷哂嘤成洳⒆R(shí)別冗余零.但由于程序執(zhí)行過程的不確定性，基礎(chǔ)代碼塊最后的跳轉(zhuǎn)指令的目標(biāo)地址往往無法靜態(tài)確定，因此基于數(shù)據(jù)流的數(shù)據(jù)類型推斷僅受限于單個(gè)基礎(chǔ)代碼塊，從而某些存在跨基礎(chǔ)代碼塊的定義-使用關(guān)系的浮點(diǎn)值讀取指令時(shí)可能仍會(huì)推斷為讀取整型值.然而，由于時(shí)空局部性的存在，這些推斷錯(cuò)誤依舊可以認(rèn)為是較少的，不會(huì)影響最終報(bào)告的冗余映射與冗余零比例.

3.2 在線細(xì)粒度緩存跡分析

為了分析得到所有訪存操作讀取內(nèi)存值的冗余映射與冗余零信息，本文提出了在線細(xì)粒度緩存跡分析在細(xì)粒度緩存區(qū)中緩存一定量的訪存操作信息并基于該緩存區(qū)進(jìn)行針對(duì)冗余零的在線分析來檢測(cè)冗余零導(dǎo)致的軟件低效行為.具體來講，該過程主要分為4 步：細(xì)粒度緩存區(qū)的創(chuàng)建、細(xì)粒度緩存跡插樁、細(xì)粒度緩存跡更新以及在線冗余零分析.

在工具初始化時(shí)，DrZero 需要?jiǎng)?chuàng)建細(xì)粒度緩存區(qū)來保存程序運(yùn)行過程中內(nèi)存讀取操作的信息，包括目標(biāo)地址、調(diào)用上下文以及讀取的值.為了避免插樁后的代碼執(zhí)行時(shí)頻繁檢查讀取值的數(shù)據(jù)類型從而造成繁重的分支操作，DrZero 對(duì)每個(gè)可能的數(shù)據(jù)類型都建立緩存區(qū)，包括1b，2b，4b，8b 整型值，單、雙精度浮點(diǎn)值以及128b，256b 整型向量，單、雙精度浮點(diǎn)向量.對(duì)于每個(gè)緩沖區(qū)，DrZero 分配大小為4 096個(gè)元素的緩沖區(qū).

在目標(biāo)應(yīng)用程序執(zhí)行時(shí)，Dynamorio 會(huì)觸發(fā)基礎(chǔ)代碼塊載入事件.在經(jīng)過3.1 節(jié)所述的數(shù)據(jù)類型推斷后，DrZero 向基礎(chǔ)代碼塊中插入細(xì)粒度緩存跡更新以及在線冗余零分析代碼.由于讀取內(nèi)存值的數(shù)據(jù)類型可靜態(tài)推斷，DrZero 根據(jù)推斷的數(shù)據(jù)類型來插入相應(yīng)的指令，向?qū)?yīng)緩存區(qū)存儲(chǔ)目標(biāo)內(nèi)存地址、調(diào)用上下文句柄（通過DrCCTProf[26]獲?。┮约白x取值.例如，圖3 中內(nèi)存讀取操作被推斷為32b 浮點(diǎn)類型（FP32），然后插入指令將相應(yīng)信息緩存到FP32 對(duì)應(yīng)的細(xì)粒度緩存跡中以便后續(xù)在線分析.此外，在每個(gè)基礎(chǔ)代碼塊級(jí)別都需要靜態(tài)推斷各個(gè)細(xì)粒度緩存跡將要填充的數(shù)量，并對(duì)每個(gè)將要填充的細(xì)粒度緩存跡都在基礎(chǔ)代碼塊入口進(jìn)行插樁：

1）插入指令，檢查是否將滿或溢出；

2）插入條件跳轉(zhuǎn)指令與函數(shù)調(diào)用，從而保證在將滿或溢出時(shí)調(diào)用在線冗余零分析代碼；

3）在在線冗余零分析后清空該緩存跡.

在插樁完成后，Dynamorio 將會(huì)負(fù)責(zé)執(zhí)行插樁后的代碼，因此所有內(nèi)存讀取操作的信息都會(huì)被記錄到細(xì)粒度緩存跡中，并及時(shí)更新細(xì)粒度緩存跡，以及在將滿或溢出時(shí)觸發(fā)在線冗余零分析.該過程也稱為細(xì)粒度緩存跡更新.在線冗余零分析過程根據(jù)檢測(cè)模式的不同分為以代碼為中心的在線分析和以數(shù)據(jù)為中心的在線分析.由于具體DrZero 的冗余零檢測(cè)算法與ZeroSpy[9]中的冗余零檢測(cè)算法類似，本文僅介紹在線分析的核心思想.

1）以代碼為中心（code-centric）的在線分析.該分析過程旨在發(fā)現(xiàn)指令級(jí)別的冗余零現(xiàn)象，可以檢測(cè)冗余零導(dǎo)致的無用計(jì)算以及數(shù)據(jù)寬度過長導(dǎo)致的資源浪費(fèi).由于觸發(fā)在線分析的細(xì)粒度緩存跡都已經(jīng)靜態(tài)確定其數(shù)據(jù)類型，在線分析過程中便不用檢查其類型并直接進(jìn)行冗余零檢測(cè).在冗余零檢測(cè)后，所有檢測(cè)數(shù)據(jù)都被記錄、累計(jì)在以調(diào)用上下文句柄為鍵值的散列映射表中.

2）以數(shù)據(jù)對(duì)象為中心（data-centric）的在線分析.該分析過程旨在發(fā)現(xiàn)數(shù)據(jù)對(duì)象級(jí)別的冗余零現(xiàn)象，可以檢測(cè)數(shù)據(jù)結(jié)構(gòu)使用不當(dāng)以及數(shù)據(jù)寬度過長的問題.類似以代碼為中心的在線分析，在線分析過程中不用檢查其數(shù)據(jù)類型.數(shù)據(jù)對(duì)象信息則在在線分析過程中通過緩存跡中的目標(biāo)內(nèi)存地址從DrCCTProf獲取數(shù)據(jù)對(duì)象信息，包括靜態(tài)數(shù)據(jù)對(duì)象的變量名以及動(dòng)態(tài)數(shù)據(jù)對(duì)象分配時(shí)的調(diào)用上下文.由于只有靜態(tài)數(shù)據(jù)對(duì)象與動(dòng)態(tài)數(shù)據(jù)對(duì)象可以獲取到足夠的調(diào)試信息以供后續(xù)優(yōu)化，本文只對(duì)靜態(tài)與動(dòng)態(tài)數(shù)據(jù)對(duì)象進(jìn)行冗余零檢測(cè)與報(bào)告.

相較ZeroSpy[9]的檢測(cè)方法，在線細(xì)粒度緩存跡分析擁有3 點(diǎn)優(yōu)勢(shì)：1）盡可能避免頻繁、高開銷的算數(shù)狀態(tài)保存操作；2）避免對(duì)每次內(nèi)存讀取的值進(jìn)行分析、記錄，從而減輕工具對(duì)應(yīng)用的緩存污染；3）集中批處理冗余零檢測(cè)與記錄操作，具有更好的時(shí)空局部性.

3.3 冗余零報(bào)告與性能優(yōu)化指導(dǎo)的可視化界面

為了更好地展示冗余零檢測(cè)結(jié)果，DrZero 提供基于VSCode 的插件來將檢測(cè)結(jié)果可視化.DrZero 的性能報(bào)告分為總覽（metric overview）和按線程劃分的詳細(xì)報(bào)告（detailed metrics）.如圖4 所示，ZeroSpy 用戶界面的總覽頁面分為全局整數(shù)冗余零字節(jié)（total integer redundant byte）以及全局浮點(diǎn)數(shù)冗余零字節(jié)（total floating point redundant byte）兩個(gè)部分，并分別列出了冗余零與總訪問字節(jié).此外，各個(gè)線程所統(tǒng)計(jì)的冗余零數(shù)量以及冗余零比例也可以在此頁面查看.按線程劃分的詳細(xì)報(bào)告則可通過圖4 中“detail”鏈接查看.DrZero 可以分別生成以代碼為中心的分析模式與以數(shù)據(jù)對(duì)象為中心的分析模式報(bào)告，其線程詳細(xì)報(bào)告頁面如圖5 所示.

Fig.4 Metric overview page reported by DrZero GUI圖 4 DrZero 用戶界面報(bào)告的總覽頁面

Fig.5 The detailed report of each thread by DrZero GUI圖 5 DrZero 用戶界面的線程詳細(xì)報(bào)告頁面

1）以代碼為中心的分析模式.如圖5 所示，各個(gè)線程的以代碼為中心模式的報(bào)告頁面分為整數(shù)冗余信息以及浮點(diǎn)冗余信息2 個(gè)部分.對(duì)于以代碼為中心的模式報(bào)告，頁面將會(huì)顯示發(fā)生冗余的程序指令的記錄，且每條記錄是按照檢測(cè)到的冗余字節(jié)數(shù)量從高到低排列.對(duì)于每條記錄，“Redundancy”是該指令的冗余零在所有檢測(cè)到的冗余零中的比例，“l(fā)ocal redundancy”則是該指令的冗余零在所有執(zhí)行該特定指令檢測(cè)到的冗余零中的比例.使用者可以進(jìn)一步點(diǎn)擊每條記錄以顯示更多冗余零信息，包括完全冗余零占比、指令的冗余映射（從最低到最高）.此外，每條記錄會(huì)給出包含源代碼行號(hào)與文件路徑的調(diào)用上下文信息，從而指導(dǎo)開發(fā)者進(jìn)一步的代碼優(yōu)化.

2）以數(shù)據(jù)對(duì)象為中心的分析模式.如圖5 所示，各個(gè)線程的以數(shù)據(jù)對(duì)象為中心的模式報(bào)告頁面同樣分為整數(shù)冗余信息以及浮點(diǎn)冗余信息2 個(gè)部分.對(duì)于以數(shù)據(jù)對(duì)象為中心的模式報(bào)告，頁面將會(huì)顯示發(fā)生冗余的靜態(tài)或動(dòng)態(tài)數(shù)據(jù)對(duì)象的記錄，且每條記錄是按照檢測(cè)到的冗余字節(jié)數(shù)量從高到低排列.對(duì)于靜態(tài)數(shù)據(jù)對(duì)象，每一條記錄都會(huì)顯示對(duì)象的名稱，以幫助使用者在源代碼中定位該靜態(tài)數(shù)據(jù)對(duì)象.對(duì)于動(dòng)態(tài)分配的數(shù)據(jù)對(duì)象，報(bào)告會(huì)提供其調(diào)用上下文信息（CCT info）指示其動(dòng)態(tài)數(shù)據(jù)對(duì)象創(chuàng)建的位置.每條記錄均會(huì)顯示靜態(tài)或動(dòng)態(tài)數(shù)據(jù)對(duì)象的數(shù)據(jù)大小、以字節(jié)為單位的未訪問數(shù)據(jù)比例信息以及冗余零比例信息.此外，使用者還可以點(diǎn)擊“redmap”字樣以跳轉(zhuǎn)到鏈接的數(shù)據(jù)對(duì)象的以字節(jié)為單位的冗余映射熱力圖，如圖6 所示.

Fig.6 The heatmap of the dynamic data object with significant redundant zeros in NPB-IS program圖 6 NPB-IS 程序中報(bào)告大量冗余零的動(dòng)態(tài)數(shù)據(jù)對(duì)象的熱力圖

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

本文使用如表1 所示的x86 和ARM 實(shí)驗(yàn)平臺(tái)對(duì)DrZero 進(jìn)行評(píng)測(cè).為了檢驗(yàn)DrZero 的跨平臺(tái)冗余零檢測(cè)的性能開銷以及檢測(cè)效果，本文選用NASParallel Benchmarks（NPB-3.4）[27]和Rodinia[28]基準(zhǔn)測(cè)試程序集進(jìn)行評(píng)測(cè).其中NPB 基準(zhǔn)測(cè)試使用C CLASS輸入問題規(guī)模.此外，為了評(píng)測(cè)實(shí)際應(yīng)用規(guī)模的冗余零檢測(cè)能力，本文也選用SPEC CPU2017[29]中的NAB生命科學(xué)應(yīng)用（ref 輸入大?。┮约癋otonik3D 計(jì)算電磁學(xué)應(yīng)用（ref 輸入大小）作為案例研究來詳細(xì)講解DrZero 的冗余零檢測(cè)結(jié)果以及優(yōu)化流程.所有程序都使用GCC 11.0-O3-g-fopenmp 編譯，并在單個(gè)CPU 上（x86 平臺(tái)上14 線程，ARM 平臺(tái)上32 線程）并行執(zhí)行.

Table 1 The Detailed Software and Hardware Configurations of Evaluated X86 and ARM Platform表 1 x86 和ARM 評(píng)測(cè)平臺(tái)詳細(xì)軟硬件配置信息

4.2 冗余零識(shí)別效果

DrZero 在x86 和ARM 平臺(tái)上的冗余零檢測(cè)結(jié)果分別如表2 和表3 所示.其中，CC 表示以代碼為中心的冗余零分析模式，其冗余零比例按照所有整數(shù)或浮點(diǎn)數(shù)累計(jì)的冗余零數(shù)量除以總訪問字節(jié)數(shù)得到，CC 數(shù)值越大表明執(zhí)行過程中冗余零相關(guān)的冗余計(jì)算、資源浪費(fèi)越嚴(yán)重；DC 表示以數(shù)據(jù)為中心的冗余零分析模式，其冗余零比例按照所有數(shù)據(jù)對(duì)象中含有的冗余零數(shù)量除以所有數(shù)據(jù)對(duì)象的數(shù)量大小之和得到，DC 數(shù)值越大表明數(shù)據(jù)對(duì)象的稀疏性越高或潛在的數(shù)據(jù)寬度過長問題越嚴(yán)重.此外，在x86 和ARM平臺(tái)上DrZero 使用以代碼為中心（CC）以及以數(shù)據(jù)為中心（DC）的冗余零分析模式的評(píng)測(cè)，結(jié)果對(duì)比分別如圖7、圖8 所示.評(píng)測(cè)結(jié)果證明DrZero 擁有跨平臺(tái)檢測(cè)冗余零導(dǎo)致的軟件低效行為的能力.此外，本文還展示了在x86 平臺(tái)上ZeroSpy 與DrZero 報(bào)告的冗余零比例的比較，如圖7 所示.其中，由于ZeroSpy報(bào)告中冗余零比例在CC 與DC 模式下的計(jì)算方式相同，本文僅展示CC 模式下的冗余零比例檢測(cè)比較.DrZero 在大部分測(cè)試程序中檢測(cè)的冗余零比例與ZeroSpy 相當(dāng).然而，有些程序的冗余零比例則有較明顯的差距（如heartwall）.通過細(xì)致分析發(fā)現(xiàn)，DrZero與ZeroSpy 所檢測(cè)的冗余零數(shù)量差別不大.而由于Dynamorio 不能完全識(shí)別所有的指令，DrZero 可能會(huì)將有些特殊的訪存指令識(shí)別為空指令（nop），從而大大低估了總訪問字節(jié)數(shù).此外，通過圖7 所示的同一代碼在不同平臺(tái)上的冗余零比例對(duì)比，本文發(fā)現(xiàn)雖然某些代碼在不同平臺(tái)上展現(xiàn)一定的冗余零比例的一致性，但仍然有一些基準(zhǔn)測(cè)試程序在同樣的代碼、不同平臺(tái)下的冗余零情況具有較大的差異性（例如LU）.這表明x86 和ARM 指令集對(duì)程序的針對(duì)冗余零的低效行為擁有不同的敏感度.不同指令集之間的冗余零發(fā)散現(xiàn)象需要進(jìn)一步詳細(xì)研究.

Table 2 Fraction of Redundant Zero and Profiling Overheads Reported by DrZero on x86 Platform表 2 DrZero 報(bào)告在x86 平臺(tái)上的冗余零比例以及檢測(cè)分析開銷

Table 3 Fraction of Redundant Zero and Profiling Overheads Reported by DrZero on ARM Platform表 3 DrZero 報(bào)告在ARM 平臺(tái)上的冗余零比例以及檢測(cè)分析開銷

Fig.7 Fraction of integer（INT）and floating point（FP）redundant zeros reported by DrZero CC mode on x86 and ARM platforms圖 7 DrZero CC 模式下分別在x86 和ARM 平臺(tái)上檢測(cè)的整型（INT）以及浮點(diǎn)（FP）類型的冗余零含量

Fig.8 Fraction of integer（INT）and floating point（FP）redundant zeros reported by DrZero DC mode on x86 and ARM platforms圖 8 DrZero DC 模式下分別在x86 和ARM 平臺(tái)上檢測(cè)的整型（INT）以及浮點(diǎn)（FP）類型的冗余零含量

4.3 性能與內(nèi)存開銷

本文評(píng)測(cè)的DrZero 的性能與內(nèi)存開銷如表2 與表3 所示.實(shí)驗(yàn)結(jié)果表明DrZero 在x86 平臺(tái)上的以CC 與DC 性能開銷的中位數(shù)分別為40.32 倍與44.02倍.與ZeroSpy 所報(bào)告的性能開銷的中位數(shù)64.17 倍（CC）與99.52 倍（DC）相比[9]，DrZero 的平均性能開銷分別降低了37.2%和55.8%.此外，在ARM 平臺(tái)，DrZero的CC 和DC 的平均性能開銷僅為14.12 倍和13.40 倍，性能開銷中位數(shù)則僅分別為8.76 倍和10.20 倍.DrZero的性能開銷與常見的二進(jìn)制插裝工具[1-4]持平甚至更低，因此具有良好的應(yīng)用前景.

ZeroSpy（x86 平臺(tái)運(yùn)行）、DrZero-x86（x86 平臺(tái)上運(yùn)行）以及DrZero-ARM（x86 平臺(tái)上運(yùn)行）之間在以代碼為中心的和以數(shù)據(jù)對(duì)象為中心的分析模式下的詳細(xì)性能開銷對(duì)比分別如圖9 與圖10 所示.實(shí)驗(yàn)結(jié)果表明，本文提出的DrZero 在大部分程序下CC 和DC 的性能開銷都優(yōu)于ZeroSpy，并且DrZero 在ARM平臺(tái)上相較在x86 平臺(tái)具有更低的性能開銷.更低的性能開銷主要來自2 個(gè)方面：1）DrZero 調(diào)用上下文采集基于DrCCTProf 實(shí)現(xiàn)，使用性能開銷更低的指令內(nèi)聯(lián)方式來獲取調(diào)用上下文，且DrCCTProf 也針對(duì)ARM 平臺(tái)進(jìn)行高度優(yōu)化，因此DrZero 調(diào)用上下文采集開銷相較依賴Intel Pin 的CCTLib[30]更低；2）DrZero的在線細(xì)粒度緩存跡分析方法可以有效避免冗余且高開銷的頻繁算數(shù)、寄存器狀態(tài)緩存操作，從而帶來可觀的性能提升.

Fig.9 Comparison of the performance overhead of CC mode caused by ZeroSpy,DrZero-x86,and DrZero-ARM圖 9 在CC 模式下ZeroSpy，DrZero-x86，DrZero-ARM 上的性能開銷對(duì)比

如圖11 所示，DrZero 在CC 模式下，在x86 平臺(tái)和ARM 平臺(tái)上內(nèi)存開銷都普遍低于ZeroSpy.然而，如圖12 所示，DrZero 在DC 模式下則相反，其內(nèi)存開銷都普遍高于ZeroSpy.具體情況如表2 所示，DrZero在x86 平臺(tái)上的CC 和DC 的內(nèi)存開銷中位數(shù)分別為2.74 倍和55.68 倍.相較ZeroSpy 所報(bào)告的內(nèi)存開銷中位數(shù)4.47 倍（CC）和6.56 倍（DC），DrZero 在CC 模式下具有更低的內(nèi)存開銷（降低38.7%），而在DC 模式下具有更高的內(nèi)存開銷（升高8.49 倍）.經(jīng)過進(jìn)一步分析，DC 模式下DrCCTProf[26]為了更高的性能，將所有已靜態(tài)、動(dòng)態(tài)分配內(nèi)存的數(shù)據(jù)對(duì)象的所有地址空間通過影射內(nèi)存（shadow memory）方法按字節(jié)映射、存儲(chǔ)其數(shù)據(jù)對(duì)象信息.該方法相較ZeroSpy 依賴的基于Intel Pin 的CCTLib[30]支持的基于樹的實(shí)現(xiàn)擁有更大的內(nèi)存開銷.此外，由于需要DrZero 的DC 模式下的冗余零檢測(cè)需要數(shù)據(jù)對(duì)象的起、止內(nèi)存地址，在擴(kuò)展DrCCTProf 的數(shù)據(jù)對(duì)象信息實(shí)現(xiàn)后，每個(gè)數(shù)據(jù)對(duì)象在每個(gè)影射位需要存儲(chǔ)的信息變?yōu)樵瓉淼? 倍，使得內(nèi)存開銷問題變得更為嚴(yán)重，甚至在ARM 平臺(tái)上NPB FP 會(huì)超出內(nèi)存容量（out of memory，OOM）從而無法采集冗余零信息.因此，未來工作需要提出更加內(nèi)存友好且能保持低開銷的數(shù)據(jù)對(duì)象采集方法來替代DrCCTProf 的影射內(nèi)存方法，以獲取更低的內(nèi)存開銷.

Fig.10 Comparison of the performance overhead of DC mode caused by ZeroSpy,DrZero-x86,and DrZero-ARM圖 10 在DC 模式下ZeroSpy，DrZero-x86，DrZero-ARM 上的性能開銷對(duì)比

Fig.11 Comparison of the memory overhead of CC mode caused by ZeroSpy,DrZero-x86,and DrZero-ARM圖 11 在CC 模式下ZeroSpy，DrZero-x86，DrZero-ARM 上的內(nèi)存開銷對(duì)比

Fig.12 Comparison of the memory overhead of DC mode caused by ZeroSpy,DrZero-x86,and DrZero-ARM圖 12 在DC 模式下ZeroSpy，DrZero-x86，DrZero-ARM 上的內(nèi)存開銷對(duì)比

4.4 NAB 案例研究

NAB 是一個(gè)包含在SPEC CPU2017 基準(zhǔn)測(cè)試套件[29]中的分子建模程序.NAB 是生命科學(xué)模擬領(lǐng)域典型的計(jì)算密集型程序.由于DrZero 報(bào)告的NAB 冗余零情況在x86 和ARM 平臺(tái)上都類似，因此本文僅展示x86 上的冗余零報(bào)告結(jié)果.DrZero 的以代碼為中心的冗余零分析模式檢測(cè)出NAB 包含11.52%的整數(shù)冗余零和6.57%的浮點(diǎn)冗余零.DrZero 報(bào)告NAB中產(chǎn)生最多浮點(diǎn)冗余零的指令信息以及其對(duì)應(yīng)于源代碼中的位置如圖13 所示.

產(chǎn)生冗余零的代碼區(qū)域如圖14 所示，其中*kappa的值頻繁為0.由于完全冗余零的比例很高，本文使用基于條件判斷的方法（如圖15 所示的if/else 語句）來跳過處理冗余零的無用計(jì)算.此外，該優(yōu)化方法還可以通過在進(jìn)入2 個(gè)嵌套循環(huán)之前判斷*kappa的值來進(jìn)一步減少分支開銷.優(yōu)化后的代碼如圖15 所示，類似的優(yōu)化也應(yīng)用于具有類似冗余的其他代碼區(qū)域.經(jīng)過我們的優(yōu)化，NAB 在x86 平臺(tái)實(shí)現(xiàn)9.7%的性能加速，ARM 平臺(tái)上實(shí)現(xiàn)6.08%的性能加速.

Fig.13 The operation with the most significant redundant zeros in NAB reported by DrZero CC mode圖 13 DrZero CC 模式報(bào)告中NAB 產(chǎn)生最多浮點(diǎn)冗余零的指令

4.5 Fotonik3D 案例研究

Fig.14 Code snippet containing the most significant redundant zeros in the egb function of NAB圖 14 NAB 的函數(shù)egb 中包含最多冗余零的程序片段

Fig.15 Code snippet in the egb function of NAB after optimization圖 15 NAB 的函數(shù)egb 優(yōu)化后的程序片段

Fotonik3D 是一個(gè)包含在SPEC CPU2017 基準(zhǔn)測(cè)試套件[29]中的計(jì)算電磁學(xué)程序，其中包含了計(jì)算電磁學(xué)程序中常見的計(jì)算模式.Fotonik3D 使用麥克斯韋方程組的有限差分時(shí)域（FDTD）方法計(jì)算光子波導(dǎo)的傳輸系數(shù).在本文的評(píng)測(cè)中，F(xiàn)otonik3D 使用SPEC套件中提供的ref 輸入數(shù)據(jù)集進(jìn)行評(píng)測(cè).由于Fotonik3D在x86 和ARM 上檢測(cè)的冗余零含量類似，本文僅給出x86 上的DrZero 的冗余零檢測(cè)結(jié)果.DrZero 的以代碼為中心的冗余零檢測(cè)結(jié)果表明，F(xiàn)otonik3D 的執(zhí)行過程中含有8.76%的整型冗余零以及32.30%的浮點(diǎn)冗余零.通過進(jìn)一步分析發(fā)現(xiàn)，其中數(shù)組Ex,Ey,Ez相關(guān)的計(jì)算都含有大量的完全冗余零.具體情況如圖16 中左圖所示，在計(jì)算過程中，數(shù)組Ex,Ey,Ez由大量完全冗余零構(gòu)成，且其中大量x-z平面數(shù)據(jù)往往為0，即該數(shù)組是結(jié)構(gòu)化稀疏的.因此，稀疏數(shù)據(jù)使用稠密數(shù)據(jù)結(jié)構(gòu)以及稠密算法是造成Fotonik3D 應(yīng)用程序中大量完全冗余零及其相關(guān)無用計(jì)算的根本原因.

Fig.16 Large fraction of redundant zeros in Fotonik3D圖 16 Fotonik3D 中含有大量冗余零

為了優(yōu)化并消除冗余零造成的冗余計(jì)算，本文針對(duì)該應(yīng)用數(shù)據(jù)特點(diǎn)對(duì)結(jié)構(gòu)化稀疏數(shù)據(jù)結(jié)構(gòu)以及對(duì)應(yīng)的算法進(jìn)行設(shè)計(jì).如圖16 中右圖所示，原Ex,Ey,Ez數(shù)組的三維數(shù)據(jù)存儲(chǔ)格式由原來的（x,y,z）的存儲(chǔ)順序改為按照（x,z,y）順序存儲(chǔ)，使得x-z平面在內(nèi)存中得以連續(xù)存儲(chǔ)；此外，數(shù)組稀疏存儲(chǔ)格式按照類似稀疏矩陣格式[31]進(jìn)行存儲(chǔ)，即數(shù)組中僅存儲(chǔ)非零x-z平面，并將對(duì)應(yīng)y軸方向上的坐標(biāo)值記錄在下標(biāo)向量Indexy中.經(jīng)過本文所提出的優(yōu)化，F(xiàn)otonik3D 在x86 平臺(tái)上實(shí)現(xiàn)1.76 倍的性能加速，在ARM 平臺(tái)上實(shí)現(xiàn)2.12 倍的性能加速.

5 結(jié)束語

本文提出了一個(gè)針對(duì)冗余零的跨平臺(tái)細(xì)粒度性能分析工具DrZero.為了適配訪存、計(jì)算指令分離的ARM 指令集，本文提出了基于數(shù)據(jù)流分析的數(shù)據(jù)類型推斷方法來自動(dòng)推斷訪存指令讀取內(nèi)存數(shù)據(jù)的數(shù)據(jù)類型.此外，為了更低的性能開銷，本文也提出了在線細(xì)粒度緩存跡分析來檢測(cè)、記錄冗余零相關(guān)的指標(biāo).DrZero 也提供了基于VSCode 的可視化插件來展示冗余零檢測(cè)報(bào)告以及相應(yīng)的優(yōu)化建議.本文的實(shí)驗(yàn)展示了DrZero 跨平臺(tái)檢測(cè)冗余零的能力.DrZero在以代碼、數(shù)據(jù)為中心的冗余零分析中，分別以x86和ARM 平臺(tái)45.31 倍、54.20 倍和14.12 倍、13.40 倍平均性能開銷檢測(cè)冗余零并給出優(yōu)化建議.基于DrZero 給出的性能優(yōu)化指導(dǎo)，本文優(yōu)化的應(yīng)用程序在x86 和ARM 上分別達(dá)到了最高1.76 倍和2.12 倍的性能加速.DrZero 的實(shí)現(xiàn)代碼已經(jīng)開源：https://github.com/buaa-hipo/ZeroSpy-drcctprof.

在未來，我們認(rèn)為還有3 個(gè)問題需要解決.首先，在ARM 平臺(tái)上數(shù)據(jù)對(duì)象信息采集需要過大的內(nèi)存開銷，這導(dǎo)致運(yùn)行使用較多內(nèi)存的應(yīng)用無法使用以數(shù)據(jù)為中心的分析模式進(jìn)行分析，從而錯(cuò)失一些潛在的優(yōu)化機(jī)會(huì).其次，本文發(fā)現(xiàn)的x86 和ARM 平臺(tái)之間同一代碼下冗余零的發(fā)散現(xiàn)象需要進(jìn)一步研究其原因，以便挖掘更多的性能優(yōu)化機(jī)會(huì).最后，希望將來更多的ARM 平臺(tái)（例如天河三號(hào)原型機(jī)中使用的國產(chǎn)ARM 處理器FT2000+）中測(cè)試本文提出的DrZero工具來發(fā)現(xiàn)更多的性能優(yōu)化機(jī)會(huì).

作者貢獻(xiàn)聲明：游心提出研究思路，設(shè)計(jì)實(shí)現(xiàn)研究方案，撰寫論文；楊海龍負(fù)責(zé)論文起草以及最終版本修訂；雷克倫負(fù)責(zé)采集實(shí)驗(yàn)數(shù)據(jù)并實(shí)現(xiàn)可視化界面；孔祥浩負(fù)責(zé)實(shí)現(xiàn)ARM 平臺(tái)部分功能；徐筠、欒鐘治、錢德沛負(fù)責(zé)最終版本修訂.