第5章 流水處理機

第一章 計算機系統(tǒng)結(jié)構(gòu)的基本概念第二章 數(shù)據(jù)表示與指令系統(tǒng)第三章 中斷與輸入輸出系統(tǒng)第四章 存儲體系第五章 重疊、流水和向量處理機第六章 并行處理機和相聯(lián)處理機第七章 多處理機第八章 具有現(xiàn)代特色的計算機1、并行性的含義： 并行性是指問題中具有可同時運算或操作的特性。同時性：兩個或多個事件在同一時刻發(fā)生；并發(fā)性：兩個或多個事件在同一時間間隔內(nèi)發(fā)生；引言：系統(tǒng)結(jié)構(gòu)中的并行性發(fā)展2、開發(fā)并行性的途徑：時間重疊：——讓多個處理過程在時間上錯開，輪流重疊地使用同一套硬件設(shè)備的各個部分，使之加快硬件使用的周轉(zhuǎn)來贏得速度。（流水線處理機）資源重復(fù)：——通過重復(fù)設(shè)置硬件資源來提高性能或可靠性。（并行處理機、相聯(lián)處理機）資源共享：——用軟件的方法讓多個用戶共用同一套資源，通過提高系統(tǒng)資源的利用率來提高系統(tǒng)的效率和性能。（多處理機）3、計算機系統(tǒng)的分類：SISD——單指令流單數(shù)據(jù)流SingleInstructionStreamSingleDataStream流水線處理機CUPUMMISCSDSCUISCSDSDSDSSIMD——單指令流多數(shù)據(jù)流SingleInstructionStreamMultipleDataStream并行處理機MISD——多指令流單數(shù)據(jù)流MultipleInstructionStreamSingleDataStreamISCSDSMIMD——多指令流多數(shù)據(jù)流MultipleInstructionStreamMultipleDataStream多處理機ISCSDS一、重疊方式1、指令的順序方式與重疊方式解釋指令的順序解釋方式指的是指令與指令之間順序串行，指令內(nèi)的各個微操作之間也是順序串行的。優(yōu)點：每條指令轉(zhuǎn)入下一條指令的時間關(guān)系是確定的，指令間相互的關(guān)聯(lián)關(guān)系易于得到控制和處理。缺點：程序解釋的速度低，系統(tǒng)內(nèi)各部件的時間利用率低。指令的重疊解釋方式是在相鄰的指令之間，讓取指令、分析指令、執(zhí)行指令等操作在時間上錯開重疊的進行，而指令內(nèi)部的微操作仍然是順序串行的。一次重疊：在任何時間都只有“執(zhí)行K”與“分析K+1”在時間上重疊。1234n1234n時間空間分析指令執(zhí)行指令采用“一次重疊”的好處是系統(tǒng)只需要一套指令分析部件和一套指令執(zhí)行部件，節(jié)省了硬件，也簡化了指令之間的相關(guān)控制。為了使“一次重疊”方式的系統(tǒng)能有較高的重疊效率，應(yīng)使“分析”和“執(zhí)行”的時間盡可能調(diào)整成一樣的。重疊解釋不能加快每條指令的解釋速度，但在硬件增加不多的情形下，可以加快相鄰兩條指令以及整段程序的解釋，使系統(tǒng)的性能價格比有顯著提高。2、重疊方式對計算機組成的要求為解決“分析K+1”、“執(zhí)行K”在重疊時的訪主存沖突，可采用的辦法：①、分別設(shè)置各自獨立編址的數(shù)據(jù)存儲器和指令存儲器，讓存、取操作數(shù)和取指令可同時訪存。缺點：增加了總線控制和軟件設(shè)計的負擔。②、讓主存用邏輯上統(tǒng)一編址的多分體交叉訪問的并行組成方式。缺點：可能發(fā)生分體沖突，而使并行度受到限制③、在硬件上，增設(shè)有一定容量的指令緩沖器和數(shù)據(jù)緩沖器，讓主存插空將預(yù)取的指令存入指令緩沖器，或?qū)⒁獙懭氲臄?shù)據(jù)暫時存入數(shù)據(jù)緩沖器中。目前，多采用第二、三種辦法的組合。3．“一次重疊”方式的相關(guān)控制指令相關(guān)：下一條指令的內(nèi)容取決于上一條指令的執(zhí)行結(jié)果。 條件轉(zhuǎn)移指令與后繼指令存在著相關(guān)性，會使重疊效率下降。因此，程序中應(yīng)盡量減少條件轉(zhuǎn)移指令的使用。在需要使用條件轉(zhuǎn)移指令時，可采用“延遲轉(zhuǎn)移”的技術(shù)，由編譯程序生成目標程序時，將條件轉(zhuǎn)移指令與其前面的指令交換位置，可使重疊效率不致下降。 另外因為指令在程序的執(zhí)行過程中允許被修改（本條指令要等到之前的指令執(zhí)行完后才能修改形成好）也可能造成指令相關(guān)。解決這種指令相關(guān)的根本辦法是在機器中規(guī)定指令在執(zhí)行過程中不允許修改。但是，為了滿足用戶編程的靈活性，需要修改指令時，可以設(shè)置類似IBM370的“執(zhí)行”指令，將指令相關(guān)轉(zhuǎn)成操作數(shù)相關(guān)，統(tǒng)一按操作數(shù)相關(guān)來處理。數(shù)相關(guān)：主存空間的數(shù)相關(guān)：它是在相鄰指令之間出現(xiàn)了對主存同一單元要求在先的指令必須先完成寫，在后的指令才能讀的“先寫后讀”相關(guān)。由于發(fā)生主存空間數(shù)相關(guān)的概率很低，為此可以采取推后后繼指令對相關(guān)單元的讀操作的辦法來解決。通用寄存器組的數(shù)相關(guān)：推后后繼指令的分析；設(shè)置“相關(guān)專用通道”BC運算器通用寄存器組數(shù)據(jù)總線相關(guān)專用通路

二、流水方式1、流水是重疊的引申“一次重疊”是把指令的解釋分成兩個子過程，讓相鄰的指令在時間上錯開重疊的解釋，因此，“一次重疊”對速度的提高最多也只是順序方式的兩倍。流水則是把指令的解釋分成更多個（m個）子過程，讓相鄰的m條指令的解釋在時間上錯開重疊。1234123412341234時間空間取指令指令譯碼取操作數(shù)指令執(zhí)行2、

流水線的分類部件級流水——處理機級流水——系統(tǒng)級流水部件機流水是指部件內(nèi)的各個子部件之間的流水，如分析部件內(nèi)部的取址、譯碼、地址形成和取數(shù)之間的流水；浮點加/減法運算器內(nèi)的求階差、對階、尾數(shù)加/減和尾數(shù)規(guī)格化之間的流水；Cache存儲器內(nèi)查地址映象表進行地址變換與訪物理Cache之間的流水處理機級流水是指構(gòu)成處理機的各個部件之間的流水，如取指、分析、執(zhí)行部件間的流水系統(tǒng)級流水是指處理機之間的流水，如宏流水，在任務(wù)、作業(yè)一級上的流水單功能流水——多功能流水單功能流水是指流水線內(nèi)各段固定連接，只能完成單一的一種功能多功能流水是指流水線中各個段可以有多種不同的連接，以實現(xiàn)多種不同的功能在多功能流水線的基礎(chǔ)上，靜態(tài)流水——動態(tài)流水靜態(tài)流水是指在流水線內(nèi)各個段于同一時間里只能按其中的一種功能流水，只有等各個段全部空閑后，才能切換成按另一種功能的連接來流水，把功能負擔加到軟件調(diào)整上。動態(tài)流水是指流水線的各個段可以同時為不同的功能服務(wù)，把功能負擔加到硬件控制上。123AABAABAAB123123123123123AAB輸入減階對階移位相加規(guī)格化相乘累加輸出時間空間線性流水——非線性流水線性流水線中各個段之間串行的連接，無反饋也無跳躍，每個任務(wù)流經(jīng)流水線中各個段均只有一次。非線性流水是指如果流水線中除有串行聯(lián)接的通路外，還有某種反饋回路，使一個任務(wù)流經(jīng)流水線時，需多次經(jīng)過某個段或越過某些段。1234向量流水機——標量流水機標量流水機則只有流水線，沒有向量數(shù)據(jù)表示，處理向量、數(shù)組時需要借用程序的循環(huán)和變址向量流水機是向量數(shù)據(jù)表示和流水線的結(jié)合3、流水線處理機的主要性能吞吐率和效率是反映流水機器性能的主要指標吞吐率指的是在單位時間內(nèi)，流水線機器所能處理的數(shù)據(jù)、指令或任務(wù)的數(shù)目效率是指流水線中設(shè)備實際使用時間占整個運行時間之比，也稱為流水線設(shè)備的時間利用率；從時—空圖上看，效率實際上就是n個任務(wù)占用的時—空區(qū)面積和m個段總的時—空區(qū)面積之比。12341234123412341234空間時間1234提高吞吐率的兩個措施：2123412341234123412341234空間時間1212223341、將瓶頸子過程再細化1342122231234123432141234空間時間12A2B2C342、重復(fù)設(shè)置多套瓶頸段并使之并聯(lián)1342A2B2C實際吞吐率：設(shè)一m段流水線的各段經(jīng)過時間均為△t0，則最大吞吐率TPmax是1/△t0；則完成n條指令共需要T=m*△t0+(n–1)*△t0

則實際吞吐率TP=n/(m*△t0+(n–1)*△t0)=Tpmax/(1+(m–1)/n)1234n1234n1234n1234n1234空間時間補充：用加速比表示流水線方式相對于非流水線順序串行方式速度提高的比值。非流水線順序串行方式：n*m*△t0

流水線方式：m*△t0+(n–1)*△t0

加速比：Sp=m/1+(m-1)/n結(jié)論：如果線性流水線的各段時間相同，僅當n>>m時，即連續(xù)流入的任務(wù)數(shù)n遠遠大于流水線子過程數(shù)m的時候，其加速比才能趨于最大值，為流水線的段數(shù)m。假設(shè)指令的解釋分取指、分析和執(zhí)行3步，每步的時間相應(yīng)為t取指t分析t執(zhí)行，分別計算下列情況下，執(zhí)行完100條指令所需時間的一般關(guān)系式：①順序方式；②僅執(zhí)行k與取址k+1重疊；③取址k+2分析k+1和執(zhí)行k流水；當t取指=t分析=2，t執(zhí)行=1當t取指=t執(zhí)行=5，t分析=2取分析E取分析E取分析E取分析Et取指+100t分析+99max｛t取指，t執(zhí)行｝+t執(zhí)行取分析E取分析E取分析E取分析E……取分析E取分析Et取指+max｛t取指，t分析｝+98max｛t取指，t分析，t執(zhí)行｝+max｛t分析，t執(zhí)行｝+t執(zhí)行設(shè)有兩個向量A和B，各有4個元素，要在如下圖所示的靜態(tài)雙功能流水線上，計算向量點積A·B（a1*b1+a2*b2+a3*b3+a4*b4）。其中，1→2→3→5組成加法流水線，1→4→5組成乘法流水線。又設(shè)每個流水線所經(jīng)過的時間均為△t0

，而且流水線的輸出結(jié)果可以直接返回到輸入或暫存于相應(yīng)的緩沖寄存器中，其延遲時間和功能切換所需的時間都可以忽略不計。請求出流水線從開始流入到結(jié)果流出這段時間的實際吞吐率TP和效率η。123541234+++1234++++++1234+++空間時間12345實際吞吐率：7/15加速比：24△t0/15△t0=1.6效率：24△t0/75△t0=0.32空間時間123412345++++12345++++12345++++12345++++【｛(A1+A2)+(A3+A4)｝+(A9+A10)】+｛(A5+A6)+(A7+A8)｝空間時間1234123456789123456789123456789A*(B+C*(D+E*F))+G*H=A*B+A*C*D+A*C*E*F+G*HA*CE*F1*D1*2A*BG*H5+34+6吞吐率：3/8；效率：3/8；空間時間1234123456789123456778899123456789A*(B+C*(D+E*F))+G*H=A*B+A*C*D+A*C*E*F+G*HA*CE*F1*D1*2A*BG*H5+34+6吞吐率：3/8；效率：3/8；空間時間12341234576891234566778899123457689A*(B+C*(D+E*F))+G*H=A*B+A*C*D+A*C*E*F+G*HA*CE*F1*D1*2A*BG*H5+34+6吞吐率：3/8；效率：3/8；A1*B1+A2*B2+A3*B3+A4*B4+A5*B5+A6*B6+A7*B7+A8*B8空間時間+++++++12345678空間時間⑴、（8+7）*5=75；+++++++12345678乘法加法乘法加法⑵、（2+7）*5=45；乘法加法1456714567145671456714567181818181812空間時間空間時間+++++++++++++++++++++++++++++++++++12345678123456781234567812345678123456781+2;3+4;5+6;12+7;34+8;56+127;348+125674、流水線的任務(wù)調(diào)度——非線性流水線預(yù)約表：二維的預(yù)約表其實就是一個任務(wù)在流水時的時空圖；延遲禁止表：將流水線中所有各段對一個任務(wù)流過時會爭用同一段的節(jié)拍間隔數(shù)匯集在一起，就構(gòu)成一個延遲禁止表；初始沖突向量：由延遲禁止表可轉(zhuǎn)換得到初始沖突向量；沖突向量中第I位的狀態(tài)用以表示與當時相隔I拍給流水線送入后繼任務(wù)是否會發(fā)生功能段的使用沖突；如果不會發(fā)生沖突，令該位為0，表示允許送入，否則，讓該位為1，表示禁止送入。如果每個任務(wù)通過流水線需要n拍，則沖突向量取n–1位。由初始沖突向量可以得到狀態(tài)轉(zhuǎn)移圖。預(yù)約表打√最多的行是流水線的性能瓶頸，其√的個數(shù)實際上限定了流水線可達到的最短平均間隔拍數(shù)。t0t1t2t3t4t5t6t7t8s1**s2**s3***s4**s5**123456123456121234345656123456123142536456t1t2t3t4t5t6t7t8t9s1**s2**s3***s4**s5**100011011010111110001111調(diào)度方案平均延遲2，53.52，74.5556，55.5666，76.5775，23.5257657576由初始狀態(tài)出發(fā)，構(gòu)成一種間隔拍數(shù)呈周期性重復(fù)的方案1000110100100011100011010000010010001101000000011000110100000010單功能流水線狀態(tài)圖禁止向量：8，1，3，4，5、流水機器的相關(guān)——全局性相關(guān)和局部性相關(guān)全局性相關(guān)：轉(zhuǎn)移指令與其后繼指令之間的相關(guān)發(fā)生全局性相關(guān)時，不僅不能同時解釋，還會使指令緩沖器所預(yù)取的指令全部作廢，重新花較長的時間再去訪問主存取出指令；它對流水線性能的下降有著至關(guān)重要的影響；局部性相關(guān)：指令相關(guān)、主存數(shù)相關(guān)、通用寄存器組的數(shù)相關(guān)、基（變）址值相關(guān)等；這些相關(guān)都只影響到使相關(guān)的指令在某些功能段上停留等待一段時間，不會影響到使流水線需要等待，去重新訪問主存取指令。這樣，它們對流水線的吞吐率和效率的下降的影響是局部的，所以稱為局部性相關(guān)。⑴、流水線全局性相關(guān)的處理①猜測法——猜選I+1和p中的一個分支繼續(xù)流入流水線；為了猜錯時使猜測流入流水線的那些指令都作廢其部分解釋，恢復(fù)成解釋之前的原始現(xiàn)場，我們使用后援寄存器—讓流入流水線的指令，其所有可能被破壞的原始內(nèi)容都保存在后援寄存器中，一旦猜錯了，只需很少的時間，用后援寄存器的內(nèi)容來恢復(fù)就可以了。為了猜錯后能盡快轉(zhuǎn)入p分支流水，可設(shè)置轉(zhuǎn)移目標指令緩沖器，以便在猜測流水的同時就預(yù)取p、p+1等指令，并將它們存入轉(zhuǎn)移目標指令緩沖器中。這樣，一旦猜錯時，就不必再去訪問存儲器，只需直接從轉(zhuǎn)移目標指令緩沖器中取出指令即可，以減少此時流水線的空等時間。②加快條件轉(zhuǎn)移時條件碼的生成包括在單條指令內(nèi)部條件碼的提前形成和在程序段內(nèi)所用分支條件碼的提前形成。提前知道程序?qū)⒘飨蚰膫€分支，就可以減少猜錯時，流水線效率的過分下降。也可以采用“延遲轉(zhuǎn)移”技術(shù)。依靠編譯技術(shù)，將轉(zhuǎn)移指令與其前面不相關(guān)的一條或多條指令對換一下位置，使成功轉(zhuǎn)移總是延遲到這一條或多條指令之后進行，就可以使轉(zhuǎn)移造成的流水線性能的損失降低到最小。③加快對短循環(huán)程序的處理如果發(fā)現(xiàn)是一個短循環(huán)程序，就可將整個循環(huán)程序中的各條指令一次性全部裝入指令緩沖器中，并暫時停止指令的預(yù)取操作，以減少不必要的訪存次數(shù)。同時，讓流水線的循環(huán)出口恒猜選循環(huán)分支?？臻g時間123412345ABC12345ABC12345ABc12345ABC⑵、流水線局部性相關(guān)的處理由于局部性相關(guān)都是因為出現(xiàn)“先寫后讀”引起的，因此，與重疊方式類似，可以采用推后對相關(guān)單元的讀操作和設(shè)置相關(guān)專用通路的辦法來解決。為了使流水線發(fā)生局部相關(guān)的指令在某個功能段處于停止等待時，后續(xù)不相關(guān)的指令可以越過它繼續(xù)向前流動，以保證流水線仍有較高的吞吐率和效率，可以采用異步流動控制方式——流入流水線的指令順序可以與流入流水線之前的指令順序不同流水線采用異步流動方式后，會產(chǎn)生“寫—寫”相關(guān)和“先讀后寫”相關(guān)。“寫—寫”相關(guān)：指令之間對同一寄存器或存儲單元，要求在先的指令應(yīng)先寫好，在后的指令才能寫入的關(guān)聯(lián)。“先讀后寫”相關(guān)：指令之間要求對同一寄存器或存儲單元在先的指令應(yīng)先讀出，在后的指令才能寫入的關(guān)聯(lián)。流水機器處理局部性相關(guān)的一種典型的基本結(jié)構(gòu)是IBM360/91。空間時間讀寫123345123345123345123345空間時間1234351234351234351234356、流水機器的中斷處理中斷和轉(zhuǎn)移一樣，都會使流水線斷流。由于發(fā)生中斷的概率遠比發(fā)生條件轉(zhuǎn)移的概率低，所以流水機器處理中斷的關(guān)鍵不在于如何縮短因中斷引起流水線斷流的時間，而是看如何保存好中斷時的斷點及中斷現(xiàn)場，以便在中斷返回后，能使程序從斷點處恢復(fù)正常工作?！安痪_斷點”法——不管第I條指令在哪一段發(fā)出中斷請求，讓未流入流水線的指令不再流入，而已進入流水線的指令繼續(xù)流完，然后再轉(zhuǎn)去執(zhí)行中斷處理程序，這種不精確的斷點對程序的設(shè)計和排錯很不利。IBM360/91“精確斷點”法——不論指令I(lǐng)是在流水線中的哪一段響應(yīng)中斷，給中斷處理程序的現(xiàn)場全都是對應(yīng)I的，I之后流入流水線的指令的原有現(xiàn)場都能恢復(fù)?！熬_斷點”法需要設(shè)置大量的后援寄存器，以保證流水線內(nèi)各條指令的原有現(xiàn)場都能保存和恢復(fù)。Amdahl470/V6D=A*(B+C)三、向量的流水處理和向量處理機橫向（水平）處理方式：逐個求結(jié)果向量的各個元素；縱向（垂直）處理方式：將兩個向量先全部運算完，得到一個中間結(jié)果向量后，再用此中間結(jié)果向量與其他向量運算。7+N+7+N+8+N=22+3N訪存取A送入V3寄存器組V0(B)+V1(C)送入V2

V2*V3送入V4

訪存取A送入V3寄存器組V0(B)+V1(C)送入V2

V2*V3送入V4

7+N+8+N=15+2N訪存取A送入V3寄存器組V0(B)+V1(C)送入V2

V2*V3送入V4

8+8+N=16+N在向量處理機上，每條向量指令的內(nèi)部都是流水的；鄰近多條向量指令之間如果既無流水線功能部件的使用沖突，也無向量寄存器組Vi的使用沖突，則這些向量指令都可以同時并行流水。如果相鄰的多條向量指令之間無功能部件使用沖突，只有向量寄存器組Vi的先寫后讀相關(guān)，可以通過鏈接，實現(xiàn)指令之間大部分時間并行流水；鏈接：將前面指令的結(jié)果向量直接鏈入后續(xù)指令所用的流水線，使多個流水線功能部件鏈接，構(gòu)成一條大的流水線，從而使處理機有更高的性能。如果后續(xù)指令的兩個源向量寄存器組恰好是先行兩條指令的結(jié)果寄存器組，只要前面這兩條指令能設(shè)法調(diào)整到同一時鐘周期得到一對分量時，可以實現(xiàn)鏈接。如果兩條向量指令的向量長度不等，則不能鏈接。四、指令級高度并行的超級處理機結(jié)構(gòu)特性標量超標量超流水超長指令字指令發(fā)射每周期1條每周期m條每周期1條*每周期1條是否與標量機兼容/是是否是否要軟件支持/是否是（編譯系統(tǒng)）時鐘周期是否與標量相同/是否（小于標量）是CPI>1<1>1*<1流水線結(jié)構(gòu)一條多條一條一條1、超標量(Superscalar)處理機：采用設(shè)置m條指令流水線同時并行，來實現(xiàn)度為m的。它是靠編譯時，由編譯程序來優(yōu)化編排指令的執(zhí)行順序，將可并行的指令搭配成組，硬件不調(diào)整所執(zhí)行指令的順序，以利于實現(xiàn)。2、超流水線(Superpipelining)處理機：采用多相的高頻時鐘。一臺度為m的超流水線處理機的時鐘只是基本機器周期的1/m。3、超長指令字(VLIW)處理機：將水平型微碼和超標量處理相結(jié)合。在編譯時，將多個能并行執(zhí)行的不相關(guān)或無關(guān)的操作組合在一起，形成一條有多個操作碼字段的超長指令字。運行時，直接控制機器中多個相互獨立的功能部件并行操作，來實現(xiàn)同時執(zhí)行多條指令。123456789101112123456789101112123456789101112取指分析執(zhí)行常規(guī)標量流水處理機481237112610159481237112610159481237112610159取指分析執(zhí)行超標量處理機（m=4）4812371126101594812371126101511481237112610159取指分析執(zhí)行5.75超流水線處理機（m=4）123123123123123123取指分析執(zhí)行超長指令字處理機（m=4）復(fù)習(xí)指導(dǎo)：第五章重疊、流水和向量處理機概述：本章著重講述在計算機組成設(shè)計中，如何通過采用重疊和流水等控制方式來提高解釋機器語言程序的速度。在此基礎(chǔ)上，講述向量的流水處理方式、向量流水機的結(jié)構(gòu)。結(jié)合CRAY-1向量流水處理機，介紹通過讓向量指令之間并行或鏈接執(zhí)行來進一步提高流水機的性能。最后簡要介紹在指令級上發(fā)展高度并行的超標量處理機、超長指令字處理機和超流水線處理機的工作原理?；疽螅?、領(lǐng)會重疊方式的工作原理——采用重疊工作方式時，對計算機在組成設(shè)計上的要求；