第四章指令級并行

主要內容4.1指令級并行的概念4.2指令的動態調度4.3動態分支預測技術4.4多指令流出技術

4.5循環展開和指令調度4.1指令級并行的概念4.1指令級并行的概念指令級并行(ILP：Instruction-LevelParallelism)：是指指令之間存在的一種并行性，利用它計算機可以執行兩條或兩條以上的指令。途徑：資源重復-設置多個處理部件

時間重疊-幾乎所有的處理機都利用流水線來使指令重疊并行執行，以達到提高性能的目的。本章研究：如何通過各種可能的技術，獲得更多的指令級并行性。

硬件＋軟件技術必須要硬件技術和軟件技術互相配合，才能夠最大限度地挖掘出程序中存在的指令級并行。流水線處理機的實際CPI理想流水線的CPI加上各類停頓的時鐘周期數：

CPI流水線

=CPI理想

+停頓結構沖突

+停頓數據沖突

+停頓控制沖突理想CPI是衡量流水線最高性能的一個指標。通過減少右邊各項，就能減小總的CPI，從而提高IPC。IPC（InstructionsPerCycle）：定義為一個時鐘周期內流水線上完成的指令條數。4.1指令級并行的概念1.循環級并行使一個循環中的不同循環體并行執行。開發循環體中存在的并行性是指令級并行研究的重點之一最基本的開發循環級并行的技術循環展開（loopunrolling）技術（4.5節介紹）采用向量指令和向量數據表示（向量章節介紹）2.相關與流水線沖突靜態指令調度動態指令調度4.1指令級并行的概念相關是程序固有的一種屬性，它反映了程序中指令之間的相互依賴關系。相關是否會導致實際沖突的發生以及該沖突會帶來多長的停頓，則是流水線的屬性。不保持“程序順序”3.對于正確地執行程序來說，必須保持的最關鍵的兩個屬性是：數據流和異常行為。數據流：指數據值從其產生者指令到其消費者指令的實際流動。保持異常行為是指：無論怎么改變指令的執行順序，都不能改變程序中異常的發生情況。即原來程序中是怎么發生的，改變執行順序后還是怎么發生。弱化為：指令執行順序的改變不能導致程序中發生新的異常。4.1指令級并行的概念4.2指令的動態調度4.2指令的動態調度關鍵知識回顧：相關相關是指兩條指令之間存在某種依賴關系，是程序固有的一種屬性。相關包括：名相關，數據相關，控制相關。沖突（HAZARDS，也稱為冒險）沖突是指由于相關的存在，使得指令流中的下一條指令不能在指定的時鐘周期執行。具體一次相關是否會導致實際沖突的發生以及該沖突會帶來多長的停頓，則是流水線的屬性。流水線沖突包括：結構沖突，數據沖突，控制沖突。3.沖突的解決（1）結構沖突：停頓（流水線氣泡）（2）數據沖突：定向傳送技術定向傳送與停頓相結合指令調度（編譯器）

前提：在亂序流動的流水線中。不足：可能會產生新的WAR或WAW沖突。（3）控制沖突：預測分支失敗預測分支成功延遲轉移技術（編譯器）靜態調度4.2指令的動態調度靜態調度依靠編譯器對代碼進行靜態調度，以減少相關和沖突。它不是在程序執行的過程中，而是在編譯期間進行代碼調度和優化。通過把相關的指令拉開距離來減少可能產生的停頓。動態調度在程序的執行過程中，依靠專門硬件對代碼進行調度，減少數據相關導致的停頓。4.2指令的動態調度一、動態調度的基本思想考慮下面一段代碼：

DIV.D F4，F0，F2 SUB.D F10，F4，F6 ADD.D F12，F6，F14SUB.D指令與DIV.D指令關于F4相關，導致流水線停頓。ADD.D指令與流水線中的任何指令都沒有關系，但也因此受阻。4.2指令的動態調度在前面的基本流水線中：指令在譯碼階段判斷相關關系。ID檢測結構沖突檢測數據沖突一旦一條指令受阻，其后的指令都將停頓。4.2指令的動態調度動態調度的基本思想是前面指令的阻塞不影響后面的指令的繼續前進。具體做法是流水線的譯碼階段再分為兩個階段：流出(Issue,IS)：指令譯碼，并檢查結構沖突。(in-orderissue)讀操作數（ReadOperands,RO）：等待數據沖突消失(如果有沖突)，然后讀操作數。(outoforderexecution)ISRO檢測結構沖突檢測數據沖突4.2指令的動態調度有的代碼在采用亂序執行后可能會發生WAR沖突和WAW沖突。例如，考慮下面的代碼

DIV.D F4,F0,F2SUB.D F10,F4,F6ADD.D F6,F8,F14DIV.D F10,F1,F3 …反相關輸出相關數據相關SUB.DF10,F4,F6WAR沖突WAW沖突Tomasulo算法可以通過使用寄存器重命名來消除。

4.2指令的動態調度回顧：寄存器換名可以消除WAR沖突和WAW沖突。考慮之前的代碼：

DIV.D F4,F0,F2SUB.D F10,F4,F6ADD.D F6,F8,F14DIV.D F10,F1,F3反相關,F6輸出相關,F10數據相關,F4消除名相關：引入兩個臨時寄存器S和T，分別將第一個F10換成S，將后一個F6換成T。S,T,4.2指令的動態調度二、Tomasulo算法1.基本思想核心思想：記錄和檢測指令相關，操作數一旦就緒就立即執行，把發生RAW沖突的可能性減少到最小；通過寄存器換名來消除WAR沖突和WAW沖突。

4.2指令的動態調度IBM360/91首先采用了Tomasulo算法。IBM360/91的設計目標是基于整個360系列的統一指令集和編譯器來實現高性能，而不是設計和利用專用的編譯器來提高性能。需要更多地依賴于硬件。IBM360體系結構只有4個雙精度浮點寄存器，限制了編譯器調度的有效性。360/91的訪存時間和浮點計算時間都很長。（也是Tomasulo算法要解決的問題）4.2指令的動態調度基于Tomasulo算法的MIPS處理器浮點部件的基本結構1）保留站（reservationstation）設置在運算部件入口，每個保留站中保存一條已經流出并等待到本功能部件執行的指令（相關信息）。

包括：操作碼、操作數以及用于檢測和解決沖突的信息。在一條指令“流出”到保留站的時候，如果該指令的源操作數已經在寄存器中就緒，則將之取到該保留站中。如果操作數還沒有計算出來，則在該保留站中記錄將產生這個操作數的保留站的標識。浮點加法器有3個保留站：ADD1，ADD2，ADD3浮點乘法器有2個保留站：MULT1，MULT2

每個保留站都有一個標識字段，唯一地標識了該保留站。

4.2指令的動態調度基于Tomasulo算法的MIPS處理器浮點部件的基本結構2）公共數據總線CDB

(CommonDataBus)所有功能部件的計算結果都是送到CDB上，由它把這些結果直接送到（播送到）各個需要該結果的地方。3）load緩沖器和store緩沖器存放讀/寫存儲器的數據或地址（與保留站類似）4）浮點寄存器FP共有16個浮點寄存器：F0，F2，F4，…，F30。它們通過一對總線連接到功能部件，并通過CDB連接到store緩沖器。4.2指令的動態調度5）指令隊列指令部件送來的(譯碼后)指令放入指令隊列指令隊列中的指令按先進先出的順序流出6）運算部件浮點加法器完成加法和減法操作浮點乘法器完成乘法和除法操作4.2指令的動態調度F8F6F4F2CBAADD1MUL1MUL2ADD2ADD3ADDF2,F0,F6MULFO,F2,F4QiF0DSUBF6,F8,F4MULFO,F2,F4ADDF2,F0,F6SUBF6,F8,F4MULFO,F2,F4ADDF2,F0,F6SUBF6,F8,F4MULA,BADDF2,F0,F6F8F6F4F2DCBADD1MUL1MUL2ADD2ADD3QiSUBF6,F8,F4F0AMUL1寄存器狀態表MULFO,F2,F4ADDF2,F0,F6SUBF6,F8,F4MULA,BADDCF8F6F4F2DCBADD1MUL1MUL2ADD2ADD3MUL1ADD1QiF0ASUBDBADD2SUBF6,F8,F4MUL1MULFO,F2,F4ADDF2,F0,F6SUBF6,F8,F4MULA,BADDMUL1,CF8F6F4F2DCBADD1MUL1MUL2ADD2ADD3MUL1ADD1QiF0ASUBD,BADD2EADDE,

C硬件重命名F在Tomasulo算法中，寄存器換名是通過保留站和流出邏輯來共同完成的。當指令流出時，如果其操作數還沒有計算出來，則將該指令中相應的寄存器號換名為將產生這個操作數的保留站的標識。指令流出到保留站后，其操作數寄存器號或者換成了數據本身（如果該數據已經就緒），或者換成了保留站的標識，不再與寄存器有關系。4.2指令的動態調度Tomasulo算法具有以下兩個特點：1）沖突檢測和指令執行控制是分布的。每個功能部件的保留站中的信息決定了什么時候指令可以在該功能部件開始執行。2）計算結果通過CDB直接從產生它的保留站傳送到所有需要它的功能部件，而不用經過寄存器。4.2指令的動態調度2.指令執行的步驟使用Tomasulo算法的流水線需3步：(1)流出：從指令隊列的頭部取一條指令。如果沒有空閑的保留站，指令就不能流出。(結構沖突)如果該指令的操作所要求的保留站有空閑的，就把該指令送到該保留站（設為r）。如果其操作數在寄存器中已經就緒，就將這些操作數送入保留站r。如果其操作數還沒有就緒，就把將產生該操作數的保留站的標識送入保留站r。（寄存器換名和對操作數進行緩沖，消除WAR沖突）完成對目標寄存器的預約工作（消除了WAW沖突）4.2指令的動態調度(2)執行

當兩個操作數都就緒后，本保留站就用相應的功能部件開始執行指令規定的操作。（消除了RAW沖突）load和store指令的執行需要兩個步驟：計算有效地址（要等到基地址寄存器就緒）把有效地址放入load或store緩沖器(3)寫結果功能部件計算完畢后，就將計算結果放到CDB上，所有等待該計算結果的寄存器和保留站（包括store緩沖器）都同時從CDB上獲得所需要的數據。4.2指令的動態調度3.Tomasulo算法舉例

每個保留站有以下6個字段：（P121圖4.2）Busy：為“yes”表示本保留站或緩沖單元“忙”。

Op：要對源操作數進行的操作。Vj，Vk：源操作數的值。Qj，Qk：將產生源操作數的保留站號。等于0表示操作數已經就緒且在Vj或Vk中，或者不需要操作數。（起“標志字段”作用）對于每一個操作數來說，V或Q字段只有一個有效。A：僅load和store緩沖器有該字段。開始是存放指令中的立即數字段，地址計算后存放有效地址。Qi：寄存器狀態表。每個寄存器在該表中有對應的一項，用于存放將把結果寫入該寄存器的保留站的站號。為0表示當前沒有正在執行的指令要寫入該寄存器，也即該寄存器中的內容就緒。（起“標志字段”作用）

例：對于下述指令序列，給出當第一條指令完成并寫入結果時，Tomasulo算法所用的各信息表中的內容。L.D F6,34（R2）L.D F2,45（R3）MUL.D F0,F2,F4SUB.D F8,F2,F6DIV.D F10,F0,F6ADD.D F6,F8,F24.2指令的動態調度當采用Tomasulo算法時，當第一條指令完成并寫入結果時，各條指令所處階段如下表。指

令

指令狀態表

流出

執行

寫結果

L.D F6,34(R2)√√√L.D F2,45(R3)√√MUL.D F0,F2,F4√SUB.D F8,F6,F2√DIV.D F10,F0,F6√ADD.D F6,F8,F2√

4.2指令的動態調度名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2Busy

no

no

no

no

no

no

noOp

Vj

Vk

Qj

Qk

A

寄存器狀態表

F0

F2

F4F6F8F10…F30

Qi

L.DF6,34(R2)①流出load緩沖器、保留站以及寄存器狀態表中的內容如下表Regs[R2]34LDyesLoad1名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2Busyyes

no

no

no

no

no

noOp

LD

Vj

Vk

Qj

Qk

A

34+Regs[R2]

寄存器狀態表

F0F2F4F6F8F10…F30

Qi

Load1

…load緩沖器、保留站以及寄存器狀態表中的內容如下表L.DF6,34(R2)②

執行計算有效地址名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2Busy

no

no

no

no

no

no

noOp

Vj

Vk

Qj

Qk

A

寄存器狀態表

F0F2F4F6F8F10…F30

Qi

…load緩沖器、保留站以及寄存器狀態表中的內容如下表L.DF6,34(R2)③

完成釋放load緩沖寫結果，修改狀態名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2BusynoyesyesyesnoyesyesOp

LDSUBADD

MULDIVVj

Vk

Mem[34+Regs[R2]]