指令調度

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

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

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

數據型冒險

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

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

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

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

算法

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

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

• 將已調度指令所占用的處理器資源記錄下來，若候選指令同樣會占用這些資源，則降低其優先度。
• 若前指令的延遲（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.