流水線原理及其在CPU設(shè)計(jì)中的應(yīng)用

第6章流水線原理及其在CPU設(shè)計(jì)中的應(yīng)用國(guó)家級(jí)規(guī)劃教材張代遠(yuǎn)計(jì)算機(jī)組成原理教程（第二版）第6章流水線原理及其在CPU設(shè)計(jì)中的應(yīng)用流水線技術(shù)是重要的加快處理器運(yùn)算速度的基本技術(shù)之一。本章介紹了流水線的基本概念、原理。線性流水線原理、性能分析非線性流水線原理、性能分析通過模型機(jī)給出了CPU指令級(jí)流水線的具體實(shí)施方案。相關(guān)概念及相關(guān)處理結(jié)構(gòu)相關(guān)數(shù)據(jù)相關(guān)控制相關(guān)26.1概述來看一個(gè)例子假設(shè)有4個(gè)工人要到醫(yī)院去體檢，每個(gè)人都要按照順序檢查內(nèi)科、外科、五官科。怎樣做？見圖示。36.1概述流水線：流水線是一種并行工作方式，它有以下特點(diǎn)：有一批可以重復(fù)運(yùn)行的任務(wù)；每一個(gè)任務(wù)能被分解成多個(gè)子任務(wù)；使用多個(gè)功能部件；不同的功能部件完成不同的子任務(wù)；多個(gè)功能部件并行運(yùn)行。46.1概述計(jì)算機(jī)中怎樣引入流水線技術(shù)？計(jì)算機(jī)級(jí)流水；處理器級(jí)流水；指令級(jí)流水。本章研究的是指令級(jí)流水線56.2指令流水線概念及指令的重疊運(yùn)行方式為了能夠?qū)崿F(xiàn)指令級(jí)流水工作，必須將指令的整個(gè)運(yùn)行階段劃分成幾個(gè)子功能段。一種粗略的劃分方式為：取指令階段、譯碼階段、執(zhí)行階段（見圖6.1）。重疊概念：將每一條指令的整個(gè)運(yùn)行階段分解為更小的功能段，使得多條指令在時(shí)間上并行運(yùn)行，稱為時(shí)間重疊，簡(jiǎn)稱為重疊。61.順序運(yùn)行方式順序運(yùn)行方式：設(shè)總共有n條指令需要運(yùn)行。若第i條指令與第i+1條指令的各功能段之間都沒有時(shí)間上的重疊。當(dāng)?shù)趇條指令與第i+1條指令之間沒有等待時(shí)間時(shí)（見圖6.2），這樣的串行運(yùn)行方式稱為順序運(yùn)行方式。順序運(yùn)行方式運(yùn)行n條指令所用的時(shí)間為（見圖6.2）6.2指令流水線概念及指令的重疊運(yùn)行方式(6.1)76.2指令流水線概念及指令的重疊運(yùn)行方式2.一次重疊運(yùn)行方式指令的一次重疊：第i條指令與第i+1條指令有一個(gè)功能段在時(shí)間上重疊，稱為指令的一次重疊（見圖6.3）。86.2指令流水線概念及指令的重疊運(yùn)行方式設(shè)重疊部分的工作時(shí)間相等，則完成n條指令時(shí)間為（見圖6.3）比較（6.1）式與（6.2）式，當(dāng)n>1時(shí)有(6.2)（6.3）96.2指令流水線概念及指令的重疊運(yùn)行方式3.二次重疊運(yùn)行方式指令的二次重疊：第i條指令與第i+1條指令有兩個(gè)功能段在時(shí)間上重疊，稱為指令的二次重疊（見圖6.4）。106.2指令流水線概念及指令的重疊運(yùn)行方式如果重疊部分時(shí)間相等，則運(yùn)行n條指令所用的時(shí)間為（見圖6.4）。顯然有（6.4）116.2指令流水線概念及指令的重疊運(yùn)行方式于是，當(dāng)n>1時(shí)有因此，指令的二次重疊運(yùn)行速度要高于一次重疊的運(yùn)行速度；指令的一次重疊運(yùn)行速度要高于順序運(yùn)行的速度?？梢?，相鄰指令重疊段數(shù)越多，指令的運(yùn)行速度就越快。（6.5）126.2指令流水線概念及指令的重疊運(yùn)行方式指令級(jí)流水線指令以流水線方式工作的前提在硬件上能將整個(gè)指令的運(yùn)行階段分解為一些更小的子功能段；指令也能劃分成對(duì)應(yīng)于硬件子功能段的子任務(wù)；為了能夠完成指令的運(yùn)行，子功能段的輸出數(shù)據(jù)要能被其他子功能段所使用。因此，需要在各個(gè)子功能段之間加上狀態(tài)部件（見圖6.5）。請(qǐng)觀察模型機(jī)的指令級(jí)流水線136.2指令流水線概念及指令的重疊運(yùn)行方式流水線的瓶頸若各個(gè)子功能段的工作時(shí)間不相等，則工作時(shí)間長(zhǎng)的子功能段成為流水線的“瓶頸功能段”。圖6.6給出了具有瓶頸功能段的流水線的例子。站在輸出端看，整個(gè)流水線的速度取決于速度最慢的子功能段，快速子功能段不能充分發(fā)揮能力。146.2指令流水線概念及指令的重疊運(yùn)行方式兩個(gè)基本概念：指令周期：指令從開始到運(yùn)行完畢所使用的最短時(shí)間，即采用非流水線運(yùn)行方式下完整運(yùn)行一條指令的最短時(shí)間。流水周期：設(shè)流水線方式下，若每一個(gè)功能段所需最短時(shí)間相等，則該最短時(shí)間稱為流水周期。若功能段所需時(shí)間不等，則選擇瓶頸段經(jīng)歷時(shí)間作為流水周期。156.3時(shí)空?qǐng)D常采用時(shí)空?qǐng)D來描述流水線的工作過程。見圖6.7。時(shí)空?qǐng)D反映了流水線的時(shí)間-空間關(guān)系。在時(shí)空?qǐng)D中，橫坐標(biāo)是流水線的運(yùn)行時(shí)間；縱坐標(biāo)是流水線的空間，即各子功能段。假設(shè)一個(gè)浮點(diǎn)流水線加法器可以分解為求階差、對(duì)階、尾數(shù)加、規(guī)格化四個(gè)子功能段，就可以畫出流水線的時(shí)空?qǐng)D（見圖6.8）。16線性流水線和非線性流水線線性流水線：各個(gè)功能段串連，數(shù)據(jù)從一個(gè)功能段輸出，流入另一個(gè)功能段，每一個(gè)功能段流過一次，僅流過一次。見圖6.9。非線性流水線：除了串行連接外，還有反饋回路。見圖6.10。6.4流水線的分類176.4流水線的分類單功能流水線與多功能流水線單功能流水線：各功能段之間只能進(jìn)行固定的連接，只完成一種功能。多功能流水線：各功能段之間可以進(jìn)行不同的連接，實(shí)現(xiàn)不同功能。圖6.11給出了一個(gè)實(shí)例18（6.6）吞吐率：指在單位時(shí)間內(nèi)完成任務(wù)數(shù)量或輸出結(jié)果數(shù)量式中n為任務(wù)數(shù)；Tk

為k段流水線處理完n個(gè)任務(wù)所有時(shí)間。TP也稱為流水線的實(shí)際吞吐率。6.5流水線的性能指標(biāo)與線性流水線性能分析吞吐率的一般定義式19

6.5流水線的性能指標(biāo)與線性流水線性能分析加速比：順序工作方式所用時(shí)間與流水方式所用時(shí)間的比值。式中Tk表示k段流水線按照流水線方式處理完n個(gè)任務(wù)所需要的時(shí)間，Ts為按照順序運(yùn)行方式處理完這n個(gè)任務(wù)所需要的時(shí)間。（6.7）加速比的一般定義式206.5流水線的性能指標(biāo)與線性流水線性能分析效率：流水線的各個(gè)功能段的利用率。η的分子是流水線功能段“忙”區(qū)占用的面積，分母是“忙”區(qū)和“空閑”區(qū)的面積之和。圖6.12可以幫助理解該公式。（6.8）216.5.1線性流水線的性能分析線性流水線的吞吐率假設(shè)線性流水線的各段工作時(shí)間相等，記為Δt

，輸入的n個(gè)任務(wù)連續(xù)，則一條k段線性流水線的吞吐率TP可以由下面公式計(jì)算：（6.10）226.5.1線性流水線的性能分析線性流水線吞吐率的上確界（工程上稱為最大吞吐率）因?yàn)門P是n的一元函數(shù)，而k>1，求導(dǎo)得說明TP(n)是n的嚴(yán)格單調(diào)增函數(shù)，所以上確界（最大吞吐率）為236.5.1線性流水線的性能分析一般而言，假設(shè)某一線性流水線有k個(gè)功能段，每個(gè)功能段的工作時(shí)間分別是Δti（i=1,2,…,k），則其吞吐率為(6.15)246.5.1線性流水線的性能分析具有瓶頸段的線性流水線的吞吐率的上確界是（6.16）256.5.1線性流水線的性能分析事實(shí)上，線性流水線的吞吐率要低于最大吞吐率，主要原因：線性流水線存在“裝入”和“排空”時(shí)間；輸入的任務(wù)往往是不連續(xù)的；程序本身存在數(shù)據(jù)相關(guān)。266.5.1線性流水線的性能分析線性流水線的加速比式中Tk為k段流水線按照流水線的運(yùn)行方式處理完n個(gè)任務(wù)所用時(shí)間，TS為按照順序運(yùn)行方式完這n個(gè)任務(wù)所用的時(shí)間。(6.17)276.5.1線性流水線的性能分析由于k>1，所以

故S(n)是n的嚴(yán)格單調(diào)增函數(shù)，所以加速比的上確界Smax為(6.18)(6.19)286.5.1線性流水線的性能分析結(jié)論：當(dāng)n>>k時(shí)，線性流水線各段工作時(shí)間相等的情況下，線性流水線的最大加速比近似等于該線性流水線的段數(shù)。根據(jù)加速比公式可以畫出圖6.17的曲線?？梢钥闯鰊較大時(shí)加速比接近于它的漸近線。k越多，它能夠獲得的加速比理論值越大，但是n實(shí)際不可能很大，原因是：296.5.1線性流水線的性能分析實(shí)際應(yīng)用的影響一般程序存在數(shù)據(jù)相關(guān)、轉(zhuǎn)移、中斷等情況，使連續(xù)輸入的n受到限制。物理實(shí)現(xiàn)實(shí)現(xiàn)成本；寄存器數(shù)量；布線長(zhǎng)度。306.5.1線性流水線的性能分析一般而言，每個(gè)功能段的工作時(shí)間為，

則k段線性流水線完成n個(gè)連續(xù)任務(wù)的實(shí)際加速比為(6.20)316.5.1線性流水線的性能分析流水線的效率效率反映資源利用率。并行系統(tǒng)效率的一般概念，涉及到可擴(kuò)展性，等效率函數(shù)等概念。326.5.1線性流水線的性能分析各功能段的工作時(shí)間相等的線性流水線的效率為上面的效率表達(dá)式也是n的嚴(yán)格單調(diào)增函數(shù)，故其上確界為(6.22)(6.21)336.5.1線性流水線的性能分析各功能段的工作時(shí)間不相等的效率(6.23)346.5.1線性流水線的性能分析每一個(gè)功能加權(quán)后，得到：(6.24)356.5.2線性流水線的特點(diǎn)流水線中處理的必須是連續(xù)任務(wù)。每一個(gè)任務(wù)分解為幾個(gè)有聯(lián)系的子任務(wù)，每一個(gè)子任務(wù)由一個(gè)專門的功能部件實(shí)現(xiàn)。每一個(gè)功能部件后面都要有一個(gè)緩沖寄存器，用于保存本段的運(yùn)行結(jié)果。流水線中各段的時(shí)間應(yīng)盡量相等，否則，產(chǎn)生瓶頸問題。366.6非線性流水線6.6.1引言 非線性流水線中存在回路，不能像線性流水線那樣每隔一個(gè)流水周期輸入一個(gè)任務(wù)，否則，會(huì)出現(xiàn)流水線（或功能部件）沖突問題。非線性流水線的調(diào)度就是要提供一個(gè)方案，按照該方案所確定的流水周期向流水線中輸入新任務(wù)，各功能部件都不發(fā)生沖突，而且流水線的性能指標(biāo)達(dá)到最高。376.6.2預(yù)約表幾個(gè)名詞：流線連接：相鄰功能段之間的前向直接連接線。見圖6.18的S1到S2和S2到S3之間的連接線。前饋連接：不相鄰功能段之間的前向直接連接線。見圖6.18的S1到S3之間的連接線。反饋連接：功能段之間的反向連接線見圖6.18的S3到S2之間的連接線，S3到S1之間的連接線。386.6.2預(yù)約表預(yù)約表：圖6.19和圖6.20畫出了圖6.18給出的非線性流水線的X功能和Y功能的各個(gè)功能段被使用的情況，這兩個(gè)圖中的表就是預(yù)約表，描述了一個(gè)功能在運(yùn)行過程中數(shù)據(jù)流通過流水線的時(shí)間與空間（各功能段）之間的關(guān)系。396.6.2預(yù)約表預(yù)約表的行數(shù)表示功能段數(shù)，列數(shù)表示給定功能的運(yùn)行時(shí)間。橫坐標(biāo)表示流水線的工作時(shí)間，單位為流水周期?？v坐標(biāo)表示流水線的功能段。X和Y表示該功能段在這一流水周期處于的工作狀態(tài)。每一張預(yù)約表對(duì)應(yīng)一個(gè)特定功能的運(yùn)行過程。一條非線性流水線一般需要一個(gè)結(jié)構(gòu)圖和預(yù)約圖來共同表示。406.6.3啟動(dòng)距離分析啟動(dòng)距離：向一條非線性流水線的輸入端輸入兩個(gè)相鄰任務(wù)之間的流水周期數(shù)。禁止啟動(dòng)距離：引起沖突的啟動(dòng)距離。一些啟動(dòng)距離會(huì)產(chǎn)生沖突，另一些不會(huì)產(chǎn)生沖突。會(huì)產(chǎn)生沖突的啟動(dòng)距離實(shí)例見例6.1，該例中啟動(dòng)距離為2、5均可產(chǎn)生沖突，預(yù)約表分別見圖6.21、圖6.22。416.6.3啟動(dòng)距離分析禁止向量：將預(yù)約表中的每一行中任意兩個(gè)標(biāo)記之間的距離都算出，去掉重復(fù)的，求得一個(gè)10進(jìn)制數(shù)列，將該數(shù)列按照遞減方式排列成一個(gè)向量，稱為禁止向量，記為Vf。求出圖6.19的禁止向量Vf＝(7,5,4,2)。允許啟動(dòng)距離：不會(huì)引起沖突的啟動(dòng)距離。允許啟動(dòng)序列：由允許啟動(dòng)距離構(gòu)成的數(shù)列。426.6.3啟動(dòng)距離分析允許啟動(dòng)循環(huán)：當(dāng)一個(gè)啟動(dòng)序列是一個(gè)循環(huán)數(shù)列時(shí)，這樣的循環(huán)數(shù)列稱為允許啟動(dòng)循環(huán)。啟動(dòng)循環(huán)的平均允許啟動(dòng)距離：其中dav為啟動(dòng)循環(huán)的平均啟動(dòng)距離，C

為啟動(dòng)循環(huán)階，di(i=1,2,...,C)為啟動(dòng)循環(huán)的啟動(dòng)距離。恒定循環(huán)：一階啟動(dòng)循環(huán)又稱為恒定循環(huán)。436.6.4迭加原理與無沖突調(diào)度方法非線性流水線無沖突調(diào)度的目標(biāo)是找出平均允許啟動(dòng)距離最小的啟動(dòng)循環(huán)。根據(jù)該原理導(dǎo)出狀態(tài)圖的畫法規(guī)則。零輸入調(diào)度向量：某時(shí)刻舊任務(wù)對(duì)后繼任務(wù)影響綜合效果，記為：446.6.4迭加原理與無沖突調(diào)度方法零狀態(tài)調(diào)度向量：假設(shè)在某一時(shí)刻已經(jīng)進(jìn)入但還沒有流出流水線的任務(wù)總是，并假設(shè)為空，即只考慮新任務(wù)對(duì)后繼任務(wù)調(diào)度的影響時(shí)，用二進(jìn)制向量表示，稱為零狀態(tài)調(diào)度向量。456.6.4迭加原理與無沖突調(diào)度方法

迭加原理：假設(shè)在某一時(shí)刻已經(jīng)進(jìn)入但還沒有流出流水線的任務(wù)總數(shù)是，同時(shí)考慮新、舊任務(wù)對(duì)后繼任務(wù)調(diào)度的影響時(shí)，綜合效果用二進(jìn)制向量表示，它是零輸入調(diào)度向量與零狀態(tài)調(diào)度向量按位求邏輯或的運(yùn)算結(jié)果（證明見教材)466.6.4迭加原理與無沖突調(diào)度方法由(6.30)得到遞推公式為了保證流水線不沖突，后繼任務(wù)的調(diào)度應(yīng)該是允許距離，得到：（6.32）（6.31）476.6.4迭加原理與無沖突調(diào)度方法將（6.32）式代入（6.31）式得到迭加原理數(shù)學(xué)表達(dá)的遞推公式：（6.34）486.6.4迭加原理與無沖突調(diào)度方法將（6.32）式代入（6.31）式得到迭加原理數(shù)學(xué)表達(dá)的另一種遞推公式：（6.34）式反映了兩個(gè)相鄰任務(wù)的調(diào)度向量之間的關(guān)系，而（6.35）式反映了兩個(gè)相鄰任務(wù)的零輸入調(diào)度向量之間的關(guān)系。（6.35）496.6.4迭加原理與無沖突調(diào)度方法零狀態(tài)調(diào)度向量的求解方法：先根據(jù)預(yù)約表求得禁止向量。將零狀態(tài)調(diào)度向量表示成一個(gè)維的二進(jìn)制向量，如果是禁止啟動(dòng)距離，則規(guī)定；如果是允許啟動(dòng)距離，則規(guī)定，顯然總有，對(duì)應(yīng)于最大禁止啟動(dòng)距離（中最大的那個(gè)）。506.6.4迭加原理與無沖突調(diào)度方法引入記號(hào)表示初始調(diào)度向量，得到一般無沖突調(diào)度方法：(1)將初始調(diào)度向量送入一個(gè)m+1位具有邏輯右移功能的移位寄存器；(2)當(dāng)從移位寄存器移出的位為0時(shí)，用移位寄存器中的值與零狀態(tài)調(diào)度向量作“按位或”運(yùn)算，得到一個(gè)新的調(diào)度向量；516.6.4迭加原理與無沖突調(diào)度方法(3)若移位寄存器移出的位為1，不作任何處理；(4)對(duì)于(2)和(3)重復(fù)m+1次；(5)對(duì)于中間形成的每一個(gè)新的調(diào)度向量，按(2)和(3)的方法做。526.6.4迭加原理與無沖突調(diào)度方法無沖突調(diào)度方法特殊情況－零狀態(tài)調(diào)度向量是常數(shù)根據(jù)前面的討論知道，僅僅考慮作用，即任務(wù)剛剛進(jìn)入流水線時(shí)(時(shí)刻)，流水線中沒有任何其他舊任務(wù)（即在時(shí)刻流水線為空）時(shí)后繼任務(wù)的調(diào)度向量。應(yīng)該指出的是，如果在流水線的整個(gè)工作過程中，預(yù)約表沒有改變，則與任務(wù)無關(guān)，即536.6.4迭加原理與無沖突調(diào)度方法于是可以將看成常向量，并記為Z。因此有此時(shí)(6.34)可以寫成：(6.37)546.6.4迭加原理與無沖突調(diào)度方法如果假設(shè)在第一個(gè)X1輸入流水線之前，流水線是空的，在這種情況下，滿足如下初始條件：此時(shí)按照（6.37）式有：(6.38)556.6.4迭加原理與無沖突調(diào)度方法根據(jù)（6.37）式、（6.38）式得到特殊情況下無沖突調(diào)度方法：將零狀態(tài)調(diào)度向量Z送入一個(gè)m+1位具有邏輯右移功能的移位寄存器；當(dāng)從移位寄存器移出的位為0時(shí)，用移位寄存器中的值與零狀態(tài)調(diào)度向量做“按位或”運(yùn)算，得到一個(gè)新的調(diào)度向量；若移位寄存器移出的位為1，不作任何處理；566.6.4迭加原理與無沖突調(diào)度方法對(duì)于2和3重復(fù)m+1次；對(duì)于中間形成的每一個(gè)新的調(diào)度向量，按2和3的方法做。關(guān)于允許啟動(dòng)距離d的討論576.6.4迭加原理與無沖突調(diào)度方法允許啟動(dòng)距離的最大值是：將最大禁止啟動(dòng)距離的范圍代入上式有：于是，允許啟動(dòng)距離的取值范圍為：(6.39)(6.40)(6.41)586.6.4迭加原理與無沖突調(diào)度方法以圖6.19為例示例運(yùn)用迭加原理尋找狀態(tài)圖調(diào)度方法：假設(shè)一批任務(wù)X1,X2,…,Xn要無沖突地輸入流水線，并假設(shè)在第一個(gè)任務(wù)X1輸入流水線之前，流水線是空的，將第一個(gè)任務(wù)X1進(jìn)入時(shí)刻作為初始時(shí)刻，即T(X1+0)。則零狀態(tài)調(diào)度向量Z=(01011010)就反映了X1剛剛輸入流水線后，準(zhǔn)備向流水線輸入任務(wù)X2

的允許和禁止流水周期數(shù)。由于Z=(01011010)的1、3、6、8位是0，表示經(jīng)過1、3、6、8個(gè)流水周期后可以無沖突地向流水線輸入新任務(wù)X2。596.6.4迭加原理與無沖突調(diào)度方法于是新任務(wù)X2流入流水線地時(shí)刻為，這時(shí)，流水線中已經(jīng)存在有兩個(gè)任務(wù)X2和X3，后面的新任務(wù)再流入流水線時(shí)，在流水線中的沖突情況與任務(wù)X2有關(guān)，還與已經(jīng)遷移了d個(gè)流水周期的任務(wù)X1有關(guān)。對(duì)于X3的后繼任務(wù)X4、X4的后繼任務(wù)X5等等，情況相同。根據(jù)迭加原理推出的無沖突調(diào)度方法，得到以下幾個(gè)無沖突調(diào)度方案。在下面的例子中，假設(shè)算子“→”的優(yōu)先級(jí)高于“∨”的優(yōu)先級(jí)。606.6.4迭加原理與無沖突調(diào)度方法啟動(dòng)循環(huán)（1,8）啟動(dòng)循環(huán)（3）啟動(dòng)循環(huán)（6）把上面的工作畫在一張圖上，可以直觀的看出流水線的調(diào)度方案。這張圖稱為狀態(tài)圖。見圖6.27。狀態(tài)圖說明了流水線持續(xù)輸入任務(wù)的情況下流水線的允許啟動(dòng)距離狀態(tài)的變遷。616.7非線性流水線的性能分析6.7.1引言時(shí)空?qǐng)D在分析非線性流水線時(shí)并不方便，而且不能反映各參數(shù)之間的內(nèi)在聯(lián)系。本書作者給出了計(jì)算非線性流水線參數(shù)公式，并給出了各參數(shù)之間關(guān)系的數(shù)學(xué)表達(dá)式。626.7非線性流水線的性能分析6.7.2非線性流水線的Tk的求法假設(shè)任務(wù)總數(shù)為n。啟動(dòng)循環(huán)為(d1+d2+…+dC)，啟動(dòng)距離的個(gè)數(shù)為C，非線性流水線的功能段數(shù)為K，預(yù)約表中的標(biāo)記總數(shù)為K1，預(yù)約表中的列數(shù)為N，每個(gè)功能段的運(yùn)行時(shí)間是Δt，Tk表示對(duì)某一K段非線性流水線，輸入N

個(gè)任務(wù)時(shí)從輸入到流出該非線性流水線所經(jīng)歷的時(shí)間。636.7非線性流水線的性能分析設(shè)某時(shí)刻Tstart=t，向流水線輸入初始任務(wù)，則向流水線輸入的第一個(gè)新任務(wù)的起始時(shí)刻是t+d1，向流水線輸入的第2個(gè)新任務(wù)的時(shí)刻為t+d1+d2，如此推下去，輸入C

個(gè)新任務(wù)的起始時(shí)刻是t+d1+d2+…+dC

，輸入C+1個(gè)新任務(wù)的起始時(shí)刻是t+(d1+d2+…+dC)+d1，向流水線輸入的第n+1個(gè)新任務(wù)的起始時(shí)刻是646.7非線性流水線的性能分析設(shè)總?cè)蝿?wù)為n，分別是X0,X1,…,Xn-1，并設(shè)

根據(jù)(6.42)式有：其中表示最后一個(gè)任務(wù)流出流水線的結(jié)束時(shí)刻，N表示最后一個(gè)任務(wù)的排空流水周期數(shù)由（6.43）式可以得到：(6.43)(6.44)656.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系非線性流水線的吞吐率有以下公式當(dāng)各段同權(quán)時(shí)，效率公式為非線性流水線的加速比公式:（6.45）（6.46）（6.47）666.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系由上面幾個(gè)公式得到非線性流水線的吞吐率、效率、加速比之間的關(guān)系:（6.48）（6.49）676.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系通過上面兩個(gè)公式可以得到線性流水線的對(duì)應(yīng)關(guān)系，對(duì)于線性有，所以（6.51）（6.50）686.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系定義：輸入任務(wù)時(shí)的非性流水線的吞吐率、效率、加速比分別記為。利用（6.45）式~（6.47）式可以求得：（6.52）696.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系類似的可以求得：（6.53）（6.54）706.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系根據(jù)以上公式可以求出這三個(gè)參數(shù)TPmax、ηmax、Smax

之間的關(guān)系。對(duì)于給定的流水線，Δt是常數(shù)。對(duì)于特定的任務(wù)，K1、K、N也是常數(shù)，因此從(6.52)~(6.54)可以看出三個(gè)性能參數(shù)取決于平均啟動(dòng)距離dav，并且與dav成反比。不同的調(diào)度方案dav是不同的，為了獲得TPmax、ηmax、Smax的最大值，應(yīng)當(dāng)選擇dav最小的方案。716.7.3非線性流水線的吞吐率、效率、加速比及其關(guān)系從(6.52)式~(6.54)式可以直接求得線性流水線的相應(yīng)參數(shù)。（6.55）（6.56）（6.57）726.8模型機(jī)的指令級(jí)流水線模型機(jī)流水線的數(shù)據(jù)路徑模型機(jī)流水線的控制相關(guān)及處理結(jié)構(gòu)相關(guān)數(shù)據(jù)相關(guān)控制相關(guān)流水線的基本性能問題736.8.1模型機(jī)流水線的數(shù)據(jù)路徑在模型機(jī)中l(wèi)oad指令劃分為5個(gè)流水周期，它們是IF、ID、EX、MEM、WB周期。圖6.30是第4章的一個(gè)單周期的數(shù)據(jù)路徑，包括5個(gè)階段：（1）IF：取指令子功能段。（2）ID：指令譯碼/讀寄存器堆子功能段。（3）EX：執(zhí)行或計(jì)算地址子功能階段。（4）MEM：存儲(chǔ)器訪問子功能段。（5）WB：寫回子功能段。746.8.1模型機(jī)流水線的數(shù)據(jù)路徑在圖6.30中所示的單周期數(shù)據(jù)路徑中，指令的每一步在圖中由左至右映射到數(shù)據(jù)路徑上。寫回過程與PC的更新過程是例外，第一種導(dǎo)致數(shù)據(jù)相關(guān)、第二種導(dǎo)致控制相關(guān)。根據(jù)前面的討論，為了使得流水線能正常工作，在每一個(gè)子功能段的后面應(yīng)當(dāng)有一個(gè)寄存器，保存該子功能段的輸出結(jié)果。圖6.31畫出了這樣的寄存器，稱為流水線寄存器。需要注意的是寫回階段后面沒有流水線寄存器。756.8.1模型機(jī)流水線的數(shù)據(jù)路徑為了處理數(shù)據(jù)相關(guān)，需要將指令的源寄存器號(hào)和目的寄存器號(hào)沿著流水線寄存器向前傳遞，如圖6.32。為了討論方便，也采用另一種表示流水線數(shù)據(jù)的路徑的方法，這種方法假定每一條指令有它獨(dú)立的數(shù)據(jù)路徑，然后把這些數(shù)據(jù)路徑放在同一時(shí)間軸上表示它們之間的關(guān)系。如圖6.33所示。766.8.1模型機(jī)流水線的數(shù)據(jù)路徑圖6.33是一種簡(jiǎn)化的流水線圖形表示。IM表示取指階段的指令存儲(chǔ)器和程序計(jì)數(shù)器PC等。Reg表示指令譯碼/讀寄存器堆階段的寄存器堆和符號(hào)擴(kuò)展。ALU表示算術(shù)邏輯單元ALU和計(jì)算轉(zhuǎn)移地址的加法器Add等。DM表示存儲(chǔ)器訪問，這一階段也將轉(zhuǎn)移地址寫入PC（如果轉(zhuǎn)移成功）。776.8.2模型機(jī)流水線的控制本節(jié)介紹如何在流水線的數(shù)據(jù)路徑中加入控制：首先，標(biāo)識(shí)已有的數(shù)據(jù)路徑上的控制信號(hào)線。這里采用與第4章中單周期數(shù)據(jù)路徑相同的標(biāo)識(shí)方式（見圖4.20和表4.12），如表6.2所示。為了詳細(xì)說明流水線的控制過程，根據(jù)流水線將控制線分成五組：取指令、指令譯碼/讀寄存器、指令執(zhí)行/地址計(jì)算、存儲(chǔ)器訪問、寫回。786.8.2模型機(jī)流水線的控制情況分別如下：取指令、指令譯碼/讀寄存器無需設(shè)置流水線控制器。指令執(zhí)行/地址計(jì)算：設(shè)置信號(hào)有RegDst、ALUOp和ALUSrc。存儲(chǔ)器訪問：設(shè)置信號(hào)有Branch、MemRead、和MemWrite。寫回：設(shè)置信號(hào)有MemtoReg和RegWrite。796.9相關(guān)及其處理

6.9.1相關(guān)概念在流水線的體系結(jié)構(gòu)中，關(guān)鍵的性能屏障是存在流水線斷流。當(dāng)一組新的輸入不能注入流水線時(shí)，就發(fā)生斷流。這是由于相關(guān)引起的。相關(guān)是流水線的主要障礙，它使得指令流中下一條指令無法在緊接著的流水周期內(nèi)運(yùn)行，相關(guān)將會(huì)降低流水線可能獲得的理想性能。806.9.1相關(guān)概念相關(guān)有以下幾種情況：結(jié)構(gòu)相關(guān) 數(shù)據(jù)相關(guān)控制相關(guān)816.9.2結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān)產(chǎn)生原因：一種特定體系結(jié)構(gòu)的實(shí)現(xiàn)沒有足夠的資源支持某些種類的指令在時(shí)間上重疊。實(shí)例：存儲(chǔ)器資源有限，不支持訪問存儲(chǔ)器指令和取指令的重疊。見圖6.36。結(jié)果：指令串行化，降低處理器效率。解決方案：斷流法（讓流水線中的一部分指令正常運(yùn)行而另一部分指令被延遲運(yùn)行），見圖6.37。826.9.2結(jié)構(gòu)相關(guān)常見的結(jié)構(gòu)（資源）相關(guān)：資源沒有充分重復(fù)設(shè)置，不足以讓流水線中的若干條指令同時(shí)運(yùn)行。如一個(gè)流水周期寫兩次寄存器。部分功能部件沒有充分流水運(yùn)行，一系列使用該部件的指令不能按照每個(gè)流水周期前進(jìn)一拍的速率流水運(yùn)行。如瓶頸段流水線。836.9.3數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)產(chǎn)生原因：流水線中的流水指令改變了操作數(shù)的讀寫順序，使得順序與邏輯指令序列不同。將以流水方式運(yùn)行的指令序列稱為流水指令序列，簡(jiǎn)稱流水指令。邏輯指令序列也就是通常意義下的指令序列。846.9.3數(shù)據(jù)相關(guān)實(shí)例（PGM6.1）：addR1,R2,R3 //add指令寫寄存器R1subR4,R1,R5 //第一個(gè)操作數(shù)依賴于add指令的運(yùn)算結(jié)果andR6,R7,R1 //第二個(gè)操作數(shù)依賴于add指令的運(yùn)算結(jié)果orR8,R1,R9 //第一個(gè)操作數(shù)依賴于add指令的運(yùn)算結(jié)果xorR10,R1,R11 //第一個(gè)操作數(shù)依賴于add指令的運(yùn)算結(jié)果add指令后的所有指令都用到了add結(jié)果，如圖6.40所示。856.9.3數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)解決方案采用編譯技術(shù)解決數(shù)據(jù)相關(guān)采用前傳技術(shù)需要斷流的數(shù)據(jù)相關(guān)866.9.3數(shù)據(jù)相關(guān)1.采用編譯技術(shù)解決數(shù)據(jù)相關(guān)通過編譯器禁止像PGM6.1中具有相關(guān)性的五條指令，避免數(shù)據(jù)相關(guān)。例如在add和sub之間插入兩條沒有相關(guān)性的指令消除數(shù)據(jù)相關(guān)。若沒有這種指令則插入一定數(shù)量的nop指令。參看圖6.40。

addR1,R2,R3

nop

nop subR4,R1,R5 andR6,R1,R7 orR8,R1,R9

xorR10,R1,R11876.9.3數(shù)據(jù)相關(guān)2.采用前傳技術(shù)前傳技術(shù)是將某一指令的操作結(jié)果盡快傳遞給它的后繼指令，而不必等到該指令完全運(yùn)行完畢的一種技術(shù)。一般來說，指令只在流水線中的特定功能段和特定的時(shí)刻產(chǎn)生操作結(jié)果或接受前傳。圖6.41是一條6段流水線。886.9.3數(shù)據(jù)相關(guān)前傳技術(shù)是流水線中廣泛采用的一種技術(shù)，它將流水線中某一個(gè)功能段的輸出結(jié)果超越它的直接前驅(qū)功能段，而前向傳遞給需要該功能段輸出數(shù)據(jù)的其他功能段。圖6.47是前傳技術(shù)的示意圖。896.9.3數(shù)據(jù)相關(guān)前傳技術(shù)在模型機(jī)中不僅在R型指令中使用，在其他指令中也使用，例如：PGM6.2

addR1,R2,R3 loadR8,0(R1) storeR8,58(R1)圖6.48畫出了該序列的所有可能的前傳，這些前傳可以使得指令序列PGM6.2在流水線中正常流動(dòng)，而不會(huì)斷流。906.9.3數(shù)據(jù)相關(guān)3.需要斷流的數(shù)據(jù)相關(guān)前傳雖然可以解決一些數(shù)據(jù)相關(guān)問題，但并非所有的數(shù)據(jù)相關(guān)都可以采用前傳的方法來解決。例如：PGM6.3 loadR1,0(R2) addR3,R1,R4 subR5,R1,R6 orR7,R1,R8就不能通過前傳解決。其帶前傳的流水線數(shù)據(jù)路徑采用簡(jiǎn)化的圖6.50表示。916.9.3數(shù)據(jù)相關(guān)在這種情況下，需要斷流流水線，讓需要結(jié)果的操作一直等到該結(jié)果產(chǎn)生為止。圖6.51畫出了load指令與add指令之間通過斷流解決數(shù)據(jù)相關(guān)的簡(jiǎn)化流水線圖。這里，除了需要一個(gè)前傳單元以外，還需要一個(gè)相關(guān)檢測(cè)單元。圖6.52給出了相關(guān)檢測(cè)單元和前傳單元的流水線連接。926.9.4控制相關(guān)控制相關(guān)產(chǎn)生原因：流水線中的轉(zhuǎn)移指令（分支指令）或其他改寫PC（除PC正常增量以外）的指令造成的相關(guān)?？刂葡嚓P(guān)解決方案：轉(zhuǎn)移斷流法：一旦發(fā)現(xiàn)有轉(zhuǎn)移指令就對(duì)該指令之后的直接后繼指令進(jìn)行重新取指令的操作。見圖6.53。936.9.4控制相關(guān)猜測(cè)法：在條件轉(zhuǎn)移指令后，選擇一個(gè)分支方向，讓后繼指令進(jìn)入流水線運(yùn)行。實(shí)現(xiàn)方法是直接取下一條指令，好像轉(zhuǎn)移指令只是一條普通的指令那樣，流水線看起來也沒有特殊之處。但是只要轉(zhuǎn)移條件滿足（即轉(zhuǎn)移成功）時(shí)，就需要用空操作代替取來的指令，并到目標(biāo)地址重新取指令。946.9.4控制相關(guān)借助于編譯技術(shù)：轉(zhuǎn)移延遲技術(shù)：在流水線中，轉(zhuǎn)移指令后面加上延遲槽，并在延遲槽中填入適當(dāng)?shù)闹噶?，以提高流水線吞吐率的一種技術(shù)。見圖6.58、圖6.59。延遲槽深度為1的5段模型機(jī)流水線的工作流程如圖6.60、圖6.61所示。分支取消技術(shù)：轉(zhuǎn)移指令帶有對(duì)分支能否被選中（即轉(zhuǎn)移是否成功）的預(yù)測(cè)。當(dāng)預(yù)測(cè)準(zhǔn)確時(shí)，延遲槽中的指令像通常那樣流水運(yùn)行，否則就把延遲槽中的指令變成空操作指令。見圖6.62、圖6.63。延遲槽深度為1的5段模型機(jī)流水線的工作流程如圖6.64、圖6.65。956.10流水線的基本性能問題需要解決的問題流水線增大了CPU的指令吞吐率，但沒有減少每一條指令各自的運(yùn)行時(shí)間。限制了流水線的深度。除了流水線延遲引起的限制，流水線的不平衡和流水線的附加開銷也引入了某些限制。前者因?yàn)闀r(shí)鐘不能快于最慢的流水線功能段，后者是因?yàn)榱魉€的延遲和時(shí)鐘偏移。966.11超標(biāo)量流水線概念一般的流水線處理器只有一條指令級(jí)流水線，流水線除了有裝入和排空時(shí)間外，還有數(shù)據(jù)相關(guān)、轉(zhuǎn)移等的影響，因此，一般流水線標(biāo)量處理器每個(gè)流水周期平均完成的指令的條數(shù)小于1，即它的指令級(jí)并行度ILP<l。為了提高指令及并行度，可以采用超標(biāo)量處理器，使用超標(biāo)量流水線（superscalarpipelining）。通常把一個(gè)流水周期內(nèi)能夠同時(shí)發(fā)射多條指令的處理器稱為超標(biāo)量處理器。976.12本章小結(jié)本章介紹了流水線的基本概念、原理及其在CPU設(shè)計(jì)中的應(yīng)用，包括：指令流水線概念及指令的重疊運(yùn)行方式時(shí)空?qǐng)D流水線的分類流水線的性能指標(biāo)與線性流水線性能分析非線性流水線非線性流水線的性能分析模型機(jī)的指令級(jí)流水線相關(guān)及其處理結(jié)構(gòu)相關(guān)數(shù)據(jù)相關(guān)控制相關(guān)流水線的基本性能問題超標(biāo)量流水線概念9899串行工作方式圖示內(nèi)科外科五官科考察一下4個(gè)工人在醫(yī)院體檢的兩種不同方式100串行工作方式圖示W(wǎng)1內(nèi)科外科五官科101串行工作方式圖示W(wǎng)1內(nèi)科外科五官科102串行工作方式圖示W(wǎng)1內(nèi)科外科五官科103串行工作方式圖示W(wǎng)2內(nèi)科外科五官科104串行工作方式圖示W(wǎng)2內(nèi)科外科五官科105串行工作方式圖示W(wǎng)2內(nèi)科外科五官科106串行工作方式圖示W(wǎng)3內(nèi)科外科五官科107串行工作方式圖示W(wǎng)3內(nèi)科外科五官科108串行工作方式圖示W(wǎng)3內(nèi)科外科五官科109串行工作方式圖示W(wǎng)4內(nèi)科外科五官科110串行工作方式圖示W(wǎng)4內(nèi)科外科五官科111串行工作方式圖示W(wǎng)4內(nèi)科外科五官科112串行工作方式圖示內(nèi)科外科五官科這種工作方式的缺點(diǎn)是什么？答案：效率低113流水工作方式圖示內(nèi)科外科五官科114流水工作方式圖示W(wǎng)1內(nèi)科外科五官科115流水工作方式圖示W(wǎng)2W1內(nèi)科外科五官科116流水工作方式圖示W(wǎng)3W2W1內(nèi)科外科五官科117流水工作方式圖示W(wǎng)4W3W2內(nèi)科外科五官科118流水工作方式圖示W(wǎng)4W3內(nèi)科外科五官科119流水工作方式圖示W(wǎng)4內(nèi)科外科五官科120流水工作方式圖示內(nèi)科外科五官科返回主調(diào)處121時(shí)間t取指令譯碼執(zhí)行圖6.1將一條指令分解為取指令階段、譯碼階段、執(zhí)行階段122取指令i譯碼i執(zhí)行i取指i+1譯碼i+1執(zhí)行i+1時(shí)間ti：i+1：指令流圖6.2指令的順序運(yùn)行123取指i譯碼i執(zhí)行i取指i+1譯碼i+1執(zhí)行i+1取指i+2譯碼i+2執(zhí)行i+2時(shí)間ti：i+1：i+2：指令流圖6.3指令的一次重疊運(yùn)行方式124取指令i譯碼i執(zhí)行i取指令i+1譯碼i+1執(zhí)行i+1取指令i+2譯碼i+2執(zhí)行i+2指令i：指令i+1：指令i+2：時(shí)間t圖6.4指令的二次重疊運(yùn)行方式125取指令I(lǐng)F指令譯碼ID指令執(zhí)行EX輸入輸出IF/IDID/EXEX/OUT圖6.5用于流水線的指令的各個(gè)子功能段之間應(yīng)當(dāng)加寄存器126快速S1快速S2快速S3快速S1慢速S2快速S3慢速S1慢速S2慢速S3輸入輸入輸入快速輸出慢速輸出慢速輸出abc圖6.6有“瓶頸”段的流水線127取指令k取指令k+1取指令k+2取指令k+3譯碼k譯碼k+1譯碼k+2譯碼k+3執(zhí)行k執(zhí)行k+1執(zhí)行k+2執(zhí)行k+3空間S執(zhí)行譯碼取指令時(shí)間t時(shí)空?qǐng)D的橫坐標(biāo)t表示流水線的執(zhí)行時(shí)間；縱坐標(biāo)S表示空間，其含義是流水線的各個(gè)子功能段，對(duì)應(yīng)于流水線執(zhí)行指令的各個(gè)子過程。在時(shí)空?qǐng)D中，流水線的一個(gè)子功能段通常也簡(jiǎn)稱為功能段

圖6.7時(shí)空?qǐng)D：流水線的時(shí)間-空間關(guān)系圖128將浮點(diǎn)流水線加法器分解為求階差、對(duì)階、尾數(shù)加、規(guī)格化4個(gè)子功能段。圖中畫出了該流水線的時(shí)空?qǐng)D，并假設(shè)求階差、對(duì)階、尾數(shù)加、規(guī)格化4個(gè)子功能段所需要的時(shí)間相等求階差1求階差2求階差3求階差4求階差5對(duì)階1對(duì)階2對(duì)階3對(duì)階4對(duì)階5尾數(shù)加1尾數(shù)加2尾數(shù)加3尾數(shù)加4尾數(shù)加5規(guī)格化1規(guī)格化2規(guī)格化3規(guī)格化4規(guī)格化5求階差對(duì)階尾數(shù)加規(guī)格化空間功能塊0t1t2t3t4t5

t6t7t8時(shí)間t圖6.8一條浮點(diǎn)流水線加法器的時(shí)空?qǐng)D129

S1、S2、S3分別表示流水線的3個(gè)子功能段。輸入數(shù)據(jù)從S1功能段輸入，完成操作后由S1功能段輸出，并作為S2功能段的輸入信號(hào)，在S2功能段完成相應(yīng)的操作后，從S2的另一端輸出，再作為S3功能段的輸入信號(hào)，在S3功能段完成相應(yīng)的操作后，從S3的輸出端輸出。從而完成了全部操作，數(shù)據(jù)流出了流水線。數(shù)據(jù)在流水線中的各個(gè)功能段流過時(shí)，每一個(gè)功能段都流過1次，而且僅僅流過1次S1S2S3輸入輸出圖6.9一種3個(gè)功能段構(gòu)成的線性流水線130

S1、S2、S3分別表示流水線的3個(gè)子功能段。非線性流水線指的是在流水線的各個(gè)功能段之間除了有串行的連接之外，還有反饋回路。由于反饋回路的存在，會(huì)使得非線性流水線的分析變得復(fù)雜。但有時(shí)系統(tǒng)中會(huì)出現(xiàn)反饋回路，因此，對(duì)反饋回路的分析是有著實(shí)際應(yīng)用價(jià)值的S1S2S3輸入輸出圖6.10一種3個(gè)功能段構(gòu)成的非線性流水線131a.定點(diǎn)乘法輸入求階差對(duì)階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出輸入求階差對(duì)階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出b.浮點(diǎn)加法ABAB圖6.11多功能流水線132111122223333……………………n-1nn-1n-1n-1nnn空間S1S4S3S2功能段“空閑”區(qū)功能段“忙”區(qū)功能段“空閑”區(qū)Tk圖6.12流水線的效率分析133S1輸入輸出S2S4S3Δt1=ΔtΔt2=3ΔtΔt3=ΔtΔt4=Δt這是一個(gè)具有4個(gè)功能段的線性流水線。該流水線的各個(gè)功能段的工作時(shí)間不相等。S1、S3、S4功能段的工作時(shí)間為Δt1=Δt3=Δt4=Δt，S2功能段的工作時(shí)間為Δt2=3Δt。當(dāng)線性流水線中各段的工作時(shí)間不完全相等時(shí)，線性流水線中就存在“瓶頸”段。圖中的S2功能段就是這條流水線的“瓶頸段”圖6.13一條具有瓶頸段的4個(gè)功能段的線性流水線134圖6.14具有瓶頸段的線性流水線的時(shí)空?qǐng)D圖中T1表示第一個(gè)任務(wù)從進(jìn)入到流出流水線的時(shí)間，即T1=Δt1+Δt2+Δt3+Δt4，Δti

表示功能段Si（i=1,…,4）需要使用的時(shí)間S1S2S3S4123…n123…n123…n123…n空間(n-1)maxΔti

T1時(shí)間135將線性流水線的“瓶頸”部分再細(xì)分，如圖所示。即把第二個(gè)功能段再分成三個(gè)串聯(lián)起來的子功能段，分別記為S2-1、S2-2、S2-3，這樣，每一個(gè)功能段及子功能段的延遲時(shí)間均為Δt。根據(jù)線性流水線的吞吐率的表達(dá)式可以知道，這樣做可以提高線性流水線的吞吐率S2-1S1S2-2S3S2-3S4S2(3Δt)輸出輸入圖6.15將線性流水線的“瓶頸”段再細(xì)分成若干子功能段136S2-1S2-2S2-3S1S3S4Δt1=ΔtΔt3=ΔtΔt4=ΔtΔt2=3Δt輸入輸出如果“瓶頸”功能段不能再細(xì)分時(shí)，則采用若干個(gè)相同的“瓶頸”功能段并聯(lián)重復(fù)設(shè)置的方法來提高線性流水線的吞吐率。其控制邏輯比較復(fù)雜，需要設(shè)置一個(gè)數(shù)據(jù)分配器和一個(gè)數(shù)據(jù)收集器圖6.16“瓶頸”功能段并聯(lián)重復(fù)設(shè)置13711248163264128n246810加速比Sk=6k=10圖中畫出了k=6和k=10兩條線性流水線的加速比曲線?？梢钥闯?，當(dāng)n較大時(shí)，加速比曲線接近于它的漸進(jìn)線。線性流水線的段數(shù)k越大，其加速比的上確界也越大圖6.17線性流水線的加速比曲線138S1輸入S2S3X輸出Y輸出這時(shí)一條由三個(gè)功能段組成的非線性流水線。有一個(gè)輸入端，兩個(gè)輸出端。兩個(gè)輸出端分別是X輸出端和Y輸出端。由于非線性流水線存在反饋連接，因此輸出端的位置較為靈活，不必在一定要位于S3功能段的右邊圖6.18一條三段非線性流水線結(jié)構(gòu)圖139時(shí)間（流水周期Δt）12345678S3S2S1功能段XXXXXXXX預(yù)約表中的X表示在對(duì)應(yīng)的流水周期，相應(yīng)的功能段處于忙碌狀態(tài)；而表中的空格則表示在對(duì)應(yīng)的流水周期，相應(yīng)的功能段處于空閑狀態(tài)圖6.19圖6.18的非線性流水線功能X的預(yù)約表140時(shí)間（流水周期Δt）123456S3S2S1功能段YYYYYY表中的Y表示在對(duì)應(yīng)的流水周期，相應(yīng)的功能段處于忙碌狀態(tài)，而表中的空格則表示在對(duì)應(yīng)的流水周期，相應(yīng)的功能段處于空閑狀態(tài)圖6.20圖6.18的非線性流水線功能Y的預(yù)約表141S3S2S1時(shí)間（流水周期Δt）12345678X1X2X3X1X1X1X2X1X2X2X3X1X2X3X1X4X1X2X3X4X2X3X4X2X3X491011………圖中Xi（i=1,2,…）表示按照X功能的預(yù)約表，以啟動(dòng)距離2輸入的第i個(gè)任務(wù)?？梢钥闯觯诘?個(gè)流水周期任務(wù)X1和X2同時(shí)爭(zhēng)用S2功能段，從而產(chǎn)生沖突。這種情況還發(fā)生在其它的一些功能段圖6.21對(duì)圖6.19的非線性流水線功能X，2是禁止啟動(dòng)距離142S3S2S112345678X1X1X1X1X1X191011………X1X2X2X1X2X2X2時(shí)間（流水周期Δt）圖中Xi（i=1,2,…）表示按照X功能的預(yù)約表，以啟動(dòng)距離5輸入的第i個(gè)任務(wù)?？梢钥闯?，在第6個(gè)流水周期任務(wù)X1和X2同時(shí)爭(zhēng)用S1功能段，從而產(chǎn)生沖突。這種情況還發(fā)生在其它的一些功能段圖6.22啟動(dòng)距離為5時(shí)流水線的沖突情況143S3S2S112345678X1X1X1X1X1X191011………X1X2X512131415161718192021X2X2X2X3X2X1X3X4X4X5X3X4X4X5X3X4X4X7重復(fù)周期…X2X3X3X4X2X3X5X6X5X5X6X6X7X2X3X4X5X6X5X6重復(fù)周期重復(fù)周期重復(fù)周期對(duì)圖6.19給出的非線性流水線的功能X，啟動(dòng)序列(3,3,…)構(gòu)成了一個(gè)啟動(dòng)循環(huán)圖6.23圖6.19給出的非線性流水線的功能X的啟動(dòng)循環(huán)(3)144圖6.24圖6.19給出的非線性流水線的功能X的啟動(dòng)循環(huán)(6)S3S2S112345678X1X1X1X1X1X191011………X1X312131415161718192021X2X1X2X2X3X2X4X4重復(fù)周期…X2X2X2X3X3X3X4X2X2X3重復(fù)周期X3對(duì)圖6.19給出的非線性流水線的功能X，啟動(dòng)序列(6,6,…)構(gòu)成了一個(gè)啟動(dòng)循環(huán)145S3S2S112345678X1X1X1X1X1X191011………X3X4X1X2X512131415161718192021X2X2X2X2X2X2X2X1X3X4X3X4X3X4X3X4X3X4X3X4X3X4X5X6X2和X1的啟動(dòng)距離為1X3和X2的啟動(dòng)距離為8X4和X3的啟動(dòng)距離為1，如此等等。X1流出時(shí)刻X2流出時(shí)刻重復(fù)周期…對(duì)圖6.19給出的非線性流水線的功能X，啟動(dòng)序列(1,8,1,8…)構(gòu)成了一個(gè)啟動(dòng)循環(huán)圖6.25圖6.19給出的非線性流水線的功能X的啟動(dòng)循環(huán)(1,8)1461234S3S2S1功能段XXXS4X時(shí)間（流水周期Δt）對(duì)于允許啟動(dòng)距離p=1的一階啟動(dòng)循環(huán)，其預(yù)約表呈對(duì)角線形狀

圖6.26對(duì)角線形狀的預(yù)約表147圖6.27圖6.19預(yù)約表的狀態(tài)圖圖中畫出了流水線從零狀態(tài)調(diào)度向量到各個(gè)調(diào)度向量之間的狀態(tài)遷移。最重要的是啟動(dòng)距離，因?yàn)樗鼈兘o出了流水線的無沖突調(diào)度方案。雖然啟動(dòng)距離為8的那些數(shù)據(jù)可以改成大于8的任何正整數(shù)，但是這樣做會(huì)降低流水線的工作速度，因此圖中只保留了數(shù)據(jù)8。這里m=738010110100101101101111111183686零狀態(tài)調(diào)度向量Z調(diào)度向量調(diào)度向量148圖6.28一個(gè)非線性流水線的計(jì)算實(shí)例t1t2t3t4t5t6S1XXS2XS3XXX149中畫出了流水線從零狀態(tài)調(diào)度向量到各個(gè)調(diào)度向量之間的狀態(tài)遷移。最重要的是啟動(dòng)距離，因?yàn)樗鼈兘o出了流水線的無沖突調(diào)度方案。雖然啟動(dòng)距離為5的那些數(shù)據(jù)可以改成大于5的任何正整數(shù)，但是這樣做會(huì)降低流水線的工作速度，因此圖中只保留了數(shù)據(jù)5。這里m=4350101001011011111535零狀態(tài)調(diào)度向量Z調(diào)度向量調(diào)度向量圖6.29例6.4預(yù)約表的狀態(tài)圖150圖6.30單周期數(shù)據(jù)路徑的功能段劃分40Mux01PC0Mux11MuxAddress指令存儲(chǔ)器ReadReg1ReadReg2WrigeRegWriteDataReadData1ReadData2寄存器堆AddressReadDataWriteData數(shù)據(jù)存儲(chǔ)器符號(hào)擴(kuò)展左移兩位AddALUZeroAdd1632

IF功能段 ID功能段 EX功能段 MEM功能段 WB功能段151圖6.31單周期CPU的各個(gè)功能段之間帶有流水線寄存器40Mux01PC0Mux11MuxAddress指令存儲(chǔ)器ReadReg1ReadReg2WrigeRegWriteDataReadData1ReadData2寄存器堆AddressReadDataWriteData數(shù)據(jù)存儲(chǔ)器符號(hào)擴(kuò)展左移兩位AddIF/ID ID/EX EX/MEM MEM/WBALUZeroAdd1632152圖6.32寄存器堆的WriteReg端的寫編號(hào)來自流水線寄存器MEM/WB，而它是由流水線寄存器ID/EX傳遞過來的40Mux01PC0Mux11MuxAddress指令存儲(chǔ)器ReadReg1ReadReg2WrigeRegWriteDataReadData1ReadData2寄存器堆AddressReadDataWriteData數(shù)據(jù)存儲(chǔ)器符號(hào)擴(kuò)展左移兩位AddIF/ID ID/EX EX/MEM MEM/WBALUZeroAdd1632153圖6.33流水線數(shù)據(jù)路徑的簡(jiǎn)化圖形表示154圖6.34當(dāng)指令在流水線中傳遞時(shí)控制信號(hào)的使用155圖6.35在流水線寄存器中帶有控制信號(hào)的流水線數(shù)據(jù)路徑156圖6.36結(jié)構(gòu)相關(guān)引起的訪問存儲(chǔ)器資源沖突157圖6.37將指令3推遲（斷流）1個(gè)流水周期進(jìn)入流水線，可以解決存儲(chǔ)器結(jié)構(gòu)相關(guān)問題IFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIF斷流ID斷流EX斷流MEM斷流WB斷流load指令1指令2指令3斷流一個(gè)流水周期CC1CC2CC3CC4CC5時(shí)間（流水周期數(shù)）單端口存儲(chǔ)器的load指令引起結(jié)構(gòu)相關(guān)時(shí)的流水線斷流。在流水周期4沒有指令進(jìn)入流水線（正常情況下應(yīng)該是指令3進(jìn)人流水線）。當(dāng)一條指令被斷流后，流水線中所有該指令之后的指令都會(huì)被斷流。流水線中該指令之前的指令還是正常運(yùn)行。因?yàn)樽x入的指令被斷流，斷流周期將流過流水線158圖6.38將存儲(chǔ)器分成指令存儲(chǔ)器IM和數(shù)據(jù)存儲(chǔ)器DM以避免訪問存儲(chǔ)器資源沖突159圖6.39將存儲(chǔ)器分成指令存儲(chǔ)器IM和數(shù)據(jù)存儲(chǔ)器DM來解決存儲(chǔ)器資源相關(guān)IFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBload指令1指令2指令4指令3CC1CC2CC3CC4CC5時(shí)間（流水周期數(shù)）由于將存儲(chǔ)器分成了指令存儲(chǔ)器IM和數(shù)據(jù)存儲(chǔ)器DM，存儲(chǔ)器訪問load指令不會(huì)引起結(jié)構(gòu)相關(guān)。在流水周期4指令3正常進(jìn)入了流水線，因此沒有產(chǎn)生流水線斷流。這種采用資源重復(fù)設(shè)置的方法是一種解決流水線斷流的方案，但是增加了硬件成本160圖6.40數(shù)據(jù)相關(guān)的簡(jiǎn)化流水線圖形表示161S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6時(shí)間（流水周期）123456S1S2S3S4S5S6S1S2S3S4S5S6指令i指令i+1指令i+2指令i與指令i+1在功能段S3是單周期數(shù)據(jù)相關(guān)，指令i與指令i+2在功能段S3是2周期數(shù)據(jù)相關(guān)圖6.41單周期與2周期數(shù)據(jù)相關(guān)發(fā)生在S3功能段162圖6.42單周期與2周期前傳S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6S3功能段單周期前傳S1S2S3S4S5S6S3功能段2周期前傳S1/S2S2/S3S3/S4S4/S5S5/S6時(shí)間（流水周期）123456163S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6時(shí)間（流水周期）123456S1S2S3S4S5S6S1S2S3S4S5S6指令i指令i+1指令i+2指令i與指令i+1在功能段3、功能段5是單周期數(shù)據(jù)相關(guān)，指令i、

i+1與指令i+2沒有數(shù)據(jù)相關(guān)圖6.43單數(shù)據(jù)相關(guān)發(fā)生在S3、S5功能段164圖6.44單周期與2周期數(shù)據(jù)相關(guān)發(fā)生在S3功能段，單周期數(shù)據(jù)相關(guān)還發(fā)生在S5功能段S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6時(shí)間（流水周期）123456S1S2S3S4S5S6S1S2S3S4S5S6指令i指令i+1指令i+2指令i與指令i+1在功能段3、功能段5是單周期相關(guān)，指令i與指令i+2在功能段3是2周期相關(guān)165圖6.45在流水線的不同功能段出現(xiàn)的單周期與多周期前傳S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6時(shí)間（流水周期）123456S3功能段單周期前傳S1S2S3S4S5S6S3功能段單周期前傳、2周期前傳S1/S2S2/S3S3/S4S4/S5S5/S6S5功能段單周期前傳S5功能段單周期前傳166圖6.46模型機(jī)EX功能段的1CC前傳和2CC前傳簡(jiǎn)圖167圖6.47前傳的流水線簡(jiǎn)化圖形表示168圖6.48指令序列PGM5.2的前傳數(shù)據(jù)路徑簡(jiǎn)化圖169圖6.49含有R型指令前傳單元的數(shù)據(jù)路徑PCMuxMuxALUEXMWBMWBWBID/EXEX/MEMMEM/WBMuxIF/IDInstructionMuxRdRtRtRs指令存儲(chǔ)器寄存器堆前傳單元數(shù)據(jù)存儲(chǔ)器主控制單元R.IF/ID.rsR.IF/ID.rtI.IF/ID.rtR.IF/ID.rdR.EX/MEM.rdR.MEM/WB.rd170圖6.50load指令引起的數(shù)據(jù)相關(guān)171圖6.51load指令與add指令之間通過斷流解決數(shù)據(jù)相關(guān)1726.52帶有數(shù)據(jù)相關(guān)檢測(cè)單元的數(shù)據(jù)路徑

PCMuxMuxMuxALUEXMWBMWBWBID/EXEX/MEMMEM/WBMux0MuxIF/IDInstructionID/EX.MemReadIF/IDWritePCWriteRtRsRdRt.數(shù)據(jù)存儲(chǔ)器R.IF/ID.rsR.IF/ID.rtI.IF/ID.rtR.IF/ID.rdR.EX/MEM.rdR.MEM/WB.rd寄存器堆指令存儲(chǔ)器前傳單元主控制單元相關(guān)檢測(cè)單元173圖6.53轉(zhuǎn)移指令的最簡(jiǎn)單處理方法的簡(jiǎn)化流水線圖形描述本圖是對(duì)轉(zhuǎn)移指令最簡(jiǎn)單處理方法的簡(jiǎn)化流水線圖形描述。當(dāng)在ID段發(fā)現(xiàn)有轉(zhuǎn)移指令后就忽略轉(zhuǎn)移指令的直接后繼指令，并計(jì)算地址，按新地址重新取指令。這種轉(zhuǎn)移指令的處理方式使得不管轉(zhuǎn)移是否成功，在模型機(jī)的5段流水線中都將產(chǎn)生1個(gè)流水周期的斷流IFIDEXMEMWBIF清空清空清空清空IFIDEXMEMIFIDEXMEMWB轉(zhuǎn)移指令i忽略直接后繼轉(zhuǎn)移指令的目標(biāo)或直接后繼轉(zhuǎn)移指令的目標(biāo)或直接后繼+1時(shí)間（流水周期數(shù)）123456789WBIFIDEXMEMWB轉(zhuǎn)移指令的目標(biāo)或直接后繼+2174圖6.54轉(zhuǎn)移的影響原始指令流…ib+k-1…ib+2ib+1ib轉(zhuǎn)移成功………it+2it+1it轉(zhuǎn)移目標(biāo)新指令流長(zhǎng)為k-1的延遲槽ib=轉(zhuǎn)移成功it=轉(zhuǎn)移目標(biāo)

k=流水線的段數(shù)△t=流水周期b=延遲槽的大小ib+k-1ib+k-2…ib+2ib+1ib指令流△t流水周期175圖6.55在猜測(cè)轉(zhuǎn)移不成功分支策略情況下的流水線工作情況轉(zhuǎn)移指令+1是流水指令序列中轉(zhuǎn)移指令的直接后繼指令，也是對(duì)應(yīng)的邏輯指令序列中的轉(zhuǎn)移不成功分支的第一條指令。當(dāng)在ID段發(fā)現(xiàn)轉(zhuǎn)移不成功時(shí)，流水線中已經(jīng)讀取到了正確的指令，只需繼續(xù)運(yùn)行，流水線不斷流IFIDEXMEMWBIFIDEXMEMIFIDEXMEMWB轉(zhuǎn)移不成功轉(zhuǎn)移指令+1轉(zhuǎn)移指令+2轉(zhuǎn)移指令+3時(shí)間（流水周期數(shù)）12