BWDSP10x上地址和數(shù)據(jù)謂詞執(zhí)行的編譯優(yōu)化①

樊永朝, 鄭啟龍, 耿 銳, 王向前, 王 昊

1(中國科學(xué)技術(shù)大學(xué) 安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室, 合肥 230027)2(中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 合肥 230027)3(中國電子科技集團(tuán)公司 第三十八研究所, 合肥 230088)

BWDSP10x上地址和數(shù)據(jù)謂詞執(zhí)行的編譯優(yōu)化①

樊永朝1,2, 鄭啟龍1,2, 耿 銳3, 王向前3, 王 昊3

1(中國科學(xué)技術(shù)大學(xué) 安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室, 合肥 230027)2(中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 合肥 230027)3(中國電子科技集團(tuán)公司 第三十八研究所, 合肥 230088)

傳統(tǒng)的謂詞優(yōu)化技術(shù)是在馮·諾伊曼體系結(jié)構(gòu)計(jì)算機(jī)上實(shí)施的, 僅對(duì)數(shù)據(jù)流進(jìn)行優(yōu)化, 并沒有考慮哈佛體系結(jié)構(gòu)下指令和數(shù)據(jù)分開的情況. BWDSP10x是指令和數(shù)據(jù)分開的哈佛體系結(jié)構(gòu), 它支持超長指令字, 不僅提供了對(duì)數(shù)據(jù)謂詞執(zhí)行的支持也提供了對(duì)地址謂詞執(zhí)行的支持. 特此提出了一種在區(qū)域上對(duì)兩種謂詞模式優(yōu)化支持的方法, 在進(jìn)行兩種比較之前, 通過判斷比較操作的兩個(gè)操作數(shù)類型來分別實(shí)施兩種模式的謂詞優(yōu)化, 使得對(duì)地址的比較不用傳輸?shù)酵ㄓ眉拇嫫髦? 實(shí)驗(yàn)結(jié)果表明該優(yōu)化方法能顯著地節(jié)省CPU的時(shí)間和帶寬, 大大減少了分支指令, 使程序性能提高了28.4%.

地址謂詞執(zhí)行; 數(shù)據(jù)謂詞執(zhí)行; 區(qū)域; 編譯優(yōu)化

指令在執(zhí)行中要經(jīng)歷取指、譯碼、執(zhí)行、存取等階段. 現(xiàn)在的處理器中大多都有多個(gè)執(zhí)行單元, 從而能使上述過程實(shí)現(xiàn)指令流水, 達(dá)到指令級(jí)并行的效果.但由于程序中條件分支的存在, 使指令流水停頓, 減弱了指令流水的效果. 為了減弱條件分支對(duì)指令流水的影響, 傳統(tǒng)的優(yōu)化方法有軟件流水[1]、指令調(diào)度[2]、分支預(yù)測[3]等, 軟件流水和指令調(diào)度通過循環(huán)展開,調(diào)整指令之間的次序來減弱分支指令對(duì)指令流水的影響, 但沒有從根本上消除條件分支. 分支預(yù)測使用分支預(yù)測器來猜測哪條分支將會(huì)被執(zhí)行, 它的缺點(diǎn)是當(dāng)發(fā)生分支誤預(yù)測時(shí), 流水線的性能大大降低.

解決條件分支的另一種方法是謂詞執(zhí)行[4], 利用條件轉(zhuǎn)換[5]使所有可能的分支路徑都被編碼, 在實(shí)際執(zhí)行中使一些指令執(zhí)行, 另一些指令不執(zhí)行. 謂詞執(zhí)行的基本思想是每條指令和一個(gè)謂詞相關(guān), 只有當(dāng)謂詞為真時(shí)指令才被執(zhí)行, 這樣便消除了條件分支, 使被條件分支分割的多個(gè)基本塊合為一個(gè)基本塊, 雖然增加了基本塊的長度, 但和減少的分支停頓相比這點(diǎn)代價(jià)很小. 傳統(tǒng)的謂詞優(yōu)化[6]僅僅針對(duì)馮·諾伊曼體系結(jié)構(gòu), 對(duì)地址和數(shù)據(jù)的謂詞優(yōu)化都放在通用寄存器中比較, 而BWDSP10x的哈佛體系結(jié)構(gòu)指令和數(shù)據(jù)是分開的, 地址和數(shù)據(jù)的比較操作都采用一種模式不能充分利用處理器的資源.

本文基于BWDSP10x體系結(jié)構(gòu)提出了一種對(duì)地址和數(shù)據(jù)比較都進(jìn)行謂詞優(yōu)化的方法, 對(duì)條件分支中地址和數(shù)據(jù)的比較分開進(jìn)行, 減少了不必要的數(shù)據(jù)傳輸, 提高了帶寬利用率, 使流水線停頓的次數(shù)大大減少, 從而提高了程序性能.

1 編譯器框架

1.1 BWDSP10x體系結(jié)構(gòu)

BWDSP10x處理器[7]是一款32位靜態(tài)超標(biāo)量處理器, 采用16發(fā)射、SIMD(單指令流, 多數(shù)據(jù)流)架構(gòu). BWDSP10x處理器內(nèi)核有4個(gè)運(yùn)算宏, 每個(gè)運(yùn)算宏由8個(gè)算術(shù)邏輯單元、4個(gè)乘法器、2個(gè)移位器、1個(gè)超算器、1個(gè)8位數(shù)據(jù)謂詞寄存器以及1個(gè)通用寄存組組成. 運(yùn)算宏之間通過宏間傳輸總線通信. 內(nèi)部運(yùn)算單元和存儲(chǔ)器之間的數(shù)據(jù)交換所需的存儲(chǔ)器地址主要是通過內(nèi)部若干個(gè)地址發(fā)生器來提供. BWDSP10x內(nèi)部有三個(gè)地址發(fā)生器(U/V/W), 地址發(fā)生器由三部分構(gòu)成: 瞬時(shí)地址運(yùn)算器、地址更新運(yùn)算器和16個(gè)寄存器組構(gòu)成的地址寄存器組, 每個(gè)地址寄存器位寬為32位.

1.2 BWDSP10x編譯器謂詞優(yōu)化框架

BWDSP10x的編譯器基于開源編譯器OPEN64, OPEN64前端是GCC, 后端構(gòu)建在WHIRL中間語言的基礎(chǔ)上, OPEN64是為Intel IA64提供編譯優(yōu)化支持的[5]. BWDSP10x的謂詞模塊在后端代碼生成(CG)階段, 在CG階段開始后, 以中間語言VL WHIRL作為輸入, 經(jīng)過CG expansion、生成region tree信息后開始以區(qū)域[8]為單元執(zhí)行謂詞優(yōu)化. 圖1描述了BWDSP10x謂詞執(zhí)行優(yōu)化框架, 其中謂詞定義指令生成、謂詞執(zhí)行指令生成構(gòu)成了本文謂詞優(yōu)化算法.

2 添加機(jī)器描述

現(xiàn)階段為了支持多種目標(biāo)體系結(jié)構(gòu), 許多編譯器基礎(chǔ)設(shè)施都采用了機(jī)器描述[9]的方式來對(duì)目標(biāo)機(jī)的資源進(jìn)行描述, OPEN64也是如此. 為了提供對(duì)BWDSP10x謂詞的支持, 則需要添加BWDSP10x謂詞指令的描述. BWDSP10x謂詞部分的機(jī)器描述包括地址謂詞U/V/W描述和數(shù)據(jù)謂詞CPred描述兩部分, 它們主要由以下幾部分構(gòu)成:

圖1 BWDSP10x謂詞執(zhí)行優(yōu)化框架

3 區(qū)域信息生成

區(qū)域是一個(gè)流圖中只有單個(gè)入口結(jié)點(diǎn)的部分, 用區(qū)域可以很方便地進(jìn)行控制流優(yōu)化. 區(qū)域有5種, 分別是: 根區(qū)域、多入口多出口區(qū)域、單入口多出口區(qū)域、不可規(guī)約區(qū)域、循環(huán)區(qū)域, 其中根區(qū)域是區(qū)域樹最外層區(qū)域[10]. 一個(gè)自然循環(huán)就是一個(gè)區(qū)域, 但區(qū)域不一定包含一條回邊. 為了構(gòu)造區(qū)域, 必須找到自然循環(huán), 然后分析它的區(qū)域結(jié)構(gòu). 任何兩個(gè)自然循環(huán)要么不相交, 要么一個(gè)循環(huán)嵌套在另一個(gè)循環(huán)里. 沒有循環(huán)的基本塊本身就是一個(gè)區(qū)域. 一個(gè)程序的流圖分為可規(guī)約流圖和不可規(guī)約流圖. 對(duì)于可規(guī)約流圖, 把每個(gè)基本塊當(dāng)做一個(gè)區(qū)域, 把循環(huán)從內(nèi)到外排序, 對(duì)每一個(gè)自然循環(huán)構(gòu)造循環(huán)體區(qū)域和循環(huán)區(qū)域, 完成對(duì)循環(huán)的規(guī)約, 規(guī)約完成后所有的循環(huán)都被規(guī)約為單個(gè)結(jié)點(diǎn). 規(guī)約過程: 首先處理自然循環(huán), 直到流圖中包含環(huán)沒有回邊, 剩下不可規(guī)約的部分. 不可規(guī)約的部分盡管可以用結(jié)點(diǎn)分割的技術(shù)成為可規(guī)約的, 但由于時(shí)間復(fù)雜度較高, 本文不對(duì)此進(jìn)行處理, 但必須把用強(qiáng)連通分量算法[11]找出不可規(guī)約區(qū)域, 供謂詞優(yōu)化階段優(yōu)化使用. 對(duì)于重疊的循環(huán),考慮到時(shí)間復(fù)雜度, 不需要進(jìn)一步優(yōu)化. 最后, 對(duì)所有的區(qū)域進(jìn)行分解提高目標(biāo)機(jī)資源利用效率. 構(gòu)建區(qū)域樹算法偽代碼, 如圖2所示.

圖2 區(qū)域樹算法

算法輸入為函數(shù)中的第一個(gè)基本塊first_bb, 輸出為一個(gè)區(qū)域樹, 樹上每一個(gè)結(jié)點(diǎn)代表一個(gè)區(qū)域. 首先創(chuàng)建基本塊結(jié)點(diǎn)映射, 把每個(gè)基本塊映射到相對(duì)應(yīng)的區(qū)域控制流結(jié)點(diǎn)上, 然后增加區(qū)域樹的根結(jié)點(diǎn), 根據(jù)全局?jǐn)?shù)據(jù)流圖構(gòu)建局部區(qū)域控制流圖, 在構(gòu)建區(qū)域控制流圖的同時(shí)計(jì)算相應(yīng)的入口和出口信息, 最后處理循環(huán)和不可規(guī)約的部分以及重疊的非自然循環(huán).

在構(gòu)建區(qū)域樹算法中處理循環(huán)和不可規(guī)約部分是在區(qū)域控制流圖中進(jìn)行的, 先找出環(huán), 然后計(jì)算關(guān)鍵邊和回邊找到強(qiáng)連通分量, 構(gòu)建循環(huán)區(qū)域和不可規(guī)約區(qū)域. 處理循環(huán)和不可規(guī)約部分算法偽代碼如圖3所示.

圖3 處理循環(huán)和不可規(guī)約算法

盡管區(qū)域越大越好, 但如果區(qū)域超出了目標(biāo)機(jī)的資源約束, 則會(huì)導(dǎo)致程序執(zhí)行效率[6]降低. 因此, 區(qū)域樹算法最后一步是按照目標(biāo)機(jī)的體系結(jié)構(gòu)對(duì)所有的區(qū)域進(jìn)行分解, 把所有區(qū)域分解為較小的區(qū)域, 以最大利用目標(biāo)機(jī)資源. 區(qū)域最終被分解為單入口多出口區(qū)域供后面謂詞優(yōu)化階段使用. 區(qū)域分解算法偽代碼如圖4所示.

圖4 區(qū)域分解算法

4 謂詞優(yōu)化算法

BWDSP10x和IA64一樣也提供了謂詞指令, 但BWDSP10x和IA64有兩點(diǎn)區(qū)別: 一、BWDSP10x是指令和數(shù)據(jù)分開的哈佛體系結(jié)構(gòu), 而IA64是傳統(tǒng)的馮·諾伊曼體系結(jié)構(gòu), 因此BWDSP10x支持U/V/W地址謂詞和CPred數(shù)據(jù)謂詞兩種模式; 二、IA64支持全謂詞執(zhí)行技術(shù), 在指令執(zhí)行前利用每條指令的限定謂詞來決定此指令是否執(zhí)行, 不需要單獨(dú)的謂詞執(zhí)行指令,而BWDSP10x只支持部分謂詞, 需要單獨(dú)的謂詞執(zhí)行指令.

BWDSP10x的地址謂詞寄存器有16個(gè), 當(dāng)做謂詞寄存器使用時(shí), 可使用其中的8位. 數(shù)據(jù)謂詞寄存器即每一個(gè)執(zhí)行宏上的一個(gè)獨(dú)立的8位CPred寄存器. U/V/W地址模式中把兩個(gè)地址比較結(jié)果放在地址發(fā)生器U/V/W中的一個(gè)地址寄存器的一位中, 此時(shí)地址寄存器中存的是立即數(shù). CPred數(shù)據(jù)模式是把兩個(gè)數(shù)據(jù)比較的結(jié)果放在一個(gè)8位謂詞寄存器CPred中的一位中,此時(shí)CPred中存的也是立即數(shù).

BWDSP10x兩種謂詞指令分別支持兩種不同的謂詞模式. 每一種指令都定義了謂詞定義指令、謂詞執(zhí)行指令. 其中U/V/W模式還定義了謂詞傳輸指令, 其原因是謂詞定義指令的結(jié)果和源操作數(shù)都是地址, 而條件分支中的兩個(gè)操作數(shù)之一可能是立即數(shù)或數(shù)據(jù),需要把其傳輸?shù)降刂芳拇嫫髦? CPred模式中的謂詞定義指令中的兩個(gè)源操作數(shù)都是數(shù)據(jù), 比較操作可以在通用寄存器中進(jìn)行, 因此不需要謂詞傳輸指令.

4.1 謂詞定義指令生成

謂詞定義指令生成是指把編譯器中間代碼生成的比較指令替換為謂詞指令的過程.

BWDSP10x的U/V/W地址謂詞定義指令中的U地址指令形式如表1所示, V/W地址形式類似, 這些指令均為單字指令. 其中, s、m、n為地址謂詞寄存器的編號(hào). 指令含義為根據(jù)Um和Un的比較結(jié)果對(duì)Us的第K位置位. 若比較結(jié)果為真, Us第[k]位置為1, 否則置為0, 0＜=k＜8. 本指令由U地址發(fā)生器中的“加法/移位”部件執(zhí)行.

BWDSP10x的CPred數(shù)據(jù)謂詞定義指令中的指令形式如表2所示, 這些指令均為雙字指令. 其中, x、y、z、t為運(yùn)算宏的編號(hào), m, n為通用寄存器編號(hào).指令含義為在四個(gè)運(yùn)算宏之一內(nèi)根據(jù)Rm和Rn的比較結(jié)果對(duì)CPred的第k位置位. 若比較結(jié)果為真, CPred第k位置為1, 否則置為0, 0＜=k＜8. 第k個(gè)ALU控制CPred寄存器的第k位, 本指令由第k個(gè)ALU執(zhí)行.

表1 U/V/W地址謂詞定義指令形式

表2 CPred數(shù)據(jù)謂詞定義指令形式

由上可知, 在生成謂詞定義指令時(shí)需要對(duì)謂詞寄存器每一位進(jìn)行編號(hào)確定運(yùn)算單元比較結(jié)果置位的位置. 兩種謂詞寄存器的謂詞定義指令比較結(jié)果安排方式一樣. 謂詞寄存器的每一位表示一個(gè)比較條件, 8位代表在一個(gè)函數(shù)中, 一個(gè)if語句中最多能有8個(gè)比較條件或者最多有8層的if-else嵌套, 在一個(gè)if-else中每個(gè)條件置位謂詞寄存器的一位. 置位的順序從第一個(gè)比較條件開始置位謂詞寄存器最低位, 根據(jù)BWDSP10x指令集謂詞執(zhí)行指令, 當(dāng)k為0時(shí)指令必須執(zhí)行, 因此謂詞寄存器最低位從1開始標(biāo)號(hào), 而不是0. 謂詞定義比較結(jié)果安排示意如表3所示.

表3 謂詞定義中比較結(jié)果安排

謂詞定義指令生成的算法流程和算法偽代碼分別如圖5和圖6所示.

在生成謂詞定義指令時(shí), 在找到分支指令后, 判斷分支指令里比較的兩個(gè)操作數(shù)之一是否為地址來決定采用哪一種謂詞模式. 如果兩個(gè)操作數(shù)均為數(shù)據(jù)則生成CPred謂詞定義指令, 若其中一個(gè)操作數(shù)為地址另一個(gè)操作數(shù)為數(shù)據(jù), 則把為數(shù)據(jù)操作數(shù)傳輸?shù)降刂芳拇嫫髦? 生成U/V/W謂詞定義指令. 在生成U/V/W謂詞定義指令和CPred謂詞定義指令之前要分別初始化一個(gè)虛擬謂詞寄存器u0和對(duì)應(yīng)執(zhí)行宏的CPred, 并分別對(duì)兩種模式條件分支進(jìn)行計(jì)數(shù), 計(jì)數(shù)變量為全局變量ak、ck, 初值設(shè)為0, ak、ck同時(shí)指明了要置位的謂詞寄存器位編號(hào), 選擇哪個(gè)執(zhí)行宏上的cpred寄存器要根據(jù)操作數(shù)的執(zhí)行宏來決定,當(dāng)ak、ck、以及要使用的謂詞寄存器確定后就可以插入如上的謂詞定義指令.

4.2 謂詞執(zhí)行指令生成

在謂詞定義指令生成后開始謂詞執(zhí)行指令的生成,謂詞執(zhí)行指令的生成過程也是把跳轉(zhuǎn)分支合并為單個(gè)基本塊的過程. 在IA64中這是通過在跳轉(zhuǎn)目標(biāo)塊前加上限定謂詞實(shí)現(xiàn)的, 而在BWDSP10x采用的是生成謂詞執(zhí)行指令的方式實(shí)現(xiàn).

BWDSP10x的U/V/W地址謂詞執(zhí)行指令中的U地址指令形式如表4所示, V/W地址格式類似, 這些指令均為雙字指令. 指令判斷Um對(duì)應(yīng)K1為1位置的數(shù)據(jù)是否等于常數(shù)C1對(duì)應(yīng)K1為1的位置的數(shù)據(jù), 若判斷結(jié)果為真, 則執(zhí)行當(dāng)前指令行中該指令后的前n條指令, 包括所有指令類型.

BWDSP10x的CPred數(shù)據(jù)謂詞執(zhí)行指令中的指令形式如表5所示, 這些指令均為雙字指令. 指令判斷CPred對(duì)應(yīng)K1為1位置的數(shù)據(jù)是否等于常數(shù)C1對(duì)應(yīng)K1為1的位置的數(shù)據(jù), 若判斷結(jié)果為真, 則執(zhí)行當(dāng)前指令行中該指令后的前n條指令, 只控制這些指令中受CPred控制的指令. 本指令不能控制非運(yùn)算指令、宏間傳輸指令、訪存指令(無論讀或?qū)?等執(zhí)行單元不在宏內(nèi)的指令.

圖5 謂詞定義指令生成算法流程圖

表4 U/V/W地址謂詞執(zhí)行指令形式

圖6 謂詞定義指令生成算法偽代碼

表5 CPred數(shù)據(jù)謂詞執(zhí)行指令格式

一個(gè)常見的帶多個(gè)條件分支的區(qū)域通過謂詞執(zhí)行技術(shù)規(guī)約過程如圖7. 首先過程1中基本塊2, 3合并到基本塊1中, 7合并到6中, 完成一次規(guī)約后刪除條件分支, 轉(zhuǎn)變?yōu)檫^程2, 再進(jìn)行規(guī)約刪除條件分支最終轉(zhuǎn)換為過程3. 算法流程如圖8, 具體算法偽代碼如圖9所示.

圖7 條件分支轉(zhuǎn)換規(guī)約過程

圖8 條件轉(zhuǎn)換規(guī)約算法流程圖

圖9 謂詞執(zhí)行指令生成算法偽代碼

算法首先查找前面生成的謂詞定義指令, 根據(jù)謂詞定義指令的操作碼決定是生成U/V/W地址謂詞執(zhí)行指令還是CPred數(shù)據(jù)謂詞執(zhí)行指令. 然后獲得當(dāng)前謂詞定義指令中的謂詞寄存器被置位的k和常量2^(result_k-1)相比較得到條件比較結(jié)果對(duì)跳轉(zhuǎn)目標(biāo)或落入分支設(shè)置限定謂詞, 即生成謂詞執(zhí)行指令. 在生成CPred數(shù)據(jù)謂詞執(zhí)行指令時(shí), 需要把設(shè)置限定謂詞的基本塊中不受CPred控制的指令移動(dòng)到謂詞執(zhí)行指令的前面; 而且, 由于在CPred數(shù)據(jù)謂詞定義指令生成時(shí)已經(jīng)確定了執(zhí)行宏, 此時(shí)不再需要重新確定執(zhí)行宏.

5 實(shí)例分析

常見的地址比較條件分支程序優(yōu)化前和優(yōu)化后對(duì)比如圖10所示.

常見的數(shù)據(jù)比較條件分支程序優(yōu)化前和優(yōu)化后對(duì)比如圖11所示.

圖10 地址比較條件分支優(yōu)化前后對(duì)比

圖11 數(shù)據(jù)比較條件分支優(yōu)化前后對(duì)比

實(shí)驗(yàn)選取了SPEC CPU 2006 測試項(xiàng)目中的五個(gè)程序來驗(yàn)證在打開謂詞優(yōu)化選項(xiàng)后的優(yōu)化結(jié)果. 這五個(gè)程序分別是壓縮程序bzip2、組合優(yōu)化mcf、尋路算法astar、有限元分析dealII、影像光線追蹤povray, 這些程序在DSP領(lǐng)域應(yīng)用很廣泛.

這五種程序單獨(dú)實(shí)施地址謂詞優(yōu)化結(jié)果如表6所示.

表6 實(shí)施地址謂詞優(yōu)化前后對(duì)比

這五種程序單獨(dú)實(shí)施數(shù)據(jù)謂詞優(yōu)化結(jié)果如表7所示.

表7 實(shí)施數(shù)據(jù)謂詞優(yōu)化前后對(duì)比

這五種程序同時(shí)實(shí)施兩種謂詞優(yōu)化結(jié)果如表8所示.

表8 同時(shí)實(shí)施兩種謂詞優(yōu)化前后對(duì)比

從以上實(shí)驗(yàn)結(jié)果可以看出, 表6中單獨(dú)實(shí)施地址謂詞優(yōu)化程序性能平均提升了17%; 表7中單獨(dú)實(shí)施數(shù)據(jù)謂詞優(yōu)化程序性能平均提升了10%; 從表6和表7的結(jié)果可以看出, 由于增加了地址謂詞的優(yōu)化, 使對(duì)地址的比較不用傳輸?shù)酵ㄓ眉拇嫫髦性龠M(jìn)行比較, 節(jié)省了時(shí)間和帶寬, 比傳統(tǒng)的單一謂詞優(yōu)化模式性能有很大提升; 從表8可以看出尋路算法和影像光線追蹤優(yōu)化效果要比壓縮程序好, 說明謂詞優(yōu)化技術(shù)特別適用于地址比較條件分支和數(shù)據(jù)比較條件分支較多的程序, 表8中同時(shí)實(shí)施兩種謂詞優(yōu)化程序性能平均提升了28.4%, 說明實(shí)施謂詞優(yōu)化后消除了一部分分支指令減少了流水線停頓使指令流水效率大大提高了.

6 結(jié)語

本文針對(duì)BWDSP10x體系結(jié)構(gòu)提供的謂詞指令,提出了一種條件分支轉(zhuǎn)換的方法. 通過生成謂詞定義指令和謂詞生成指令, 使源程序的條件分支基本塊可以合并為一個(gè)基本塊, 充分提高了程序的并行性. 這種方法適合指令和數(shù)據(jù)分開的哈佛結(jié)構(gòu), 能對(duì)地址和數(shù)據(jù)的條件分支優(yōu)化分開進(jìn)行, 進(jìn)一步提高了程序的效率. 本文只對(duì)兩種謂詞模式的生成做了研究, 接下來還應(yīng)在生成的謂詞指令的基礎(chǔ)上進(jìn)行各種數(shù)據(jù)流優(yōu)化分析.

1 馮玉謙.基于多簇VLIW軟件流水及相關(guān)編譯優(yōu)化技術(shù)研究[碩士學(xué)位論文].合肥:中國科學(xué)技術(shù)大學(xué),2013.

2 付和萍.基于超長指令字的全局無環(huán)指令調(diào)度和復(fù)數(shù)乘法優(yōu)化設(shè)計(jì)[碩士學(xué)位論文].合肥:中國科學(xué)技術(shù)大學(xué),2013.

3 黃偉,王玉艷,章建雄.嵌入式處理器動(dòng)態(tài)分支預(yù)測機(jī)制研究與設(shè)計(jì).計(jì)算機(jī)工程,2008,34(21):163–165.

4 Gary ST. The effects of predicated execution on branchprediction. Proc. of the 27th Annual International Symposium on Microarchitecture. 1994. 196–206.

5 蘆運(yùn)照.謂詞相關(guān)編譯技術(shù)和深層代碼優(yōu)化[博士學(xué)位論文].北京:中國科學(xué)院研究生院計(jì)算技術(shù)研究所,2004.

6 劉旸.基于區(qū)域的編譯技術(shù)和棧寄存器優(yōu)化[博士學(xué)位論文].北京:中國科學(xué)院研究生院計(jì)算技術(shù)研究所,2003.

7 CETC. BWDSP100軟件用戶手冊.合肥:中國電子科技集團(tuán)公司第三十八研究所,2013:1–2.

8 Aho AV, Lam MS, Sethi R, et al. Compilers: Principles, Techniques, and Tools. 2nd ed., Beijing: China Machine Press, 2009: 428–436.

9 楊萍,王生原.用于多目標(biāo)編譯系統(tǒng)構(gòu)造的目標(biāo)機(jī)體系結(jié)構(gòu)描述.計(jì)算機(jī)科學(xué),2005,32(9):239–242.

10 劉旸,張兆慶,喬如良.基于域的編譯框架.計(jì)算機(jī)學(xué)報(bào), 2003,26(2):190.

11 Lengauer T, Tarjan R, Endre R. A fast algorithm for finding dominators in a flowgraph. ACM Trans. on Programming Languages and Systems, 1979, 1(1): 121–141.

Compilation Optimization of Address and Data Predicated Execution on BWDSP10x

FAN Yong-Chao1,2, ZHENG Qi-Long1,2, GENG Rui3, WANG Xiang-Qian3, WANG Hao312
(Anhui High Performance Computing Key Laboratory, University of Science and Technology of China, Hefei 230027, China)3(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China) (No. 38th Research Institute, China Electronics Technology Group Corporation, Hefei 230088, China)

The traditional predicate optimization technique is based on the Von Neumann architecture, which considers the data flow optimization only. However, BWDSP10x is based on the Harvard architecture, which data and instructions are physically separated. It provides VLIW and supports not only data predicated execution but also address predicated execution. Hence, we present an optimization method for the two predicated execution technology based on the region. In this method, types of the two operands of comparison operation will be identified before the two kinds of operations are executed, and when addresses are compared, the two operands don’t need to transfer to general registers. Experimental result shows that the optimization method can highly reduce the time and bandwidth of CPU, and reduce large numbers of branch instructions. The performance of programs tested is increased by 28.4 percent after the optimization.

address predicated execution; data predicated execution; region; compilation optimization

“核高基”重大專項(xiàng)(2012ZX01034-00-001)

2016-03-22;收到修改稿時(shí)間:2016-06-12

10.15888/j.cnki.csa.005573