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

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

指令流水間的stall主要由數(shù)據(jù)型冒險(xiǎn)、結(jié)構(gòu)性冒險(xiǎn)、控制型冒險(xiǎn)導(dǎo)致。

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

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

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

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

   x = 1;
   y = x;
   

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

   y = x;
   x = 1;
   

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

   x = 1;
   x = 2;
   

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

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

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

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

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

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

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

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

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

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

結(jié)語

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

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

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

參考

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