指令調度
指令調度（instruction scheduling）是一種代碼優化手段，常見於優化編譯器，其主要功能在於通過加強指令層級的並行運行，使得程序在擁有指令流水線的中央處理器上能夠高效運行。換句話說，此手段力求以不改變程序運算結果的方式，完成以下任務：
其中流水線停頓主要由結構型冒險（受處理器的資源所限）、數據型冒險以及控制流型冒險導致。
數據型冒險
指令調度一般在某基礎塊（basic block）上執行。為了確保指令的運行順序在重組後，其運算結果依舊不變，編譯器的開發者們必須要認識到數據依賴這種概念。數據型冒險總共有三種，其性質恰恰與數據型冒險相符，這三種數據冒險分別是：
- 寫入後讀取（RAW, Read After Write） - I1 的輸出值之後會被 I2 使用。
- 讀取後寫入（WAR, Write After Read） - I1 的輸入位置之後會被 I2 使用並覆蓋。
- 寫入後寫入（WAW, Write After Write） - I1 以及 I2 皆將結果寫入同一個位置上。
其中 I1 以及 I2 是兩個在不同時間點上執行的指令。
對於這三種冒險，指令 I1 都必須執行於 I2 被執行前，否則其運算結果是不被定義的（具體結果視該機器的硬件實現而定）。對於冒險1，這是因為 I2 依賴着 I1 的數據；對於冒險2，則是因為 I1 依賴着即將被 I2 所覆蓋的數據；對於冒險3，則是因為在 I1 和 I2 之間所運行的指令可能會使用到 I1 的輸出結果。為了確保這些數據依賴所需的運行順序得到保證，編譯器首先需要建立一幅依賴圖，即一幅頂點是指令，而邊是依賴性的有向圖。最終，這幅圖的任何一種拓撲排序都可以是有效的指令調度表。
算法
尋找拓撲排序最簡單且常見的算法是列表調度法，其基本概念是不斷將依賴圖的某個源抽出，並將其添加到現有指令調度表上。在此過程中變成源的其他頂點，也會如前面所言被抽出並進行調度。當這幅依賴圖為空時，算法便會結束。
在這種算法裏，為了優化指令調度表的有效性，以減少流水線停頓等現象的發生頻率，該算法所選擇用於調度的下一條指令尤為重要。為此常用的啟發式有：
- 將已調度指令所佔用的處理器資源記錄下來，若候選指令同樣會佔用這些資源，則降低其優先度。
- 若前指令的延遲（latency）高於前指令與候選指令的距離（即二者的周期差），則降其優先度。
- 當某候選指令坐落在依賴圖中的某關鍵路徑時，則提高其優先度。這使得這個算法擁有部分向前探查的功能，而不再尋找局部最優解。
- 如果候選指令能創造大量新源，則提高其優先度。這項啟發式一般能提供調度器更多的調度自由。
執行次序
指令調度可以在寄存器配置之前或之後進行，也可以在寄存器配置之前和之後進行。在寄存器配置前執行指令調度的好處是可以最大化程序的並行性，然而這種做法會有一定的代價，即代碼的寄存器需求量可能會有所增加，而當這個需求量大於處理器所擁有的寄存器時，寄存器溢出便會隨之產生，造成性能影響。
如果該處理器架構不允許某些特定的指令序列組合（一般由於缺乏跨指令互鎖），則指令調度須在寄存器配置發生後才能執行。這種配置法同時也有助於寄存器溢出問題。
如果指令調度在寄存器配置後發生，指令排序可能因寄存器配置器產生的假依賴性而受到一定限制。
類型
指令調度有幾種類型，其中包括了：
- 本地（基本塊）調度：指令僅能在其所在基礎塊內移動。
- 全局調度：指令能在各基礎塊內移動。
- 模算調度：屬於一種軟件流水線的生成算法，通過交叉運行不同的循環達到指令層級並行的效果。
- 跟蹤調度：第一種真正實用的全局調度方法，編譯器盡力優化最常被運行的代碼控制流路。[1]
- 超塊（superblock）調度： 跟蹤調度的簡化版。
參考
- ^ 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.