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

1、第四章第四章 指令級(jí)并行指令級(jí)并行 主要內(nèi)容 n4.1 指令級(jí)并行的概念 n4.2 指令的動(dòng)態(tài)調(diào)度 n4.3 動(dòng)態(tài)分支預(yù)測(cè)技術(shù) n4.4 多指令流出技術(shù) n4.5 循環(huán)展開(kāi)和指令調(diào)度 n4.1指令級(jí)并行的概念 4.1 4.1 指令級(jí)并行的概念指令級(jí)并行的概念 n指令級(jí)并行指令級(jí)并行(ILP：Instruction-Level Parallelism)：是指 指令之間存在的一種并行性，利用它計(jì)算機(jī)可以執(zhí)行兩條 或兩條以上的指令。 n途徑：資源重復(fù)資源重復(fù)-設(shè)置多個(gè)處理部件 時(shí)間重疊時(shí)間重疊-幾乎所有的處理機(jī)都利用流水線來(lái)使指令 重疊并行執(zhí)行，以達(dá)到提高性能的目的。 n本章研究：本章研究：如何通過(guò)

2、各種可能的技術(shù)，獲得更多的指令級(jí) 并行性。 硬件軟件技術(shù)硬件軟件技術(shù) 必須要硬件技術(shù)和軟件技術(shù)互相配合，才能夠最大限度地挖 掘出程序中存在的指令級(jí)并行。 n流水線處理機(jī)的實(shí)際流水線處理機(jī)的實(shí)際CPICPI 理想流水線的CPI加上各類停頓的時(shí)鐘周期數(shù)： CPICPI流水線 流水線 = CPI = CPI理想 理想 + + 停頓停頓結(jié)構(gòu)沖突 結(jié)構(gòu)沖突 + + 停頓停頓數(shù)據(jù)沖突 數(shù)據(jù)沖突 + + 停頓停頓控制沖突 控制沖突 理想CPI是衡量流水線最高性能的一個(gè)指標(biāo)。通過(guò) 減少右邊各項(xiàng)，就能減小總的CPI，從而提高IPC。 IPC（Instructions Per Cycle）：定義為一個(gè)時(shí) 鐘周期內(nèi)

3、流水線上完成的指令條數(shù)。 4.1 指令級(jí)并行的概念指令級(jí)并行的概念 1. 循環(huán)級(jí)并行循環(huán)級(jí)并行 n使一個(gè)循環(huán)中的不同循環(huán)體并行執(zhí)行。 n開(kāi)發(fā)循環(huán)體中存在的并行性是指令級(jí)并行研究的重點(diǎn)之一 n最基本的開(kāi)發(fā)循環(huán)級(jí)并行的技術(shù) n循環(huán)展開(kāi)（loop unrolling）技術(shù) （4.5節(jié)介紹） n采用向量指令和向量數(shù)據(jù)表示 （向量章節(jié)介紹） 2. 相關(guān)與流水線沖突相關(guān)與流水線沖突 n靜態(tài)指令調(diào)度 n動(dòng)態(tài)指令調(diào)度 4.1 指令級(jí)并行的概念指令級(jí)并行的概念 相關(guān)是程序固有的相關(guān)是程序固有的 一種屬性，它反映一種屬性，它反映 了程序中指令之間了程序中指令之間 的相互依賴關(guān)系。的相互依賴關(guān)系。 相關(guān)是否會(huì)導(dǎo)致實(shí)

4、際沖相關(guān)是否會(huì)導(dǎo)致實(shí)際沖 突的發(fā)生以及該沖突會(huì)突的發(fā)生以及該沖突會(huì) 帶來(lái)多長(zhǎng)的停頓，則是帶來(lái)多長(zhǎng)的停頓，則是 流水線的屬性。流水線的屬性。 不保持不保持“程序順序程序順序” 3. 對(duì)于正確地執(zhí)行程序來(lái)說(shuō)，必須保持的最關(guān)鍵的兩個(gè) 屬性是：數(shù)據(jù)流數(shù)據(jù)流和異常行為。異常行為。 n數(shù)據(jù)流：數(shù)據(jù)流：指數(shù)據(jù)值從其產(chǎn)生者指令到其消費(fèi)者指令的實(shí)際 流動(dòng)。 n保持異常行為保持異常行為是指：無(wú)論怎么改變指令的執(zhí)行順序，都不 能改變程序中異常的發(fā)生情況。 l即原來(lái)程序中是怎么發(fā)生的，改變執(zhí)行順序后還是怎 么發(fā)生。 l弱化為：指令執(zhí)行順序的改變不能導(dǎo)致程序中發(fā)生新 的異常。 4.1 指令級(jí)并行的概念指令級(jí)并行的概念

5、n4.2 指令的動(dòng)態(tài)調(diào)度 4.2 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 關(guān)鍵知識(shí)回顧：關(guān)鍵知識(shí)回顧： 1.相關(guān)相關(guān) u相關(guān)是指兩條指令之間存在某種依賴關(guān)系，是程序固有的一種 屬性。 u相關(guān)包括：名相關(guān)，數(shù)據(jù)相關(guān)，控制相關(guān)。 2.沖突（沖突（ HAZARDS，也稱為冒險(xiǎn)），也稱為冒險(xiǎn)） u沖突是指由于相關(guān)的存在，使得指令流中的下一條指令不能在 指定的時(shí)鐘周期執(zhí)行。 u具體一次相關(guān)是否會(huì)導(dǎo)致實(shí)際沖突的發(fā)生以及該沖突會(huì)帶來(lái)多 長(zhǎng)的停頓，則是流水線的屬性。 u流水線沖突包括：結(jié)構(gòu)沖突，數(shù)據(jù)沖突，控制沖突。 3. 沖突的解決沖突的解決 （1 1）結(jié)構(gòu)沖突：）結(jié)構(gòu)沖突：停頓（流水線氣泡） （2 2）數(shù)據(jù)沖

6、突：）數(shù)據(jù)沖突： 定向傳送技術(shù) 定向傳送與停頓相結(jié)合 指令調(diào)度（編譯器）（編譯器） 前提：在亂序流動(dòng)的流水線中。 不足：可能會(huì)產(chǎn)生新的WAR或WAW沖突。 （3 3）控制沖突）控制沖突： 預(yù)測(cè)分支失敗 預(yù)測(cè)分支成功 延遲轉(zhuǎn)移技術(shù) （編譯器）（編譯器） 靜態(tài)調(diào)度靜態(tài)調(diào)度 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 n靜態(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)的指令拉開(kāi)距離來(lái)減少可能產(chǎn)生的停頓。 n動(dòng)態(tài)調(diào)度動(dòng)態(tài)調(diào)度 在程序的執(zhí)行過(guò)程中，依靠專門硬件對(duì)代碼進(jìn)行調(diào)度， 減少數(shù)據(jù)相關(guān)導(dǎo)致的停頓。 4.2 指令的

7、動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 一、動(dòng)態(tài)調(diào)度的基本思想一、動(dòng)態(tài)調(diào)度的基本思想 考慮下面一段代碼： DIV.D F4F4，F(xiàn)0，F(xiàn)2 SUB.D F10，F(xiàn)4F4，F(xiàn)6 ADD.D F12，F(xiàn)6，F(xiàn)14 SUB.DSUB.D指令與DIV.DDIV.D指令關(guān)于F4F4相關(guān)，導(dǎo)致流水線停頓。 ADD.DADD.D指令與流水線中的任何指令都沒(méi)有關(guān)系，但也因此受但也因此受 阻阻。 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(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)

8、調(diào)度 n動(dòng)態(tài)調(diào)度的基本思想是前面指令的阻塞不影響后面的 指令的繼續(xù)前進(jìn)。具體做法是流水線的譯碼階段再分為 兩個(gè)階段： n流出流出( (Issue, IS) )：指令譯碼，并檢查結(jié)構(gòu)沖突。(in- order issue) n讀操作數(shù)（讀操作數(shù)（Read Operands, RO）：）：等待數(shù)據(jù)沖突消失 (如果有沖突)，然后讀操作數(shù)。(out of order execution) IS RO 檢測(cè)結(jié)構(gòu)沖突檢測(cè)數(shù)據(jù)沖突 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 n有的代碼在采用亂序執(zhí)行后可能會(huì)發(fā)生WAR沖突和WAW沖突。 n例如，考慮下面的代碼 DIV.D F4, F0, F2 SUB.D F10,

9、 F4, F6 ADD.D F6, F8, F14 DIV.D F10, F1, F3 反相關(guān)反相關(guān) 輸出相關(guān)輸出相關(guān) 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) SUB.D SUB.D F10F10, , F4F4, , F6F6 WARWAR沖突沖突 WAWWAW沖突沖突 TomasuloTomasulo算法算法可以通過(guò)使用寄存器重命名來(lái)消除?？梢酝ㄟ^(guò)使用寄存器重命名來(lái)消除。 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 回顧：寄存器換名可以消除WAR沖突和WAW沖突。 考慮之前的代碼： DIV.D F4, F0, F2 SUB.D F10,F4, F6 ADD.D F6, F8, F14 DIV.D F10, F1, F

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

11、Tomasulo算法。 nIBM 360/91的設(shè)計(jì)目標(biāo)是基于整個(gè)360系列的統(tǒng)一指令 集和編譯器來(lái)實(shí)現(xiàn)高性能，而不是設(shè)計(jì)和利用專用的 編譯器來(lái)提高性能。 需要更多地依賴于硬件。 nIBM 360體系結(jié)構(gòu)只有4 4個(gè)雙精度浮點(diǎn)寄存器，限制了 編譯器調(diào)度的有效性。 n360/91360/91的訪存時(shí)間和浮點(diǎn)計(jì)算時(shí)間都很長(zhǎng)。 （也是Tomasulo算法要解決的問(wèn)題） 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 n基于Tomasulo算法的MIPS處理器浮點(diǎn)部件的基本結(jié)構(gòu) 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP store緩緩沖沖器器 load緩緩沖沖器器 地地址址部部件件 load/stor

12、e操操作作 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 數(shù)數(shù)據(jù)據(jù) 1 1 存存儲(chǔ)儲(chǔ)部部件件 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 地地址址 2 3 2 3 4 5 6 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) 1 1）保留站（保留站（reservation stationreservation station） 設(shè)置在運(yùn)算部件入口，每個(gè)保留站中保存一條已經(jīng)流出并 等待到本功能部件執(zhí)行的指令執(zhí)行的指令（相關(guān)信息）。 包括：包括：操作碼、操作數(shù)以及用于檢測(cè)和解決沖突的信息。 n在一條指令“流出”到保留站的時(shí)候，如果該指令 的

13、源操作數(shù)已經(jīng)在寄存器中就緒，則將之取到該保 留站中。 n如果操作數(shù)還沒(méi)有計(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)度指令的動(dòng)態(tài)調(diào)度 n基于Tomasulo算法的MIPS處理器浮點(diǎn)部件的基本結(jié)構(gòu) 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP store緩緩沖沖器器 load緩緩沖沖器器 地地址址部部件件 load/store操操作作 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 數(shù)數(shù)據(jù)

14、據(jù) 1 1 存存儲(chǔ)儲(chǔ)部部件件 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 地地址址 2 3 2 3 4 5 6 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) 2 2）公共數(shù)據(jù)總線公共數(shù)據(jù)總線CDBCDB (Common Data Bus) 所有功能部件的計(jì)算結(jié)果都是送到CDB上，由它把這些結(jié) 果直接送到（播送到）各個(gè)需要該結(jié)果的地方。 3 3）loadload緩沖器和緩沖器和storestore緩沖器緩沖器 存放讀/寫存儲(chǔ)器的數(shù)據(jù)或地址 （與保留站類似） 4 4）浮點(diǎn)寄存器）浮點(diǎn)寄存器FPFP n共有16個(gè)浮點(diǎn)寄存器：F0，F(xiàn)2，F(xiàn)4，F(xiàn)30。

15、 n它們通過(guò)一對(duì)總線連接到功能部件，并通過(guò)CDB連接到 store緩沖器。 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 5）指令隊(duì)列）指令隊(duì)列 n指令部件送來(lái)的(譯碼后)指令放入指令隊(duì)列 n指令隊(duì)列中的指令按先進(jìn)先出的順序流出 6）運(yùn)算部件）運(yùn)算部件 n浮點(diǎn)加法器完成加法和減法操作 n浮點(diǎn)乘法器完成乘法和除法操作 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站

16、站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) F8F8 F6F6 F4F4 F2F2 C C B B A A ADD1ADD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 ADD F2,ADD F2,F0F0,F6,F6 MUL MUL FOFO,F2,F4,F2,F4 Qi F0F0 D D SUB SUB F6,F8,F4F6,F8,F4 MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)

17、總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)

18、標(biāo)識(shí)識(shí) MUL A, BMUL A, B ADD F2,F0,F6ADD F2,F0,F6 F8F8 F6F6 F4F4 F2F2 D D C C B B ADD1ADD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 Qi SUB SUB F6,F8,F4F6,F8,F4 F0F0 A A MUL1MUL1 寄存器寄存器 狀態(tài)表狀態(tài)表 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB）

19、1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) MUL A, BMUL A, B ADD CADD C F8F8 F6F6 F4F4 F2F2 D D C C B B ADD1A

20、DD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 MUL1MUL1 ADD1ADD1 Qi F0F0 A A SUB D BSUB D B ADD2ADD2 SUB SUB F6,F8,F4F6,F8,F4 MUL1 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) MUL MUL FOFO,F2,F4,F2,F4 ADD F2,ADD F2

21、,F0F0, ,F6F6 SUB SUB F6F6,F8,F4,F8,F4 從從指指令令部部件件來(lái)來(lái) 浮浮點(diǎn)點(diǎn)寄寄存存器器FP 緩緩沖沖器器 浮浮點(diǎn)點(diǎn)操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 1 浮浮點(diǎn)點(diǎn)加加法法器器 浮浮點(diǎn)點(diǎn)乘乘法法器器 指指令令隊(duì)隊(duì)列列 2 3 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 標(biāo)標(biāo)識(shí)識(shí) 標(biāo)標(biāo)識(shí)識(shí) MUL A, BMUL A, B ADD MUL1, CADD MUL1, C F8F8 F6F6 F4F4 F2F2 D D C C B B ADD1ADD1 MUL1MUL1 MUL2MUL2 ADD2ADD2 ADD3ADD3 MUL1MUL

22、1 ADD1ADD1 Qi F0F0 A A SUB D, BSUB D, B ADD2ADD2 E E ADD E, ADD E, C C 硬件重命名硬件重命名 F F n在Tomasulo算法中，寄存器換名是通過(guò)保留站和流出邏輯 來(lái)共同完成的。 n當(dāng)指令流出時(shí)，如果其操作數(shù)還沒(méi)有計(jì)算出來(lái)，則將該 指令中相應(yīng)的寄存器號(hào)換名為將產(chǎn)生這個(gè)操作數(shù)的保留站換名為將產(chǎn)生這個(gè)操作數(shù)的保留站 的標(biāo)識(shí)的標(biāo)識(shí)。 n指令流出到保留站后，其操作數(shù)寄存器號(hào)或者換成了數(shù) 據(jù)本身（如果該數(shù)據(jù)已經(jīng)就緒），或者換成了保留站的標(biāo) 識(shí)，不再與寄存器有關(guān)系不再與寄存器有關(guān)系。 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 nTomasu

23、lo算法具有以下兩個(gè)特點(diǎn)：兩個(gè)特點(diǎn)： 1）沖突檢測(cè)和指令執(zhí)行控制是分布的。 每個(gè)功能部件的保留站中的信息決定了什么時(shí)候指每個(gè)功能部件的保留站中的信息決定了什么時(shí)候指 令可以在該功能部件開(kāi)始執(zhí)行。令可以在該功能部件開(kāi)始執(zhí)行。 2）計(jì)算結(jié)果通過(guò)CDB直接從產(chǎn)生它的保留站傳送到所有需 要它的功能部件，而不用經(jīng)過(guò)寄存器。 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 2.2.指令執(zhí)行的步驟指令執(zhí)行的步驟 使用Tomasulo算法的流水線需3步： (1)流出：流出：從指令隊(duì)列的頭部取一條指令。 n如果沒(méi)有空閑的保留站，指令就不能流出。(結(jié)構(gòu)沖突) n如果該指令的操作所要求的保留站有空閑的，就把該 指令送到該保留

24、站（設(shè)為r）。 n如果其操作數(shù)在寄存器中已經(jīng)就緒，就將這些操作數(shù)送入保留站如果其操作數(shù)在寄存器中已經(jīng)就緒，就將這些操作數(shù)送入保留站r r。 n如果其操作數(shù)還沒(méi)有就緒，就把將產(chǎn)生該操作數(shù)的保留站的標(biāo)識(shí)送入如果其操作數(shù)還沒(méi)有就緒，就把將產(chǎn)生該操作數(shù)的保留站的標(biāo)識(shí)送入 保留站保留站r r。 （寄存器換名和對(duì)操作數(shù)進(jìn)行緩沖，消除WARWAR沖突） n完成對(duì)目標(biāo)寄存器的預(yù)約目標(biāo)寄存器的預(yù)約工作 （消除了WAWWAW沖突） 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 (2) 執(zhí)行執(zhí)行 n當(dāng)兩個(gè)操作數(shù)都就緒后，本保留站就用相應(yīng)的功能部件 開(kāi)始執(zhí)行指令規(guī)定的操作。 （消除了R RAWAW沖突） nload和stor

25、e指令的執(zhí)行需要兩個(gè)步驟： n計(jì)算有效地址（要等到基地址寄存器就緒） n把有效地址放入load或store緩沖器 (3) 寫結(jié)果寫結(jié)果 功能部件計(jì)算完畢后，就將計(jì)算結(jié)果放到CDBCDB上，所有 等待該計(jì)算結(jié)果的寄存器和保留站（包括storestore緩沖器） 都同時(shí)從CDBCDB上獲得所需要的數(shù)據(jù)。 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 3. 3. TomasuloTomasulo算法舉例算法舉例 每個(gè)保留站有以下6個(gè)字段：（P121 圖4.2） nBusy：為“yes”表示本保留站或緩沖單元“忙”。 nOp：要對(duì)源操作數(shù)進(jìn)行的操作。 nVj，Vk：源操作數(shù)的值。 nQj，Qk：將產(chǎn)生源操作數(shù)

26、的保留站號(hào)。 n等于0 0表示操作數(shù)已經(jīng)就緒且在VjVj或VkVk中，或者不需要操 作數(shù)。 （起“標(biāo)志字段”作用） n對(duì)于每一個(gè)操作數(shù)來(lái)說(shuō)，V V或Q Q字段只有一個(gè)有效。 nA：僅loadload和storestore緩沖器有該字段。開(kāi)始是存放指令中的立 即數(shù)字段，地址計(jì)算后存放有效地址。 nQi：寄存器狀態(tài)表。 n每個(gè)寄存器在該表中有對(duì)應(yīng)的一項(xiàng)，用于存放將把結(jié)果 寫入該寄存器的保留站的站號(hào)。 n為0 0表示當(dāng)前沒(méi)有正在執(zhí)行的指令要寫入該寄存器，也即 該寄存器中的內(nèi)容就緒。 （起“標(biāo)志字段”作用） 例：對(duì)于下述指令序列，給出當(dāng)?shù)谝粭l指令完成并寫 入結(jié)果時(shí)，Tomasulo算法所用的各信息表中

27、的內(nèi)容。 L.DF6,34（R2） L.DF2,45（R3） MUL.DF0,F2,F4 SUB.DF8,F2,F6 DIV.DF10,F0,F6 ADD.DF6,F8,F2 4.2 指令的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 n當(dāng)采用Tomasulo算法時(shí)，當(dāng)?shù)谝粭l指令完成并寫入結(jié) 果時(shí)， 各條指令所處階段如下表。 指指 令令 指令狀態(tài)表指令狀態(tài)表 流出流出 執(zhí)行執(zhí)行 寫結(jié)果寫結(jié)果 L.D F6 , 34(R2) L.D F2 , 45(R3) MUL.DF0 , F2 , F4 SUB.D F8 , F6 , F2 DIV.DF10 , F0 , F6 ADD.D F6 , F8 , F2 4.2 指令

28、的動(dòng)態(tài)調(diào)度指令的動(dòng)態(tài)調(diào)度 名稱名稱 保留站保留站 Load1Load1 Load2Load2 Add1Add1 Add2Add2 Add3Add3 Mult1Mult1 Mult2Mult2 BusyBusy nono no no no no no no nono nono nono OpOp VjVj VkVk QjQj QkQk A A 寄存器狀態(tài)表寄存器狀態(tài)表 F0 F0 F2 F2 F4 F4 F6 F8 F6 F8 F10 F30F10 F30 Qi Qi L.D F6,34(R2) 流出流出 loadload緩沖器、保留站以及寄存器狀態(tài)表中的內(nèi)容如下表緩沖器、保留站以及寄存器狀態(tài)表

29、中的內(nèi)容如下表 RegsRegsR2R23434LDLDyesyes Load1Load1 名稱名稱 保留站保留站 Load1Load1 Load2Load2 Add1Add1 Add2Add2 Add3Add3 Mult1Mult1 Mult2Mult2 BusyBusy yes yes no no no no no no nono nono nono OpOp LD LD VjVj VkVk QjQj QkQk A A 34+RegsR234+RegsR2 寄存器狀態(tài)表寄存器狀態(tài)表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi Loa

30、d1 Load1 loadload緩沖器、保留站以及寄存器狀態(tài)表中的內(nèi)容如下表緩沖器、保留站以及寄存器狀態(tài)表中的內(nèi)容如下表 L.D F6,34(R2) 執(zhí)行執(zhí)行 計(jì)算有效地址計(jì)算有效地址 名稱名稱 保留站保留站 Load1Load1 Load2Load2 Add1Add1 Add2Add2 Add3Add3 Mult1Mult1 Mult2Mult2 BusyBusy nono no no no no no no nono nono nono OpOp VjVj VkVk QjQj QkQk A A 寄存器狀態(tài)表寄存器狀態(tài)表 F0 F2 F4 F6 F8 F10 F30F0 F2 F4 F6 F8 F10 F30 Qi Qi loadload緩沖器、保留站以及寄存器狀態(tài)表中的內(nèi)容如