第4章 指令級並行
需要掌握的內容和概念：
指令級的並行
指令的靜態排程技術
指令的動態排程技術
迴圈展開排程技術
程式中的資料相關、名相關、控制相關定義
指令的動態排程最常用的兩種硬體策略：記分牌技術和Tomasulo演算法
指令多流出技術：超標量技術、超流水技術和超長指令字技術
根據所學的指令排程技術分析和設計指令的排程
應用問題：
應用指令排程技術分析和設計指令的排程，計算效能
主要內容
指令級並行的概念
指令的動態排程
控制相關的動態解決技術
多指令流出技術
主要內容
（1）指令的靜態排程包括迴圈級並行的處理、暫存器換名和指令排程等。是由編譯器完成的靜態排程處理技術。
（2）指令的動態排程包括目前最常用的記分牌和Tmasulo演算法。
（3）解決控制相關的技術，理解分支預測緩衝技術、分支目標緩衝技術和前瞻執行技術。
（4）多流出技術是實現每個時鐘週期中流出多條指令的必由之路。
指令級並行的概念
指令之間不存在相關時，它們在流水線中是可以重疊起來並行執行的。這種指令序列中存在的潛在並行性稱為
指令級並行（Instruction-Level Parallelism,ILP）
流水線處理器的實際CPI（平均每條指令使用的週期數）等於理想流水線的CPI加上各類停頓引起的週期數的總和：
迴圈展開排程的基本方法
指令排程
就是透過改變指令在程式中的位置，將相關指令之間的距離加大到不小於指令執行延遲的時鐘數。
指令排程是迴圈展開的技術基礎，編譯器在完成這種指令排程時，受限於：1。程式固有的指令級並行性；2。流水線功能部件的執行延遲。
迴圈展開和指令排程時要注意：
保證正確性
注意有效性
使用不同的暫存器
儘可能地減少迴圈控制中的測試指令和分支指令
注意對儲存器資料的相關性分析
注意新的相關性
相關性
資料相關（Data Dependence）
對於指令
和指令
，如果指令
使用指令
產生的結果或者指令
與指令
資料相關，指令
與指令
資料相關，則指令
與指令
資料相關。
傳遞性
先寫後讀鏈
硬體可以採用
互鎖（Interlock）機制
，也就是一旦硬體檢測到某條指令與前面正在流水線中執行的指令存在資料相關，則停止本指令的執行，插入空轉週期，知道前面執行指令的結果可用為止。
如果定義指令的相關距離（Distance）為兩條指令之間的指令條數，則分析資料相關的主要工作如下：
確定指令的相關性，找到所有可能產生停頓的地方
確定必須嚴格遵守的資料的計算順序
確定指令的最大相關距離，確定程式中可能的最大並行性
另一個需要判斷的還有是發生在暫存器還是儲存器。
名相關（Name Dependence）
指令使用的暫存器或儲存器稱為名。如果兩條指令
使用相同的名
，但它們之間並
沒有資料流
，則稱之為
名相關
。
1）
反相關（Anti-dependence）
：指令
先執行，指令
寫的名是指令
讀的名。（先讀後寫相關）
2）
輸出相關（Output Dependence）
：指令
和指令
寫相同的名。（寫後寫相關）
與資料相關比較，名相關的指令之間沒有資料交換。可以透過改變指令中運算元的名消除名相關，即
換名（Renaming）技術
。對於暫存器運算元進行換名稱為
暫存器換名（Register Renaming）
。
控制相關（Contol Dependence）
由分支指令引起的相關，需要根據分支指令執行的結果來確定後續指令執行的順序。
處理原則：
1）與控制相關的指令不能移到分支指令之前，即控制有關的指令不能排程到分支指令控制範圍之外。
2）與控制無關的指令不能移到分支指令之後，即控制無關的指令不能排程到婦女之指令控制範圍之內。
指令的動態排程
依靠編譯器確定並分理處程式中存在相關的指令，然後進行指令排程，並對程式碼進行最佳化，這個過程稱為
靜態排程
。
另外一種稱為
動態排程
，透過硬體重新安排指令的執行順序來調整相關指令實際執行時的關係，減少處理器空轉。
動態排程的原理
對指令譯碼階段的工作進一步細化，將指令結構阻塞檢查和等待資料阻塞解釋分為兩部分，只要沒有結構阻塞指令就可以流出，資料就緒就可以執行。執行時可以亂序（out of order execution），因此指令的結束也是亂序的。
為了允許亂序執行，將基本流水線的譯碼階段再分為以下兩個階段：
1）流出（Issue，IS）：指令譯碼，檢查是否存在結構阻塞。
2）讀運算元（Read Operands，RO）：當沒有資料相關引發的阻塞時就讀運算元。
指令流出之前先被取至指令佇列中，一旦滿足流出條件，指令就從佇列中流出。這樣分段處理，就可以同時並行執行多條指令。執行階段緊跟在讀運算元之後，和基本流水線的結構以及工作過程相同。
動態排程演算法之一：記分牌
在動態排程流水線中，所有的指令在流出（IS）階段是順序的（In-Order Issue），但是在第二階段讀運算元（RO）時，只要指令所需的資源滿足並且沒有資料阻塞，就應該允許指令亂序執行。記分牌（Scoreboard）技術就是這樣一種方法。
每條指令均經過記分牌，並記錄下各條指令間資料相關的資訊，這一步對應於指令流出，部分取代MIPS的指令譯碼（ID）階段的功能。然後記分牌就需要判斷什麼時候指令可以讀到所需的運算元，開始執行指令。如果記分牌判斷出一條指令不能立即執行，它就檢測硬體的變化從而決定何時能夠執行。記分牌還控制指令寫目標暫存器的時機。
每條指令在流水線中的執行過程可分為指令的流出 讀運算元、執行和寫結果等四段，由於主要考慮浮點操作，因此不涉及儲存器訪問段。
流出（Issue,IS）
。若本指令所需的功能部件有空閒，且其他正在執行的指令使用的目的儲存器於本指令的不同，記分牌就向功能部件流出本指令，並修改記分牌內部的資料記錄。
讀運算元（Read Operation,RO）
。記分牌需要監測源運算元暫存器中資料的有效性，如果前面已流出的還在執行的指令不對本指令的源運算元暫存器進行寫操作，或一個正在工作的功能部件已經完成了對這個暫存器的寫操作，則此運算元有效。解決了RAW相關。
執行（Execution,EX）
。取到運算元後就開始執行指令。
寫結果（Write Result,WR）
。記分牌知道指令執行完畢後，如果目標暫存器空閒，就將結果寫入到目標暫存器中，然後釋放本指令使用的資源。
記分牌需要記錄的資訊分為三部分：
指令狀態表
：記錄正在執行的各條指令已經進入記分牌MIPS流水線四段中的哪一段；
功能部件狀態表
：記錄各個功能部件的狀態。每個功能部件在狀態表中都由以下9各域來記錄：
Busy：指示功能部件是否在工作
Op：功能部件當前執行的操作
：目的暫存器編號
：源暫存器編號
：向
中寫結果的功能部件
：表示
是否就緒，是否已經被使用
結果暫存器狀態表
：每個暫存器在表中有一個域，用於記錄寫入本暫存器的功能部件（編號）。如果當前正在執行的功能部件沒有需要寫入本暫存器的，則相應域置為空。
記分牌的效能受限於以下幾個方面：
程式指令中可開發的並行性，即是否存在可以並行執行的不相關的指令
記分牌容量。決定了流水線能在多大範圍內尋找不相關指令。流水線中可以同時容納的指令數量又稱為指令視窗，目前假設記分牌指令視窗中僅僅容納一個基本快，這樣就可以不考慮分支指令的問題。
功能部件的數目和種類。
反相關和輸出相關。引起記分牌中先讀後寫和寫後寫阻塞。
動態排程演算法之二：Tomasulo演算法
將記分牌的關鍵部分和暫存器換名技術結合在一起，其核心思想是透過暫存器換名來消除寫後寫和先讀後寫相關而可能引發的流水線阻塞。
Tomasulo演算法和記分牌在結構上還有下列3處顯著的不同：
指令流出邏輯和保留站相結合實現暫存器換名，從而完全消除了資料寫後寫和先讀後寫相關這類名相關。
衝突檢測和指令執行控制機制分開。一個功能部件的指令何時開始執行，由該功能部件的保留站控制，而記分牌則是集中控制。
計算的結果透過相關通路（公共資料匯流排Common Data Bus，CDB實現）直接從功能部件進入對應的保留站進行緩衝，而不一定是寫到暫存器。所有等待這個結果的功能部件（指令）可同時讀取。與之相比，記分牌將結果首先寫到暫存器，等待此結果的功能部件要透過競爭，在記分牌的控制下使用。
Tomasulo演算法相對於記分牌技術主要的優點列舉如下：
具有分佈的阻塞檢測機制：如果多條指令都在等待一個結果，且指令的另一個運算元都已準備就緒，公共資料匯流排廣播這個被等待的結果後，這些指令可以同時得到這個結果資料，並同時開始進入執行段。
消除了資料的寫後寫和先讀後寫相關導致的阻塞。
注意：由於一旦指令進入流出段，原來指令在程式中的順序就難以再保持，為了保持程式的例外特徵不變，一旦由一條分支指令還沒有執行完畢，其後的指令是不允許進入執行段，後面將採用前瞻技術解決這個問題。
Tomasulo演算法的另一個關鍵技術——動態儲存器地址判別。第二遍迴圈的取操作再第一遍迴圈的存操作完成前就可以執行，這與正常的順序是不同的。這種動態的儲存器地址判別技術在編譯器中排程取和存操作時也經常使用，可以消除關於儲存器的寫後讀（RAW）相關、讀後寫（WAR）相關和寫後寫（WAW）相關。
Tomasulo演算法結合了以下兩種不同的技術：暫存器換名，可以獲得更大的虛擬暫存器空間；對寄存檔案中源運算元快取，解決了暫存器中的有效運算元相關引起的阻塞
Tomasulo孫發提高指令級並行的關鍵技術：指令動態排程、暫存器換名、動態儲存器地址判別
控制相關的動態解決技術
控制相關的分支處理的動態處理技術稱為動態分支預測技術。其有兩種目標：預測轉移是否成功和儘早得到轉移目標地址。
分支預測緩衝
動態分支預測是一種基於分支操作歷史記錄的預測技術，必須解決：1。如何記錄一個分支操作的歷史；2。決定預測的走向
記錄分支歷史的方法有： 1）僅僅記錄最近以詞或幾次的分支歷史 2）記錄分支成功的目標地址 3）記錄分支歷史和分支目標地址 4）記錄分支目標地址的一條或若干條指令
最簡單的動態分支預測技術叫做
分支預測緩衝技術（Branch Prediction Buffer或Branch History Table,BTB或BHT）
，它僅僅使用一片儲存區域，記錄最近一次或幾次分支特徵的歷史。其用分支指令地址的低位來索引，儲存區為1位的分支歷史記錄位，又稱為預測位，記錄該指令最近一次是否成功。緩衝區沒有其他任何標誌位，它的狀態如下：
分支預測緩衝技術包括以下兩個步驟： 1）分支預測 2）預測位修改：與分支指令的執行結果有關
簡單的1位預測機制有一個缺點：即使預測幾乎都正確，只要預測出錯，往往是連續兩次而不是一次。
為了解決這種預測錯誤，可以採用兩個預測位的預測機制。
兩位分支預測機制是
位分支預測的一個特例。
位分支預測緩衝採用
位計數器，當計數器的值大於或等於最大值的一半時，則預測下一次分支成功，否則不成功。
分支目標緩衝
將分支成功的分支指令的地址和它的分支目標地址都放到一個緩衝區中儲存起來，緩衝區以分支指令的地址作為標識；取指令階段，所有指令地址都與儲存的標識作比較，一旦相同，就認為本指令時分支指令，且讓那位它轉移成功，且它的分支目標（下一條指令）地址就是儲存在緩衝區中的分支目標地址。這個緩衝區就是分支目標緩衝區（Branch-Target Buffer，BTB或Branch-Target Cache）
對分支預測機制的一種改進是在緩衝區中不僅存入目的地址，而且還存入一個或多個目標指令（如圖4。5中虛線部分）。這種改動又兩種潛在的好處：1。在連續取指令之前，可以較長時間的訪問緩衝區，這時的分支目的緩衝區較大；2。對目的指令進行緩衝，構成稱為分支目標指令緩衝（Branch Folding）的結構，它可使無條件分支的延遲達到零，甚至有的條件分支也可達到零延遲。
基於硬體的前瞻執行
前瞻（Speculation）技術
允許在處理器還未判斷指令是否能執行之前就提前執行，以客服控制相關。
基於硬體的前瞻執行結婚了3種思想：
採用動態的分支預測技術來選擇後續執行語句
在控制相關消除之前指令前瞻執行
對基本塊採用動態排程
基於硬體的前瞻是
動態地根據資料相關性
來選擇指令和指令的執行時間，實質上是
資料流驅動執行（Data Flow Execution）
：只要運算元有效，指令就可以執行。
將指令由前瞻轉化為非前瞻這一步加到執行階段以後，稱為指令的確認（Instruction Commit）。
實現前瞻的關鍵思想是：
允許指令亂序執行，但必須順序確認
。只有確認以後的結果才是最終結果。加入指令確認階段需要一套額外的硬體緩衝來儲存那些執行完畢但未經確認的指令及其結果，這種
硬體的緩衝稱為再定序緩衝（Reorder Buffer,ROB）
，它同時還用來在前瞻執行的指令之間傳送結果。
再定序緩衝和Tomasulo演算法中的保留站一樣，提供了額外的虛擬暫存器，擴充了暫存器的容量。再定序緩衝儲存指令執行完畢到指令得到確認之前的所有指令及其結果，與Tomasulo演算法中保留站一樣是
後續指令運算元的來源之一
。不同點在於Tomasulo演算法中，一旦指令結果寫到目的暫存器，下面的指令就會從暫存器檔案中得到資料。而對於前瞻執行，直到指令確認後，才最終更新暫存器檔案。
再定序緩衝的每個項包含了3個域：
指令的型別：是否是分支（尚無結果）、存操作（目的地址位儲存器）或暫存器操作（ALU操作或目的地址是暫存器的取操作）
目的地址：目的地址給出結果應寫入的目的暫存器號（取操作和ALU指令）或暫存器的地址（存操作）
值域：用來儲存指令前瞻執行的結果，直到指令得到確認
使用再定序技術，MIPS浮點指令的執行包含以下4步：
流出（Issue）
：從浮點指令佇列頭取一條指令，若有空的保留站和空的ROB項就流出指令，為這條指令分配一個保留站和一個ROB項。若本指令需要的運算元在暫存器或ROB中，則將它送入分配的保留站中，並更新ROB的控制域，表示它的結果正在使用。分配給本指令的ROB編號也要送入保留站，當本指令執行的結果放到CDB上時用它來標識。若保留站或ROB全滿，則是結構阻塞，停止流出指令，直到兩者均有空項。
執行（Execution）
：若有一個或多個運算元無效，就等待並不斷地檢測CDB。這一步檢測先寫後讀相關。當保留站中兩個運算元全有效則執行此操作。
寫結果（Write Result）
：結果有效後將其寫到CDB上，結果附帶有本指令流出時分配的ROB項號，然後從CDB寫到ROB以及等待此結果的保留站。保留站也可以從ROB直接讀到結果而不需要CDB。
確認（Commit）
：當一條指令不是預測錯誤的分支轉移指令，到達ROB的出口且結果有效時，將結果寫道目的暫存器，如果是存操作，則將結果寫暫存器。指令的前瞻執行過程結束，然後將指令從ROB中清除。
前瞻技術存在的一個主要缺點：支援前瞻的硬體太複雜，需要大量硬體資源。
多指令流出技術
多指令流出處理器有3種基本結構：
超標量（Superscalar）
： 每個時鐘週期流出的指令數不定，超標量處理器的指令序列可以採用靜態或動態排程。
透過對指令流出部件採用流水技術，可以很大地提高指令流出地速率，但同時必須採用流水話的功能部件或多個獨立的功能部件，否則資料通道會很快被阻塞，稱為流水線的瓶頸。
理想情況下，超標量處理器將去除兩條指令，第一條是整數指令，第二條是浮點指令，並同時將它們流出。
超標量處理器與超長指令字處理器相比有以下兩個優點：
1）超標量結構對程式設計師是透明的，因為處理器能自己檢測下一條指令能否流出
2）即使是沒有經過編譯器對超標量結構進行排程最佳化的程式碼也可執行，想要到達很好的效果，就要使用動態超標量排程技術
超流水（Super Pipeline）
多條指令流出技術，也可用記分牌或Tomasulo演算法進行動態排程處理。
有兩種方式可以實現兩路超標量。第一種是將指令流出段進一步流水化，使指令流出的速度是基本機器週期的兩倍。這就可以在後面指令流出前更改暫存器表。第二種方法是對流出的指令組合進行限制，只有浮點的取操作指令或是從整數暫存器將資料送入浮點暫存器的傳送操作，才會產生相關而導致兩條指令不能同時執行。
動態排程對資料傳送時最有效的，而靜態排程對暫存器-暫存器操作的程式碼序列最有效。
透過佇列實現儲存器操作和資料傳送操作，而脫離對其他功能部件的保留站依賴的結構，稱為解耦（Decoupled）結構。
超長指令字VLIW（Very Long Instruction Word,VLIW）
VLIW採用多個獨立的功能部件，但它不是將多條指令流出到各個功能單元，而是將多條指令的操作組裝成固定的指令包，形成一條非常長的指令。
超長指令字的格式固定，處理過程簡單，採用超長指令字的處理器所需硬體量比超標量要少。但處理器種指令流出的能力時有效的，功能部件使用效率不高也是超長指令字的不足之一。
多流出處理器受到的限制
處理器種指令流出能力時有限的，它主要受以下幾個方面的影響。
1）程式內在的指令級並行性
2）硬體實現的困難
3）超標量和超長指令字處理器固有的技術限制