并行計算機體系結構第三章

《并行計算機體系結構第三章》由會員分享，可在線閱讀，更多相關《并行計算機體系結構第三章（215頁珍藏版）》請在裝配圖網上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

14、,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é)拍等。,,在每一個流水段的末尾或開頭必須設置一個寄存器，稱為,流水寄存器、流水鎖存器、流水閘門寄存器等,。,,在一般流水線時空圖中不畫出流水寄存器。,2.,一種指令流水線,,一般,4,至,12,個流水段，≥,8,

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

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

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

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

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

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

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

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

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

24、.,無沖突調度方法,,由及其學生于,1971,年提出,,禁止向量,：預約表中每一行任意兩個,“,×,”,之間距離的集合。上例中為,（,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,,，它的預約表如下：,,,(1),寫出流水線的禁止向量和初始沖突向量。,,,(2),畫出調度流水線的狀態(tài)圖。,,,(3),求最小啟動循環(huán)和最小平均啟

25、動距離。,,,(4),求平均啟動距離最小的恒定循環(huán)。,,,(5),按照最小啟動循環(huán)連續(xù)輸入,4,個任務，求流水線實際吞吐率。,解：,,(1),禁止向量為：,(2,，,4,，,6),,,初始沖突向量：,S = 101010,,(2),構造狀態(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,

26、右移,7,位或大于,7,位后：還原到它本身。,101111,右移,5,位之后：,000001∨101010,＝,101011,，,,101011,右移,3,位之后：,000101∨101010,＝,101111,，,,101011,右移,5,位之后：,000001∨101010,＝,101011,。,簡單循環(huán)：,狀態(tài)圖中各種沖突向量只經過一次的啟動循環(huán)。,,(3),最小的啟動循環(huán),為（,1,，,7,）和（,3,，,5,）,,,,,平均啟動距離為,4,。,,(4),啟動距離最小的恒定循環(huán)為（,5,）,,(4),按照最小啟動循環(huán)（,1,，,7,）連續(xù)輸入,4,個任務，流水線實際吞吐率為：,1/,（

27、,4,△t,）,數據相關,(,局部相關,),數據相關：在執(zhí)行本條指令的過程中，如果用到的指令、操作數、變址量等是前面指令的執(zhí)行結果，這種相關稱為數據相關。,,控制相關：由條件分支指令、轉子程序指令、中斷等引起的相關。,,解決數據相關的方法有兩種：,,推后處理,,設置專用路徑,1.,指令相關,,發(fā)生指令相關的情況：,,,n,：,STORE R1,,n,+1,,n,+1,：,……,,,滿足關系： 結果地址,(,n),＝指令地址,(,n,+1),,當第,n,條指令還沒有把執(zhí)行結果寫到主存之前，取出的第,n,+1,條指令顯然是錯誤的。,,在,k,個流水段的流水線處理機中，第,n,條指令要修改從第,n

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

29、又具有再入性。,,,,,,,,,,,,,,,,,,“,執(zhí)行”指令執(zhí)行由第二地址,((X,2,)+(B,2,)+D,2,),決定的主存數據區(qū)中的指令。,2.,主存操作數相關,(,相鄰兩條指令之間出現對主存同一單元要求先寫后讀的關聯,),,發(fā)生主存操作數相關的指令序列：,,,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,),,出現下列情況之一，就發(fā)生主存操作數相關：,,,A,1,（,n,）＝,A,2,（,n,＋,1,）,,,A,1,（,n,

30、）＝,A,3,（,n,＋,1,）,,解決辦法,(,出現概率低,,,不宜采用設置專用通路,),：,,對于訪問主存儲器的請求，寫結果的優(yōu)先級高于讀操作數，實現自動推后處理。,3.,通用寄存器數據相關,,發(fā)生寄存器數據相關的可能性很大，影響面也很大,,,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,數據相關。,,發(fā)生,R,1,(n),＝,R,2,(n,＋,1),稱為,R,2,數據,相關。,,解決通

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

32、，可能發(fā)生與通用寄存器數據相關類似變址相關，發(fā)生概率較高，通常多采用設置專用通路的方法解決相關問題。,4. LOAD,相關,,,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,數據相關。,,解決方法：,方法一：,由編譯器在,LOAD,之后插入不發(fā)生數據相關的指令，,由于,LOAD,的執(zhí)行時間不確定，不能根本解決

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

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

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

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

37、(2),動態(tài)分支預測技術,,根據近期轉移是否成功的記錄來預測下一次轉移的方向。,,所有的動態(tài)轉移預測方法都能夠隨程序的執(zhí)行過程動態(tài)地改變轉移的預測方向。,(3),靜態(tài)分支預測技術,,轉移預測的方向是確定的，或者預測轉移不成功，或者預測轉移成功，,,在程序實際執(zhí)行過程中，轉移預測的方向不能改變。,,靜態(tài)轉移預測可以只用軟件實現，也可用硬件來實現，還可以在轉移的兩個方向上都預取指令。,,TI,公司的,SuperSPARC,處理機采用了靜態(tài)轉移預測技術，而且設置有轉移目標緩沖棧，在兩個方向上都預取指令。,2.,條件分支在流水線中的執(zhí)行過程,,因為第,i,條指令所需要的條件碼由第,i-1,條指令給出；

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

39、譯碼和準備好運算所需要的操作數，在轉移條件沒有形成之前不執(zhí)行運算；,,另一種方法是一直執(zhí)行到運算完成，但不送回運算結果。,靜態(tài)分支預測技術,靜態(tài)分支預測：,,在程序執(zhí)行過程中轉移預測方向不能改變,,動態(tài)分支預測：,,在程序執(zhí)行過程中能夠改變轉移預測方向,,本節(jié)講靜態(tài)預測技術,,1.,軟件,“,猜測法,”,,目標：,通過編譯器盡量降低轉移成功的概率。,,例如：對于循環(huán)程序，普通編譯器生成的目標代碼，轉移成功的概率很高，不成功的只有一次。這種編譯結果對流水線極為不利。,,,軟件,“,猜測法,”,：,,,通過編譯器降低轉移成功的概率,2.,硬件,“,猜測法,”,,方法：,通過改變硬件結構來降低轉移指

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

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

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

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

44、高效運行,,用靜態(tài)調度法生成的代碼也能在動態(tài)調度法的機器中運行,,主要缺點：,指令級并行度低，因為只能在比較小的范圍內尋找并行性,順序流動與亂序流動,1.,順序流動方式：,任務按順序流入流水線,,,也按順序流出流水線,,把如下一段程序輸入到這條流水線中：,,,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,將逐漸空閑

45、。,,缺點：,吞吐率和效率降低,,優(yōu)點：,流水線的控制邏輯比較簡單,流水線,“,斷流,”,，有些功能段,“,空閑,”,2.,亂序,(Out of order),流動方式：,指令流出流水線的順序與流入流水線的順序不同。,又稱為,錯序流動方式、無序流動方式、異步流動方式等。,亂序流動中的數據相關,在亂序流動方式中，可能發(fā)生三種數據相關,,,寫寫相關,,,k,：,LOAD F1, A ;F1,?,（,A,）,寫讀相關,,,k+1,：,FADD F2, F1 ;F2,?,（,F2,）,+,（,F1,）,,,k+2,：,FMUL F1, F3 ;F1,?,（,F1,）,?,（,F3,）,,,k+

46、3,：,STORE F1, B ;B,?,（,F1,）,讀寫相關,,(1),寫讀相關：,指令,k,與指令,k+1,之間關于,F1,的相關，又稱為數據相關、先寫后讀相關、流相關、,WR,相關、,RAW,相關等。,,(2),讀寫相關：,指令,k+1,與指令,k+2,之間關于,F1,的相關，變量名相關、先讀后寫相關、反相關、,RW,相關、,WAR,相關等。,,(3),寫寫相關：,指令,k,與指令,k+2,左邊的,F1,之間的相關關系稱為：輸出相關、寫寫相關、,WW,相關、,WAW,相關或寫后再寫相關等。,,有時把,相關,稱為,“,冒險,”,(hazard),、,“,竟爭,”,,(competiti

47、on),等。,,在程序執(zhí)行過程中，只有避免相關，執(zhí)行結果才是正確的。,,三種數據相關可以用下列關系式來表示：,,對于寫讀相關,D(i) ∩ S(j) ≠,?,,,對于讀寫相關,S(i) ∩ D(j) ≠,?,,,對于寫寫相關,D(i) ∩ D(j) ≠,?,數據重定向方法,1.,三種數據相關的重定向,,重定向之前，,j,只能在,i,之后執(zhí)行。,,重定向之后，可以做到：,,(1),寫讀相關，,j,與,i,可以同時執(zhí)行,,即專用數據通路,,(2),寫寫相關，,先后順序無關,,(3),讀寫相關，,先后順序無關,,后兩種情況又稱為,“,變量換名技術,”,2.,變量換名技術,,用來自動消除,讀寫數據相關

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

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

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

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

52、順序是按照程序中指令排列順序進行的稱為順序發(fā)射,,順序完成,(in-order completion),與亂序完成,(out-order completion),：,指令完成順序是按照程序中指令排列順序進行的稱為順序完成,,多流水線的調度主要有三種方法：,,順序發(fā)射順序完成,,順序發(fā)射亂序完成,,亂序發(fā)射亂序完成,以如下,6,條指令組成的程序為例，說明這三種調度方法（,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,個數據相關，包括,2,個寫讀相關，,1,個讀寫相關和,1,個寫寫相關。,,1.,順序發(fā)射順序完成,,共用,10,個時鐘周期完成,,還有,8,個空閑的時鐘周期,2.,順序發(fā)射亂序完成,,總的執(zhí)行時間為,9,個時鐘周期，,,,節(jié)省了一個時鐘周期。少了,5,個空閑時鐘周期。,3.,亂序發(fā)射亂序完成（采用先行指令窗口，度,m=3,）,沒有空閑周期，功能部件得到充分利用。

54、,,總的執(zhí)行時間為,8,個周期，節(jié)省,2,個周期。,資源沖突,如果操作部件采用流水線結構，發(fā)生資源沖突的可能性很??；,,如果不采用流水線結構，發(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,個空閑周期

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

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

57、的特點,。,超標量處理機性能,單流水線普通標量處理機的指令級并行度記作,(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,超流水線處理機的兩種定義

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

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

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

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

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

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

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

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

66、量處理機上,,,可以只用一條指令：,C(10:1010)=A(10:1010) + B(10:1010),一條向量指令可處理Ｎ個或Ｎ對操作數,,在標量處理機上用,10,多條指令，其中有,8,條指令要循環(huán),1000,次。,,采用多寄存器結構的兩地址指令編寫程序,,存儲器采用字節(jié)編址方式，字長為,32,位,從標量到向量,在一般標量處理機中需要如下指令序列來實現（,A,、,B,、,C,分別是向量,a,、,b,、,c,在內存中的起始地址）：,START: LOAD R0, ST ;,讀循環(huán)初值,10,,,LOAD R1, ED ;,讀循環(huán)終值,1010,,,LOAD R2, L ;,讀內存地址增量,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