指令調(diào)度的問題與約束

指令調(diào)度受到多方面的約束，如數(shù)據(jù)依賴約束、功能部件約束、寄存器約束等^[3]^，在這些約束下，尋找到最優(yōu)解，降低指令流水間的stall，就是指令調(diào)度的終極目標。

指令流水間的stall主要由數(shù)據(jù)型冒險、結構性冒險、控制型冒險導致。

• 數(shù)據(jù)型冒險：當前指令的執(zhí)行依賴與上一條指令執(zhí)行的結果。數(shù)據(jù)型冒險共有三種：寫后讀（RAW）、讀后寫（WAR）、寫后寫（WAW）。數(shù)據(jù)冒險可能產(chǎn)生數(shù)據(jù)流依賴。
• 結構型冒險：多條指令同時訪問一個硬件單元的時候，由于缺少相應的資源，導致結構型冒險。
• 控制型冒險：存在分支跳轉(zhuǎn)，無法預測下一條要執(zhí)行的指令，導致其產(chǎn)生的控制型冒險。

編譯器解決上述冒險的方法就是通過插入 NOP 指令，增加流水間的stall來化解冒險。

下面簡單介紹一下三種數(shù)據(jù)型冒險（即數(shù)據(jù)依賴）：

1. 寫后讀（RAW）：一條指令讀取前一條指令的寫入結果。寫后讀是最常見的一種數(shù)據(jù)依賴類型，這種依賴被稱為真數(shù)據(jù)依賴（true dependence）。

   x = 1;
   y = x;
   

2. 讀后寫（WAR）：一條指令寫入數(shù)據(jù)到前一條指令的操作數(shù)。這種依賴被稱為反依賴或反相關（anti dependence）。

   y = x;
   x = 1;
   

3. 寫后寫（WAW）：兩條指令寫入同一個目標。這種依賴被稱為輸出依賴（output dependence）。

   x = 1;
   x = 2;
   

指令調(diào)度算法之表調(diào)度（List Scheduling）

表調(diào)度是一種貪心+啟發(fā)式方法，用以調(diào)度基本塊中的各個指令操作，是基本塊中指令調(diào)度的最常見方法。基于基本塊的指令調(diào)度不需要考慮程序的控制流，主要考慮數(shù)據(jù)依賴、硬件資源等信息。

表調(diào)度的基本思想：維護一個用來存儲已經(jīng)準備執(zhí)行的指令的ready列表和一個正在執(zhí)行指令的active列表，ready列表的構建主要基于數(shù)據(jù)依賴約束和硬件資源信息；根據(jù)調(diào)度算法以周期為單位來執(zhí)行具體的指令調(diào)度，包括從列表中選擇及調(diào)度指令，更新列表信息。

基本的表調(diào)度算法大致分為以下三步：

1. 根據(jù)指令間依賴，建立依賴關系圖。
2. 根據(jù)當前指令節(jié)點到根節(jié)點的長度以及指令的latency，計算每個指令的優(yōu)先級。
3. 不斷選擇一個指令，并調(diào)度它，
   • 使用兩個隊列維護ready的指令和正在執(zhí)行的active的指令；
   • 在每個周期：選擇一個滿足條件的ready的指令并調(diào)度它，更新ready隊列；檢查active的指令是否執(zhí)行完畢，更新active列表。

指令調(diào)度案例^[4]^

本案例選自卡內(nèi)基梅隆大學（Carnegie Mellon University）的Compiler Design課程。

假設當前CPU有兩個計算單元（即每個周期可以執(zhí)行兩條指令）；加法指令的latency為 2 cycles，其他指令為 1 cycle。

1. 根據(jù)數(shù)據(jù)依賴關系構建出依賴關系圖。
   
2. 計算指令節(jié)點優(yōu)先級
   優(yōu)先級計算公式如下：
   其中，表示當前指令節(jié)點，表示的子節(jié)點，表示 "true dependency" ，表示 "anti-dependency" 。
   
   其中 I10 為葉節(jié)點，優(yōu)先級為其latency，故結果為1；I4 為非葉節(jié)點，優(yōu)先級為當前節(jié)點latency（I4 為加法指令，latency為2）+ 子節(jié)點的優(yōu)先級，故結果為3。本例中無反依賴（anti-dependency）情形。
3. 執(zhí)行調(diào)度
   
   在實際執(zhí)行調(diào)度時，對于同等優(yōu)先級的指令，由于具體調(diào)度方案的不同，會出現(xiàn)不同的情況，例如本例中出現(xiàn)的場景，可以通過添加其他度量標準進一步優(yōu)化優(yōu)先級計算方案。盡管表調(diào)度方法不能保證得到最優(yōu)調(diào)度結果，但它是接近最優(yōu)解的。

本文只是簡單介紹了最基本的表調(diào)度方法，在實際應用中，存在各種基于該方法的改進方案。關于LLVM編譯器中的表調(diào)度算法，可以先自行閱讀其源碼，更多相關介紹，敬請期待。

結語

本文簡單介紹了指令調(diào)度的基本概念，指令調(diào)度的原因與影響以及基本的指令調(diào)度算法。

指令調(diào)度作為NP完全問題目前依舊尚未有一個完美的解決方案，對指令調(diào)度算法的探索與優(yōu)化尚有很大的發(fā)展空間。

LLVM之父Chris Lattner認為“編譯器的黃金時代”已經(jīng)降臨^[5]^。隨著計算機架構的復興，未來的N年里將是每一位編譯器工程師大顯身手的時代。

參考

1. Keith D. Cooper, Linda Torczon. Engineering a Compiler (Second Edition).
2. https://zhuanlan.zhihu.com/p/360364235
3. Andrew W.Apple, Maia Ginsburg. Modern Compiler Implementation in C.
4. https://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/L18-Instruction-Scheduling-pre-class.pdf
5. https://zhuanlan.zhihu.com/p/502730940