吳艾青,李 偉,別夢妮,南龍梅,陳 韜

(戰(zhàn)略支援部隊信息工程大學(xué),鄭州 450001)

1 引 言

近年來,隨著信息技術(shù)的高速發(fā)展,數(shù)據(jù)安全問題也愈發(fā)受到關(guān)注.密碼算法是應(yīng)對隱私威脅的有效手段,被廣泛應(yīng)用在數(shù)據(jù)傳輸、安全存儲等各個場景中[1].為兼顧通用處理器的靈活性和專用集成電路的高性能,李偉等[2]、南龍梅等[3]和戴紫彬等[4]分別設(shè)計了分組、序列和橢圓曲線密碼專用處理器.作為一種計算密集型應(yīng)用,密碼運(yùn)算中存在大量的指令級并行,且較少需要實時控制,因此密碼專用處理器常采用分簇式超長指令字(Very Long Instruction Word,VLIW)架構(gòu).通過簡化調(diào)度邏輯,大規(guī)模堆疊運(yùn)算單元,來提升體系結(jié)構(gòu)的并行性[5].編譯器的優(yōu)劣是能否充分利用處理器性能的關(guān)鍵因素之一.和通用處理器中常采用的分支預(yù)測、亂序執(zhí)行等技術(shù)[6]相比,分簇式VLIW架構(gòu)的處理器大多采用靜態(tài)調(diào)度策略,其性能的發(fā)揮更加依賴于編譯器的優(yōu)化[7].因此,研究面向密碼專用處理器的編譯后端優(yōu)化問題有著十分重要的意義.

目前,相關(guān)研究集中在數(shù)字信號處理器(Digital Signal Processor,DSP)領(lǐng)域[8],VLIW處理器的編譯器后端優(yōu)化包括3個核心階段:簇指派、指令調(diào)度和寄存器分配.簇指派確定指令執(zhí)行時所處的簇,以減小跨簇數(shù)據(jù)傳輸?shù)臅r間開銷.指令調(diào)度重排指令的執(zhí)行順序,以提升程序的并行性.寄存器分配將變量映射到寄存器或內(nèi)存中.這3個階段都是生成高性能程序的關(guān)鍵,且三者互相影響,每個都是NP困難問題.為降低復(fù)雜度,編譯器通常基于局部優(yōu)化的貪心策略,采用啟發(fā)式算法孤立地解決每個問題[9].Ellis[10]采用蹤跡調(diào)度算法處理指令調(diào)度問題,并為蹤跡中的指令進(jìn)行簇指派.Capitanio等[11]提出一種超圖染色技術(shù),以解決分簇式VLIW處理器的寄存器分配問題.

獨(dú)立的解決方案沒有考慮到不同階段的相互影響,組合優(yōu)化可以發(fā)現(xiàn)問題間的依賴性,通常會取得更高的程序性能.?zer等[12]將簇指派和指令調(diào)度相結(jié)合,在列表調(diào)度階段同時進(jìn)行基于優(yōu)先級的簇指派.Zalamea等[13]和Su等[14]進(jìn)一步將寄存器分配合并處理,通過減少變量溢出以獲得更高的吞吐率.

組合優(yōu)化方案大多采用啟發(fā)式算法,能夠在一定時間內(nèi)找到相對較優(yōu)的解.然而,啟發(fā)式算法自身的局限性要求對編譯過程多次迭代,并且解的質(zhì)量不穩(wěn)定.非啟發(fā)的組合優(yōu)化方案可以避免迭代,生成質(zhì)量穩(wěn)定的解.Arafath等[15]采用依賴于父節(jié)點的簇指派和基于優(yōu)先級的列表調(diào)度,從而減小簇間的數(shù)據(jù)交互.湯海京等[16]用“引力”描述指令間數(shù)據(jù)相關(guān)性,用“斥力”描述資源可用性,在簇指派和指令調(diào)度時平衡“引力”和“斥力”.在此基礎(chǔ)上,何虎等[17]在簇指派和指令調(diào)度時考慮了寄存器壓力,包括端口壓力和存儲壓力,來優(yōu)化全局寄存器的使用.這些研究采用無迭代的組合優(yōu)化方式,可以減少編譯時間、適用于更大規(guī)模的程序,相對于啟發(fā)式算法也能夠取得更高的程序性能,但這種方式只適應(yīng)于特定的體系結(jié)構(gòu).

和DSP相比,密碼處理器采用一種專用的VLIW架構(gòu),包括任意讀、固定寫的寄存器訪問方式,不同字長的指令,可重構(gòu)的運(yùn)算單元等.現(xiàn)有研究對專用架構(gòu)的適應(yīng)性不佳,因此本文提出了一種面向分簇式VLIW密碼處理器的編譯器后端優(yōu)化方法.方法以高性能為目標(biāo),將簇指派、指令調(diào)度和寄存器分配3個階段相結(jié)合,在簇指派和指令調(diào)度階段實時評估可用的運(yùn)算資源,減小訪問規(guī)則沖突;結(jié)合密碼處理器的體系結(jié)構(gòu)特征,確定指令篩選和簇生成方案、基于優(yōu)先級的指令選擇方案,以及基于平衡寄存器壓力的簇指派方案;改進(jìn)傳統(tǒng)的線性掃描算法,用“待引用次數(shù)”列表代替“活躍周期”列表,進(jìn)行實時的寄存器分配.該方法是非啟發(fā)式的,不需要進(jìn)行回溯,可以降低編譯時間,生成質(zhì)量穩(wěn)定的解.

本篇論文的剩余部分如下組織:第2部分介紹分簇式VLIW密碼處理器的體系結(jié)構(gòu)模型,并總結(jié)匯編指令需要滿足的約束;基于該模型,第3部分詳述了算法的具體過程,包括寄存器類型指派、指令篩選、基于優(yōu)先級的指令選擇、基于平衡壓力的簇指派和具體寄存器分配等;第4部分與其他代碼生成算法進(jìn)行對比,展現(xiàn)了本方法在提升性能的同時,降低了編譯時間;最后,第5部分進(jìn)行總結(jié)與展望.

2 密碼專用處理器的硬件結(jié)構(gòu)模型

以可重構(gòu)對稱密碼處理器[2,3]為基礎(chǔ),抽象出如圖1所示的分簇式VLIW密碼專用處理器的硬件結(jié)構(gòu)模型.處理器內(nèi)部包含4個簇,分別為Cluster A,Cluster B,Cluster C和Cluster D,簇間采用同構(gòu)設(shè)計,即每個簇的結(jié)構(gòu)完全相同,簇內(nèi)包含12個可重構(gòu)運(yùn)算單元(Reconfigurable Computing Elements,RCEs),32×32 bit的數(shù)據(jù)寄存器文件(Data Register Files,DRFs)和64×32 bit的密鑰寄存器文件(Key Register Files,KRFs).每個DRFs有兩個讀端口和一個寫端口,每個KRFs有一個讀端口和一個寫端口.所有指令都是單周期的,并通過數(shù)據(jù)前推等方式解決了相鄰超長指令之間的數(shù)據(jù)相關(guān)性.

和DSP[18]等分簇式VLIW架構(gòu)相比,密碼處理器需要遵守一些特殊規(guī)則:

1)考慮到密碼運(yùn)算的混亂和擴(kuò)散特性,典型的分簇式VLIW架構(gòu)會造成頻繁的跨簇通信.因此,DRFs和KRFs均采用任意讀和固定寫的組織方式,即在滿足讀端口數(shù)目約束的前提下,RCEs可以讀取其他簇寄存器文件中的數(shù)據(jù),但只能將數(shù)據(jù)寫回到本簇的寄存器文件中.

圖1 密碼專用處理器的硬件結(jié)構(gòu)模型Fig.1 Architecture of cryptographic processors

2)簇內(nèi)的部分運(yùn)算單元采用可重構(gòu)設(shè)計,包括置換、S盒替代、模運(yùn)算等.通過寫入相應(yīng)的配置信息,同一運(yùn)算單元能夠?qū)崿F(xiàn)不同參數(shù)的運(yùn)算,包括置換運(yùn)算的置換表、S盒替代運(yùn)算的替代表等.簇內(nèi)的配置信息和RCEs之間是緊耦合的,即簇內(nèi)的配置信息只對該簇的運(yùn)算單元有效.

圖2 密碼專用處理器的指令格式Fig.2 Instruction format of cryptographic processors

3)DRFs和KRFs盡管命名為“數(shù)據(jù)”寄存器文件和“密鑰”寄存器文件,但并不根據(jù)數(shù)據(jù)在密碼算法中是“數(shù)據(jù)”或“密鑰”對寄存器區(qū)分使用,而是根據(jù)指令格式.

4)如圖2所示,設(shè)計了不同字長的指令以適應(yīng)密碼運(yùn)算中靈活的操作位寬,包括單字指令、雙字指令和四字指令,分別處理32、64和128比特的數(shù)據(jù),占據(jù)1個、2個和4個指令槽.占據(jù)多個指令槽的指令,可以將結(jié)果寫回到相應(yīng)的多個簇中.比如,占據(jù)Slot 1和Slot 2的雙字指令,可以將數(shù)據(jù)寫回到Cluster A或者Cluster B的寄存器中.

3 統(tǒng)一化的編譯器后端

密碼專用處理器的編譯器后端包括3個核心階段:簇指派、指令調(diào)度和寄存器分配.3個階段獨(dú)立處理時,由于無法實時評估可用的運(yùn)算資源,導(dǎo)致生成代碼的性能不高,并且需要進(jìn)行回溯.將3個階段合并處理,則可以很大程度上避免上述問題的發(fā)生.因此,本節(jié)設(shè)計了面向分簇式VLIW密碼專用處理器的統(tǒng)一化編譯器后端,具體流程如算法1所示.

算法1.統(tǒng)一化的編譯器后端

輸入：數(shù)據(jù)流圖DFG,可用資源的狀態(tài);

輸出：密碼專用指令的匯編程序;

1.為變量進(jìn)行寄存器類型指派;

2.對DFG進(jìn)行ASAP調(diào)度,得到指令OP的最早執(zhí)行時間為Te(OP);

3.對DFG進(jìn)行ALAP調(diào)度,得到指令OP的最晚執(zhí)行時間為Tl(OP);

4.計算指令OP的可移動性,Mobility(OP)=Tl(OP)-Te(OP);

5.構(gòu)造無前驅(qū)結(jié)點的指令列表L;

6.根據(jù)可用資源的狀態(tài),進(jìn)行指令篩選和候選簇生成;

7.基于優(yōu)先級的指令選擇;

8.基于平衡寄存器壓力的簇指派;

9.檢查指令槽是否被填滿,填滿則跳轉(zhuǎn)至Step 11;

10.更新可用資源的狀態(tài),進(jìn)行二次指令篩選和候選簇生成,仍存在可調(diào)度的指令則跳轉(zhuǎn)至Step 7;

11.為目的操作數(shù)進(jìn)行具體寄存器分配;

12.檢查是否完成調(diào)度,未完成則執(zhí)行Step 13,否則結(jié)束程序;

13.更新未調(diào)度指令的前驅(qū)結(jié)點個數(shù),并將新增的無前驅(qū)結(jié)點指令添加到L中;

14.檢查并解決新增的無前驅(qū)結(jié)點指令中單條指令內(nèi)出現(xiàn)的讀端口沖突;

15.更新“定值-引用”鏈,另L中所有的指令可調(diào)度,并跳轉(zhuǎn)至Step 6;

首先,確定變量的寄存器類型.指令手冊中詳細(xì)地約束了每條指令中操作數(shù)的寄存器類型,約束不僅出現(xiàn)在源操作數(shù)位置,還出現(xiàn)在目的操作數(shù)位置.比如,PERM_XOR Rd,Rs1,Rs2,Rs3指令中的源操作數(shù)Rs3只能來自KRFs,而XOR32 Rd,Rs1,Rs2指令中的目的操作數(shù)Rd只能寫回到DRFs.這意味著每個操作數(shù)都有兩個或兩個以上的寄存器類型約束.在指令調(diào)度時進(jìn)行寄存器類型指派,無法評估后續(xù)引用對變量的寄存器類型約束,從而增大了類型沖突的可能性.在指令調(diào)度結(jié)束后再進(jìn)行寄存器類型指派,解決沖突時需要插入新指令,從而產(chǎn)生不必要的回溯.因此,先為變量指派寄存器類型.

圖3 ASAP和ALAP的調(diào)度結(jié)果Fig.3 Result of ASAP and ALAP scheduling

在Step 2和Step 3中,不考慮資源約束的情況下,分別對數(shù)據(jù)流圖(Data Flow Graph,DFG)進(jìn)行ASAP(As Soon As Possible)和ALAP(As Late As Possible)調(diào)度,得到指令OP的最早執(zhí)行時間Te(OP)和最晚執(zhí)行時間Tl(OP).Step 4進(jìn)一步計算指令的可移動性.指令的可移動性是指在無資源約束和不影響程序執(zhí)行時間的前提下,指令在不同周期內(nèi)的可移動性.圖3展示了對同一DFG的ASAP和ALAP調(diào)度結(jié)果,其中指令OP4和指令OP7的可移動性為1,其余指令的可移動性為0.可移動性用于Step 7中指令的優(yōu)先級計算.

除了無前驅(qū)結(jié)點以外,可調(diào)度的指令還要滿足可用資源約束.因此,Step 6對Step 5構(gòu)造的無前驅(qū)結(jié)點指令列表L進(jìn)行篩選,篩選出可調(diào)度的指令,以及指令的候選簇,這一過程將在3.2節(jié)中被詳述.Step 7和Step 8基于優(yōu)先級,從可調(diào)度的指令中選擇優(yōu)先級最高的指令來討論簇指派問題,指令選擇和簇指派的詳細(xì)過程分別在3.3節(jié)和3.4節(jié)當(dāng)中.

一條超長指令內(nèi)有多個指令槽,可以并行執(zhí)行多條指令.Step 9檢查當(dāng)前超長指令的指令槽是否被填充滿.當(dāng)指令槽被填充滿時,Step 11對超長指令內(nèi)的所有目的操作數(shù)進(jìn)行寄存器分配.否則,Step 10更新資源占用情況,對可執(zhí)行的指令進(jìn)行二次篩選.如果仍存在可執(zhí)行的指令,返回到Step 7進(jìn)行后續(xù)的指令選擇和簇指派.否則,同樣進(jìn)行Step 11寄存器分配.

以上就完成了一條超長指令的簇指派、指令調(diào)度和寄存器分配.因此,Step 13可以更新DFG,將當(dāng)前被執(zhí)行指令的后繼結(jié)點的前驅(qū)結(jié)點個數(shù)減1,并將新增的無前驅(qū)結(jié)點指令添加到可調(diào)度指令列表L中.新增的指令中,有可能在單條指令內(nèi)就出現(xiàn)了讀端口沖突,Step 14先檢查并解決這種沖突,再生成下一條超長指令,直至DFG中所有結(jié)點被處理完成.

3.1 寄存器類型指派

寄存器類型指派階段,根據(jù)變量的“定值-引用”鏈和指令中對操作數(shù)的寄存器類型約束,為變量指派寄存器類型,具體過程如算法2所示.

算法2.寄存器類型指派

輸入：數(shù)據(jù)流圖DFG,可用資源的狀態(tài);

輸出：變量的寄存器類型;

1. 為每個變量x構(gòu)造相應(yīng)的“定值-引用”鏈;

2.foreach(x)

3. 計算x的候選寄存器類型集合C;

4.if(card(C)= 1)

5. 為x指派C中的寄存器類型;

6.elseif(card(C)= 2)

7. 為x指派DRFs;

8.else

9. 將所有沖突的引用重命名成x1;

10. 在x1的第1個引用前插入movx1,x指令;

11. 分別為x和x1指派寄存器類型;

12. 更新DFG和“定值-引用”鏈;

首先,根據(jù)DFG為每個變量構(gòu)造相應(yīng)的“定值-引用”鏈.“定值-引用”鏈可以用三元組{Name,Define,Use}來表示,其中Name是變量名,Define是定值所在位置,Use是所有引用的集合.如圖4(a)所示,{x,,{,}}表示變量x在指令OP1的第1個操作數(shù)位置被定值,在指令OP4的第3個操作數(shù)位置和指令OP6的第2個操作數(shù)位置被引用.

其次,確定變量的候選寄存器類型集合.用type(OP,k)表示指令OP第k個操作數(shù)位置的寄存器類型約束,type(OP,k)的取值有3種情況:{DRFs}、{KRFs}、{DRFs,KRFs}.變量的候選寄存器類型集合,是定值點候選寄存器類型集合和所有引用點候選寄存器類型集合的交集.比如,變量x的候選寄存器類型集合為type(OP1,1)∩type(OP4,3)∩type(OP6,2),其取值有4種可能的情況:{DRFs}、{KRFs}、{DRFs,KRFs}、Φ:

1)當(dāng)集合為{DRFs}或{KRFs}時,即集合中只有一個元素時,直接為變量指派相應(yīng)的寄存器類型.

2)當(dāng)集合為{DRFs,KRFs},應(yīng)當(dāng)平衡不同類型寄存器文件間的壓力,但此時并未進(jìn)行指令調(diào)度,無法準(zhǔn)確評估這種壓力.在密碼運(yùn)算中,除密鑰以外的大部分?jǐn)?shù)據(jù)定值后立刻被引用,且只引用一次,整體來說DRFs有更小的寄存器壓力,因此本文直接為變量指派DRFs.

圖4 解決寄存器類型沖突的示意圖Fig.4 Resolving register type conflicts

3)當(dāng)集合為Φ時,則出現(xiàn)了寄存器類型沖突,可以通過重命名所有沖突的引用、插入mov指令并更新DFG和“定值-引用”鏈的方式解決沖突.假設(shè)type(OP1,1)= {DRFs},type(OP4,3)= {DRFs,KRFs},type(OP6,2)= {KRFs},計算type(OP1,1)∩type(OP4,3)= {DRFs},而type(OP1,1)∩type(OP4,3)∩type(OP6,2)= Φ,可以認(rèn)為所有沖突的引用為.因此,在OP1和OP6之間插入一條movx1,x指令OP7,為變量x指派為DRFs類型,為變量x1指派為KRFs類型.在此基礎(chǔ)上,DFG和“定值-引用”鏈需要進(jìn)行更新,更新后的DFG如圖4(b)所示.原本的1條“定值-引用”鏈也被轉(zhuǎn)換成2條,{x,,{}}和{x1,,{}},更新后的“定值-引用”鏈用于3.5節(jié)的具體寄存器分配.

3.2 指令篩選和候選簇生成

指令篩選和候選簇生成部分,根據(jù)可用資源的狀態(tài),從所有無前驅(qū)結(jié)點的指令中篩選出可執(zhí)行的指令,并生成指令的候選簇,具體過程如算法3所示.

算法3.指令篩選和候選簇生成

輸入：無前驅(qū)結(jié)點的指令列表L,可用資源的狀態(tài);

輸出：可調(diào)度的指令,及其候選簇;

1.foreachOP inL

2.if(OP是可重構(gòu)指令)

3.if(OP配置信息所在簇被占用)

4. OP不可執(zhí)行;

5.elseif(OP滿足讀端口約束)

6. OP可執(zhí)行,候選簇為配置信息所在簇;

7.else

8. OP不可執(zhí)行;

9.else

10. 根據(jù)指令字長生成初始候選簇集合;

11. 根據(jù)簇占用情況去除集合中不可用的元素;

12.if(候選簇集合為空)

13. OP不可執(zhí)行;

14.elseif(OP滿足讀端口約束)

15. OP可執(zhí)行;

16.else

17. OP不可執(zhí)行,設(shè)候選簇集合為空;

對于可重構(gòu)指令,比如置換指令、S盒替代指令等,先檢查配置信息所在簇是否被占用.由于RCEs和配置信息的緊耦合性,一旦被其他指令占用,使用簇內(nèi)配置信息的指令便不能在當(dāng)前周期執(zhí)行.

對于非可重構(gòu)指令,不同字長指令的初始候選簇集合不同.四字指令、雙字指令和單字指令的的初始候選簇集合分別為{Cluster ABCD},{Cluster AB,Cluster CD}和{Cluster A,Cluster B,Cluster C,Cluster D}.其次,根據(jù)簇占用情況去除初始候選簇集合中不可用的元素.比如,當(dāng)只有Cluster A被占用時,四字指令、雙字指令和單字指令的候選簇集合分別為Φ、{Cluster CD}和{Cluster B,Cluster C,Cluster D}.

最后,無論是可重構(gòu)指令還是非可重構(gòu)指令,都要滿足讀端口約束.DRFs和KRFs有固定的讀端口數(shù),DRFs有兩個讀端口,KRFs有一個讀端口.超長指令內(nèi)已調(diào)度的指令會占用一部分讀端口,因此新增的指令不能造成沖突.

3.3 基于優(yōu)先級的指令選擇

經(jīng)過指令篩選,在可用資源的狀態(tài)下,存在一條或多條可執(zhí)行的指令.當(dāng)只有一條指令時,跳過該步驟.有多條可選的指令時,為了保證對性能影響較大的指令先被執(zhí)行,采用基于優(yōu)先級的指令選擇方法.表1展示了4條指令的優(yōu)先級計算,依次考慮指令的可移動性、后繼結(jié)點個數(shù)和指令字長對調(diào)度的影響.

表1 指令優(yōu)先級的計算Table 1 Priority list of instructions

算法1根據(jù)ASAP和ALAP的調(diào)度結(jié)果計算了指令的可移動性.可移動性越小,其對于指令調(diào)度越關(guān)鍵.可移動性小的指令一旦被推遲,將會惡化程序整體的執(zhí)行時間.因此,可移動性小的指令應(yīng)當(dāng)優(yōu)先被處理.

在可移動性相同的前提下,根據(jù)后繼結(jié)點個數(shù)判斷指令優(yōu)先級.指令的后繼結(jié)點個數(shù)越多,其被執(zhí)行之后能夠釋放的指令也就越多,有利于下一步的調(diào)度.因此,后繼結(jié)點個數(shù)多的指令應(yīng)當(dāng)優(yōu)先被處理.

在可移動性和后繼結(jié)點個數(shù)相同的前提下,長字指令有更高的優(yōu)先級.一方面,對于四字指令,無論先執(zhí)行還是后執(zhí)行都不影響程序最終的執(zhí)行時間;另一方面,從靈活性來看,短字指令比長字指令更加靈活.單字指令可以被填充到指令槽的任一位置,雙字指令必須有兩個連續(xù)的指令槽,四字指令則要求所有指令槽均為空.因此,相對于短字指令,長字指令應(yīng)當(dāng)優(yōu)先被處理.

3.4 基于平衡寄存器壓力的簇指派

在可用資源的狀態(tài)下,優(yōu)先級最高的指令存在一個或多個候選簇.當(dāng)只有一個候選簇時,跳過該步驟.有多個候選簇時,采用基于平衡寄存器壓力的簇指派方法.

指令所在簇直接決定了目的操作數(shù)的存儲位置,因此簇指派要平衡寄存器文件間的壓力.一方面,變量溢出需要增加訪存指令,進(jìn)而惡化生成程序的性能,相對平衡的寄存器壓力可以降低變量溢出的概率;另一方面,相對平衡的寄存器壓力使指令源操作數(shù)的來源相對均衡,進(jìn)而降低寄存器文件讀端口沖突的概率,同樣有利于下一步的調(diào)度.

表2 寄存器文件的最大壓力差計算Table 2 Maximum pressure difference between 4 DRFs

計算不同簇指派方案下寄存器文件間的最大壓力差.寄存器文件間的最大壓力差是指當(dāng)前周期寄存器文件最大壓力和最小壓力的差值.在3.1節(jié),已經(jīng)為變量指派了寄存器類型,因此需要將DRFs和KRFs分開考慮.比如,4組DRFs的初始壓力分別為2、3、1、2,單字指令XOR32 Rd,Rs1,Rs2中目的操作數(shù)Rd的寄存器類型為DRFs,該指令的3個候選簇分別為Cluster B、Cluster C、Cluster D.如表2所示,計算3種不同方案下寄存器文件間的最大壓力差分別為3、1、2.選擇最大壓力差最小的方案,該方案可以實現(xiàn)寄存器壓力的平衡,即將指令指派到Cluster C上.

3.5 具體寄存器分配

寄存器分配可以被看作3個階段:寄存器類型指派、寄存器簇指派和具體寄存器分配.寄存器類型指派在3.1節(jié)中完成;指令所在簇直接決定了目的操作數(shù)的存儲位置,寄存器簇指派在3.4節(jié)完成.因此,本節(jié)只討論具體寄存器分配.另外,變量在定值后才能被引用,實際只討論目的操作數(shù)的具體寄存器分配.

算法采用同時進(jìn)行指令調(diào)度和具體寄存器分配的方式,即每調(diào)度完一條超長指令,就為當(dāng)前指令中的目的操作數(shù)分配具體寄存器.該方式在具體寄存器分配前并未完成指令調(diào)度,也就無法直接構(gòu)造沖突圖,并用圖著色算法[19]處理寄存器分配問題,而線性掃描算法[20]恰好按照指令的執(zhí)行順序進(jìn)行寄存器分配,因此本文改進(jìn)了傳統(tǒng)的線性掃描算法,將其擴(kuò)展到VLIW密碼專用處理器上,如算法4所示.

處理器內(nèi)的多個寄存器文件各自維護(hù)其“活躍變量”列表,即當(dāng)前存儲在相應(yīng)寄存器文件中的變量.所有寄存器文件共同維護(hù)變量的“活躍周期”列表,用于表示各個變量的定值位置和最后一次引用位置.當(dāng)變量定值時,將其存儲到寄存器;當(dāng)變量不再被引用時,釋放其所處的寄存器.由于寄存器分配時未完成指令調(diào)度,無法判斷變量實際的“活躍周期”,因此用“待引用次數(shù)”列表Ln替代“活躍周期”列表.

變量每被引用一次,需要將Ln中相應(yīng)的待引用次數(shù)減1.待引用次數(shù)為0表明變量不再被引用,即“活躍周期”結(jié)束,將變量從Ln中刪除,并釋放其所在的寄存器,為下一步的分配勻出更多資源.變量一旦被定值,則根據(jù)算法1中的“定值-引用”鏈,將變量名和待引用次數(shù)加入到Ln中.如果寄存器文件內(nèi)有空余的寄存器,直接為變量分配寄存器即可.如果沒有空余的寄存器,需要先對寄存器文件中的變量進(jìn)行溢出.變量溢出時既可以采用“先進(jìn)先出”的策略,即先被定值的變量先溢出,也可以采用其他策略,包括“后進(jìn)先出”、“少用先出”等.

算法4.具體寄存器分配

輸入：待寄存器分配的超長指令,可用資源的狀態(tài);

輸出：具體寄存器分配方案;

1.for(每個源操作數(shù))

2. 將Ln中相應(yīng)變量的待引用次數(shù)減1;

3.if(變量的待引用次數(shù)為0)

4. 將變量從Ln中刪除,并釋放其所在的寄存器;

5.for(每個目的操作數(shù))

6.if(無可用寄存器)

7. 變量溢出;

8. 分配寄存器,并將變量和待引用次數(shù)添加到Ln中;

4 實 驗

4.1 實驗環(huán)境

將分組密碼領(lǐng)域?qū)Ｓ谜Z言DSLBCA[21]擴(kuò)展到可以描述不同體制密碼算法的領(lǐng)域?qū)Ｓ谜Z言Crypto-DSL,其支持密碼運(yùn)算中常見的粗粒度算子.Crypto-DSL的算子粒度和密碼專用處理器的指令粒度接近,可以高效地將Crypto-DSL描述的程序轉(zhuǎn)化成以密碼專用指令為結(jié)點的DFG.

圖5 Crypto-DSL cc的編譯框架Fig.5 Compiler framework of Crypto-DSL cc

Crypto-DSL cc是相應(yīng)的編譯器,圖5展示了面向密碼專用指令處理器的Crypto-DSL cc編譯框架,整體上包括3部分:編譯前端、編譯后端和模擬仿真器.編譯前端進(jìn)行詞法分析、語法分析、語義分析,并生成中間代碼;后端建立DFG并進(jìn)行簇指派、指令調(diào)度和寄存器分配;模擬仿真器則進(jìn)行匯編程序級的仿真驗證,輸出相應(yīng)結(jié)果,并得到程序消耗的時鐘周期數(shù).整個編譯器是自主開發(fā)的,且是高度模塊化的,便于將本文提出的后端實現(xiàn)并嵌入到編譯器中.

編譯器后端和模擬仿真器的輸入都包括目標(biāo)機(jī)的體系結(jié)構(gòu)配置文件,意味著Crypto-DSL cc能夠適應(yīng)于不同的密碼專用處理器.用戶可以編寫處理器配置文件,配置簇的數(shù)量、簇內(nèi)運(yùn)算單元的個數(shù)和功能、寄存器文件寬度和深度、以及寄存器文件的訪問規(guī)則等.本實驗中采用對稱密碼處理器[2,3]和ECC密碼處理器[4]這兩種目標(biāo)機(jī),對稱密碼處理器的簇間是同構(gòu)組織的,而ECC密碼處理器的簇間是異構(gòu)組織的,配置文件主要參數(shù)如表3所示.

表3 密碼處理器的配置文件參數(shù)Table 3 Parameters for cryptographic processors

為了評估編譯器后端對于不同體制密碼算法的有效性,采用如表4所示的4類共10種密碼算法作為測試集,其中分組、序列和雜湊密碼算法各選擇了3種不同的算法,ECC密碼算法則選擇了2組不同的參數(shù):素數(shù)域上密鑰長度為128bit的橢圓曲線和二元域上密鑰長度為163bit的橢圓曲線.由于雜湊密碼算法和分組密碼算法在結(jié)構(gòu)上的相似性,分組、序列和雜湊密碼算法在對稱密碼處理器上執(zhí)行,ECC密碼算法在ECC密碼處理器上執(zhí)行.

表4 實驗測試集Table 4 Test sets

4.2 生成代碼的性能對比

將經(jīng)典的BUG算法[10]作為比較基準(zhǔn),選擇其他3種方案進(jìn)行對比,分別為UAS算法[12]、WCET算法[14]和FBTP算法[16].圖6展示了不同方案相對于BUG算法的性能提升.

圖6 不同方案的性能比較Fig.6 Performance comparison

UAS算法在指令調(diào)度時未考慮指令優(yōu)先級,順序地從可調(diào)度的指令列表中選擇指令進(jìn)行調(diào)度,并且未實時考慮寄存器分配問題,因此其性能最低.FBTP算法在指令調(diào)度時優(yōu)先處理關(guān)鍵路徑上的指令,并根據(jù)指令的前驅(qū)或后繼結(jié)點,以及簇占用情況進(jìn)行簇指派,但并未進(jìn)行實時的寄存器分配,其性能高于UAS算法,低于WCET算法.WCET算法用增量的圖著色技術(shù)進(jìn)行實時的寄存器分配,但其指令優(yōu)先級和后繼節(jié)點之間的最大延遲有關(guān),并未預(yù)先計算程序的關(guān)鍵路徑,而本方案先進(jìn)行了關(guān)鍵路徑的分析,因此WCET算法比本方案的性能略低.

在所有的測試向量中,本方案在生成程序的性能上均優(yōu)于其他方案的另一個主要原因在于其他方案對于密碼專用處理器硬件結(jié)構(gòu)的不適應(yīng).傳統(tǒng)VLIW處理器的簇間數(shù)據(jù)交互需要額外指令,因此無論是BUG算法,還是其他算法都以減小簇間通信為主要目標(biāo)之一.比如,UAS算法的簇指派優(yōu)先級的策略3根據(jù)指令中源操作數(shù)所在簇為指令進(jìn)行簇指派,FBTP算法簇指派時考慮前驅(qū)和后繼結(jié)點所在簇,WCET算法優(yōu)先將后繼結(jié)點的多個前驅(qū)結(jié)點指派到同一簇上.然而,對于密碼專用處理器來說,合理的簇間數(shù)據(jù)交互是必要的,在算法設(shè)計中考慮這一因素可以有效提升生成程序的性能.

本方案在處理序列密碼算法和ECC密碼算法的性能提升較小,比如Grain v1和ECC(2,163).主要原因在于,序列密碼算法占用的寄存器規(guī)模小,不需要考慮寄存器壓力的平衡性就可以取得不錯的性能提升;ECC密碼處理器采用了異構(gòu)組織的簇間運(yùn)算單元,指令的簇指派受到限制,使得不同方案的調(diào)度結(jié)果差距較小.分組密碼算法需要生成并存儲中間密鑰,雜湊密碼算法則需要對消息進(jìn)行擴(kuò)展,這些都占用了較多的寄存器資源.比如,AES-128需要存儲44個密鑰字,SHA1將消息擴(kuò)展至80個消息子塊.UAS算法在簇指派時并沒有考慮平衡寄存器壓力,這導(dǎo)致簇間寄存器壓力不平衡,產(chǎn)生不必要的溢出.基于平衡寄存器壓力的方案可以取得更高的生成代碼性能.

4.3 編譯時間對比

將本方案和其他3種方案進(jìn)行編譯時間的對比,分別為UAS算法[12]、WCET算法[14]和FBTP算法[16],對比結(jié)果如圖7所示.

圖7 不同方案的編譯時間比較Fig.7 Compilation time comparison

UAS算法順序地進(jìn)行指令調(diào)度,簇優(yōu)先級策略相對簡單,盡管最后階段要進(jìn)行寄存器分配并處理讀端口沖突,但其編譯時間仍最低.WECT算法的局部調(diào)度策略和本方案接近,在無變量溢出時并不采用啟發(fā)式算法,優(yōu)先級計算、增量沖突圖著色的寄存器分配技術(shù)比本方案復(fù)雜,但本方案增加了關(guān)鍵路徑的分析過程,因此編譯時間相近.FBTP算法需要預(yù)先分析關(guān)鍵路徑,調(diào)度過程分為預(yù)調(diào)度和重調(diào)度兩個階段,且簇優(yōu)先級需要進(jìn)行復(fù)雜計算,因此其編譯時間最長.

同樣地,編譯時間較長的另一個主要原因在于其他方案對密碼算法應(yīng)用場景,以及密碼專用處理器硬件結(jié)構(gòu)的不適應(yīng),編譯階段均存在一些不必要的操作.比如,密碼算法中一般只包含簡單的循環(huán)和分支結(jié)構(gòu),WCET算法復(fù)雜的全局優(yōu)化策略卻消耗了較長的編譯時間;傳統(tǒng)VLIW處理器的簇間數(shù)據(jù)交互需要額外指令,FBTP算法復(fù)雜的簇優(yōu)先級計算都集中在當(dāng)前指令和前驅(qū)或后繼結(jié)點的關(guān)系上,這對于密碼專用處理器來說也是沒有必要的.因此,在具體應(yīng)用場景中,本方案既可以提升編譯性能,也能夠有效降低編譯消耗的時間.

5 總 結(jié)

本文提出一種面向分簇式VLIW密碼處理器的編譯器后端優(yōu)化方法.將簇指派、指令調(diào)度和寄存器分配3個階段合并處理,實時評估可用的運(yùn)算資源,減小訪問規(guī)則沖突.結(jié)合密碼處理器的體系結(jié)構(gòu)特征,確定指令篩選和候選簇生成方案、基于優(yōu)先級的指令選擇方案,以及基于平衡寄存器壓力的簇指派方案.改進(jìn)傳統(tǒng)的線性掃描算法,用“待引用次數(shù)”列表代替“活躍周期”列表,以進(jìn)行實時的寄存器分配.結(jié)果表明,在密碼專用處理器中,和其他研究相比,本文提出的方法可以在節(jié)約編譯時間的基礎(chǔ)上,獲得更高的程序性能.