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

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

2、軟件技術(shù)互相配合，才能夠最大必須要硬件技術(shù)和軟件技術(shù)互相配合，才能夠最大限度地挖掘出程序中存在的指令級(jí)并行。限度地挖掘出程序中存在的指令級(jí)并行。41471.1.流水線處理器的實(shí)際流水線處理器的實(shí)際CPICPICPICPI流水線流水線 = CPI= CPI理想理想 + + 各類(lèi)停頓周期數(shù)的總和各類(lèi)停頓周期數(shù)的總和 流水線的理想流水線的理想CPICPI是流水線的最大流量。是流水線的最大流量。 各類(lèi)停頓包括：各類(lèi)停頓包括：結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一個(gè)功能部件而導(dǎo)致的停頓。個(gè)功能部件而導(dǎo)致的停頓。控制相關(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ù)先寫(xiě)后讀相關(guān)停頓數(shù)據(jù)先寫(xiě)后讀相關(guān)停頓4.1循環(huán)展開(kāi)循環(huán)展開(kāi)控制相關(guān)停頓控制相關(guān)停頓4.1寄存器換名寄存器換名數(shù)據(jù)寫(xiě)后寫(xiě)相關(guān)和先讀后寫(xiě)數(shù)據(jù)寫(xiě)后寫(xiě)

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

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

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

7、點(diǎn)數(shù)據(jù)取操作（LD）浮點(diǎn)計(jì)算1浮點(diǎn)數(shù)據(jù)取操作（LD）浮點(diǎn)數(shù)據(jù)存操作（SD）010147例例4.14.1 對(duì)于下面的源代碼，轉(zhuǎn)換成對(duì)于下面的源代碼，轉(zhuǎn)換成DLXDLX匯編語(yǔ)言，匯編語(yǔ)言，在在不進(jìn)行指令調(diào)度不進(jìn)行指令調(diào)度和和進(jìn)行指令調(diào)度進(jìn)行指令調(diào)度兩種情況下，兩種情況下，分析代碼一次循環(huán)的執(zhí)行時(shí)間。分析代碼一次循環(huán)的執(zhí)行時(shí)間。 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)計(jì)數(shù)器，初值為向量：循環(huán)計(jì)數(shù)器，初值為向量

8、 中最高端地址元素的地址。中最高端地址元素的地址。 浮點(diǎn)寄存器浮點(diǎn)寄存器F2F2：保存常數(shù)：保存常數(shù)S S。 假定最低端元素的地址為假定最低端元素的地址為8 8。 (2)(2) DLXDLX匯編語(yǔ)言后的程序匯編語(yǔ)言后的程序 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í)行的實(shí)際時(shí)鐘程序執(zhí)行的實(shí)際時(shí)鐘根據(jù)根據(jù)表表4-24-2中給出的的延遲，實(shí)際時(shí)鐘如下：中給

9、出的的延遲，實(shí)際時(shí)鐘如下： 指令流出時(shí)鐘指令流出時(shí)鐘 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每個(gè)元素的操作需要每個(gè)元素的操作需要1010個(gè)時(shí)鐘周期，其中個(gè)時(shí)鐘周期，其中5 5個(gè)個(gè)是空轉(zhuǎn)周期。是空轉(zhuǎn)周期。13147(4)(4) 指令調(diào)度以后，程序的執(zhí)行情況指令調(diào)度以后，程序的執(zhí)行情況SDSD放在分支指令的分支延遲槽中放在分支指令的分支延遲槽中對(duì)存儲(chǔ)器地址偏移量進(jìn)行調(diào)整對(duì)存儲(chǔ)器地

10、址偏移量進(jìn)行調(diào)整 指令流出時(shí)鐘指令流出時(shí)鐘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一個(gè)元素的操作時(shí)間從一個(gè)元素的操作時(shí)間從1010個(gè)時(shí)鐘周期減少到個(gè)時(shí)鐘周期減少到6 6個(gè)個(gè)5 5個(gè)周期是有指令執(zhí)行的，個(gè)周期是有指令執(zhí)行的，1 1個(gè)空轉(zhuǎn)周期。個(gè)空轉(zhuǎn)周期。14147(5)(5) 例子中的問(wèn)題及解決方案例子中的問(wèn)題及解決方案只有只有LDLD、ADDDADDD和和SDSD這這3 3條指令是有效操作條指令是有效操作. .占用占用3 3個(gè)時(shí)鐘周期

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

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

13、F16F16：用于第用于第4 4個(gè)循環(huán)體個(gè)循環(huán)體17147(1)(1) 展開(kāi)后沒(méi)有調(diào)度的代碼展開(kāi)后沒(méi)有調(diào)度的代碼流出時(shí)鐘流出時(shí)鐘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流出時(shí)鐘流出時(shí)鐘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é)果分析: :這個(gè)循環(huán)每遍共使用了這個(gè)循環(huán)每遍共使用了2828個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期有有4 4個(gè)個(gè)循環(huán)體，完成循環(huán)體，完成4 4個(gè)個(gè)元素的操作元素的操作平均每個(gè)元素使用平均每個(gè)元素使用28/4=728/4=7個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期原始循環(huán)的每個(gè)元素需要原始循環(huán)的每個(gè)元素需要1010個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期節(jié)省的時(shí)間節(jié)省的時(shí)間: :從減少循環(huán)控制的開(kāi)銷(xiāo)中獲得的從減少循環(huán)控制的開(kāi)銷(xiāo)中獲得的在整個(gè)展開(kāi)后的循環(huán)中，實(shí)際指令只有在整個(gè)展開(kāi)

15、后的循環(huán)中，實(shí)際指令只有1414條，條，其它其它1313個(gè)周期都是空轉(zhuǎn)。個(gè)周期都是空轉(zhuǎn)。 效率并不高效率并不高19147(2)(2) 對(duì)指令序列進(jìn)行優(yōu)化調(diào)度對(duì)指令序列進(jìn)行優(yōu)化調(diào)度指令流出時(shí)鐘指令流出時(shí)鐘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é)果分析：沒(méi)有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待沒(méi)有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待整個(gè)循環(huán)僅僅使用了整個(gè)循環(huán)僅僅使用了1414個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期平均每個(gè)元素的操作使用平均每個(gè)元素的操作使用14/4=3.514/4=3.5個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期循環(huán)展開(kāi)循環(huán)展開(kāi)和和指令調(diào)度指令調(diào)度可以有效地提高循環(huán)級(jí)并可以有效地提高循環(huán)級(jí)并行性。行性。這種循環(huán)級(jí)并行性的提高實(shí)際是通過(guò)實(shí)現(xiàn)指令級(jí)這種循環(huán)級(jí)并行性的提高實(shí)際是通過(guò)實(shí)現(xiàn)指令級(jí)并行來(lái)達(dá)到的。并行來(lái)達(dá)到的?？梢允褂镁幾g器來(lái)完成，也可以通過(guò)硬件來(lái)可以使用編譯器來(lái)完成，也可以通過(guò)硬件來(lái)完成。完成。211474. 4. 循環(huán)展開(kāi)和指令調(diào)度時(shí)要注意的問(wèn)題循

17、環(huán)展開(kāi)和指令調(diào)度時(shí)要注意的問(wèn)題(1) (1) 保證正確性保證正確性(2) (2) 注意有效性注意有效性(3) (3) 使用不同的寄存器使用不同的寄存器(4) (4) 盡可能減少循環(huán)控制中的測(cè)試指令和分支指令盡可能減少循環(huán)控制中的測(cè)試指令和分支指令(5) (5) 注意對(duì)存儲(chǔ)器數(shù)據(jù)的相關(guān)性分析注意對(duì)存儲(chǔ)器數(shù)據(jù)的相關(guān)性分析(6) (6) 注意新的相關(guān)性注意新的相關(guān)性5. 5. 實(shí)現(xiàn)循環(huán)展開(kāi)的關(guān)鍵實(shí)現(xiàn)循環(huán)展開(kāi)的關(guān)鍵 分析清楚代碼中指令的相關(guān)性，然后通過(guò)分析清楚代碼中指令的相關(guān)性，然后通過(guò) 指令調(diào)度來(lái)消除相關(guān)指令調(diào)度來(lái)消除相關(guān). .221474.1.2 相關(guān)性開(kāi)發(fā)指令級(jí)并行的開(kāi)發(fā)指令級(jí)并行的關(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）對(duì)于對(duì)于指令指令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)是兩條指令之間存在一個(gè)先寫(xiě)后讀相關(guān)鏈。數(shù)據(jù)相關(guān)是兩條指令之間存在一個(gè)先寫(xiě)后讀相關(guān)鏈。相關(guān)鏈貫穿整個(gè)程序，是程序的內(nèi)在特征。相關(guān)鏈貫穿整個(gè)程序，是程序的內(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ù)的計(jì)算順序。確定必須嚴(yán)格遵守的數(shù)據(jù)的計(jì)算順序。 (3) (3) 確定指令的最大相關(guān)距離，確定程序中可確定指令的最大相關(guān)距離，確定程序中可 能的最大并行性。能的最大并行性。251472. 2. 名相關(guān)（名相關(guān)（name dependencename dependence）指令使用的寄存器或存儲(chǔ)器稱(chēng)為指令使用的寄存器或存儲(chǔ)器稱(chēng)為名名。如果兩條指令使用相同的名，但是它們之間并如果兩條指令使用相同的名，但是它們之間并沒(méi)有數(shù)據(jù)流，則稱(chēng)之為沒(méi)有數(shù)據(jù)流，則稱(chēng)之為名相關(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)的指令之間沒(méi)有數(shù)據(jù)交換。名相關(guān)的指令之間沒(méi)有數(shù)據(jù)交換。如果一條指令中的名改變了，并不影響另外一如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。條指令的執(zhí)行。通過(guò)改變指令中操作數(shù)的名來(lái)消除名相關(guān)，這通過(guò)改變指令中操作數(shù)的名來(lái)消除名相關(guān)，這就是就是換名（換名（renamingrenaming）技術(shù)）

22、技術(shù)。對(duì)于寄存器操作數(shù)進(jìn)行換名稱(chēng)為對(duì)于寄存器操作數(shù)進(jìn)行換名稱(chēng)為寄存器換名寄存器換名。 （register renamingregister renaming）可以用編譯器靜態(tài)完成或硬件動(dòng)態(tài)完成。可以用編譯器靜態(tài)完成或硬件動(dòng)態(tài)完成。27147例：例：我們對(duì)我們對(duì)例例4.24.2編譯過(guò)程進(jìn)行分析，來(lái)仔細(xì)考察編譯過(guò)程進(jìn)行分析，來(lái)仔細(xì)考察 換名的過(guò)程。換名的過(guò)程。 (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ò)對(duì)相關(guān)鏈上存儲(chǔ)器訪問(wèn)偏移編譯器可以通過(guò)對(duì)相關(guān)鏈上存儲(chǔ)器訪問(wèn)偏移 量量的直接調(diào)整，將前的直接調(diào)整，將

24、前3 3條條SUBISUBI指令消除掉，從而得到下指令消除掉，從而得到下面一個(gè)面一個(gè)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ò)寄存器通過(guò)寄存器換名，消除名換名，消除名相關(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換名操作需要較大的寄存器開(kāi)

26、銷(xiāo)。換名操作需要較大的寄存器開(kāi)銷(xiāo)。 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)。 看下面一個(gè)示例：看下面一個(gè)示例： if p1 S1; ; S; if p2 S2; ;33147 處理控制相關(guān)的處理控制相關(guān)的兩個(gè)原則兩個(gè)原則： (1) (1) 與控制相關(guān)的指令不能移到分支指令之與控制相關(guān)的指令不能移到分支指令之 前，即控制有關(guān)的指令不能調(diào)度到分支前，即控制有關(guān)的指令不能調(diào)度到分支 指

27、令控制范圍以外；指令控制范圍以外； (2) (2) 與控制無(wú)關(guān)的指令不能移到分支指令之與控制無(wú)關(guān)的指令不能移到分支指令之 后，即控制無(wú)關(guān)的指令不能調(diào)度到分支后，即控制無(wú)關(guān)的指令不能調(diào)度到分支 指令控制范圍以?xún)?nèi)。指令控制范圍以?xún)?nèi)。34147再考察再考察例例4.24.2： 假設(shè)循環(huán)展開(kāi)時(shí)，循環(huán)控制分支指令沒(méi)有去除，假設(shè)循環(huán)展開(kāi)時(shí)，循環(huán)控制分支指令沒(méi)有去除，則指令序列如下：則指令序列如下： 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指令的動(dòng)態(tài)調(diào)度靜態(tài)調(diào)度靜態(tài)調(diào)度：在出現(xiàn)數(shù)據(jù)相關(guān)時(shí)，為了消除或：在出現(xiàn)數(shù)據(jù)相關(guān)時(shí)，為了消除或 者減少流水線空轉(zhuǎn)，編譯器確定并分離出程者減少流水線空轉(zhuǎn)，編譯器確定并分離出程 序中存在相關(guān)的指令，然后進(jìn)行

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

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

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

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

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

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

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

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

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

38、）的功能部件總數(shù)超）的功能部件總數(shù)超過(guò)可用總線的數(shù)目，這會(huì)導(dǎo)致過(guò)可用總線的數(shù)目，這會(huì)導(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ì)錄各個(gè)功能部件的狀態(tài)。每個(gè)功能部件紀(jì)錄各個(gè)功能部件的狀態(tài)。每個(gè)功能部件 在狀態(tài)表中都由以下在狀態(tài)表中都由以下九個(gè)域九個(gè)域來(lái)紀(jì)錄：來(lái)紀(jì)錄： BusyBusy： 指示功能部件是否在工作指示功能部

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

40、功能部件沒(méi)有需要寫(xiě)入本寄存器的， 則相應(yīng)域置為空。則相應(yīng)域置為空。4. 4. DLXDLX記分牌所要維護(hù)的數(shù)據(jù)結(jié)構(gòu)記分牌所要維護(hù)的數(shù)據(jù)結(jié)構(gòu) 給出下列代碼運(yùn)行過(guò)程中記分牌保存的信息給出下列代碼運(yùn)行過(guò)程中記分牌保存的信息. . 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記分牌信息組成和記錄的信息記分牌信息組成和記錄的信息 部件名稱(chēng) 功能部件狀態(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部件名稱(chēng) 乘法1 整數(shù) 加法 除法51147 例例4

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

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

44、D 指令將要寫(xiě)結(jié)果時(shí)記分牌的狀態(tài)。指令將要寫(xiě)結(jié)果時(shí)記分牌的狀態(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將要寫(xiě)結(jié)果時(shí)記分牌的狀態(tài)將要寫(xiě)結(jié)果時(shí)記分牌的狀態(tài) 部件名稱(chēng) 功能部件狀態(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部件名稱(chēng) 乘法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將要寫(xiě)結(jié)果時(shí)記分牌的狀態(tài)將要寫(xiě)結(jié)果時(shí)記分牌的狀態(tài) 部件名稱(chēng) 功能部件狀態(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部件名稱(chēng) 除法571475.5.分析記分牌是如何控制指令執(zhí)行的。分析記分牌是如何控制指令執(zhí)行的。 操作在記分牌流水線中前進(jìn)時(shí)，記分牌必須操作在記分牌流水線中前進(jìn)時(shí)，記分牌必須 記錄與操作有關(guān)的信息，如寄存器號(hào)等。記錄與操作有關(guān)的信息，如寄存器號(hào)等。 約定：約定： 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)表中對(duì)應(yīng)于寄存結(jié)果寄存器狀態(tài)表中對(duì)應(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)阻塞和寫(xiě)后寫(xiě)判斷結(jié)構(gòu)阻塞和寫(xiě)后寫(xiě) (2) (2) 計(jì)分牌記錄內(nèi)容計(jì)分牌記錄內(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; /解決先寫(xiě)后讀，兩個(gè)源操作數(shù)須同時(shí)就緒解決先寫(xiě)后讀，兩個(gè)源操作數(shù)須同時(shí)就緒 60147 (2) (2)計(jì)分牌記錄內(nèi)容計(jì)分牌記錄內(nèi)容 RjnoRjno；/已經(jīng)讀走了就緒的數(shù)據(jù)已經(jīng)讀走了就緒的數(shù)據(jù)RjRj RknoRkno；/已經(jīng)讀走了就緒的數(shù)據(jù)已經(jīng)讀走了就緒的數(shù)據(jù)RkRk Qj0Qj0；/不再等待其它不再等待其它FUFU的計(jì)算結(jié)果的計(jì)算結(jié)果 Qk0Qk0； 執(zhí)行（執(zhí)

50、行（EXEX） (1)(1)結(jié)束條件結(jié)束條件 功能部件操作結(jié)束功能部件操作結(jié)束61147寫(xiě)結(jié)果（寫(xiě)結(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); / /檢查是否存在先讀后寫(xiě)檢查是否存在先讀后寫(xiě) (2)(2)計(jì)分牌記錄內(nèi)容計(jì)分牌記錄內(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； /沒(méi)有沒(méi)有FUFU使用寄存器使用寄存器FiFi為目的寄存器為目的寄存器 busy(FU)=nobusy(FU)=no/釋放釋放FUFU621476. 6. 記分牌的性能受限于以下幾個(gè)方面：記分牌的性能受限于以下幾個(gè)方面： (1) (1) 程序指令中可開(kāi)發(fā)的并行性，即是否存在程序指令中可開(kāi)發(fā)的并行性，即是否存在 可以并行執(zhí)行的不相關(guān)的指令?？梢圆⑿袌?zhí)行的不相關(guān)的指令。 (2) (2

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

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

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

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

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

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

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

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

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