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

鎖存器執行部件執行k流水

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

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

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

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

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

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

緩沖棧輸入先行指令

分析器先行讀數棧

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

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

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

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

流水線的最高效率=148流水線效率各流水段執行時間不等，輸入n個連續任務流水線的效率流水線各段的設備量或各段的價格不相等時流水線的效率

即

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

Dt505.2.3.5流水線性能分析舉例例5.1：用一條4段浮點加法器流水線求8個浮點數的和：Z=A+B+C+D+E+F+G+H解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1時間空間23求階差4567123456712345671234567對階尾數加規格化加數ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H結果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流水線的吞吐率(最簡分數)流水線的加速比流水線的效率525.2.4非線性流水線的調度技術線性流水線每個流水段都流過一次，且僅流過一次非線性流水線某些流水段之間有反饋回路或前饋回路非線性流水線調度的任務找出一個最小的循環周期按照這周期向流水線輸入新任務流水線的各個功能段都不會發生沖突流水線的吞吐率和效率最高535.2.4.1非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示流水線連接圖不能唯一表示非線性流水線的工作流程圖5.44流水線預約表(一個任務的處理過程，一個任務的時空圖)S1S2S3S4輸出輸入反饋線前饋線

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

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

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

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

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

時間流水段1234567S1XXS2XXS3XXS4X64解1.禁止向量為：F=(2，4，6)初始沖突向量：C=101010 (0)2.初始沖突向量邏輯右移2、4、6位時，不作任何處理(沖突)邏輯右移1、3、5和大于等于7時，移出0，要進行處理(疊加)(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，表示用這些啟動距離輸入新任務要發生沖突，不做任何處理右移1、3、5和大于等于7位，移出位是0，表示用這些啟動距離輸入新任務不會發生沖突7*表示大于等于71010101111111011111010117*157*3537*57*7*157*3537*57*(0)(1)(2)(3)66簡單循環預約表與狀態圖是唯一對應但不同的預約表也可能有相同的狀態圖3.簡單循環：狀態圖中各個沖突向量最多只經過一次的啟動循環7*只能最后一個簡單循環的個數一般是有限的由簡單循環可計算出平均啟動距離最小的啟動循環為(1，7)或(3，5)其平均啟動距離為4平均啟動距離最小的恒定循環為(5)(7)串行處理，性能最差簡單循環平均啟動距離(1,7)4(3,7)5(5,7)6(3,5,7)5(5,3,7)5(3,5)4(5)5(7)767最小啟動循環為(3,5)的流水線工作狀態

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

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

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

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

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

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

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))如果發生：R1(k)=X2(k+1)稱為一次變址相關如果發生：R1(k)=X2(k+2)稱為二次變址相關比一次變址相關多間隔一條指令的時間變址相關專用通路885LOAD相關RISC處理機中，只有LOAD操作能訪問存儲器LOAD操作的執行時間可能比較長

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

k：……

k+1：JMPL

…：……

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

k：…… ;置條件碼CC

k+1：JMP(CC)L ;CC為真轉向L，否則繼續執行k+2

k+2：……

...：……

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

k：OPL;先執行OP操作

;根據執行結果產生的條件碼決定是否轉向Lk+1：……

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

Cache替換

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

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

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

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

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

LOADR1,NUM ;循環次數初值裝入到寄存器R1LOOP：…… ;循體開始

………… ;循環體結束

DECR1 ;循環次數減“1”

BNELOOP ;如循環未結束，繼續執行循環體

;否則結束循環

HELT ;程序結束NUM:n ;循環次數編譯成如下程序

LOADR1,NUM ;循環次數初值裝入到寄存器R1LOOP:LDECR1 ;專用循環次數減“1”指令

…… ;循體開始

………… ;循環體結束

LBNELOOP ;專用測試循環是否結束的指令

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