,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,第三章 流水和向量處理,,3.1,提高計算機速度的措施,MIPS=IPC*f,c,,其中,IPC,為每拍流出的指令條數(shù)。提高,IPC,和,f,c,是提高計算機速度最直接最有效的方法。,,提高,IPC,：增加每拍并行流出的指令條數(shù)和配置更多的功能部件?？臻g并行。,,提高,f,c,：功能部件應(yīng)該能在更高的頻率下工作。時間平行。,,可以用,P=O,（,s*f,）衡量系統(tǒng)的潛在性能，,s,是與設(shè)備量成正比的功能部件并行度，,f,是主頻。,3.1.1,提高頻率,提高系統(tǒng)的頻率是提高系統(tǒng)性能的最直接的方法，但是頻率的提高具有很大的難度：,,1.,器件的速度和集成度,,2.,流水線分站的代價和效率,,3.,高速信號傳輸,,4.,時鐘沿的離散,,5.,高密度組裝工藝和冷卻技術(shù),,**往往當(dāng)通過提高頻率來提高計算機的速度不能滿足要求時，我們才考慮空間并行性,3.1.1,空間并行,為了達到更高的主頻，需要特殊技術(shù)并且代價巨大。這導(dǎo)致了大規(guī)模并行處理系統(tǒng),MPP,的出現(xiàn)。,,可以設(shè)置多個功能部件支持向量、超標量、超長指令字和超流水結(jié)構(gòu)。空間并行性可以有效提高計算機速度，速度提高的最大倍數(shù),<=,部件設(shè)備量增加的倍數(shù)。,,上述不等式的原因主要是有存儲和外設(shè)限制造成的，為了提高速度往往需要高帶寬存儲系統(tǒng)的支持和高效的,I/O,能力，我們將在后面的章節(jié)討論存儲系統(tǒng)和,I/O,系統(tǒng)。,,當(dāng)然在,MPP,中各個結(jié)點相聯(lián)還需要不同的互聯(lián)網(wǎng)絡(luò)的支持。,先行控制技術(shù),—,補充,1.,順序執(zhí)行方式,,執(zhí)行,n,條指令所用的時間為：,,,,如果每段時間都為,t,，則執(zhí)行,n,條指令所用的時間為：,T,＝,3 n t,,,主要優(yōu)點：,控制簡單，節(jié)省設(shè)備,,主要缺點：,速度慢，功能部件的利用率低,2.,一次重疊執(zhí)行方式,,如果兩個過程的時間相等，則執(zhí)行,n,條指令的時間為：,T,＝,(,1+2n)t,,,,,主要優(yōu)點：,,,指令的執(zhí)行時間縮短，,,功能部件的利用率明顯提高。,,主要缺點：,,,需要增加一些硬件，,,控制過程稍復(fù)雜。,3.,二次重疊執(zhí)行方式,,如果三個過程的時間相等，執(zhí)行,n,條指令的時間為：,T,＝,(,2,＋,n,）,t,,在理想情況下，處理機中同時有三條指令在執(zhí)行。,,處理機的結(jié)構(gòu)要作比較大的改變，需要采用先行控制技術(shù)。,,先行控制方式的原理,1.,采用二次重疊執(zhí)行方式必須解決兩個問題：,,(1),有獨立的取指令部件、指令分析部件和指令執(zhí)行部件,,把一個集中的指令控制器，分解成三個獨立的控制器：,,存儲控制器、指令控制器、運算控制器,,(2),要解決訪問主存儲器的沖突問題,,取指令、分析指令、執(zhí)行指令都可能要訪問存儲器,,2.,解決訪存沖突的方法：,,(1),采用低位交叉存取方式：,,這種方法不能根本解決沖突問題。,,讀指令、讀操作數(shù)、寫結(jié)果。,,(2),兩個獨立的存儲器：,獨立的指令存儲器和數(shù)據(jù)存儲器。,,如果再規(guī)定，執(zhí)行指令的執(zhí)行結(jié)果只寫到通用寄存器，則取指令、分析指令和執(zhí)行指令就可以同時進行。,,在許多高性能處理機中，有獨立的指令,Cache,和數(shù)據(jù),Cache,。這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)。,(3),采用先行控制技術(shù),,采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。,,緩沖技術(shù)通常用在工作速度不固定的兩個功能部件之間。設(shè)置緩沖棧的目的是用以平滑功能部件之間的工作速度。,,在采用了緩沖技術(shù)和預(yù)處理技術(shù)之后，運算器能夠?qū)Ｐ挠跀?shù)據(jù)的運算，從而大幅度提高程序的執(zhí)行速度。,先行處理機結(jié)構(gòu),1.,三個獨立的控制器：,,存儲控制器、指令控制器、運算控制器。,,2.,四個緩沖棧：,,先行指令緩沖棧、先行讀數(shù)緩沖棧、先行操作棧、后行寫數(shù)棧。,,3.,處理機組成,4.,先行指令緩沖棧的組成,,作用：,只要指令緩沖棧沒有充滿，就自動發(fā)出取指令的請求。,,設(shè)置兩個程序計數(shù)器：,,先行程序計數(shù)器,PC,1,，用來指示取指令，,,現(xiàn)行程序計數(shù)器,PC,，記錄指令分析器正在分析的指令地址。,,5.,存在的主要問題：,,各類指令,“,分析,”,和,“,執(zhí)行,”,的時間相差很大,,數(shù)據(jù)相關(guān),,轉(zhuǎn)移或轉(zhuǎn)子程序指令,,先行指令緩沖棧的組成,指令執(zhí)行時序,設(shè)置了指令緩沖棧，取指令的時間就可以忽略不計。,,一條指令的執(zhí)行可分為,2,個過程,,1.,分析指令和執(zhí)行指令時間不相等時的情況,采用先行緩沖棧的指令執(zhí)行過程,,先行讀數(shù)棧,,,先行操作棧,,,后行寫數(shù)棧。,,,,,,,理想情況下，指令執(zhí)行部件應(yīng)該一直忙碌。,,連續(xù)執(zhí)行,n,條指令的時間為：,先行緩沖棧,設(shè)置先行緩沖棧的目的：,使指令分析器和指令執(zhí)行部件能夠獨立工作。,,1.,先行指令緩沖棧：,,處于主存儲器與指令分析器之間,,用它來平滑主存儲器取指令和指令分析器使用指令之間的速度差異,,RR,型指令,，不必處理，直接送先行緩沖棧,,RS,型指令,，主存有效地址送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的主存地址碼部分，形成,RR*,指令送先行緩沖棧,RI,型指令,，指令中的立即數(shù)送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的立即數(shù)部分，形成,RR*,指令送先行緩沖棧,,轉(zhuǎn)移指令,，一般在指令分析器中直接執(zhí)行。,,先行操作棧,,處于指令分析器和運算控制器之間,,使指令分析器和運算器能夠各自獨立工作。,,采用先進先出方式工作，由指令寄存器堆和控制邏輯組成。,先行讀數(shù)棧,,處于主存儲器與運算器之間,,平滑運算器與主存儲器的工作,,每個緩沖寄存器由地址寄存器、操作數(shù)寄存器和標志三部分組成。也可以把地址寄存器和操作數(shù)寄存器合為一個。,,當(dāng)收到從指令分析器中送來的有效地址時，就向主存申請讀操作數(shù)。,,讀出的操作數(shù)存放在操作數(shù)寄存器中或覆蓋掉地址寄存器中的地址。,后行寫數(shù)棧,,每個后行緩沖寄存器由地址寄存器、數(shù)據(jù)寄存器和標志三部分組成。,,指令分析器遇到向主存寫結(jié)果的指令時，把形成的有效地址送入后行寫數(shù)棧的地址寄存器中，并用該地址寄存器的編號替換指令的目的地址部分，形成,RR*,指令送入先行操作棧。,,當(dāng)運算器執(zhí)行這條,RR*,型寫數(shù)指令時，,,只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可。,采用先行控制方式時一個程序的執(zhí)行情況：,緩沖深度的設(shè)計方法,以靜態(tài)分析為主，通過模擬來確定緩沖深度。,,1.,先行指令緩沖棧的設(shè)計,,考慮兩種極端情況：假設(shè)緩沖深度為,D,I,,(1),先行指令緩沖棧已經(jīng)充滿,,指令流出的速度最快，例如連續(xù)分析,RR,型指令，設(shè)這種指令序列的最大長度為,L,1,，平均分析一條這種指令的時間為,t,1,；,,指令流入的速度最慢，設(shè)平均取一條指令的時間為,t,2,。從主存儲器中取到先行指令緩沖棧中的指令條數(shù)是,L,1,－,D,I,條。,應(yīng)該滿足如下關(guān)系：,L,1,,t,1,＝,(,L,I,－,D,I,),t,2,,,計算出緩沖深度為：,,如果這種指令流的連續(xù)長度超過,L,1,，則先行指令緩沖棧失去作用。,,(2),先行指令緩沖棧原來為空,,輸入端指令流入的速度最快，每次取指令的時間最短；設(shè)這種指令序列的最大長度為,L,2,，平均取一條這種指令的時間為,t,2,’,；,輸出端指令流出的速度最慢,，指令分析器連續(xù)分析最難分析的指令；設(shè)平均分析一條指令的時間為,t,1,’,。分析的指令條數(shù)是,L,2,－,D,I,條。,,應(yīng)該滿足如下關(guān)系：,(,L,2,－,D,I,),t,1,’,＝,L,2,t,2,’,,,計算出緩沖深度為：,,如果這種指令流的連續(xù)長度超過,L,2,，先行指令緩沖棧失去緩沖作用。,設(shè)計舉例,,在一般處理機中連續(xù)執(zhí)行短指令的概率大。,,例：一個采用先行控制方式的處理機，指令分析器分析一條指令用一個周期，到主存儲器中取一條指令裝入先行指令緩沖棧平均用,4,個周期，如果這種指令的平均長度,為,9,，即,90,％的指令是執(zhí)行時間短的指令。,,解：計算先行指令緩沖棧的緩沖深度為：,先行指令緩沖棧的工作時間關(guān)系,,,,,,,,第,1,個周期，取走指令,k+1,，請求取指令,,第,4,個周期末尾，指令,k+8,取到先行指令緩沖棧,,第,8,個周期末尾，指令,k+9,取到先行指令緩沖棧,,第,9,個周期，分析指令,k+9,，先行指令緩沖棧空,,第,10,個周期，指令分析器等待,其余緩沖棧的設(shè)計原則,,一般有關(guān)系：,D,I,≥,D,C,≥,D,R,≥,D,W,,,其中：,D,I,是先行指令緩沖棧的緩沖深度，,,,D,C,是先行操作棧的緩沖深度，,,,D,R,是先行讀數(shù)棧的緩沖深度，,,,D,W,是后行寫數(shù)棧的緩沖深度。,,例如：,IBM370/165,機：,,,D,I,＝,4,，,D,C,＝,3,，,D,R,＝,2,，,D,W,＝,1,。,,我國研制的兩臺大型計算機：,,,D,I,＝,8,，,D,C,＝,D,R,＝,4,，,D,W,＝,2,。,,,D,I,＝,12,，,D,C,＝,D,R,＝,6,，,D,W,＝,2,。,流水線工作原理,1.,流水寄存器,,流水線的每一個階段稱為,流水步,、流水步驟、,流水段,、流水線階段、流水功能段、,功能段,、,流水級,、流水節(jié)拍等。,,在每一個流水段的末尾或開頭必須設(shè)置一個寄存器，稱為,流水寄存器、流水鎖存器、流水閘門寄存器等,。,,在一般流水線時空圖中不畫出流水寄存器。,2.,一種指令流水線,,一般,4,至,12,個流水段，≥,8,個流水段的稱為超流水線處理機,,,,,,3.,流水線時空圖,,一個浮點加法器流水線的時空圖,4.,流水線的主要特點,,只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效率,,盡量減少因條件分支造成的“斷流”,,通過編譯技術(shù)提供連續(xù)的相同類型操作,,每個流水線段都要設(shè)置一個流水寄存器,,時間開銷：流水線的執(zhí)行時間加長,,是流水線中需要增加的主要硬件,,各流水段的時間應(yīng)盡量相等,,流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度。,,流水線需要有,“,裝入時間,”,和,“,排空時間,”,,流水線的分類,1.,線性流水線與非線性流水線,,流水線的各個流水段之間是否有反饋信號,,線性流水線,（,Linear Pipelining,）：,,每一個流水段都流過一次，而且僅流過一次,,非線性流水線,（,Nonlinear Pipelining,）：,,某些流水段之間有反饋回路或前饋回路。,,線性流水線能夠用流水線連接圖唯一表示,,非線性流水線必須用流水線連接圖和流水線預(yù)約表共同表示,2.,按照流水線的級別來分,,處理機級流水線，又稱為,指令流水線,。,,例如：在采用先行控制器的處理機中，各功能部件之間的流水線,,部件級流水線,(,操作流水線,),,,如浮點加法器流水線,,,,,,,宏流水線,(Macro Pipelining),,,處理機之間的流水線稱，每個處理機對同一個數(shù)據(jù)流的不同部分分別進行處理。,3.,單功能流水線與多功能流水線,,單功能流水線：,,只能完成一種固定功能的流水線。,,,Cray-1,計算機種有,12,條，,YH-1,計算機有,18,條,,,Pentium,有一條,5,段定點和一條,8,段浮點流水線。,,,PentiumⅢ,有兩條定點和一條浮點指令流水線。,,多功能流水線：,,,流水線的各段通過不同連接實現(xiàn)不同功能,,,Texas,公司的,ASC,機，,8,段流水線，能夠?qū)崿F(xiàn)：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運算等。,4.,靜態(tài)流水線與動態(tài)流水線,,靜態(tài)流水線,：同一段時間內(nèi)，各個功能段只能按照一種方式連接，實現(xiàn)一種固定的功能。,動態(tài)流水線,：在同一段時間內(nèi)，各段可以按照不同的方式連接，同時執(zhí)行多種功能。,5.,流水線的其他分類方法,,按照數(shù)據(jù)表示方式：,標量流水線和向量流水線,,按照,控制方式：,同步流水線和異步流水線,,,,,,順序流水線與亂序流水線,，亂序流水線又稱為無序流水線、錯序流水線或異步流水線等。,線性流水線的性能分析,,主要指標：,吞吐率、加速比和效率,,1.,吞吐率（,Though Put,）,,流水線吞吐率的最基本公式：,,其中：,n,為任務(wù)數(shù)，,,Ｔ,k,為完成,n,個任務(wù)所用的時間。,,各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下，完成,n,個任務(wù)需要的總時間為：,,,T,k,＝,(k,＋,n,－,1),?,t,,,其中：,k,,為流水線的段數(shù)，,?,t,為時鐘周期。,,T,k,= k,? Δt + (n-1) Δt =,(k+n-1),?,t,,吞吐率為：,,最大吞吐率為：,,各段時間不等，完成,n,個連續(xù)任務(wù)：,,,吞吐率：,,,最大吞吐率：,,,,,流水線各段執(zhí)行時間不相等的解決辦法,(1),將,“,瓶頸,”,部分再細分,（如果可分的話）,2.,加速比（,Speedup,）,,計算加速比的基本公式：,,各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下,,,（不考慮棧寄存器時間）,,,加速比：,,最大加速比：,,,,各段時間不等，輸入連續(xù)任務(wù)情況下,,,實際加,,,速比為：,,當(dāng)流水線段數(shù)增加時，需要連續(xù)輸入的任務(wù)數(shù)也必須增加,3.,效率（,Efficiency,）,,計算流水線效率的一般公式：,,,,各流水段時間相等，輸入,n,個連續(xù)任務(wù)，流水線的效率為：,,,,最高效率為：,,各流水段時間不等，輸入,n,個連續(xù)任務(wù)，,流水,,線效率為：,,,,,,,,,,流水線的吞吐率、,加速比與效率的關(guān)系：,,,因為：,,,因此：,E,＝,TP,·,?,t,，,S,＝,k,·,E,,,流水線性能分析舉例,,對于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。,,對于輸入不連續(xù)任務(wù)，或多功能流水線，通常采用基本公式計算。,,例：,,用一條,4,段浮點加法器流水線求,8,個浮點數(shù)的和：,Z,＝,A,＋,B,＋,C,＋,D,＋,E,＋,F,＋,G,＋,H,解：,,,Z,＝,[(A,＋,B),＋,(C,＋,D)],＋,[(E,＋,F),＋,(G,＋,H)],解：,流水線的設(shè)計原理,為提高系統(tǒng)效率我們當(dāng)然希望流水線分站越多越好，但是站寄存器的存在增加了流水線的延遲和代價，降低了功能部件的時間利用率和流水線的性價比。,,站數(shù)的確定，可以用流水線功能時間利用率不小于,e,和最高性能價格比以及器件和工藝條件綜合決定。,,,效率：,T/(T+kt,d,)>=e,,,性價比：,PCR=1/(T/k+t,d,)(C+kd),,其中,k,為流水線站數(shù)，,T,為每段執(zhí)行時間，,t,d,為站流水線的延遲時間，,C,為功能部件的價格。,流水線的設(shè)計原理,令（,PCR,）,’=0,，得到,,,因為,,（,PCR,）,’’<0,，所以此時,k,站流水線的性價比最高,,同時為了減少站寄存器的位數(shù)，分段時往往選在連線最少的部位。如果每段時間無法保持一致，則,ζ,M,（最大段執(zhí)行時間）和,t,d,同時決定了流水線的工作周期。其頻率為,1/(,ζ,M,+ t,d,).,,由于工程實現(xiàn)時元件的布局和器件時間參數(shù)離散等原因，到達各站寄存器的時鐘信號時離散的。,流水線的設(shè)計原理,設(shè)相鄰兩站的最大離散值為,Δ,，則工作頻率降低為,,1/(,ζ,M,+ t,d,+,Δ,),。,,,書本,35-36,頁，圖,3.2,信號穿透問題。,,非線性流水線的調(diào)度,非線性流水線調(diào)度的任務(wù)是要找出一個最小的循環(huán)周期，按照這周期向流水線輸入新任務(wù)，流水線的各個功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。,,1.,非線性流水線的表示,,線性流水線能夠用流水線連接圖唯一表示,,對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預(yù)約表,,例如：,,非線形流水線的連接圖和預(yù)約表,,一張預(yù)約表可能與多個流水線連接圖相對應(yīng),,一個流水線連接圖對應(yīng)于多張預(yù)約表,2.,非線性流水線的沖突,,啟動距離：連續(xù)輸入兩個任務(wù)之間的時間間隔,,流水線沖突：幾個任務(wù)爭用同一個流水段,3.,無沖突調(diào)度方法,,由及其學(xué)生于,1971,年提出,,禁止向量,：預(yù)約表中每一行任意兩個,“,×,”,之間距離的集合。上例中為,（,3,，,4,，,6,）,,沖突向量,：,C,＝（,C,m,C,m-1,…C,2,C,1,）,,其中：,m,是,禁止向量中的最大值。,,如果,i,在禁止向量中，則,C,i,＝,1,，否則,C,i,＝,0,。,,上,例中,C,＝,(101100),例：一條,4,功能段的非線性流水線，每個功能段的延遲時間都相等為,△,t,,，它的預(yù)約表如下：,,,(1),寫出流水線的禁止向量和初始沖突向量。,,,(2),畫出調(diào)度流水線的狀態(tài)圖。,,,(3),求最小啟動循環(huán)和最小平均啟動距離。,,,(4),求平均啟動距離最小的恒定循環(huán)。,,,(5),按照最小啟動循環(huán)連續(xù)輸入,4,個任務(wù)，求流水線實際吞吐率。,解：,,(1),禁止向量為：,(2,，,4,，,6),,,初始沖突向量：,S = 101010,,(2),構(gòu)造狀態(tài)圖,,,S,邏輯右移,2,、,4,、,6,位時，不作任何處理，,,邏輯右移,1,、,3,、,5,和大于等于,7,時：,,,S,右移,1,位之后：,010101∨101010,＝,111111,，,,,S,右移,3,位之后：,000101∨101010,＝,101111,，,,,S,右移,5,位之后：,000001∨101010,＝,101011,，,,,S,右移,7,位或大于,7,位后：還原到它本身。,101111,右移,5,位之后：,000001∨101010,＝,101011,，,,101011,右移,3,位之后：,000101∨101010,＝,101111,，,,101011,右移,5,位之后：,000001∨101010,＝,101011,。,簡單循環(huán)：,狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。,,(3),最小的啟動循環(huán),為（,1,，,7,）和（,3,，,5,）,,,,,平均啟動距離為,4,。,,(4),啟動距離最小的恒定循環(huán)為（,5,）,,(4),按照最小啟動循環(huán)（,1,，,7,）連續(xù)輸入,4,個任務(wù)，流水線實際吞吐率為：,1/,（,4,△t,）,數(shù)據(jù)相關(guān),(,局部相關(guān),),數(shù)據(jù)相關(guān)：在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址量等是前面指令的執(zhí)行結(jié)果，這種相關(guān)稱為數(shù)據(jù)相關(guān)。,,控制相關(guān)：由條件分支指令、轉(zhuǎn)子程序指令、中斷等引起的相關(guān)。,,解決數(shù)據(jù)相關(guān)的方法有兩種：,,推后處理,,設(shè)置專用路徑,1.,指令相關(guān),,發(fā)生指令相關(guān)的情況：,,,n,：,STORE R1,,n,+1,,n,+1,：,……,,,滿足關(guān)系： 結(jié)果地址,(,n),＝指令地址,(,n,+1),,當(dāng)?shù)?n,條指令還沒有把執(zhí)行結(jié)果寫到主存之前，取出的第,n,+1,條指令顯然是錯誤的。,,在,k,個流水段的流水線處理機中，第,n,條指令要修改從第,n+,1,到第,n+ k,指令中的任意一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤。,在采用先行控制方式的處理機中，如果執(zhí)行部件正在執(zhí)行第,n,條指令，與下述情況之一發(fā)生相關(guān)，都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤,:,,存放在先行操作棧中的指令,,正在指令分析器中分析的指令,,已經(jīng)預(yù)取到先行指令緩沖棧中的指令,,更嚴重的是：有些分支指令，可能已經(jīng)在指令分析器中執(zhí)行完成。,解決指令相關(guān)的根本辦法是：,,,在程序執(zhí)行過程中不允許修改指令。,,現(xiàn)代程序設(shè)計方法要求程序具有再入性，可以被遞歸調(diào)用等，也要求不修改指令。,,在,IBM370,系列機中，用,“,執(zhí)行,”,指令來解決：在程序執(zhí)行過程中既能夠修改指令，程序又具有再入性。,,,,,,,,,,,,,,,,,,“,執(zhí)行”指令執(zhí)行由第二地址,((X,2,)+(B,2,)+D,2,),決定的主存數(shù)據(jù)區(qū)中的指令。,2.,主存操作數(shù)相關(guān),(,相鄰兩條指令之間出現(xiàn)對主存同一單元要求先寫后讀的關(guān)聯(lián),),,發(fā)生主存操作數(shù)相關(guān)的指令序列：,,,n,：,OP A,1,，,A,2,，,A,3,,；,A,1,＝,(A,2,) OP (A,3,),,n+1,：,OP A,1,，,A,2,，,A,3,,；,A,1,＝,(A,2,) OP (A,3,),,出現(xiàn)下列情況之一，就發(fā)生主存操作數(shù)相關(guān)：,,,A,1,（,n,）＝,A,2,（,n,＋,1,）,,,A,1,（,n,）＝,A,3,（,n,＋,1,）,,解決辦法,(,出現(xiàn)概率低,,,不宜采用設(shè)置專用通路,),：,,對于訪問主存儲器的請求，寫結(jié)果的優(yōu)先級高于讀操作數(shù)，實現(xiàn)自動推后處理。,3.,通用寄存器數(shù)據(jù)相關(guān),,發(fā)生寄存器數(shù)據(jù)相關(guān)的可能性很大，影響面也很大,,,n,：,OP R,1,，,A,2,,；,R,1,＝,(R,1,) OP (A,2,),,n+1,：,OP R,1,，,R,2,,；,R,1,＝,(R,1,) OP (R,2,),,發(fā)生,R,1,(n),＝,R,1,(n,＋,1),稱為,R,1,數(shù)據(jù)相關(guān)。,,發(fā)生,R,1,(n),＝,R,2,(n,＋,1),稱為,R,2,數(shù)據(jù),相關(guān)。,,解決通用寄存器數(shù)據(jù)相關(guān)的方法：,,方法一：把讀操作數(shù)、寫運算結(jié)果與指令執(zhí)行合在一個節(jié)拍。,,采用一種典型的運算器結(jié)構(gòu)，通用寄存器到運算器之間建立有直接數(shù)據(jù)通路，即不設(shè)置緩沖寄存器或鎖存器。,,當(dāng)發(fā)生下述情況時，不能采用這種方法：,,當(dāng)寄存器個數(shù)多時，讀寫寄存器的時間長,,當(dāng)功能部件的執(zhí)行時間比較長，或要求指令的執(zhí)行時間短時,方法二：建立相關(guān)專用通路,(ByPass),,由于發(fā)生寄存器數(shù)據(jù)相關(guān)的情況很普遍，一般計算機系統(tǒng)都采用專用數(shù)據(jù)通路，以增加硬件為代價減少速度損失。,,在運算器的輸出端到鎖存器輸入端之間建立一條專用的數(shù)據(jù)通路。,變址相關(guān)：,在采用變址尋址方式的處理機中，由于變址量放在寄存器中，因此，可能發(fā)生與通用寄存器數(shù)據(jù)相關(guān)類似變址相關(guān)，發(fā)生概率較高，通常多采用設(shè)置專用通路的方法解決相關(guān)問題。,4. LOAD,相關(guān),,,LOAD,操作的執(zhí)行時間可能比較長,,,n,：,LOAD R,1,，,A,；,R,1,＝,(A),,n+1,：,ADD R,1,，,R,2,,；,R,1,＝,(R,1,) OP (R,2,),,,如果,R,1,(n),＝,R,2,(n,＋,1),，或,R,1,(n),＝,R,1,(n,＋,1),，,,則發(fā)生,LOAD,數(shù)據(jù)相關(guān)。,,解決方法：,方法一：,由編譯器在,LOAD,之后插入不發(fā)生數(shù)據(jù)相關(guān)的指令，,由于,LOAD,的執(zhí)行時間不確定，不能根本解決問題,,方法二：,由硬件自動插入空操作，直到,LOAD,操作完成,,在單條流水線處理機中，也可以停止節(jié)拍發(fā)生器，直到數(shù)據(jù)從存儲器中讀出為止。,控制相關(guān),(,全局相關(guān),),因程序的執(zhí)行方向可能被改變而引起的相關(guān)，也稱為,全局相關(guān),。,,主要包括：,無條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、復(fù)合條件轉(zhuǎn)移、中斷,等。,,1.,無條件轉(zhuǎn)移,,在流水線處理機中，無條件轉(zhuǎn)移指令不進入執(zhí)行流水段，一般在指令譯碼階段就實際執(zhí)行完成。,,如果在處理機中設(shè)置有指令先行緩沖棧，則要全部或部分作廢先行指令緩沖棧中的指令。,如果轉(zhuǎn)移目標指令,L,不在先行指令緩沖棧中,，則要將先行指令緩沖棧中的所有指令全部作廢，并等待取出轉(zhuǎn)移目標指令,L,。,,如果轉(zhuǎn)移目標指令,L,在先行指令緩沖棧中,，只要作廢先行指令緩沖棧中的部分指令。,,無條件轉(zhuǎn)移指令一般對指令執(zhí)行部件的工作不會造成影響。,,為進一步減少無條件轉(zhuǎn)移指令造成的影響，,在先行指令緩沖棧的入口處增設(shè)一個專門處理無條件轉(zhuǎn)移指令的指令分析器,2.,一般條件轉(zhuǎn)移,,,k,：,……,;,置條件碼,CC,,k+1,：,JMP(CC) L ;,如果,CC,為真轉(zhuǎn)向,L,,,……,,L,：,……,,,當(dāng)條件碼是上一條指令產(chǎn)生時，相關(guān)最嚴重,無論轉(zhuǎn)移是否成功，條轉(zhuǎn)移指令都在指令分析階段就已經(jīng)執(zhí)行完成。,,無論轉(zhuǎn)移不成功或不成功，指令分析器要停頓一段時間，等待條件碼產(chǎn)生。,如果轉(zhuǎn)移成功：指令,L,已經(jīng)在先行指令緩沖棧，指令分析器接著,“,分析,L,”,，如果指令,L,不在先行指令緩沖棧，指令分析器要等待一個周期。,,轉(zhuǎn)移不成功，對程序執(zhí)行影響不大，,,當(dāng)轉(zhuǎn)移成功時，不僅指令執(zhí)行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。,,在采用流水線方式的處理機中，要通過軟件與硬件的多種手段來近可能地降低轉(zhuǎn)移成功的概率，減少轉(zhuǎn)移成功造成的影響。,3.,復(fù)合條件轉(zhuǎn)移,,,k,：,OP L ;,產(chǎn)生條件碼，并決定是否轉(zhuǎn)向,L,,,……,,L,：,……,,如果轉(zhuǎn)移不成功：不造成任何影響，就象普通的運算型指令一樣,,如果轉(zhuǎn)移成功：造成的影響比一般條件轉(zhuǎn)移指令還要大得多。,全部或部分作廢先行指令緩沖棧、先行操作棧、先行讀數(shù)棧和指令分析器中的指令。,,必須采取策略，減小轉(zhuǎn)移成功造成的影響。,條件分支對流水線的影響,處理好條件轉(zhuǎn)移和中斷的關(guān)鍵問題有兩個：,,要確保流水線能夠正常工作,,減少因,“,斷流,”,引起的吞吐率和效率的下降,,1.,條件分支的處理方法,,條件轉(zhuǎn)移指令對流水線的影響很大，必須采取措施來減少這種影響。可能的措施有：,,(1),延遲轉(zhuǎn)移技術(shù)和指令取消技術(shù),,只能用于單流水線處理機中，且流水線的級數(shù)不能太多；,據(jù)統(tǒng)計，,編譯器調(diào)度一條指令成功的概率在,90,％以上，而調(diào)度兩條指令成功的概率只有,40,％左右。,,當(dāng)沒有合適的指令可調(diào)度時，編譯器只能插入空操作。,,(2),動態(tài)分支預(yù)測技術(shù),,根據(jù)近期轉(zhuǎn)移是否成功的記錄來預(yù)測下一次轉(zhuǎn)移的方向。,,所有的動態(tài)轉(zhuǎn)移預(yù)測方法都能夠隨程序的執(zhí)行過程動態(tài)地改變轉(zhuǎn)移的預(yù)測方向。,(3),靜態(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ù)取指令。,,TI,公司的,SuperSPARC,處理機采用了靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)，而且設(shè)置有轉(zhuǎn)移目標緩沖棧，在兩個方向上都預(yù)取指令。,2.,條件分支在流水線中的執(zhí)行過程,,因為第,i,條指令所需要的條件碼由第,i-1,條指令給出；在一條由,k,個功能段的流水線中，第,i-1,條指令要等到第,i+k-2,條指令進入流水線時才能形成條件碼。,,轉(zhuǎn)移不成功，猜測正確，流水線的吞吐率和效率沒有降低，,,轉(zhuǎn)移成功，猜測錯誤，要先作廢流水線中已經(jīng)執(zhí)行的,i+1,、,i+2,、,……,、,i+k-2,指令；然后再從分支點開始執(zhí)行第,P,、,p+1,、,……,指令。,,條件分支指令在流水線中的執(zhí)行過程,當(dāng)分支的執(zhí)行方向猜測錯誤時，可能造成程序執(zhí)行結(jié)果發(fā)生錯誤。,,例如，若第,i+1,條指令是：,(R1,＋,(R2)→R1,，,寄存器,R1,中內(nèi)容就被破壞，整個程序執(zhí)行的結(jié)果是錯誤的。,,目前的處理機有兩種做法：,,一種方法是只進行指令譯碼和準備好運算所需要的操作數(shù)，在轉(zhuǎn)移條件沒有形成之前不執(zhí)行運算；,,另一種方法是一直執(zhí)行到運算完成，但不送回運算結(jié)果。,靜態(tài)分支預(yù)測技術(shù),靜態(tài)分支預(yù)測：,,在程序執(zhí)行過程中轉(zhuǎn)移預(yù)測方向不能改變,,動態(tài)分支預(yù)測：,,在程序執(zhí)行過程中能夠改變轉(zhuǎn)移預(yù)測方向,,本節(jié)講靜態(tài)預(yù)測技術(shù),,1.,軟件,“,猜測法,”,,目標：,通過編譯器盡量降低轉(zhuǎn)移成功的概率。,,例如：對于循環(huán)程序，普通編譯器生成的目標代碼，轉(zhuǎn)移成功的概率很高，不成功的只有一次。這種編譯結(jié)果對流水線極為不利。,,,軟件,“,猜測法,”,：,,,通過編譯器降低轉(zhuǎn)移成功的概率,2.,硬件,“,猜測法,”,,方法：,通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對流水線的影響,,在先行指令緩沖棧的人口處設(shè)置一個簡單的指令分析器，當(dāng)檢測到轉(zhuǎn)移指令時，就把轉(zhuǎn)移目標地址,L,送入先行程序計數(shù)器,PC,1,中，同時保留當(dāng)前,PC,1,中的內(nèi)容到另一寄存器中。,,轉(zhuǎn)移成功，猜測正確。對轉(zhuǎn)移指令對流水線不造成影響。,,轉(zhuǎn)移不成功，用保存下來的地址恢復(fù),PC,1,和,PC,。,,軟硬件共同配合，都往同一個方向去猜測。,3.,兩個先行指令緩沖棧,,向前條件轉(zhuǎn)移，轉(zhuǎn)移成功與不成功各,50%,,在先行指令緩沖棧中,增加一個先行目標緩沖棧,,按照轉(zhuǎn)移成功的方向預(yù)取指令到先行目標緩沖棧中。,,先行指令緩沖棧仍然按照轉(zhuǎn)移不成功的方向繼續(xù)預(yù)取指令。,,如果轉(zhuǎn)移不成功，則繼續(xù)分析原來先行指令緩沖棧中指令。,,如果轉(zhuǎn)移成功，則分析新增設(shè)的先行目標緩沖棧中的指令。,提前形成條件碼,必要性：對提高流水線的性能非常有效,,可能性：,可在運算開始或中間產(chǎn)生條件碼,,對于乘除法，兩個源操作數(shù)的符號相同結(jié)果為正，符號相反結(jié)果為負,,對于乘法，有一個操作數(shù)為,0,，則乘積為,0,,被除數(shù)為,0,，商為,0,； 除數(shù)為,0,，除法結(jié)果溢出,,同號加或異號減，結(jié)果符號與第一操作數(shù)相同,,異號加或同號減，結(jié)果的符號與絕對值大的操作數(shù)相同,,溢出及是否為,0,可以通過一個比較器提前產(chǎn)生,精確斷點與不精確斷點,對于輸入輸出設(shè)備的中斷服務(wù)，實際上不需要有精確斷點。,,比較簡單的處理方法是：讓已經(jīng)進入流水線的所有指令都執(zhí)行完成，斷點就是最后進入流水線的那條指令的地址。,,對于程序性錯誤和機器故障等引起的中斷，它們出現(xiàn)的概率很低，處理原則：,不在于縮短時間，關(guān)鍵是要正確保存現(xiàn)場和正確恢復(fù)斷點。,不精確斷點,(Imprecise),，,流水線可以不斷流,,需要的硬件比較少，控制邏輯比較簡單,,中斷響應(yīng)時間加長,,,采用不精確斷點法可能會發(fā)生如下兩個問題：,,(1),程序的調(diào)試困難,,早期的流水線處理機，多采用不精確斷點法,,近期的流水線處理機一般都采用精確斷點法,(2),程序執(zhí)行的結(jié)果可能出錯，例如：,,,i,：,FADD R1, R2,；,(R1),＋,(R2)→R1,,i+1,：,FMUL R3, R1,；,(R3)×(R1)→R3,,當(dāng)?shù)?i,條指令執(zhí)行到,S,6,段時發(fā)現(xiàn)浮點加法結(jié)果溢出，于是發(fā)出中斷服務(wù)申請。由于采用不精確斷點法，已經(jīng)進入流水線的第,i+1,條指令將執(zhí)行完成；因為第,i+1,條指令使用了不正確的,R1,，所以浮點乘法的執(zhí)行結(jié)果是不正確的。,,采用精確斷,(Precise),點法，要設(shè)置一定數(shù)量的后援寄存器,，把整個流水線中所有指令的執(zhí)行結(jié)果和現(xiàn)場都保存下來。,動態(tài)調(diào)度技術(shù),實現(xiàn)方法：,,由硬件動態(tài)調(diào)整指令執(zhí)行順序，以減少數(shù)據(jù)相關(guān)造成的影響。,,主要優(yōu)點：,,能夠處理在編譯時無法確定的相關(guān)，并簡化編譯器設(shè)計,,在其他流水線機器上編譯的目標代碼也能夠高效運行,,用靜態(tài)調(diào)度法生成的代碼也能在動態(tài)調(diào)度法的機器中運行,,主要缺點：,指令級并行度低，因為只能在比較小的范圍內(nèi)尋找并行性,順序流動與亂序流動,1.,順序流動方式：,任務(wù)按順序流入流水線,,,也按順序流出流水線,,把如下一段程序輸入到這條流水線中：,,,k,：,R0←,（,R1,）,,,k+1,：,……,,k+2,：,R2←,（,R0,）＋（,R3,）,,,k+3,：,……,,k+4,：,……,,k+5,：,……,指令,k+2,無法繼續(xù)執(zhí)行，要在功能段,S,2,中等待。,,后續(xù)的指令,k+4,、,k+5,、,……,等也不能進入流水線。,,功能段,S,3,、,S,4,、,S,5,將逐漸空閑。,,缺點：,吞吐率和效率降低,,優(yōu)點：,流水線的控制邏輯比較簡單,流水線,“,斷流,”,，有些功能段,“,空閑,”,2.,亂序,(Out of order),流動方式：,指令流出流水線的順序與流入流水線的順序不同。,又稱為,錯序流動方式、無序流動方式、異步流動方式等。,亂序流動中的數(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)等。,,(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,與指令,k+2,左邊的,F1,之間的相關(guān)關(guān)系稱為：輸出相關(guān)、寫寫相關(guān)、,WW,相關(guān)、,WAW,相關(guān)或?qū)懞笤賹懴嚓P(guān)等。,,有時把,相關(guān),稱為,“,冒險,”,(hazard),、,“,竟爭,”,,(competition),等。,,在程序執(zhí)行過程中，只有避免相關(guān)，執(zhí)行結(jié)果才是正確的。,,三種數(shù)據(jù)相關(guān)可以用下列關(guān)系式來表示：,,對于寫讀相關(guān),D(i) ∩ S(j) ≠,?,,,對于讀寫相關(guān),S(i) ∩ D(j) ≠,?,,,對于寫寫相關(guān),D(i) ∩ D(j) ≠,?,數(shù)據(jù)重定向方法,1.,三種數(shù)據(jù)相關(guān)的重定向,,重定向之前，,j,只能在,i,之后執(zhí)行。,,重定向之后，可以做到：,,(1),寫讀相關(guān)，,j,與,i,可以同時執(zhí)行,,即專用數(shù)據(jù)通路,,(2),寫寫相關(guān)，,先后順序無關(guān),,(3),讀寫相關(guān)，,先后順序無關(guān),,后兩種情況又稱為,“,變量換名技術(shù),”,2.,變量換名技術(shù),,用來自動消除,讀寫數(shù)據(jù)相關(guān),和,寫寫數(shù)據(jù)相關(guān),,規(guī)則：,一個變量只允許定值一次,,在三種數(shù)據(jù)相關(guān)中，實際上只有寫讀數(shù)據(jù)相關(guān)必須依靠硬件、或采用軟硬件結(jié)合的方法來解決,,解決方法：,推后處理,或,專用數(shù)據(jù)通路,,在上面的數(shù)據(jù)重定向圖中，把,B,換成了,B’,，并在以后的都引用,B’,讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就不存在了。,三種主流處理機,(,指令級高度并行的超級處理機,),：,,,超標量處理機,,超流水線處理機,,超標量超流水線處理機,基本結(jié)構(gòu),普通標量流水線處理機：,,,一條指令流水線,，一個多功能操作部件，,,每個時鐘周期平均執(zhí)行指令的條數(shù)小于,1,。,,多操作部件標量處理機：,,,一條指令流水線,，多個獨立的操作部件，,,,指令級并行度小于,1,。,,超標量處理機典型結(jié)構(gòu)：,,多條并行工作的指令流水線,，,多個獨立的操作部件，,,,指令級并行度（,ILP,）大于,1,。,,Motorola,公司的,MC88110,,有,10,個操作部件,,兩個寄存器堆：,,整數(shù)部件通用寄存器堆，,32,個,32,位寄存器,,浮點部件擴展寄存器堆，,32,個,80,位寄存器,,緩沖深度為,4,的先行讀數(shù)棧,,緩沖深度為,3,的后行寫數(shù)棧,,兩個獨立的高速,Cache,中，各為,8KB,，采用兩路組相聯(lián)方式,,轉(zhuǎn)移目標指令,Cache,，用于存放另一條分支上的指令,單發(fā)射與多發(fā)射,1.,單發(fā)射處理機,(,普通流水線標量處理機,),：,,每個周期只取一條指令、只譯碼一條指令，只執(zhí)行一條指令，只寫回一個運算結(jié)果。,,取指令部件和指令譯碼部件各設(shè)置一套；,,只設(shè)置一個多功能操作部件或設(shè)置多個獨立的操作部件；,,操作部件中可以采用流水線結(jié)構(gòu)，也可以不采用流水線結(jié)構(gòu)。,,目標是每個時鐘周期平均執(zhí)行一條指令，,ILP,的期望值為,1,。,2.,多發(fā)射處理機：,,每個周期同時取多條指令、同時譯碼多條指令，同時執(zhí)行多條指令，同時寫回多個運算結(jié)果。,,多個取指令部件，多個指令譯碼部件和多個寫結(jié)果部件。,,設(shè)置多個指令執(zhí)行部件，有些指令執(zhí)行部件采用流水線結(jié)構(gòu)。,,目標是每個時鐘周期平均執(zhí)行多條指令，,ILP,的期望值大于,1,。,3.,超標量處理機,(,一個時鐘周期內(nèi)同時發(fā)射多條指令的處理機,),：,,有兩條或兩條以上能同時工作的指令流水線。,,先行指令窗口,：能夠從指令,Cache,中預(yù)取多條指令，能夠?qū)Υ翱趦?nèi)的指令進行數(shù)據(jù)相關(guān)性分析和功能部件沖突檢測，提高功能部件利用率，一般取,2-8,條指令。,,由于程序中指令并行性的開發(fā)有限，所以度,m,比較低，理論上最佳,m=3,。,,,超標量處理機的指令級并行度：,1,＜,ILP,＜,m,。,,,超標量處理機非常適合于求解像稀疏向量或矩陣這類標量計算問題。,多流水線調(diào)度,順序發(fā)射,(in-order issue),與亂序發(fā)射,(out-order issue),：,指令發(fā)射順序是按照程序中指令排列順序進行的稱為順序發(fā)射,,順序完成,(in-order completion),與亂序完成,(out-order completion),：,指令完成順序是按照程序中指令排列順序進行的稱為順序完成,,多流水線的調(diào)度主要有三種方法：,,順序發(fā)射順序完成,,順序發(fā)射亂序完成,,亂序發(fā)射亂序完成,以如下,6,條指令組成的程序為例，說明這三種調(diào)度方法（,m=2,）,,,I,1,：,LOAD R1, A,；,R1←(A),,I,2,：,FADD R2, R1,；,R2←(R2),＋,(R1),,I,3,：,FMUL R3, R4,；,R3←(R3)×(R4),,I,4,：,FADD R4, R5,；,R4←(R4),＋,(R5),,I,5,：,DEC R6,；,R6←(R6),－,1,,I,6,：,FMUL R6, R7,；,R6←(R6)×(R7),,6,條指令中有,4,個數(shù)據(jù)相關(guān)，包括,2,個寫讀相關(guān)，,1,個讀寫相關(guān)和,1,個寫寫相關(guān)。,,1.,順序發(fā)射順序完成,,共用,10,個時鐘周期完成,,還有,8,個空閑的時鐘周期,2.,順序發(fā)射亂序完成,,總的執(zhí)行時間為,9,個時鐘周期，,,,節(jié)省了一個時鐘周期。少了,5,個空閑時鐘周期。,3.,亂序發(fā)射亂序完成（采用先行指令窗口，度,m=3,）,沒有空閑周期，功能部件得到充分利用。,,總的執(zhí)行時間為,8,個周期，節(jié)省,2,個周期。,資源沖突,如果操作部件采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性很小；,,如果不采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性就比較大。,,下面是一個由,4,條指令的程序例子：,,,I1,：,FADD R0, R1,；,R0←(R0),＋,(R1),,I2,：,FMUL R2, R3,；,R2←(R2)×(R3),,I3,：,FADD R4, R5,；,R4←(R4),＋,(R5),,I4,：,FMUL R6, R7,；,R6←(R6)×(R7),操作部件不采用流水線：,,,做完,4,條指令總共用了,11,個周期，,,有,5,個空閑周期,。,操作部件采用流水線：,,做完,4,條指令共用,8,個周期，,,少用,3,個周期。,操作部件采用流水線結(jié)構(gòu)的原因分析,,假設(shè)每個周期發(fā)射,m,條指令，操作部件的延遲時間為,k,個周期，,,如果操作部件不采用流水線結(jié)構(gòu)，則使用同一個操作部件的兩條指令序號應(yīng)該,至少相差,m×k,,如果操作部件采用,k,段流水線結(jié)構(gòu)，則使用同一個操作部件的兩條指令,只需相差,m,或,m,以上,,操作部件的延遲時間,k,一般在,4,至,10,之間，每個時鐘周期發(fā)射的指令條數(shù),m,在,2,至,4,之間。取中間值，,k,＝,7,，,m,＝,3,為了不發(fā)生資源沖突，如果操作部件不采用流水線結(jié)構(gòu)，,,,兩條使用同一個功能部件的指令序號必須相差,21,或,21,以上。,,如果操作部件采用流水線結(jié)構(gòu)，,,,兩條使用同一個功能部件的指令序號只需要相差,3,或,3,以上。,,因此，在超標量處理機中，操作部件一般要采用流水線結(jié)構(gòu)。,,如果由于某種原因，操作部件不能采用流水線結(jié)構(gòu)，則必須設(shè)置多個相同種類的操作部件,普通標量處理機，希望相同操作連續(xù)出現(xiàn)。,,只有連續(xù)出現(xiàn)相同操作的指令序列時，流水線的效率才能得到充分發(fā)揮。,,超標量處理機,則正好相反，,希望相同操作不要連續(xù)出現(xiàn),。,,相同操作的指令序列連續(xù)出現(xiàn)時，會發(fā)生資源沖突；,,要求相同操作的指令能夠相對均勻地分布在程序中。,,超標量處理機的這種要求正好符合一般標量程序的特點,。,超標量處理機性能,單流水線普通標量處理機的指令級并行度記作,(1, 1),，,,超標量處理機的指令級并行度記作,(m, 1),，,,超流水線處理機的指令級并行度記作,(1, n),，,,而超標量超流水線處理機的指令級并行度記作,(m, n),。,,在理想情況下，,N,條指令在單流水線標量處理機上的執(zhí)行時間為：,,,T(1, 1),＝,(k,＋,N,－,1),?,t,在每個周期發(fā)射,m,條指令的超標量處理機上執(zhí)行的時間為：,,,,,,超標量處理機相對于單流水線標量處理機的加速比為：,,,,,超標量處理機的加速比的最大值為：,S,(,m,,1),MAX,＝,m,超流水線處理機的兩種定義：,,在一個基本時鐘周期內(nèi)分時發(fā)射多條指令的處理機,,指令流水線的段數(shù)大于等于,8,的流水線處理機（深度流,,水）,,提高處理機性能的兩種方法：,,通過增加硬件資源來提高處理機性能（空間并行性）,,通過各部分硬件的重疊工作來提高處理機性能（時間并,,行性）,,兩種不同并行性：,,超標量處理機采用的是空間并行性。,,超流水線處理機采用的是時間并行性。,指令執(zhí)行時序,每隔,1/n,個時鐘周期發(fā)射一條指令,，,,即處理機的流水線周期為,1/n,個時鐘周期。,典型處理機結(jié)構(gòu),MIPS R4000,處理機：,,每個時鐘周期包含兩個流水段,,是一種很標準的超流水線處理機結(jié)構(gòu)。,,指令流水線有,8,個流水段。,,指令,Cache,和數(shù)據(jù),Cache,的容量各,8KB,，,,每個時鐘周期可以訪問,Cache,兩次，,,在一個時鐘周期內(nèi)可以從指令,Cache,中讀出兩條指令，從數(shù)據(jù),Cache,中讀出或?qū)懭雰蓚€數(shù)據(jù)。,,主要運算部件有整數(shù)部件和浮點部件。,,如果在,LOAD,指令之后的兩條指令中，任何一條指令要在它的,EX,流水級使用這個數(shù)據(jù)，則指令流水線要暫停一個時鐘周期。,超流水線處理機性能,指令級并行度為,(1,n),的超流水線處理機，執(zhí)行,N,條指令所的時間為：,,,,超流水線處理機相對于單流水線普通標量處理機的加速比為：,,,,,,,加速比的最大值為：,S(1, n),MAX,＝,n,超標量超流水線處理機,,一個時鐘周期發(fā)射,n,次，每次發(fā)射,m,條指令，每個時鐘周期共發(fā)射指令,mn,條。同時開發(fā)空間并行性和時間并行性,,,指令執(zhí)行時序,典型處理機結(jié)構(gòu),DEC,公司的,Alpha,處理機為典型的,超標量超流水線結(jié)構(gòu),。,,主要由四個功能部件和兩個,Cache,組成：整數(shù)部件,EBOX,,,浮點部件,FBOX,,,地址部件,ABOX,,,中央控制部件,IBOX,,,指令,Cache,和數(shù)據(jù),Cache,,在,EBOX,內(nèi)還有多條專用數(shù)據(jù)通路，可以把運算結(jié)果直接送到執(zhí)行部件。,中央控制部件,IBOX,能夠同時完成：,,同時讀出兩條指令；,,同時對兩條指令進行譯碼，并作相關(guān)性檢測；,,如果資源和相關(guān)性允許，,IBOX,就把兩條指令同時發(fā)射給,EBOX,、,ABOX,和,FBOX,三個執(zhí)行部件中的兩個。,,指令流水線的控制方式：,,采用,順序發(fā)射亂序完成,。,,在指令,Cache,中有一個轉(zhuǎn)移歷史表，實現(xiàn)條件轉(zhuǎn)移的動態(tài)預(yù)測。,Alpha 21064,處理機共有,三條指令流水線：,,(1),整數(shù)操作流水線為,7,個流水段,，其中，取指令,2,個流水段、分析指令,2,個流水段、運算,2,個流水段、寫結(jié)果,1,個流水段。,,(2),訪問存儲器流水線為,7,個流水段,。,,(3),浮點操作流水線分為,10,個流水段,，其中，浮點執(zhí)行部件,FBOX,的延遲時間為,6,個流水段。,,三條指令流水線的平均段數(shù)為,(7+7+10)/3=8,，且每個時鐘周期發(fā)射兩條指令。因此，,Alpha 21064,處理機為超標量超流水線處理機。,超標量超流水線處理機的性能,指令級并行度為,(m,n),的超標量超流水線處理機，連續(xù)執(zhí)行,N,條指令所需要的時間為：,,,,超標量超流水線處理機相對于單流水線標量處理機的加速比為：,,,,在理想情況下，超標量超流水線處理機加速比的最大值為：,,S,(m,n),MAX,＝,m n,三種標量處理機的性能比較,,從三種標量處理機的性能曲線中，可以得出如下結(jié)論：,,1.,三種處理機的性能關(guān)系,,超標量處理機的相對性能最高，其次是超標量超流水線處理機，超流水線處理機的相對性能最低，,主要原因如下：,,(1),超標量處理機功能部件的沖突比超流水線處理機小。在指令執(zhí)行過程中的許多功能段，超標量處理機都重復(fù)設(shè)置有多個相同的指令執(zhí)行部件，而超流水線處理機只是把同一個指令執(zhí)行部件分解為多個流水級。,(2),條件轉(zhuǎn)移等操作造成的損失，超流水線處理機要比超標量處理機大。,,由于超流水線處理機采用深度流水線結(jié)構(gòu)，對條件轉(zhuǎn)移等操作比超標量處理機敏感。,,(3),超流水線處理機的啟動延遲通常要比超標量處理機大。,,超標量處理機在每個時鐘周期的一開始就同時發(fā)射多條指令，,,超流水線處理機把一個時鐘周期平均分成多個流水線周期，每個流水線周期只發(fā)射一條指令。,2.,實際指令級并行度與理論指令級并行度的關(guān)系,,當(dāng)橫坐標給出的理論指令級并行度比較低時，處理機的實際指令級并行度的提高比較快。,,當(dāng)理論指令級并行度進一步增加時，處理機實際指令級并行度提高的速度越來越慢。,,在實際設(shè)計超標量、超流水線、超標量超流水線處理機的指令級并行度時要適當(dāng)，否則，有可能造成花費了大量的硬件，但實際上處理機所能達到的指令級并行度并不高。,,目前，一般認為，,m,和,n,都不要超過,4,。,3.,最大指令級并行度,,一個特定程序由于受到本身的數(shù)據(jù)相關(guān)和控制相關(guān)的限制，它的指令級并行度的最大值是有限的，是有個確定的值。,,最大指令級并行度由程序自身的語義決定，與這個程序運行在那一種處理機上及采用何種方法開發(fā)并行性無關(guān)。,,對于某一個特定的程序，圖中的三條曲線最終都要收攏到同一個點上。,,對于各個不同程序，這個收攏點的位置也是不同的。,具有向量數(shù)據(jù)表示和向量指令系統(tǒng)的處理機,,向量處理機是解決數(shù)值計算問題的一種高性能計算機,,向量處理機屬,大型或巨型機,，也可以用微機加一臺,向量協(xié)處理器,組成,,向量處理機一般都采用流水線結(jié)構(gòu)，,通常有有多條并行工作的流水線,,必須把要解決的問題轉(zhuǎn)化為向量運算，才能發(fā)揮向量處理機的效率,向量處理,例：一個簡單的,C,語言程序如下：,for (i = 10; i <= 1010; i++) c[i] = a[i] + b[i] ;,,在向量處理機上,,,可以只用一條指令：,C(10:1010)=A(10:1010) + B(10:1010),一條向量指令可處理Ｎ個或Ｎ對操作數(shù),,在標量處理機上用,10,多條指令，其中有,8,條指令要循環(huán),1000,次。,,采用多寄存器結(jié)構(gòu)的兩地址指令編寫程序,,存儲器采用字節(jié)編址方式，字長為,32,位,從標量到向量,在一般標量處理機中需要如下指令序列來實現(xiàn)（,A,、,B,、,C,分別是向量,a,、,b,、,c,在內(nèi)存中的起始地址）：,START: LOAD R0, ST ;,讀循環(huán)初值,10,,,LOAD R1, ED ;,讀循環(huán)終值,1010,,,LOAD R2, L ;,讀內(nèi)存地址增量,4,,,MOVE R3, R2,,MUL R3, R0 ;,計算向量偏移量,,,,;,初始值為,40,,LOOP: LOAD R4,A(R3) ;,讀,A,向量的一個元素,LOAD R5, B(R3) ;,讀,B,向量的一個元素,,,ADD R4, R5 ;,加一個元素,,,STORE R4, C(R3) ;,寫,C,向量的一個元素,,,ADD R3, R2