計算機系統(tǒng)結(jié)構(gòu)-4-指令級并行

1、21474.1指令級并行的概念4.2指令的動態(tài)調(diào)度4.3控制相關(guān)的動態(tài)解決技術(shù)4.4多指令流出技術(shù)31474.1指令級并行的概念當(dāng)指令之間不存在相關(guān)時，它們在流水線中是可以當(dāng)指令之間不存在相關(guān)時，它們在流水線中是可以重疊起來并行執(zhí)行的。這種指令序列中存在的潛在重疊起來并行執(zhí)行的。這種指令序列中存在的潛在并行性稱為并行性稱為指令級并行指令級并行。（Instruction-Level Parallelism，簡記為ILP）本章研究：本章研究：如何通過各種可能的技術(shù)，獲得更多的如何通過各種可能的技術(shù)，獲得更多的指令級并行性。指令級并行性。 （硬件技術(shù)和軟件技術(shù)）（硬件技術(shù)和軟件技術(shù)）必須要硬件技術(shù)和

2、軟件技術(shù)互相配合，才能夠最大必須要硬件技術(shù)和軟件技術(shù)互相配合，才能夠最大限度地挖掘出程序中存在的指令級并行。限度地挖掘出程序中存在的指令級并行。41471.1.流水線處理器的實際流水線處理器的實際CPICPICPICPI流水線流水線 = CPI= CPI理想理想 + + 各類停頓周期數(shù)的總和各類停頓周期數(shù)的總和 流水線的理想流水線的理想CPICPI是流水線的最大流量。是流水線的最大流量。 各類停頓包括：各類停頓包括：結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一個功能部件而導(dǎo)致的停頓。個功能部件而導(dǎo)致的停頓?？刂葡嚓P(guān)停頓：是由于指令流的改變（如控制相關(guān)停頓：是由于指令

3、流的改變（如分支指令）而導(dǎo)致的停頓。分支指令）而導(dǎo)致的停頓。RAWRAW、WARWAR和和WAWWAW停頓：由數(shù)據(jù)相關(guān)造成的。停頓：由數(shù)據(jù)相關(guān)造成的。減少其中的任何一種停頓，都可以有效地減少減少其中的任何一種停頓，都可以有效地減少CPICPI，從而提高流水線的性能。，從而提高流水線的性能。51472. 2. 本章要研究的技術(shù)以及它們所克服的停頓本章要研究的技術(shù)以及它們所克服的停頓技術(shù)技術(shù)主要克服的停頓主要克服的停頓章節(jié)章節(jié)基本流水線調(diào)度基本流水線調(diào)度數(shù)據(jù)先寫后讀相關(guān)停頓數(shù)據(jù)先寫后讀相關(guān)停頓4.1循環(huán)展開循環(huán)展開控制相關(guān)停頓控制相關(guān)停頓4.1寄存器換名寄存器換名數(shù)據(jù)寫后寫相關(guān)和先讀后寫數(shù)據(jù)寫后寫

4、相關(guān)和先讀后寫相關(guān)停頓相關(guān)停頓4.1指令動態(tài)調(diào)度（記分牌和指令動態(tài)調(diào)度（記分牌和Tomasulo算法）算法）各種數(shù)據(jù)相關(guān)停頓各種數(shù)據(jù)相關(guān)停頓4.2動態(tài)分支預(yù)測動態(tài)分支預(yù)測控制相關(guān)停頓控制相關(guān)停頓4.3前瞻（前瞻（Speculation）所有數(shù)據(jù)所有數(shù)據(jù)/控制相關(guān)停頓控制相關(guān)停頓4.3多指令流出（超標(biāo)量和超多指令流出（超標(biāo)量和超長指令字）長指令字）提高理想提高理想CPI4.461473.3.幾個概念幾個概念基本程序塊基本程序塊一段除了入口和出口以外不包含其它分支的線一段除了入口和出口以外不包含其它分支的線性代碼段。性代碼段。程序平均每程序平均每6 67 7條指令就會有一個分支。條指令就會有一個分

5、支。循環(huán)體中指令之間的并行性稱為循環(huán)體中指令之間的并行性稱為循環(huán)級并行性循環(huán)級并行性。開發(fā)循環(huán)體中存在的并行性。開發(fā)循環(huán)體中存在的并行性。 最常見、最基本最常見、最基本是指令級并行研究的重點之一。是指令級并行研究的重點之一。7147最基本的開發(fā)循環(huán)級并行的技術(shù)最基本的開發(fā)循環(huán)級并行的技術(shù)指令調(diào)度指令調(diào)度（schedulingscheduling）技術(shù)技術(shù)循環(huán)展開循環(huán)展開（loop unrollingloop unrolling）技術(shù)技術(shù)換名換名（renamingrenaming）技術(shù)技術(shù)81474.1.1 循環(huán)展開調(diào)度的基本方法1. 1. 指令調(diào)度指令調(diào)度 通過改變指令在程序中的位置，將相關(guān)指

6、通過改變指令在程序中的位置，將相關(guān)指令之間的距離加大到不小于指令執(zhí)行延遲，將令之間的距離加大到不小于指令執(zhí)行延遲，將相關(guān)指令轉(zhuǎn)化為無關(guān)指令。相關(guān)指令轉(zhuǎn)化為無關(guān)指令。 指令調(diào)度是循環(huán)展開的技術(shù)基礎(chǔ)。指令調(diào)度是循環(huán)展開的技術(shù)基礎(chǔ)。2. 2. 編譯器在完成這種指令調(diào)度時，受限于以下兩編譯器在完成這種指令調(diào)度時，受限于以下兩 個特性：個特性： 程序固有的指令級并行性程序固有的指令級并行性 流水線功能部件的執(zhí)行延遲流水線功能部件的執(zhí)行延遲91473. 3. 本章使用的浮點流水線的延遲本章使用的浮點流水線的延遲產(chǎn)生結(jié)果指令使用結(jié)果指令延遲時鐘周期數(shù)浮點計算另外的浮點計算3浮點計算浮點數(shù)據(jù)存操作（SD）2浮

7、點數(shù)據(jù)取操作（LD）浮點計算1浮點數(shù)據(jù)取操作（LD）浮點數(shù)據(jù)存操作（SD）010147例例4.14.1 對于下面的源代碼，轉(zhuǎn)換成對于下面的源代碼，轉(zhuǎn)換成DLXDLX匯編語言，匯編語言，在在不進(jìn)行指令調(diào)度不進(jìn)行指令調(diào)度和和進(jìn)行指令調(diào)度進(jìn)行指令調(diào)度兩種情況下，兩種情況下，分析代碼一次循環(huán)的執(zhí)行時間。分析代碼一次循環(huán)的執(zhí)行時間。 for (i=1; i=1000; i+)for (i=1; i=1000; i+) xi = xi + s; xi = xi + s;11147解：解：(1)(1) 變量分配寄存器變量分配寄存器 整數(shù)寄存器整數(shù)寄存器R1R1：循環(huán)計數(shù)器，初值為向量：循環(huán)計數(shù)器，初值為向量

8、 中最高端地址元素的地址。中最高端地址元素的地址。 浮點寄存器浮點寄存器F2F2：保存常數(shù)：保存常數(shù)S S。 假定最低端元素的地址為假定最低端元素的地址為8 8。 (2)(2) DLXDLX匯編語言后的程序匯編語言后的程序 Loop:Loop:LDLDF0,0(R1) F0,0(R1) ADDD ADDDF4,F0,F2F4,F0,F2 SD SD0(R1),F40(R1),F4 SUBI SUBIR1,R1,#8R1,R1,#8 BNEZ BNEZR1,LoopR1,Loop12147(3)(3) 程序執(zhí)行的實際時鐘程序執(zhí)行的實際時鐘根據(jù)根據(jù)表表4-24-2中給出的的延遲，實際時鐘如下：中給

9、出的的延遲，實際時鐘如下： 指令流出時鐘指令流出時鐘 Loop: LD F0 , 0(R1) 1 （空轉(zhuǎn)） 2 ADDD F4 , F0 , F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 SD 0(R1) , F4 6 SUBI R1 , R1 , #8 7 （空轉(zhuǎn)） 8 BNEZ R1 , Loop 9 （空轉(zhuǎn)） 10每個元素的操作需要每個元素的操作需要1010個時鐘周期，其中個時鐘周期，其中5 5個個是空轉(zhuǎn)周期。是空轉(zhuǎn)周期。13147(4)(4) 指令調(diào)度以后，程序的執(zhí)行情況指令調(diào)度以后，程序的執(zhí)行情況SDSD放在分支指令的分支延遲槽中放在分支指令的分支延遲槽中對存儲器地址偏移量進(jìn)行調(diào)整對存儲器地

10、址偏移量進(jìn)行調(diào)整 指令流出時鐘指令流出時鐘Loop: LD F0 , 0(R1) 1 SUBI R1 , R1 , #8 2 ADDD F4 , F0 , F2 3 （空轉(zhuǎn)） 4 BNEZ R1 , Loop 5 SD 8(R1) , F4 6一個元素的操作時間從一個元素的操作時間從1010個時鐘周期減少到個時鐘周期減少到6 6個個5 5個周期是有指令執(zhí)行的，個周期是有指令執(zhí)行的，1 1個空轉(zhuǎn)周期。個空轉(zhuǎn)周期。14147(5)(5) 例子中的問題及解決方案例子中的問題及解決方案只有只有LDLD、ADDDADDD和和SDSD這這3 3條指令是有效操作條指令是有效操作. .占用占用3 3個時鐘周期

11、個時鐘周期而而SUBISUBI、空轉(zhuǎn)空轉(zhuǎn)和和BENZBENZ這這3 3個時鐘周期都是附加個時鐘周期都是附加的循環(huán)控制開銷。的循環(huán)控制開銷。循環(huán)展開技術(shù)循環(huán)展開技術(shù)多次復(fù)制循環(huán)體并相應(yīng)調(diào)整展開后的指令和多次復(fù)制循環(huán)體并相應(yīng)調(diào)整展開后的指令和循環(huán)結(jié)束條件，增加有效操作時間與控制操循環(huán)結(jié)束條件，增加有效操作時間與控制操作時間的比率。作時間的比率。也給編譯器進(jìn)行指令調(diào)度帶來了更大的空間。也給編譯器進(jìn)行指令調(diào)度帶來了更大的空間。15147例例4.2 4.2 體現(xiàn)循環(huán)展開技術(shù)的特點體現(xiàn)循環(huán)展開技術(shù)的特點 將將例例4.14.1中的循環(huán)展開成中的循環(huán)展開成3 3次次得到得到4 4個個循循環(huán)體，再對展開后的指令

12、序列在不調(diào)度和環(huán)體，再對展開后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性能。調(diào)度兩種情況下，分析代碼的性能。 假定假定R1R1的初值為的初值為3232的倍數(shù)，即循環(huán)的倍數(shù)，即循環(huán)次數(shù)為次數(shù)為4 4的倍數(shù)。的倍數(shù)。16147解：解：補償代碼問題補償代碼問題寄存器分配寄存器分配展開后的循環(huán)體內(nèi)不重復(fù)使用寄存器。展開后的循環(huán)體內(nèi)不重復(fù)使用寄存器。F0F0、F4F4：用于展開后的第：用于展開后的第1 1個循環(huán)體個循環(huán)體F2F2：保存常數(shù)：保存常數(shù)F6F6和和F8F8：用于展開后的第用于展開后的第2 2個循環(huán)體個循環(huán)體F10F10和和F12F12：用于第用于第3 3個循環(huán)體個循環(huán)體F14F14和和

13、F16F16：用于第用于第4 4個循環(huán)體個循環(huán)體17147(1)(1) 展開后沒有調(diào)度的代碼展開后沒有調(diào)度的代碼流出時鐘流出時鐘Loop:LDF0,0(R1) 1（空轉(zhuǎn)） 2ADDDF4,F0,F2 3（空轉(zhuǎn)） 4（空轉(zhuǎn)） 5SD0(R1),F4 6LDF6,-8(R1) 7（空轉(zhuǎn)） 8ADDDF8,F6,F2 9（空轉(zhuǎn)） 10（空轉(zhuǎn)） 11SD-8(R1),F8 12LDF10,-16(R1) 13（空轉(zhuǎn)） 14流出時鐘流出時鐘ADDDF12,F10,F2 15（空轉(zhuǎn)） 16 （空轉(zhuǎn)） 17SD-16(R1),F12 18LDF14,-24(R1) 19（空轉(zhuǎn)） 20ADDDF16,F14,

14、F2 21（空轉(zhuǎn)） 22（空轉(zhuǎn)） 23SD-24(R1),F16 24SUBIR1,R1,#32 25（空轉(zhuǎn)） 26BNEZR1,Loop 27（空轉(zhuǎn)） 2818147結(jié)果分析結(jié)果分析: :這個循環(huán)每遍共使用了這個循環(huán)每遍共使用了2828個時鐘周期個時鐘周期有有4 4個個循環(huán)體，完成循環(huán)體，完成4 4個個元素的操作元素的操作平均每個元素使用平均每個元素使用28/4=728/4=7個時鐘周期個時鐘周期原始循環(huán)的每個元素需要原始循環(huán)的每個元素需要1010個時鐘周期個時鐘周期節(jié)省的時間節(jié)省的時間: :從減少循環(huán)控制的開銷中獲得的從減少循環(huán)控制的開銷中獲得的在整個展開后的循環(huán)中，實際指令只有在整個展開

15、后的循環(huán)中，實際指令只有1414條，條，其它其它1313個周期都是空轉(zhuǎn)。個周期都是空轉(zhuǎn)。 效率并不高效率并不高19147(2)(2) 對指令序列進(jìn)行優(yōu)化調(diào)度對指令序列進(jìn)行優(yōu)化調(diào)度指令流出時鐘指令流出時鐘Loop:LDF0,0(R1)1 LDF6,-8(R1)2 LDF10,-16(R1)3 LDF14,-24(R1)4 ADDDF4,F0,F25 ADDDF8,F6,F26 ADDDF12,F10,F27 ADDDF16,F14,F28 SD0(R1),F49 SD-8(R1),F810 SUBIR1,R1,#3212 SD16(R1),F1211 BNEZR1,Loop13 SD8(R1),

16、F161420147結(jié)果分析：結(jié)果分析：沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待整個循環(huán)僅僅使用了整個循環(huán)僅僅使用了1414個時鐘周期個時鐘周期平均每個元素的操作使用平均每個元素的操作使用14/4=3.514/4=3.5個時鐘周期個時鐘周期循環(huán)展開循環(huán)展開和和指令調(diào)度指令調(diào)度可以有效地提高循環(huán)級并可以有效地提高循環(huán)級并行性。行性。這種循環(huán)級并行性的提高實際是通過實現(xiàn)指令級這種循環(huán)級并行性的提高實際是通過實現(xiàn)指令級并行來達(dá)到的。并行來達(dá)到的?？梢允褂镁幾g器來完成，也可以通過硬件來可以使用編譯器來完成，也可以通過硬件來完成。完成。211474. 4. 循環(huán)展開和指令調(diào)度時要注意的問題循

17、環(huán)展開和指令調(diào)度時要注意的問題(1) (1) 保證正確性保證正確性(2) (2) 注意有效性注意有效性(3) (3) 使用不同的寄存器使用不同的寄存器(4) (4) 盡可能減少循環(huán)控制中的測試指令和分支指令盡可能減少循環(huán)控制中的測試指令和分支指令(5) (5) 注意對存儲器數(shù)據(jù)的相關(guān)性分析注意對存儲器數(shù)據(jù)的相關(guān)性分析(6) (6) 注意新的相關(guān)性注意新的相關(guān)性5. 5. 實現(xiàn)循環(huán)展開的關(guān)鍵實現(xiàn)循環(huán)展開的關(guān)鍵 分析清楚代碼中指令的相關(guān)性，然后通過分析清楚代碼中指令的相關(guān)性，然后通過 指令調(diào)度來消除相關(guān)指令調(diào)度來消除相關(guān). .221474.1.2 相關(guān)性開發(fā)指令級并行的開發(fā)指令級并行的關(guān)鍵關(guān)鍵存在

18、相關(guān)的兩條指令，不能改變它們的順序。存在相關(guān)的兩條指令，不能改變它們的順序。相關(guān)是否導(dǎo)致流水線的空轉(zhuǎn)，還與流水線的相關(guān)是否導(dǎo)致流水線的空轉(zhuǎn)，還與流水線的組織與結(jié)構(gòu)有關(guān)。組織與結(jié)構(gòu)有關(guān)。程序中的相關(guān)主要有以下三種程序中的相關(guān)主要有以下三種 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) 名相關(guān)名相關(guān) 控制相關(guān)控制相關(guān)231471. 1. 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)（data dependencedata dependence）對于對于指令指令i i和和指令指令j j，如果，如果 (1) (1) 指令指令j j使用使用指令指令i i產(chǎn)生的結(jié)果，或者產(chǎn)生的結(jié)果，或者 (2) (2) 指令指令j j與與指令指令k k數(shù)據(jù)相關(guān)，數(shù)據(jù)相關(guān)，指令

19、指令k k與與指令指令i i數(shù)據(jù)相數(shù)據(jù)相 關(guān)，則關(guān)，則指令指令j j與與指令指令i i數(shù)據(jù)相關(guān)。數(shù)據(jù)相關(guān)。 數(shù)據(jù)相關(guān)具有傳遞性。數(shù)據(jù)相關(guān)具有傳遞性。數(shù)據(jù)相關(guān)是兩條指令之間存在一個先寫后讀相關(guān)鏈。數(shù)據(jù)相關(guān)是兩條指令之間存在一個先寫后讀相關(guān)鏈。相關(guān)鏈貫穿整個程序，是程序的內(nèi)在特征。相關(guān)鏈貫穿整個程序，是程序的內(nèi)在特征。這種相關(guān)鏈?zhǔn)菍?dǎo)致流水線停頓的原因之一。這種相關(guān)鏈?zhǔn)菍?dǎo)致流水線停頓的原因之一。24147指令的相關(guān)距離指令的相關(guān)距離（distancedistance） 兩條指令之間的指令條數(shù)。兩條指令之間的指令條數(shù)。分析數(shù)據(jù)相關(guān)的主要工作分析數(shù)據(jù)相關(guān)的主要工作: : (1) (1) 確定指令的相關(guān)性

20、，找到所有可能產(chǎn)生停確定指令的相關(guān)性，找到所有可能產(chǎn)生停 頓的地方。頓的地方。 (2) (2) 確定必須嚴(yán)格遵守的數(shù)據(jù)的計算順序。確定必須嚴(yán)格遵守的數(shù)據(jù)的計算順序。 (3) (3) 確定指令的最大相關(guān)距離，確定程序中可確定指令的最大相關(guān)距離，確定程序中可 能的最大并行性。能的最大并行性。251472. 2. 名相關(guān)（名相關(guān)（name dependencename dependence）指令使用的寄存器或存儲器稱為指令使用的寄存器或存儲器稱為名名。如果兩條指令使用相同的名，但是它們之間并如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流，則稱之為沒有數(shù)據(jù)流，則稱之為名相關(guān)名相關(guān)。指令指令j j與

21、與指令指令i i之間名相關(guān)有以下兩種：之間名相關(guān)有以下兩種： (1) (1) 反相關(guān)反相關(guān)（anti-dependenceanti-dependence） (2) (2) 輸出相關(guān)輸出相關(guān)（output dependenceoutput dependence）26147 消除名相關(guān)消除名相關(guān)名相關(guān)的指令之間沒有數(shù)據(jù)交換。名相關(guān)的指令之間沒有數(shù)據(jù)交換。如果一條指令中的名改變了，并不影響另外一如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。條指令的執(zhí)行。通過改變指令中操作數(shù)的名來消除名相關(guān)，這通過改變指令中操作數(shù)的名來消除名相關(guān)，這就是就是換名（換名（renamingrenaming）技術(shù)）

22、技術(shù)。對于寄存器操作數(shù)進(jìn)行換名稱為對于寄存器操作數(shù)進(jìn)行換名稱為寄存器換名寄存器換名。 （register renamingregister renaming）可以用編譯器靜態(tài)完成或硬件動態(tài)完成?？梢杂镁幾g器靜態(tài)完成或硬件動態(tài)完成。27147例：例：我們對我們對例例4.24.2編譯過程進(jìn)行分析，來仔細(xì)考察編譯過程進(jìn)行分析，來仔細(xì)考察 換名的過程。換名的過程。 (1) (1) 首先，僅僅去除首先，僅僅去除4 4遍循環(huán)體中的分支指令，遍循環(huán)體中的分支指令， 得到以下由得到以下由1717條指令構(gòu)成的指令序列：條指令構(gòu)成的指令序列：28147Loop: LD F0 , 0(R1) ADDD F4 , F

23、0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LDF0 , 0(R1)ADDDF4 , F0 , F2 SD0(R1) , F4SUBIR1 , R1 , #8 LDF0 , 0(R1)ADDDF4 , F0 , F2 SD0(R1) , F4SUBIR1 , R1 , #8BNEZR1 , Loop29147(2) (2) 編譯器可以通過對相關(guān)鏈上存儲器訪問偏移編譯器可以通過對相關(guān)鏈上存儲器訪問偏移 量量的直接調(diào)整，將前的直接調(diào)整，將

24、前3 3條條SUBISUBI指令消除掉，從而得到下指令消除掉，從而得到下面一個面一個1414條指令構(gòu)成的指令序列：條指令構(gòu)成的指令序列： 30147Loop: LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 LD F0 , -8(R1) ADDD F4 , F0 , F2 SD -8(R1) , F4 LD F0 , -16(R1) ADDD F4 , F0 , F2 SD -16(R1) , F4 LD F0 , -24(R1) ADDD F4 , F0 , F2 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1

25、 , Loop31147(3) (3) 通過寄存器通過寄存器換名，消除名換名，消除名相關(guān)。相關(guān)。 得到右邊得到右邊的指令序列：的指令序列： Loop:LDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4LDF6 , -8(R1)ADDD F8 , F6 , F2SD-8(R1) , F8LDF10 , -16(R1)ADDD F12 , F10 , F2SD-16(R1) , F12LDF14 , -24(R1)ADDD F16 , F14 , F2SD-24(R1) , F16SUBIR1 , R1 , #32BNEZR1 , Loop換名操作需要較大的寄存器開

26、銷。換名操作需要較大的寄存器開銷。 321473 3控制相關(guān)（控制相關(guān)（control dependencecontrol dependence） 控制相關(guān)控制相關(guān)是指由分支指令引起的相關(guān)。是指由分支指令引起的相關(guān)。 典型的程序結(jié)構(gòu)是典型的程序結(jié)構(gòu)是“if-thenif-then”結(jié)構(gòu)。結(jié)構(gòu)。 看下面一個示例：看下面一個示例： if p1 S1; ; S; if p2 S2; ;33147 處理控制相關(guān)的處理控制相關(guān)的兩個原則兩個原則： (1) (1) 與控制相關(guān)的指令不能移到分支指令之與控制相關(guān)的指令不能移到分支指令之 前，即控制有關(guān)的指令不能調(diào)度到分支前，即控制有關(guān)的指令不能調(diào)度到分支 指

27、令控制范圍以外；指令控制范圍以外； (2) (2) 與控制無關(guān)的指令不能移到分支指令之與控制無關(guān)的指令不能移到分支指令之 后，即控制無關(guān)的指令不能調(diào)度到分支后，即控制無關(guān)的指令不能調(diào)度到分支 指令控制范圍以內(nèi)。指令控制范圍以內(nèi)。34147再考察再考察例例4.24.2： 假設(shè)循環(huán)展開時，循環(huán)控制分支指令沒有去除，假設(shè)循環(huán)展開時，循環(huán)控制分支指令沒有去除，則指令序列如下：則指令序列如下： 35147Loop: LDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BEQZR1 , ExitLDF0 , 0(R1)ADDD F4 , F0

28、, F2SD0(R1) , F4SUBIR1 , R1 , #8BEQZR1 , Exit LDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BEQZR1 , ExitLDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BNEZR1 , Loop Exit: 361474.2指令的動態(tài)調(diào)度靜態(tài)調(diào)度靜態(tài)調(diào)度：在出現(xiàn)數(shù)據(jù)相關(guān)時，為了消除或：在出現(xiàn)數(shù)據(jù)相關(guān)時，為了消除或 者減少流水線空轉(zhuǎn)，編譯器確定并分離出程者減少流水線空轉(zhuǎn)，編譯器確定并分離出程 序中存在相關(guān)的指令，然后進(jìn)行

29、指令調(diào)度，序中存在相關(guān)的指令，然后進(jìn)行指令調(diào)度， 并對代碼進(jìn)行優(yōu)化。并對代碼進(jìn)行優(yōu)化。動態(tài)調(diào)度動態(tài)調(diào)度：通過硬件重新安排指令的執(zhí)行順序，：通過硬件重新安排指令的執(zhí)行順序， 來調(diào)整相關(guān)指令實際執(zhí)行時的關(guān)系，減少處理來調(diào)整相關(guān)指令實際執(zhí)行時的關(guān)系，減少處理 器空轉(zhuǎn)。器空轉(zhuǎn)。 以硬件復(fù)雜性的顯著增加為代價。以硬件復(fù)雜性的顯著增加為代價。 371474.2.1 動態(tài)調(diào)度的原理 到目前為止我們所使用流水線的最大的到目前為止我們所使用流水線的最大的局限性局限性: : 指令必須順序流出指令必須順序流出看下面一段代碼：看下面一段代碼： DIVD F0 , F2 , F4; S1S1 ADDD F10 , F0

30、 , F8; S2S2：S2S2對對S1S1數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān), , S2 S2被阻塞被阻塞 SUBD F12 , F8 ,F14; ;S3S3：S3S3與與S1S1、S2S2都沒都沒 有相關(guān)有相關(guān), ,但也被阻塞但也被阻塞38147為了允許亂序執(zhí)行，我們將基本流水線的譯碼階段為了允許亂序執(zhí)行，我們將基本流水線的譯碼階段 再分為兩個階段：再分為兩個階段： (1)(1)流出流出（IssueIssue，ISIS）：指令譯碼，檢查是否存）：指令譯碼，檢查是否存 在結(jié)構(gòu)阻塞。在結(jié)構(gòu)阻塞。 (2)(2)讀操作數(shù)讀操作數(shù)（Read OperandsRead Operands，RORO）：當(dāng)沒有數(shù)）：當(dāng)沒有數(shù)

31、 據(jù)相關(guān)引發(fā)的阻塞時就讀操作數(shù)。據(jù)相關(guān)引發(fā)的阻塞時就讀操作數(shù)。指令亂序結(jié)束帶來的指令亂序結(jié)束帶來的最大問題最大問題: : 異常處理比較復(fù)雜異常處理比較復(fù)雜 ( (精確異常處理、不精確異常處理精確異常處理、不精確異常處理) ) 391474.2.2 動態(tài)調(diào)度算法之一：記分牌 例：例：數(shù)據(jù)先讀后寫（數(shù)據(jù)先讀后寫（WARWAR）相關(guān)引起的阻塞）相關(guān)引起的阻塞 代碼序列：代碼序列： DIVDF0 , F2 , F4 ADDDF10 , F0 , F8 SUBDF8 , F8 , F14 指令亂序執(zhí)行時就會出現(xiàn)指令亂序執(zhí)行時就會出現(xiàn)先讀后寫相關(guān)先讀后寫相關(guān)。 記分牌技術(shù)的目標(biāo)：記分牌技術(shù)的目標(biāo)： 在資源

32、充足時，盡可能早地執(zhí)行沒有數(shù)據(jù)阻在資源充足時，盡可能早地執(zhí)行沒有數(shù)據(jù)阻 塞的指令，達(dá)到每個時鐘周期執(zhí)行一條指令。塞的指令，達(dá)到每個時鐘周期執(zhí)行一條指令。 40147 要發(fā)揮指令亂序執(zhí)行的好處，必須有多條指令要發(fā)揮指令亂序執(zhí)行的好處，必須有多條指令 同時處于執(zhí)行階段，這就要求有同時處于執(zhí)行階段，這就要求有多個功能部件多個功能部件 或功能部件流水化或者兩者兼有或功能部件流水化或者兩者兼有。 假設(shè)：處理器采用多個功能部件。假設(shè)：處理器采用多個功能部件。 CDC 6600CDC 6600具有具有1616個功能部件：個功能部件： 4 4個個浮點部件，浮點部件， 5 5個個存儲器訪問部件存儲器訪問部件 7

33、 7個個整數(shù)操作部件整數(shù)操作部件 在在DLXDLX中，假設(shè)有中，假設(shè)有2 2個個乘法器、乘法器、1 1個個加法器、加法器、1 1 個個除法部件和除法部件和1 1個個整數(shù)部件。整數(shù)部件。1.1.采用記分牌技術(shù)的采用記分牌技術(shù)的DLXDLX處理器的基本結(jié)構(gòu)。處理器的基本結(jié)構(gòu)。 寄存器 整數(shù)部件 記分牌 浮點除法 浮點乘法 浮點乘法 數(shù)據(jù)總線 控制/狀態(tài) 控制/狀態(tài) 浮點加法 圖圖4.1 4.1 具有記分牌的具有記分牌的DLXDLX處理器基本結(jié)構(gòu)處理器基本結(jié)構(gòu) 42147 記分牌電路負(fù)責(zé)記錄資源的使用，并負(fù)責(zé)相記分牌電路負(fù)責(zé)記錄資源的使用，并負(fù)責(zé)相關(guān)檢測，控制指令的流出和執(zhí)行。關(guān)檢測，控制指令的流出

34、和執(zhí)行。 2.2.每條指令在流水線中的執(zhí)行過程分為每條指令在流水線中的執(zhí)行過程分為四段四段： (1) (1) 流出（流出（IssueIssue，記為，記為ISIS） 如果本指令所需的功能部件有空閑，并如果本指令所需的功能部件有空閑，并 且其它正在執(zhí)行的指令使用的目的寄存器與且其它正在執(zhí)行的指令使用的目的寄存器與 本指令的不同，記分牌就向功能部件流出本本指令的不同，記分牌就向功能部件流出本 指令，并修改記分牌內(nèi)部的數(shù)據(jù)記錄。指令，并修改記分牌內(nèi)部的數(shù)據(jù)記錄。 解決了指令間存在的解決了指令間存在的結(jié)構(gòu)相關(guān)或?qū)懞髮懴嚓P(guān)結(jié)構(gòu)相關(guān)或?qū)懞髮懴嚓P(guān)。 43147(2) (2) 讀操作數(shù)（讀操作數(shù)（Read O

35、perandRead Operand，記為，記為RORO）。）。 記分牌需要監(jiān)測源操作數(shù)寄存器中數(shù)據(jù)的記分牌需要監(jiān)測源操作數(shù)寄存器中數(shù)據(jù)的 有效性，如果前面已流出的還在運行的指令不有效性，如果前面已流出的還在運行的指令不 對本指令的源操作數(shù)寄存器進(jìn)行寫操作，或者對本指令的源操作數(shù)寄存器進(jìn)行寫操作，或者 一個正在工作的功能部件已經(jīng)完成了對這個寄一個正在工作的功能部件已經(jīng)完成了對這個寄 存器的寫操作，那么此操作數(shù)有效。當(dāng)操作數(shù)存器的寫操作，那么此操作數(shù)有效。當(dāng)操作數(shù) 有效后，記分牌將啟動本指令的功能部件讀操有效后，記分牌將啟動本指令的功能部件讀操 作數(shù)并開始執(zhí)行。作數(shù)并開始執(zhí)行。 解決了數(shù)據(jù)的解決

36、了數(shù)據(jù)的先寫后讀（先寫后讀（RAWRAW）相關(guān)）相關(guān)。 通過以上步驟，記分牌動態(tài)解決了結(jié)構(gòu)相通過以上步驟，記分牌動態(tài)解決了結(jié)構(gòu)相 和數(shù)據(jù)相關(guān)引發(fā)的阻塞，指令可能亂序流出。和數(shù)據(jù)相關(guān)引發(fā)的阻塞，指令可能亂序流出。 44147(3) (3) 執(zhí)行（執(zhí)行（ExecutionExecution，記為，記為EXEX）。）。(4) (4) 寫結(jié)果（寫結(jié)果（Write ResultWrite Result，記為，記為WRWR）。）。 記分牌知道指令執(zhí)行完畢后，如果目標(biāo)記分牌知道指令執(zhí)行完畢后，如果目標(biāo) 寄存器空閑，就將結(jié)果寫入到目標(biāo)寄存器中，寄存器空閑，就將結(jié)果寫入到目標(biāo)寄存器中， 然后釋放本指令使用的所有

37、資源。然后釋放本指令使用的所有資源。 檢測先讀后寫（檢測先讀后寫（WARWAR）相關(guān)）相關(guān) 在出現(xiàn)以下的情況時，就不允許指令寫結(jié)果在出現(xiàn)以下的情況時，就不允許指令寫結(jié)果: : 前面的某條指令（按順序流出）還沒有讀取操作數(shù)；前面的某條指令（按順序流出）還沒有讀取操作數(shù)； 其中某個源操作數(shù)寄存器與本指令的目的寄存器相同。其中某個源操作數(shù)寄存器與本指令的目的寄存器相同。45147 存在一個問題存在一個問題: :就是功能部件到寄存器文件的就是功能部件到寄存器文件的數(shù)據(jù)總線寬度是有限的，當(dāng)流水線中進(jìn)入讀操作數(shù)據(jù)總線寬度是有限的，當(dāng)流水線中進(jìn)入讀操作數(shù)段（數(shù)段（RORO）和寫結(jié)果段（）和寫結(jié)果段（WBWB

38、）的功能部件總數(shù)超）的功能部件總數(shù)超過可用總線的數(shù)目，這會導(dǎo)致過可用總線的數(shù)目，這會導(dǎo)致結(jié)構(gòu)阻塞結(jié)構(gòu)阻塞。 3. 3. 記分牌需要紀(jì)錄的信息分為三部分：記分牌需要紀(jì)錄的信息分為三部分： (1) (1) 指令狀態(tài)表指令狀態(tài)表 記錄正在執(zhí)行的各條指令已經(jīng)進(jìn)入記記錄正在執(zhí)行的各條指令已經(jīng)進(jìn)入記 分牌分牌DLXDLX流水線四段中的哪一段。流水線四段中的哪一段。46147(2)(2) 功能部件狀態(tài)表功能部件狀態(tài)表 紀(jì)錄各個功能部件的狀態(tài)。每個功能部件紀(jì)錄各個功能部件的狀態(tài)。每個功能部件 在狀態(tài)表中都由以下在狀態(tài)表中都由以下九個域九個域來紀(jì)錄：來紀(jì)錄： BusyBusy： 指示功能部件是否在工作指示功能部

39、件是否在工作 OpOp： 功能部件當(dāng)前執(zhí)行的操作功能部件當(dāng)前執(zhí)行的操作 FiFi： 目的寄存器編號目的寄存器編號 FjFj，fkfk：源寄存器編號源寄存器編號 QjQj，QkQk：向向RjRj，RkRk中寫結(jié)果的功能部件中寫結(jié)果的功能部件 RjRj，RkRk：表示表示FjFj，F(xiàn)kFk是否就緒，是否就緒， 是否已經(jīng)被使用是否已經(jīng)被使用47147(3) (3) 結(jié)果寄存器狀態(tài)表結(jié)果寄存器狀態(tài)表 每個寄存器在表中有一個域，用于紀(jì)錄寫每個寄存器在表中有一個域，用于紀(jì)錄寫 入本寄存器的功能部件（編號）。如果當(dāng)前正入本寄存器的功能部件（編號）。如果當(dāng)前正 在運行的功能部件沒有需要寫入本寄存器的，在運行的

40、功能部件沒有需要寫入本寄存器的， 則相應(yīng)域置為空。則相應(yīng)域置為空。4. 4. DLXDLX記分牌所要維護(hù)的數(shù)據(jù)結(jié)構(gòu)記分牌所要維護(hù)的數(shù)據(jù)結(jié)構(gòu) 給出下列代碼運行過程中記分牌保存的信息給出下列代碼運行過程中記分牌保存的信息. . 48147LD F6 , 34(R2)LD F2 , 45(R3)MULTDF0 , F2 , F4SUBD F8 , F6 , F2DIVD F10 , F0 , F6ADDDF6 , F8 , F249147指 令 指令狀態(tài)表 IS RO EX WR LD F6 , 34(R2) LD F2 , 45(R3) MULTDF0 , F2 , F4 SUBDF8 , F6

41、, F2 DIVDF10 , F0 , F6 ADDDF6 , F8 , F2 圖圖4.2 DLX4.2 DLX記分牌信息組成和記錄的信息記分牌信息組成和記錄的信息 部件名稱 功能部件狀態(tài)表 Busy Op Fi Fj Fk Qj Qk Rj Rk整數(shù) yes LD F2 R3 no乘法1 yes MULTD F0 F2 F4 整數(shù) no yes乘法2 no加法 yes SUBD F8 F6 F2 整數(shù) yes no除法 yes DIVD F10 F0 F6 乘法1 no yes 結(jié)果寄存器狀態(tài)表 F0 F2 F4 F6 F8 F10 F30部件名稱 乘法1 整數(shù) 加法 除法51147 例例4

42、.34.3 假設(shè)浮點流水線中執(zhí)行的延遲如下：假設(shè)浮點流水線中執(zhí)行的延遲如下： 加法需加法需2 2個個時鐘周期時鐘周期 乘法需乘法需1010個個時鐘周期時鐘周期 除法需除法需4040個個時鐘周期時鐘周期 代碼段和記分牌信息的起始點狀態(tài)代碼段和記分牌信息的起始點狀態(tài)如圖如圖4.24.2。分。分別給出別給出MULTDMULTD和和DIVDDIVD準(zhǔn)備寫結(jié)果之前的記分牌狀態(tài)。準(zhǔn)備寫結(jié)果之前的記分牌狀態(tài)。 解：解： 在分析記分牌狀態(tài)之前，首先需要分析指令之在分析記分牌狀態(tài)之前，首先需要分析指令之間存在的相關(guān)性，因為相關(guān)性會影響指令進(jìn)入記分間存在的相關(guān)性，因為相關(guān)性會影響指令進(jìn)入記分牌牌DLXDLX流水線

43、的相應(yīng)段。流水線的相應(yīng)段。 52147(1) (1) 第二個第二個LDLD指令到指令到MULDMULD和和SUBDSUBD、MULTDMULTD到到DIVDDIVD 之間以及之間以及SUBDSUBD到到ADDDADDD之間存在著先寫后讀相關(guān)；之間存在著先寫后讀相關(guān)；(2) (2) DIVDDIVD和和ADDDADDD之間存在著先讀后寫相關(guān)；之間存在著先讀后寫相關(guān)；(3) (3) ADDDADDD和和SUBDSUBD指令關(guān)于浮點加法部件還存在著結(jié)指令關(guān)于浮點加法部件還存在著結(jié) 構(gòu)相關(guān)。構(gòu)相關(guān)。 圖圖4.34.3和和圖圖4.44.4分別給出了分別給出了MULTDMULTD指令和指令和DIVDDIV

44、D 指令將要寫結(jié)果時記分牌的狀態(tài)。指令將要寫結(jié)果時記分牌的狀態(tài)。 53147指 令 指令狀態(tài)表 IS RO EX WR LD F6 , 34(R2) LD F2 , 45(R3) MULTDF0 , F2 , F4 SUBDF8 , F6 , F2 DIVDF10 , F0 , F6 ADDDF6 , F8 , F2 圖圖4.3 4.3 程序段執(zhí)行到程序段執(zhí)行到MULTDMULTD將要寫結(jié)果時記分牌的狀態(tài)將要寫結(jié)果時記分牌的狀態(tài) 部件名稱 功能部件狀態(tài)表 Busy Op Fi Fj Fk Qj Qk Rj Rk整數(shù) no 乘法1 yes MULTD F0 F2 F4 no no乘法2 no加法

45、 yes ADDD F6 F8 F2 no no除法 yes DIVD F10 F0 F6 乘法1 no yes 結(jié)果寄存器狀態(tài)表 F0 F2 F4 F6 F8 F10 F30部件名稱 乘法1 加法 除法55147指 令 指令狀態(tài)表 IS RO EX WRLD F6 , 34(R2) LD F2 , 45(R3) MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2 圖圖4.4 4.4 程程序段執(zhí)行到序段執(zhí)行到DIVDDIVD將要寫結(jié)果時記分牌的狀態(tài)將要寫結(jié)果時記分牌的狀態(tài) 部件名稱 功能部件狀態(tài)表

46、Busy Op Fi Fj Fk Qj Qk Rj Rk整數(shù) no 乘法1 no乘法2 no加法 no除法 yes DIVD F10 F0 F6 no no 結(jié)果寄存器狀態(tài)表 F0 F2 F4 F6 F8 F10 F30部件名稱 除法571475.5.分析記分牌是如何控制指令執(zhí)行的。分析記分牌是如何控制指令執(zhí)行的。 操作在記分牌流水線中前進(jìn)時，記分牌必須操作在記分牌流水線中前進(jìn)時，記分牌必須 記錄與操作有關(guān)的信息，如寄存器號等。記錄與操作有關(guān)的信息，如寄存器號等。 約定：約定： FjFj（FUFU）S1S1 ：將寄存器將寄存器S1S1的名字送入的名字送入FjFj（FUFU） FU FU ： 指

47、令使用的功能部件指令使用的功能部件 D D ： 目的寄存器的名字目的寄存器的名字 S1S1和和S2S2： 源操作數(shù)寄存器的名字，源操作數(shù)寄存器的名字， OpOp： 進(jìn)行的操作進(jìn)行的操作 FjFj（FUFU）：）： 功能部件功能部件FUFU的的FjFj域域 resultresult（D D）：）：結(jié)果寄存器狀態(tài)表中對應(yīng)于寄存結(jié)果寄存器狀態(tài)表中對應(yīng)于寄存器器D D的內(nèi)容，為產(chǎn)生寄存器的內(nèi)容，為產(chǎn)生寄存器D D中結(jié)果的功能部件名。中結(jié)果的功能部件名。 58147 流出（流出（ISIS） (1) (1) 進(jìn)入條件進(jìn)入條件 not Busy(FU) and not result(not Busy(FU)

48、 and not result(D D) )； /判斷結(jié)構(gòu)阻塞和寫后寫判斷結(jié)構(gòu)阻塞和寫后寫 (2) (2) 計分牌記錄內(nèi)容計分牌記錄內(nèi)容 Busy(FU)yes;Busy(FU)yes; OP(FU)Op OP(FU)Op； Fi(FU)Fi(FU)D D； Fj(FU)Fj(FU)S1S1； Fk(FU)Fk(FU)S2S2； 59147 Qjresult(Qjresult(S1S1) )；/處理處理S1S1的的FUFU Qkresult(Qkresult(S2S2) )；/處理處理S2S2的的FUFU Rjnot QjRjnot Qj； /Rj/Rj是否可用？是否可用？ Rknot QkR

49、knot Qk； /Rk/Rk是否可用？是否可用？ result(result(D D)FU)FU； /D D被被FUFU用作目的寄存器用作目的寄存器讀操作數(shù)（讀操作數(shù)（RORO） (1)(1)進(jìn)入條件進(jìn)入條件 RjRjRk;Rk; /解決先寫后讀，兩個源操作數(shù)須同時就緒解決先寫后讀，兩個源操作數(shù)須同時就緒 60147 (2) (2)計分牌記錄內(nèi)容計分牌記錄內(nèi)容 RjnoRjno；/已經(jīng)讀走了就緒的數(shù)據(jù)已經(jīng)讀走了就緒的數(shù)據(jù)RjRj RknoRkno；/已經(jīng)讀走了就緒的數(shù)據(jù)已經(jīng)讀走了就緒的數(shù)據(jù)RkRk Qj0Qj0；/不再等待其它不再等待其它FUFU的計算結(jié)果的計算結(jié)果 Qk0Qk0； 執(zhí)行（執(zhí)

50、行（EXEX） (1)(1)結(jié)束條件結(jié)束條件 功能部件操作結(jié)束功能部件操作結(jié)束61147寫結(jié)果（寫結(jié)果（WRWR） (1)(1)進(jìn)入條件進(jìn)入條件 f(Fj(f)f(Fj(f) Fi(FU) or Rj(f)=no)Fi(FU) or Rj(f)=no) and (Fk(f) and (Fk(f) Fi(FU) or Rk(f)=no);Fi(FU) or Rk(f)=no); / /檢查是否存在先讀后寫檢查是否存在先讀后寫 (2)(2)計分牌記錄內(nèi)容計分牌記錄內(nèi)容 f(if Qj(f)=FU then Rj(f)yes)f(if Qj(f)=FU then Rj(f)yes)； /有等結(jié)果的指

51、令，則數(shù)據(jù)可用有等結(jié)果的指令，則數(shù)據(jù)可用 f(if Qk(f)=FU then Rk(f)yes)f(if Qk(f)=FU then Rk(f)yes)； result(Fi(FU)0result(Fi(FU)0； /沒有沒有FUFU使用寄存器使用寄存器FiFi為目的寄存器為目的寄存器 busy(FU)=nobusy(FU)=no/釋放釋放FUFU621476. 6. 記分牌的性能受限于以下幾個方面：記分牌的性能受限于以下幾個方面： (1) (1) 程序指令中可開發(fā)的并行性，即是否存在程序指令中可開發(fā)的并行性，即是否存在 可以并行執(zhí)行的不相關(guān)的指令。可以并行執(zhí)行的不相關(guān)的指令。 (2) (2

52、) 記分牌容量。記分牌的容量決定了流水線記分牌容量。記分牌的容量決定了流水線 能在多大范圍內(nèi)尋找不相關(guān)指令。能在多大范圍內(nèi)尋找不相關(guān)指令。 流水線中可以同時容納的指令數(shù)量又流水線中可以同時容納的指令數(shù)量又 稱為稱為指令窗口指令窗口。 (3) (3) 功能部件的數(shù)目和種類。功能部件的總數(shù)功能部件的數(shù)目和種類。功能部件的總數(shù) 決定了結(jié)構(gòu)沖突的嚴(yán)重程度。決定了結(jié)構(gòu)沖突的嚴(yán)重程度。 (4) (4) 反相關(guān)和輸出相關(guān)。引起計分牌中先讀后反相關(guān)和輸出相關(guān)。引起計分牌中先讀后 寫和寫后寫阻塞。寫和寫后寫阻塞。631474.2.3 動態(tài)調(diào)度算法之二：Tomasulo算法 Tomasulo Tomasulo算法

53、將記分牌的關(guān)鍵部分和寄存器換名算法將記分牌的關(guān)鍵部分和寄存器換名 技術(shù)結(jié)合在一起。技術(shù)結(jié)合在一起。 基本核心：基本核心：通過寄存器換名來消除寫后寫和先讀通過寄存器換名來消除寫后寫和先讀 后寫相關(guān)而可能引發(fā)的流水線阻塞。后寫相關(guān)而可能引發(fā)的流水線阻塞。 下面的討論是基于下面的討論是基于DLXDLX的浮點流水線功能部件。的浮點流水線功能部件。 TomasuloTomasulo算法中，寄存器換名是通過保留站來實算法中，寄存器換名是通過保留站來實 現(xiàn)，它保存等待流出和正在流出指令所需要的操現(xiàn)，它保存等待流出和正在流出指令所需要的操 作數(shù)。作數(shù)。 TomasuloTomasulo算法的基本思想算法的基本

54、思想64147 只要操作數(shù)有效，就將其取到保留站，避免只要操作數(shù)有效，就將其取到保留站，避免指令流出時才到寄存器中取數(shù)據(jù)。指令流出時才到寄存器中取數(shù)據(jù)。指令的執(zhí)行結(jié)果直接送到等待數(shù)據(jù)的其它保指令的執(zhí)行結(jié)果直接送到等待數(shù)據(jù)的其它保留站中去。留站中去。一條指令流出時，存放操作數(shù)的寄存器名被一條指令流出時，存放操作數(shù)的寄存器名被換成為對應(yīng)于該寄存器保留站的名稱。換成為對應(yīng)于該寄存器保留站的名稱。 除了寄存器換名技術(shù)，除了寄存器換名技術(shù)，TomasuloTomasulo算法和記分牌在算法和記分牌在 結(jié)構(gòu)上還有兩處顯著的不同：結(jié)構(gòu)上還有兩處顯著的不同： 65147 沖突檢測和指令執(zhí)行控制機制分開。沖突檢

55、測和指令執(zhí)行控制機制分開。 計算的結(jié)果通過相關(guān)專用通路直接從功能部件計算的結(jié)果通過相關(guān)專用通路直接從功能部件 進(jìn)入對應(yīng)的保留站進(jìn)行緩沖，而不一定是寫到進(jìn)入對應(yīng)的保留站進(jìn)行緩沖，而不一定是寫到 寄存器。寄存器。 （相關(guān)專用通路通過一條數(shù)據(jù)總線來實現(xiàn)）（相關(guān)專用通路通過一條數(shù)據(jù)總線來實現(xiàn)） 指 令 隊 列 3 2 1 2 1 浮點寄存器組 1 2 3 4 浮點加法器 浮點乘法器 公共數(shù)據(jù)總線（CDB） 存的數(shù)據(jù) 從指令部件來 保留站 存儲器部件 取緩沖 6 5 4 3 2 1 地址部件 地址 取的數(shù)據(jù) 存-取操作 浮點操作 操作數(shù)總線 操作總線 存緩沖 1.1.采用采用TomasuloTomasu

56、lo算法的算法的DLXDLX浮點部件的基本結(jié)構(gòu)浮點部件的基本結(jié)構(gòu) 67147 保留站保留站中保存已流出并等待到本功能部件執(zhí)行的中保存已流出并等待到本功能部件執(zhí)行的 操作（指令）；還保存指令執(zhí)行所需的控制信息。操作（指令）；還保存指令執(zhí)行所需的控制信息。 如果該操作的源操作數(shù)在寄存器中已經(jīng)就緒，如果該操作的源操作數(shù)在寄存器中已經(jīng)就緒，剛將該操作數(shù)取來，保存到保留站中；剛將該操作數(shù)取來，保存到保留站中；如果操作數(shù)還沒有計算出來，則保留站中記如果操作數(shù)還沒有計算出來，則保留站中記錄這個操作數(shù)將由誰計算出來，即指明它由錄這個操作數(shù)將由誰計算出來，即指明它由哪個功能部件產(chǎn)生。哪個功能部件產(chǎn)生。 取緩沖和

57、存緩沖取緩沖和存緩沖保存的是讀保存的是讀/ /寫存儲器的數(shù)據(jù)或?qū)懘鎯ζ鞯臄?shù)據(jù)或 地址。地址。68147浮點寄存器通過一對操作數(shù)總線連到功能部件，浮點寄存器通過一對操作數(shù)總線連到功能部件，通過其中通過其中一條總線連到公共數(shù)據(jù)總線，再送到一條總線連到公共數(shù)據(jù)總線，再送到存緩沖。存緩沖。功能部件的計算結(jié)果和從存儲器讀取的數(shù)據(jù)都送功能部件的計算結(jié)果和從存儲器讀取的數(shù)據(jù)都送到公用數(shù)據(jù)總線上，除了取緩沖的輸入和存緩沖到公用數(shù)據(jù)總線上，除了取緩沖的輸入和存緩沖的輸出以外，所有部分均與公用數(shù)據(jù)總線相連。的輸出以外，所有部分均與公用數(shù)據(jù)總線相連。兩個運算功能部件兩個運算功能部件 浮點乘法器完成乘法和除法操作浮點

58、乘法器完成乘法和除法操作 浮點加法器完成加法和減法操作浮點加法器完成加法和減法操作69147 2. 2.指令流水線的分段情況指令流水線的分段情況 使用使用TomasuloTomasulo算法的流水線需三段：算法的流水線需三段： (1) (1) 流出（流出（IssueIssue）：從浮點操作隊列中取一條指令。）：從浮點操作隊列中取一條指令。 (2) (2) 執(zhí)行（執(zhí)行（ExecuteExecute） (3) (3) 寫結(jié)果（寫結(jié)果（Write ResultWrite Result） 3.3.這些步驟和記分牌基本上類似，但有以下以下幾點這些步驟和記分牌基本上類似，但有以下以下幾點 不同：不同： (

59、1)(1)無需任何操作來檢查數(shù)據(jù)無需任何操作來檢查數(shù)據(jù)寫后寫寫后寫和和先讀后寫先讀后寫相關(guān)相關(guān) 的過程，在指令流出過程中操作數(shù)寄存器換名已的過程，在指令流出過程中操作數(shù)寄存器換名已 將其消除。將其消除。 70147(2)(2)通過公共數(shù)據(jù)總線來廣播結(jié)果，將結(jié)果送到通過公共數(shù)據(jù)總線來廣播結(jié)果，將結(jié)果送到 等待此結(jié)果作為操作數(shù)的保留站，目標(biāo)寄存器也等待此結(jié)果作為操作數(shù)的保留站，目標(biāo)寄存器也 相當(dāng)于一個需要結(jié)果的保留站，而不是將結(jié)果相當(dāng)于一個需要結(jié)果的保留站，而不是將結(jié)果 寫回到寄存器中。寫回到寄存器中。(3)(3)存儲器存和取都作為基本的功能部件。存儲器存和取都作為基本的功能部件。(4)(4)由于

60、保留站技術(shù)能夠有效地解決先寫后讀，而由于保留站技術(shù)能夠有效地解決先寫后讀，而 無需特殊處理，因此，記分牌流水線中用于完無需特殊處理，因此，記分牌流水線中用于完 成判斷先寫后讀的成判斷先寫后讀的“取操作數(shù)取操作數(shù)”段也被消掉。段也被消掉。 711474. 4. 定義有關(guān)的術(shù)語和數(shù)據(jù)結(jié)構(gòu)定義有關(guān)的術(shù)語和數(shù)據(jù)結(jié)構(gòu) 標(biāo)志（標(biāo)志（tagstags） 指緩沖或產(chǎn)生結(jié)果的保留站（功能部件）。指緩沖或產(chǎn)生結(jié)果的保留站（功能部件）。 每個保留站有以下每個保留站有以下6 6個個域：域： OpOp：對源操作數(shù)對源操作數(shù)S1S1和和S2S2所進(jìn)行的操作。所進(jìn)行的操作。 QjQj，QkQk：產(chǎn)生結(jié)果的保留站號。等于產(chǎn)生