精確斷點與不精確斷點

1、精確斷點與不精確斷點第1頁，共65頁，2022年，5月20日，8點55分，星期二不精確斷點(Imprecise)，流水線可以不斷流需要的硬件比較少，控制邏輯比較簡單中斷響應(yīng)時間加長 采用不精確斷點法可能會發(fā)生如下兩個問題：(1)程序的調(diào)試?yán)щy調(diào)試程序時要設(shè)置斷點，程序員通過查看斷點處的中間執(zhí)行結(jié)果判斷程序是否正確。但由于不精確斷點，程序不能準(zhǔn)確中斷，因此，難于調(diào)試。早期的流水線處理機(jī)，多采用不精確斷點法近期的流水線處理機(jī)一般都采用精確斷點法第2頁，共65頁，2022年，5月20日，8點55分，星期二(2)程序執(zhí)行的結(jié)果可能出錯，例如： i：FADD R1, R2 ；(R1)(R2)R1 i+1

2、：FMUL R3, R1 ；(R3)(R1)R3當(dāng)?shù)趇條指令執(zhí)行到S6段時發(fā)現(xiàn)浮點加法結(jié)果溢出，于是發(fā)出中斷服務(wù)申請。由于采用不精確斷點法，已經(jīng)進(jìn)入流水線的第i+1條指令將執(zhí)行完成；因為第i+1條指令使用了不正確的R1，所以浮點乘法的執(zhí)行結(jié)果是不正確的。采用精確斷(Precise)點法，要設(shè)置一定數(shù)量的后援寄存器，把整個流水線中所有指令的執(zhí)行結(jié)果和現(xiàn)場都保存下來。第3頁，共65頁，2022年，5月20日，8點55分，星期二5.4 動態(tài)調(diào)度技術(shù)5.4.1 順序流動與亂序流動5.4.2 亂序流動中的數(shù)據(jù)相關(guān)5.4.3 數(shù)據(jù)重定向方法5.4.4 Tomasulo動態(tài)調(diào)度算法第4頁，共65頁，2022

3、年，5月20日，8點55分，星期二實現(xiàn)方法： 由硬件動態(tài)調(diào)整指令執(zhí)行順序，以減少數(shù)據(jù)相關(guān)造成的影響。主要優(yōu)點：能夠處理在編譯時無法確定的相關(guān)，并簡化編譯器設(shè)計在其他流水線機(jī)器上編譯的目標(biāo)代碼也能夠高效運行用靜態(tài)調(diào)度法生成的代碼也能在動態(tài)調(diào)度法的機(jī)器中運行主要缺點：指令級并行度低，因為只能在比較小的范圍內(nèi)尋找并行性第5頁，共65頁，2022年，5月20日，8點55分，星期二5.4.1 順序流動與亂序流動1.順序流動方式：任務(wù)按順序流入流水線,也按順序流出流水線把如下一段程序輸入到這條流水線中： k： R0（R1） k+1： k+2： R2（R0）（R3） k+3： k+4： k+5： 第6頁，共

4、65頁，2022年，5月20日，8點55分，星期二指令k+2無法繼續(xù)執(zhí)行，要在功能段S2中等待。后續(xù)的指令k+4、k+5、等也不能進(jìn)入流水線。功能段S3、S4、S5將逐漸空閑。缺點：吞吐率和效率降低優(yōu)點：流水線的控制邏輯比較簡單第7頁，共65頁，2022年，5月20日，8點55分，星期二流水線“斷流”，有些功能段“空閑”第8頁，共65頁，2022年，5月20日，8點55分，星期二2.亂序(Out of order)流動方式：指令流出流水線的順序與流入流水線的順序不同。又稱為錯序流動方式、無序流動方式、異步流動方式等。第9頁，共65頁，2022年，5月20日，8點55分，星期二5.4.2 亂序流

5、動中的數(shù)據(jù)相關(guān)在亂序流動方式中，可能發(fā)生三種數(shù)據(jù)相關(guān) 寫寫相關(guān) k： LOAD F1, A ;F1（A） 寫讀相關(guān) k+1：FADD F2, F1 ;F2（F2）+（F1） k+2：FMUL F1, F3 ;F1（F1）（F3） k+3：STORE F1, B ;B（F1）讀寫相關(guān)(1)寫讀相關(guān)：指令k與指令k+1之間關(guān)于F1的相關(guān)，又稱為數(shù)據(jù)相關(guān)、先寫后讀相關(guān)、流相關(guān)、WR相關(guān)、RAW相關(guān)等。第10頁，共65頁，2022年，5月20日，8點55分，星期二(2)讀寫相關(guān)：指令k+1與指令k+2之間關(guān)于F1的相關(guān)，變量名相關(guān)、先讀后寫相關(guān)、反相關(guān)、RW相關(guān)、WAR相關(guān)等。(3)寫寫相關(guān)：指令k與

6、指令k+2左邊的F1之間的相關(guān)關(guān)系稱為：輸出相關(guān)、寫寫相關(guān)、WW相關(guān)、WAW相關(guān)或?qū)懞笤賹懴嚓P(guān)等。有時把相關(guān)稱為“冒險”(hazard)、“竟?fàn)帯?(competition)等。在程序執(zhí)行過程中，只有避免相關(guān)，執(zhí)行結(jié)果才是正確的。第11頁，共65頁，2022年，5月20日，8點55分，星期二 三種數(shù)據(jù)相關(guān)可以用下列關(guān)系式來表示： 對于寫讀相關(guān) D(i) S(j) 對于讀寫相關(guān) S(i) D(j) 對于寫寫相關(guān) D(i) D(j) 第12頁，共65頁，2022年，5月20日，8點55分，星期二5.4.3 數(shù)據(jù)重定向方法1.三種數(shù)據(jù)相關(guān)的重定向 重定向之前，j只能在i之后執(zhí)行。 重定向之后，可以做

7、到：(1)寫讀相關(guān)，j與i可以同時執(zhí)行 即專用數(shù)據(jù)通路(2)寫寫相關(guān)，先后順序無關(guān)(3)讀寫相關(guān)，先后順序無關(guān) 后兩種情況又稱為“變量換名技術(shù)”第13頁，共65頁，2022年，5月20日，8點55分，星期二第14頁，共65頁，2022年，5月20日，8點55分，星期二2.變量換名技術(shù)用來自動消除讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)規(guī)則：一個變量只允許定值一次在三種數(shù)據(jù)相關(guān)中，實際上只有寫讀數(shù)據(jù)相關(guān)必須依靠硬件、或采用軟硬件結(jié)合的方法來解決 解決方法：推后處理或?qū)Ｓ脭?shù)據(jù)通路在上面的數(shù)據(jù)重定向圖中，把B換成了B，并在以后的都引用B讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就不存在了。一個實際例子：第15頁，共65頁，202

8、2年，5月20日，8點55分，星期二Loop: LD F0, 0(R1) ADD F0, F2 SD 0(R1), F0 LD F0, -8(R1) ADD F0, F2 SD -8(R1), F0 LD F0, -16(R1) ADD F0, F2 SD -16(R1), F0 LD F0, -24(R1) ADD F0, F2 SD -24(R1), F0 SUBI R1, R1, #32 BNEZ R1, LoopLoop: LD F0, 0(R1) LD F4, -8(R1) LD F6, -16(R1) LD F8, -24(R1) ADD F0，F(xiàn)2 ADD F4，F(xiàn)2 ADD F

9、6，F(xiàn)2 ADD F8，F(xiàn)2 SD 0(R1), F0 SD -8(R1), F4 SUBI R1, R1, #32 SD -16(R1), F6 BNEZ R1, Loop SD -24(R1), F8第16頁，共65頁，2022年，5月20日，8點55分，星期二3.一個簡單的程序： k： LOAD F1, A k+1： FADD F1, F2 k+2： FMUL F1, F3 k+3： STORE F1, B第17頁，共65頁，2022年，5月20日，8點55分，星期二專門設(shè)置：AFADD、FMULB、FADDFMUL三條專用路徑。撤消：F1FADD、F1FMUL、FADDF1 、AF1的

10、路徑。第18頁，共65頁，2022年，5月20日，8點55分，星期二5.4.4 Tomasulo動態(tài)調(diào)度算法P310實用的動態(tài)調(diào)度算法主要有兩種:(1)集中控制：CDC計分牌(scorebord)算法， 最先在CDC 6600大型機(jī)中采用。(2)分散控制：Tomasulo算法, 公共數(shù)據(jù)總線法，令牌法等。最早在大型機(jī)IBM 360/91的浮點處理部件中被采用。以上面的一段程序為例說明Tomasulo算法k： LOAD F1, Ak+1： FADD F1, F2k+2： FMUL F1, F3k+3： STORE F1, B第19頁，共65頁，2022年，5月20日，8點55分，星期二5.5 超

11、標(biāo)量處理機(jī)5.5.1 基本結(jié)構(gòu)5.5.2 單發(fā)射與多發(fā)射5.5.3 多流水線調(diào)度5.5.4 資源沖突5.5.5 超標(biāo)量處理機(jī)性能第20頁，共65頁，2022年，5月20日，8點55分，星期二三種主流處理機(jī)： 超標(biāo)量處理機(jī) 超流水線處理機(jī) 超標(biāo)量超流水線處理機(jī)第21頁，共65頁，2022年，5月20日，8點55分，星期二5.5.1 基本結(jié)構(gòu)普通標(biāo)量流水線處理機(jī)： 一條指令流水線，一個多功能操作部件， 每個時鐘周期平均執(zhí)行指令的條數(shù)小于1。多操作部件標(biāo)量處理機(jī)： 一條指令流水線，多個獨立的操作部件， 指令級并行度小于1。超標(biāo)量處理機(jī)典型結(jié)構(gòu)： 多條并行工作的指令流水線，多個獨立的操作部件， 指令級

12、并行度（ILP）大于1。第22頁，共65頁，2022年，5月20日，8點55分，星期二第23頁，共65頁，2022年，5月20日，8點55分，星期二 Motorola公司的MC88110有10個操作部件兩個寄存器堆：整數(shù)部件通用寄存器堆，32個32位寄存器浮點部件擴(kuò)展寄存器堆，32個80位寄存器緩沖深度為4的先行讀數(shù)棧緩沖深度為3的后行寫數(shù)棧兩個獨立的高速Cache中，各為8KB，采用兩路組相聯(lián)方式轉(zhuǎn)移目標(biāo)指令Cache，用于存放另一條分支上的指令第24頁，共65頁，2022年，5月20日，8點55分，星期二5.5.2 單發(fā)射與多發(fā)射1.單發(fā)射處理機(jī)：每個周期只取一條指令、只譯碼一條指令，只執(zhí)

13、行一條指令，只寫回一個運算結(jié)果。取指令部件和指令譯碼部件各設(shè)置一套；只設(shè)置一個多功能操作部件或設(shè)置多個獨立的操作部件；操作部件中可以采用流水線結(jié)構(gòu)，也可以不采用流水線結(jié)構(gòu)。目標(biāo)是每個時鐘周期平均執(zhí)行一條指令，ILP的期望值為1。第25頁，共65頁，2022年，5月20日，8點55分，星期二2.多發(fā)射處理機(jī)：每個周期同時取多條指令、同時譯碼多條指令，同時執(zhí)行多條指令，同時寫回多個運算結(jié)果。多個取指令部件，多個指令譯碼部件和多個寫結(jié)果部件。設(shè)置多個指令執(zhí)行部件，有些指令執(zhí)行部件采用流水線結(jié)構(gòu)。目標(biāo)是每個時鐘周期平均執(zhí)行多條指令，ILP的期望值大于1。第26頁，共65頁，2022年，5月20日，8點

14、55分，星期二第27頁，共65頁，2022年，5月20日，8點55分，星期二第28頁，共65頁，2022年，5月20日，8點55分，星期二第29頁，共65頁，2022年，5月20日，8點55分，星期二3.超標(biāo)量處理機(jī)：有兩條或兩條以上能同時工作的指令流水線先行指令窗口：能夠從指令Cache中預(yù)取多條指令，能夠?qū)Υ翱趦?nèi)的指令進(jìn)行數(shù)據(jù)相關(guān)性分析和功能部件沖突檢測。例如：Intel公司的i860、i960、Pentium，Motolora公司的MC88110，IBM公司的Power 6000,TI公司生產(chǎn)SuperSPARC等操作部件的個數(shù)一般多于每個周期發(fā)射的指令條數(shù)。通常為4 個至16個操作部件

15、。超標(biāo)量處理機(jī)的指令級并行度：1ILPm第30頁，共65頁，2022年，5月20日，8點55分，星期二第31頁，共65頁，2022年，5月20日，8點55分，星期二5.5.3 多流水線調(diào)度順序發(fā)射(in-order issue)與亂序發(fā)射(out-order issue)：指令發(fā)射順序是按照程序中指令排列順序進(jìn)行的稱為順序發(fā)射順序完成(in-order completion)與亂序完成(out-order completion)：指令完成順序是按照程序中指令排列順序進(jìn)行的稱為順序完成多流水線的調(diào)度主要有三種方法：順序發(fā)射順序完成順序發(fā)射亂序完成亂序發(fā)射亂序完成第32頁，共65頁，2022年，5

16、月20日，8點55分，星期二以如下6條指令組成的程序為例，說明這三種調(diào)度方法 I1：LOAD R1, A ；R1(A) I2：FADD R2, R1 ；R2(R2)(R1) I3：FMUL R3, R4 ；R3(R3)(R4) I4：FADD R4, R5 ；R4(R4)(R5) I5：DEC R6 ；R6(R6)1 I6：FMUL R6, R7 ；R6(R6)(R7)6條指令中有4個數(shù)據(jù)相關(guān)，包括2個寫讀相關(guān)，1個讀寫相關(guān)和1個寫寫相關(guān)。第33頁，共65頁，2022年，5月20日，8點55分，星期二1.順序發(fā)射順序完成 共用10個時鐘周期完成 還有8個空閑的時鐘周期第34頁，共65頁，202

17、2年，5月20日，8點55分，星期二2.順序發(fā)射亂序完成 總的執(zhí)行時間為9個時鐘周期， 節(jié)省了一個時鐘周期。少了5個空閑時鐘周期。第35頁，共65頁，2022年，5月20日，8點55分，星期二3. 亂序發(fā)射亂序完成沒有空閑周期，功能部件得到充分利用。 總的執(zhí)行時間為8個周期，節(jié)省2個周期。第36頁，共65頁，2022年，5月20日，8點55分，星期二5.5.4 資源沖突如果操作部件采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性很?。蝗绻徊捎昧魉€結(jié)構(gòu)，發(fā)生資源沖突的可能性就比較大。下面是一個由4條指令的程序例子： I1：FADD R0, R1 ；R0(R0)(R1) I2：FMUL R2, R3 ；R

18、2(R2)(R3) I3：FADD R4, R5 ；R4(R4)(R5) I4：FMUL R6, R7 ；R6(R6)(R7)第37頁，共65頁，2022年，5月20日，8點55分，星期二操作部件不采用流水線： 做完4條指令總共用了11個周期， 有5個空閑周期。第38頁，共65頁，2022年，5月20日，8點55分，星期二操作部件采用流水線： 做完4條指令共用8個周期， 少用3個周期。第39頁，共65頁，2022年，5月20日，8點55分，星期二操作部件采用流水線結(jié)構(gòu)的原因分析假每個周期發(fā)射m條指令，操作部件的延遲時間為k個周期，如果操作部件不采用流水線結(jié)構(gòu)，則使用同一個操作部件的兩條指令應(yīng)該

19、至少相差mk如果操作部件采用k段流水線結(jié)構(gòu)，則使用同一個操作部件的兩條指令只需相差m或m以上指令流水線的段數(shù)k一般在4至10之間，每個時鐘周期發(fā)射的指令條數(shù)m在2至4之間。取中間值，k7，m3第40頁，共65頁，2022年，5月20日，8點55分，星期二為了不發(fā)生資源沖突，如果操作部件不采用流水線結(jié)構(gòu)， 兩條使用同一個功能部件的指令序號必須相差21或21以上。如果操作部件采用流水線結(jié)構(gòu)， 兩條使用同一個功能部件的指令序號只需要相差3或3以上。因此，在超標(biāo)量處理機(jī)中，操作部件一般要采用流水線結(jié)構(gòu)。 如果由于某種原因，操作部件不能采用流水線結(jié)構(gòu)，則必須設(shè)置多個相同種類的操作部件第41頁，共65頁，

20、2022年，5月20日，8點55分，星期二普通標(biāo)量處理機(jī)，希望相同操作連續(xù)出現(xiàn)。 只有連續(xù)出現(xiàn)相同操作的指令序列時，流水線的效率才能得到充分發(fā)揮。超標(biāo)量處理機(jī)則正好相反，希望相同操作不要連續(xù)出現(xiàn)。相同操作的指令序列連續(xù)出現(xiàn)時，會發(fā)生資源沖突；要求相同操作的指令能夠相對均勻地分布在程序中。超標(biāo)量處理機(jī)的這種要求正好符合一般標(biāo)量程序的特點。第42頁，共65頁，2022年，5月20日，8點55分，星期二5.5.5 超標(biāo)量處理機(jī)性能單流水線普通標(biāo)量處理機(jī)的指令級并行度記作(1, 1)，超標(biāo)量處理機(jī)的指令級并行度記作(m, 1)，超流水線處理機(jī)的指令級并行度記作(1, n)，而超標(biāo)量超流水線處理機(jī)的指令

21、級并行度記作(m, n)。在理想情況下，N條指令在單流水線標(biāo)量處理機(jī)上的執(zhí)行時間為： T(1, 1)(kN1)t第43頁，共65頁，2022年，5月20日，8點55分，星期二在每個周期發(fā)射m條指令的超標(biāo)量處理機(jī)上執(zhí)行的時間為： 超標(biāo)量處理機(jī)相對于單流水線標(biāo)量處理機(jī)的加速比為：超標(biāo)量處理機(jī)的加速比的最大值為：S(m,1)MAXm第44頁，共65頁，2022年，5月20日，8點55分，星期二5.6 超流水線處理機(jī)5.6.1 指令執(zhí)行時序5.6.2 典型處理機(jī)結(jié)構(gòu)5.6.3 超流水線處理機(jī)性能第45頁，共65頁，2022年，5月20日，8點55分，星期二超流水線處理機(jī)的兩種定義：在一個周期內(nèi)分時發(fā)射

22、多條指令的處理機(jī)指令流水線的段數(shù)大于等于8的流水線處理機(jī)提高處理機(jī)性能的兩種方法：通過增加硬件資源來提高處理機(jī)性能通過各部分硬件的重疊工作來提高處理機(jī)性能兩種不同并行性：超標(biāo)量處理機(jī)采用的是空間并行性。超流水線處理機(jī)采用的是時間并行性。第46頁，共65頁，2022年，5月20日，8點55分，星期二5.6.1 指令執(zhí)行時序每隔1/n個時鐘周期發(fā)射一條指令， 即處理機(jī)的流水線周期為1/n個時鐘周期。第47頁，共65頁，2022年，5月20日，8點55分，星期二5.6.2 典型處理機(jī)結(jié)構(gòu)MIPS R4000處理機(jī)： 每個時鐘周期包含兩個流水段是一種很標(biāo)準(zhǔn)的超流水線處理機(jī)結(jié)構(gòu)。指令流水線有8個流水段。

23、指令Cache和數(shù)據(jù)Cache的容量各8KB，每個時鐘周期可以訪問Cache兩次，在一個時鐘周期內(nèi)可以從指令Cache中讀出兩條指令，從數(shù)據(jù)Cache中讀出或?qū)懭雰蓚€數(shù)據(jù)。主要運算部件有整數(shù)部件和浮點部件。第48頁，共65頁，2022年，5月20日，8點55分，星期二第49頁，共65頁，2022年，5月20日，8點55分，星期二第50頁，共65頁，2022年，5月20日，8點55分，星期二如果在LOAD指令之后的兩條指令中，任何一條指令要在它的EX流水級使用這個數(shù)據(jù)，則指令流水線要暫停一個時鐘周期。第51頁，共65頁，2022年，5月20日，8點55分，星期二5.6.3 超流水線處理機(jī)性能指令

24、級并行度為(1,n)的超流水線處理機(jī)，執(zhí)行N條指令所的時間為：超流水線處理機(jī)相對于單流水線普通標(biāo)量處理機(jī)的加速比為： 加速比的最大值為：S(1, n)MAXn第52頁，共65頁，2022年，5月20日，8點55分，星期二5.7 超標(biāo)量超流水線處理機(jī)一個時鐘周期發(fā)射m次，每次發(fā)射n條指令 5.7.1 指令執(zhí)行時序5.7.2 典型處理機(jī)結(jié)構(gòu)5.7.3 超標(biāo)量超流水線處理機(jī)性能5.7.4 三種處理機(jī)的性能比較第53頁，共65頁，2022年，5月20日，8點55分，星期二5.7.1 指令執(zhí)行時序第54頁，共65頁，2022年，5月20日，8點55分，星期二5.7.2 典型處理機(jī)結(jié)構(gòu)DEC公司的Alph

25、a處理機(jī)為典型的超標(biāo)量超流水線結(jié)構(gòu)。主要由四個功能部件和兩個Cache組成：整數(shù)部件EBOX 浮點部件FBOX 地址部件ABOX 中央控制部件IBOX 指令Cache和數(shù)據(jù)Cache在EBOX內(nèi)還有多條專用數(shù)據(jù)通路，可以把運算結(jié)果直接送到執(zhí)行部件。第55頁，共65頁，2022年，5月20日，8點55分，星期二中央控制部件IBOX能夠同時完成： 同時讀出兩條指令； 同時對兩條指令進(jìn)行譯碼，并作相關(guān)性檢測； 如果資源和相關(guān)性允許，IBOX就把兩條指令同時發(fā)射給EBOX、ABOX和FBOX三個執(zhí)行部件中的兩個。指令流水線的控制方式： 采用順序發(fā)射亂序完成。在指令Cache中有一個轉(zhuǎn)移歷史表，實現(xiàn)條件

26、轉(zhuǎn)移的動態(tài)預(yù)測。第56頁，共65頁，2022年，5月20日，8點55分，星期二Alpha 21064處理機(jī)共有三條指令流水線：(1)整數(shù)操作流水線為7個流水段，其中，取指令2個流水段、分析指令2個流水段、運算2個流水段、寫結(jié)果1個流水段。(2)訪問存儲器流水線為7個流水段。(3)浮點操作流水線分為10個流水段，其中，浮點執(zhí)行部件FBOX的延遲時間為6個流水段。 三條指令流水線的平均段數(shù)為(7+7+10)/3=8，且每個時鐘周期發(fā)射兩條指令。因此，Alpha 21064處理機(jī)為超標(biāo)量超流水線處理機(jī)。第57頁，共65頁，2022年，5月20日，8點55分，星期二第58頁，共65頁，2022年，5月

27、20日，8點55分，星期二5.7.3 超標(biāo)量超流水線處理機(jī)的性能指令級并行度為(m,n)的超標(biāo)量超流水線處理機(jī)，連續(xù)執(zhí)行N條指令所需要的時間為：超標(biāo)量超流水線處理機(jī)相對于單流水線標(biāo)量處理機(jī)的加速比為：在理想情況下，超標(biāo)量超流水線處理機(jī)加速比的最大值為： S(m,n)MAXm n第59頁，共65頁，2022年，5月20日，8點55分，星期二5.7.4 三種標(biāo)量處理機(jī)的性能比較第60頁，共65頁，2022年，5月20日，8點55分，星期二 從三種標(biāo)量處理機(jī)的性能曲線中，可以得出如下結(jié)論：1.三種處理機(jī)的性能關(guān)系超標(biāo)量處理機(jī)的相對性能最高，其次是超標(biāo)量超流水線處理機(jī)，超流水線處理機(jī)的相對性能最低，主要原因如下：(1)超標(biāo)量處理機(jī)功能部件的沖突比超流水線處理機(jī)小。在指令執(zhí)