計(jì)算機(jī)體系結(jié)構(gòu)第四章-1

第四章指令級(jí)并行

主要內(nèi)容4.1指令級(jí)并行的概念4.2指令的動(dòng)態(tài)調(diào)度4.3動(dòng)態(tài)分支預(yù)測(cè)技術(shù)4.4多指令流出技術(shù)

4.5循環(huán)展開和指令調(diào)度4.1指令級(jí)并行的概念4.1指令級(jí)并行的概念指令級(jí)并行(ILP：Instruction-LevelParallelism)：是指指令之間存在的一種并行性，利用它計(jì)算機(jī)可以執(zhí)行兩條或兩條以上的指令。途徑：資源重復(fù)-設(shè)置多個(gè)處理部件

時(shí)間重疊-幾乎所有的處理機(jī)都利用流水線來(lái)使指令重疊并行執(zhí)行，以達(dá)到提高性能的目的。本章研究：如何通過(guò)各種可能的技術(shù)，獲得更多的指令級(jí)并行性。

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

CPI流水線

=CPI理想

+停頓結(jié)構(gòu)沖突

+停頓數(shù)據(jù)沖突

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

前提：在亂序流動(dòng)的流水線中。不足：可能會(huì)產(chǎn)生新的WAR或WAW沖突。（3）控制沖突：預(yù)測(cè)分支失敗預(yù)測(cè)分支成功延遲轉(zhuǎn)移技術(shù)（編譯器）靜態(tài)調(diào)度4.2指令的動(dòng)態(tài)調(diào)度靜態(tài)調(diào)度依靠編譯器對(duì)代碼進(jìn)行靜態(tài)調(diào)度，以減少相關(guān)和沖突。它不是在程序執(zhí)行的過(guò)程中，而是在編譯期間進(jìn)行代碼調(diào)度和優(yōu)化。通過(guò)把相關(guān)的指令拉開距離來(lái)減少可能產(chǎn)生的停頓。動(dòng)態(tài)調(diào)度在程序的執(zhí)行過(guò)程中，依靠專門硬件對(duì)代碼進(jìn)行調(diào)度，減少數(shù)據(jù)相關(guān)導(dǎo)致的停頓。4.2指令的動(dòng)態(tài)調(diào)度一、動(dòng)態(tài)調(diào)度的基本思想考慮下面一段代碼：

DIV.D F4，F(xiàn)0，F(xiàn)2 SUB.D F10，F(xiàn)4，F(xiàn)6 ADD.D F12，F(xiàn)6，F(xiàn)14SUB.D指令與DIV.D指令關(guān)于F4相關(guān)，導(dǎo)致流水線停頓。ADD.D指令與流水線中的任何指令都沒有關(guān)系，但也因此受阻。4.2指令的動(dòng)態(tài)調(diào)度在前面的基本流水線中：指令在譯碼階段判斷相關(guān)關(guān)系。ID檢測(cè)結(jié)構(gòu)沖突檢測(cè)數(shù)據(jù)沖突一旦一條指令受阻，其后的指令都將停頓。4.2指令的動(dòng)態(tài)調(diào)度動(dòng)態(tài)調(diào)度的基本思想是前面指令的阻塞不影響后面的指令的繼續(xù)前進(jìn)。具體做法是流水線的譯碼階段再分為兩個(gè)階段：流出(Issue,IS)：指令譯碼，并檢查結(jié)構(gòu)沖突。(in-orderissue)讀操作數(shù)（ReadOperands,RO）：等待數(shù)據(jù)沖突消失(如果有沖突)，然后讀操作數(shù)。(outoforderexecution)ISRO檢測(cè)結(jié)構(gòu)沖突檢測(cè)數(shù)據(jù)沖突4.2指令的動(dòng)態(tài)調(diào)度有的代碼在采用亂序執(zhí)行后可能會(huì)發(fā)生WAR沖突和WAW沖突。例如，考慮下面的代碼

DIV.D F4,F0,F2SUB.D F10,F4,F6ADD.D F6,F8,F14DIV.D F10,F1,F3 …反相關(guān)輸出相關(guān)數(shù)據(jù)相關(guān)SUB.DF10,F4,F6WAR沖突WAW沖突Tomasulo算法可以通過(guò)使用寄存器重命名來(lái)消除。

4.2指令的動(dòng)態(tài)調(diào)度回顧：寄存器換名可以消除WAR沖突和WAW沖突?？紤]之前的代碼：

DIV.D F4,F0,F2SUB.D F10,F4,F6ADD.D F6,F8,F14DIV.D F10,F1,F3反相關(guān),F6輸出相關(guān),F10數(shù)據(jù)相關(guān),F4消除名相關(guān)：引入兩個(gè)臨時(shí)寄存器S和T，分別將第一個(gè)F10換成S，將后一個(gè)F6換成T。S,T,4.2指令的動(dòng)態(tài)調(diào)度二、Tomasulo算法1.基本思想核心思想：記錄和檢測(cè)指令相關(guān)，操作數(shù)一旦就緒就立即執(zhí)行，把發(fā)生RAW沖突的可能性減少到最??；通過(guò)寄存器換名來(lái)消除WAR沖突和WAW沖突。

4.2指令的動(dòng)態(tài)調(diào)度IBM360/91首先采用了Tomasulo算法。IBM360/91的設(shè)計(jì)目標(biāo)是基于整個(gè)360系列的統(tǒng)一指令集和編譯器來(lái)實(shí)現(xiàn)高性能，而不是設(shè)計(jì)和利用專用的編譯器來(lái)提高性能。需要更多地依賴于硬件。IBM360體系結(jié)構(gòu)只有4個(gè)雙精度浮點(diǎn)寄存器，限制了編譯器調(diào)度的有效性。360/91的訪存時(shí)間和浮點(diǎn)計(jì)算時(shí)間都很長(zhǎng)。（也是Tomasulo算法要解決的問(wèn)題）4.2指令的動(dòng)態(tài)調(diào)度基于Tomasulo算法的MIPS處理器浮點(diǎn)部件的基本結(jié)構(gòu)1）保留站（reservationstation）設(shè)置在運(yùn)算部件入口，每個(gè)保留站中保存一條已經(jīng)流出并等待到本功能部件執(zhí)行的指令（相關(guān)信息）。

包括：操作碼、操作數(shù)以及用于檢測(cè)和解決沖突的信息。在一條指令“流出”到保留站的時(shí)候，如果該指令的源操作數(shù)已經(jīng)在寄存器中就緒，則將之取到該保留站中。如果操作數(shù)還沒有計(jì)算出來(lái)，則在該保留站中記錄將產(chǎn)生這個(gè)操作數(shù)的保留站的標(biāo)識(shí)。浮點(diǎn)加法器有3個(gè)保留站：ADD1，ADD2，ADD3浮點(diǎn)乘法器有2個(gè)保留站：MULT1，MULT2

每個(gè)保留站都有一個(gè)標(biāo)識(shí)字段，唯一地標(biāo)識(shí)了該保留站。

4.2指令的動(dòng)態(tài)調(diào)度基于Tomasulo算法的MIPS處理器浮點(diǎn)部件的基本結(jié)構(gòu)2）公共數(shù)據(jù)總線CDB

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

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

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

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

Op：要對(duì)源操作數(shù)進(jìn)行的操作。Vj，Vk：源操作數(shù)的值。Qj，Qk：將產(chǎn)生源操作數(shù)的保留站號(hào)。等于0表示操作數(shù)已經(jīng)就緒且在Vj或Vk中，或者不需要操作數(shù)。（起“標(biāo)志字段”作用）對(duì)于每一個(gè)操作數(shù)來(lái)說(shuō)，V或Q字段只有一個(gè)有效。A：僅load和store緩沖器有該字段。開始是存放指令中的立即數(shù)字段，地址計(jì)算后存放有效地址。Qi：寄存器狀態(tài)表。每個(gè)寄存器在該表中有對(duì)應(yīng)的一項(xiàng)，用于存放將把結(jié)果寫入該寄存器的保留站的站號(hào)。為0表示當(dāng)前沒有正在執(zhí)行的指令要寫入該寄存器，也即該寄存器中的內(nèi)容就緒。（起“標(biāo)志字段”作用）

例：對(duì)于下述指令序列，給出當(dāng)?shù)谝粭l指令完成并寫入結(jié)果時(shí)，Tomasulo算法所用的各信息表中的內(nèi)容。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指令的動(dòng)態(tài)調(diào)度當(dāng)采用Tomasulo算法時(shí)，當(dāng)?shù)谝粭l指令完成并寫入結(jié)果時(shí)，各條指令所處階段如下表。指

令

指令狀態(tài)表

流出

執(zhí)行

寫結(jié)果

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指令的動(dòng)態(tài)調(diào)度名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2Busy

no

no

no

no

no

no

noOp

Vj

Vk

Qj

Qk

A

寄存器狀態(tài)表

F0

F2

F4F6F8F10…F30

Qi

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

保留站

Load1Load2Add1Add2Add3Mult1Mult2Busyyes

no

no

no

no

no

noOp

LD

Vj

Vk

Qj

Qk

A

34+Regs[R2]

寄存器狀態(tài)表

F0F2F4F6F8F10…F30

Qi

Load1

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

執(zhí)行計(jì)算有效地址名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2Busy

no

no

no

no

no

no

noOp

Vj

Vk

Qj

Qk

A

寄存器狀態(tài)表

F0F2F4F6F8F10…F30

Qi

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

完成釋放load緩沖寫結(jié)果，修改狀態(tài)名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2BusynoyesyesyesnoyesyesOp

LDSUBADD

MULDIVVj

Vk

Mem[34+Regs[R2]]