上海交通大學(xué) 計算機(jī)組成原理考研輔導(dǎo)講稿

1、第八章流水技術(shù)第一節(jié)流水線工作原理流水工作方式：將一個計算任務(wù)細(xì)分成若干個子任務(wù)，每個子任務(wù)由專門的部件處理， 多個計算任務(wù)依次進(jìn)行并行處理。處理鎖處理鎖處理鎖部件存9部件存* 1部件存一1器2器器CLK一、流水線的分類操作部件級，指令級，處理器級單功能，多功能靜態(tài)，動態(tài)線性，非線性標(biāo)量，向量二、流水線的性能吞吐率：單位時間內(nèi)流水線能處理的任務(wù)數(shù)量。對于線性流水線：t=maxt1，f,tm + tz時空圖：圖8 1流水線的時空圖例子最大吞吐率：流水線達(dá)到不間斷流水的穩(wěn)定狀態(tài)后可獲得的吞吐率。Tp max1_ 1maxr,., t,., t +1, t1 i m l流水線瓶頸的解決:t&(b)瓶

2、頸段細(xì)分(c)瓶頸段重復(fù)設(shè)置部8 2消除流水線瓶頸段的兩種方法(a)原流水線時空圖對于線性流水線，完成n個任務(wù)所需時間為T=mAt+(n-1)At,實際吞吐率為: n1T p maxT =p mZ + (n -1) AtAt (1+ m-1)1+ m -1nn加速比：流水方式的工作速度與等效的順序工作方式時間的比值。 對于線性流水線:S _ T _ nm _ mp Tk m + n 1 1 + m -1 n3.使用效率:工作時間的時空區(qū)與流水線中各段總的時空區(qū)之比。E nmAtn Sp 了 心m( m + n 1) At m + n 1 m p退耦流水線三、流水線的相關(guān)處理三種相關(guān)性：1.資源

3、相關(guān)(結(jié)構(gòu)相關(guān))解決方法：增加資源數(shù)據(jù)相關(guān)（RAW、WAR、WAW）解決方法：停頓、編譯檢測、旁路相關(guān)專用通路控制相關(guān)。解決方法：提前判斷、轉(zhuǎn)移延遲槽等四、流水線的調(diào)度非線性流水線的調(diào)度方法預(yù)約表禁止表沖突向量C = 10110001調(diào)度狀態(tài)轉(zhuǎn)換圖圖8- 3非線性流水線狀態(tài)圖調(diào)度方案比較表8-2各種調(diào)度方案的平均間隔拍數(shù)調(diào)度策略平均間隔周期bc: (3,4)3.50ad: (2,7)4.50ade: (2,2,7)3.67abcb: (3,4,2,7)4.25abc: (3,4,7)4.67acb: (4,3,7)4.67ab: (3,7)5.00ac: (4,7)5.50a700習(xí)題：5，6

4、第二節(jié)標(biāo)量流水技術(shù)一、基本概念指令流水線結(jié)構(gòu):PC指令存儲數(shù)據(jù)寄存數(shù)據(jù)Do存儲器指令級并行性：指令序列中的并行性?；緣K循環(huán)級并行性：循環(huán)遞歸之間的并行性。例：for (i=1; i=1000; i=i+1) xi = xi + s;循環(huán)展開后loop: LDF0, 0(R1);F0=array elementADDDF4,F0,F2;add scalar in F2SD0(R1),F4;store resultSUBIR1,R1,8;decrement pointer 8 bytes (per DW)BNEZR1,loop;branch if R1!=zero執(zhí)行時的情況：loop: LDF

5、0, 0(R1)1stall2ADDDF4,F0,F23stall4stall5SD0(R1),F46SUBIR1,R1,87BNEZR1,loop8stall9指令調(diào)度后：loop: LDF0, 0(R1)stallADDDF4,F0,F2SUBIR1,R1,8BNEZR1,loopSD8(R1),F4執(zhí)行時間減少到6個時鐘周期。將上述程序展開3次之后loop: LD F0, 0(R1)2ADDDF4,F0,F23SD0(R1),F41LDF6,-8,0(R1)2ADDDF8,F6,F23SD-8(R1),F81LDF10,-16(R1)2ADDDF12,F10,F23SD-16(R1),F

6、121LDF14,-24(R1)2ADDDF16,F14,F23SD-24(R1),F161SUBI R1,R1,#321BNEZ R1,loop2未調(diào)度時，執(zhí)行時間為27個周期，平均每個迭代6.8個周期。loop: LD F0, 0(R1)LD F6,-8,0(R1)LD F10,-16(R1)LD F14,-24(R1)ADDD F4,F0,F2ADDD F8,F6,F2ADDD F12,F10,F2ADDD F16,F14,F2SD 0(R1),F4SD -8(R1),F8SD -16(R1),F12SUBI R1,R1,#32BNEZ R1,loopSD 8(R1),F16調(diào)度后，執(zhí)行

7、時間為14個周期，平均每個迭代3.5個周期。指令流水處理中的相關(guān)性：數(shù)據(jù)相關(guān)。如果滿足以下兩個條件，則稱指令j與指令，是數(shù)據(jù)相關(guān)的：指令i產(chǎn)生的結(jié)果被指令j使用；指令j與指令k數(shù)據(jù)相關(guān)，而指令k與指令i數(shù)據(jù)相關(guān)。上述程序簡單展開的結(jié)果是：loop: LD F0, 0(R1)ADDD F4,F0,F2SD 0(R1),F4SUBI R1,R1,#8LD F6,0(R1)ADDD F8,F6,F2SD 0(R1),F8SUBI R1,R1,#8LD F10,0(R1)ADDD F12,F10,F2SD 0(R1),F12SUBI R1,R1,#8LD F14,0(R1)ADDD F16,F14,F

8、2SD 0(R1),F16SUBI R1,R1,#8BNEZ R1,loop這里，相關(guān)性都來自減法指令。它使得指令只能順序執(zhí)行，而且指令數(shù)量多。名字相關(guān)。名字相關(guān)發(fā)生在當(dāng)兩條指令使用相同的寄存器或存儲單元(稱為名字) 時。但是在指令之間不存在涉及該名字的數(shù)據(jù)流。在指令i及其后的指令j之間存在兩種名 字相關(guān)性。反相關(guān)。當(dāng)指令j寫一個寄存器，而指令i讀這個寄存器時發(fā)生反相關(guān)。反相關(guān)對 應(yīng)于WAR險象，這種險象的檢測使得反相關(guān)指令對保持其原有的順序。輸出相關(guān)。輸出相關(guān)發(fā)生于指令i和指令j寫相同寄存器或存儲器單元時。指令的 順序必須保持。輸出相關(guān)對應(yīng)于WAW險象，可通過檢測手段發(fā)現(xiàn)。解決名字相關(guān)的方法

9、：寄存器更名(Register rename)。例如對于上述循環(huán)的例子，如果不進(jìn)行寄存器重新命名，其名字相關(guān)的情況如下所示：loop: LD F0, 0(R1)ADDD F4,F0,F2SD 0(R1),F4LD F0,-8(R1)ADDD F4,F0,F2SD -8(R1),F4LD F0,-16(R1)ADDD F4,F0,F2SD -16(R1),F4LD F0,-24(R1)ADDD F4,F0,F2SD -24(R1),F4SUBI R1,R1,#32BNEZ R1,loop這些名字相關(guān)迫使指令序列只能按序執(zhí)行。在經(jīng)過了寄存器重新命名之后，名字相關(guān)就被消除，而只剩下數(shù)據(jù)相關(guān)。loop

10、: LD F0, 0(R1)ADDD F4,F0,F2SD 0(R1),F4LD F6,-8(R1)ADDD F8,F6,F2SD -8(R1),F8LD F10,-16(R1)ADDD F12,F10,F2SD -16(R1),F12LD F14,-24(R1)ADDD F16,F14,F2SD -24(R1),F16SUBI R1,R1,#32BNEZ R1,loop控制相關(guān)?？刂葡嚓P(guān)決定了轉(zhuǎn)移指令與其它指令之間的執(zhí)行順序。程序中除了開 始的第一個基本塊之外，其它每條指令都對某些分支指令有控制相關(guān)性，通常必須保持這 種控制相關(guān)性。控制相關(guān)導(dǎo)致兩個基本約束：一條與一個分支相關(guān)的指令不能移動到

11、這個分支指令之前而使這條指令不受該分 支的控制。一條與一個分支不相關(guān)的指令不能移動到這個分支之后而使這條指令受到該分支 指令的控制。上例中循環(huán)展開時取消了一些控制指令，因而消除了一些控制相關(guān)。兩種保持控制相關(guān)性的方法：(1)按序執(zhí)行；(2)檢測控制或分支險象，保證與分支指 令控制相關(guān)的指令在分支的方向明確之后才執(zhí)行，而與分支指令不相關(guān)的指令則可以提前 或者延遲執(zhí)行?？刂葡嚓P(guān)本身不是必須保持不變的本質(zhì)因素。必須保持不變的是程序的兩個特性：異常行為和數(shù)據(jù)流。例如：BEQZ R2,L1LW R1,0(R2)L1:這里只存在控制相關(guān)，不存在數(shù)據(jù)相關(guān)。習(xí)題：7二、指令的動態(tài)調(diào)度靜態(tài)調(diào)度：用編譯調(diào)度動態(tài)調(diào)

12、度：用硬件調(diào)度基本思想：無序執(zhí)彳丁打破指令執(zhí)彳丁的順序限制。有序指令啟動：DIVD F0,F2,F4ADDD F10,F0,F8SUBD F12,F8,F14第三條指令不能提前啟動。無序指令啟動的方法：記分牌方法，Tomasulo法1.記分牌方法記分牌的構(gòu)成：指令狀態(tài)表。功能部件狀態(tài)表。寄存器結(jié)果狀態(tài)表。四個執(zhí)行階段：啟動、讀操作數(shù)、執(zhí)行、寫結(jié)果啟動規(guī)則：無結(jié)構(gòu)沖突，沒有WAW相關(guān)讀操作數(shù)規(guī)則：操作數(shù)具備一一消除RAW相關(guān)寫結(jié)果規(guī)則：前面指令已讀取操作數(shù)或者無數(shù)據(jù)相關(guān)一一消除WAR相關(guān)例如：一個具有五個功能部件的CPU,包括一個整數(shù)部件(Integer)、兩個乘法部件(Multi,Mult2)

13、、一個加法部件(Add)和一個除法部件(Divide)。假定以下指令序列：LD F6,34(R2)LD F2,45(R3)MULTD F0,F2,F4SUBD F8,F6,F2DIVD F10,F0,F6ADDD F6,F8,F2這里L(fēng)D指令由整數(shù)部件執(zhí)行(無流水功能)，加法和減法都由加法部件執(zhí)行，乘法和 除法運算操作由相應(yīng)的部件執(zhí)行。指令狀態(tài)表WF2F4F6F8F10F12F30指令指令狀態(tài)啟動讀操作數(shù)執(zhí)行完成寫結(jié)果LD F6,34(R2)1234LD F2,45(R3)567MULTD F0,F2,F46SUBD F8,F6,F27DIVD F10,F0,F68ADDD F6F8F2MMi

14、ltl IntegerSub Divide假定加法部件的執(zhí)行需要2個時鐘周期，乘法需要10個周期，除法需要40個周期。在MULTD和DIVD寫結(jié)果時的記分牌情況如下所示。指令狀態(tài)表指令指令狀態(tài)啟動讀操作數(shù)執(zhí)行完成寫結(jié)果LD F6,34(R2)1匕人】/卜廠廠定入234LD F2,45(R3)5678MULTD F0,F2,F4691920SUBD F8,F6,F2791112DIVD F10,F0,F68216061ADDD F6F8F2UU1622功能部件狀態(tài)表功能部件狀態(tài)部件名BusyOpFiFjFkQjQkRjRkIntegerNoMult1YesMultF0F2F4NoNoMult2N

15、oAddYesAddF6F8F2NoNoDivide1YesDivF10F0F6Multi寄存器狀態(tài)表No-FQF2F4F6F8F10F12:F30MultiAddDivide習(xí)題：122. Tomasul o調(diào)度法特點：寄存器更名一一消除名字相關(guān)分布式保存站一一并行調(diào)度消除調(diào)度瓶頸寫回控制一一寫寫相關(guān)時最后一條指令寫入命令隊列一一使取指令與啟動執(zhí)行退耦例如：指令序列及其執(zhí)行狀態(tài)如下（假定執(zhí)行周期數(shù)與上述相同）：指令狀態(tài)表指令指令狀態(tài)啟動執(zhí)行完成寫結(jié)果LD F6,34(R2)134LD F2,45(R3)245MULTD F0,F2,F431516SUBD F8,F6,F2478DIVD F1

16、0,F0,F655657ADDD F6 F8 F261011各保存站情況如下:各浮點寄存器狀態(tài)如下表:0F2F4E6E8E10E12-E30Mult1Load2Add2Add1 ,Mult2保存站部件名BusyOdViVkQiQkAdd1YesSUBMem34+RegsR21Load2Add2YesADDAdd1Load2Add3NoMult1YesMULTRegsF4Load2Mult2YesDIVMem34+RegsR2Mult1存儲器總線一裝入緩存一J0010LD F3,34(R2)0001LD F6,K4(R3)指令處理部件忙站號數(shù)據(jù)1100 )0T0 0001浮點寄存器OPrQi V

17、i，Qj Vjb忙圖8 5 Tomasulo指令調(diào)度法結(jié)構(gòu)框圖三、分支預(yù)測靜態(tài)：永遠(yuǎn)不轉(zhuǎn)移，永遠(yuǎn)轉(zhuǎn)移，后向轉(zhuǎn)移（準(zhǔn)確率40%65%） （i486） 動態(tài)：1位，2位，多位（1級，2級）建立一個記錄轉(zhuǎn)移狀態(tài)的cache1位動態(tài)：根據(jù)上次轉(zhuǎn)移情況預(yù)測下次，準(zhǔn)確率77%79%（Alpha）0*=L2位動態(tài)：根據(jù)上兩次轉(zhuǎn)移情況預(yù)測下次，準(zhǔn)確率78%89% （奔騰）012級預(yù)測：根據(jù)多次轉(zhuǎn)移情況選擇預(yù)測狀態(tài)，準(zhǔn)確率93%（P6）移位方向轉(zhuǎn)移歷史寄存器1 011 最近轉(zhuǎn)移位圖8 7兩級轉(zhuǎn)移預(yù)測方法 分支目標(biāo)緩存：快速形成分支目標(biāo)地址或者目標(biāo)指令。取預(yù)測的PC作為新PC值圖8-8分支目標(biāo)緩存圖中：目標(biāo)緩存一

18、一分支目標(biāo)地址預(yù)測PC分支指令地址標(biāo)記預(yù)測狀態(tài)位一一預(yù)測狀態(tài)的編碼四、多重指令啟動目標(biāo)：在一個時鐘周期內(nèi)能夠啟動多條指令。方法：動態(tài)多重指令啟動（超標(biāo)量，超流水），靜態(tài)多重指令啟動（VLIW）。退耦結(jié)構(gòu)：將數(shù)據(jù)裝載操作和數(shù)據(jù)運算并行進(jìn)行，并采用load/store緩存，使得訪存操 作與運算操作之間存在一個彈性關(guān)系。表8-4 （假設(shè)可同時啟動一條浮點指令和一條整型指令）迭代編號指令啟動周期執(zhí)行周期寫回周期1LDF00/R1)1241ADDDF4F0F21581SDL ,LU, L t0(P1)F429Q HP T3A1BNEZR1,R1,#8R1TOOP452t nFC) n f p 1 82A

19、DDDF4,F0,F259122SD0(R1)F46132SUBIu (、*，,R1R1#87892BNEZR1,LOOP89時空圖表示:超長指令字：指令中包含多個部件的操作訪存部件1訪存部件2浮點部件1浮點部件2整型/轉(zhuǎn)移LDF0,0(R1)LDF6,-8(R1)LDF10,-16(R1) LDF14,-24(R1)LDF18,-32(R1) LDF22,-40(R1)ADDD F4,F0,F2ADDD F8,F6,F2LDF26,-48(R1)ADDD F12,F10,F2ADDD F16,F14,F2ADDD F20,F18,F2ADDD F24,F22,F2SD0(R1),F4SD-8

20、(R1),F8ADDD F2 8,F2 6,F2SD-16(R1),F12 SD-24(R1),F16SD-32(R1),F20 SD-40(R1),F24SUBI R1,R1,#56SD_+ 8(R1) .F28BNEZ R1 .LOOP執(zhí)行時間為9個周期，平均每個迭代1.28個周期。習(xí)題：15五、指令級并行性的進(jìn)一步開發(fā)相關(guān)性的檢測與消除采用編譯技術(shù)消除相關(guān)性(見書上例子)軟件流水重新組織循環(huán)程序例：對于前面的循環(huán)例子LD F0,0(R1)ADDD F4,F0,F2LD F0,0(R1)SD 0(R1),F4ADDD F4,F0,F2LD F0,0(R1)SD 0(R1),F4ADDD F

21、4,F0,F2SD 0(R1),F4路徑調(diào)度技術(shù)將指令調(diào)度的范圍擴(kuò)展到跨越轉(zhuǎn)移指令的更大的區(qū)域，開發(fā)非循環(huán)分支程序中的并行 性，用于VLIW。兩種步驟：路徑選擇，路徑壓縮條件指令給指令增加一個條件，以消除轉(zhuǎn)移指令，或使得指令能夠跨越轉(zhuǎn)移指令進(jìn)行調(diào)度。例：語句if(A=0) S=T;在一般的計算機(jī)中轉(zhuǎn)換成BNEZ R1,LMOV R2,R3L:可以用一條條件傳輸指令，在第三個操作數(shù)為零時進(jìn)行數(shù)據(jù)傳輸操作：CMOVZ R2,R3,R1又如，對于下列雙啟動的超標(biāo)量機(jī)指令序列：LW R1,40(R2) ADD R3,R4,R5ADD R6,R3,R7BEQZ R10,LLW R8,20(R10)LW

22、R9,0(R8)L:程序浪費一個存儲器操作節(jié)拍，轉(zhuǎn)移不發(fā)生時將發(fā)生一個數(shù)據(jù)相關(guān)停頓，因為轉(zhuǎn)移指 令后的第二條LW指令與上一條指令是相關(guān)的。用條件訪存指令LWC,程序改為：LW R1,40（R2） ADD R3,R4,R5LWC R8,20（R10）,R10ADDR6,R3,R7BEQZ R10,LLW R9,0（R8）5.推測執(zhí)行將指令的執(zhí)行與指令結(jié)果的寫回退耦，允許指令預(yù)執(zhí)行。指令的提交：結(jié)果寫回提交方式：有序提交（可實現(xiàn)精確中斷），無序提交（需進(jìn)行相關(guān)性檢測） 重排序緩存：保存指令執(zhí)行完成后但尚未提交的結(jié)果。| IF | 川* IS | Ex | 寫緩* 提交習(xí)題：9，10第三節(jié)向量流水技

23、術(shù)一、向量指令和數(shù)據(jù)的編碼表示向量指令：以向量數(shù)據(jù)為操作數(shù)的指令。向量操作數(shù)：包含n個數(shù)據(jù)元素的有序集合，n稱為向量的長度。在FORTRAN擴(kuò)展語言中，向量元素子集的表示：初始下標(biāo):終止下標(biāo):下標(biāo)增量 e1:e2:e3 e1:e2*e1:*:e3向量數(shù)據(jù)的壓縮和展開LJE（b）有序向量（c）壓縮向量圖8-12稀疏向量、有序向量和壓縮向量自定義類型的數(shù)據(jù) 標(biāo)志符數(shù)據(jù)圖8-13帶標(biāo)志符數(shù)據(jù)表示格式優(yōu)點：（1）簡化指令系統(tǒng)，（2）數(shù)據(jù)類型檢查和轉(zhuǎn)換能夠用硬件實現(xiàn)。（3）硬件能自動 轉(zhuǎn)換數(shù)據(jù)轉(zhuǎn)換。（4）方便了程序調(diào)試。主要問題：（1）使數(shù)據(jù)區(qū)域占用的存儲空間增加。（2）指令執(zhí)行速度將減慢。（3）數(shù)據(jù) 的初始化復(fù)雜。數(shù)據(jù)描述符：用于描述復(fù)合數(shù)據(jù)類型。格式：描述符標(biāo)志位特征標(biāo)記數(shù)據(jù)塊長度數(shù)據(jù)塊起始地址圖8-14數(shù)據(jù)描述符格式例子:二、向量流水原理典型的向量機(jī)基本系統(tǒng)結(jié)構(gòu)主存;標(biāo)量寄存器，向量地址H向量流部件寄存器指令處理部件，向量指令1控制部件圖8-15向量處理機(jī)的典型結(jié)構(gòu)圖六種向量指令向量-向量指令。例：ADDV V1, V2, V3向量-標(biāo)量指令。例：ADDV V1, F2, V3 向量-存儲器指令。例：LV V1, R1向量歸約指令。例：MAX F0, V1收集-擴(kuò)展指令。Gather-Scatter屏蔽指令。例：SENSV F0, V1標(biāo)量4裝入0裝入