廣工計算機(jī)系統(tǒng)結(jié)構(gòu)課件第五章

1計算機(jī)系統(tǒng)結(jié)構(gòu)第一章基本概念第二章指令系統(tǒng)第三章存儲系統(tǒng)第四章輸入輸出系統(tǒng)**第五章標(biāo)量處理機(jī)第六章向量處理機(jī)**第七章互連網(wǎng)絡(luò)第八章并行處理機(jī)第九章多處理機(jī)2并行兩種并行性概念同時性并行Simultaneity:兩個或兩個以上事件在同一時刻發(fā)生并發(fā)性并行Concurrency:兩個或兩個以上事件在同一時間間隔內(nèi)發(fā)生三條技術(shù)途徑資源重復(fù)(空間并行性,同時性并行):重復(fù)設(shè)置多個處理部件來提高速度時間重疊(時間并行性,并發(fā)性并行):流水線資源共享:分時系統(tǒng)，分布式系統(tǒng)時間---空間關(guān)系資源重復(fù)(空間并行性,同時性并行):增加空間以多個空間容納多條指令時間重疊(時間并行性,并發(fā)性并行):細(xì)分空間以多個子空間容納多條指令3第五章標(biāo)量處理機(jī)標(biāo)量處理機(jī)只有標(biāo)量數(shù)據(jù)表示和標(biāo)量指令系統(tǒng)的處理機(jī)提高指令執(zhí)行速度的主要途徑提高處理機(jī)的工作主頻采用更好的算法和設(shè)計更好的功能部件采用指令級并行技術(shù)三種指令級并行處理機(jī)流水線處理機(jī)和超流水線(Super-pipelining)處理機(jī)超標(biāo)量(Superscalar)處理機(jī)超長指令字(VLIW:VeryLongInstructionWord)處理機(jī)同時性并行?并發(fā)性并行?四種基本技術(shù)先行控制技術(shù)流水線技術(shù)相關(guān)性分析技術(shù)動態(tài)調(diào)度技術(shù)4本章主要內(nèi)容5.1先行控制技術(shù)5.2流水線技術(shù)5.1.4,5.2.6相關(guān)性分析技術(shù)5.1.3,5.2.5動態(tài)調(diào)度技術(shù)5.3.1超標(biāo)量處理機(jī)5.3.2超流水線處理機(jī)5.3.3超標(biāo)量超流水線處理機(jī)55.1先行控制技術(shù)先行控制(Lookahead)技術(shù)最早在IBM公司的STRETCH機(jī)器中采用先行控制技術(shù)的關(guān)鍵緩沖技術(shù)預(yù)處理技術(shù)(目前，許多處理機(jī)中都已經(jīng)采用了先行控制技術(shù))65.1先行控制技術(shù)5.1.1指令的重疊執(zhí)行方式1順序執(zhí)行方式執(zhí)行n條指令所用的時間如每段時間都為t，則執(zhí)行n條指令所用的時間T=3nt主要優(yōu)點：控制簡單，節(jié)省設(shè)備主要缺點：執(zhí)行指令的速度慢，功能部件的利用率低取指令k分析k執(zhí)行k取指令k+1分析k+1執(zhí)行k+172一次重疊執(zhí)行方式如果兩個過程的時間相等，則執(zhí)行n條指令的時間T=(1+2n)t總時間-重疊部分一種最簡單的流水線方式主要優(yōu)點指令的執(zhí)行時間縮短功能部件的利用率明顯提高主要缺點需要增加一些硬件控制過程稍復(fù)雜取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1取指k+2分析k+2執(zhí)行k+283二次重疊執(zhí)行方式如果三過程的時間相等，執(zhí)行n條指令的時間：T=(2+n)t理想情況下同時有三條指令在執(zhí)行處理機(jī)的結(jié)構(gòu)要作比較大的改變，必須采用先行控制方式取指k+2分析k+2執(zhí)行k+2取指k+1分析k+1執(zhí)行k+1取指k分析k執(zhí)行k91采用二次重疊執(zhí)行方式，必須解決兩個問題(1)有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件一個集中的指令控制器要分解成三個相對獨(dú)立的控制器存儲控制器、指令控制器、運(yùn)算控制器(2)解決訪問主存儲器的沖突問題取指令、分析指令、執(zhí)行指令都可能要訪問存儲器5.1.2先行控制方式的原理和結(jié)構(gòu)10(1)兩個獨(dú)立的存儲器：獨(dú)立的指令存儲器和數(shù)據(jù)存儲器如果再規(guī)定，執(zhí)行指令所需的操作數(shù)和執(zhí)行結(jié)果只寫到通用寄存器，那么，取指令、分析指令和執(zhí)行指令就可同時進(jìn)行許多高性能處理機(jī)中，有獨(dú)立的指令Cache和數(shù)據(jù)Cache。這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)(2)采用低位交叉存取方式不能根本解決沖突問題取指令、讀操作數(shù)、寫結(jié)果(3)采用先行控制技術(shù)關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖棧，用以平滑它們的工作預(yù)處理技術(shù)把進(jìn)入運(yùn)算器的指令都處理成RR型指令拆分長的，復(fù)雜的數(shù)據(jù)通路運(yùn)算器能夠?qū)Ｐ挠跀?shù)據(jù)的運(yùn)算，從而大幅度提高程序的執(zhí)行速度2解決訪存沖突的方法115.1.2.1處理機(jī)結(jié)構(gòu)處理機(jī)內(nèi)部設(shè)置一定容量的指令緩沖棧指令分析器所需的指令事先取到指令緩沖棧，不必訪問主存儲器取指令、分析指令和執(zhí)行指令重疊執(zhí)行三個獨(dú)立的控制器存儲控制器、指令控制器、運(yùn)算控制器四個緩沖棧先行指令緩沖棧、先行操作棧、先行讀數(shù)緩沖棧、后行寫數(shù)棧12先行指令緩沖棧的組成只要指令緩沖棧沒有充滿，就自動發(fā)出取指令的請求設(shè)置兩個程序計數(shù)器現(xiàn)行程序計數(shù)器PC，記錄指令分析器正在分析的指令地址先行程序計數(shù)器PC1，用來指示取指令13先行控制方式中的一次重疊執(zhí)行指令分析器每次取指令能在先行指令緩沖棧中得到，則取指令只需很短的時間就能完成可把取指令與分析指令合并到一起構(gòu)成一次重疊執(zhí)行方式存在的主要問題(1)各類指令“分析”和“執(zhí)行”所需要的時間相差很大(2)數(shù)據(jù)相關(guān)和變址相關(guān)(3)轉(zhuǎn)移或轉(zhuǎn)子程序指令本節(jié)及以后兩節(jié)逐個解決分析k執(zhí)行k分析k+1執(zhí)行k+1分析k+2執(zhí)行k+2145.1.2.2先行控制方式的指令執(zhí)行時序設(shè)置了指令緩沖棧，取指令的時間可忽略不計1一次重疊執(zhí)行方式,分析指令和執(zhí)行指令時間不相等時2采用先行緩沖棧的指令執(zhí)行過程4個先行緩沖棧:先行指令緩沖棧、先行操作棧、先行讀數(shù)棧、后行寫數(shù)棧153指令執(zhí)行過程的時空圖表示方法指令執(zhí)行過程的另一種形式的時空圖表示理想情況下，指令執(zhí)行部件應(yīng)一直忙碌連續(xù)執(zhí)行n條指令的時間165.1.2.3先行緩沖棧設(shè)置先行緩沖棧的目的：使指令分析器和指令執(zhí)行部件各自獨(dú)立工作1先行指令緩沖棧2先行操作棧3先行讀數(shù)棧4后行寫數(shù)棧171先行指令緩沖棧位置：主存儲器與指令分析器之間作用：平滑主存儲器取指令和指令分析器的工作指令分析器從先行指令緩沖棧取指令運(yùn)算、移位、數(shù)據(jù)傳送等指令處理成RR型指令，送入先行操作棧RR型指令，不必處理，直接送先行操作棧RS和RX型指令，主存有效地址送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的主存地址碼部分，形成RR*指令送先行操作棧RI型指令，指令中的立即數(shù)送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的立即數(shù)部分，形成RR*指令送先行操作?！拔招汀敝噶?--在指令分析器中直接執(zhí)行無條件轉(zhuǎn)移及條件轉(zhuǎn)移指令182先行操作棧位置：指令分析器和運(yùn)算控制器之間作用：使指令分析器和運(yùn)算器各自獨(dú)立工作工作過程采用先進(jìn)先出方式工作，由先行指令寄存器堆和控制邏輯組成193先行讀數(shù)棧位置：主存儲器與運(yùn)算器之間作用：平滑運(yùn)算器與主存儲器的工作工作過程每個緩沖寄存器由地址寄存器、操作數(shù)寄存器和標(biāo)志三部分組成也可把地址寄存器和操作數(shù)寄存器合為一個當(dāng)收到從指令分析器中送來的有效地址時，就向主存申請讀操作數(shù)讀出的操作數(shù)存放在操作數(shù)緩沖寄存器中或覆蓋掉地址寄存器中的地址204后行寫數(shù)棧每個后行緩沖寄存器由地址寄存器、數(shù)據(jù)寄存器和標(biāo)志三個部分組成指令分析器遇到向主存寫結(jié)果的指令，把形成的有效地址送入后行寫數(shù)棧的地址寄存器中，并用該地址寄存器的編號替換指令的目的地址部分，形成RR*指令送入先行操作棧運(yùn)算器執(zhí)行這條RR*型寫數(shù)指令時，只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可215在采用先行控制方式的處理機(jī)中，一個程序的執(zhí)行情況指令地址指令執(zhí)行情況......k-i-1已執(zhí)行完成的指令k-i......k-1在“后行寫數(shù)?！敝械却呀Y(jié)果寫到主存儲器中的指令(等待運(yùn)算結(jié)果的寫數(shù)指令已包含在k...k+j+n等以下幾行，不再單獨(dú)出現(xiàn))k正在“指令執(zhí)行部件”中執(zhí)行的指令k+1......k+j已由“指令分析器”預(yù)處理完成，被存放在“先行操作?！敝械腞R*型指令，指令所需要的操作數(shù)也已讀到“先行讀數(shù)?！敝衚+j+1......k+j+n指令已由“指令分析器”預(yù)處理完成，存放在“先行操作?！敝?，指令所需要的操作數(shù)還沒有讀到“先行讀數(shù)?！敝衚+j+n+1正在“指令分析器”中進(jìn)行分析和預(yù)處理的指令k+j+n+2......k+j+n+m已從主存儲器中預(yù)取到“先行指令緩沖?！敝械闹噶頺+j+n+m+1......還沒有進(jìn)入處理機(jī)的指令225.2流水線處理機(jī)空間并行性(同時性并行,資源重復(fù))設(shè)置多個獨(dú)立的操作部件多操作部件處理機(jī)超標(biāo)量處理機(jī)時間并行性(并發(fā)性并行,時間重疊)采用流水線技術(shù)不增加或只增加少量硬件就能使運(yùn)算速度提高幾倍流水線處理機(jī)超流水線處理機(jī)時間---空間關(guān)系資源重復(fù)(空間并行性,同時性并行):增加空間以多個空間容納多條指令時間重疊(時間并行性,并發(fā)性并行):細(xì)分空間以多個子空間容納多條指令235.2.1流水線工作原理5.2.1.1從重疊到流水線一次重疊執(zhí)行方式，就是一種簡單的指令流水線流水線的每一個階段稱為stage,流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級、流水節(jié)拍等在每一個流水段的末尾或開頭必須設(shè)置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等為了簡化，流水線中一般不畫出流水鎖存器先行控制技術(shù)--復(fù)雜，不整齊，不可預(yù)知，不可控流水線--簡單，統(tǒng)一，可預(yù)知，可控分析器分析k+1流水

鎖存器執(zhí)行部件執(zhí)行k流水

鎖存器輸入輸出Dt1Dt2242一種指令流水線一般4至12個流水段等于及大于8個流水段的稱為超流水線處理機(jī)機(jī)器周期(CPU周期,T1T2T3T4,一次數(shù)據(jù)通路,起點到終點)被分解到更細(xì)的操作步驟流水線的連接圖表示方法表示流水線的邏輯關(guān)系流水線的時空圖表示方法表示流水線的時間關(guān)系流水線的預(yù)約表表示方法將在非線性流水線中介紹取指形成操

作數(shù)地址譯碼取操作數(shù)執(zhí)行保存結(jié)果255.2.1.2時空圖一條簡單流水線的時空圖t時間s流水段(空間)k指令(指令序號)------三元關(guān)系水平方向------不同時間某流水段處理的指令垂直方向------同一時間各流水段處理的指令斜線------一條指令的流過過程所有斜線放平，保持重疊------縱坐標(biāo)為指令序號的時空圖所有斜線放平、首尾相接------T0，串行方式斜線越陡峭，時間壓縮越厲害，TN越小，流水線加速越多分析k分析k+1分析k+2分析k+3執(zhí)行k執(zhí)行k+1執(zhí)行k+2執(zhí)行k+3時間空間s0t1t2t3t4t526另一種時空圖t時間s流水段(空間)I指令(指令序號)------三元關(guān)系水平方向------不同時間某條指令的處理垂直方向------同一時間各條指令的處理斜線------一個流水段不同時間處理的指令直觀描述程序的執(zhí)行過程前一種時空圖直觀描述流水段與時間的關(guān)系IF時鐘

周期指令I(lǐng)1I2I3IDEXWRIFIDEXWRIFIDEXWR12345627一個浮點加法器流水線的時空圖求階差、對階、尾數(shù)加和規(guī)格化4個流水段ED1時間空間0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：規(guī)格化MA：尾數(shù)加EA：對階ED：求階差285.2.1.3流水線的特點1在流水線中處理的必須是連續(xù)任務(wù)只有連續(xù)不斷地提供任務(wù)才能充分發(fā)揮流水線的效率采用流水線方式工作的處理機(jī)，特別是當(dāng)流水線的級數(shù)較多時，要在軟件和硬件設(shè)計等多方面盡量為流水線提供連續(xù)的任務(wù)，以提高流水線的效率2把一個任務(wù)(一條指令或一個操作)分解為幾個有聯(lián)系的子任務(wù)，每個子任務(wù)由一個專門的功能部件來實現(xiàn)流水線把一個大的功能部件分解為多個獨(dú)立的功能部件，依靠多個功能部件并行工作來縮短程序的執(zhí)行時間3在流水線的每一個功能部件的后面要要設(shè)置一個緩沖寄存器，或稱為鎖存器、閘門寄存器，用于保存本段的執(zhí)行結(jié)果因為流水線中每一段的延遲時間一般不可能都相等在段與段之間傳送子任務(wù)時，必須通過緩沖寄存器。當(dāng)某一個流水段的執(zhí)行時間變化范圍比較大時，要設(shè)置多個緩沖寄存器295.2.1.3流水線的特點4流水線各段的時間應(yīng)盡量相等,否則將引起“堵塞”、“斷流”執(zhí)行時間長的一段將成為整個流水線的“瓶頸”，流水線中的各個功能部件將不能充分發(fā)揮作用一種辦法是把“瓶頸”流水段再細(xì)分，另一種辦法是重復(fù)設(shè)置瓶頸功能段5流水線需要有“裝入時間”和“排空時間”，流過時間k裝入時間,k-1,全空-->全滿,指第一個任務(wù)進(jìn)入流水線到填滿流水線的時間排空時間,k-1,全滿-->全空,指第n個(最后一個)任務(wù)進(jìn)入流水線到輸出流水線的時間這兩種情況下，流水線不滿載流水線完全充滿，整個流水線的效率才得到充分發(fā)揮在流水線處理機(jī)的設(shè)計過程中，要充分注意上述問題，以設(shè)計出高效率的流水線在流水線處理機(jī)上設(shè)計程序時，也必須注意流水線的上述特點，以充分發(fā)揮流水線處理機(jī)的高效率305.2.2流水線的分類5.2.2.1線性流水線與非線性流水線流水線的各個流水段之間是否有反饋信號線性流水線(LinearPipelining)

每個流水段都流過一次，且僅流過一次非線性流水線(NonlinearPipelining)

在流水線的某些流水段之間有反饋回路或前饋回路線性流水線能夠用流水線連接圖唯一表示

非線性流水線須用流水線連接圖流水線預(yù)約表等共同表示S1輸入S2S3輸出前饋回路反饋回路一種簡單的非線性流水線S1輸入S2S3輸出前饋回路反饋回路315.2.2.2流水線的級別處理機(jī)級流水線,又稱為指令流水線(InstructionPipelining)如采用先行控制器的處理機(jī)，各功能部件之間的流水線1個任務(wù)=1條指令先行指令

緩沖棧輸入先行指令

分析器先行讀數(shù)棧

先行操作棧取指譯碼取操作數(shù)指令執(zhí)行部件后行寫數(shù)棧輸出執(zhí)行寫結(jié)果32部件級流水線(運(yùn)算流水線ArithmeticPipelining、操作流水線)1個任務(wù)=1個加法,......浮點加法器流水線處理機(jī)之間的流水線稱為宏流水線(MacroPipelining)

每個處理機(jī)對同一個數(shù)據(jù)流的不同部分分別進(jìn)行處理1個任務(wù)=1個數(shù)據(jù)流求階差輸入輸出Dt1對階尾數(shù)加規(guī)格化Dt2Dt3Dt4P1輸入任務(wù)1MM…P2任務(wù)2MPn任務(wù)n輸出5.2.2.2流水線的級別335.2.2.3單功能流水線與多功能流水線單功能流水線只能完成一種固定功能的流水線Cray-1計算機(jī)有12條；YH-1計算機(jī)有18條；Pentium有一條5段的定點和一條8段的浮點流水線；PentiumIII有三條指令流水線，其中兩條定點指令流水線，一條浮點指令流水線多功能流水線流水線的各段通過不同連接實現(xiàn)不同功能Texas公司的ASC計算機(jī)中的8段流水線，能夠?qū)崿F(xiàn)：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等34355.2.2.4靜態(tài)流水線與動態(tài)流水線靜態(tài)流水線同一段時間內(nèi)，多功能流水線中的各個功能段只能按照一種固定的方式連接，實現(xiàn)一種固定的功能只有連續(xù)出現(xiàn)同一種運(yùn)算時，靜態(tài)流水線的效率才能得到充分的發(fā)揮動態(tài)流水線在同一段時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能36一次性整體切換1時間空間023…n123…n123…n123…n123…n123…n1234…123…12……1輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出靜態(tài)流水線時空圖浮點加法定點乘法靜態(tài)流水線時空圖371時間空間023…n123…n123…n123…n123…n123…n輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出動態(tài)流水線時空圖………………123546123541234123…………浮點加法定點乘法逐段切換動態(tài)流水線時空圖38流水線的其他分類方法按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線按照控制方式：同步流水線和異步流水線按照流水線輸出端流出的任務(wù)與流水線輸入端流入的任務(wù)的順序是否相同:順序流水線與亂序流水線亂序流水線又稱為無序流水線、錯序流水線或異步流水線S1就緒回答S2就緒回答S3就緒回答輸出就緒回答輸入395.2.3線性流水線的性能分析衡量流水線性能的主要指標(biāo)有：吞吐率TP、加速比S和效率E一般公式吞吐率(ThoughPut)n為任務(wù)數(shù)，Tk為完成n個任務(wù)所用時間加速比(Speedup)S=順序執(zhí)行時間T0/流水線執(zhí)行時間Tk效率(Efficiency)405.2.3.1吞吐率(ThoughPut)各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下完成n個連續(xù)任務(wù)需要的總時間Tk=(k+n-1)Dtk為流水線的段數(shù)Dt為時鐘周期k+n-11從出口看k+n-1k第1條指令流過時間n-1條后續(xù)指令隔1T流出1條斜線+水平線2從入口看n+k-1n條指令進(jìn)入流水線的時間(吞)k-1第n條指令排空時間3從出口看k-1+nk-1第1條指令裝入時間n條指令隔1T流出1條(吐)4從入口看n-1+kn-1條指令進(jìn)入流水線的時間k最后1條指令流過時間5從效率看k-1+n-(k-1)+k-1先k-1逐段填充流水線，裝入時間最后k-1逐段排空流水線，排空時間中間n-(k-1)流水線全滿,全效工作流過時間k，裝入時間k-1，排空時間k-1，裝入三角形，排空三角形1時間空間S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nkDt(n-1)DtnDt(k-1)DtTk吐吞41流水線吞吐率各段執(zhí)行時間相等，輸入連續(xù)n個任務(wù)吞吐率最大吞吐率1/Dt各段執(zhí)行時間不相等、輸入連續(xù)任務(wù)情況下吞吐率=第1個任務(wù)流過時間+余后(n-1)個任務(wù)*瓶頸段時間最大吞吐率42流水線各段執(zhí)行時間不相等時吞吐率計算斜線間距撐開為瓶頸段時間?S1輸入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt輸出1時間空間S1S2S3S4∑Dti(n-1)Dt2Tk23…n123…n123…n123…n43流水線各段執(zhí)行時間不相等的解決辦法一是將“瓶頸”流水段細(xì)分(如果可分的話)4段--->6段二是將“瓶頸”流水段重復(fù)設(shè)置pentium420級、31級1，2Pentium系統(tǒng)結(jié)構(gòu)的核心是超標(biāo)量流水線。U,V兩條指令流水線，有各自的ALU、地址生成電路、與數(shù)據(jù)Cache的接口RISC2，4，8，16個整數(shù)運(yùn)算器2??HyperThreading超線程技術(shù)S1輸入輸出DtS2-1DtS2-2DtS2-3DtS3DtS4DtS2(3Dt)S1輸入輸出Dt1=DtS2-1S2-2S2-3S3S4Dt3=DtDt4=DtDt2=3Dt44消除“堵塞”、“斷流”前段能順利后傳后段不需空等流水段重復(fù)設(shè)置的流水線1時間空間23nS1S2-1456…14…n-2n-1n-225…n-136…n123n456…n-2n-1123n456…n-2n-1S2-2S2-3S3S4“瓶頸”流水段重復(fù)設(shè)置1時間空間S1S2S3S423…n123…n123…n123…n堵塞斷流455.2.3.2加速比(Speedup)各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下T0=nkDt加速比

最大加速比=k各段執(zhí)行時間不等，輸入連續(xù)任務(wù)情況下實際加速比46k=6k=10任務(wù)個數(shù)n加速比S10246811248163264128流水線加速比475.2.3.3效率(Efficiency)計算流水線效率的一般公式

E=有效面積/占用面積有效面積=有效的方塊推擠后的實心長方形=nkDt=T0=串行連接的(一行)方塊=T0占用面積=一個程序占用后不能為其他程序占用的時空區(qū)=一個程序占用的時空區(qū)擴(kuò)展成的外接長方形=平行四邊形+兩個三角形=kTk各流水段執(zhí)行時間相等，輸入n個連續(xù)任務(wù),流水線的效率

流水線的最高效率=148流水線效率各流水段執(zhí)行時間不等，輸入n個連續(xù)任務(wù)流水線的效率流水線各段的設(shè)備量或各段的價格不相等時流水線的效率

即

其中，ai<k，且49流水線的吞吐率、加速比與效率的關(guān)系由一般公式有S=k·E各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下T0=nkDt有E=TP·

Dt505.2.3.5流水線性能分析舉例例5.1：用一條4段浮點加法器流水線求8個浮點數(shù)的和：Z=A+B+C+D+E+F+G+H解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1時間空間23求階差4567123456712345671234567對階尾數(shù)加規(guī)格化加數(shù)ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H結(jié)果A+BC+DE+FG+HA+B+C+DE+F+G+H51例5.1時鐘周期為Dt

n=7個浮點加法共用了Tk=15Dtk=4段T0=knDt=4x7

Dt=28

Dt流水線的吞吐率(最簡分?jǐn)?shù))流水線的加速比流水線的效率525.2.4非線性流水線的調(diào)度技術(shù)線性流水線每個流水段都流過一次，且僅流過一次非線性流水線某些流水段之間有反饋回路或前饋回路非線性流水線調(diào)度的任務(wù)找出一個最小的循環(huán)周期按照這周期向流水線輸入新任務(wù)流水線的各個功能段都不會發(fā)生沖突流水線的吞吐率和效率最高535.2.4.1非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示流水線連接圖不能唯一表示非線性流水線的工作流程圖5.44流水線預(yù)約表(一個任務(wù)的處理過程，一個任務(wù)的時空圖)S1S2S3S4輸出輸入反饋線前饋線

時間流水段1234567S1XXXS2XXS3XXS4X54預(yù)約表表示一個任務(wù)的處理過程(一個任務(wù)的時空圖)預(yù)約表橫坐標(biāo)表示流水線的時鐘周期，縱坐標(biāo)表示流水線的各個流水段，中間有“X”表示該流水段在這一個時鐘周期處于工作狀態(tài)，空白表示該流水段在這一個時鐘周期不工作一行中可有多個“X”，表示一個任務(wù)在不同時鐘周期重復(fù)使用同一流水段一列中有多個“X”表示一個任務(wù)在同一個時鐘周期同時占用了多個流水段預(yù)約表的行數(shù)是流水線的段數(shù)(空間)，預(yù)約表的列數(shù)是一個任務(wù)從進(jìn)入流水線到流水線中輸出所經(jīng)過的時鐘周期數(shù)(時間)---流過時間預(yù)約表55預(yù)約表---連接圖一張預(yù)約表可能與多個流水線連接圖相對應(yīng)與上面的預(yù)約表對應(yīng)的另一種非線性流水線的連接圖移動段拓?fù)潢P(guān)系不變一個連接圖對應(yīng)有多張預(yù)約表與前一個連接圖對應(yīng)的另一張預(yù)約表同一段多個出口時間、次序未限定

時間流水段1234567S1XXXS2XS3XXS4X565.2.4.2非線性流水線的沖突向一條非線性流水線的輸入端連續(xù)輸入兩個任務(wù)之間的時間間隔稱為非線性流水線的啟動距離預(yù)約表表示一個任務(wù)的處理過程(一個任務(wù)的時空圖)預(yù)約表移位疊加，得到多個任務(wù)的時空圖流水線在某些流水段發(fā)生沖突，即兩個以上任務(wù)同時爭用一個流水段。引起非線性流水線流水段沖突的啟動距離稱為禁止啟動距離必定發(fā)生沖突的啟動距離，至少1行至少1格將出現(xiàn)兩個或多個"X"重疊不發(fā)生沖突的啟動距離是一個循環(huán)數(shù)列。使非線性流水線的任何一個流水段在任何一個時鐘周期都不發(fā)生沖突的循環(huán)數(shù)列稱為非線性流水線的啟動循環(huán)要正確地調(diào)度一條非線性流水線，首先要找出流水線的所有禁止啟動距離所有禁止啟動距離組合在一起成為一個數(shù)列，稱為禁止向量57啟動距離為3的流水線沖突情況預(yù)約表移位疊加，得到多個任務(wù)的時空圖…X3X2X1S4…X4X2X3X1X2X1S3…X3X4X2X3X1X2X1S2…X2X3X4X1X2X3X1X2X1S1…1110987654321

時間流水段兩個任務(wù)爭用一個流水段三個任務(wù)爭用一個流水段58…X2X1X1S4…X2X2X2X1S3…X3X1X1S2…X2X1X1X1S1…1110987654321

時間流水段X2X2啟動周期重復(fù)啟動周期(5)是一個循環(huán)，稱為恒定循環(huán)啟動距離為5的流水線預(yù)約表59啟動距離為(1,7)循環(huán)時的流水線預(yù)約表時間流水段12345678910111213141516S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X460非線性流水線調(diào)度的任務(wù)找出一個最小的循環(huán)周期按照這周期向流水線輸入新任務(wù)流水線的各個功能段都不會發(fā)生沖突流水線的吞吐率和效率最高615.2.4.3無沖突調(diào)度方法相關(guān)理論由E.S.Davidson及其學(xué)生們于1971年提出非線性流水線的禁止向量F(所有禁止啟動距離)計算預(yù)約表中每一行任意兩個“×”之間的距離(空到X)，去掉重復(fù)的---空到X間距作為啟動距離必定沖突由禁止向量F得到?jīng)_突向量CC=(CmCm-1…C2C1) 其中：m是禁止向量F中的最大值如果i在禁止向量F中，則Ci=1，否則Ci=0Ci=0表示相應(yīng)的間距可疊加，相應(yīng)列任一行均無沖突圖5.44所示的預(yù)約表禁止向量F=(3,4,6)，沖突向量C=(101100)

時間流水段1234567S1XXX3,3,6S2XX3S3XX4S4X62由沖突向量構(gòu)造狀態(tài)圖把沖突向量送入一個m位邏輯右移移位器，當(dāng)移位器移出0時，用移位器中的值與初始沖突向量C作“按位或”運(yùn)算，得到一個新的沖突向量；否則不作任何處理；如此重復(fù)m次預(yù)約表移位疊加，加入新任務(wù)，得到多個任務(wù)的時空圖移出1,有沖突的啟動距離，至少1行至少1格將出現(xiàn)兩個或多個"X"重疊中間形成的每一個新的沖突向量，也按這一方法進(jìn)行處理初始沖突向量和所有的新形成的沖突向量間用帶箭頭的線連接，當(dāng)新形成的沖突向量和已有沖突向量出現(xiàn)重復(fù)時合并到一起63例一條有4個功能段的非線性流水線，每個功能段的延遲時間都相等1寫出流水線的禁止向量F和初始沖突向量C2畫出調(diào)度流水線的狀態(tài)圖3求流水線的最小啟動循環(huán)和最小平均啟動距離4求平均啟動距離最小的恒定循環(huán)

時間流水段1234567S1XXS2XXS3XXS4X64解1.禁止向量為：F=(2，4，6)初始沖突向量：C=101010 (0)2.初始沖突向量邏輯右移2、4、6位時，不作任何處理(沖突)邏輯右移1、3、5和大于等于7時，移出0，要進(jìn)行處理(疊加)(0)右移1位之后：010101v101010=111111 (0)--1-->(1)(0)右移3位之后：000101v101010=101111 (0)--3-->(2)(0)右移5位之后：000001v101010=101011 (0)--5-->(3)(0)右移7位或大于7位后，還原到(0) (0)--7*->(0)(1)右移7位或大于7位后，還原到(0) (1)--7*->(0)(2)右移5位之后：000001v101010=101011 (2)--5-->(3)(2)右移7位或大于7位后，還原到(0) (2)--7*->(0)(3)右移3位之后：000101v101010=101111 (3)--3-->(2)(3)右移5位之后：000001v101010=101011 (3)--5-->(3)(3)右移7位或大于7位后，還原到(0) (3)--7*->(0)

時間流水段1234567S1XX6S2XX4S3XX2S4X65例右移2、4、6位，移出位為1，表示用這些啟動距離輸入新任務(wù)要發(fā)生沖突，不做任何處理右移1、3、5和大于等于7位，移出位是0，表示用這些啟動距離輸入新任務(wù)不會發(fā)生沖突7*表示大于等于71010101111111011111010117*157*3537*57*7*157*3537*57*(0)(1)(2)(3)66簡單循環(huán)預(yù)約表與狀態(tài)圖是唯一對應(yīng)但不同的預(yù)約表也可能有相同的狀態(tài)圖3.簡單循環(huán)：狀態(tài)圖中各個沖突向量最多只經(jīng)過一次的啟動循環(huán)7*只能最后一個簡單循環(huán)的個數(shù)一般是有限的由簡單循環(huán)可計算出平均啟動距離最小的啟動循環(huán)為(1，7)或(3，5)其平均啟動距離為4平均啟動距離最小的恒定循環(huán)為(5)(7)串行處理，性能最差簡單循環(huán)平均啟動距離(1,7)4(3,7)5(5,7)6(3,5,7)5(5,3,7)5(3,5)4(5)5(7)767最小啟動循環(huán)為(3,5)的流水線工作狀態(tài)

時間功能段12345678910111213141516S1X1X2X1X3X2X4X3…S2X1X2X1X2X3X4X3…S3X1X1X2X2X3X3X4…S4X1X2X3X4…68最小啟動循環(huán)為(1,7)的流水線工作狀態(tài)

時間流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4吞吞吞吞吐吐吐69??最小啟動循環(huán)為(1,7),10個，11個任務(wù)的完成時間流過時間=7T?吞序列?吐序列?吞吐率705.2.4.4優(yōu)化調(diào)度方法L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍1下限是預(yù)約表中任意一行里“×”的最多個數(shù)2小于或等于狀態(tài)圖中任意一個簡單循環(huán)的平均啟動距離3最小平均啟動距離的上限是沖突向量中1的個數(shù)再加上11992年，L.E.Shar證明了上述限制范圍最有用的是第1條。預(yù)約表中“×”最多的行一定是瓶頸流水段采用預(yù)留算法調(diào)度非線性流水線第1步：確定最小平均啟動距離為預(yù)約表中任意一行中“×”的最多個數(shù)第2步：確定最小啟動循環(huán)以恒定循環(huán)作為最小啟動循環(huán)第3步：采用預(yù)留算法，插入非計算延遲段實現(xiàn)最小啟動循環(huán)71插入非計算延遲段實現(xiàn)最小啟動循環(huán)上一節(jié)的例子：S1、S2、S3對應(yīng)的行有2個“×”，最小平均啟動距離為2以恒定循環(huán)(2)作為最小啟動循環(huán)在S4的輸出端到S3的輸入端中間插入一個非計算延遲D1每一行中與第1個“×”的距離為2的倍數(shù)的位置都要預(yù)留出來(數(shù)空白)，實現(xiàn)最小啟動循環(huán)的疊加間距S3行的第2個“×”從周期5延遲到周期6S2行的第2個“×”也要向后延遲一個周期，從周期6延遲到周期7S1行的第2個“×”也要向后延遲一個周期，從周期7延遲到周期8流過時間增加，但平均啟動距離最小72插入一個非計算延遲D173非線性流水線中，“×”最多的流水段一定是“瓶頸“流水段最優(yōu)調(diào)度的流過時間增加，但平均啟動距離最小最優(yōu)調(diào)度的目標(biāo)是使“瓶頸”流水段處于忙碌狀態(tài)，沒有空閑最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率、加速比和效率達(dá)到最優(yōu)?非恒定循環(huán)，如(1,3)的預(yù)留?最優(yōu)調(diào)度使得流過時間增加,吞吐率、加速比和效率等性能指標(biāo)是否變壞74先行控制--->流水線線性流水線--->非線性流水線無沖突調(diào)度--->優(yōu)化調(diào)度755.3相關(guān)性分析技術(shù)5.3.1數(shù)據(jù)相關(guān)5.3.2控制相關(guān)5.3.3條件分支對流水線的影響5.3.4靜態(tài)分支預(yù)測技術(shù)5.3.5動態(tài)分支預(yù)測技術(shù)5.3.6提前形成條件碼5.3.7精確斷點與不精確斷點765.3.1數(shù)據(jù)相關(guān)相關(guān)correlation:相鄰或相近的兩條指令存在某種關(guān)系,可能影響指令的重疊執(zhí)行,后一條指令不能在原定的時鐘周期執(zhí)行數(shù)據(jù)相關(guān)執(zhí)行本條指令的過程中，用到的指令、操作數(shù)、變址量等正好是前面指令的執(zhí)行結(jié)果須等待前面的指令執(zhí)行完成，并把結(jié)果寫到主存或寄存器后，本條指令才能開始執(zhí)行控制相關(guān)條件分支指令、轉(zhuǎn)子程序指令、中斷等引起的相關(guān)數(shù)據(jù)相關(guān)有四種指令相關(guān)主存操作數(shù)相關(guān)通用寄存器相關(guān)變址相關(guān)解決數(shù)據(jù)相關(guān)的方法有兩種推后分析法設(shè)置專用路徑法771指令相關(guān)發(fā)生指令相關(guān)

n：STORER1,n+1n+1：……滿足關(guān)系：結(jié)果地址(n)=指令地址(n+1)當(dāng)?shù)趎條指令把執(zhí)行結(jié)果寫到主存前，取出的第n+1條指令顯然是錯誤的78指令相關(guān)造成的后果采用k個流水段的流水線處理機(jī)中，第n條指令修改從第n+1到第n+k指令中的任意一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤采用先行控制方式的處理機(jī)中，如果執(zhí)行部件正在執(zhí)行第n條指令，與下面的任意一條指令發(fā)生相關(guān)，都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤已經(jīng)存放在先行操作棧中的指令正在指令分析器中進(jìn)行預(yù)處理指令已經(jīng)預(yù)取到先行指令緩沖棧中的指令更為嚴(yán)重的是：有一些“吸收型”指令，已在指令分析器執(zhí)行完成79解決指令相關(guān)的根本辦法在程序設(shè)計中不允許修改指令現(xiàn)代程序設(shè)計方法要求程序具有再入性，可被遞歸調(diào)用IBM370機(jī)中，用“執(zhí)行指令”來解決指令相關(guān)“執(zhí)行指令”本身并不執(zhí)行，它執(zhí)行的是由第二地址((X2)+(B2)+D2)決定的主存單元中的指令。這個主存單元一般不在指令區(qū)，而是在數(shù)據(jù)區(qū)802主存操作數(shù)相關(guān)發(fā)生主存操作數(shù)相關(guān)的指令序列指令執(zhí)行結(jié)果寫到主存，所需要的操作數(shù)也來自主存

n：OPA1，A2，A3；A1=(A2)OP(A3)n+1：OPA1，A2，A3；A1=(A2)OP(A3)出現(xiàn)下列兩種情況之一時，發(fā)生主存操作數(shù)相關(guān)A1(n)=A2(n+1)A1(n)=A3(n+1)81

解決辦法運(yùn)算結(jié)果寫到通用寄存器，而不寫到主存對于訪問主存儲器的請求，寫結(jié)果的優(yōu)先級高于讀操作數(shù)對設(shè)置有先行操作棧的處理機(jī)，解決操作數(shù)相關(guān)的辦法剛進(jìn)入先行操作棧中的指令在向主存讀操作數(shù)之前，先把訪問主存的地址與后行寫數(shù)棧中的所有主存地址進(jìn)行比較如發(fā)現(xiàn)有相等的，則先行操作棧的讀操作數(shù)要暫緩進(jìn)行，等到發(fā)生操作數(shù)相關(guān)的指令執(zhí)行完成，并把結(jié)果寫回到主存之后再開始讀操作數(shù)823通用寄存器數(shù)據(jù)相關(guān)發(fā)生通用寄存器數(shù)據(jù)相關(guān)發(fā)生的可能性最大，影響面也最大的一種數(shù)據(jù)相關(guān)

n：OPR1，A2；R1=(R1)OP(A2)n+1：OPR1，R2；R1=(R1)OP(R2)如果發(fā)生：R1(n)=R1(n+1)，稱為R1數(shù)據(jù)相關(guān)如果發(fā)生：R1(n)=R2(n+1)，稱為R2數(shù)據(jù)相關(guān)比R1數(shù)據(jù)相關(guān)晚1T83解決通用寄存器數(shù)據(jù)相關(guān)的方法方法一分析指令推后一個(機(jī)器)周期下一指令分析階段讀操作數(shù)推后到上一指令執(zhí)行階段寫結(jié)果后一周期串行進(jìn)行速度損失大方法二分析指令推后一個節(jié)拍(T4+)下一指令分析階段讀操作數(shù)推后到上一指令執(zhí)行階段寫結(jié)果后一節(jié)拍84解決通用寄存器數(shù)據(jù)相關(guān)的方法方法三寄存器到運(yùn)算器有直接數(shù)據(jù)通路(閉環(huán))讀操作數(shù)、寫運(yùn)算結(jié)果與指令執(zhí)行合在一個節(jié)拍數(shù)據(jù)從寄存器讀出，在運(yùn)算器中完成運(yùn)算，結(jié)果寫回寄存器的整個回路中，只有寄存器是時序邏輯寄存器個數(shù)和操作部件個數(shù)不多時，是一種最常用的方法存在問題寄存器個數(shù)比較多時，讀、寫寄存器的時間長功能部件數(shù)量比較多時，寄存器堆的讀寫端口很多。必須使用多級多路選擇器85方法四設(shè)置專用數(shù)據(jù)通路(一個更小的閉環(huán))(輸入輸出兜兩圈，合并兩條指令的數(shù)據(jù)通路，直接數(shù)據(jù)通路)在運(yùn)算器的入口處增加兩個鎖存器86第k條指令的執(zhí)行結(jié)果，如果寫回寄存器堆，然后再讀出來，則第k+1條指令須推后兩個周期增加相關(guān)專用通路后，第k+1條指令的執(zhí)行不必推后。節(jié)省了兩個時鐘周期通用寄存器數(shù)據(jù)相關(guān)出現(xiàn)的概率很高，增加一條相關(guān)專用通路是合適的指令的執(zhí)行結(jié)果在寫回到通用寄存器的時候，同時也寫入運(yùn)算器入口處的鎖存器數(shù)據(jù)從鎖存器讀出，在運(yùn)算器中完成運(yùn)算，結(jié)果再寫入鎖存器的整個回路中，只有鎖存器是時序邏輯874變址相關(guān)采用變址方式的處理機(jī)，變址偏移量放在寄存器，與通用寄存器的數(shù)據(jù)相關(guān)類似，有可能發(fā)生變址相關(guān)通用寄存器作變址寄存器，指令分析時用來計算有效地址

k：OPR1，R2 ;R1=(R1)OP(R2)k+1：OPR1，A2(X2) ;R1=(R1)OP((A2)+(X2))k+2：OPR1，A2(X2) ;R1=(R1)OP((A2)+(X2))如果發(fā)生：R1(k)=X2(k+1)稱為一次變址相關(guān)如果發(fā)生：R1(k)=X2(k+2)稱為二次變址相關(guān)比一次變址相關(guān)多間隔一條指令的時間變址相關(guān)專用通路885LOAD相關(guān)RISC處理機(jī)中，只有LOAD操作能訪問存儲器LOAD操作的執(zhí)行時間可能比較長

n：LOADR1，A ；R1=(A)n+1：ADDR2，R1 ；R2=(R1)OP(R2)如果R1(n)=R1(n+1)，則發(fā)生LOAD數(shù)據(jù)相關(guān)(主存讀且R1寫)解決方法方法一：由編譯器在LOAD之后插入不發(fā)生數(shù)據(jù)相關(guān)的指令由于LOAD操作的執(zhí)行時間不能確定，依靠插入指令不能根本解決問題方法二：由硬件自動插入空操作，直到LOAD操作完成只有一條流水線的處理機(jī)中，可采用停止節(jié)拍發(fā)生器的方法，直到存儲器的回答信號到來，再啟動節(jié)拍發(fā)生器89各種數(shù)據(jù)相關(guān)的三種主要解決方法1采用硬件或軟件的辦法盡量避免數(shù)據(jù)相關(guān)發(fā)生例如，為了避免通用寄存器數(shù)據(jù)相關(guān)，采用D型觸發(fā)器構(gòu)成通用寄存器堆，且通用寄存器堆在一個節(jié)拍中能夠讀出兩個操作數(shù)并寫回一個結(jié)果2在確保指令正確執(zhí)行的前提下，推后指令分析3設(shè)置相關(guān)專用通路來解決數(shù)據(jù)相關(guān)905.3.2控制相關(guān)程序的執(zhí)行方向可能被改變而引起的相關(guān)可能改變程序執(zhí)行方向的指令無條件轉(zhuǎn)移一般條件轉(zhuǎn)移復(fù)合條件轉(zhuǎn)移子程序調(diào)用、中斷數(shù)據(jù)相關(guān)稱為局部相關(guān)，影響到的僅僅是本條指令附近的少數(shù)幾條指令控制相關(guān)稱為全局相關(guān)，影響的范圍要大得多，它可能引起程序執(zhí)行方向的改變911無條件轉(zhuǎn)移無條件轉(zhuǎn)移指令在程序中一般如下

k：……

k+1：JMPL

…：……

L：……流水線處理機(jī)中，無條件轉(zhuǎn)移指令不進(jìn)入執(zhí)行流水段，一般在指令譯碼(或稱為指令分析)階段就實際執(zhí)行完成如果在處理機(jī)中設(shè)置有先行指令緩沖棧，無條件轉(zhuǎn)移指令一般能夠在指令分析階段就執(zhí)行完成，形成轉(zhuǎn)移地址L同時送入先行程序計數(shù)器PC1和現(xiàn)行程序計數(shù)器PC中，指令緩沖棧按照PC1的指示重新開始向存儲控制器申請取指令921無條件轉(zhuǎn)移轉(zhuǎn)移距離比較遠(yuǎn)指令L不在指令緩沖棧中，則要將指令緩沖棧中的所有指令全部作廢指令分析器要等待一個“取指令L”周期之后才能開始“分析L”轉(zhuǎn)移距離比較近有可能指令L已經(jīng)被取到了指令緩沖棧中作廢指令緩沖棧中的部分指令，即作廢從k+2到L-1之間的所有指令指令分析器完成“分析k+1”后，可接著進(jìn)行“分析L”，即指令分析器仍可不停頓地連續(xù)工作931無條件轉(zhuǎn)移設(shè)置有先行操作棧的處理機(jī)中，無條件轉(zhuǎn)移指令一般對指令執(zhí)行部件的工作不會造成影響為進(jìn)一步減少無條件轉(zhuǎn)移指令造成的影響，在先行指令緩沖棧的入口處增設(shè)一個專門處理無條件轉(zhuǎn)移指令的指令分析器。就不會再發(fā)生作廢先行緩沖棧中指令的情況942一般條件轉(zhuǎn)移條件轉(zhuǎn)移指令有兩種一般條件轉(zhuǎn)移指令的轉(zhuǎn)移條件來自上一條指令，或更前面的指令復(fù)合型條件轉(zhuǎn)移指令直接根據(jù)本條指令的執(zhí)行結(jié)果決定是否轉(zhuǎn)移

k：…… ;置條件碼CC

k+1：JMP(CC)L ;CC為真轉(zhuǎn)向L，否則繼續(xù)執(zhí)行k+2

k+2：……

...：……

L：……952一般條件轉(zhuǎn)移一般條件轉(zhuǎn)移指令，相關(guān)最嚴(yán)重的情況發(fā)生在條件碼是由上一條指令產(chǎn)生的條件碼要直到先行操作棧中的指令全部完成，在“執(zhí)行k”的末尾才能形成“分析k+1”在一開始就要根據(jù)條件碼判斷轉(zhuǎn)移條件是否成立指令分析器分析到條件轉(zhuǎn)移指令時，必須停下來等待所需的條件碼962一般條件轉(zhuǎn)移無論轉(zhuǎn)移是否成功，條件轉(zhuǎn)移指令都在指令分析階段就已執(zhí)行完成如果轉(zhuǎn)移不成功分析k+2如果轉(zhuǎn)移成功指令L已經(jīng)在先行指令緩沖棧，指令分析器接著“分析L”指令L不在先行指令緩沖棧，指令分析器要等待一個周期轉(zhuǎn)移不成功，對程序執(zhí)行影響不大轉(zhuǎn)移成功時，指令執(zhí)行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令采用流水線方式的處理機(jī)中，通過軟件與硬件的多種手段來盡可能地降低轉(zhuǎn)移成功的概率，減少轉(zhuǎn)移成功造成的影響973復(fù)合條件轉(zhuǎn)移復(fù)合型條件轉(zhuǎn)移指令本身就是一條運(yùn)算指令，根據(jù)本條指令的運(yùn)算結(jié)果決定是否轉(zhuǎn)移復(fù)合型條件轉(zhuǎn)移指令的執(zhí)行時間關(guān)系

k：OPL;先執(zhí)行OP操作

;根據(jù)執(zhí)行結(jié)果產(chǎn)生的條件碼決定是否轉(zhuǎn)向Lk+1：……

…：……L：……復(fù)合型條件轉(zhuǎn)移指令不能在指令分析器中執(zhí)行完成，須象其它運(yùn)算型指令一樣經(jīng)指令執(zhí)行部件執(zhí)行無條件轉(zhuǎn)移指令和一般條件轉(zhuǎn)移指令能在指令分析器中執(zhí)行完成，稱為吸收型指令983復(fù)合條件轉(zhuǎn)移轉(zhuǎn)移不成功不造成任何影響，復(fù)合型條件轉(zhuǎn)移指令就象一條普通的運(yùn)算型指令一樣轉(zhuǎn)移成功造成的影響比一般條件轉(zhuǎn)移指令還要大得多全部或部分作廢先行指令緩沖棧中已經(jīng)預(yù)取的指令全部或部分作廢先行操作棧中的指令和先行讀數(shù)棧中的操作數(shù)可能作廢當(dāng)前在指令分析器中分析的指令99!數(shù)據(jù)相關(guān) 數(shù)據(jù)引用的正確性 指令分析器---運(yùn)算器控制相關(guān) 指令流動的正確性無條件轉(zhuǎn)移 先行指令緩沖棧一般條件轉(zhuǎn)移 先行指令緩沖棧 等待條件碼復(fù)合條件轉(zhuǎn)移 運(yùn)算器---先行指令緩沖棧1005.3.3條件分支對流水線的影響條件分支或程序中斷引起的相關(guān)被稱為全局相關(guān)全局相關(guān)對流水線的吞吐率和效率的影響相對于數(shù)據(jù)相關(guān)要大得多處理好條件轉(zhuǎn)移和中斷的關(guān)鍵問題要確保流水線能夠正常工作減少因“斷流”引起的吞吐率和效率的下降1/5的分支指令CPU內(nèi)(流水線)跳

Cache替換

虛存頁替換10ms延遲1011條件分支的處理方法一般程序中，條件轉(zhuǎn)移指令占五分之一左右條件轉(zhuǎn)移指令對流水線的影響很大，必須采取措施來減少這種影響可能采取的措施(1)延遲轉(zhuǎn)移技術(shù)和指令取消技術(shù)只能用于單流水線標(biāo)量處理機(jī)，且流水線級數(shù)不能太多據(jù)統(tǒng)計，編譯器調(diào)度一條指令成功的概率在90%以上調(diào)度兩條指令成功的概率只有40%左右沒有合適的指令可調(diào)度時，編譯器只能插入空操作SUN公司的SPARC處理機(jī)，SGI公司的一部分MIPS處理機(jī)采用了延遲轉(zhuǎn)移技術(shù)。HPPA處理機(jī)采用指令取消技術(shù)1021條件分支的處理方法(2)靜態(tài)分支預(yù)測技術(shù)轉(zhuǎn)移預(yù)測的方向是固定的，或者預(yù)測轉(zhuǎn)移不成功，或者預(yù)測轉(zhuǎn)移成功在程序?qū)嶋H執(zhí)行過程中，轉(zhuǎn)移預(yù)測的方向不能改變靜態(tài)轉(zhuǎn)移預(yù)測可以只用軟件實現(xiàn)，也可用硬件來實現(xiàn)，還可以在轉(zhuǎn)移的兩個方向上都預(yù)取指令SUN/TI公司的SuperSPARC處理機(jī)采用靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)，且設(shè)置有轉(zhuǎn)移目標(biāo)緩沖棧，在兩個方向上都預(yù)取指令(3)動態(tài)分支預(yù)測技術(shù)根據(jù)近期轉(zhuǎn)移是否成功的歷史記錄預(yù)測下一次轉(zhuǎn)移的方向所有的動態(tài)轉(zhuǎn)移預(yù)測方法都能夠隨程序的執(zhí)行過程動態(tài)地改變轉(zhuǎn)移的預(yù)測方向1032條件分支在流水線中的執(zhí)行過程第i條指令所需要的條件碼由第i-1條指令給出；k個功能段的流水線中，要等到第i+k-2條指令進(jìn)入流水線時第i-1條指令才能形成條件碼1042條件分支在流水線中的執(zhí)行過程轉(zhuǎn)移不成功，則猜測正確，流水線的吞吐率和效率沒有降低轉(zhuǎn)移成功，則猜測錯誤，要先作廢流水線中已經(jīng)執(zhí)行的第i+1、i+2、……、i+k-2條指令；然后，再從分支點開始執(zhí)行第P、p+1、……

、i+k-3條指令一條k段流水線有k-2個功能段是浪費(fèi)的當(dāng)分支方向猜測錯誤時，可能造成程序執(zhí)行結(jié)果發(fā)生錯誤若第i+1條指令是：(R1)+(R2)→R1寄存器R1中內(nèi)容就被破壞，整個程序執(zhí)行的結(jié)果將錯誤目前的處理機(jī)有兩種做法一種方法是只進(jìn)行指令譯碼和準(zhǔn)備好運(yùn)算所需要的操作數(shù)，在轉(zhuǎn)移條件沒有形成之前不執(zhí)行運(yùn)算另一種方法是一直執(zhí)行到運(yùn)算完成，但不送回運(yùn)算結(jié)果1053條件分支對流水線性能的影響假設(shè)條件轉(zhuǎn)移指令在一般程序中所占的比例為p，轉(zhuǎn)移成功的概率為qn條指令的總的執(zhí)行時間是：TK-IF=(n+k-1)t+npq(k-1)t有條件轉(zhuǎn)移影響的流水線吞吐率有條件轉(zhuǎn)移影響的流水線最大吞吐率TPMAX-IF=流水線吞吐率下降的百分比D=1063條件分支對流水線性能的影響典型程序中，轉(zhuǎn)移指令占的比例為p=20%，轉(zhuǎn)移成功的概率為q=60%一條有8個功能段的指令流水線，由于條件轉(zhuǎn)移指令的影響，流水線的最大吞吐率要下降

D8==46%如果指令流水線的功能段數(shù)為10，由于條件轉(zhuǎn)移指令的影響，流水線的最大吞吐率將下降到原來的一半以下

D10==52%條件分支使流水線的吞吐率大約下降50%1075.3.4靜態(tài)分支預(yù)測技術(shù)RISC關(guān)鍵技術(shù)延遲轉(zhuǎn)移技術(shù)(p118)指令取消技術(shù)(p119)靜態(tài)分支預(yù)測在程序執(zhí)行過程中，轉(zhuǎn)移預(yù)測的方向不能改變動態(tài)分支預(yù)測在程序執(zhí)行過程中，能夠動態(tài)地改變轉(zhuǎn)移預(yù)測方向1081軟件“猜測法”

轉(zhuǎn)移不成功時，條件轉(zhuǎn)移指令對流水線的影響比較小編譯器在對源程序進(jìn)行編譯時，為了達(dá)到比較好的效果，要盡量降低轉(zhuǎn)移成功出現(xiàn)的概率優(yōu)點：不需要改變硬件結(jié)構(gòu)，只要適當(dāng)修改編譯器就能夠大幅度降低條件轉(zhuǎn)移指令的影響主要目的：通過編譯器盡量降低轉(zhuǎn)移成功的概率1091軟件“猜測法”例如：對于普通的循環(huán)程序，一般編譯器生成的目標(biāo)代碼，轉(zhuǎn)移成功的概率很高，不成功的只有一次。這種編譯結(jié)果對流水線的影響非常大1102硬件“猜測法”基本原理通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對流水線造成的影響實現(xiàn)方法在先行指令緩沖棧的入口處設(shè)置一個簡單的指令分析器，當(dāng)這個指令分析器檢測到轉(zhuǎn)移指令時，就把轉(zhuǎn)移目標(biāo)地址L送入先行程序計數(shù)器PC1中，同時保留當(dāng)前PC1中的內(nèi)容到另一寄存器中轉(zhuǎn)移成功，則猜測正確。轉(zhuǎn)移指令對流水線不造成影響轉(zhuǎn)移不成功，用保存下來的地址恢復(fù)PC1和PC中的內(nèi)容，清除先行指令緩沖棧、先行操作棧、先行讀數(shù)棧，并重新開始取指令軟件和硬件要共同配合，軟件與硬件都往同一個方向去猜測1113兩個指令緩沖棧原因?qū)τ谘h(huán)程序，軟件“猜測法”或硬件“猜測法”都能獲得很好效果對于普通條件轉(zhuǎn)移指令(向前轉(zhuǎn)移)；轉(zhuǎn)移成功與不成功的概率很難預(yù)測普通條件轉(zhuǎn)移指令；如“IF”語句編譯產(chǎn)生的條件轉(zhuǎn)移指令,轉(zhuǎn)移成功與不成功的概率一般各為50%方法增加一個指令目標(biāo)緩沖棧當(dāng)指令分析器分析到條件轉(zhuǎn)移指令時，按照轉(zhuǎn)移成功的方向預(yù)取指令到這個指令目標(biāo)緩沖棧中原來的指令緩沖棧仍按照轉(zhuǎn)移不成功的方向繼續(xù)預(yù)取指令轉(zhuǎn)移不成功，則繼續(xù)分析原來指令緩沖棧中指令轉(zhuǎn)移成功，則分析新增加的指令目標(biāo)緩沖棧中的指令112IBM370/165機(jī)采用了兩個先行指令緩沖棧先行目標(biāo)緩沖棧AIB的緩沖深度為4為了簡化對兩套先行指令緩沖棧的控制，在轉(zhuǎn)移成功時，交換先行目標(biāo)緩沖棧AIB和原來的先行指令緩沖棧IB中內(nèi)容，使指令分析器仍然從原來的指令緩沖棧IB中的取指令1135.3.5動態(tài)分支預(yù)測技術(shù)動態(tài)轉(zhuǎn)移預(yù)測技術(shù)的兩個關(guān)鍵問題一是記錄轉(zhuǎn)移歷史信息二個是根據(jù)所記錄的轉(zhuǎn)移歷史信息預(yù)測轉(zhuǎn)移的方向記錄轉(zhuǎn)移歷史信息的方法有三種第一種是把最近一次或幾次轉(zhuǎn)移是否成功的信息記錄在轉(zhuǎn)移指令中第二種是用一個小容量的高速緩沖棧保存條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)地址第三種是用Cache保存轉(zhuǎn)移目標(biāo)地址之后的n條指令根據(jù)三種不同的記錄轉(zhuǎn)移歷史信息的方法，有三類動態(tài)轉(zhuǎn)移預(yù)測技術(shù)1141在指令Cache中記錄轉(zhuǎn)移歷史信息指令Cache中專門設(shè)置一個字段，稱為“轉(zhuǎn)移歷史表”執(zhí)行轉(zhuǎn)移指令時，轉(zhuǎn)移成功或不成功的信息記錄在這個表當(dāng)下次再執(zhí)行到這條指令時，轉(zhuǎn)移預(yù)測邏輯根據(jù)“轉(zhuǎn)移歷史表”中記錄的信息預(yù)測轉(zhuǎn)移成功或不成功每一條指令一位的“轉(zhuǎn)移歷史表”，只記錄最近一次轉(zhuǎn)移是否成功的歷史信息115只記錄最近一次轉(zhuǎn)移是否成功箭頭:“轉(zhuǎn)移歷史表”修改規(guī)則，即記錄本條轉(zhuǎn)移指令實際轉(zhuǎn)移是否成功執(zhí)行條件轉(zhuǎn)移指令時，如果“轉(zhuǎn)移歷史表”中記錄的內(nèi)容是“T”，則轉(zhuǎn)移預(yù)測邏輯預(yù)測轉(zhuǎn)移成功，并按照轉(zhuǎn)移成功的方向取指令如果記錄的是“N”，按照轉(zhuǎn)移不成功的方向繼續(xù)取下一條指令116記錄最近兩次轉(zhuǎn)移是否成功的歷史信息箭頭:“轉(zhuǎn)移歷史表”修改規(guī)則，采用向左移位的方法轉(zhuǎn)移預(yù)測偏向于轉(zhuǎn)移成功只有歷史上最近兩次執(zhí)行這條轉(zhuǎn)移指令時轉(zhuǎn)移都沒有成功，本次才預(yù)測轉(zhuǎn)移不成功對于另外三種情況都預(yù)測轉(zhuǎn)移成功1171在指令Cache中記錄轉(zhuǎn)移歷史信息“轉(zhuǎn)移歷史表”的修改規(guī)則和轉(zhuǎn)移預(yù)測規(guī)則可以有多種多樣也可以記錄轉(zhuǎn)移預(yù)測是否成功的信息預(yù)測本次轉(zhuǎn)移方向時，也可以用最近預(yù)測是否成功的信息作為依據(jù)“轉(zhuǎn)移歷史表”空白時，有兩種做法一種是在“轉(zhuǎn)移歷史表”中預(yù)置轉(zhuǎn)移歷史信息另一種是根據(jù)指令本身的偏移字段的符號來預(yù)測轉(zhuǎn)移方向如果偏移字段的符號是負(fù)的，則預(yù)測轉(zhuǎn)移成功，否則預(yù)測轉(zhuǎn)移不成功主要優(yōu)點：不必專門設(shè)置轉(zhuǎn)移緩沖棧，所記錄的轉(zhuǎn)移歷史信息比較少DEC公司的Alpha21064超標(biāo)量超流水線處理機(jī)就采用了這種轉(zhuǎn)移預(yù)測方法，在一級指令Cache有一個“轉(zhuǎn)移歷史表”字段1182設(shè)置轉(zhuǎn)移目標(biāo)地址緩沖棧用高速緩沖棧保存最近k條轉(zhuǎn)移指令的“轉(zhuǎn)移歷史表”和轉(zhuǎn)移目標(biāo)地址“轉(zhuǎn)移指令地址”字段采用全相聯(lián)方式訪問當(dāng)前指令地址與轉(zhuǎn)移目標(biāo)緩沖棧中的所有轉(zhuǎn)移指令地址比較如果發(fā)現(xiàn)有相等的根據(jù)同一行中的“轉(zhuǎn)移歷史表”所記錄的歷史信息預(yù)測本次轉(zhuǎn)移的方向用轉(zhuǎn)移目標(biāo)地址預(yù)取指令根據(jù)某一種規(guī)則修改“轉(zhuǎn)移歷史表”1193設(shè)置轉(zhuǎn)移目標(biāo)指令緩沖棧上面方法的轉(zhuǎn)移目標(biāo)地址改為存放轉(zhuǎn)移目標(biāo)地址后的n條指令預(yù)測轉(zhuǎn)移方向的規(guī)則和修改“轉(zhuǎn)移歷史表”的規(guī)則與上面的方法相同1205.3.6提前形成條件碼必要性：盡早產(chǎn)生條件碼有效減少流水線吞吐率和效率損失可能性：對于大多數(shù)情況，可以在運(yùn)算實際開始之前或者在運(yùn)算中間產(chǎn)生條件碼乘法和除法兩個源操作數(shù)符號相同結(jié)果為正，相反結(jié)果為負(fù)有一個操作數(shù)為“0”，則乘積為“0”被除數(shù)為“0”，則商為“0”除數(shù)為“0”，則除法結(jié)果溢出加法和減法同號相加，異號相減，結(jié)果符號與第一操作數(shù)相同異號相加，同號相減，結(jié)果符號與絕對值大的操作數(shù)相同溢出、是否為“0”可以通過一個比較器提前產(chǎn)生在絕大多數(shù)情況下，在運(yùn)算部件的入口處設(shè)置一個比較器，能提前形成結(jié)果的正負(fù)號、是否為“0”、是否溢出等條件碼如果能夠在一個時鐘之前就產(chǎn)生條件碼，流水線就不會“斷流”Amdahl470V/6(阿姆達(dá)爾)在運(yùn)算部件的入口處設(shè)置一個LOCK部件來預(yù)判條件碼1215.2.6.3提前形成條件碼流水線處理機(jī)中對循環(huán)程序的特殊的處理產(chǎn)生條件碼的運(yùn)算型指令與使用條件碼的條件轉(zhuǎn)移指令分離原程序

LOADR1,NUM ;循環(huán)次數(shù)初值裝入到寄存器R1LOOP：…… ;循體開始

………… ;循環(huán)體結(jié)束

DECR1 ;循環(huán)次數(shù)減“1”

BNELOOP ;如循環(huán)未結(jié)束，繼續(xù)執(zhí)行循環(huán)體

;否則結(jié)束循環(huán)

HELT ;程序結(jié)束NUM:n ;循環(huán)次數(shù)編譯成如下程序

LOADR1,NUM ;循環(huán)次數(shù)初值裝入到寄存器R1LOOP:LDECR1 ;專用循環(huán)次數(shù)減“1”指令

…… ;循體開始

………… ;循環(huán)體結(jié)束

LBNELOOP ;專用測試循環(huán)是否結(jié)束的指令

HELT ;程序結(jié)束NUM:n ;循環(huán)次數(shù)1225.3.7精確斷點與不精確斷點輸入輸出設(shè)備申請的中斷服務(wù)，實際上不需要有精確斷點讓已經(jīng)進(jìn)入流水線的所有指令都執(zhí)行完成斷點就是最后進(jìn)入流水線的那條指令的地址程序性錯誤和機(jī)器故障等引起的中斷，它們出現(xiàn)的概率很低處理原則：不在于縮短時間，關(guān)鍵是要正確保存現(xiàn)場和正確恢復(fù)斷點不精確斷點(Impreciseinterrupt)方法精確斷點(Preciseinterrupt)方法123不精確斷點法采用不精確斷點法，流水線可以不“斷流”所需要的硬件比較少，控制邏輯相對比較簡單中斷響應(yīng)時間稍長要增加一條流水線的時間長度124采用不精確斷點法可能會發(fā)生如下兩個問題(1)程序執(zhí)行的結(jié)果可能出錯例如，有如下兩條指令i：FADDR1,R2；(R1)+(R2)→R1i+1：FMULR3,R1；(R3)×(R1)→R3第i條指令執(zhí)行到S6段時發(fā)現(xiàn)浮點加法結(jié)果溢出，于是發(fā)出中斷服務(wù)申請采用不精確斷點法，讓進(jìn)入流水線的第i+1條指令執(zhí)行完成第i+1條指令使用了不正確的通用寄存器R1中的內(nèi)容作源操作數(shù)，因此，浮點乘法的執(zhí)行結(jié)果一般也是不正確的(2)程序的調(diào)試?yán)щy早期一批大型流水線處理機(jī)，多采用不精確斷點法近期的流水線處理機(jī)，一般采用精確斷點法設(shè)置一定數(shù)量的后援寄存器把整個流水線中所有指令的執(zhí)行結(jié)果和現(xiàn)場都保存下來1255.4動態(tài)調(diào)度技術(shù)由硬件動態(tài)調(diào)整指令執(zhí)行順序以減少數(shù)據(jù)相關(guān)的影響能處理編譯階段無法確定的相關(guān)關(guān)系，并簡化編譯器設(shè)計在別的流水線機(jī)器上編譯的代碼也能夠高效運(yùn)行采用靜態(tài)調(diào)度方法生成的代碼也能在采用動態(tài)調(diào)度法的機(jī)器中運(yùn)行5.4.1順序流動與亂序流動5.4.2亂序流動方式中的數(shù)據(jù)相關(guān)5.4.3數(shù)據(jù)重定向方法5.4.4Tomasulo動態(tài)調(diào)度算法126順序流動方式，流水線的控制邏輯比較簡單在程序中有“先寫后讀”數(shù)據(jù)相關(guān)時，流水線可能會“斷流”，這將降低流水線的吞吐率和效率亂序流動方式中，除了有“先寫后讀”數(shù)據(jù)相關(guān)之外，還可能發(fā)生“先讀后寫”數(shù)據(jù)相關(guān)和“寫-寫”數(shù)據(jù)相關(guān)“先寫后讀”數(shù)據(jù)相關(guān)又稱為數(shù)據(jù)相關(guān)、寫讀相關(guān)、流相關(guān)、WR相關(guān)、RAW相關(guān)“先讀后寫”相關(guān)又稱為變量名相關(guān)、讀寫相關(guān)、反相關(guān)、RW相關(guān)、WAR相關(guān)“寫-寫”數(shù)據(jù)相關(guān)又稱為輸出相關(guān)、WW相關(guān)、WAW相關(guān)或?qū)懞笤賹懴嚓P(guān)1275.4.1順序流動與亂序流動順序流動方式：任務(wù)按順序流入流水線，按順序流出流水線把如下一段程序輸入到這條流水線中128順序流動方式指令k與指令k+2之間有數(shù)據(jù)相關(guān)指令k+2停留(阻塞)在功能段S2中等待讀取R0后續(xù)的指令k+4、k+5、……不能進(jìn)入流水線，k+3不能進(jìn)入S2段功能段S3、S4、S5將逐漸空閑(斷流)缺點：流水線“斷流”，有些功能段“空閑”，吞吐率和效率降低優(yōu)點：流水線的控制邏輯比較簡單WR129亂序流動方式亂序(Outoforder)流動方式，錯序流動方式、無序流動方式、異步流動方式等指令流出流水線的順序與指令原先的順序不同從流水線的輸出端看，指令流出流水線的順序與進(jìn)入流水線的順序不一樣造成流水線亂序流動方式的原因“先寫后讀”數(shù)據(jù)相關(guān)有些指令執(zhí)行的時間短或經(jīng)過的流水段比較少，超越執(zhí)行時間長或經(jīng)過流水段多的指令130亂序流動方式指令k+2保持在功能段S2中等待讀取R0滿足條件的后續(xù)指令k+3、k+4、k+5進(jìn)入功能段S2執(zhí)行，超越指令k+2進(jìn)入后續(xù)功能段S3不再出現(xiàn)“斷流”，沒有功能段“空閑”WR1315.4.2亂序流動方式中的數(shù)據(jù)相關(guān)在亂序流動方式中，還有另外兩種不同的相關(guān)下面的程序在采用亂序流動方式的流水線，可能發(fā)生三種不同的數(shù)據(jù)相關(guān)F1、F2和F3是三個浮點寄存器，A和B是兩個內(nèi)存單元(1)指令k的F1與指令k+1的F1之間：寫讀相關(guān)(RAW,先寫后讀相關(guān))(2)指令k+1的F1與指令k+2的左邊那個F1之間：讀寫相關(guān)(3)指令k的F1與指令k+2的左邊那個F1之間