《并行計(jì)算機(jī)體系結(jié)構(gòu)第三章》由會員分享，可在線閱讀，更多相關(guān)《并行計(jì)算機(jī)體系結(jié)構(gòu)第三章（215頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,,,,,單擊此處編輯母版標(biāo)題樣式,,單擊

2、此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,第三章 流水和向量處理,,3.1,提高計(jì)算機(jī)速度的措施,MIPS=IPC*f,c,,其中,IPC,為每拍流出的指令條數(shù)。提高,IPC,和,f,c,是提高計(jì)算機(jī)速度最直接最有效的方法。,,提高,IPC,：增加每拍并行流出的指令條數(shù)和配置更多的功能部件?？臻g并行。,,提高,f,c,：功能部件應(yīng)該能在更高的頻率下工作。時(shí)間平行。,,可以用,P=O,（,s*f,）衡量系統(tǒng)的潛在性能，,s,是與設(shè)備量成正比的功能部件并行度，,f,是主頻。,3.1.1,提高頻率,提高系統(tǒng)的頻率是提高系統(tǒng)性能的最直接的方法，但是頻率的提高具有很大的難度

3、：,,1.,器件的速度和集成度,,2.,流水線分站的代價(jià)和效率,,3.,高速信號傳輸,,4.,時(shí)鐘沿的離散,,5.,高密度組裝工藝和冷卻技術(shù),,**往往當(dāng)通過提高頻率來提高計(jì)算機(jī)的速度不能滿足要求時(shí)，我們才考慮空間并行性,3.1.1,空間并行,為了達(dá)到更高的主頻，需要特殊技術(shù)并且代價(jià)巨大。這導(dǎo)致了大規(guī)模并行處理系統(tǒng),MPP,的出現(xiàn)。,,可以設(shè)置多個(gè)功能部件支持向量、超標(biāo)量、超長指令字和超流水結(jié)構(gòu)?？臻g并行性可以有效提高計(jì)算機(jī)速度，速度提高的最大倍數(shù),<=,部件設(shè)備量增加的倍數(shù)。,,上述不等式的原因主要是有存儲和外設(shè)限制造成的，為了提高速度往往需要高帶寬存儲系統(tǒng)的支持和高效的,I/O,能力，我們

4、將在后面的章節(jié)討論存儲系統(tǒng)和,I/O,系統(tǒng)。,,當(dāng)然在,MPP,中各個(gè)結(jié)點(diǎn)相聯(lián)還需要不同的互聯(lián)網(wǎng)絡(luò)的支持。,先行控制技術(shù),—,補(bǔ)充,1.,順序執(zhí)行方式,,執(zhí)行,n,條指令所用的時(shí)間為：,,,,如果每段時(shí)間都為,t,，則執(zhí)行,n,條指令所用的時(shí)間為：,T,＝,3 n t,,,主要優(yōu)點(diǎn)：,控制簡單，節(jié)省設(shè)備,,主要缺點(diǎn)：,速度慢，功能部件的利用率低,2.,一次重疊執(zhí)行方式,,如果兩個(gè)過程的時(shí)間相等，則執(zhí)行,n,條指令的時(shí)間為：,T,＝,(,1+2n)t,,,,,主要優(yōu)點(diǎn)：,,,指令的執(zhí)行時(shí)間縮短，,,功能部件的利用率明顯提高。,,主要缺點(diǎn)：,,,需要增加一些硬件，,,控制過程稍復(fù)雜。,3.,二次重

5、疊執(zhí)行方式,,如果三個(gè)過程的時(shí)間相等，執(zhí)行,n,條指令的時(shí)間為：,T,＝,(,2,＋,n,）,t,,在理想情況下，處理機(jī)中同時(shí)有三條指令在執(zhí)行。,,處理機(jī)的結(jié)構(gòu)要作比較大的改變，需要采用先行控制技術(shù)。,,先行控制方式的原理,1.,采用二次重疊執(zhí)行方式必須解決兩個(gè)問題：,,(1),有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件,,把一個(gè)集中的指令控制器，分解成三個(gè)獨(dú)立的控制器：,,存儲控制器、指令控制器、運(yùn)算控制器,,(2),要解決訪問主存儲器的沖突問題,,取指令、分析指令、執(zhí)行指令都可能要訪問存儲器,,2.,解決訪存沖突的方法：,,(1),采用低位交叉存取方式：,,這種方法不能根本解決沖突問題

6、。,,讀指令、讀操作數(shù)、寫結(jié)果。,,(2),兩個(gè)獨(dú)立的存儲器：,獨(dú)立的指令存儲器和數(shù)據(jù)存儲器。,,如果再規(guī)定，執(zhí)行指令的執(zhí)行結(jié)果只寫到通用寄存器，則取指令、分析指令和執(zhí)行指令就可以同時(shí)進(jìn)行。,,在許多高性能處理機(jī)中，有獨(dú)立的指令,Cache,和數(shù)據(jù),Cache,。這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)。,(3),采用先行控制技術(shù),,采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。,,緩沖技術(shù)通常用在工作速度不固定的兩個(gè)功能部件之間。設(shè)置緩沖棧的目的是用以平滑功能部件之間的工作速度。,,在采用了緩沖技術(shù)和預(yù)處理技術(shù)之后，運(yùn)算器能夠?qū)Ｐ挠跀?shù)據(jù)的運(yùn)算，從而大幅度提高程序的執(zhí)行速度。,先行處理機(jī)結(jié)構(gòu),1.,三個(gè)獨(dú)立的控

7、制器：,,存儲控制器、指令控制器、運(yùn)算控制器。,,2.,四個(gè)緩沖棧：,,先行指令緩沖棧、先行讀數(shù)緩沖棧、先行操作棧、后行寫數(shù)棧。,,3.,處理機(jī)組成,4.,先行指令緩沖棧的組成,,作用：,只要指令緩沖棧沒有充滿，就自動發(fā)出取指令的請求。,,設(shè)置兩個(gè)程序計(jì)數(shù)器：,,先行程序計(jì)數(shù)器,PC,1,，用來指示取指令，,,現(xiàn)行程序計(jì)數(shù)器,PC,，記錄指令分析器正在分析的指令地址。,,5.,存在的主要問題：,,各類指令,“,分析,”,和,“,執(zhí)行,”,的時(shí)間相差很大,,數(shù)據(jù)相關(guān),,轉(zhuǎn)移或轉(zhuǎn)子程序指令,,先行指令緩沖棧的組成,指令執(zhí)行時(shí)序,設(shè)置了指令緩沖棧，取指令的時(shí)間就可以忽略不計(jì)。,,一條指令的執(zhí)行可分為

8、,2,個(gè)過程,,1.,分析指令和執(zhí)行指令時(shí)間不相等時(shí)的情況,采用先行緩沖棧的指令執(zhí)行過程,,先行讀數(shù)棧,,,先行操作棧,,,后行寫數(shù)棧。,,,,,,,理想情況下，指令執(zhí)行部件應(yīng)該一直忙碌。,,連續(xù)執(zhí)行,n,條指令的時(shí)間為：,先行緩沖棧,設(shè)置先行緩沖棧的目的：,使指令分析器和指令執(zhí)行部件能夠獨(dú)立工作。,,1.,先行指令緩沖棧：,,處于主存儲器與指令分析器之間,,用它來平滑主存儲器取指令和指令分析器使用指令之間的速度差異,,RR,型指令,，不必處理，直接送先行緩沖棧,,RS,型指令,，主存有效地址送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的主存地址碼部分，形成,RR*,指令送先行緩沖棧,R

9、I,型指令,，指令中的立即數(shù)送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的立即數(shù)部分，形成,RR*,指令送先行緩沖棧,,轉(zhuǎn)移指令,，一般在指令分析器中直接執(zhí)行。,,先行操作棧,,處于指令分析器和運(yùn)算控制器之間,,使指令分析器和運(yùn)算器能夠各自獨(dú)立工作。,,采用先進(jìn)先出方式工作，由指令寄存器堆和控制邏輯組成。,先行讀數(shù)棧,,處于主存儲器與運(yùn)算器之間,,平滑運(yùn)算器與主存儲器的工作,,每個(gè)緩沖寄存器由地址寄存器、操作數(shù)寄存器和標(biāo)志三部分組成。也可以把地址寄存器和操作數(shù)寄存器合為一個(gè)。,,當(dāng)收到從指令分析器中送來的有效地址時(shí)，就向主存申請讀操作數(shù)。,,讀出的操作數(shù)存放在操作數(shù)寄存器中或覆蓋掉地址寄

10、存器中的地址。,后行寫數(shù)棧,,每個(gè)后行緩沖寄存器由地址寄存器、數(shù)據(jù)寄存器和標(biāo)志三部分組成。,,指令分析器遇到向主存寫結(jié)果的指令時(shí)，把形成的有效地址送入后行寫數(shù)棧的地址寄存器中，并用該地址寄存器的編號替換指令的目的地址部分，形成,RR*,指令送入先行操作棧。,,當(dāng)運(yùn)算器執(zhí)行這條,RR*,型寫數(shù)指令時(shí)，,,只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可。,采用先行控制方式時(shí)一個(gè)程序的執(zhí)行情況：,緩沖深度的設(shè)計(jì)方法,以靜態(tài)分析為主，通過模擬來確定緩沖深度。,,1.,先行指令緩沖棧的設(shè)計(jì),,考慮兩種極端情況：假設(shè)緩沖深度為,D,I,,(1),先行指令緩沖棧已經(jīng)充滿,,指令流出的速度最快，例如連續(xù)

11、分析,RR,型指令，設(shè)這種指令序列的最大長度為,L,1,，平均分析一條這種指令的時(shí)間為,t,1,；,,指令流入的速度最慢，設(shè)平均取一條指令的時(shí)間為,t,2,。從主存儲器中取到先行指令緩沖棧中的指令條數(shù)是,L,1,－,D,I,條。,應(yīng)該滿足如下關(guān)系：,L,1,,t,1,＝,(,L,I,－,D,I,),t,2,,,計(jì)算出緩沖深度為：,,如果這種指令流的連續(xù)長度超過,L,1,，則先行指令緩沖棧失去作用。,,(2),先行指令緩沖棧原來為空,,輸入端指令流入的速度最快，每次取指令的時(shí)間最短；設(shè)這種指令序列的最大長度為,L,2,，平均取一條這種指令的時(shí)間為,t,2,’,；,輸出端指令流出的速度最慢,，指令

12、分析器連續(xù)分析最難分析的指令；設(shè)平均分析一條指令的時(shí)間為,t,1,’,。分析的指令條數(shù)是,L,2,－,D,I,條。,,應(yīng)該滿足如下關(guān)系：,(,L,2,－,D,I,),t,1,’,＝,L,2,t,2,’,,,計(jì)算出緩沖深度為：,,如果這種指令流的連續(xù)長度超過,L,2,，先行指令緩沖棧失去緩沖作用。,設(shè)計(jì)舉例,,在一般處理機(jī)中連續(xù)執(zhí)行短指令的概率大。,,例：一個(gè)采用先行控制方式的處理機(jī)，指令分析器分析一條指令用一個(gè)周期，到主存儲器中取一條指令裝入先行指令緩沖棧平均用,4,個(gè)周期，如果這種指令的平均長度,為,9,，即,90,％的指令是執(zhí)行時(shí)間短的指令。,,解：計(jì)算先行指令緩沖棧的緩沖深度為：,先行指

13、令緩沖棧的工作時(shí)間關(guān)系,,,,,,,,第,1,個(gè)周期，取走指令,k+1,，請求取指令,,第,4,個(gè)周期末尾，指令,k+8,取到先行指令緩沖棧,,第,8,個(gè)周期末尾，指令,k+9,取到先行指令緩沖棧,,第,9,個(gè)周期，分析指令,k+9,，先行指令緩沖?？?,第,10,個(gè)周期，指令分析器等待,其余緩沖棧的設(shè)計(jì)原則,,一般有關(guān)系：,D,I,≥,D,C,≥,D,R,≥,D,W,,,其中：,D,I,是先行指令緩沖棧的緩沖深度，,,,D,C,是先行操作棧的緩沖深度，,,,D,R,是先行讀數(shù)棧的緩沖深度，,,,D,W,是后行寫數(shù)棧的緩沖深度。,,例如：,IBM370/165,機(jī)：,,,D,I,＝,4,，,D

14、,C,＝,3,，,D,R,＝,2,，,D,W,＝,1,。,,我國研制的兩臺大型計(jì)算機(jī)：,,,D,I,＝,8,，,D,C,＝,D,R,＝,4,，,D,W,＝,2,。,,,D,I,＝,12,，,D,C,＝,D,R,＝,6,，,D,W,＝,2,。,流水線工作原理,1.,流水寄存器,,流水線的每一個(gè)階段稱為,流水步,、流水步驟、,流水段,、流水線階段、流水功能段、,功能段,、,流水級,、流水節(jié)拍等。,,在每一個(gè)流水段的末尾或開頭必須設(shè)置一個(gè)寄存器，稱為,流水寄存器、流水鎖存器、流水閘門寄存器等,。,,在一般流水線時(shí)空圖中不畫出流水寄存器。,2.,一種指令流水線,,一般,4,至,12,個(gè)流水段，≥,8,

15、個(gè)流水段的稱為超流水線處理機(jī),,,,,,3.,流水線時(shí)空圖,,一個(gè)浮點(diǎn)加法器流水線的時(shí)空圖,4.,流水線的主要特點(diǎn),,只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效率,,盡量減少因條件分支造成的“斷流”,,通過編譯技術(shù)提供連續(xù)的相同類型操作,,每個(gè)流水線段都要設(shè)置一個(gè)流水寄存器,,時(shí)間開銷：流水線的執(zhí)行時(shí)間加長,,是流水線中需要增加的主要硬件,,各流水段的時(shí)間應(yīng)盡量相等,,流水線處理機(jī)的基本時(shí)鐘周期等于時(shí)間最長的流水段的時(shí)間長度。,,流水線需要有,“,裝入時(shí)間,”,和,“,排空時(shí)間,”,,流水線的分類,1.,線性流水線與非線性流水線,,流水線的各個(gè)流水段之間是否有反饋信號,,線性流水線,（,Linear

16、 Pipelining,）：,,每一個(gè)流水段都流過一次，而且僅流過一次,,非線性流水線,（,Nonlinear Pipelining,）：,,某些流水段之間有反饋回路或前饋回路。,,線性流水線能夠用流水線連接圖唯一表示,,非線性流水線必須用流水線連接圖和流水線預(yù)約表共同表示,2.,按照流水線的級別來分,,處理機(jī)級流水線，又稱為,指令流水線,。,,例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線,,部件級流水線,(,操作流水線,),,,如浮點(diǎn)加法器流水線,,,,,,,宏流水線,(Macro Pipelining),,,處理機(jī)之間的流水線稱，每個(gè)處理機(jī)對同一個(gè)數(shù)據(jù)流的不同部分分別進(jìn)行處理。

17、,3.,單功能流水線與多功能流水線,,單功能流水線：,,只能完成一種固定功能的流水線。,,,Cray-1,計(jì)算機(jī)種有,12,條，,YH-1,計(jì)算機(jī)有,18,條,,,Pentium,有一條,5,段定點(diǎn)和一條,8,段浮點(diǎn)流水線。,,,PentiumⅢ,有兩條定點(diǎn)和一條浮點(diǎn)指令流水線。,,多功能流水線：,,,流水線的各段通過不同連接實(shí)現(xiàn)不同功能,,,Texas,公司的,ASC,機(jī)，,8,段流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加減法、定點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。,4.,靜態(tài)流水線與動態(tài)流水線,,靜態(tài)流水線,：同一段時(shí)間內(nèi)，各個(gè)功能段只能按照一種方式連接，實(shí)現(xiàn)一種固定的功能

18、。,動態(tài)流水線,：在同一段時(shí)間內(nèi)，各段可以按照不同的方式連接，同時(shí)執(zhí)行多種功能。,5.,流水線的其他分類方法,,按照數(shù)據(jù)表示方式：,標(biāo)量流水線和向量流水線,,按照,控制方式：,同步流水線和異步流水線,,,,,,順序流水線與亂序流水線,，亂序流水線又稱為無序流水線、錯(cuò)序流水線或異步流水線等。,線性流水線的性能分析,,主要指標(biāo)：,吞吐率、加速比和效率,,1.,吞吐率（,Though Put,）,,流水線吞吐率的最基本公式：,,其中：,n,為任務(wù)數(shù)，,,Ｔ,k,為完成,n,個(gè)任務(wù)所用的時(shí)間。,,各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下，完成,n,個(gè)任務(wù)需要的總時(shí)間為：,,,T,k,＝,(k,＋,n,－,

19、1),?,t,,,其中：,k,,為流水線的段數(shù)，,?,t,為時(shí)鐘周期。,,T,k,= k,? Δt + (n-1) Δt =,(k+n-1),?,t,,吞吐率為：,,最大吞吐率為：,,各段時(shí)間不等，完成,n,個(gè)連續(xù)任務(wù)：,,,吞吐率：,,,最大吞吐率：,,,,,流水線各段執(zhí)行時(shí)間不相等的解決辦法,(1),將,“,瓶頸,”,部分再細(xì)分,（如果可分的話）,2.,加速比（,Speedup,）,,計(jì)算加速比的基本公式：,,各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下,,,（不考慮棧寄存器時(shí)間）,,,加速比：,,最大加速比：,,,,各段時(shí)間不等，輸入連續(xù)任務(wù)情況下,,,實(shí)際加,,,速比為：,,當(dāng)流水線段數(shù)增加時(shí)

20、，需要連續(xù)輸入的任務(wù)數(shù)也必須增加,3.,效率（,Efficiency,）,,計(jì)算流水線效率的一般公式：,,,,各流水段時(shí)間相等，輸入,n,個(gè)連續(xù)任務(wù)，流水線的效率為：,,,,最高效率為：,,各流水段時(shí)間不等，輸入,n,個(gè)連續(xù)任務(wù)，,流水,,線效率為：,,,,,,,,,,流水線的吞吐率、,加速比與效率的關(guān)系：,,,因?yàn)椋?,,因此：,E,＝,TP,·,?,t,，,S,＝,k,·,E,,,流水線性能分析舉例,,對于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計(jì)算出流水線的吞吐率、加速比和效率。,,對于輸入不連續(xù)任務(wù)，或多功能流水線，通常采用基本公式計(jì)算。,,例：,,用一條,4,段

21、浮點(diǎn)加法器流水線求,8,個(gè)浮點(diǎn)數(shù)的和：,Z,＝,A,＋,B,＋,C,＋,D,＋,E,＋,F,＋,G,＋,H,解：,,,Z,＝,[(A,＋,B),＋,(C,＋,D)],＋,[(E,＋,F),＋,(G,＋,H)],解：,流水線的設(shè)計(jì)原理,為提高系統(tǒng)效率我們當(dāng)然希望流水線分站越多越好，但是站寄存器的存在增加了流水線的延遲和代價(jià)，降低了功能部件的時(shí)間利用率和流水線的性價(jià)比。,,站數(shù)的確定，可以用流水線功能時(shí)間利用率不小于,e,和最高性能價(jià)格比以及器件和工藝條件綜合決定。,,,效率：,T/(T+kt,d,)>=e,,,性價(jià)比：,PCR=1/(T/k+t,d,)(C+kd),,其中,k,為流水線站數(shù)，,T

22、,為每段執(zhí)行時(shí)間，,t,d,為站流水線的延遲時(shí)間，,C,為功能部件的價(jià)格。,流水線的設(shè)計(jì)原理,令（,PCR,）,’=0,，得到,,,因?yàn)?,（,PCR,）,’’<0,，所以此時(shí),k,站流水線的性價(jià)比最高,,同時(shí)為了減少站寄存器的位數(shù)，分段時(shí)往往選在連線最少的部位。如果每段時(shí)間無法保持一致，則,ζ,M,（最大段執(zhí)行時(shí)間）和,t,d,同時(shí)決定了流水線的工作周期。其頻率為,1/(,ζ,M,+ t,d,).,,由于工程實(shí)現(xiàn)時(shí)元件的布局和器件時(shí)間參數(shù)離散等原因，到達(dá)各站寄存器的時(shí)鐘信號時(shí)離散的。,流水線的設(shè)計(jì)原理,設(shè)相鄰兩站的最大離散值為,Δ,，則工作頻率降低為,,1/(,ζ,M,+ t,d,+,Δ,)

23、,。,,,書本,35-36,頁，圖,3.2,信號穿透問題。,,非線性流水線的調(diào)度,非線性流水線調(diào)度的任務(wù)是要找出一個(gè)最小的循環(huán)周期，按照這周期向流水線輸入新任務(wù)，流水線的各個(gè)功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。,,1.,非線性流水線的表示,,線性流水線能夠用流水線連接圖唯一表示,,對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預(yù)約表,,例如：,,非線形流水線的連接圖和預(yù)約表,,一張預(yù)約表可能與多個(gè)流水線連接圖相對應(yīng),,一個(gè)流水線連接圖對應(yīng)于多張預(yù)約表,2.,非線性流水線的沖突,,啟動距離：連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔,,流水線沖突：幾個(gè)任務(wù)爭用同一個(gè)流水段,3

24、.,無沖突調(diào)度方法,,由及其學(xué)生于,1971,年提出,,禁止向量,：預(yù)約表中每一行任意兩個(gè),“,×,”,之間距離的集合。上例中為,（,3,，,4,，,6,）,,沖突向量,：,C,＝（,C,m,C,m-1,…C,2,C,1,）,,其中：,m,是,禁止向量中的最大值。,,如果,i,在禁止向量中，則,C,i,＝,1,，否則,C,i,＝,0,。,,上,例中,C,＝,(101100),例：一條,4,功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等為,△,t,,，它的預(yù)約表如下：,,,(1),寫出流水線的禁止向量和初始沖突向量。,,,(2),畫出調(diào)度流水線的狀態(tài)圖。,,,(3),求最小啟動循環(huán)和最小平均啟

25、動距離。,,,(4),求平均啟動距離最小的恒定循環(huán)。,,,(5),按照最小啟動循環(huán)連續(xù)輸入,4,個(gè)任務(wù)，求流水線實(shí)際吞吐率。,解：,,(1),禁止向量為：,(2,，,4,，,6),,,初始沖突向量：,S = 101010,,(2),構(gòu)造狀態(tài)圖,,,S,邏輯右移,2,、,4,、,6,位時(shí)，不作任何處理，,,邏輯右移,1,、,3,、,5,和大于等于,7,時(shí)：,,,S,右移,1,位之后：,010101∨101010,＝,111111,，,,,S,右移,3,位之后：,000101∨101010,＝,101111,，,,,S,右移,5,位之后：,000001∨101010,＝,101011,，,,,S,

26、右移,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,個(gè)任務(wù)，流水線實(shí)際吞吐率為：,1/,（

27、,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,條指令顯然是錯(cuò)誤的。,,在,k,個(gè)流水段的流水線處理機(jī)中，第,n,條指令要修改從第,n

28、+,1,到第,n+ k,指令中的任意一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤。,在采用先行控制方式的處理機(jī)中，如果執(zhí)行部件正在執(zhí)行第,n,條指令，與下述情況之一發(fā)生相關(guān)，都可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤,:,,存放在先行操作棧中的指令,,正在指令分析器中分析的指令,,已經(jīng)預(yù)取到先行指令緩沖棧中的指令,,更嚴(yán)重的是：有些分支指令，可能已經(jīng)在指令分析器中執(zhí)行完成。,解決指令相關(guān)的根本辦法是：,,,在程序執(zhí)行過程中不允許修改指令。,,現(xiàn)代程序設(shè)計(jì)方法要求程序具有再入性，可以被遞歸調(diào)用等，也要求不修改指令。,,在,IBM370,系列機(jī)中，用,“,執(zhí)行,”,指令來解決：在程序執(zhí)行過程中既能夠修改指令，程序

29、又具有再入性。,,,,,,,,,,,,,,,,,,“,執(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,

30、）＝,A,3,（,n,＋,1,）,,解決辦法,(,出現(xiàn)概率低,,,不宜采用設(shè)置專用通路,),：,,對于訪問主存儲器的請求，寫結(jié)果的優(yōu)先級高于讀操作數(shù)，實(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)。,,解決通

31、用寄存器數(shù)據(jù)相關(guān)的方法：,,方法一：把讀操作數(shù)、寫運(yùn)算結(jié)果與指令執(zhí)行合在一個(gè)節(jié)拍。,,采用一種典型的運(yùn)算器結(jié)構(gòu)，通用寄存器到運(yùn)算器之間建立有直接數(shù)據(jù)通路，即不設(shè)置緩沖寄存器或鎖存器。,,當(dāng)發(fā)生下述情況時(shí)，不能采用這種方法：,,當(dāng)寄存器個(gè)數(shù)多時(shí)，讀寫寄存器的時(shí)間長,,當(dāng)功能部件的執(zhí)行時(shí)間比較長，或要求指令的執(zhí)行時(shí)間短時(shí),方法二：建立相關(guān)專用通路,(ByPass),,由于發(fā)生寄存器數(shù)據(jù)相關(guān)的情況很普遍，一般計(jì)算機(jī)系統(tǒng)都采用專用數(shù)據(jù)通路，以增加硬件為代價(jià)減少速度損失。,,在運(yùn)算器的輸出端到鎖存器輸入端之間建立一條專用的數(shù)據(jù)通路。,變址相關(guān)：,在采用變址尋址方式的處理機(jī)中，由于變址量放在寄存器中，因此

32、，可能發(fā)生與通用寄存器數(shù)據(jù)相關(guān)類似變址相關(guān)，發(fā)生概率較高，通常多采用設(shè)置專用通路的方法解決相關(guān)問題。,4. LOAD,相關(guān),,,LOAD,操作的執(zhí)行時(shí)間可能比較長,,,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í)行時(shí)間不確定，不能根本解決

33、問題,,方法二：,由硬件自動插入空操作，直到,LOAD,操作完成,,在單條流水線處理機(jī)中，也可以停止節(jié)拍發(fā)生器，直到數(shù)據(jù)從存儲器中讀出為止。,控制相關(guān),(,全局相關(guān),),因程序的執(zhí)行方向可能被改變而引起的相關(guān)，也稱為,全局相關(guān),。,,主要包括：,無條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、復(fù)合條件轉(zhuǎn)移、中斷,等。,,1.,無條件轉(zhuǎn)移,,在流水線處理機(jī)中，無條件轉(zhuǎn)移指令不進(jìn)入執(zhí)行流水段，一般在指令譯碼階段就實(shí)際執(zhí)行完成。,,如果在處理機(jī)中設(shè)置有指令先行緩沖棧，則要全部或部分作廢先行指令緩沖棧中的指令。,如果轉(zhuǎn)移目標(biāo)指令,L,不在先行指令緩沖棧中,，則要將先行指令緩沖棧中的所有指令全部作廢，并等待取出轉(zhuǎn)移目標(biāo)指令,

34、L,。,,如果轉(zhuǎn)移目標(biāo)指令,L,在先行指令緩沖棧中,，只要作廢先行指令緩沖棧中的部分指令。,,無條件轉(zhuǎn)移指令一般對指令執(zhí)行部件的工作不會造成影響。,,為進(jìn)一步減少無條件轉(zhuǎn)移指令造成的影響，,在先行指令緩沖棧的入口處增設(shè)一個(gè)專門處理無條件轉(zhuǎn)移指令的指令分析器,2.,一般條件轉(zhuǎn)移,,,k,：,……,;,置條件碼,CC,,k+1,：,JMP(CC) L ;,如果,CC,為真轉(zhuǎn)向,L,,,……,,L,：,……,,,當(dāng)條件碼是上一條指令產(chǎn)生時(shí)，相關(guān)最嚴(yán)重,無論轉(zhuǎn)移是否成功，條轉(zhuǎn)移指令都在指令分析階段就已經(jīng)執(zhí)行完成。,,無論轉(zhuǎn)移不成功或不成功，指令分析器要停頓一段時(shí)間，等待條件碼產(chǎn)生。,如果轉(zhuǎn)移成功：指

35、令,L,已經(jīng)在先行指令緩沖棧，指令分析器接著,“,分析,L,”,，如果指令,L,不在先行指令緩沖棧，指令分析器要等待一個(gè)周期。,,轉(zhuǎn)移不成功，對程序執(zhí)行影響不大，,,當(dāng)轉(zhuǎn)移成功時(shí)，不僅指令執(zhí)行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。,,在采用流水線方式的處理機(jī)中，要通過軟件與硬件的多種手段來近可能地降低轉(zhuǎn)移成功的概率，減少轉(zhuǎn)移成功造成的影響。,3.,復(fù)合條件轉(zhuǎn)移,,,k,：,OP L ;,產(chǎn)生條件碼，并決定是否轉(zhuǎn)向,L,,,……,,L,：,……,,如果轉(zhuǎn)移不成功：不造成任何影響，就象普通的運(yùn)算型指令一樣,,如果轉(zhuǎn)移成功：造成的影響比一般條件轉(zhuǎn)移指令還要大得多。,全部或部分作廢

36、先行指令緩沖棧、先行操作棧、先行讀數(shù)棧和指令分析器中的指令。,,必須采取策略，減小轉(zhuǎn)移成功造成的影響。,條件分支對流水線的影響,處理好條件轉(zhuǎn)移和中斷的關(guān)鍵問題有兩個(gè)：,,要確保流水線能夠正常工作,,減少因,“,斷流,”,引起的吞吐率和效率的下降,,1.,條件分支的處理方法,,條件轉(zhuǎn)移指令對流水線的影響很大，必須采取措施來減少這種影響?？赡艿拇胧┯校?,(1),延遲轉(zhuǎn)移技術(shù)和指令取消技術(shù),,只能用于單流水線處理機(jī)中，且流水線的級數(shù)不能太多；,據(jù)統(tǒng)計(jì)，,編譯器調(diào)度一條指令成功的概率在,90,％以上，而調(diào)度兩條指令成功的概率只有,40,％左右。,,當(dāng)沒有合適的指令可調(diào)度時(shí)，編譯器只能插入空操作。,,

37、(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ù)測可以只用軟件實(shí)現(xiàn)，也可用硬件來實(shí)現(xiàn)，還可以在轉(zhuǎn)移的兩個(gè)方向上都預(yù)取指令。,,TI,公司的,SuperSPARC,處理機(jī)采用了靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)，而且設(shè)置有轉(zhuǎn)移目標(biāo)緩沖棧，在兩個(gè)方向上都預(yù)取指令。,2.,條件分支在流水線中的執(zhí)行過程,,因?yàn)榈?i,條指令所需要的條件碼由第,i-1,條指令給出；

38、在一條由,k,個(gè)功能段的流水線中，第,i-1,條指令要等到第,i+k-2,條指令進(jìn)入流水線時(shí)才能形成條件碼。,,轉(zhuǎn)移不成功，猜測正確，流水線的吞吐率和效率沒有降低，,,轉(zhuǎn)移成功，猜測錯(cuò)誤，要先作廢流水線中已經(jīng)執(zhí)行的,i+1,、,i+2,、,……,、,i+k-2,指令；然后再從分支點(diǎn)開始執(zhí)行第,P,、,p+1,、,……,指令。,,條件分支指令在流水線中的執(zhí)行過程,當(dāng)分支的執(zhí)行方向猜測錯(cuò)誤時(shí)，可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤。,,例如，若第,i+1,條指令是：,(R1,＋,(R2)→R1,，,寄存器,R1,中內(nèi)容就被破壞，整個(gè)程序執(zhí)行的結(jié)果是錯(cuò)誤的。,,目前的處理機(jī)有兩種做法：,,一種方法是只進(jìn)行指令

39、譯碼和準(zhǔn)備好運(yùn)算所需要的操作數(shù)，在轉(zhuǎn)移條件沒有形成之前不執(zhí)行運(yùn)算；,,另一種方法是一直執(zhí)行到運(yùn)算完成，但不送回運(yùn)算結(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.,軟件,“,猜測法,”,,目標(biāo)：,通過編譯器盡量降低轉(zhuǎn)移成功的概率。,,例如：對于循環(huán)程序，普通編譯器生成的目標(biāo)代碼，轉(zhuǎn)移成功的概率很高，不成功的只有一次。這種編譯結(jié)果對流水線極為不利。,,,軟件,“,猜測法,”,：,,,通過編譯器降低轉(zhuǎn)移成功的概率,2.,硬件,“,猜測法,”,,方法：,通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指

40、令對流水線的影響,,在先行指令緩沖棧的人口處設(shè)置一個(gè)簡單的指令分析器，當(dāng)檢測到轉(zhuǎn)移指令時(shí)，就把轉(zhuǎn)移目標(biāo)地址,L,送入先行程序計(jì)數(shù)器,PC,1,中，同時(shí)保留當(dāng)前,PC,1,中的內(nèi)容到另一寄存器中。,,轉(zhuǎn)移成功，猜測正確。對轉(zhuǎn)移指令對流水線不造成影響。,,轉(zhuǎn)移不成功，用保存下來的地址恢復(fù),PC,1,和,PC,。,,軟硬件共同配合，都往同一個(gè)方向去猜測。,3.,兩個(gè)先行指令緩沖棧,,向前條件轉(zhuǎn)移，轉(zhuǎn)移成功與不成功各,50%,,在先行指令緩沖棧中,增加一個(gè)先行目標(biāo)緩沖棧,,按照轉(zhuǎn)移成功的方向預(yù)取指令到先行目標(biāo)緩沖棧中。,,先行指令緩沖棧仍然按照轉(zhuǎn)移不成功的方向繼續(xù)預(yù)取指令。,,如果轉(zhuǎn)移不成功，則繼續(xù)分

41、析原來先行指令緩沖棧中指令。,,如果轉(zhuǎn)移成功，則分析新增設(shè)的先行目標(biāo)緩沖棧中的指令。,提前形成條件碼,必要性：對提高流水線的性能非常有效,,可能性：,可在運(yùn)算開始或中間產(chǎn)生條件碼,,對于乘除法，兩個(gè)源操作數(shù)的符號相同結(jié)果為正，符號相反結(jié)果為負(fù),,對于乘法，有一個(gè)操作數(shù)為,0,，則乘積為,0,,被除數(shù)為,0,，商為,0,； 除數(shù)為,0,，除法結(jié)果溢出,,同號加或異號減，結(jié)果符號與第一操作數(shù)相同,,異號加或同號減，結(jié)果的符號與絕對值大的操作數(shù)相同,,溢出及是否為,0,可以通過一個(gè)比較器提前產(chǎn)生,精確斷點(diǎn)與不精確斷點(diǎn),對于輸入輸出設(shè)備的中斷服務(wù)，實(shí)際上不需要有精確斷點(diǎn)。,,比較簡單的處理方法是：讓已

42、經(jīng)進(jìn)入流水線的所有指令都執(zhí)行完成，斷點(diǎn)就是最后進(jìn)入流水線的那條指令的地址。,,對于程序性錯(cuò)誤和機(jī)器故障等引起的中斷，它們出現(xiàn)的概率很低，處理原則：,不在于縮短時(shí)間，關(guān)鍵是要正確保存現(xiàn)場和正確恢復(fù)斷點(diǎn)。,不精確斷點(diǎn),(Imprecise),，,流水線可以不斷流,,需要的硬件比較少，控制邏輯比較簡單,,中斷響應(yīng)時(shí)間加長,,,采用不精確斷點(diǎn)法可能會發(fā)生如下兩個(gè)問題：,,(1),程序的調(diào)試?yán)щy,,早期的流水線處理機(jī)，多采用不精確斷點(diǎn)法,,近期的流水線處理機(jī)一般都采用精確斷點(diǎn)法,(2),程序執(zhí)行的結(jié)果可能出錯(cuò)，例如：,,,i,：,FADD R1, R2,；,(R1),＋,(R2)→R1,,i+1,：,

43、FMUL R3, R1,；,(R3)×(R1)→R3,,當(dāng)?shù)?i,條指令執(zhí)行到,S,6,段時(shí)發(fā)現(xiàn)浮點(diǎn)加法結(jié)果溢出，于是發(fā)出中斷服務(wù)申請。由于采用不精確斷點(diǎn)法，已經(jīng)進(jìn)入流水線的第,i+1,條指令將執(zhí)行完成；因?yàn)榈?i+1,條指令使用了不正確的,R1,，所以浮點(diǎn)乘法的執(zhí)行結(jié)果是不正確的。,,采用精確斷,(Precise),點(diǎn)法，要設(shè)置一定數(shù)量的后援寄存器,，把整個(gè)流水線中所有指令的執(zhí)行結(jié)果和現(xiàn)場都保存下來。,動態(tài)調(diào)度技術(shù),實(shí)現(xiàn)方法：,,由硬件動態(tài)調(diào)整指令執(zhí)行順序，以減少數(shù)據(jù)相關(guān)造成的影響。,,主要優(yōu)點(diǎn)：,,能夠處理在編譯時(shí)無法確定的相關(guān)，并簡化編譯器設(shè)計(jì),,在其他流水線機(jī)器上編譯的目標(biāo)代碼也能夠

44、高效運(yùn)行,,用靜態(tài)調(diào)度法生成的代碼也能在動態(tài)調(diào)度法的機(jī)器中運(yùn)行,,主要缺點(diǎn)：,指令級并行度低，因?yàn)橹荒茉诒容^小的范圍內(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,、,……,等也不能進(jìn)入流水線。,,功能段,S,3,、,S,4,、,S,5,將逐漸空閑

45、。,,缺點(diǎn)：,吞吐率和效率降低,,優(yōu)點(diǎn)：,流水線的控制邏輯比較簡單,流水線,“,斷流,”,，有些功能段,“,空閑,”,2.,亂序,(Out of order),流動方式：,指令流出流水線的順序與流入流水線的順序不同。,又稱為,錯(cuò)序流動方式、無序流動方式、異步流動方式等。,亂序流動中的數(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+

46、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)等。,,有時(shí)把,相關(guān),稱為,“,冒險(xiǎn),”,(hazard),、,“,竟?fàn)?”,,(competiti

47、on),等。,,在程序執(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,可以同時(shí)執(zhí)行,,即專用數(shù)據(jù)通路,,(2),寫寫相關(guān)，,先后順序無關(guān),,(3),讀寫相關(guān)，,先后順序無關(guān),,后兩種情況又稱為,“,變量換名技術(shù),”,2.,變量換名技術(shù),,用來自動消除,讀寫數(shù)據(jù)相關(guān)

48、,和,寫寫數(shù)據(jù)相關(guān),,規(guī)則：,一個(gè)變量只允許定值一次,,在三種數(shù)據(jù)相關(guān)中，實(shí)際上只有寫讀數(shù)據(jù)相關(guān)必須依靠硬件、或采用軟硬件結(jié)合的方法來解決,,解決方法：,推后處理,或,專用數(shù)據(jù)通路,,在上面的數(shù)據(jù)重定向圖中，把,B,換成了,B’,，并在以后的都引用,B’,讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就不存在了。,三種主流處理機(jī),(,指令級高度并行的超級處理機(jī),),：,,,超標(biāo)量處理機(jī),,超流水線處理機(jī),,超標(biāo)量超流水線處理機(jī),基本結(jié)構(gòu),普通標(biāo)量流水線處理機(jī)：,,,一條指令流水線,，一個(gè)多功能操作部件，,,每個(gè)時(shí)鐘周期平均執(zhí)行指令的條數(shù)小于,1,。,,多操作部件標(biāo)量處理機(jī)：,,,一條指令流水線,，多個(gè)獨(dú)立的操作部

49、件，,,,指令級并行度小于,1,。,,超標(biāo)量處理機(jī)典型結(jié)構(gòu)：,,多條并行工作的指令流水線,，,多個(gè)獨(dú)立的操作部件，,,,指令級并行度（,ILP,）大于,1,。,,Motorola,公司的,MC88110,,有,10,個(gè)操作部件,,兩個(gè)寄存器堆：,,整數(shù)部件通用寄存器堆，,32,個(gè),32,位寄存器,,浮點(diǎn)部件擴(kuò)展寄存器堆，,32,個(gè),80,位寄存器,,緩沖深度為,4,的先行讀數(shù)棧,,緩沖深度為,3,的后行寫數(shù)棧,,兩個(gè)獨(dú)立的高速,Cache,中，各為,8KB,，采用兩路組相聯(lián)方式,,轉(zhuǎn)移目標(biāo)指令,Cache,，用于存放另一條分支上的指令,單發(fā)射與多發(fā)射,1.,單發(fā)射處理機(jī),(,普通流水線標(biāo)量處理

50、機(jī),),：,,每個(gè)周期只取一條指令、只譯碼一條指令，只執(zhí)行一條指令，只寫回一個(gè)運(yùn)算結(jié)果。,,取指令部件和指令譯碼部件各設(shè)置一套；,,只設(shè)置一個(gè)多功能操作部件或設(shè)置多個(gè)獨(dú)立的操作部件；,,操作部件中可以采用流水線結(jié)構(gòu)，也可以不采用流水線結(jié)構(gòu)。,,目標(biāo)是每個(gè)時(shí)鐘周期平均執(zhí)行一條指令，,ILP,的期望值為,1,。,2.,多發(fā)射處理機(jī)：,,每個(gè)周期同時(shí)取多條指令、同時(shí)譯碼多條指令，同時(shí)執(zhí)行多條指令，同時(shí)寫回多個(gè)運(yùn)算結(jié)果。,,多個(gè)取指令部件，多個(gè)指令譯碼部件和多個(gè)寫結(jié)果部件。,,設(shè)置多個(gè)指令執(zhí)行部件，有些指令執(zhí)行部件采用流水線結(jié)構(gòu)。,,目標(biāo)是每個(gè)時(shí)鐘周期平均執(zhí)行多條指令，,ILP,的期望值大于,1,。,

51、3.,超標(biāo)量處理機(jī),(,一個(gè)時(shí)鐘周期內(nèi)同時(shí)發(fā)射多條指令的處理機(jī),),：,,有兩條或兩條以上能同時(shí)工作的指令流水線。,,先行指令窗口,：能夠從指令,Cache,中預(yù)取多條指令，能夠?qū)Υ翱趦?nèi)的指令進(jìn)行數(shù)據(jù)相關(guān)性分析和功能部件沖突檢測，提高功能部件利用率，一般取,2-8,條指令。,,由于程序中指令并行性的開發(fā)有限，所以度,m,比較低，理論上最佳,m=3,。,,,超標(biāo)量處理機(jī)的指令級并行度：,1,＜,ILP,＜,m,。,,,超標(biāo)量處理機(jī)非常適合于求解像稀疏向量或矩陣這類標(biāo)量計(jì)算問題。,多流水線調(diào)度,順序發(fā)射,(in-order issue),與亂序發(fā)射,(out-order issue),：,指令發(fā)射

52、順序是按照程序中指令排列順序進(jìn)行的稱為順序發(fā)射,,順序完成,(in-order completion),與亂序完成,(out-order completion),：,指令完成順序是按照程序中指令排列順序進(jìn)行的稱為順序完成,,多流水線的調(diào)度主要有三種方法：,,順序發(fā)射順序完成,,順序發(fā)射亂序完成,,亂序發(fā)射亂序完成,以如下,6,條指令組成的程序?yàn)槔?，說明這三種調(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),,

53、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,個(gè)數(shù)據(jù)相關(guān)，包括,2,個(gè)寫讀相關(guān)，,1,個(gè)讀寫相關(guān)和,1,個(gè)寫寫相關(guān)。,,1.,順序發(fā)射順序完成,,共用,10,個(gè)時(shí)鐘周期完成,,還有,8,個(gè)空閑的時(shí)鐘周期,2.,順序發(fā)射亂序完成,,總的執(zhí)行時(shí)間為,9,個(gè)時(shí)鐘周期，,,,節(jié)省了一個(gè)時(shí)鐘周期。少了,5,個(gè)空閑時(shí)鐘周期。,3.,亂序發(fā)射亂序完成（采用先行指令窗口，度,m=3,）,沒有空閑周期，功能部件得到充分利用。

54、,,總的執(zhí)行時(shí)間為,8,個(gè)周期，節(jié)省,2,個(gè)周期。,資源沖突,如果操作部件采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性很小；,,如果不采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性就比較大。,,下面是一個(gè)由,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,個(gè)周期，,,有,5,個(gè)空閑周期

55、,。,操作部件采用流水線：,,做完,4,條指令共用,8,個(gè)周期，,,少用,3,個(gè)周期。,操作部件采用流水線結(jié)構(gòu)的原因分析,,假設(shè)每個(gè)周期發(fā)射,m,條指令，操作部件的延遲時(shí)間為,k,個(gè)周期，,,如果操作部件不采用流水線結(jié)構(gòu)，則使用同一個(gè)操作部件的兩條指令序號應(yīng)該,至少相差,m×k,,如果操作部件采用,k,段流水線結(jié)構(gòu)，則使用同一個(gè)操作部件的兩條指令,只需相差,m,或,m,以上,,操作部件的延遲時(shí)間,k,一般在,4,至,10,之間，每個(gè)時(shí)鐘周期發(fā)射的指令條數(shù),m,在,2,至,4,之間。取中間值，,k,＝,7,，,m,＝,3,為了不發(fā)生資源沖突，如果操作部件不采用流水線結(jié)構(gòu)，,,,兩條使用同一個(gè)功能

56、部件的指令序號必須相差,21,或,21,以上。,,如果操作部件采用流水線結(jié)構(gòu)，,,,兩條使用同一個(gè)功能部件的指令序號只需要相差,3,或,3,以上。,,因此，在超標(biāo)量處理機(jī)中，操作部件一般要采用流水線結(jié)構(gòu)。,,如果由于某種原因，操作部件不能采用流水線結(jié)構(gòu)，則必須設(shè)置多個(gè)相同種類的操作部件,普通標(biāo)量處理機(jī)，希望相同操作連續(xù)出現(xiàn)。,,只有連續(xù)出現(xiàn)相同操作的指令序列時(shí)，流水線的效率才能得到充分發(fā)揮。,,超標(biāo)量處理機(jī),則正好相反，,希望相同操作不要連續(xù)出現(xiàn),。,,相同操作的指令序列連續(xù)出現(xiàn)時(shí)，會發(fā)生資源沖突；,,要求相同操作的指令能夠相對均勻地分布在程序中。,,超標(biāo)量處理機(jī)的這種要求正好符合一般標(biāo)量程序

57、的特點(diǎn),。,超標(biāo)量處理機(jī)性能,單流水線普通標(biāo)量處理機(jī)的指令級并行度記作,(1, 1),，,,超標(biāo)量處理機(jī)的指令級并行度記作,(m, 1),，,,超流水線處理機(jī)的指令級并行度記作,(1, n),，,,而超標(biāo)量超流水線處理機(jī)的指令級并行度記作,(m, n),。,,在理想情況下，,N,條指令在單流水線標(biāo)量處理機(jī)上的執(zhí)行時(shí)間為：,,,T(1, 1),＝,(k,＋,N,－,1),?,t,在每個(gè)周期發(fā)射,m,條指令的超標(biāo)量處理機(jī)上執(zhí)行的時(shí)間為：,,,,,,超標(biāo)量處理機(jī)相對于單流水線標(biāo)量處理機(jī)的加速比為：,,,,,超標(biāo)量處理機(jī)的加速比的最大值為：,S,(,m,,1),MAX,＝,m,超流水線處理機(jī)的兩種定義

58、：,,在一個(gè)基本時(shí)鐘周期內(nèi)分時(shí)發(fā)射多條指令的處理機(jī),,指令流水線的段數(shù)大于等于,8,的流水線處理機(jī)（深度流,,水）,,提高處理機(jī)性能的兩種方法：,,通過增加硬件資源來提高處理機(jī)性能（空間并行性）,,通過各部分硬件的重疊工作來提高處理機(jī)性能（時(shí)間并,,行性）,,兩種不同并行性：,,超標(biāo)量處理機(jī)采用的是空間并行性。,,超流水線處理機(jī)采用的是時(shí)間并行性。,指令執(zhí)行時(shí)序,每隔,1/n,個(gè)時(shí)鐘周期發(fā)射一條指令,，,,即處理機(jī)的流水線周期為,1/n,個(gè)時(shí)鐘周期。,典型處理機(jī)結(jié)構(gòu),MIPS R4000,處理機(jī)：,,每個(gè)時(shí)鐘周期包含兩個(gè)流水段,,是一種很標(biāo)準(zhǔn)的超流水線處理機(jī)結(jié)構(gòu)。,,指令流水線有,8,個(gè)流水段

59、。,,指令,Cache,和數(shù)據(jù),Cache,的容量各,8KB,，,,每個(gè)時(shí)鐘周期可以訪問,Cache,兩次，,,在一個(gè)時(shí)鐘周期內(nèi)可以從指令,Cache,中讀出兩條指令，從數(shù)據(jù),Cache,中讀出或?qū)懭雰蓚€(gè)數(shù)據(jù)。,,主要運(yùn)算部件有整數(shù)部件和浮點(diǎn)部件。,,如果在,LOAD,指令之后的兩條指令中，任何一條指令要在它的,EX,流水級使用這個(gè)數(shù)據(jù)，則指令流水線要暫停一個(gè)時(shí)鐘周期。,超流水線處理機(jī)性能,指令級并行度為,(1,n),的超流水線處理機(jī)，執(zhí)行,N,條指令所的時(shí)間為：,,,,超流水線處理機(jī)相對于單流水線普通標(biāo)量處理機(jī)的加速比為：,,,,,,,加速比的最大值為：,S(1, n),MAX,＝,n,超標(biāo)

60、量超流水線處理機(jī),,一個(gè)時(shí)鐘周期發(fā)射,n,次，每次發(fā)射,m,條指令，每個(gè)時(shí)鐘周期共發(fā)射指令,mn,條。同時(shí)開發(fā)空間并行性和時(shí)間并行性,,,指令執(zhí)行時(shí)序,典型處理機(jī)結(jié)構(gòu),DEC,公司的,Alpha,處理機(jī)為典型的,超標(biāo)量超流水線結(jié)構(gòu),。,,主要由四個(gè)功能部件和兩個(gè),Cache,組成：整數(shù)部件,EBOX,,,浮點(diǎn)部件,FBOX,,,地址部件,ABOX,,,中央控制部件,IBOX,,,指令,Cache,和數(shù)據(jù),Cache,,在,EBOX,內(nèi)還有多條專用數(shù)據(jù)通路，可以把運(yùn)算結(jié)果直接送到執(zhí)行部件。,中央控制部件,IBOX,能夠同時(shí)完成：,,同時(shí)讀出兩條指令；,,同時(shí)對兩條指令進(jìn)行譯碼，并作相關(guān)性檢測；,

61、,如果資源和相關(guān)性允許，,IBOX,就把兩條指令同時(shí)發(fā)射給,EBOX,、,ABOX,和,FBOX,三個(gè)執(zhí)行部件中的兩個(gè)。,,指令流水線的控制方式：,,采用,順序發(fā)射亂序完成,。,,在指令,Cache,中有一個(gè)轉(zhuǎn)移歷史表，實(shí)現(xiàn)條件轉(zhuǎn)移的動態(tài)預(yù)測。,Alpha 21064,處理機(jī)共有,三條指令流水線：,,(1),整數(shù)操作流水線為,7,個(gè)流水段,，其中，取指令,2,個(gè)流水段、分析指令,2,個(gè)流水段、運(yùn)算,2,個(gè)流水段、寫結(jié)果,1,個(gè)流水段。,,(2),訪問存儲器流水線為,7,個(gè)流水段,。,,(3),浮點(diǎn)操作流水線分為,10,個(gè)流水段,，其中，浮點(diǎn)執(zhí)行部件,FBOX,的延遲時(shí)間為,6,個(gè)流水段。,,三

62、條指令流水線的平均段數(shù)為,(7+7+10)/3=8,，且每個(gè)時(shí)鐘周期發(fā)射兩條指令。因此，,Alpha 21064,處理機(jī)為超標(biāo)量超流水線處理機(jī)。,超標(biāo)量超流水線處理機(jī)的性能,指令級并行度為,(m,n),的超標(biāo)量超流水線處理機(jī)，連續(xù)執(zhí)行,N,條指令所需要的時(shí)間為：,,,,超標(biāo)量超流水線處理機(jī)相對于單流水線標(biāo)量處理機(jī)的加速比為：,,,,在理想情況下，超標(biāo)量超流水線處理機(jī)加速比的最大值為：,,S,(m,n),MAX,＝,m n,三種標(biāo)量處理機(jī)的性能比較,,從三種標(biāo)量處理機(jī)的性能曲線中，可以得出如下結(jié)論：,,1.,三種處理機(jī)的性能關(guān)系,,超標(biāo)量處理機(jī)的相對性能最高，其次是超標(biāo)量超流水線處理機(jī)，超流水線

63、處理機(jī)的相對性能最低，,主要原因如下：,,(1),超標(biāo)量處理機(jī)功能部件的沖突比超流水線處理機(jī)小。在指令執(zhí)行過程中的許多功能段，超標(biāo)量處理機(jī)都重復(fù)設(shè)置有多個(gè)相同的指令執(zhí)行部件，而超流水線處理機(jī)只是把同一個(gè)指令執(zhí)行部件分解為多個(gè)流水級。,(2),條件轉(zhuǎn)移等操作造成的損失，超流水線處理機(jī)要比超標(biāo)量處理機(jī)大。,,由于超流水線處理機(jī)采用深度流水線結(jié)構(gòu)，對條件轉(zhuǎn)移等操作比超標(biāo)量處理機(jī)敏感。,,(3),超流水線處理機(jī)的啟動延遲通常要比超標(biāo)量處理機(jī)大。,,超標(biāo)量處理機(jī)在每個(gè)時(shí)鐘周期的一開始就同時(shí)發(fā)射多條指令，,,超流水線處理機(jī)把一個(gè)時(shí)鐘周期平均分成多個(gè)流水線周期，每個(gè)流水線周期只發(fā)射一條指令。,2.,實(shí)際指令

64、級并行度與理論指令級并行度的關(guān)系,,當(dāng)橫坐標(biāo)給出的理論指令級并行度比較低時(shí)，處理機(jī)的實(shí)際指令級并行度的提高比較快。,,當(dāng)理論指令級并行度進(jìn)一步增加時(shí)，處理機(jī)實(shí)際指令級并行度提高的速度越來越慢。,,在實(shí)際設(shè)計(jì)超標(biāo)量、超流水線、超標(biāo)量超流水線處理機(jī)的指令級并行度時(shí)要適當(dāng)，否則，有可能造成花費(fèi)了大量的硬件，但實(shí)際上處理機(jī)所能達(dá)到的指令級并行度并不高。,,目前，一般認(rèn)為，,m,和,n,都不要超過,4,。,3.,最大指令級并行度,,一個(gè)特定程序由于受到本身的數(shù)據(jù)相關(guān)和控制相關(guān)的限制，它的指令級并行度的最大值是有限的，是有個(gè)確定的值。,,最大指令級并行度由程序自身的語義決定，與這個(gè)程序運(yùn)行在那一種處理機(jī)上

65、及采用何種方法開發(fā)并行性無關(guān)。,,對于某一個(gè)特定的程序，圖中的三條曲線最終都要收攏到同一個(gè)點(diǎn)上。,,對于各個(gè)不同程序，這個(gè)收攏點(diǎn)的位置也是不同的。,具有向量數(shù)據(jù)表示和向量指令系統(tǒng)的處理機(jī),,向量處理機(jī)是解決數(shù)值計(jì)算問題的一種高性能計(jì)算機(jī),,向量處理機(jī)屬,大型或巨型機(jī),，也可以用微機(jī)加一臺,向量協(xié)處理器,組成,,向量處理機(jī)一般都采用流水線結(jié)構(gòu)，,通常有有多條并行工作的流水線,,必須把要解決的問題轉(zhuǎn)化為向量運(yùn)算，才能發(fā)揮向量處理機(jī)的效率,向量處理,例：一個(gè)簡單的,C,語言程序如下：,for (i = 10; i <= 1010; i++) c[i] = a[i] + b[i] ;,,在向

66、量處理機(jī)上,,,可以只用一條指令：,C(10:1010)=A(10:1010) + B(10:1010),一條向量指令可處理Ｎ個(gè)或Ｎ對操作數(shù),,在標(biāo)量處理機(jī)上用,10,多條指令，其中有,8,條指令要循環(huán),1000,次。,,采用多寄存器結(jié)構(gòu)的兩地址指令編寫程序,,存儲器采用字節(jié)編址方式，字長為,32,位,從標(biāo)量到向量,在一般標(biāo)量處理機(jī)中需要如下指令序列來實(shí)現(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 ;,計(jì)算向量偏移量,,,,;,初始值為,40,,LOOP: LOAD R4,A(R3) ;,讀,A,向量的一個(gè)元素,LOAD R5, B(R3) ;,讀,B,向量的一個(gè)元素,,,ADD R4, R5 ;,加一個(gè)元素,,,STORE R4, C(R3) ;,寫,C,向量的一個(gè)元素,,,ADD R3, R2