王玉林，鄭啟龍

(1. 中國科學技術大學 計算機科學與技術學院，安徽 合肥 230027;2.中國科學技術大學 安徽省高性能計算重點實驗室，安徽 合肥 230027)

?

魂芯分簇VLIW DSP上指令調(diào)度的優(yōu)化*

王玉林1,2，鄭啟龍1

(1. 中國科學技術大學 計算機科學與技術學院，安徽 合肥 230027;2.中國科學技術大學 安徽省高性能計算重點實驗室，安徽 合肥 230027)

魂芯DSP處理器是一款32 bit靜態(tài)超標量、分簇結(jié)構的、支持SIMD的VLIW處理器。魂芯DSP芯片有4個執(zhí)行簇和3個內(nèi)存塊，但簇間數(shù)據(jù)傳輸和尋址會占用總線帶寬?；晷綝SP上每個簇中有大量的計算部件，但是現(xiàn)有的編譯器框架中指令調(diào)度算法是針對非分簇結(jié)構的，無法充分利用魂芯DSP的分簇結(jié)構特點，產(chǎn)生出高效的指令級并行代碼。根據(jù)魂芯處理器架構分簇的特點，提出了在魂芯DSP上進行指令分簇和指令調(diào)度的啟發(fā)式算法，并且在開源Open64編譯器框架上進行了實現(xiàn)。實驗結(jié)果表明，該算法在魂芯DSP編譯器上的實現(xiàn)可以顯著提高一些在DSP上有著計算密集型程序的性能。

分簇體系DSP；指令級并行；指令分簇；指令調(diào)度；Open64編譯器

0 引言

魂芯DSP是一款32 bit靜態(tài)超標量處理器，采用4個執(zhí)行簇16發(fā)射、單指令流多數(shù)據(jù)流(Single Instruction Multiple-data Stream,SIMD)架構[1]。處理器指令總線寬度為512 bit；內(nèi)部數(shù)據(jù)總線采用非對稱全雙工總線，內(nèi)部數(shù)據(jù)讀總線位寬為512 bit，內(nèi)部數(shù)據(jù)總線位寬為256 bit。該處理器是一款32 bit浮點數(shù)字信號處理器(Digital Signal Processor,DSP)，采用超長指令字(Very Long Instruction Word,VLIW)架構[2]，具有強大的并行處理能力，能較好地滿足高速實時信號處理的應用要求。

魂芯DSP芯片具有4個執(zhí)行簇，每個執(zhí)行簇都有自己的本地寄存器組和計算單元，指令分簇和調(diào)度可以高效利用DSP的硬件并行性并且利用單指令組合成超長指令字產(chǎn)生高質(zhì)量的代碼。對于分簇體系結(jié)構，指令調(diào)度比原有的正交體系結(jié)構調(diào)度更難，各個簇間的通信是通過簇內(nèi)部的數(shù)據(jù)總線，單周期內(nèi)只能夠從一個簇傳值64 bit的數(shù)據(jù)到另一個簇。本文重點介紹魂芯DSP上的指令分簇和調(diào)度算法，并在開源編譯基礎設施Open64編譯器框架上進行了實現(xiàn)。實驗效果表明，與原有的非分簇指令調(diào)度算法相比該指令分簇和調(diào)度算法能夠生成更高質(zhì)量的代碼。

1 編譯器框架

1.1 魂芯DSP體系結(jié)構

魂芯DSP是一款分簇結(jié)構、字尋址模式、支持SIMD的16發(fā)射的VLIW浮點運算信號處理器[3],片內(nèi)有3塊數(shù)據(jù)處理器，每塊8 MB。主要結(jié)構如圖1所示?；晷綝SP有4個計算簇，分別是X簇、Y簇、Z簇、T簇，每個計算簇有8個算術邏輯單元(ALU)、4個乘法器(MUL)、2個移位器(SHF)、1個超算單元(SPU)和1個寄存器組。計算簇與計算簇之間通過簇間數(shù)據(jù)總線通信。有3個地址簇即地址生成器，分別是U簇、V簇、W簇。存儲器與計算核之間的數(shù)據(jù)交換所需要的地址計算由地址生成器提供(AGU地址)。AGU是作用訪存地址計算的特殊單元，每個AGU上有獨立的地址寄存器文件(address register file)、專用的地址運算器(address calculation ALU)以及內(nèi)存存儲單元(load/store unit)。AGU主要用于普通的地址加減計算，以及l(fā)oad和store指令。

圖1 魂芯DSP體系結(jié)構

1.2 Open64開源編譯器框架

BWDSP編譯器采用開源Open64[4]編譯器基礎設施作為編譯器研究框架。Open64是一款GPL協(xié)議的工業(yè)級開源編譯基礎設施，以中后端提供的強大的分析優(yōu)化能力著稱。主要架構如圖2所示。

采取GCC作為前端，中間語言為抽象語法樹ASTtree。高級語言經(jīng)過前端時，以tree的形式存在，經(jīng)由gspin(一種從gcc的tree到WHIRL轉(zhuǎn)換的中間表示)的媒介，轉(zhuǎn)換成為WHIRL中間語言。Open64的前端將源程序轉(zhuǎn)化為內(nèi)部中間表示W(wǎng)HIRL，后端讀入WHIRL，經(jīng)過翻譯生成代碼生成階段(Code Generation，CG)的中間表示CGIR，再經(jīng)過一系列優(yōu)化，最終CGIR經(jīng)過代碼輸出生成匯編程序。

圖2 Open64編譯器架構

然而Open64編譯器框架支持的眾多處理器中沒有簇的概念。由于魂芯DSP擁有豐富的向量化資源，同時其應用對性能要求極高，因此有必要對魂芯DSP提供分簇支持，在分簇基礎上對指令進行調(diào)度。本文針對DSP芯片分簇和計算單元堆疊的特點，設計了一種算法，把指令分簇和指令調(diào)度耦合為一個過程來進行處理，通過指令調(diào)度的反饋來優(yōu)化指令分簇，進而迭代優(yōu)化指令調(diào)度。

2 指令調(diào)度

指令調(diào)度是對編譯器后端生成的指令的調(diào)度，利用可以并行執(zhí)行的指令充分發(fā)揮目標機的性能。所謂指令調(diào)度就是從順序程序中識別出指令級可并行的成分，并利用這些并行性合理安排指令的執(zhí)行順序，以達到最大限度地發(fā)揮目標機所提供的處理能力的目的。指令調(diào)度決定操作執(zhí)行的相對順序、各操作的具體執(zhí)行時間及使用哪些硬件資源等。

現(xiàn)有的一些比較好的局部和全局的調(diào)度算法都是針對非分簇體系結(jié)構。例如線性調(diào)度、基于關鍵路徑的調(diào)度[5]，以及跟蹤調(diào)度[6]和滲透調(diào)度[7]。這些算法都不是為了分簇體系結(jié)構設計的，在利用這些算法前至少需要一個對指令分簇的階段。然而這些算法在指令分簇的階段并不能知道后期指令調(diào)度中對資源和通信的約束。

2.1 問題定義

DSP上指令調(diào)度要解決的問題可以如下闡述：用B來表示一個基本塊，可以通過一個數(shù)據(jù)流圖(DFG)G=(V,E,ω)來代表。假設DFG中V表示具體指令，DFG中的邊表示指令間的依賴關系，每一條邊e的權重ω(e)是一個整數(shù)，代表了兩條指令間延遲的值。

假定DFG中的節(jié)點都還沒有綁定到X、Y、Z、T任何一個簇上。

P：V→{X,Y,Z,T}

分簇可定義為選擇DFG中的每一個節(jié)點應該綁定到X、Y、Z、T中的哪一個簇上，在選定了節(jié)點要綁定到哪一個簇的同時，這個節(jié)點需要的計算部件FU也就可以在這個簇上綁定到這個節(jié)點了。對于一個給定的分簇P，指令調(diào)度可以用如下兩個映射表示：

F：V→{ALU,MUL,SHF,SPU}

C:V→INs

一個調(diào)度是有效的指令調(diào)度定義為：對于任意的一個節(jié)點v∈V，指令需要的功能部件FUF(v)是在簇P(v)上的，每一個部件FU在一個周期內(nèi)只能使用一次，并且指令條C不能違反任何內(nèi)部的指令間依賴關系。也就是說對于任意的節(jié)點v的入邊都需要滿足下面的約束條件：

e1=(μ1,v),…,ek=(μk,v)

指令調(diào)度S=(F,C)的長度L(S)定義為控制流執(zhí)行的最后一步。最后一步的意思是，對于一條指令v的延遲，設為d(v)，那么L(S)是其中的執(zhí)行周期加上指令本身延遲中的最大值。

本文的目標是同時計算出一個分簇P和一個有效的并且長度最短的調(diào)度(F,C)。

2.2 指令分簇算法

調(diào)度算法包括兩個相互交互的階段。在階段1會產(chǎn)生一個暫時的指令分簇，然后對于給定的分簇信息階段2可以進行指令調(diào)度。調(diào)度的代價(指令執(zhí)行的周期數(shù))作為評價分簇的測量指標，然后基于此反饋，階段1重新找到一個更好的分簇結(jié)果作為階段2的輸入，一直迭代到收斂終止條件。

第一階段的分簇采用的是模擬退火算法(SA)[8]，與其他的遺傳算法類似，SA適用于非線性的優(yōu)化問題，因為它能避免基于評價函數(shù)的局部最優(yōu)化的問題。算法的思想是模擬冷卻的過程，從一個初始的結(jié)果和初始的閾值開始，每一步迭代中當前的結(jié)果被隨機地改變，如果更改后的結(jié)果更好那就作為當前的最優(yōu)解，否則就會根據(jù)當前的一個隨機值決定是否接受這個值作為最優(yōu)解。在迭代過程中，閾值越來越小，接受不好的值作為最優(yōu)解的可能性越來越小，算法如下：

algorithm PARTITION

input DFG

outout: P: array[1..N]of {0,1,2,3}

var

int i,j,r,cost,mincost;

Operlist operlist

float T;

begin

T=10; p:=InitalRandomPartitioning();

mincost:=ListSchedule(G,P)

while T>0.01 do

for i=1 to 50 do

r:=Random(1,n)

Pre_clustered:=P[r];

operlist:=getOpnds(r);

P[r]:=getMostOperlistClusterFlag(operlist,m);

cost:=ListSchedule(G,P);

delta:=cost-mincost;

if delta<0 or Random(0,1)

then mincost:=cost;

else P[r]:=Pre_clustered

end if

end for

T=0.6*T

end while

return P;

end algorithm

2.3 指令調(diào)度算法

調(diào)度算法的主函數(shù)是一個線性的調(diào)度算法[9]，輸入是一個DFG圖G和一個分簇過的指令流P。算法是一個拓撲排序問題，首先標記所有的節(jié)點指令為未調(diào)度的指令。每一個被選擇的節(jié)點通過函數(shù)ScheduleNode加到調(diào)度序列中，這個函數(shù)是指令調(diào)度的核心。最后算法返回調(diào)度后的指令周期數(shù)。主調(diào)度算法代碼如下：

algorithm ListSchedule

input: DFG G, Partitioning P;

output: schedule length;

var m: DFG node;

S: schedule;

scheduled[N];

begin

for i=0 to N do

Scheduled[i]:=false;

S:={};

while(not all nodes scheduled) do

m:=NextReadyNode(G);

S:=ScheduleNode(S,m,P);

scheduled[m]:=true;

end while

return Length(S);

end algorithm

子過程ScheduleNode用一些啟發(fā)式算法來避免增加多余的指令數(shù)，因為如果指令需要的被調(diào)度到不同的簇上，那么就需要通過增加mov_inter指令，通過簇間總線[10]將需要的操作數(shù)從另一個簇拷貝到本簇中。算法的輸入是當前的序列S，即將要加入S中的節(jié)點m，以及當前的分簇信息P[11]。主要的策略是在不違反資源約束和依賴約束的前提下把指令m盡可能插入到最早可以調(diào)度的指令數(shù)。開始，以m能最早被調(diào)度的周期數(shù)作為初始值，然而，如果它的前繼節(jié)點在調(diào)度中是第t個周期，并且這個前繼節(jié)點的延遲是d,那么m節(jié)點不能早于第t+d個周期被調(diào)度。測試是否滿足約束在子過程EarliestControlStep中。指令m在S中可執(zhí)行的周期數(shù)一直在增加，直到找到一個滿足約束條件的有效周期數(shù)。單個節(jié)點的調(diào)度算法如下：

algorithm ScheduleNode

input: current S, node m, partitioning P;

output: updated S containing m;

var cs:control step number

begin

cs:=EarliestControlStep(m)-1;

repeat

cs:=cs+1;

fm:=GetNodeUnit(m,cs,p);

if fm={} then continue;

if (m has a argument on a different cluster) then

CheckArgTransfer();

if(at least one transfer impossible) then continue;

else TryScheduleTransfers();

if (BusConfict(cs,m)) then continue;

until (m has been scheduled)

if (m is a load instruction) then

ScheduleAddrLoadPath(m);

end if

return S;

end algorithm

對于一個給定的周期數(shù)cs，GetNodeUnit尋找一個能執(zhí)行m指令的功能單元fm,且此功能部件fm在簇P(m)上第cs周期是可用的。對于魂芯DSP上的大部分指令，優(yōu)先SHF來執(zhí)行，SHF無空閑的情況下，可以通過ALU或者MUL來執(zhí)行。當然，因為每個簇中有2個SHF、4個MUL、8個ALU，當有多個FU滿足條件時，隨機選擇一個部件綁定到指令m上。

3 實驗結(jié)果

在提出了基于魂系DSP體系結(jié)構的指令分簇和調(diào)度算法[12]后，為了測試效果，選取了DSP經(jīng)典的測試集來測試編譯器性能，測試了原有的Open64中指令調(diào)度算法[13]和本文提出的調(diào)度算法對同一個程序編譯后執(zhí)行的周期數(shù)。在 ECS(Effective Coding Studio)統(tǒng)計程序執(zhí)行的周期數(shù)，優(yōu)化指令調(diào)度前后程序的周期數(shù)如圖3所示。沒有考慮寄存器分配的影響，是因為寄存器分配是在指令調(diào)度之前，所生成的DFG是一樣的，而且魂芯DSP每個簇中有64個通用寄存器，所以寄存器溢出并不是一個關鍵因素，不同的只是最后的指令調(diào)度階段。至此，基于開源編譯器框架Open64完成了針對魂芯DSP上指令分簇和指令調(diào)度的優(yōu)化，加速了程序的執(zhí)行。

圖3 DSP代碼的性能對比

圖3中的左邊柱條是指令優(yōu)化前的實驗結(jié)果，右邊的柱條是優(yōu)化后的指令調(diào)度算法的結(jié)果。實驗結(jié)果表明，程序性能提高了11%(irr)～41%(dct)，對于計算密集型程序且關鍵路徑節(jié)點較少的dct程序來說優(yōu)化效果最好，程序的限制因素是資源部件的約束，而對于程序中關鍵路徑節(jié)點較多的程序iir來說，指令調(diào)度并不能帶來多高的程序性能的提高。

最后，要說明一下本文提出算法的運行時開銷。原有的Open64的匯編優(yōu)化使用的是純啟發(fā)式的分簇和調(diào)度算法，開銷比較小。也就是說，SA算法對于大的優(yōu)化問題有較大的運行時開銷。然而，在本文提出的算法中，只是用SA算法進行分簇，指令調(diào)度還是用的啟發(fā)式算法[14]。這種橋接模式可以在可接受的時間內(nèi)調(diào)度較多DFGs節(jié)點的程序，而且在嵌入式系統(tǒng)中，代碼質(zhì)量要遠遠高于對編譯速度的考量，所以這點運行時開銷是可接受的。

4 結(jié)束語

本文針對魂芯DSP高性能處理芯片，利用其分簇特點和VLIW特點，提出了針對魂芯DSP上指令分簇和指令調(diào)度的算法?；陂_源的Open64編譯器，對算法進行了實現(xiàn)，實驗結(jié)果表明算法進一步優(yōu)化了魂芯DSP程序的代碼質(zhì)量，充分利用了魂芯DSP 4個簇和功能部件，縮短了程序指令的指令周期。對于這種分簇結(jié)構的處理器，一般是先進行分簇之后再進行指令調(diào)度。本文提出的算法基本上與機器是獨立的，算法把指令分簇和指令調(diào)度結(jié)合起來，相比原有兩遍單獨的優(yōu)化，取得了更好的優(yōu)化效果。

未來的工作是，考慮如何把寄存器分配和全局指令調(diào)度考慮進來。目前的調(diào)度是基于基本塊的，但是塊與塊之間全局的調(diào)度也有很大的優(yōu)化空間。

[1] 張為華, 朱嘉華, 張宏江, 等.基于位寬控制提高架構并行度的優(yōu)化算法[J].計算機學報, 2009, 32(11):2168-2176.

[2] FISHER J A, FARABOSCHI P, YOUNG C. Embedded computing: a VLIW approach to architecture, compilers and tools[M].北京:機械工業(yè)出版社, 2006.

[3] CETC38.BWDSP100 hardware user manual[Z]. Hefei:China Electronics Technology Group Corporation No.38 Research Institute, 2011.

[4] 高偉, 李驍, 趙博.源源翻譯流程研究[J].信息工程大學學報, 2013, 14(5):612-618.

[5] AIKEN A, NICOLAU A.A development environment for horizontal microcode[J].IEEE Transactions on Software Engineering, 1988, 14(5):584-594.

[6] 中國電子科技集團第三十八研究所.軟件用戶手冊[Z]. 2011:181-191.

[7] DAVIDSON S, LANDSKOV D, SHRIVER B D, et al.Some experiments in local microcode compaction for horizontal machines[J].IEEE Transactions on Computers, 1981, 100(7):460-477.

[8] CHENG G, LAM M. An optimizer for multimedia instruction sets[R]. Proceedings of the 2nd SUIF Compiler Workshop. Stanford University, 1997.

[9] FERNANDES M M, LLOSA J, TOPHAM N.Partitioned schedules for clustered vliw architectures[C].Parallel Processing Symposium, 1998. IPPS/SPDP 1998. IEEE, 1998: 386-391.

[10] LARSEN S, AMARASINGHE S .Exploiting supeword level parallelism with multimedia instruction sets[J].ACM SIGPLAN Notices, 2000, 35(5):145-156.

[12] 黃勝兵,鄭啟龍,郭連偉. 分簇VLIW DSP上支持單雙字模式選擇的SIMD編譯優(yōu)化[J]. 計算機應用,2015，35(8):2371-2374.

[13] HU E W, KU C, RUSSO A, et al.New DSP benchmark based on Selectable Mode Vocoder (SMV)[C].CDES, 2006: 175-181.

[14] 王向前,洪一,王昊,等. 魂芯DSP的編譯器設計與優(yōu)化[J]. 電子學報,2015,43(8):1656-1661.

Instruction scheduling optimization for clustered VLIW BWDSP

Wang Yulin1,2, Zheng Qilong1

(1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China;2. Anhui High Performance Computing Key Laboratory, University of Science and Technology of China, Hefei 230027, China)

BWDSP is a 32 bit static scalar digital signal processor which supports clustering and SIMD features. The BWDSP chip has four execution clusters and three memory blocks, but the inter-cluster data transmission and addressing will occupy the bus bandwidth. There are a large number of computing components in each cluster of the core BWDSP, but the instruction scheduling algorithm in the existing compiler framework is for non-clustered structure, and can not make full use of the clustering structure characteristic of the core BWDSP to produce efficient instruction level parallelism(IPL). According to the characteristics of the core processor architecture, a heuristic algorithm for instruction clustering and instruction scheduling on the BWDSP core is proposed to improve the instruction level parallelism. The framework is implemented on traditional Open64 compiler framework. Experimental results show that the implementation of the instructions can meet the requirements of the circumstances and the proposed technique is capable of generating more efficient code.

multi-cluster DSP; ILP; instruction partitioning; instruction scheduling; Open64 compiler

“核高基”重大專項(2012ZX01034-001-001)

TP314

A

10.19358/j.issn.1674- 7720.2017.11.007

王玉林，鄭啟龍.魂芯分簇VLIW DSP上指令調(diào)度的優(yōu)化[J].微型機與應用，2017,36(11)：23-26,30.

2017-01-13)

王玉林(1992-)，男，碩士研究生，主要研究方向：并行計算、編譯理論與技術。

鄭啟龍(1969-)，男，碩士，副教授，主要研究方向：并行編譯。