面向DCU非一致控制流的編譯優(yōu)化

楊小藝，趙榮彩，王洪生，韓林，徐坤坤

面向DCU非一致控制流的編譯優(yōu)化

楊小藝1，2，趙榮彩1，2，王洪生2*，韓林1，2，徐坤坤1，2

（1.鄭州大學(xué) 計(jì)算機(jī)與人工智能學(xué)院，鄭州 450001； 2.國(guó)家超級(jí)計(jì)算鄭州中心，鄭州 450001）（ ? 通信作者電子郵箱whs1814@foxmail.com）

國(guó)產(chǎn)DCU采用單指令多線程（SIMT）的并行執(zhí)行模型，在程序執(zhí)行時(shí)核函數(shù)內(nèi)會(huì)產(chǎn)生非一致控制流，導(dǎo)致線程束中的線程部分只能串行執(zhí)行，即線程束分化。針對(duì)核函數(shù)的性能因線程束分化受到嚴(yán)重制約的問題，提出一種減少線程束分化時(shí)間的編譯優(yōu)化方法——部分控制流合并（PCFM）。首先，通過散度分析找到同構(gòu)且含有大量相同指令和相似指令的可融合發(fā)散區(qū)域；其次，統(tǒng)計(jì)合并后節(jié)省的指令周期百分比，從而評(píng)估可融合發(fā)散區(qū)域的融合盈利；最后，查找對(duì)齊序列，并合并有收益的可融合發(fā)散區(qū)域。在DCU上使用PCFM測(cè)試從圖形處理器（GPU）基準(zhǔn)測(cè)試套件Rodinia和經(jīng)典的排序算法中選擇的測(cè)試用例，實(shí)驗(yàn)結(jié)果表明，PCFM對(duì)測(cè)試用例能夠取得1.146的平均加速比，與分支融合+尾合并方法相比，使用PCFM的加速比平均提高了5.72%?？梢姡岱椒p少線程束分化的效果更好。

DCU；單指令多線程；線程束分化；復(fù)雜控制流；編譯優(yōu)化

0 引言

國(guó)產(chǎn)DCU （Deep Computer Unit）［1］的單指令多線程（Single Instruction Multiple Thread， SIMT）并行執(zhí)行模型采用鎖步的機(jī)制，使一個(gè)線程束在某一時(shí)刻只能有一個(gè)活躍的程序計(jì)數(shù)器（Program Counter， PC）。但是，在很多通用的并行應(yīng)用程序中存在頻繁的分支指令和不規(guī)則的數(shù)據(jù)訪問，導(dǎo)致非一致的控制流行為，此時(shí)線程束中的線程根據(jù)相應(yīng)分支指令的執(zhí)行結(jié)果選擇不同的執(zhí)行路徑。由于線程束中的所有線程在某一周期內(nèi)必須執(zhí)行相同的指令，因此在遇到非一致控制流的情況下線程束中的線程只能串行執(zhí)行，即線程束分化。

圖1為非一致控制流的執(zhí)行示例，圖1（a）是分支轉(zhuǎn)移的控制流結(jié)構(gòu)，其中：每個(gè)方塊代表一個(gè)基本塊，基本塊中每位數(shù)字表示一位掩碼位，代表對(duì)應(yīng)的單指令多數(shù)據(jù)流（Single Instruction Multiple Data， SIMD）通道：“1”表示該通道上有活躍線程執(zhí)行，“0”表示該通道空閑。圖1（b）展示了圖1（a）中的線程在通道中的具體執(zhí)行情況。從圖1（b）中可以看出，當(dāng)出現(xiàn)線程束分化時(shí)，SIMD通道不能滿負(fù)載運(yùn)行，并且線程束中的線程串行執(zhí)行，導(dǎo)致計(jì)算資源的利用率低，嚴(yán)重制約了性能。如在極端情況下，若線程束中的64個(gè)線程均執(zhí)行不同的分支路徑，則理論上性能將降低為原來的1/64。因此，有必要研究減少線程束分化時(shí)間的優(yōu)化技術(shù)。

圖1　非一致控制流執(zhí)行示例

減少線程束分化時(shí)間，就是減少線程串行執(zhí)行的時(shí)間，即壓縮每個(gè)分支單獨(dú)運(yùn)行的時(shí)間。在傳統(tǒng)的編譯優(yōu)化技術(shù)中，減少線程束分化時(shí)間的主要方法是分支融合［2］和尾合并［3］。

圖2　分支融合示例

從圖2～3可以看出，分支融合和尾合并的實(shí)現(xiàn)條件較嚴(yán)苛，只對(duì)簡(jiǎn)單的控制流有一定的優(yōu)化作用；然而，較多通用的并行應(yīng)用程序都有著非常復(fù)雜的控制流，傳統(tǒng)的編譯優(yōu)化技術(shù)并不能較好地解決這些問題。

圖3　尾合并示例

針對(duì)非一致控制流嚴(yán)重制約核函數(shù)性能的問題，本文提出一種減少線程束分化時(shí)間的編譯優(yōu)化方法——部分控制流合并（Partial-Control-Flow-Merging， PCFM）。該方法面向基本塊和區(qū)域，合并發(fā)散控制流中擁有大量相同指令和相似指令的基本塊?基本塊、區(qū)域?區(qū)域。與分支融合和尾合并方法僅提升和下沉相同指令相比，PCFM的適用范圍更廣、融合區(qū)域更大，可以有效減少線程束分化的時(shí)間，提高活躍線程數(shù)。

本文的主要工作如下：

1）分析核函數(shù)中的復(fù)雜控制流，識(shí)別同構(gòu)且含有大量相同指令和相似指令的可融合的發(fā)散區(qū)域。

2）統(tǒng)計(jì)合并后節(jié)省的指令周期百分比，計(jì)算融合盈利，評(píng)估可融合發(fā)散區(qū)域。

3）使用分層序列對(duì)比方法查找對(duì)齊序列，對(duì)有收益的可融合發(fā)散區(qū)域?qū)崿F(xiàn)部分控制流的合并。

1 相關(guān)知識(shí)

異構(gòu)系統(tǒng)架構(gòu)（Heterogeneous System Architecture， HSA）在超級(jí)計(jì)算機(jī)系統(tǒng)中得到了廣泛的使用，我國(guó)自主研發(fā)的新一代超級(jí)計(jì)算機(jī)“嵩山”超級(jí)計(jì)算機(jī)系統(tǒng)采用中央處理器（Central Processing Unit， CPU）+圖形處理器（Graphics Processing Unit， GPU）異構(gòu)體系結(jié)構(gòu)［4］。

1.1　異構(gòu)系統(tǒng)架構(gòu)

異構(gòu)系統(tǒng)架構(gòu)（HSA）是將通用計(jì)算單元（Compute Unit， CU）和專用計(jì)算單元結(jié)合以加快處理速度的一種新興架構(gòu)。異構(gòu)計(jì)算表示在異構(gòu)系統(tǒng)上進(jìn)行并行計(jì)算，異構(gòu)計(jì)算根據(jù)計(jì)算任務(wù)的特點(diǎn)選擇適合的架構(gòu)，使架構(gòu)的優(yōu)勢(shì)得到充分的發(fā)揮，更好地提升性能。在眾核異構(gòu)系統(tǒng)中，CPU+GPU異構(gòu)系統(tǒng)的適用范圍廣且能效比較優(yōu)，已經(jīng)成為了主流架構(gòu)，并在超級(jí)計(jì)算機(jī)系統(tǒng)中得到廣泛的應(yīng)用。

1.2　海光一號(hào)DCU加速器

我國(guó)自主研發(fā)的新一代超級(jí)計(jì)算機(jī)“嵩山”超級(jí)計(jì)算機(jī)系統(tǒng)采用海光一號(hào)CPU+海光一號(hào)DCU加速器的異構(gòu)體系結(jié)構(gòu)?！搬陨健背?jí)計(jì)算機(jī)系統(tǒng)配備的海光一號(hào)DCU加速器是一種通用圖形處理器（General Purpose Graphics Processing Unit， GPGPU），每個(gè)DCU有60個(gè)CU，每個(gè)CU有64個(gè)計(jì)算核心。與CPU相比，DCU部署了大面積的CU，精簡(jiǎn)了用于邏輯判斷、分支跳轉(zhuǎn)和中斷處理等功能的控制單元，因此DCU設(shè)備在面向多數(shù)據(jù)并行計(jì)算的問題和具有高算術(shù)密集度類型的應(yīng)用上有著更強(qiáng)的算力。

1.3　DCU中線程組織情況

DCU對(duì)線程的組織通常分為三級(jí)：線程束（Wavefront）級(jí)、線程塊（Block）級(jí)和線程網(wǎng)格（Grid）級(jí)。線程束是CU中基本的執(zhí)行單元，線程塊由多個(gè)線程（Thread）構(gòu)成，多個(gè)線程塊構(gòu)成了線程網(wǎng)格。在具體執(zhí)行時(shí)，當(dāng)一個(gè)線程塊所在的網(wǎng)格被啟動(dòng)后，該網(wǎng)格中的線程塊將分布在CU中，一旦線程塊被調(diào)度到一個(gè)CU上，線程塊中的線程會(huì)被進(jìn)一步劃分為線程束。DCU采用三級(jí)線程層次結(jié)構(gòu)，從而在線程與線程處理的數(shù)據(jù)元素之間建立映射關(guān)系，圖4展示了DCU的線程層次結(jié)構(gòu)。

在DCU中，一個(gè)線程束由64個(gè)連續(xù)的線程組成，在一個(gè)線程束中，所有的線程按照SIMT方式執(zhí)行，即所有線程都執(zhí)行相同的指令，每個(gè)線程在私有數(shù)據(jù)上操作，線程與線程之間的通信通過共享存儲(chǔ)器和同步操作完成。

1.4　LLVM

LLVM［5］的命名最早起源于底層虛擬機(jī)（Low Level Virtual Machine， LLVM）的首字母縮寫，但是隨著LLVM的發(fā)展，原有的內(nèi)涵發(fā)生了巨大的轉(zhuǎn)變，目前LLVM為模塊化和可重用的編譯器以及工具鏈的集合。

圖5展示了傳統(tǒng)的編譯器架構(gòu)和LLVM架構(gòu)，可以看出，LLVM架構(gòu)是基于傳統(tǒng)的三段式架構(gòu)（前端、優(yōu)化、后端）設(shè)計(jì)的編譯器。與傳統(tǒng)的編譯器架構(gòu)相比，LLVM架構(gòu)可以擴(kuò)展新的前端和后端，支持更多的語言和設(shè)備（如C、Fortran、X86和Power PC等）。LLVM中不同的前端后端使用統(tǒng)一的中間代碼（LLVM Intermediate Representation， LLVM IR）；優(yōu)化階段是一個(gè)通用的階段，因此針對(duì)統(tǒng)一的LLVM IR，可以高度復(fù)用優(yōu)化階段的工作。本文提出的PCFM就是針對(duì)LLVM IR進(jìn)行修改和優(yōu)化，PCFM通過識(shí)別且合并可融合的發(fā)散區(qū)域，減少分支串行執(zhí)行的時(shí)間，從而提升性能。

圖5　傳統(tǒng)編譯器架構(gòu)與LLVM架構(gòu)

2 PCFM

2.1　部分控制流

圖6　復(fù)雜控制流示例

2.2　合并思想

圖7　合并示例

3 在編譯器中的實(shí)現(xiàn)

PCFM主要包括4個(gè)步驟：1）識(shí)別編譯器中間代碼中的可融合發(fā)散區(qū)域；2）評(píng)估可融合發(fā)散區(qū)域；3）若有收益，則查找可融合發(fā)散區(qū)域的對(duì)齊序列；4）合并發(fā)散區(qū)域。

3.1　相關(guān)定義

定義2 簡(jiǎn)單區(qū)域。簡(jiǎn)單區(qū)域是CFG的子圖。僅通過入口邊和出口邊連接剩余的CFG。

滿足以上任一條件的兩個(gè)單入口單出口子圖均可以合并，且不會(huì)給控制流引入額外的分化。

3.2　識(shí)別可融合發(fā)散區(qū)域

通過散度分析［6］識(shí)別程序中的發(fā)散區(qū)域。如圖8所示，若線程束中不同線程分支條件的計(jì)算值不一致，則認(rèn)為線程束在這個(gè)分支條件下是發(fā)散的，對(duì)該分支條件作一個(gè)發(fā)散標(biāo)記。如果分支條件依賴于數(shù)據(jù)或發(fā)散變量，如線程ID［7］，后續(xù)需要對(duì)它進(jìn)行更加復(fù)雜的散度分析［8］。包含一個(gè)發(fā)散分支的最小CFG區(qū)域就是該分支對(duì)應(yīng)的發(fā)散區(qū)域，在找到發(fā)散區(qū)域后根據(jù)定義5找到可融合發(fā)散區(qū)域。

圖8　散度分析流程

3.3　評(píng)估可融合發(fā)散區(qū)域

找到可融合發(fā)散區(qū)域后，通過計(jì)算融合盈利值評(píng)估合并后的性能，根據(jù)評(píng)估的結(jié)果決定是否合并。

融合盈利計(jì)算分為基本塊的融合盈利計(jì)算和區(qū)域的融合盈利計(jì)算。它們的核心思想都是考慮在最佳情況下（即不考慮指令的執(zhí)行順序），兩個(gè)基本塊或兩個(gè)區(qū)域融合后節(jié)省的指令周期百分比。

3.4　查找對(duì)齊序列

為了保證合并后的正確性，PCFM在確保操作相對(duì)順序不變的情況下融合具有相同操作碼和兼容操作數(shù)類型的指令序列，其中操作碼相同、操作數(shù)兼容的指令稱為相似指令。查找對(duì)齊序列［9］是查找在操作相對(duì)順序上保持一致的相似指令序列。若能在可融合發(fā)散區(qū)域中找到最大數(shù)量的對(duì)齊序列進(jìn)行合并，則可以節(jié)省的指令周期百分比最大。

PCFM使用史密斯?沃特曼算法［10］計(jì)算可融合發(fā)散區(qū)域中指令的最佳對(duì)齊方式。在史密斯算法中，相似指令被認(rèn)為是可以對(duì)齊的指令，具有較高延遲的指令對(duì)齊優(yōu)先于具有較低延遲的指令對(duì)齊。此外，該算法對(duì)未對(duì)齊的指令也使用了間歇懲罰以處理它產(chǎn)生的額外分支，并且可融合發(fā)散區(qū)域合并算法與指令對(duì)齊算法之間相互獨(dú)立。

史密斯算法計(jì)算指令對(duì)齊序列分為兩個(gè)步驟：首先建立一個(gè)盈利矩陣，計(jì)算每對(duì)指令的盈利值；其次反向遍歷盈利矩陣，找到指令的最佳對(duì)齊方式。

盈利矩陣的計(jì)算公式如下：

圖9　指令對(duì)齊算法

3.5　合并可融合發(fā)散區(qū)域

得到融合盈利和指令對(duì)齊序列后，合并可融合發(fā)散區(qū)域［11］。指令對(duì)齊序列的合并分為指令對(duì)齊和指令非對(duì)齊這兩種情況，針對(duì)不同的情況采取不同的合并措施。

圖10　復(fù)雜控制流示例1對(duì)齊指令的合并

圖12　退出塊的合并

在基本塊合并的過程中會(huì)引入具有相同后繼節(jié)點(diǎn)的分支、冗余的phi指令，針對(duì)這些情況后續(xù)會(huì)對(duì)它們進(jìn)行消除。

算法1 子圖合并核心算法。

BuildNewBlock（）

else｛

RunPostOptimizations（）

3.6　PCFM的核心算法

圖13展示了復(fù)雜控制流示例1應(yīng)用PCFM后每個(gè)階段的轉(zhuǎn)換情況。

圖13　PCFM的核心算法的應(yīng)用

算法2 PCFM核心算法。

do｛

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

在LLVM 12.0.0版本編譯器中實(shí)現(xiàn)針對(duì)非一致控制流的PCFM，并使用單節(jié)點(diǎn)、單DCU測(cè)試該方法的優(yōu)化效果。

4.1　基準(zhǔn)程序

采用的測(cè)試集取自GPU基準(zhǔn)測(cè)試套件Rodinia［13］和經(jīng)典的排序算法程序。選取了7個(gè)適用于PCFM的測(cè)試用例。

1）BITonic sort （BIT）［14］。排序網(wǎng)絡(luò)中一種比較順序和數(shù)據(jù)無關(guān)的算法，適合并行運(yùn)算。

2）Speckle Reducing Anisotropic Diffusion （SRAD）［13］。取自基準(zhǔn)測(cè)試套件Rodinia，是一種基于偏微分方程的擴(kuò)散算法，用于在不犧牲圖像重要特征的情況下去除圖像中的散斑，廣泛應(yīng)用于超聲波和雷達(dá)成像領(lǐng)域。

3）MergeSort （MS）。建立在歸并操作上的一種有效的排序算法，通過并行的自下而上的合并排序?qū)崿F(xiàn)，其中，合并的核函數(shù)包含依賴于數(shù)據(jù)的非一致性控制流。

4）N-QUeens （NQU）。使用回溯法找到將個(gè)Queens放置在×棋盤上并且不會(huì)相互攻擊的所有方式，使用的核函數(shù)來自GPGPU-sim［15］基準(zhǔn)套件，為15。

5）Partition and Concurrent Merge （PCM）［16］。一種基于奇偶合并排序的并行排序算法。PCM在數(shù)組的每個(gè)位置對(duì)已排序的元素執(zhí)行奇偶合并，導(dǎo)致具有嵌套數(shù)據(jù)依賴分支的循環(huán)，給減少線程束分化算法提供了機(jī)會(huì)。

6）LU-Decomposition （LUD）［13］。取自基準(zhǔn)測(cè)試套件Rodinia中，是矩陣分解的一種，主要應(yīng)用于數(shù)值分析，復(fù)雜控制流減少線程束分化重點(diǎn)評(píng)估lud_perimeter內(nèi)核。

7）DCT quantization （DCT）（https：//docs.nvidia.com/cuda/cuda-samples）。離散余弦變換，把目標(biāo)信號(hào)從復(fù)雜的時(shí)域信號(hào)分解為不同頻率強(qiáng)度的頻域信號(hào)，主要用于數(shù)據(jù)和圖像的壓縮中。

4.2　測(cè)試結(jié)果

選取的7個(gè)測(cè)試用例的內(nèi)核中線程塊的大小都可以調(diào)節(jié)。在某些情況下，線程塊大小對(duì)線程束分化的影響較大，因此在測(cè)試過程中考慮了每個(gè)內(nèi)核在不同塊大小情況下使用PCFM的性能。表1展示了7個(gè)測(cè)試用例分別使用無控制流優(yōu)化、分支融合［2］+尾合并［3］和PCFM的性能對(duì)比，并以無控制流優(yōu)化的性能作為基準(zhǔn)，且無控制流優(yōu)化下所有測(cè)試用例的加速比均為1.000。

從表1可以發(fā)現(xiàn)，PCFM對(duì)選取的所有測(cè)試用例的平均加速比為1.146，分支融合+尾合并對(duì)選取的所有測(cè)試用例的加速比為1.084，因此PCFM的優(yōu)化能力更強(qiáng)，加速比平均提高了5.72%。BIT和SRAD使用PCFM的加速效果最顯著，這是因?yàn)樵贐IT和SRAD中存在大量的可融合發(fā)散區(qū)域，PCFM能夠有效合并這些可融合發(fā)散區(qū)域，大幅提升性能。LUD的散度取決于塊的大小，當(dāng)LUD塊的大小為16、32和64時(shí)會(huì)產(chǎn)生線程束分化，此時(shí)PCFM的優(yōu)化效果明顯優(yōu)于分支融合+尾合并。

表1　不同算法的加速比性能對(duì)比

融合閾值決定了可融合發(fā)散區(qū)域合并的力度。表2為在實(shí)際的基準(zhǔn)測(cè)試中融合閾值對(duì)性能的影響，7個(gè)測(cè)試用例選取的塊大小均為最佳性能下的塊大小?？梢钥闯?，并不是融合閾值越大性能越好，隨著融合閾值的增大，會(huì)損失一部分的合并機(jī)會(huì)，但也不能將它完全置為0，因?yàn)檫@會(huì)導(dǎo)致不考慮融合盈利而將所有的可融合發(fā)散區(qū)域都進(jìn)行合并。

4.3　性能分析

通過測(cè)試發(fā)現(xiàn)PCFM對(duì)性能的提升顯著，本節(jié)使用性能分析工具分析性能提升的原因。

表3展示了7個(gè)測(cè)試用例的歸一化共享內(nèi)存指令數(shù)的情況。BIT和PCM的可融合發(fā)散區(qū)域中包含了大量的共享內(nèi)存指令，PCFM合并這些共享內(nèi)存指令，使性能得到了顯著的提升。DCT沒有使用共享內(nèi)存，所以共享內(nèi)存的指令個(gè)數(shù)為0。共享內(nèi)存指令比大部分的ALU指令的延遲更高，因此合并共享內(nèi)存指令對(duì)性能的提升更為明顯。

表2　不同融合閾值下的加速比

表3　不同算法的歸一化共享內(nèi)存指令數(shù)

5 結(jié)語

本文面向DCU平臺(tái)分析了大量核函數(shù)中存在的復(fù)雜控制流，針對(duì)非一致控制流提出了優(yōu)化方法PCFM，并在編譯器中實(shí)現(xiàn)了該方法。PCFM通過檢測(cè)、評(píng)估和合并不同路徑中的同構(gòu)區(qū)域提升性能，與傳統(tǒng)減少線程束分化的優(yōu)化方法分支融合+尾合并相比，PCFM的適用范圍更廣，減少線程束分化的效果更好。

目前PCFM的優(yōu)化方法只針對(duì)同構(gòu)區(qū)域進(jìn)行合并，在分析核函數(shù)中的復(fù)雜控制流時(shí)，很多不具備同構(gòu)性質(zhì)的區(qū)域也存在合并的可能性，因此在未來的工作中準(zhǔn)備從非同構(gòu)區(qū)域入手，擴(kuò)大方法的適用范圍。

[1] 胡偉方. 面向DCU的多面體編譯優(yōu)化技術(shù)研究［D］. 鄭州：鄭州大學(xué)， 2021： 11-19.（HU W F. Research on DCU-oriented polyhedron compiler optimization technology［D］. Zhengzhou： Zhengzhou University， 2021：11-19.）

[2] HOLZINGER P， REICHENBACH M， FEY D. A new generic HLS approach for heterogeneous computing： on the feasibility of high-level synthesis in HSA-compatible systems［C］// Proceedings of the 18th International Conference on Embedded Computer Systems： Architectures， Modeling， and Simulation. New York： ACM， 2018： 18-27.

[3] CHEN W K， LI B G， GUPTA R. Code compaction of matching single-entry multiple-exit regions［C］// Proceedings of the 2003 International Static Analysis Symposium， LNCS 2694. Berlin： Springer， 2003： 401-417.

[4] COUTINHO B， SAMPAIO D， PEREIRA F M Q， et al. Divergence analysis and optimizations［C］// Proceedings of the 2011 International Conference on Parallel Architectures and Compilation Techniques. Piscataway： IEEE， 2011： 320-329.

[5] LATTNER C， ADVE V. LLVM： a compilation framework for lifelong program analysis & transformation［C］// Proceedings of the 2004 International Symposium on Code Generation and Optimization. Piscataway： IEEE， 2004： 75-86.

[6] HAN T D， ABDELRAHMAN T S. Reducing branch divergence in GPU programs［C］// Proceedings of the 4th Workshop on General Purpose Processing on Graphics Processing Units. New York： ACM， 2011： No.3.

[7] KARRENBERG R， HACK S. Improving performance of OpenCL on CPUs［C］// Proceedings of the 2012 International Conference on Compiler Construction， LNCS 7210. Berlin： Springer， 2012： 1-20.

[8] ROSEMANN J， MOLL S， HACK S. An abstract interpretation for SPMD divergence on reducible control flow graphs［J］. Proceedings of the ACM on Programming Languages and Systems， 2021， 5（POPL）： No.31.

[9] ROCHA R C O， PETOUMENOS P， WANG Z， et al. Function merging by sequence alignment［C］// Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization. Piscataway： IEEE， 2019： 149-163.

[10] SMITH T F， WATERMAN M S. Identification of common molecular subsequences［J］. Journal of Molecular Biology， 1981， 147（1）： 195-197.

[11] ROCHA R C O， PETOUMENOS P， WANG Z， et al. Effective function merging in the SSA form［C］// Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. New York： ACM， 2020： 854-868.

[12] CYTRON R， FERRANTE J， ROSEN B K， et al. Efficiently computing static single assignment form and the control dependence graph［J］. ACM Transactions on Programming Languages and Systems， 1991， 13（4）：451-490.

[13] CHE S， BOYER M， MENG J， et al. Rodinia： a benchmark suite for heterogeneous computing［C］// Proceedings of the 2009 IEEE International Symposium on Workload Characterization. Piscataway： IEEE， 2009： 44-54.

[14] BATCHER K E. Sorting networks and their applications［C］// Proceedings of the 1968 Spring Joint Computer Conference. New York： ACM， 1968： 307-314.

[15] BAKHODA A， YUAN G L， FUNG W W L， et al. Analyzing CUDA workloads using a detailed GPU simulator［C］// Proceedings of the 2009 IEEE International Symposium on Performance Analysis of Systems and Software. Piscataway： IEEE， 2009： 163-174.

[16] HERRUZO E， RUíZ G， BENAVIDES J I， et al. A new parallel sorting algorithm based on odd-even mergesort［C］// Proceedings of the 15th EUROMICRO International Conference on Parallel， Distributed and Network-Based Processing. Piscataway： IEEE， 2007： 18-22.

Compilation optimizations for inconsistent control flow on deep computer unit

YANG Xiaoyi1，2， ZHAO Rongcai1，2， WANG Hongsheng2*， HAN Lin1，2， XU Kunkun1，2

（1，，450001，；2，450001，）

The domestic DCU （Deep Computer Unit） adopts the parallel execution model of Single Instruction Multiple Thread （SIMT）. When the programs are executed， inconsistent control flow is generated in the kernel function， which causes the threads in the warp be executed serially. And that is warp divergence. Aiming at the problem that the performance of the kernel function is severely restricted by warp divergence， a compilation optimization method to reduce the warp divergence time — Partial-Control-Flow-Merging （PCFM） was proposed. Firstly， divergence analysis was performed to find the fusible divergent regions that are isomorphic and contained a large number of same instructions and similar instructions. Then， the fusion profit of the fusible divergent regions was evaluated by counting the percentage of instruction cycles saved after merging. Finally， the alignment sequence was searched， the profitable fusible divergent regions were merged. Some test cases from Graphics Processing Unit （GPU） benchmark suite Rodinia and the classic sorting algorithm were selected to test PCFM on DCU. Experimental results show that PCFM can achieve an average speedup ratio of 1.146 for the test cases. And the speedup of PCFM is increased by 5.72% compared to that of the branch fusion + tail merging method. It can be seen that the proposed method has a better effect on reducing warp divergence.

Deep Computer Unit (DCU); Single Instruction Multiple Thread (SIMT); warp divergence; complex control flow; compilation optimization

This work is partially supported by Major Science and Technology Special Project of Henan Province （221100210600）.

YANG Xiaoyi， born in 1997， M. S. candidate. Her research interests include advanced compilation technology.

ZHAO Rongcai， born in 1957， Ph. D.， professor. His research interests include advanced compilation technology， high-performance computing.

WANG Hongsheng，born in 1994， M. S. His research interests include advanced compilation technology， high-performance computing.

HAN Lin， born in 1978， Ph. D.， associate professor. His research interests include advanced compilation technology， high-performance computing.

XU Kunkun， born in 1991， M. S. candidate. His research interests include advanced compilation technology.

1001-9081（2023）10-3170-08

10.11772/j.issn.1001-9081.2022091338

2022?09?12；

2022?12?21；

河南省重大科技專項(xiàng)（221100210600）。

楊小藝（1997—），女，河南南陽人，碩士研究生，主要研究方向：先進(jìn)編譯技術(shù)； 趙榮彩（1957—），男，河南洛陽人，教授，博士，CCF會(huì)員，主要研究方向：先進(jìn)編譯技術(shù)、高性能計(jì)算； 王洪生（1994—），山東濱州人，碩士，主要研究方向：先進(jìn)編譯技術(shù)、高性能計(jì)算； 韓林（1978—），男，山東臨沂人，副教授，博士，CCF會(huì)員，主要研究方向：先進(jìn)編譯技術(shù)、高性能計(jì)算； 徐坤坤（1991—），男，河南信陽人，碩士研究生，主要研究方向：先進(jìn)編譯技術(shù)。

TP314

A

2022?12?25。