章節.3 指令階層架構平行與其利用

1. 指令層級平行(Instruction-Level Parallelism,ILP)的概念與挑戰

現在的處理器都支援流水線執行，事實上流水線執行就是利用了ILP的特性，將指令執行的時間重疊起來，使程式執行得更快。

利用ILP的方法主要有兩種:

  • 利用硬體來動態的發現並利用程式內的ILP特性
  • 利用編譯器來發現程式內的ILP特性，並透過重新編排其指令順序來加速程式執行

以下為流水線CPI的公式: $CPI_{pipeline}=CPI_{ideal\ pipeline}+stalls_{structural\ harzard}+stalls_{data\ harzard}+stalls_{control\ harzard}$

目前有以下方法來減少stalls所耗的時間:

Technique Reduces
Forwarding and bypassing Potential data hazard stalls
Delayed branches and simple branch scheduling Control hazard stalls
Basic compiler pipeline scheduling Data hazard stalls
Basic dynamic scheduling (scoreboarding) Data hazard stalls from true dependences
Loop unrolling Control hazard stalls
Branch prediction Control stalls
Dynamic scheduling with renaming Stalls from data hazards, output dependences, and antidependences
Hardware speculation Data hazard and control hazard stalls
Dynamic memory disambiguation Data hazard stalls with memory
Issuing multiple instructions per cycle Ideal CPI
Compiler dependence analysis, software pipelining, trace scheduling Ideal CPI, data hazard stalls
Hardware support for compiler speculation Ideal CPI, data hazard stalls, branch hazard stalls

basic block（被Branch或是jump斷開的程式碼區段）中指令所能提供的平行度並不高，故為了要盡可能得到平行化的優點，我們必須透過橫跨數個basic block來開發平行。

提高ILP最常見且最簡單的方法，就是於迴圈裡每次迭代間來開發平行，這類的平行稱為循環層級平行(loop-level parallelism)，譬如說：

    for( i=0; i<999; i++ )
        z[i]=x[i]+y[i];

因為每次迭代的資料跟上一次的資料並沒有關係，故每次迭代可以跟其他次迭代並行。

事實上這種loop-level parallelism，在現在也常利用向量處理器或是GPU來處理，達到執行時間與指令數減少的結果。

  1. 相依和衝突 在實現IPL的過程中，我們必須確保指令符合在執行的過程中不會有相依與衝突發生，不會導致流水線停頓（假設不會發生資源不足而出現結構衝突）。

    1. 相依 相依可以細分為三種
      • 資料相依(Data dependence):也稱為true data dependence
      • 名稱相依(Name dependence)
      • 控制相依(Control dependence)
      1. 資料相依(Data dependence) 如果滿足以下兩個條件，則我們說指令i與指令j相依：
        • 指令i生成的結果，指令j會用到
        • 指令j的資料與指令k相依，而指令k又跟指令i相依

        第二個條件的長度可以非常長，而這一連串的指令我們稱為相依鏈(dependence chain)。 如果兩個指令是資料相依，則指令必須要依序執行。

        相依是程式的特性，資料相依傳達了三個資訊：

        • 衝突發生的可能性
        • 計算結果所需遵循的指令順序
        • 平行程度的上限

        資料相依性可透過下列兩種方法解決：

        • 保護相依性但避免發生停頓
        • 透過移動程式碼來消除相依性
      2. 名稱相依(Name dependence) 當兩條指令使用同個記憶體位置或是同個暫存器，但沒有資料的流動的情形則稱為名稱相依，名稱相依又可在細分為：

        1. antidependence: 當指令j對指令i所讀取的記憶體或是暫存器做寫入動作，則稱為antidependence

        2. output dependence: 當指令i和指令j都會同一個記憶體或是暫存器做寫入動作，則稱為output dependence

        因為名稱相依並沒有真實的資料流動，故它們並非真實的相依，可以透過一些方法來並行這些指令。重新命名是最常見的一個方法，對暫存器重新命名的方法稱為register renaming。

      3. 控制相依(Control dependence)
        1. 條件
          • 如果一條指令跟branch控制相依，則這條指令不能在 branch之前被執行。
          • 如果一條指令跟branch控制不相依，則這條指令不能在branch之後被執行。

        2. 討論: 但實際上，為了提升速度，有時我們也會某些程度的違反控制相依，故一般標榜可以處理資料相依和控制相依的機器，僅僅保證資料流與例外的表現與循序執行的情況一樣。

        3. 名詞:
          • data flow : 真實的資料流動(result & comsume)
          • liveness: 資料是否在後面的指令還會用到，如果後面指令不會用到，則稱這筆資料dead。
    2. 資料衝突(Data Harzard) 如果相近的指令有資料相依或名稱相依，則就有可能會發生資料衝突，在有可能導致資料衝突的情況下，指令必須要依序的執行，故必須要有預先檢測衝突機制。 衝突依照原先的執行順序可以分成四種:
      • RAW(Read After Write): 最常見的harzard，由於是true dependence，故一定要維持指令原先的順序執行。
      • WAW(Write After Write): 僅發生在pipeline中，write的部分超過兩個stage的架構中。
      • WAR(Write After Read): 通常是來自Name dependence，但值得注意的是，這個harzard並不容易出現，因為在一般的pipeline架構中，read所在的stage要先於write所在的stage
      • RAR(Read After Read): 不會有harzard產生

2. 針對ILP的基本編譯器技術

為了增加平行度，編譯器要盡可能將指令間的相依性找出來並做scheduling，編譯器最常用的方法就是loop unrolling，以下為loop unrolling的範例：

for (i=999; i>=0; i=i–1)
    x[i] = x[i] + s;

MIPS指令：

pipeline MIPS:

loop unrolling：

我們可以發現經過loop unrolling後指令所需要的停頓減少了，loop本身的overhead也減少了。

在實現loop unrolling時有幾個部份需要注意：

  • 每個iteration是否獨立，若否，則不應使用
  • 使用不同的暫存器，同時在實現的過程中也該把暫存器考量進去
  • 消除額外的測試跟分支的指令並調整迴圈的終結條件
  • 觀察指令並調整指令順序，因為每個iteration是獨立的，故不同的iteration的load跟store可以自由交換指令順序。
  • 必須保證其執行結果跟原先程式的執行結果相同。

有些存在的限制會限制loop unrolling加速的效果：

  • 當展開越多iteration，loop overhead減少的數量就越少： 因為更新後的每次iteration需要loop overhead還是一樣，只差在總共要做幾次iteration。
  • code size:程式碼的大小有限制
  • compiler limitation:太過複雜的scheduling，會使編譯器變得難以設計
  • register pressure:暫存器的數量不夠，故展開的程度有限制

3. 用進階的分支預測來減少分支成本：

  1. 相關性分支預測器(Correlating Branch Predictors): 用其他分支的表現（可能也包含自己這個分支）來做預測的的預測器稱為：Correlating Branch Predictors或two-level Branch Predictors

    通常以(M,N) Predictors表示，其表示利用最近的M個branch的taken/not taken所構成的pattern，由這個pattern來選擇要看那一個branch-prdicttion buffer，而branch-prdiction buffer的每一個entries都是N bit的counter。

    為了實做方便，一般是實現一個global branch history的shift register，這個shift register就存入最近這個branch是taken/not taken。 Correlating Branch Predictors

  2. 錦標賽分支預測器(Tournament Branch Predictors): Tournament Branch Predictors是一種混合型的預測器，通常它利用兩個預測器，透過看哪一個預測器對該分支的預測較準確，就選擇該預測器的結果。 下圖是alpha 21264 它會針對每一個branch維護一個2bit飽和計數器，用來選擇要選那一個預測器，這個計數器必須要連續兩次選擇錯誤才會將狀態移到另外一個預測器，在alpha 21264的Tournament Branch Predictors中，它內部的兩個預測器分別是：

    • local predictor: 其中有個local history table，table大小為$1024\times10bits$，每個entry會紀錄最近十次PC對應到這個entry的branch的taken/untaken的資訊，接著在用這10個bits當index去找local預測器預測的值，其中每個預測器都是利用3個bit的飽和計數器實做。

    • global predictor: 由12個bits的global history來當index來找globall預測器預測的值，其中每個預測器都是利用2個bit的飽和計數器實做。

    • meta predictor(choice prediction)：用來決定要以那個predictor（local或global）的結果來當預測結果，圖上的meta predictor只是其中一種用法（也用利用PC當index的用法）。

4. Tomasulo’s Alogrithm

  1. 動態排程(Dynamic scheduling)的優點
    1. 針對不同機器編譯出來的程式碼，在不同的機器一樣可以跑得好
    2. 因為我們在編譯期間不知道程式內的真實相依性
    3. 編譯器可以比較容易設計
    4. 可以一定程度的容許不可預料的delay，因為這些在等待的時候，處理器可以同時處理其他指令

  2. 不精確中斷(imprecise exceptions) 有關於精確中斷(Precise Interrupts)詳細可見：附錄C.4.1

    動態排程有可能導致不精確中斷的發生，不精確中斷指：程式發生中斷時的處理器的狀態與循序執行時發生中斷時的狀態不同，則稱為不精確中斷。

    不精確中斷發生的原因有二：

    • 理論上要在例外發生的位置之後的指令先被完成
    • 理論上要在例外發生的位置之前的指令尚未完成

  3. 利用Tomasulo’s Alogrithm做動態排程 我們在附錄C.7有介紹Scoreboard這一個動態排程的技術，這邊我們則探討利用Tomasulo’s Alogrithm做動態排程。

    1. 差異：
      • Tomasulo’s Alogrithm利用renaming的方式消除antidependence和output dependence
      • Tomasulo’s Alogrithm可以處理預測(speculation)

    2. 作法

      • instuction queue: 用來buffer instuction

      • Reservation stations: Tomasulo’s Alogrithm在每一個functional unit上都加上Reservation stations，用來紀錄那些還要等待的運算元，紀錄的方法並非是直接紀錄其register的名字，而是紀錄他在那一個buffer或是Reservation stations上，透過這個方法可以達到register renaming的功效

      • load buffer: load buffer可以用來儲存尚未完成的load指令

      • store buffer: store buffer可以用來儲存尚未完成的store指令

      • Common data bus(CDB):用來連接每一個functional unit與store buffer和Reservation stations(因為load buffer不會讀取別的指令所產生的結果當運算元，故不須連接到CDB)

      其中buffer和Reservation stations都有tag用以紀錄其是否忙碌(busy)

    3. 特性 因為利用分散的Reservation stations而非集中管理的暫存器集，使得Tomasulo’s Alogrithm有以下特性：
      1. hazard的偵測跟執行控制是分散式的
      2. 資料不是直接透過暫存器傳給functional unit，而是透過Reservation stations傳給functional unit

      因為利用CDB廣播資料使得Tomasulo’s Alogrithm有以下特性：

      1. 無形間實作了bypassing
    4. 流程：
      1. issue:

        1. 從instuction queue pop一個指令出來

        2. 判斷指令對應的functional unit的Reservation stations是否有空間 如果有：則將它issue到Reservation stations，並檢查其運算元是否可用，如果可用則填入，如果不行則紀錄是要等哪個位置的指令處理好，去追蹤它是否完成，傳道CDB。 如果沒有：則代表發生結構衝突(structural hazard)，需要停頓

      2. execute:

        1. 如果Reservation stations 裡面中的指令的運算元尚未準備好，則去偵測CDB 裡面中的指令的運算元準備好，則去執行

        2. 為了保證例外處理的表現，任何在分支之後的指令在分支預測的結果確認之前，不能被完成。

      3. write result:
        1. 執行完畢將結果傳到CDB，在從CDB傳給需要用到的地方。

    5. 範例： 每個Reservation stations有七個欄位：

      • Op—The operation to perform on source operands S1 and S2.
      • Qj, Qk—The reservation stations that will produce the corresponding source operand; a value of zero indicates that the source operand is already available in Vj or Vk, or is unnecessary.
      • Vj, Vk—The value of the source operands. Note that only one of the V fields or the Q field is valid for each operand. For loads, the Vk field is used to hold the offset field.
      • A—Used to hold information for the memory address calculation for a load or store. Initially, the immediate field of the instruction is stored here; after the address calculation, the effective address is stored here.
      • Busy—Indicates that this reservation station and its accompanying functional unit are occupied.

      範例可參照此投影片

5. Tomasulo’s Alogrithm with speculation

  1. 硬體分支預測(hardware speculation) hardware speculation有三個關鍵的重點：
    1. 用動態的分支預測來選擇要執行哪些指令
    2. 允許在結果確定前先對預測指令做執行
    3. 利用dynamic scheduling來應付不同basic block的組合

  2. Tomasulo’s Alogrithm with speculation 為了要在Tomasulo’s Alogrithm中支援speculation，這邊我們需要將bypassing分離出來，使其預測的指令能夠運用尚未完成的指令結果，但又因為這些執行的指令僅是預測的，故不行執行那些不能撤銷的更新動作，因此我們多增加了一個步驟-提交（commit），這個步驟是指當分支結果被確定，則將指令結果寫入暫存器或是memory中。

    這邊實現的關鍵點在於：我們允許其亂序執行(execute out of order)，但它必須循序提交(commit in order)，故這邊的作法是添加一個緩衝區稱為：Reorder buffer(ROB)，用以保存執行完畢但還未提交的指令結果。

  • Reorder buffer:
    • 因為他的作用類似Tomasulo’s Alogrithm中的store buffer，故我們將store buffer的功能與Reorder buffer整合起來。
    • register與memory的值必須要等到instruction commit之後才會做更改，如果發現之前的分支預測錯誤的話：則必須要把ROB內預測所運算的結果做清除。

    • 在發生例外(exceptions)時，我們會等到發生例外的指令到達ROB的Head時，才將他釋放出來，這可以使其執行為precise。

    • 其中含有四個欄位：
      • 指令類型： branch/store/register
      • 目的地: register number
      • 值: output value
      • ready or not: completed execution?
  1. 步驟：
    1. Issue:
      1. 從instuction queue pop一個指令出來
      2. 如果對應的reservation station和ROB中的entry為空則issue指令，不然，就stall
      3. 從對應的register或ROB取得運算元資料
    2. Execute:
      1. 如果運算元都準備好，則執行指令，不然則追蹤CDB的資訊
      2. 如果是store指令，則先計算之後要存儲的有效位置
    3. Write result:
      1. 如果結果可用，則將其寫到CDB上，寫到ROB或是需要此結果的reservation station，如果是store指令，則將執行完成的指令寫到ROB中。
      2. 將reservation station標記為non-busy
    4. Commit: 這邊依照不同指令的類型，分成三種處理方式：

      • normal case: 不是store或branch則歸於這一類，這一類指令的commit，就在它達到ROB的head時將資料寫入register

      • store: 與normal case類似，只是目的地變成了memory

      • branch: 直到branch的結果確定時才將結果做commit，否則則捨棄那個結果。

6. Exploiting ILP using Multiple Issue & Static Scheduling

  1. 為了使CPI<1，傳統上一次issue一個指令的技術顯然無法達到這個目標，故我們發展了Multiple Issue的技術，這類處理器，我們稱為Multiple Issue processors，其可以在細分為：
    • Statically scheduled superscalar processors
      • 每個週期issue不定數量的的指令
      • 循序執行
      • 依靠compiler來作scheduling
      • issue的指令越多優點越不明顯
    • VLIW(Very Large Instruction Word) processors
      • 每個週期issue固定數量的的指令
      • 有兩種實作模式：
        • 一次執行一個長指令（可以在進行分割）
        • 一個指令組
      • VLIW由compiler來作scheduling
      • Intel與HP有基於VLIW進行改進，發展了IA-64的架構，支稱之為EPIC
    • Dynamically scheduled superscalar processors
      • 每個週期issue不定數量的的指令
      • 亂序執行

    延伸閱讀:superscalar

  2. VLIW(Very Large Instruction Word) processors
    1. Instruction scheduling 其scheduling由compiler負責，compiler會根據其程式碼能達到的平行度，來規劃指令的執行順序，一般Instruction scheduling我們可以初略分為：
      1. Local (Basic Block) Scheduling: instructions can’t move across basic block boundaries.
      2. Global scheduling: instructions can move across basic block boundaries.

      而針對VLIW，compiler領域發展一個技術稱為Trace scheduling可用來做VLIW的scheduling。

    2. 缺點
      1. 程式碼大小 VLIW會使程式碼大小變大，原因有二：
        1. 為了要提高平行度，必須unrolling loop，而這樣的作法會使程式碼大小變大
        2. 如果長指令內部未填滿，則會有些部份是被空指令所佔據的 為了解決這些情形，有些編碼方式被引入
      2. binary code compatibility 因為VLIW除了指令集外，牽扯到硬體實作部份，故其binary code compatibility一般很差，在不同的VLIW processor需要不同的binary code。
    3. 優點 相對於vector processor，multiple-issue processor速度不一定會比較快，但是針對於平行度較低的的程式碼，multiple-issue processor的平行效果可能更好。

7. Exploiting ILP using Multiple Issue, Dynamic Scheduling & Speculation

每個cycle issue多個指令並不容易實作，因為指令間可能有相依性。

  1. 作法

    為了要實現Multiple Issue，有兩種常見的作法：

    1. 將assigning a reservation station和updating the pipeline control tables分別以半個cycle完成： 如此一來，就能在一個cycle issue兩個指令，但這方法的限制也相當明顯，很難可以讓每個cycle的issue的指令數>2

    2. 引入必須的邏輯電路： 像是增加運算單元以及針對不同指令相依性處理的電路等…，使同時issue多個指令變成可能，需要注意的是針對不同指令相依性處理的電路會隨著所支援的issue/cycle數增加而成指數成長，故issue這個stage一般來說是 Multiple Issue cpu 設計的瓶頸所在

      • 而針對 n issues/cycle的dynamically scheduled superscalar我們可以依照以下幾步驟處理：

        1. 為下一個cycle可能會issue的指令群(issue bundle)中的指令指定Reservation station與ROB，先檢查是有足夠的空間放入這些指令（先不管指令類型），如果可以，再依據可以一次issue的指令類型做issue（看其運算單元支援同時做哪些類型的運算，而ROB的部份則直接放入），接著將滿足的指令放入指定Reservation station，如果不滿足條件的指令則等下一個cycle再issue。

        2. 分析在issue bundle中指令的的相依性

        3. 如果issue bundle中指令相依於issue bundle中前面的指令，則依其順序放入ROB中，否則則依照前兩個步驟的結果

8. Advanced Techniques for Instruction Delivery and Speculation

  1. 增加instruction fetch的頻寬：

    1. 分支目標[緩衝/快取](Branch-Target Buffers): 為了增加instruction fetch的頻寬，僅僅是branch prediction是不夠的，必須要知道branch之後可能的PC為多少，故Branch-Target Buffers/Branch-Target Caches就隨之而生。

      Branch-Target Buffers 可以根據現有的PC去查表，如果他是Branch且在表中，則去看他的branch prediction的結果，在由結果看是否去fetch Predicted PC，以下是詳細的流程圖。

      故branch penalty為(假設Branch-Target Buffers僅儲存taken的Predicted PC，且運作在5級流水線結構中)：

    2. 返回位址預測器(Return address predictors) 因為程式中indirect jump的佔的比例也不少，而indirect jump大部分又是來自程序的返回(procedure returns)，雖然也可以利用Branch-Target Buffers來處理這個部份，但會因程序在多個地方呼叫而正確率偏低，為了解決這個問題，一些架構使用了一個小型的stack來緩衝return address，如果這個stack夠大的話，它就能準確的預測return的位址。

    3. 集成指令提取單元(Integrated Instruction Fetch Units) 為了滿足multiple issue processor的需求，許多設計者實現集成指令提取單元來提昇fetch指令的頻寬。 Integrated Instruction Fetch Units可以包含下列幾個部份：

      1. Integrated branch prediction： branch prediction持續的預測branch指令

      2. Instruction prefetch： 詳細的情形見2.2

      3. Instruction memory access and buffering： 因為fetch多條指令可能需要存取多條cache，故利用這個部份封裝實做的複雜性。

  2. Speculation: Implementation Issues and Extensions 這邊探討幾個在作Speculation的問題

    1. Speculation Support: Register Renaming versus Reorder Buffers 我們可以利用一組大量實體存在的暫存器搭配register renaming來取代ROB的使用，這種方式是Tomasulo’s algorithm的擴展，利用擴展的暫存器來取代ROB的功能(維持一個queue)，在做指令issue，renaming程序將架構上的暫存器與實際暫存器做對應，其實做一儲存對應的table稱：register allocation table(RAT)/register renaming table，透過目標register renaming，WAW和WAR hazards都能夠被排除。 而在指令commit之前，資料都是由實體暫存器所儲存，commit之後，才會將其實體暫存器變成架構上的暫存器表示（此時架構上的暫存器才看得到我們要存的資料），由此，可以解決Speculation Recovery（預測錯誤需要回復暫存器狀態的動作）。 renaming map是一個資料結構，用來儲存實體暫存器跟架構暫存器的對應，只有在commit時，對應才會被永久性的更新(移除暫存器的對應也在同個時間)。

      與ROB相比，renaming approach有一個優點就是減化了指令commit的動作，使它僅需要兩個簡單的動作：

      1. 紀錄結構暫存器的和實體暫存器的對應不再是預測結果
      2. 釋放所有用以保存結構暫存器舊值的實體暫存器

      而在Register Renaming中，在釋放實體暫存器之前必須要：

      1. 確認實體暫存器與架構暫存器不再有相關性
      2. 確定針對實體的暫存器處理已經完成
      3. 其不為之後指令的source register 滿足這幾點才能回收該實體暫存器，故有另一種較容易實現的方法： 直接等到另一個寫入目標為同一個架構暫存器的指令commit才去作實體暫存器的回收

      在Register Renaming的架構上，我們實現multiple issue指令的策略與使用reorder buffer的架構相仿：

      1. 為下一個cycle可能會issue的指令群(issue bundle)預留足夠的實體暫存器

      2. 分析在issue bundle中指令的的相依性，如果存在相依性，則需要利用Renaming table查詢該由那一個實體暫存器來儲存資料，如果不存在相依性，則Renaming table則已儲存正確對應的實體暫存器編號

      3. 如果issue bundle中有指令相依於issue bundle中前面的指令，則為了issue指令，將使用在其中存放結果的預留實體暫存器來更新資訊

    2. Speculation的代價 Speculation提供了很多優點，但同時它也有許多的缺點：
      • 增加power
      • 增加晶片面積（成本）
      • 當預測錯誤時，會降低CPU效能 為了要保留大部分Speculation的優點，減少缺點造成的影響，一般來說，我們僅在例外情形成本低的情況使用Speculation（像是L1 cache miss），因為如果猜錯的話，所造成的效能損耗可能相當可觀。
    3. 多分支預測(Speculating through Multiple Branches) 有幾個情況，多分支預測可以大幅增加效能：
      1. 分支出現頻率非常的高
      2. 分支高度密集
      3. functional unit的延遲很長

      目前愛逾期複雜度，還沒有處理器可以在同個cycle預測多個分支。

    4. Speculation and the Challenge of Energy Efficiency 預測的能量損耗有三個來源：
      1. 做預測
      2. 做預測但其實不需要預測結果
      3. 預測失敗，還原狀態
    5. Value Prediction 值預測是指我們可以預測指令所產生的數值，但經過多年努力，目前仍無有效的值預測方法，但有個相關的想法已經廣泛的使用（相對容易實做）—位址別名預測(Address aliasing prediction)，他的想法是預測兩個load/store所參考的記憶體位址是否相同，如果不同，表示兩者無相關性，則可以隨意交換次序。

9. ILP 限制

在完美模型下的ILP限制有下列幾項：

  1. WAW and WAR hazards through memory: 雖然透過register renaming 可以消除register部份的WAW and WAR hazards，但卻無法消除記憶體部份的WAW and WAR hazards

  2. Unnecessary dependences
  3. Overcoming the data flow limits

參考資料： John L. Hennessy, David A. Patterson. “Computer Architecture: A Quantitative Approach, 5/e”, Chapter 3

Slides From Hsien-Hsin Sean Lee (Member of School of Electrical and Computer Engineering Georgia Institute of Technology)

Wikipedia contributors. “Instruction scheduling.” Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 6 Jan. 2018. Web. 13 Feb. 2018.