基于數據流塊的空間指令調度方法

劉炳濤 王 達 葉笑春 范東睿,2 張志敏 唐志敏

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)

2(中國科學院大學計算機與控制學院 北京 100049)

3 (杭州電子科技大學信息與控制研究所 310018)

(liubingtao@ict.ac.cn)

超標量處理器發掘指令級并行性(instruction level parallelism, ILP)的能力隨著發射寬度和調度窗口的增大而提升，然而發射隊列和操作數傳遞網絡等關鍵部件的復雜度隨著發射寬度和調度窗口的增大呈平方增長的趨勢[1].分簇超標量處理器[2]將硬件資源分區來避開大的單體部件帶來的功耗與周期懲罰.如圖1所示，分簇超標量處理器負責完成指令執行的流水線后端劃分為多個區，各分區有獨立的發射隊列、物理寄存器文件和功能單元，跨分區傳遞操作數需要額外的周期，我們稱之為分區間延遲(inter-partition latency,IPL).

Fig. 1 Clustered superscalar processor microarchitecture圖1 分簇超標量處理器微結構

處理器單核的性能和頻率提升受限于結構復雜度和功耗墻[3]等問題，為了提升計算能效，善于發掘線程級并行性(thread level parallelism, TLP)的多核處理器逐漸成為主流[4].但處理器的單線程處理能力仍然重要，Hill與Marty[5]指出，依據阿姆達法則，隨著并行部分的加速，串行部分逐漸成為繼續降低程序運行時間的瓶頸.動態多核處理器(dynamic multi-core, DMC)[5]融合數個物理核的資源來提供適應需求的計算能力.如圖2所示，含8個物理核的DMC處理器可以提供相當于2個或4個物理核計算能力的虛擬核.物理核有獨立的硬件資源，虛擬核內跨越物理核邊界傳遞操作數也存在IPL.

Fig. 2 Dynamic multi-core processor microarchitecture圖2 動態多核處理器微結構

超標量處理器采用同時多線程技術(simultaneous multithreading, SMT)[6]可以發掘TLP.SMT技術在單核中發掘TLP，DMC技術在多核中發掘ILP.殊途同歸，它們都是通過合理使用在空間分布的硬件資源實現高能效計算.分區結構能以較低功耗與周期開銷提供可擴展的計算能力，但負載不均衡和IPL可能導致性能懲罰，分區結構需要有效的指令調度方法分布指令到各分區.負載均衡傾向于將指令分布到不同分區，而減少IPL懲罰則傾向于將指令根據依賴關系分布到同一分區，存在沖突的策略需要根據指令的關鍵性進行權衡決策，這就是空間指令調度問題.

為解決空間指令調度問題，我們提出了基于數據流塊(data-flow block，DFB)的空間指令調度方法，簡稱DFB調度.DFB是動態構建、緩存并重用的一個或數個順序執行的指令基本塊的調度模式.DFB調度算法用數據流約束模型描述動態指令序列中的依賴關系，用調度空間模型描述硬件資源約束，量化分析每條指令的調度裕量，根據指令間的相對關鍵性完成調度決策，生成周期跨度盡量小的調度模式，DFB調度緩存重用這種調度模式.我們介紹了DFB調度的微結構框架和算法.通過對分區數、IPL和調度窗口容量等與調度方法密切相關的微結構參數的實驗，我們證明了DFB調度的性能和穩定性優于負載均衡調度和基于指令絕對關鍵性的依賴調度.最后舉例證明結合一種數據流塊緩存實現的DFB調度達到的調度效果接近理想化的DFB調度.

本文貢獻主要存在于3方面：

1) 我們構造了描述指令依賴關系的數據流約束模型并提出了基于量化指標的指令相對關鍵性的概念；

2) 我們構造了描述分區結構資源限制的調度空間模型并分析了空間指令調度問題；

3) 我們提出了DFB調度并進行了評估.

1 相關工作

Palacharla等人[1]研究了發射隊列的復雜度與時鐘周期的關系，指出隨著發射寬度和調度窗口增大，喚醒和選擇邏輯成為關鍵路徑.該文提出了多體發射隊列，利用分區結構解決超標量處理器可擴展性問題.

指令預調度[7-9]從時間維度調度指令，提升發射隊列效率.根據生產者指令執行延遲，指令在預調度窗口內重新排列，然后逐行進入發射隊列，這樣減少了指令在發射隊列內的等待周期數.WIB[10]和Cyclone[11]將阻塞指令從發射隊列中暫時取出，也屬于時間指令調度.

較多研究[12-15]關注分簇超標量處理器中指令空間調度問題.已有方法首先判斷指令是否是關鍵路徑指令，然后做出調度決策，研究重點在于指令關鍵性的判定.Fields等人[16]通過指令依賴鏈的長度做出指令關鍵性預測.Salverda等人[17]通過指令的歷史執行信息做出關鍵性預測.本文提出的DFB調度量化指令的調度裕量并參照硬件資源約束做出調度決策.

動態多核處理器[18-22]通過重構虛擬核的硬件資源來適應計算需求.Core Fusion[18]融合片上多核處理器(chip multi-core processor, CMP)中多個物理核提供發射寬度可變的虛擬核.TFlex[19]采用EDGE指令集，借助編譯器進行指令調度.DCM(dynamic core morphing)[20]可以根據應用的階段性特征，提供合適的后端完成計算.Voltron[21]實現寬發射的VLIW虛擬核和能進行細粒度通信的多VLIW核雙模式計算.WiDGET[22]根據需求分配合適數量的功能單元來實現與功耗成比例的計算.部分動態多核結構借助編譯器完成靜態指令調度，部分動態多核結構采用基于依賴的動態指令調度.除了動態多核處理器外，其他類型的空間結構[23-26]多借助編譯器完成指令調度.

DFB調度緩存、優化并重用指令調度策略.DIF[27]結構將調度完成的指令組緩存.再次遇到時，指令組由VLIW后端加速執行.Fill unit[28]將執行的指令壓縮并緩存，提高發射帶寬.基于Trace Cache[29]，處理器可以對緩存的指令進行動態優化以提升其執行性能[30].rePLay[31]提出了支持動態優化的框架.

2 空間指令調度問題描述與建模

分簇超標量處理器與動態多核處理器中負責執行指令的流水線后端都可抽象為分區結構.硬件資源由單體實現變為分區實現帶來的變化主要有3點：1)單個分區分得的功能單元減少；2)跨分區傳遞操作數有額外的延遲；3)單個分區的發射隊列變小.分區結構的指令調度可以看作優化問題，嘗試減弱或消除上述3要素導致的性能懲罰，使分區實現接近單體實現的執行效率.

Fig. 3 Scheduling space model for spatial architecture圖3 分區結構的調度空間模型

單個分區的指令發射帶寬、功能單元組成和發射隊列容量等限制指令調度，我們用調度塊(schedule block,ScB)描述這些資源約束.隨著周期的增長，所有分區的ScB構成了矩陣形式的調度空間約束模型，矩陣行坐標T表示指令的預期發射周期，列坐標C表示指令的分區指派，矩陣的第i行第j列的元素ScBij描述了第j個分區在第i個周期的資源約束.空間指令調度為動態指令片段中的指令確定分區指派C，在不違反調度空間約束模型的情況下，盡量減小指令片段調度模式的周期跨度.圖3展示了4分區結構的調度空間約束模型，單個分區每周期可發射2條指令，有2個整型、1個浮點、1個訪存和1個分支功能單元.調度空間約束模型的術語定義如表1所示.

Table 1 Terminology of Schedule Space Constraints Model表1 調度空間約束模型術語

指令I調度到ScBij意味著IssT(I)=i，C(I)=j.指令執行完成周期等于發射周期加上指令的執行延遲ExedT(I)=IssT(I)+Lat(I).舉例說明在調度空間約束模型下如何完成指令調度.如圖3所示，I1依賴I0，假設I1調度到ScBij，則需要滿足4項約束：

E(ScBij)>0，

(1)

F(ScBij)[type(I1)]>0，

(2)

IQ_Load(ScBij)

(3)

(4)

其中，type(I)表示取執行指令I的功能單元類型，IQ_Size是單個分區的發射隊列容量，IPL為分區間延遲.式(1)～(3)為資源約束，式(4)為生產者指令對消費者指令的調度約束.IPL設定為1周期，假設I0調度到ScB00，且Lat(I0)=3，則I1在I0的約束下的調度備選ScB如圖3所示.

如何完成調度使指令序列在調度空間約束模型的T方向上分布盡量窄，即指令調度問題.指令空間調度通過改變指令的C(I)來權衡負載均衡與IPL.已有調度方法考察指令位于關鍵路徑的可能性，然后依照其關鍵性預測做負載均衡和依賴調度2選1的即時決策，我們稱這種定性的決策標準為指令的絕對關鍵性.我們認為依據絕對關鍵性進行調度存在不足，原因有2個：1)實時關鍵性難以準確預測，指令位于不同執行路徑時，其關鍵性存在差異；2)調度決策會反饋影響指令關鍵性，根據依賴進行調度會加重負載的不均衡，根據負載進行調度會使得路徑的延遲增長，非關鍵路徑可轉化為關鍵路徑.

DFB調度根據指令上下文分析其調度裕量，不違反調度空間約束模型生成合理的調度模式并緩存復用.關注指令調度需求與資源約束的互動，通過對比競爭資源的多個指令的調度裕量做出調度決策，我們稱這種定量的決策標準為指令的相對關鍵性.第3節介紹定量描述程序調度需求的數據流約束模型.

3 數據流約束模型

“操作數準備好，指令開始執行.”是數據流計算的基本思想，也為指令調度提供依據.我們在數據流概念的基礎上做出擴展，定義指令的數據流約束為與指令有依賴關系的生產者與消費者指令對指令調度附加的周期約束.數據流約束有2個特點：1)量化約束關系，計算指令的調度裕量；2)參考指令的消費者依賴關系，即反向數據流依賴.傳統指令調度方法逐條完成指令調度，無法參考反向數據流依賴關系，DFB調度緩存并重用指令調度模式，能夠參考指令的消費者對其附加的數據流約束.數據流約束模型的術語的定義如表2所示.

數據流約束的計算舉例如圖4所示.動態指令序列可表示為無環的有向數據流圖，如圖4中①所示，邊表示指令間的依賴關系，邊的權值表示估計的指令執行延遲Lat(I)，虛線框表示指令是Terminal.數據流約束的計算有3步：

1) 按指令序遍歷所有指令，計算得到指令的調度上限sched_ub.如圖4中②所示，I0，I1等沒有生產者指令約束的指令sched_ub為周期0，ExedT(I0)=1且ExedT(I1)=3，則sched_ub(I2)=3.

2) 設置Terminal的sched_lb為其sched_ub，如圖4中③所示，然后逐個遍歷D-Tree追蹤反向數據流依賴關系，更新lb_mat，如圖4中④⑤所示.

3)lb_mat中指令約束最緊值即為指令的sched_lb，(sched_ub，sched_lb)定義指令的調度區間，差值為調度裕量，如圖4中⑥所示.

Table 2 Terminology of Data-Flow Constraints Model表2 數據流約束模型術語

Fig. 4 Data-flow constraints computation圖4 數據流約束的計算

數據流約束描述了程序的細粒度計算需求，調度上下限差值為指令的調度裕量：1)調度裕量量化表示了指令的相對關鍵性強弱，調度裕量越大其相對關鍵性越弱，當多條指令競爭調度資源時，優先滿足相對關鍵性強的指令；2)調度裕量是考慮了調度策略影響的動態指標，當指令跨分區傳遞操作數時，IPL消耗指令的調度裕量，其相對關鍵性得到提升.調度裕量表示的相對關鍵性是與上下文相關的、量化的、動態的指令關鍵性指標.

4 基于數據流塊的空間指令調度的框架

DFB是動態構建、緩存并重用的調度模式.擴展支持DFB調度的處理器微結構框圖如圖5所示.在傳統分區結構的基礎上，添加了DFB構建、緩存和重用的邏輯.DFB調度的實現基于集成數據流緩存的處理器前端設計[32]，該設計解耦合指令轉換與分支預測，DFB Cache利用程序的計算局部性覆蓋大部分的動態指令流，從而降低DFB構建的執行頻率，減少DFB Trainer的功耗開銷.DFB Trainer可以被芯片上多個物理核復用，降低其平均面積開銷.

Fig. 5 Microarchitecture augmented with DFB scheduling圖5 擴展支持DFB調度后的微結構

分支預測器給出取指地址來查詢DFB Cache：1)命中，DFB Scheduler取出緩存的DFB，指導指令的空間調度；2)未命中，DFB Trainer采樣指令，并執行DFB調度算法，將調度模式存入DFB Cache.在程序的計算局部性支持下，經過一段時間的訓練，DFB Cache可以覆蓋大部分的動態指令.

DFB內指令依賴的表示采用前向數據流指針[32]，操作數由生產者指令主動傳遞給消費者指令，DFB Trainer在DFB內插入額外的copy指令完成操作數的跨分區傳遞.指令不需要跨分區廣播操作數或訪問物理寄存器文件.主分區維護ROB(reorder buffer)信息，每個DFB占用ROB的1個空位，當DFB的最后1條指令達到提交階段時，整個DFB一起提交.物理寄存器和ROB的實現不會限制結構的可擴展性.

5 DFB空間調度算法

DFB Trainer使用DFB調度算法，輸入動態指令序列，參照數據流約束模型和調度空間約束模型完成指令調度，輸出指令序列的調度模式.DFB調度算法的目標是在不違反資源限制的前提下，盡量滿足程序的計算需求，生成時間跨度盡量小的調度模式.

在數據流約束表示的指令相對關鍵性的指導下，DFB調度算法對每條指令做依賴調度和負載均衡調度的權衡，為其指派分區.當指令的數據流約束無法滿足時，放寬約束所在D-Tree上指令的sched_lb，繼續嘗試調度當前指令，直到所有指令調度完成.

Fig. 6 Dependence based scheduling constraints圖6 基于依賴的調度約束

5.1 基于依賴的調度

調度依指令序逐條進行，當某指令開始調度時，其生產者指令已經調度完成，對其調度上限構成約束.圖6展示指令I2開始調度的周期，其依賴的指令I0調度在ScB00，I1調度在ScB12.假設Lat(I0)=3，Lat(I1)=1，IPL=1，則I0與I1附加的調度上限約束分別如圖6中虛線和點劃線所示.基于依賴的調度要求IssT(I2)同時滿足2個約束，灰色ScB為備選位置.

考慮I2的相對關鍵性.當I2的調度下限大于周期3時，可以將I2調度到分區0以外，此時I0附加的調度約束如圖7中虛線所示.將I2調度到分區0之外，讓出了分區0的執行機會或者使負載更均衡.

Fig. 7 Scheduling according to relative criticality圖7 依據相對關鍵性進行調度

Fig. 8 Loosen data-flow constraints when needed圖8 適時放松數據流約束

根據依賴關系和相對關鍵性確定了備選ScB后，按照IssT從小到大的順序考察ScB，若找到不違反資源限制約束的且IssT滿足sched_lb要求的ScB開始下條指令的調度;否則，放松數據流約束，繼續嘗試調度當前指令.如圖8所示，I1調度在了ScB22，則sched_lb(I2)=3的數據流約束無法滿足.追蹤約束來源的D-Tree，將對應的Terminal的sched_lb增1，更新lb_mat，計算sched_lb約束，重新嘗試調度I2，重復該過程直到調度成功.

5.2 基于負載均衡的調度

DFB空間調度算法使用調度空間約束模型對功能單元計算能力建模，而采用計數排序的方法應對發射隊列負載均衡的問題，優先考慮指令數少的分區，對于指令數相等的分區，優先調度到最久沒有被使用的分區.根據分區負載確定調度優先級的電路示意圖如圖9所示：

Fig. 9 Priority updating circuit for load balancing圖9 負載均衡優先級更新電路

電路主要維護2組寄存器，CSIZE寄存器組存儲各分區已經指派的指令數量，ORDER寄存器組按負載均衡優先級輸出調度分區編號.DFB開始構建時CSIZE寄存器清0，每調度1條指令，CSIZE寄存器和ORDER寄存器依次變化，更新優先級：1)指令調度的分區號C控制對應的CSIZE寄存器加1；2)更新ORDER寄存器，CSIZE越大的分區優先級越低，CSIZE相等的分區，維持優先級順序.

5.3 算法偽代碼與分析

DFB調度算法依指令序逐條調度指令.調度單條指令分為3步：

1) 根據依賴關系和數據流約束表示的相對關鍵性確定備選ScB；

2) 按照IssT遞增的順序在備選的ScB中嘗試調度指令，相同IssT的ScB依負載均衡優先級調度，若成功則完成當前指令調度；

3) 放松當前指令sched_lb所在D-Tree的約束，并返回步驟1繼續嘗試進行調度.DFB的所有指令調度完成時算法結束.

偽代碼中，n為指令數，nC為分區數，IPL為跨分區操作數傳遞延遲.inst是輸入指令序列，ScB是調度空間模型矩陣，sched_con記錄指令的關鍵消費者;輸出是分區指派C和預期發射周期IssT.算法如下：

算法1. DFB空間指令調度.

輸入:inst[],ScB[][],sched_ub[],sched_lb[],sched_con[]；

輸出:C[0:n-1],IssT[0:n-1].

偽代碼：

函數SCHED_MAIN()

① for all:ORDER[i]=(rr_token+i)%nC；

② for all:CSIZE[i]=0；

③rr_token=(rr_token+P)%nC；

④ for eachiin[0:n-1]

⑤ while (SCHED_INST(i)≠true)

⑥sched_lb[term]++；

⑦recalc_lb()；

⑧ end while

⑨ for eachjin[0:nC-1]

⑩vec.add(CSIZE[ORDER[j]]?4|j?2|ORDER[j])；

函數SCHED_INST(idx)

(ScB[ExedT[src1]][C[src1]] is nearly full‖sched_lb[idx]>ExedT[src1]))yield=true；

inst[idx])

時間復雜度簡要分析如下:函數SCHED_INST調度單條指令，Y1和Y2分別表示2條生產者指令對當前指令的調度上限約束，Y由Y1和Y2共同確定，Y的最小值minY表示當前指令最早的IssT，行～計算的時間復雜度為O(1).Y與sched_lb確定了IssT的取指范圍，各分區最頂部的ScB作為調度目標，算法在硬件實現時可以維護各分區各功能單元的發射機會向量，其與調度范圍求交集后，頂部的ScB即是各分區的候選，對最多nC個備選的ScB，按照小的IssT第1優先，ORDER寄存器第2優先的順序確定調度到的ScB，行～計算的時間復雜度為O(1).所以，SCHED_INST的時間復雜度為O(1).SCHED_MAIN負責指令序列的調度.行⑨～更新負載均衡優先級電路，其時間復雜度為O(n).行④～⑤確定2層循環，行⑤～⑦為最內層循環體，每進行1次約束放松，至少有1條指令的sched_lb增1.任何1條指令的sched_lb不會超過n×(max(Lat)+IPL)，行⑥～⑦進行約束放松為O(n2)次，行⑤調用SCHED_INST的次數等于約束放松的次數加n.因此算法總的時間復雜度為O(n2).

6 實驗評估

6.1 實驗設置

我們為ESESC模擬器[33]添加了DFB調度后運行SPECINT CPU2006測試程序集，使用ref輸入數據.我們略過初始的1億條指令后，模擬1億條指令的連續執行.因為DFB Cache依賴程序的計算局部性，關閉模擬器的采樣執行模式使模擬的動態指令流的計算局部性盡量接近程序實際執行情況.

支持亂序執行的流水線的指令執行性能受到多個結構參數的影響，取指帶寬、指令窗口容量、調度窗口容量、功能單元配置等都會影響程序的執行.為了評估指令空間調度方法，使指令執行性能體現調度方法的差異，我們對結構參數進行了差異化的設置,重點關注3個與指令空間調度方法密切相關的結構參數：分區數、IPL和調度窗口容量.部分結構參數配置如表3所示.ROB、寄存器文件等后端部件使用多端口RAM實現，可擴展性強于調度器，它們的設置根據調度窗口容量和功能單元配置合理設定，盡量減少對性能的影響.

Table 3 Processor Model Configuration表3 處理器模型配置

已有的指令調度方法對指令關鍵性的判定存在差異，但調度策略可以歸為負載均衡和依賴調度2類.我們設置2個參照的調度方法：RR調度輪轉分配指令到各分區，維持負載均衡；DEP調度基于生產者依賴關系調度指令，沒有依賴時按照LRU(least recently used)策略選擇分區;DFB調度即本文提出的依據指令的相對關鍵性構建調度模式并緩存重用的調度方法.

6.2 DFB調度算法的評估與分析

算法評估基于理想DFB調度，假設所有動態指令都被DFB Cache覆蓋.對分區數量、IPL和調度窗口容量3個結構參數，每次變化其中1個，觀察不同調度方法的性能差異.調度效果評價有2個指標：1)每指令周期數(cycle per instruction, CPI)，CPI越低調度效果越好，我們以CPI最低的配置為基準對CPI進行歸一化處理，方便比較；2)調度阻塞率(schedule blocking rate, SBR)，如果調度方法為指令選擇的分區發射隊列已滿，則阻塞流水線，直至調度成功，SBR表示阻塞周期數占總周期數的比率，SBR越小通常調度效果越好.

6.2.1 分區數與調度效果

不考慮分區結構在功耗、時序以及可擴展性等方面存在的優勢.分區越多，單個分區的資源越少，負載不均衡和IPL對性能產生負面影響的可能性越大.我們設置IPL為1個周期，總調度窗口容量為128條指令.分區數為2，4，8的配置下，各調度方法的測試結果分別如圖10～12所示.折線表示程序的CPI，繪制在主縱軸上;柱狀圖表示程序的SBR，繪制在輔縱軸，用百分比表示.

Fig. 10 Experimental result for 2 partitions圖10 分區數為2的實驗結果

Fig. 11 Experimental result for 4 partitions圖11 分區數為4的實驗結果

Fig. 12 Experimental result for 8 partitions圖12 分區數為8的實驗結果

程序的并行性特征不同導致其對調度方法存在偏好.perlbench的ILP有限，指令依賴較多，偏好DEP調度；bzip2的ILP較高，負載均衡壓力大，調度窗口易阻塞，偏好RR調度；omnetpp和xalancbmk在分區數較小時偏好DEP調度，隨著分區數增大逐漸偏好RR調度.不同程序對調度方法的偏好不同，同一個程序對調度方法的偏好也隨分區數改變，所以RR調度和DEP調度之間不存在絕對的性能優劣，適應程序并行性特征的調度方法的調度效果較好.DFB調度量化程序的數據流約束，參照硬件資源約束生成調度模式并緩存重用，可以DFB調度的質量和穩定性優于RR和DEP調度.

Fig. 13 Performance trend with increasing partition count圖13 隨著分區數增加性能的變化趨勢

程序平均性能隨分區數變化的趨勢如圖13所示.隨著分區數增加，CPI和SBR逐漸上升，負載均衡和IPL對性能影響逐漸增大.RR調度有最低的SBR；DEP調度容易導致調度窗口阻塞，SBR較高；DFB調度維持負載均衡的效果弱于RR，但其性能強于RR，說明DFB調度對指令關鍵性把握較好，照顧負載均衡的同時并沒有使得關鍵路徑過多受到IPL的懲罰.

6.2.2 跨區操作數傳遞延遲與調度效果

芯片上的功能單元互相傳遞操作數需要通信網絡.單體實現時，操作數的傳遞延遲為1個周期，但周期較長.分區實現時，鄰近功能單元操作數的傳遞延遲為1個周期，而距離越遠延遲周期數越多，但周期較短.IPL定量描述了功能單元間通信延遲不均勻的程度，比如，分簇超標量處理器中調度到同簇的指令可以背靠背執行，延遲為0周期，跨越簇的邊界廣播操作數，需要1周期.動態多核處理器中虛擬核的物理分區之間傳遞操作數需要配對的復制或同步指令，需要2或3周期.基于片上網絡在更多的核間傳遞操作數的延遲與核間的曼哈頓距離成比例.我們設置總調度窗口容量為128條指令，分區數為8.IPL為1，2，3周期時，各調度方法的測試結果分別如圖14～16所示.

Fig. 14 Experimental result for 1-cycle IPL圖14 IPL為1周期的實驗結果

Fig. 15 Experimental result for 2-cycle IPL圖15 IPL為2周期的實驗結果

Fig. 16 Experimental result for 3-cycle IPL圖16 IPL為3周期的實驗結果

IPL增加會增大跨分區傳遞操作數導致的性能懲罰.RR調度不考慮指令的依賴關系，隨IPL增加性能下降最明顯；DEP調度的SBR隨著IPL增加基本沒有變化，因為存在依賴關系的指令被分到同一分區的概率較高，性能變化較小.

程序的平均性能隨IPL變化的趨勢如圖17所示.DFB調度具有最佳調度效果.隨著IPL增長，調度裕量消耗加快，負載均衡調度的機會減少，調度結果逐漸趨近于DEP調度.

Fig. 17 Performance trend with increasing IPL圖17 隨著IPL增加性能的變化趨勢

6.2.3 調度窗口容量與調度效果

發射隊列影響周期長度.小的發射隊列容易被阻塞導致性能損失.我們設置分區數為8，IPL為1個周期.總調度窗口容量為64，128，256條指令時，各調度方法的測試結果見圖18～20所示.

Fig. 19 Experimental result for 128-entry schedule window圖19 調度窗口大小為128的實驗結果

Fig. 20 Experimental result for 256-entry schedule window圖20 調度窗口大小為256的實驗結果

總調度窗口容量為64時，程序的SBR大幅增加，各調度方法性能損失嚴重.總調度窗口容量從128變為256時：增大的調度窗口為RR調度帶來較小的性能改進；DEP調度效果變差，因為大的調度窗口使指令在做調度決策時有更大幾率分布到其生產者所在分區，這使得負載均衡變差；DFB調度受益于調度窗口容量增長，實際指令發射與執行情況接近DFB緩存的調度模式，從而有較好的調度效果.

隨著調度窗口增大，測試程序平均調度效果的變化趨勢如圖21所示.過小的調度窗口阻塞非常嚴重，RR調度均衡使用所有的分區，其SBR最小，平均性能最好.隨著調度窗口增大，DFB調度的SBR快速下降，性能變化曲線陡峭，受益于調度窗口容量增大最明顯.

Fig. 21 Performance trend with increasing schedule window size圖21 隨著調度窗口大小增加性能的變化趨勢

6.2.4 DFB空間指令調度算法分析小結

通過對分區數、IPL和調度窗口容量的實驗，我們總結出5條規律：

1) 隨著分區數的增加或發射隊列的變小，RR調度逐漸強于DEP調度.

2) 隨著IPL的增加，DEP調度性能穩定，而RR調度性能損失嚴重.

3) 具有不同并行性特征的程序對調度方法存在偏好.同一程序在不同資源配置下對調度方法存在偏好.

4) DFB調度同時參考相對關鍵性這種量化的程序并行性特征與資源約束進行調度決策，其調度效果、適應性和穩定性同時優于RR調度和DEP調度.

5) DFB調度對發射隊列容量敏感，調度效果與調度阻塞率有明顯相關性，采用合理的發射隊列大小或者引入指令預調度技術可以改善DFB調度效果.

6.3 DFB調度實現的評估

DFB Trainer構建DFB有延遲，DFB Cache也不可能覆蓋所有的動態指令.DFB Cache未命中時，DFB Scheduler使用DEP調度.假設DFB Cache最多緩存256個DFB，采用LRU替換策略，DFB Trainer構建DFB的延遲平均為100個周期.圖22展示了該DFB Cache對動態指令的覆蓋率.設置調度窗口容量為128條指令，分區數為8，IPL為1周期，程序執行結果與RR調度、DEP調度以及理想DFB調度的對比如圖23所示.

Fig. 22 Dynamic instruction coverage with the implementation example圖22 示例實現對動態指令的覆蓋率

Fig. 23 Experimental result of the implementation example圖23 示例實現的實驗結果

DFB Cache平均動態指令覆蓋率達到了80%.不同程序的覆蓋率由其計算局部性決定，覆蓋率越高，調度結果越接近理想DFB調度.緩存32 KB指令的DFB Cache的面積開銷約為同等容量的4路組相連ICache的40%，功耗僅為ICache的一半[32].

DFB Cache覆蓋率較低且DEP調度的SBR較大時，示例DFB調度實現的CPI和SBR比理想調度稍差.bzip2和h264ref的調度效果略強于理想調度，SBR稍有降低，這是因為計算局部性較差的指令基本塊被過濾掉，負載均衡優先電路的平衡作用更好.從平均調度結果可以看出，示例DFB調度實現的調度效果強于RR調度和DEP調度，比較接近理想DFB調度.

7 總結與進一步工作

為了解決周期、功耗或可擴展性等方面的問題，分簇超標量處理器與動態多核處理器等微結構使用空間分布的多個硬件分區.分區結構可能受到負載不均衡與跨區操作數傳遞延遲導致的性能懲罰，空間指令調度通過合理分布指令降低這些性能懲罰.已有方法基于指令是否位于關鍵路徑的判斷，在依賴調度和負載均衡調度之間做出權衡.

本文提出了基于數據流塊的空間指令調度.數據流塊是動態構建、緩存并重用的一個或數個順序執行的指令基本塊的調度模式.與已有方法不同，基于數據流塊的調度用調度裕量量化描述程序的并行性特征，根據指令的相對關鍵性進行調度.我們介紹了基于數據流塊的空間指令調度的微結構框架和算法.通過對分區數、跨區操作數傳遞延遲和調度窗口容量等與調度方法密切相關的結構參數的實驗，我們證明了基于數據流塊的空間調度方法的調度效果和穩定性優于負載均衡調度和參考絕對關鍵性的依賴調度.最后舉例證明，與基于數據流緩存的前端設計[32]相結合，以有限的面積與功耗開銷，基于數據流塊的空間調度的調度效果接近理想化調度.

當發射隊列較小導致調度阻塞率上升時，基于數據流塊的空間指令調度的調度效果受到較大影響.指令預調度等時間指令調度方法可以提升發射隊列的使用效率，將來我們考慮綜合使用時間和空間指令調度，進一步提升基于數據流塊的調度方法的適應性.