指令調度

指令調度(instruction scheduling)是一種代碼優化手段,常見於優化編譯器,其主要功能在於通過加強指令層級的並行運行,使得程序在擁有指令流水線中央處理器上能夠高效運行。換句話說,此手段力求以不改變程序運算結果的方式,完成以下任務:

  • 通過重組指令的運行順序,減少或阻止流水線停頓的發生;
  • 阻止非法操作(即未定義行為)的產生,例如涉及流水線時序、非互鎖資源的等等操作。

其中流水線停頓主要由結構型冒險(受處理器的資源所限)、數據型冒險以及控制流型冒險導致。

數據型冒險

指令調度一般在某基礎塊(basic block)上執行。為了確保指令的運行順序在重組後,其運算結果依舊不變,編譯器的開發者們必須要認識到數據依賴這種概念。數據型冒險總共有三種,其性質恰恰與數據型冒險相符,這三種數據冒險分別是:

  1. 寫入後讀取(RAW, Read After Write) - I1 的輸出值之後會被 I2 使用。
  2. 讀取後寫入(WAR, Write After Read) - I1 的輸入位置之後會被 I2 使用並覆蓋。
  3. 寫入後寫入(WAW, Write After Write) - I1 以及 I2 皆將結果寫入同一個位置上。

其中 I1 以及 I2 是兩個在不同時間點上執行的指令。

對於這三種冒險,指令 I1 都必須執行於 I2 被執行前,否則其運算結果是不被定義的(具體結果視該機器的硬件實現而定)。對於冒險1,這是因為 I2 依賴着 I1 的數據;對於冒險2,則是因為 I1 依賴着即將被 I2 所覆蓋的數據;對於冒險3,則是因為在 I1I2 之間所運行的指令可能會使用到 I1 的輸出結果。為了確保這些數據依賴所需的運行順序得到保證,編譯器首先需要建立一幅依賴圖,即一幅頂點是指令,而是依賴性的有向圖。最終,這幅圖的任何一種拓撲排序都可以是有效的指令調度表。

算法

尋找拓撲排序最簡單且常見的算法是列表調度法,其基本概念是不斷將依賴圖的某個源抽出,並將其添加到現有指令調度表上。在此過程中變成源的其他頂點,也會如前面所言被抽出並進行調度。當這幅依賴圖為空時,算法便會結束。

在這種算法裡,為了優化指令調度表的有效性,以減少流水線停頓等現象的發生頻率,該算法所選擇用於調度的下一條指令尤為重要。為此常用的啟發式有:

  • 將已調度指令所占用的處理器資源記錄下來,若候選指令同樣會占用這些資源,則降低其優先度。
  • 若前指令的延遲(latency)高於前指令與候選指令的距離(即二者的周期差),則降其優先度。
  • 當某候選指令坐落在依賴圖中的某關鍵路徑時,則提高其優先度。這使得這個算法擁有部分向前探查的功能,而不再尋找局部最優解。
  • 如果候選指令能創造大量新源,則提高其優先度。這項啟發式一般能提供調度器更多的調度自由。

執行次序

指令調度可以在寄存器配置之前或之後進行,也可以在寄存器配置之前和之後進行。在寄存器配置前執行指令調度的好處是可以最大化程序的並行性,然而這種做法會有一定的代價,即代碼的寄存器需求量可能會有所增加,而當這個需求量大於處理器所擁有的寄存器時,寄存器溢出便會隨之產生,造成性能影響。

如果該處理器架構不允許某些特定的指令序列組合(一般由於缺乏跨指令互鎖),則指令調度須在寄存器配置發生後才能執行。這種配置法同時也有助於寄存器溢出問題。

如果指令調度在寄存器配置後發生,指令排序可能因寄存器配置器產生的假依賴性而受到一定限制。

類型

指令調度有幾種類型,其中包括了:

  1. 本地(基本塊)調度:指令僅能在其所在基礎塊內移動。
  2. 全局調度:指令能在各基礎塊內移動。
  3. 模算調度:屬於一種軟件流水線的生成算法,通過交叉運行不同的循環達到指令層級並行的效果。
  4. 跟蹤調度:第一種真正實用的全局調度方法,編譯器盡力優化最常被運行的代碼控制流路。[1]
  5. 超塊(superblock)調度: 跟蹤調度的簡化版。

參考

  1. ^ Joseph A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Transactions on Computers. 1981-07, C–30 (7): 478–490. doi:10.1109/TC.1981.1675827.