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

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ù)將會導(dǎo)致資源的大量浪費(fèi)[6-8].以往的研究已經(jīng)證明上述低效率的根本原因之一是一些指令和數(shù)據(jù)結(jié)構(gòu)經(jīng)常處理冗余零[9].

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

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

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

1 冗余零的定義與來源

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

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

2）使用不當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也會造成大量的冗余零，從而造成大量的資源浪費(fèi).如圖1 所示，使用稠密數(shù)據(jù)結(jié)構(gòu)與稠密算法對該稀疏數(shù)據(jù)進(jìn)行處理會造成大量的完全冗余零.而如果應(yīng)用稀疏數(shù)據(jù)結(jié)構(gòu)以及對應(yīng)的稀疏算法會大幅度減少存儲、訪存開銷，并避免大量無用的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 檢測以及人工插樁等細(xì)致分析后，該示例代碼中u,v,w這3 個變量常常讀取完全冗余零（0 值），從而進(jìn)一步造成在計(jì)算mu變量值時引入繁重的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ì)算反而會充分利用硬件資源，從而得到較好的性能結(jié)果.因此，若含有大量冗余零的訪存、計(jì)算操作浪費(fèi)了大量資源，基于硬件計(jì)數(shù)器的性能分析工具并不能有效地識別類似冗余零的資源浪費(fèi)導(dǎo)致的軟件低效行為，從而無法給出有效的優(yōu)化建議.

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

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

3 冗余零檢測方法

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

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

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

Fig.3 An overview of the cross-platform redundant zeros detection techniques of DrZero圖 3 DrZero 跨平臺冗余零檢測技術(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)存中的值時才進(jìn)一步基于數(shù)據(jù)流進(jìn)行推斷（行②）.若該指令讀取內(nèi)存值，算法則枚舉所有目標(biāo)寄存器對象，并對每個目標(biāo)寄存器對象查找該基礎(chǔ)代碼塊中在該指令后執(zhí)行的所有指令的源寄存器中是否存在定義-使用關(guān)系（行③～?），若存在，則返回使用目標(biāo)寄存器的指令的類型（行?）.如果上述數(shù)據(jù)流分析過程都沒有找到定義-使用關(guān)系，則返回先前推斷的instr指令類型（行?）.

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

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

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

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

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

在目標(biāo)應(yīng)用程序執(zhí)行時，Dynamorio 會觸發(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ū)存儲目標(biāo)內(nèi)存地址、調(diào)用上下文句柄（通過DrCCTProf[26]獲?。┮约白x取值.例如，圖3 中內(nèi)存讀取操作被推斷為32b 浮點(diǎn)類型（FP32），然后插入指令將相應(yīng)信息緩存到FP32 對應(yīng)的細(xì)粒度緩存跡中以便后續(xù)在線分析.此外，在每個基礎(chǔ)代碼塊級別都需要靜態(tài)推斷各個細(xì)粒度緩存跡將要填充的數(shù)量，并對每個將要填充的細(xì)粒度緩存跡都在基礎(chǔ)代碼塊入口進(jìn)行插樁：

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

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

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

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

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

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

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

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

為了更好地展示冗余零檢測結(jié)果，DrZero 提供基于VSCode 的插件來將檢測結(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）兩個部分，并分別列出了冗余零與總訪問字節(jié).此外，各個線程所統(tǒng)計(jì)的冗余零數(shù)量以及冗余零比例也可以在此頁面查看.按線程劃分的詳細(xì)報(bào)告則可通過圖4 中“detail”鏈接查看.DrZero 可以分別生成以代碼為中心的分析模式與以數(shù)據(jù)對象為中心的分析模式報(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 所示，各個線程的以代碼為中心模式的報(bào)告頁面分為整數(shù)冗余信息以及浮點(diǎn)冗余信息2 個部分.對于以代碼為中心的模式報(bào)告，頁面將會顯示發(fā)生冗余的程序指令的記錄，且每條記錄是按照檢測到的冗余字節(jié)數(shù)量從高到低排列.對于每條記錄，“Redundancy”是該指令的冗余零在所有檢測到的冗余零中的比例，“l(fā)ocal redundancy”則是該指令的冗余零在所有執(zhí)行該特定指令檢測到的冗余零中的比例.使用者可以進(jìn)一步點(diǎn)擊每條記錄以顯示更多冗余零信息，包括完全冗余零占比、指令的冗余映射（從最低到最高）.此外，每條記錄會給出包含源代碼行號與文件路徑的調(diào)用上下文信息，從而指導(dǎo)開發(fā)者進(jìn)一步的代碼優(yōu)化.

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

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

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

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

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

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

4.2 冗余零識別效果

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

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

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 平臺上檢測的整型（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 平臺上檢測的整型（INT）以及浮點(diǎn)（FP）類型的冗余零含量

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

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

ZeroSpy（x86 平臺運(yùn)行）、DrZero-x86（x86 平臺上運(yùn)行）以及DrZero-ARM（x86 平臺上運(yùn)行）之間在以代碼為中心的和以數(shù)據(jù)對象為中心的分析模式下的詳細(xì)性能開銷對比分別如圖9 與圖10 所示.實(shí)驗(yàn)結(jié)果表明，本文提出的DrZero 在大部分程序下CC 和DC 的性能開銷都優(yōu)于ZeroSpy，并且DrZero 在ARM平臺上相較在x86 平臺具有更低的性能開銷.更低的性能開銷主要來自2 個方面：1）DrZero 調(diào)用上下文采集基于DrCCTProf 實(shí)現(xiàn)，使用性能開銷更低的指令內(nèi)聯(lián)方式來獲取調(diào)用上下文，且DrCCTProf 也針對ARM 平臺進(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 上的性能開銷對比

如圖11 所示，DrZero 在CC 模式下，在x86 平臺和ARM 平臺上內(nèi)存開銷都普遍低于ZeroSpy.然而，如圖12 所示，DrZero 在DC 模式下則相反，其內(nèi)存開銷都普遍高于ZeroSpy.具體情況如表2 所示，DrZero在x86 平臺上的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)、動態(tài)分配內(nèi)存的數(shù)據(jù)對象的所有地址空間通過影射內(nèi)存（shadow memory）方法按字節(jié)映射、存儲其數(shù)據(jù)對象信息.該方法相較ZeroSpy 依賴的基于Intel Pin 的CCTLib[30]支持的基于樹的實(shí)現(xiàn)擁有更大的內(nèi)存開銷.此外，由于需要DrZero 的DC 模式下的冗余零檢測需要數(shù)據(jù)對象的起、止內(nèi)存地址，在擴(kuò)展DrCCTProf 的數(shù)據(jù)對象信息實(shí)現(xiàn)后，每個數(shù)據(jù)對象在每個影射位需要存儲的信息變?yōu)樵瓉淼? 倍，使得內(nèi)存開銷問題變得更為嚴(yán)重，甚至在ARM 平臺上NPB FP 會超出內(nèi)存容量（out of memory，OOM）從而無法采集冗余零信息.因此，未來工作需要提出更加內(nèi)存友好且能保持低開銷的數(shù)據(jù)對象采集方法來替代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 上的性能開銷對比

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)存開銷對比

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)存開銷對比

4.4 NAB 案例研究

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

產(chǎn)生冗余零的代碼區(qū)域如圖14 所示，其中*kappa的值頻繁為0.由于完全冗余零的比例很高，本文使用基于條件判斷的方法（如圖15 所示的if/else 語句）來跳過處理冗余零的無用計(jì)算.此外，該優(yōu)化方法還可以通過在進(jìn)入2 個嵌套循環(huán)之前判斷*kappa的值來進(jìn)一步減少分支開銷.優(yōu)化后的代碼如圖15 所示，類似的優(yōu)化也應(yīng)用于具有類似冗余的其他代碼區(qū)域.經(jīng)過我們的優(yōu)化，NAB 在x86 平臺實(shí)現(xiàn)9.7%的性能加速，ARM 平臺上實(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 是一個包含在SPEC CPU2017 基準(zhǔn)測試套件[29]中的計(jì)算電磁學(xué)程序，其中包含了計(jì)算電磁學(xué)程序中常見的計(jì)算模式.Fotonik3D 使用麥克斯韋方程組的有限差分時域（FDTD）方法計(jì)算光子波導(dǎo)的傳輸系數(shù).在本文的評測中，F(xiàn)otonik3D 使用SPEC套件中提供的ref 輸入數(shù)據(jù)集進(jìn)行評測.由于Fotonik3D在x86 和ARM 上檢測的冗余零含量類似，本文僅給出x86 上的DrZero 的冗余零檢測結(jié)果.DrZero 的以代碼為中心的冗余零檢測結(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ì)算，本文針對該應(yīng)用數(shù)據(jù)特點(diǎn)對結(jié)構(gòu)化稀疏數(shù)據(jù)結(jié)構(gòu)以及對應(yīng)的算法進(jìn)行設(shè)計(jì).如圖16 中右圖所示，原Ex,Ey,Ez數(shù)組的三維數(shù)據(jù)存儲格式由原來的（x,y,z）的存儲順序改為按照（x,z,y）順序存儲，使得x-z平面在內(nèi)存中得以連續(xù)存儲；此外，數(shù)組稀疏存儲格式按照類似稀疏矩陣格式[31]進(jìn)行存儲，即數(shù)組中僅存儲非零x-z平面，并將對應(yīng)y軸方向上的坐標(biāo)值記錄在下標(biāo)向量Indexy中.經(jīng)過本文所提出的優(yōu)化，F(xiàn)otonik3D 在x86 平臺上實(shí)現(xiàn)1.76 倍的性能加速，在ARM 平臺上實(shí)現(xiàn)2.12 倍的性能加速.

5 結(jié)束語

本文提出了一個針對冗余零的跨平臺細(xì)粒度性能分析工具DrZero.為了適配訪存、計(jì)算指令分離的ARM 指令集，本文提出了基于數(shù)據(jù)流分析的數(shù)據(jù)類型推斷方法來自動推斷訪存指令讀取內(nèi)存數(shù)據(jù)的數(shù)據(jù)類型.此外，為了更低的性能開銷，本文也提出了在線細(xì)粒度緩存跡分析來檢測、記錄冗余零相關(guān)的指標(biāo).DrZero 也提供了基于VSCode 的可視化插件來展示冗余零檢測報(bào)告以及相應(yīng)的優(yōu)化建議.本文的實(shí)驗(yàn)展示了DrZero 跨平臺檢測冗余零的能力.DrZero在以代碼、數(shù)據(jù)為中心的冗余零分析中，分別以x86和ARM 平臺45.31 倍、54.20 倍和14.12 倍、13.40 倍平均性能開銷檢測冗余零并給出優(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 個問題需要解決.首先，在ARM 平臺上數(shù)據(jù)對象信息采集需要過大的內(nèi)存開銷，這導(dǎo)致運(yùn)行使用較多內(nèi)存的應(yīng)用無法使用以數(shù)據(jù)為中心的分析模式進(jìn)行分析，從而錯失一些潛在的優(yōu)化機(jī)會.其次，本文發(fā)現(xiàn)的x86 和ARM 平臺之間同一代碼下冗余零的發(fā)散現(xiàn)象需要進(jìn)一步研究其原因，以便挖掘更多的性能優(yōu)化機(jī)會.最后，希望將來更多的ARM 平臺（例如天河三號原型機(jī)中使用的國產(chǎn)ARM 處理器FT2000+）中測試本文提出的DrZero工具來發(fā)現(xiàn)更多的性能優(yōu)化機(jī)會.

作者貢獻(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 平臺部分功能；徐筠、欒鐘治、錢德沛負(fù)責(zé)最終版本修訂.