5.4-流水線技術(shù)-吳學(xué)涯

1、5.4 流水線技術(shù),5.4.1 并行處理技術(shù)概述5.4.2 流水線技術(shù)5.4.3 流水線的分類5.4.4 流水計算機(jī)的組成5.4.5 流水計算機(jī)的時空圖5.4.6 指令的相關(guān)性,,為了充分發(fā)揮計算機(jī)的效能，滿足不斷增長的應(yīng)用需求，近幾十年來，CPU的新技術(shù)層出不窮基于時間并行原理的流水線技術(shù)，使計算機(jī)系統(tǒng)結(jié)構(gòu)產(chǎn)生了重大的變革CPU技術(shù)的發(fā)展，還包括優(yōu)化編譯，采用好的指令調(diào)度算法，重新組織指令執(zhí)行順序，降低相關(guān)技術(shù)帶來的干擾

2、，以及開發(fā)多發(fā)射技術(shù)（即設(shè)法在一個時鐘周期內(nèi)發(fā)出多條指令）等等,5.4.1 并行處理技術(shù)概述,早期計算機(jī)采用串行處理計算機(jī)各個操作只能串行完成，任一時刻只能進(jìn)行一個操作并行處理使多個操作能同時進(jìn)行，大大提高了計算機(jī)速度廣義地講，并行性有兩種含義同時性：指兩個以上事件在同一時刻發(fā)生并發(fā)性：兩個以上事件在同一時間間隔內(nèi)發(fā)生,1. 時間并行,時間并行指時間重疊讓多個處理過程在時間上相互錯開，輪流重疊地使用同一套硬件設(shè)備的各個部分，

3、以加快硬件周轉(zhuǎn)而贏得速度時間并行的實(shí)現(xiàn)方式是采用流水處理部件這是一種非常經(jīng)濟(jì)實(shí)用的并行技術(shù)，能保證計算機(jī)系統(tǒng)具有較高的性能價格比目前的高性能計算機(jī)幾乎無一例外地使用了流水技術(shù),2. 空間并行,空間并行指資源重復(fù)以資源的重復(fù)配置來大幅度提高計算機(jī)的處理速度大規(guī)模和超大規(guī)模集成電路的迅速發(fā)展，為空間并行技術(shù)帶來了巨大生機(jī)，成為目前實(shí)現(xiàn)并行處理的一個主要途徑空間并行技術(shù)主要體現(xiàn)在多處理器系統(tǒng)和多處理機(jī)系統(tǒng)但是在單處理器系統(tǒng)中也得

4、到了廣泛應(yīng)用,3. 時間并行+空間并行,指時間重疊和資源重復(fù)的綜合應(yīng)用既采用時間并行性又采用空間并行性相對而言，這種并行技術(shù)帶來的高速效益是最好的現(xiàn)代計算機(jī)往往同時具有時間并行性和空間并行性,5.4.2 流水線技術(shù),在任一條指令的執(zhí)行過程中，各個功能部件都會隨著指令執(zhí)行的進(jìn)程而呈現(xiàn)出時忙時閑的現(xiàn)象要加快計算機(jī)的工作速度，就應(yīng)使各個功能部件并行工作以各自可能的高速度同時、不停地工作，使得各部件的操作在時間上重疊進(jìn)行，實(shí)現(xiàn)流水式作

5、業(yè),,計算機(jī)的流水線（Pipeline）工作方式將一個計算任務(wù)細(xì)分成若干個子任務(wù)，每個子任務(wù)都由專門的功能部件進(jìn)行處理，一個計算任務(wù)的各個子任務(wù)由流水線上各個功能部件輪流進(jìn)行處理（即各子任務(wù)在流水線的各個功能階段并發(fā)執(zhí)行），最終完成工作這樣，不必等到上一個計算任務(wù)完成，就可以開始下一個計算任務(wù)的執(zhí)行,流水線的硬件基本結(jié)構(gòu)由一系列串聯(lián)的功能部件（Si）組成各個功能部件之間設(shè)有高速緩沖寄存器（L），暫存上一功能部件的處理結(jié)果，同時

6、又能接受新的處理任務(wù)在一個統(tǒng)一的時鐘（C）控制下，計算任務(wù)從功能部件的一個功能段流向下一個功能段所有功能段同時對不同的數(shù)據(jù)進(jìn)行不同的處理，各個處理步驟并行地操作,,,當(dāng)任務(wù)連續(xù)不斷地輸入流水線時，在流水線的輸出端便連續(xù)不斷地輸出執(zhí)行結(jié)果流水線達(dá)到不間斷流水的穩(wěn)定狀態(tài)，實(shí)現(xiàn)子任務(wù)級并行當(dāng)指令流不能順序執(zhí)行時，流水過程會中斷（即斷流）為保證流水過程的工作效率，流水過程不應(yīng)經(jīng)常斷流在一個流水過程中，實(shí)現(xiàn)各個子過程的各個

7、功能段所需要的時間應(yīng)該盡可能保持相等，以避免產(chǎn)生瓶頸，導(dǎo)致流水線斷流,,流水線技術(shù)本質(zhì)將一個重復(fù)的時序過程分解成若干個子過程每一個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行采用流水線技術(shù)通過硬件實(shí)現(xiàn)并行操作后，就某一條指令而言，其執(zhí)行速度并沒有加快但就程序執(zhí)行過程的整體而言，程序執(zhí)行速度大大加快流水線技術(shù)適合于大量的重復(fù)性的處理,5.4.3 流水線的分類,1.按級別分類2.按數(shù)據(jù)分類,1.按級別分類,一個計算機(jī)系

8、統(tǒng)可以在不同的并行等級上采用流水線技術(shù)按照流水的級別，可以把流水線分為以下幾類：1）算術(shù)流水線2）指令流水線3）處理機(jī)流水線,1）算術(shù)流水線,算術(shù)流水線指運(yùn)算操作步驟的并行，是部件級流水線可以把處理器的算術(shù)邏輯部件分段，使各種數(shù)據(jù)類型均能進(jìn)行流水操作如流水加法器、流水乘法器、流水除法器等也可以將具體的算術(shù)邏輯運(yùn)算分成多個階段，分別由不同的部件實(shí)現(xiàn)將浮點(diǎn)加法操作分成求階差、對階、尾數(shù)相加以及結(jié)果規(guī)格化4個子過程來進(jìn)行流水處

9、理現(xiàn)代計算機(jī)中已廣泛采用了流水的算術(shù)運(yùn)算器。,2）指令流水線,指令流水線表示指令步驟的并行，是處理器級流水線通常可以將指令的執(zhí)行過程劃分為取指令、譯碼、執(zhí)行、取數(shù)、寫回5個并行處理的過程段，并按流水方式組織起來，形成指令流水線目前，幾乎所有的高性能計算機(jī)都采用了指令流水線,3）處理機(jī)流水線,處理機(jī)流水線指程序步驟的并行，又稱為宏流水線處理機(jī)流水線由一串級聯(lián)的處理機(jī)構(gòu)成流水線的各個過程段，每臺處理機(jī)負(fù)責(zé)某一特定的任務(wù)處理機(jī)流水線

10、大多應(yīng)用在多機(jī)系統(tǒng)中，隨著高檔微處理器芯片的出現(xiàn)，構(gòu)造處理機(jī)流水線變得更為容易,2. 按數(shù)據(jù)分類,按照數(shù)據(jù)表示，流水線可分為標(biāo)量流水線和向量流水線1）標(biāo)量流水線只能對標(biāo)量數(shù)據(jù)進(jìn)行流水處理2）向量流水線具有向量指令，能對向量數(shù)據(jù)的各元素進(jìn)行流水處理,5.4.4 流水計算機(jī)的組成,現(xiàn)代流水計算機(jī)系統(tǒng)的組成存儲器體系流水CPU,1. 存儲器體系,為了解決存儲器的速度匹配問題，使存儲器的存取時間與流水線其他各過程段的速度相匹配，一

11、般都采用多模塊交叉存儲器在現(xiàn)有的流水線計算機(jī)中，存儲器幾乎都是采用交叉存取的方式工作的高速緩存Cache的普遍采用，也大大提高了CPU對存儲器的訪問速度,2. 流水CPU,CPU內(nèi)部通常按流水線方式進(jìn)行組織由指令部件、指令隊列、執(zhí)行部件3部分組成這3個功能部件可以組成一個3級流水線1）指令部件2）指令隊列3）執(zhí)行部件,1）指令部件,指令部件本身又構(gòu)成一個流水線即指令流水線由取指令、指令譯碼、執(zhí)行指令、訪存取數(shù)、結(jié)果寫回

12、等幾個過程段組成,2）指令隊列,指令隊列是一個先進(jìn)先出（FIFO）的寄存器棧用于存放經(jīng)過譯碼的指令和取來的操作數(shù)同時也是由若干個過程段組成的流水線,3）執(zhí)行部件,執(zhí)行部件可以具有多個算術(shù)邏輯運(yùn)算部件這些部件本身又用流水線方式構(gòu)成當(dāng)執(zhí)行部件正在執(zhí)行第I條指令時，指令隊列中存放著I+1，I+2，…，I+k條指令與此同時，指令部件正在取第I+k+1條指令,執(zhí)行段的速度匹配問題，通常采用并行的運(yùn)算部件以及部件流水線的方式來解決一般

13、采用的方法：①將執(zhí)行部件分為定點(diǎn)執(zhí)行部件和浮點(diǎn)執(zhí)行部件兩個可并行執(zhí)行的部分，分別處理定點(diǎn)運(yùn)算指令和浮點(diǎn)運(yùn)算指令②在浮點(diǎn)執(zhí)行部件中，包括浮點(diǎn)加法部件和浮點(diǎn)乘/除法部件，它們可以同時執(zhí)行不同的指令③浮點(diǎn)運(yùn)算部件均以流水線方式工作,5.4.5 流水計算機(jī)的時空圖,描述流水線的工作過程，通常采用時（間）空（間）圖的方法在時空圖中，縱坐標(biāo)表示指令序列橫坐標(biāo)表示時間,1.指令流水線過程段,流水CPU中一個指令周期的任務(wù)分解取指令（IF

14、）、指令譯碼（ID）、指令執(zhí)行（EX）、訪存取數(shù)（MEM）、結(jié)果寫回（WB）5個子過程（過程段）流水線由這5個串聯(lián)的過程段組成各個過程段之間設(shè)有高速緩沖寄存器，以暫時保存上一過程段子任務(wù)處理的結(jié)果在統(tǒng)一的時鐘信號控制下，數(shù)據(jù)從一個過程段流向相鄰的過程段,,2.非流水計算機(jī)工作方式,非流水計算機(jī)的時空圖FLASH演示,,,對于非流水計算機(jī)而言，上一條指令的5個子過程全部執(zhí)行完畢后才能開始下一條指令每隔5個時鐘周期才有一個輸出結(jié)

15、果用15個時鐘周期完成3條指令，每條指令平均用時5個時鐘周期非流水線工作方式控制比較簡單，但部件利用率較低，系統(tǒng)工作速度較慢,3.標(biāo)量流水計算機(jī)工作方式,標(biāo)量（Scalar）流水計算機(jī)只有一條指令流水線時空圖FLASH演示,,對標(biāo)量流水計算機(jī)而言，上一條指令與下一條指令的5個子過程在時間上可以重疊執(zhí)行當(dāng)流水線滿載時，每一個時鐘周期就可以輸出一個結(jié)果用9個時鐘周期完成5條指令每條指令平均用時1.8個時鐘周期采用標(biāo)量

16、流水線工作方式，雖然每條指令的執(zhí)行時間并未縮短，但CPU運(yùn)行指令的總體速度卻能成倍提高作為提速的代價，需要增加部分硬件才能實(shí)現(xiàn)標(biāo)量流水,4.超標(biāo)量流水計算機(jī)工作方式,超標(biāo)量（Superscalar）流水計算機(jī)具有兩條以上的指令流水線時空圖FLASH演示,,,當(dāng)流水線滿載時，每一個時鐘周期可以執(zhí)行2條以上的指令用9個時鐘周期完成10條指令每條指令平均用時0.9個時鐘周期超標(biāo)量流水計算機(jī)是時間并行技術(shù)和空間并行技術(shù)的綜合應(yīng)

17、用,5.4.6指令的相關(guān)性,指令流水線的一個特點(diǎn)流水線中的各條指令之間存在一些相關(guān)性，使得指令的執(zhí)行受到影響要使流水線發(fā)揮高效率，就要使流水線連續(xù)不斷地流動，盡量不出現(xiàn)斷流情況然而，由于流水過程中存在的相關(guān)性沖突，斷流現(xiàn)象是不可避免的,1.數(shù)據(jù)相關(guān),在流水計算機(jī)中，指令的處理是重疊進(jìn)行的前一條指令還沒結(jié)束，第二、三條指令就陸續(xù)開始工作由于多條指令的重疊處理，當(dāng)后繼指令所需的操作數(shù)剛好是前一指令的運(yùn)算結(jié)果時，便發(fā)生數(shù)據(jù)相關(guān)沖突

18、由于這兩條指令的執(zhí)行順序直接影響到操作數(shù)讀取的內(nèi)容，必須等前一條指令執(zhí)行完畢后才能執(zhí)行后一條指令在這種情況下，這兩條指令就是數(shù)據(jù)相關(guān)的,數(shù)據(jù)相關(guān)是由于指令之間存在數(shù)據(jù)依賴性而引起的根據(jù)指令間對同一寄存器讀和寫操作的先后次序關(guān)系，可將數(shù)據(jù)相關(guān)性分為三種類型寫后讀（Read-After-Write，RAW）相關(guān)讀后寫（Write-After-Read，WAR）相關(guān)寫后寫（Write-After-Write，WAW）相關(guān)解決數(shù)據(jù)相

19、關(guān)沖突的辦法⑴采用編譯的方法⑵由硬件監(jiān)測相關(guān)性的存在，采用數(shù)據(jù)旁路技術(shù)設(shè)法解決,,⑴采用編譯的方法編譯程序通過在兩條相關(guān)指令之間插入其他不相關(guān)的指令（或空操作指令）而推遲指令的執(zhí)行，使數(shù)據(jù)相關(guān)消失，從而產(chǎn)生沒有相關(guān)性的程序代碼這種方式簡單，但降低了運(yùn)行效率,,⑵由硬件監(jiān)測相關(guān)性的存在，采用數(shù)據(jù)旁路技術(shù)設(shè)法解決當(dāng)前一條指令要寫入寄存器而下一條指令要讀取同一個寄存器時，在前一條指令執(zhí)行完畢、結(jié)果數(shù)據(jù)還未寫入寄存器前，由內(nèi)部數(shù)據(jù)通路

20、把該結(jié)果數(shù)據(jù)直接傳遞給下一條指令也就是說，下一條指令所需的操作數(shù)不再通過讀取寄存器獲得，而是直接獲取這種方式效率較高，但控制較為復(fù)雜,【例5-5】流水線中有三類數(shù)據(jù)相關(guān)沖突：寫后讀（RAW）相關(guān)、讀后寫（WAR）相關(guān)、寫后寫（WAW）相關(guān)。判斷以下三組指令各存在哪種類型的數(shù)據(jù)相關(guān)。(1)I1: ADD R1，R2，R3 ；(R2)+(R3)?R1I2: SUB R4，R1，R5 ；(R1)-(R5)?R4(2)I3

21、: STA M(x)，R3 ；(R3)?M(x)，M(x)是存儲器單元I4: ADD R3，R4，R5 ；(R4)+(R5)?R3(3)I5: MUL R3，R1，R2 ；(R1)×(R2)?R3I6: ADD R3，R4，R5 ；(R4)+(R5)?R3,【解】(1)I1指令運(yùn)算結(jié)果應(yīng)先寫入R1，然后在I2指令中讀出R1內(nèi)容。由于I2指令進(jìn)入流水線，變成I2指令在I1指令寫入R1前就讀出R1內(nèi)容，發(fā)生RA

22、W相關(guān)(2)I3指令應(yīng)先讀出R3內(nèi)容并存入存儲單元M(x)，然后在I4指令中將運(yùn)算結(jié)果寫入R3。但由于I4指令進(jìn)入流水線，變成I4指令在I3指令讀出R3內(nèi)容前就寫入R3，發(fā)生WAR相關(guān)。(3)如果I6指令的加法運(yùn)算完成時間早于I5指令的乘法運(yùn)算時間，變成指令I(lǐng)6在指令I(lǐng)5寫入R3前就寫入R3，導(dǎo)致R3的內(nèi)容錯誤，發(fā)生WAW相關(guān),2.資源相關(guān),資源相關(guān)，是指多條指令進(jìn)入流水線后在同一機(jī)器周期內(nèi)爭用同一個功能部件所發(fā)生的沖突在標(biāo)量流

23、水計算機(jī)中在第4個時鐘周期時，第1條指令處于訪存取數(shù)（MEM）階段，而第4條指令處于取指令（IF）階段如果數(shù)據(jù)和指令存放在同一存儲器中，且存儲器只有一個端口，便會發(fā)生這兩條指令爭用存儲器的沖突,,,因?yàn)槊恳粭l指令都可能需要2次訪問存儲器（讀指令和讀寫數(shù)據(jù)），在指令流水過程中，可能會有2條指令同時需要訪問存儲器，導(dǎo)致資源相關(guān)沖突解決資源相關(guān)沖突的一般辦法是增加資源增設(shè)一個存儲器，將指令和數(shù)據(jù)分別放在兩個存儲器中,3.控制相關(guān),控

24、制相關(guān)沖突是由轉(zhuǎn)移指令引起的當(dāng)執(zhí)行轉(zhuǎn)移指令時，依據(jù)轉(zhuǎn)移條件的產(chǎn)生結(jié)果，可能順序取下一條指令，也可能轉(zhuǎn)移到新的目標(biāo)地址取指令若轉(zhuǎn)移到新的目標(biāo)地址取指令，則指令流水線將被排空，并等待轉(zhuǎn)移指令形成下一條指令的地址，以便讀取新的指令，這就使得流水線發(fā)生斷流為了減小轉(zhuǎn)移指令對流水線性能的影響，通常采用兩種轉(zhuǎn)移處理技術(shù),⑴延遲轉(zhuǎn)移法,由編譯程序重排指令序列來實(shí)現(xiàn)基本思想是“先執(zhí)行再轉(zhuǎn)移”發(fā)生轉(zhuǎn)移時并不排空指令流水線，而是繼續(xù)完成下幾條指令