第5章 流水處理機

1、,1、并行性的含義：并行性是指問題中具有可同時運算或操作的特性。同時性：兩個或多個事件在同一時刻發(fā)生；并發(fā)性：兩個或多個事件在同一時間間隔內發(fā)生；,引言：系統(tǒng)結構中的并行性發(fā)展,,2、開發(fā)并行性的途徑：時間重疊：——讓多個處理過程在時間上錯開，輪流重疊地使用同一套硬件設備的各個部分，使之加快硬件使用的周轉來贏得速度。（流水線處理機）資源重復：——通過重復設置硬件資源來提高性能或可靠性。（并行處理機、相聯(lián)處理機）資源共享：—

2、—用軟件的方法讓多個用戶共用同一套資源，通過提高系統(tǒng)資源的利用率來提高系統(tǒng)的效率和性能。（多處理機）,3、計算機系統(tǒng)的分類：SISD——單指令流單數(shù)據流Single Instruction Stream Single Data Stream流水線處理機,,SIMD——單指令流多數(shù)據流Single Instruction Stream Multiple Data Stream并行處理機,MISD——多指令流單數(shù)據流Multip

3、le Instruction Stream Single Data Stream,MIMD——多指令流多數(shù)據流Multiple Instruction Stream Multiple Data Stream多處理機,一、重疊方式 1、指令的順序方式與重疊方式解釋 指令的順序解釋方式指的是指令與指令之間順序串行，指令內的各個微操作之間也是順序串行的。優(yōu)點：每條指令轉入下一條指令的時間關系是確定的，指令間相互的

4、關聯(lián)關系易于得到控制和處理。缺點：程序解釋的速度低，系統(tǒng)內各部件的時間利用率低。,指令的重疊解釋方式是在相鄰的指令之間，讓取指令、分析指令、執(zhí)行指令等操作在時間上錯開重疊的進行，而指令內部的微操作仍然是順序串行的。一次重疊：在任何時間都只有“執(zhí)行K”與“分析K+1”在時間上重疊。,采用“一次重疊”的好處是系統(tǒng)只需要一套指令分析部件和一套指令執(zhí)行部件，節(jié)省了硬件，也簡化了指令之間的相關控制。為了使“一次重疊”方式的系統(tǒng)能有較高的重疊效

5、率，應使“分析”和“執(zhí)行”的時間盡可能調整成一樣的。 重疊解釋不能加快每條指令的解釋速度，但在硬件增加不多的情形下，可以加快相鄰兩條指令以及整段程序的解釋，使系統(tǒng)的性能價格比有顯著提高。,2、重疊方式對計算機組成的要求為解決“分析K+1”、“執(zhí)行K”在重疊時的訪主存沖突，可采用的辦法：①、分別設置各自獨立編址的數(shù)據存儲器和指令存儲器，讓存、取操作數(shù)和取指令可同時訪存。缺點：增加了總線控制和軟件設計的負擔。②、讓主存

6、用邏輯上統(tǒng)一編址的多分體交叉訪問的并行組成方式。缺點：可能發(fā)生分體沖突，而使并行度受到限制③、在硬件上，增設有一定容量的指令緩沖器和數(shù)據緩沖器，讓主存插空將預取的指令存入指令緩沖器，或將要寫入的數(shù)據暫時存入數(shù)據緩沖器中。 目前，多采用第二、三種辦法的組合。,3．“一次重疊”方式的相關控制指令相關：下一條指令的內容取決于上一條指令的執(zhí)行結果。條件轉移指令與后繼指令存在著相關性，會使重疊效率下降。因此，程序中應盡量減少條件轉移指

7、令的使用。在需要使用條件轉移指令時，可采用“延遲轉移”的技術，由編譯程序生成目標程序時，將條件轉移指令與其前面的指令交換位置，可使重疊效率不致下降。另外因為指令在程序的執(zhí)行過程中允許被修改（本條指令要等到之前的指令執(zhí)行完后才能修改形成好）也可能造成指令相關。解決這種指令相關的根本辦法是在機器中規(guī)定指令在執(zhí)行過程中不允許修改。但是，為了滿足用戶編程的靈活性，需要修改指令時，可以設置類似IBM 370 的“執(zhí)行”指令，將指令相關轉成操作

8、數(shù)相關，統(tǒng)一按操作數(shù)相關來處理。,數(shù)相關：主存空間的數(shù)相關：它是在相鄰指令之間出現(xiàn)了對主存同一單元要求在先的指令必須先完成寫，在后的指令才能讀的“先寫后讀”相關。由于發(fā)生主存空間數(shù)相關的概率很低，為此可以采取推后后繼指令對相關單元的讀操作的辦法來解決。通用寄存器組的數(shù)相關： 推后后繼指令的分析； 設置“相關專用通道”,,二、流水方式 1、流水是重疊的引申“一次重疊”是把指令的解釋分成兩個子過程，讓

9、相鄰的指令在時間上錯開重疊的解釋，因此，“一次重疊”對速度的提高最多也只是順序方式的兩倍。流水則是把指令的解釋分成更多個（m個）子過程，讓相鄰的m條指令的解釋在時間上錯開重疊。,2、  流水線的分類部件級流水——處理機級流水——系統(tǒng)級流水部件機流水是指部件內的各個子部件之間的流水，如分析部件內部的取址、譯碼、地址形成和取數(shù)之間的流水；浮點加/減法運算器內的求階差、對階、尾數(shù)加/減和尾數(shù)規(guī)格化之間的流水；Cache存儲器內查

10、地址映象表進行地址變換與訪物理Cache之間的流水處理機級流水是指構成處理機的各個部件之間的流水，如取指、分析、執(zhí)行部件間的流水系統(tǒng)級流水是指處理機之間的流水，如宏流水，在任務、作業(yè)一級上的流水,單功能流水——多功能流水單功能流水是指流水線內各段固定連接，只能完成單一的一種功能多功能流水是指流水線中各個段可以有多種不同的連接，以實現(xiàn)多種不同的功能在多功能流水線的基礎上，靜態(tài)流水——動態(tài)流水靜態(tài)流水是指在流水線內各個段于同一時

11、間里只能按其中的一種功能流水，只有等各個段全部空閑后，才能切換成按另一種功能的連接來流水，把功能負擔加到軟件調整上。動態(tài)流水是指流水線的各個段可以同時為不同的功能服務，把功能負擔加到硬件控制上。,時間,空間,線性流水——非線性流水線性流水線中各個段之間串行的連接，無反饋也無跳躍，每個任務流經流水線中各個段均只有一次。非線性流水是指如果流水線中除有串行聯(lián)接的通路外，還有某種反饋回路，使一個任務流經流水線時，需多次經過某個段或越過某些

12、段。,向量流水機——標量流水機標量流水機則只有流水線，沒有向量數(shù)據表示，處理向量、數(shù)組時需要借用程序的循環(huán)和變址向量流水機是向量數(shù)據表示和流水線的結合,3、流水線處理機的主要性能吞吐率和效率是反映流水機器性能的主要指標吞吐率指的是在單位時間內，流水線機器所能處理的數(shù)據、指令或任務的數(shù)目效率是指流水線中設備實際使用時間占整個運行時間之比，也稱為流水線設備的時間利用率；從時—空圖上看，效率實際上就是n個任務占用的時—空區(qū)面積和m

13、個段總的時—空區(qū)面積之比。,空間,時間,提高吞吐率的兩個措施：,,2,空間,時間,,1、將瓶頸子過程再細化,空間,時間,2、重復設置多套瓶頸段并使之并聯(lián),實際吞吐率：,設一 m 段流水線的各段經過時間均為△t 0，則最大吞吐率TPmax是 1/ △t 0 ；則完成n條指令共需要T = m* △t 0 + (n –1)* △t 0 則實際吞吐率 TP = n / (m* △t 0 + (n –1)* △t 0 ) = Tpmax /

14、 (1 + (m –1) / n),空間,時間,補充：用加速比表示流水線方式相對于非流水線順序串行方式速度提高的比值。非流水線順序串行方式： n*m* △t 0 流水線方式：m* △t 0 + (n –1)* △t 0 加速比：Sp = m / 1 + (m -1) / n結論：如果線性流水線的各段時間相同，僅當 n >> m 時，即連續(xù)流入的任務數(shù)n遠遠大于流水線子過程數(shù)m的時候，其加速比才能趨于最大值，為流水線

15、的段數(shù)m。,設有兩個向量A和B，各有4個元素，要在如下圖所示的靜態(tài)雙功能流水線上，計算向量點積A·B（a1*b1+a2*b2+a3*b3+a4*b4）。其中，1→2→3→5組成加法流水線，1→4→5組成乘法流水線。又設每個流水線所經過的時間均為△t 0 ，而且流水線的輸出結果可以直接返回到輸入或暫存于相應的緩沖寄存器中，其延遲時間和功能切換所需的時間都可以忽略不計。請求出流水線從開始流入到結果流出這段時間的實際吞吐率TP和效

16、率η 。,空間,時間,實際吞吐率：7/15加速比：24 △t 0 / 15 △t 0 = 1.6效率： 24 △t 0 / 75 △t 0 = 0.32,t取指+100t分析+99max｛t取指，t執(zhí)行｝+t執(zhí)行,…,…,t取指+ max｛t取指，t分析｝+ 98max｛t取指，t分析，t執(zhí)行｝+max｛t分析，t執(zhí)行｝+t執(zhí)行,【｛(A1+A2)+(A3+A4)｝+(A9+A10)】+｛(A5+A6)+(A7+A8)｝,空

17、間,時間,A*(B+C*(D+E*F))+G*H = A*B+A*C*D+A*C*E*F+G*H,A*C,E*F,1*D,1*2,A*B,G*H,5+3,4+6,吞吐率：3/8；效率：3/8；,A1*B1+ A2*B2+ A3*B3+ A4*B4+ A5*B5+ A6*B6+ A7*B7+ A8*B8,空間,時間,空間,時間,⑴、（8+7）*5=75；,乘法,加法,乘法,加法,⑵、（2+7）*5=45；,,乘法,加法,,12,20,空間

18、,時間,空間,時間,,,1+2; 3+4; 5+6; 12+7; 34+8; 56+127; 348+12567,4、流水線的任務調度——非線性流水線預約表：二維的預約表其實就是一個任務在流水時的時空圖；延遲禁止表：將流水線中所有各段對一個任務流過時會爭用同一段的節(jié)拍間隔數(shù)匯集在一起，就構成一個延遲禁止表；初始沖突向量：由延遲禁止表可轉換得到初始沖突向量；沖突向量中第I位的狀態(tài)用以表示與當時相隔 I 拍給流水線送入后繼任務是否會發(fā)

19、生功能段的使用沖突；如果不會發(fā)生沖突，令該位為0，表示允許送入，否則，讓該位為1，表示禁止送入。如果每個任務通過流水線需要n拍，則沖突向量取n – 1位。由初始沖突向量可以得到狀態(tài)轉移圖。預約表打√ 最多的行是流水線的性能瓶頸，其√ 的個數(shù)實際上限定了流水線可達到的最短平均間隔拍數(shù)。,,由初始狀態(tài)出發(fā)，構成一種間隔拍數(shù)呈周期性重復的方案,禁止向量：8，1，3，4，,5、流水機器的相關——全局性相關和局部性相關全局性相關：轉移指令

20、與其后繼指令之間的相關發(fā)生全局性相關時，不僅不能同時解釋，還會使指令緩沖器所預取的指令全部作廢，重新花較長的時間再去訪問主存取出指令；它對流水線性能的下降有著至關重要的影響；局部性相關：指令相關、主存數(shù)相關、通用寄存器組的數(shù)相關、基（變）址值相關等；這些相關都只影響到使相關的指令在某些功能段上停留等待一段時間，不會影響到使流水線需要等待，去重新訪問主存取指令。這樣，它們對流水線的吞吐率和效率的下降的影響是局部的，所以稱為局部性相關。

21、,⑴、流水線全局性相關的處理① 猜測法——猜選 I + 1和 p 中的一個分支繼續(xù)流入流水線；為了猜錯時使猜測流入流水線的那些指令都作廢其部分解釋，恢復成解釋之前的原始現(xiàn)場，我們使用后援寄存器—讓流入流水線的指令，其所有可能被破壞的原始內容都保存在后援寄存器中，一旦猜錯了，只需很少的時間，用后援寄存器的內容來恢復就可以了。為了猜錯后能盡快轉入 p 分支流水，可設置轉移目標指令緩沖器，以便在猜測流水的同時就預取 p、p+1 等指令，

22、并將它們存入轉移目標指令緩沖器中。這樣，一旦猜錯時，就不必再去訪問存儲器，只需直接從轉移目標指令緩沖器中取出指令即可，以減少此時流水線的空等時間。,② 加快條件轉移時條件碼的生成 包括在單條指令內部條件碼的提前形成和在程序段內所用分支條件碼的提前形成。提前知道程序將流向哪個分支，就可以減少猜錯時，流水線效率的過分下降。也可以采用“延遲轉移”技術。依靠編譯技術，將轉移指令與其前面不相關的一條或多條指令對換一下位置，使成功轉

23、移總是延遲到這一條或多條指令之后進行，就可以使轉移造成的流水線性能的損失降低到最小。③ 加快對短循環(huán)程序的處理 如果發(fā)現(xiàn)是一個短循環(huán)程序，就可將整個循環(huán)程序中的各條指令一次性全部裝入指令緩沖器中，并暫時停止指令的預取操作，以減少不必要的訪存次數(shù)。同時，讓流水線的循環(huán)出口恒猜選循環(huán)分支。,⑵、流水線局部性相關的處理由于局部性相關都是因為出現(xiàn)“先寫后讀”引起的，因此，與重疊方式類似，可以采用推后對相關單元的讀操作和設置相

24、關專用通路的辦法來解決。為了使流水線發(fā)生局部相關的指令在某個功能段處于停止等待時，后續(xù)不相關的指令可以越過它繼續(xù)向前流動，以保證流水線仍有較高的吞吐率和效率，可以采用異步流動控制方式——流入流水線的指令順序可以與流入流水線之前的指令順序不同流水線采用異步流動方式后，會產生“寫—寫”相關和“先讀后寫”相關?！皩憽獙憽毕嚓P：指令之間對同一寄存器或存儲單元，要求在先的指令應先寫好，在后的指令才能寫入的關聯(lián)?！跋茸x后寫”相關：指令之間要

25、求對同一寄存器或存儲單元在先的指令應先讀出，在后的指令才能寫入的關聯(lián)。流水機器處理局部性相關的一種典型的基本結構是IBM 360/91。,,,空間,時間,6、流水機器的中斷處理 中斷和轉移一樣，都會使流水線斷流。由于發(fā)生中斷的概率遠比發(fā)生條件轉移的概率低，所以流水機器處理中斷的關鍵不在于如何縮短因中斷引起流水線斷流的時間，而是看如何保存好中斷時的斷點及中斷現(xiàn)場，以便在中斷返回后，能使程序從斷點處恢復正常工作。

26、 “不精確斷點”法——不管第I 條指令在哪一段發(fā)出中斷請求，讓未流入流水線的指令不再流入，而已進入流水線的指令繼續(xù)流完，然后再轉去執(zhí)行中斷處理程序，這種不精確的斷點對程序的設計和排錯很不利。 IBM 360/91 “精確斷點”法——不論指令I 是在流水線中的哪一段響應中斷，給中斷處理程序的現(xiàn)場全都是對應I 的，I之后流入流水線的指令的原有現(xiàn)場都能恢復?！熬_斷點”法需要設置大量的后援寄存器，以保證流水線內各條指令

27、的原有現(xiàn)場都能保存和恢復。 Amdahl 470/V6,,,,,,,,D=A*(B+C),,,三、向量的流水處理和向量處理機,橫向（水平）處理方式：逐個求結果向量的各個元素；縱向（垂直）處理方式：將兩個向量先全部運算完，得到一個中間結果向量后，再用此中間結果向量與其他向量運算。,,,7+N+7+N+8+N=22+3N,訪存取A送入V3寄存器組,V0(B)+V1(C) 送入V2,V2*V3 送入V4,,,7+N+8+

28、N=15+2N,訪存取A送入V3寄存器組,V0(B)+V1(C) 送入V2,V2*V3 送入V4,,,8+8+N=16+N,訪存取A送入V3寄存器組,V0(B)+V1(C) 送入V2,V2*V3 送入V4,在向量處理機上，每條向量指令的內部都是流水的；鄰近多條向量指令之間如果既無流水線功能部件的使用沖突，也無向量寄存器組Vi的使用沖突，則這些向量指令都可以同時并行流水。如果相鄰的多條向量指令之間無功能部件使用沖突，只有向量寄

29、存器組Vi的先寫后讀相關，可以通過鏈接，實現(xiàn)指令之間大部分時間并行流水；鏈接：將前面指令的結果向量直接鏈入后續(xù)指令所用的流水線，使多個流水線功能部件鏈接，構成一條大的流水線，從而使處理機有更高的性能。如果后續(xù)指令的兩個源向量寄存器組恰好是先行兩條指令的結果寄存器組，只要前面這兩條指令能設法調整到同一時鐘周期得到一對分量時，可以實現(xiàn)鏈接。如果兩條向量指令的向量長度不等，則不能鏈接。,四、指令級高度并行的超級處理機,1、超標量(Supe

30、rscalar)處理機：采用設置m條指令流水線同時并行，來實現(xiàn)度為m的。它是靠編譯時，由編譯程序來優(yōu)化編排指令的執(zhí)行順序，將可并行的指令搭配成組，硬件不調整所執(zhí)行指令的順序，以利于實現(xiàn)。2、超流水線(Superpipelining)處理機：采用多相的高頻時鐘。一臺度為m的超流水線處理機的時鐘只是基本機器周期的1/m。 3、超長指令字(VLIW)處理機：將水平型微碼和超標量處理相結合。在編譯時，將多個能并行執(zhí)行的不相關或無關的操

31、作組合在一起，形成一條有多個操作碼字段的超長指令字。運行時，直接控制機器中多個相互獨立的功能部件并行操作，來實現(xiàn)同時執(zhí)行多條指令。,取指,分析,執(zhí)行,常規(guī)標量流水處理機,,,取指,,,,分析,執(zhí)行,超標量處理機（m = 4）,,,,,,取指,分析,執(zhí)行,5.75,,超流水線處理機（m = 4）,,取指,分析,執(zhí)行,,超長指令字處理機（m = 4）,復習指導：第五章 重疊、流水和向量處理機概述：本章著重講述在計算機組成設計中，如

32、何通過采用重疊和流水等控制方式來提高解釋機器語言程序的速度。在此基礎上，講述向量的流水處理方式、向量流水機的結構。結合CRAY-1向量流水處理機，介紹通過讓向量指令之間并行或鏈接執(zhí)行來進一步提高流水機的性能。最后簡要介紹在指令級上發(fā)展高度并行的超標量處理機、超長指令字處理機和超流水線處理機的工作原理。,基本要求：1、領會重疊方式的工作原理——采用重疊工作方式時，對計算機在組成設計上的要求；“一次重疊”方式的定義及好處；掌握在“一次重疊

33、”方式工作的機器上，對指令相關、主存操作數(shù)相關、通用寄存器組的數(shù)相關、通用寄存器組的變（基）址值相關等的定義和各自的處理辦法；領會設置相關專用通路的目的及其適用的場合；在給出指令之間各種微操作時間重疊關系的要求之后，能夠熟練地計算出連續(xù)執(zhí)行完N條指令需要花費的全部時間。2、領會流水方式的工作原理——了解從不同的角度對流水線的分類和定義；熟練掌握有關流水線時空圖的畫法；在給出的流水線上，能夠計算出流水的最大吞吐率，及具體題目所能達到的實

34、際吞吐率、效率和加速比；掌握為消除流水線速度性能瓶頸可采用的兩種不同途徑的時空圖的畫法、并能計算出相應吞吐率和效率；在雙功能靜態(tài)流水線上，根據給出的具體計算式，能調整其操作的流入順序，在滿足盡可能高的性能條件下，畫出執(zhí)行此計算式相應的流水時空圖。,3、掌握流水機器對局部性相關的處理方法——熟悉流水線在異步流動時，指令之間發(fā)生先寫后讀、先讀后寫、寫—寫相關的定義。以IBM360/91為例，能綜述出在標量流水機上，處理局部性相關和全局性相關

35、時，為提高吞吐率和效率可采用的各種方法。4、熟練掌握在單功能非線性流水線上所采用的任務流入流水線的最佳調度方案，求出此時的極限吞吐率。按最佳調度方案實際調入流水線若干個任務后，能畫出在此情況下流水線工作的時空圖，并計算出實際的吞吐率和效率。5、了解向量有哪三種處理方式，哪些處理方式適合于流水處理。在CRAY-1向量流水處理機上，給出若干條向量指令后，能夠分析出這些向量指令之間，哪些可以并行；哪些雖然不能完全并行，但可以鏈接；哪些只能

36、串行；能夠計算出這些向量指令全部執(zhí)行所需要的最少拍數(shù)。6、了解超標量、超長指令字、超流水線三種處理機在指令級上并行的工作原理。給出指令數(shù)和并行的度數(shù)，能畫出各自的工作時空圖，并能計算出所需要的時間以及各自相對于在度為1的常規(guī)標量流水處理機上的加速比。,重點：1、“一次重疊”方式中，各種相關的處理；2、流水線的時空圖和性能分析；3、流水的局部性相關的處理；全局性相關的處理和對中斷的處理；4、單功能非線性流水線的調度；5、向量處