魂芯分簇VLIW DSP上指令調度的優化*

王玉林，鄭啟龍

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

?

魂芯分簇VLIW DSP上指令調度的優化*

王玉林1,2，鄭啟龍1

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

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

分簇體系DSP；指令級并行；指令分簇；指令調度；Open64編譯器

0 引言

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

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

1 編譯器框架

1.1 魂芯DSP體系結構

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

圖1 魂芯DSP體系結構

1.2 Open64開源編譯器框架

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

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

圖2 Open64編譯器架構

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

2 指令調度

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

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

2.1 問題定義

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

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

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

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

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

C:V→INs

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

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

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

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

2.2 指令分簇算法

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

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

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 指令調度算法

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

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

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

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

3 實驗結果

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

圖3 DSP代碼的性能對比

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

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

4 結束語

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

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

[1] 張為華, 朱嘉華, 張宏江, 等.基于位寬控制提高架構并行度的優化算法[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].北京:機械工業出版社, 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編譯優化[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的編譯器設計與優化[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上指令調度的優化[J].微型機與應用，2017,36(11)：23-26,30.

2017-01-13)

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

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