第五章 重疊、流水和向量處理機(jī)1

1、第五章第五章 重疊、流水和向量處理機(jī)重疊、流水和向量處理機(jī)1 重疊方式重疊方式通常提高指令執(zhí)行速度的途徑有如下三種：通常提高指令執(zhí)行速度的途徑有如下三種：1. 提高處理機(jī)的工作主頻。提高處理機(jī)的工作主頻。2. 采用更好的算法和設(shè)計更好的功能部件。采用更好的算法和設(shè)計更好的功能部件。3. 多條指令并行執(zhí)行，稱為指令級并行技術(shù)。多條指令并行執(zhí)行，稱為指令級并行技術(shù)。 可以從兩個方面來開發(fā)處理機(jī)內(nèi)部的并行性：可以從兩個方面來開發(fā)處理機(jī)內(nèi)部的并行性：空間并行性：即在一個處理機(jī)內(nèi)設(shè)置多個獨空間并行性：即在一個處理機(jī)內(nèi)設(shè)置多個獨立的操作部件，并讓這些操作部件并行工作，立的操作部件，并讓這些操作部件并行工作

2、，這種處理機(jī)稱為多操作部件處理機(jī)或超標(biāo)量這種處理機(jī)稱為多操作部件處理機(jī)或超標(biāo)量處理機(jī)處理機(jī);時間并行性：就是采用流水線技術(shù)。流水線時間并行性：就是采用流水線技術(shù)。流水線技術(shù)是一種非常經(jīng)濟(jì)、對提高處理機(jī)的運算技術(shù)是一種非常經(jīng)濟(jì)、對提高處理機(jī)的運算速度非常有效的技速度非常有效的技 術(shù)。采用流水線技術(shù)可以術(shù)。采用流水線技術(shù)可以不增加硬件或只需要增加少量硬件就能夠把不增加硬件或只需要增加少量硬件就能夠把處理機(jī)的運算速度提高幾倍處理機(jī)的運算速度提高幾倍 它是目前使用非常普遍的一種并行處理它是目前使用非常普遍的一種并行處理方式。方式。 本章學(xué)習(xí)標(biāo)量計算機(jī)上使用的流水加速技術(shù)。主要內(nèi)本章學(xué)習(xí)標(biāo)量計算機(jī)上使用

3、的流水加速技術(shù)。主要內(nèi)容有流水技術(shù)的分類、流水線性能指標(biāo)計算、非線性流水容有流水技術(shù)的分類、流水線性能指標(biāo)計算、非線性流水線的調(diào)度算法。線的調(diào)度算法。 標(biāo)量計算機(jī)指只能直接進(jìn)行標(biāo)量運算的計算機(jī)，與能標(biāo)量計算機(jī)指只能直接進(jìn)行標(biāo)量運算的計算機(jī)，與能夠直接進(jìn)行向量運算的向量計算機(jī)相對應(yīng)。夠直接進(jìn)行向量運算的向量計算機(jī)相對應(yīng)。 流水處理方式的特征，是讓多個依次啟動的任務(wù)，盡流水處理方式的特征，是讓多個依次啟動的任務(wù)，盡量同時使用系統(tǒng)的不同部件，通過時間重疊來提高處理速量同時使用系統(tǒng)的不同部件，通過時間重疊來提高處理速率。這種技術(shù)理論上不增加成本。率。這種技術(shù)理論上不增加成本。 標(biāo)量計算機(jī)上使用的流水加

4、速技術(shù)屬于指令級并行技標(biāo)量計算機(jī)上使用的流水加速技術(shù)屬于指令級并行技術(shù)。術(shù)。 每條指令的處理過程，可以劃分為取指、譯碼每條指令的處理過程，可以劃分為取指、譯碼、取數(shù)、運算、送結(jié)果、取數(shù)、運算、送結(jié)果5 5個子過程，也可以分得更個子過程，也可以分得更細(xì)或更粗一些。劃分的原則是各部分時間長度大細(xì)或更粗一些。劃分的原則是各部分時間長度大致相等、并使用致相等、并使用CPUCPU中不同的部件，這樣才有利于中不同的部件，這樣才有利于多任務(wù)重疊處理。多任務(wù)重疊處理。基本名詞術(shù)語基本名詞術(shù)語 標(biāo)量處理機(jī)，超標(biāo)量處理機(jī)：標(biāo)量處理機(jī)指只能進(jìn)行標(biāo)量處理機(jī)，超標(biāo)量處理機(jī)：標(biāo)量處理機(jī)指只能進(jìn)行標(biāo)量運算的處理機(jī)，超標(biāo)量處

5、理機(jī)指能在一個時鐘周標(biāo)量運算的處理機(jī)，超標(biāo)量處理機(jī)指能在一個時鐘周期內(nèi)同時發(fā)射多條指令的處理機(jī)；期內(nèi)同時發(fā)射多條指令的處理機(jī)； 指令級并行技術(shù)：指能使多條指令并行執(zhí)行的技術(shù)，指令級并行技術(shù)：指能使多條指令并行執(zhí)行的技術(shù)，包括流水技術(shù)、多操作部件技術(shù)和超長指令字技術(shù)；包括流水技術(shù)、多操作部件技術(shù)和超長指令字技術(shù)； 流水線處理機(jī)，超流水線處理機(jī)：流水線處理機(jī)指用流水線處理機(jī)，超流水線處理機(jī)：流水線處理機(jī)指用流水作業(yè)方式并行解釋多條指令的處理機(jī)，超流水線流水作業(yè)方式并行解釋多條指令的處理機(jī)，超流水線處理機(jī)指能在一個時鐘周期內(nèi)分時發(fā)射多條指令的處處理機(jī)指能在一個時鐘周期內(nèi)分時發(fā)射多條指令的處理機(jī)；理機(jī)

6、； 超長指令字技術(shù)超長指令字技術(shù)VLIW：指讓一條指令包含多個獨立的：指讓一條指令包含多個獨立的操作字段，并且分別控制多個功能部件并行工作的技操作字段，并且分別控制多個功能部件并行工作的技術(shù)。術(shù)。 一重疊解釋方式一重疊解釋方式1.1.一條指令的幾個過程段一條指令的幾個過程段 1 1）取指令：根據(jù)）取指令：根據(jù)PCPC（指令計數(shù)器）從（指令計數(shù)器）從M M（存儲器）（存儲器）取出指令送到取出指令送到IRIR（指令寄存器）（指令寄存器） 2 2）譯碼分析：譯出指令的操作性質(zhì)，準(zhǔn)備好所需）譯碼分析：譯出指令的操作性質(zhì)，準(zhǔn)備好所需數(shù)據(jù)數(shù)據(jù) 3 3）執(zhí)行：將準(zhǔn)備好的數(shù)按譯出性質(zhì)進(jìn)行處理，主）執(zhí)行：將準(zhǔn)備

7、好的數(shù)按譯出性質(zhì)進(jìn)行處理，主要涉及要涉及ALUALU（算術(shù)邏輯運算部件）（算術(shù)邏輯運算部件） 2. 2. 對指令執(zhí)行的幾種方式對指令執(zhí)行的幾種方式1 1）順序執(zhí)行）順序執(zhí)行 ( (傳統(tǒng)機(jī)采用傳統(tǒng)機(jī)采用) ) 只有在前一條指令的各過程段全部完成后，才只有在前一條指令的各過程段全部完成后，才從存儲器取出下一條指令從存儲器取出下一條指令 2) 僅兩條指令重疊：第僅兩條指令重疊：第i i條指令的執(zhí)行與第條指令的執(zhí)行與第i+1i+1條的取指條的取指重疊。重疊。3) 三條指令重疊：第三條指令重疊：第i i條指令的執(zhí)行與第條指令的執(zhí)行與第i+1i+1條的譯碼及條的譯碼及第第i+2i+2條的取指重疊條的取指重

8、疊。 取 譯 執(zhí) 取 譯 執(zhí) i條 i +1條 i條取譯執(zhí) i+1條取譯執(zhí) i+2條取譯執(zhí)i 條取譯執(zhí)取譯執(zhí) i+1條 若一條指令的過程段劃分更多時，重疊組合方式更多。若一條指令的過程段劃分更多時，重疊組合方式更多。 重疊解釋并不能加快一條指令的實現(xiàn)，但能加快一段重疊解釋并不能加快一條指令的實現(xiàn)，但能加快一段程序的解釋。程序的解釋。1 1）條件：設(shè)一條指令分為三個過程段，各過程段分別）條件：設(shè)一條指令分為三個過程段，各過程段分別用用t t取取、t t譯譯、t t執(zhí)執(zhí)表示。表示。 執(zhí)行執(zhí)行K K條指令，分別采用順序執(zhí)行、兩條重疊、條指令，分別采用順序執(zhí)行、兩條重疊、三條重疊。三條重疊。假設(shè)假設(shè):

9、 :各個功能段時間相同各個功能段時間相同, ,公式見教材公式見教材P231P231各個功能段時間不相同各個功能段時間不相同, ,公式見公式見順序執(zhí)行順序執(zhí)行 k k* *（t t取取+t+t譯譯+t+t執(zhí)）執(zhí)）兩條重疊兩條重疊 t t取取+ k+ k* * t t譯譯+(k-1) +(k-1) * *( t( t取取,t,t執(zhí)執(zhí))max+ t)max+ t執(zhí)執(zhí)三條重疊三條重疊 t t取取+( t+( t譯譯, t, t取取)max+(k-2) )max+(k-2) * *（t t取取,t,t譯譯,t ,t 執(zhí)）執(zhí)）max+( tmax+( t執(zhí)執(zhí), t, t譯譯)max+ t)max+ t執(zhí)執(zhí)

10、3) 3) 例子例子 當(dāng)當(dāng)k=200k=200，t t取取=3t=3t，t t譯譯=4t=4t，t t執(zhí)執(zhí)=5t=5t，時，分別計算上述三種執(zhí)行方式的時間。時，分別計算上述三種執(zhí)行方式的時間。 順序執(zhí)行：順序執(zhí)行：200200(3+4+5)=2400t(3+4+5)=2400t 兩條重疊：兩條重疊：3+2003+2004+(200-1)4+(200-1)5+5=1803t5+5=1803t 三條重疊：三條重疊：3+4+(200-2)3+4+(200-2)5+5+5=1007t5+5+5=1007t4 4 重疊方式需要解決的問題重疊方式需要解決的問題1 1）對存儲器的頻繁訪問）對存儲器的頻繁訪問

11、 有哪些訪問：取指令、取操作有哪些訪問：取指令、取操作數(shù)、存放執(zhí)行結(jié)果數(shù)、存放執(zhí)行結(jié)果, I/O, I/O通道訪問通道訪問. . 希望存儲器為多體結(jié)構(gòu)，以適希望存儲器為多體結(jié)構(gòu)，以適應(yīng)多種訪問源的需要。應(yīng)多種訪問源的需要。 當(dāng)存儲器為單體結(jié)構(gòu)時，需要當(dāng)存儲器為單體結(jié)構(gòu)時，需要將訪問源排隊，先后順序為：將訪問源排隊，先后順序為： 取指令、取數(shù)據(jù)、取指令、取數(shù)據(jù)、I/OI/O通道訪問、存通道訪問、存結(jié)果結(jié)果 先行控制（先行控制（look-ahead）技術(shù)最早在）技術(shù)最早在IBM公司研制的公司研制的STRETCH機(jī)器中采用。目前，許多處理機(jī)中都已經(jīng)采機(jī)器中采用。目前，許多處理機(jī)中都已經(jīng)采用了這種技術(shù)

12、，包括超流水處理機(jī)和超標(biāo)量處理機(jī)等。用了這種技術(shù)，包括超流水處理機(jī)和超標(biāo)量處理機(jī)等。 先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)，以及兩先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)，以及兩者的結(jié)合。者的結(jié)合。 緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖棧，用以平滑它們的工作。緩沖棧，用以平滑它們的工作。 預(yù)處理技術(shù)是把進(jìn)入運算器的指令都處理成寄存器寄預(yù)處理技術(shù)是把進(jìn)入運算器的指令都處理成寄存器寄存器（存器（RR型）指令，為進(jìn)入運算器的指令準(zhǔn)備好所需要型）指令，為進(jìn)入運算器的指令準(zhǔn)備好所需要的全部操作數(shù)的全部操作數(shù)。5.1 5.1 先行控制技術(shù)

13、先行控制技術(shù)采用先行控制方式的處理機(jī)結(jié)構(gòu)采用先行控制方式的處理機(jī)結(jié)構(gòu)2）應(yīng)具有先行控制部件）應(yīng)具有先行控制部件 先行：在重疊操作中，當(dāng)前一條指令在執(zhí)行過程中先行：在重疊操作中，當(dāng)前一條指令在執(zhí)行過程中就需要提前取出后面的指令進(jìn)行相應(yīng)處理，這種提就需要提前取出后面的指令進(jìn)行相應(yīng)處理，這種提前取出后繼指令進(jìn)行相應(yīng)處理，稱為先行。前取出后繼指令進(jìn)行相應(yīng)處理，稱為先行。 先行控制部件的主要包括先行控制部件的主要包括 ）先行地址站，包括先行指令地址站和先行操作數(shù)）先行地址站，包括先行指令地址站和先行操作數(shù)地址站；地址站； ）先行指令站，用來存放多條指令；先行指令站，用來存放多條指令； ）先行操作數(shù)站先行

14、操作數(shù)站，用來存放多個操作數(shù)；用來存放多個操作數(shù)； ）先行地址形成部件，用來形成先行指令地址先行地址形成部件，用來形成先行指令地址 以及先行操作數(shù)地址；以及先行操作數(shù)地址； ）先行操作碼譯碼站，用來完成對多條指令的先行操作碼譯碼站，用來完成對多條指令的 譯碼并保留譯碼輸出狀態(tài)。譯碼并保留譯碼輸出狀態(tài)。 也應(yīng)具有后行部件也應(yīng)具有后行部件 后行部件：對指令執(zhí)行后的結(jié)果進(jìn)行處理的器件，稱后行部件：對指令執(zhí)行后的結(jié)果進(jìn)行處理的器件，稱 后行部件。包括：后行部件。包括：后行數(shù)地址站，提供后行數(shù)存放地址。后行數(shù)地址站，提供后行數(shù)存放地址。后行數(shù)站，存放運行的結(jié)果，并且，這些結(jié)果需送存后行數(shù)站，存放運行的結(jié)

15、果，并且，這些結(jié)果需送存 儲器。儲器。5.2.1 基本思想5.2 流水處理的概念5.2.2 流水技術(shù)流水技術(shù) 流水技術(shù)流水技術(shù)：將一個重復(fù)的時序過程分解成為若干個子：將一個重復(fù)的時序過程分解成為若干個子過程，而每個子過程都可有效地在其專用功能段上與其過程，而每個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行。他子過程同時執(zhí)行。 時空圖時空圖:從時間和空間兩個方面描述了流水線的工作從時間和空間兩個方面描述了流水線的工作過程。時空圖中，橫坐標(biāo)代表時間，縱坐標(biāo)代表流水過程。時空圖中，橫坐標(biāo)代表時間，縱坐標(biāo)代表流水線的各個段。線的各個段。 CPU中的各個部件按流水處理順序連接起來，就稱為一中的各

16、個部件按流水處理順序連接起來，就稱為一條條流水線流水線。5.2.3 流水線工作原理流水線工作原理流水線方式是把一個復(fù)雜的過程分解為若干個子過流水線方式是把一個復(fù)雜的過程分解為若干個子過程，每個子過程與其他子過程同時進(jìn)行。程，每個子過程與其他子過程同時進(jìn)行。處理機(jī)解釋程序的方式有順序方式、重疊方式、流處理機(jī)解釋程序的方式有順序方式、重疊方式、流水方式等水方式等 順序方式是解釋完一條指令再開始解釋下一條順序方式是解釋完一條指令再開始解釋下一條； 流水方式是把一個重復(fù)的過程分解為若干個子過流水方式是把一個重復(fù)的過程分解為若干個子過程，每個子過程可以與其它子過程同時進(jìn)行，以此程，每個子過程可以與其它子

17、過程同時進(jìn)行，以此提高單位時間內(nèi)解釋指令的數(shù)目提高單位時間內(nèi)解釋指令的數(shù)目； 重疊方式是一種簡單的流水方式，它把指令分成重疊方式是一種簡單的流水方式，它把指令分成2個子過程個子過程 每條指令只與下一條指令相重疊每條指令只與下一條指令相重疊。 重疊方式流水線重疊方式流水線當(dāng)分析部件完成上一條指令的當(dāng)分析部件完成上一條指令的“分析分析”后，就立即將之送入后，就立即將之送入執(zhí)行部件，同時分析部件可以開始處理下一條指令。執(zhí)行部件，同時分析部件可以開始處理下一條指令。雖然從執(zhí)行一條指令的全過程來看，仍需要雖然從執(zhí)行一條指令的全過程來看，仍需要2t的時間，但從的時間，但從機(jī)器的輸出端來看，卻是每隔一個機(jī)器

18、的輸出端來看，卻是每隔一個t就能給出一條指令的執(zhí)就能給出一條指令的執(zhí)行結(jié)果。行結(jié)果。 流水線結(jié)構(gòu)圖 流水線工作時空圖流水線工作時空圖 空間（段號） 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 16 時間（拍） (a) 順序方式 空間（段號） 1 2 3 4 1 2 3 4 10 時間（拍） (b) 重疊方式 空間（段號） 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 7 時間（拍） t (c) 流水方式 圖 3.2 CPU 工作時空圖 5.2.4 5.2.4 流水線的特點流水線的特點1. 流水過程由多個相聯(lián)系的子過程組成，每個子過程稱流水過程由多個相聯(lián)系的

19、子過程組成，每個子過程稱為流水線的級或段，段的數(shù)目稱為流水線的深度。為流水線的級或段，段的數(shù)目稱為流水線的深度。2. 在流水線中處理的必須是連續(xù)任務(wù)，只有不斷的提供在流水線中處理的必須是連續(xù)任務(wù)，只有不斷的提供任務(wù)才能充分發(fā)揮流水線的效率。任務(wù)才能充分發(fā)揮流水線的效率。3. 把一個任務(wù)分解為幾個有聯(lián)系的子任務(wù)，每個子任務(wù)把一個任務(wù)分解為幾個有聯(lián)系的子任務(wù)，每個子任務(wù)由一個專門的功能部件來實現(xiàn)。由一個專門的功能部件來實現(xiàn)。4. 在流水線的每一個功能部件的后面都要有一個緩沖器在流水線的每一個功能部件的后面都要有一個緩沖器，用于保存本段的執(zhí)行結(jié)果。，用于保存本段的執(zhí)行結(jié)果。6. 流水線需要有流水線需

20、要有“裝入時間裝入時間”和和“排空時間排空時間”。5.3 5.3 流水技術(shù)的分類流水技術(shù)的分類1）按各過程段用時是否全等劃分）按各過程段用時是否全等劃分 均勻流水線：各過程段用時全等均勻流水線：各過程段用時全等 非均勻流水線：各過程段用時不全等（如非均勻流水線：各過程段用時不全等（如上圖）上圖） ）時間匹配的均勻流水線。）時間匹配的均勻流水線。 ）時間不匹配的非均勻流水線。）時間不匹配的非均勻流水線。 1t2t32t4t2）按處理的數(shù)據(jù)類型）按處理的數(shù)據(jù)類型標(biāo)量流水線：用于對標(biāo)量數(shù)據(jù)進(jìn)行流水處標(biāo)量流水線：用于對標(biāo)量數(shù)據(jù)進(jìn)行流水處理。理。向量流水線：用于對向量數(shù)據(jù)進(jìn)行流水處向量流水線：用于對向量

21、數(shù)據(jù)進(jìn)行流水處理。（向量很適合流水處理）理。（向量很適合流水處理）3）按流水線的規(guī)模）按流水線的規(guī)模操作流水線：如將一條指令劃分為多個過操作流水線：如將一條指令劃分為多個過程段進(jìn)行流水處理。規(guī)模最小程段進(jìn)行流水處理。規(guī)模最小指令流水線：以指令為單位進(jìn)行處理，用指令流水線：以指令為單位進(jìn)行處理，用于多進(jìn)程、多任務(wù)。規(guī)模較大于多進(jìn)程、多任務(wù)。規(guī)模較大 宏流水線：以程序的邏輯功能段為單位宏流水線：以程序的邏輯功能段為單位進(jìn)行流水處理。規(guī)模最大進(jìn)行流水處理。規(guī)模最大4）按流水線具有功能的多少）按流水線具有功能的多少 單功能流水線：各過程段之間固定連接，單功能流水線：各過程段之間固定連接，不能重新構(gòu)成其

22、它流水線不能重新構(gòu)成其它流水線固定流水線固定流水線 多功能流水線分：多功能流水線分： 靜態(tài)流水線：各過程段之間可重新連接，靜態(tài)流水線：各過程段之間可重新連接，但不同時刻只能重構(gòu)成一種不同的流水線。但不同時刻只能重構(gòu)成一種不同的流水線。 動態(tài)流水線：各過程段之間可重新連接，動態(tài)流水線：各過程段之間可重新連接，不同時刻可重構(gòu)成多種流水線。不同時刻可重構(gòu)成多種流水線。 5）按部件在同一時刻送出支路數(shù)的多少來分。）按部件在同一時刻送出支路數(shù)的多少來分。一維一維流水線：在同一時刻，部件只能向流水線：在同一時刻，部件只能向一個地方傳送結(jié)果。一個地方傳送結(jié)果。 陣列流水線：在同一時刻，部件可同時陣列流水線：

23、在同一時刻，部件可同時向多個地方傳送結(jié)果。向多個地方傳送結(jié)果。5.4.5 “5.4.5 “瓶頸瓶頸”問題及其解決方法問題及其解決方法 瓶頸：瓶頸就是瓶頸：瓶頸就是titi最大的段，它使流水線最大的段，它使流水線“流流速速”減慢。減慢。S1S1S2S2S3S3S4S4tt3t3t tttt 方法方法1 1：再細(xì)分：再細(xì)分 將瓶頸設(shè)備再細(xì)分為下一級將瓶頸設(shè)備再細(xì)分為下一級流水線流水線S1S1S2aS2aS2bS2bS2cS2cS3S3S4S4tttttttttttt 方法方法2 2：并行設(shè)置：并行設(shè)置 將瓶頸設(shè)備重復(fù)設(shè)置多套。將瓶頸設(shè)備重復(fù)設(shè)置多套。衡量流水線的主要指標(biāo)有吞吐率，加速比和效率。衡量

24、流水線的主要指標(biāo)有吞吐率，加速比和效率。5.4.1 5.4.1 吞吐率吞吐率TPTP吞吐率（吞吐率（TP ThroughPut）指流水線在單位時間內(nèi)執(zhí)行的任務(wù)數(shù)，）指流水線在單位時間內(nèi)執(zhí)行的任務(wù)數(shù)，可以用輸入任務(wù)數(shù)或輸出任務(wù)數(shù)表示?？梢杂幂斎肴蝿?wù)數(shù)或輸出任務(wù)數(shù)表示。 其中其中k表示流水線劃分的段數(shù)。表示流水線劃分的段數(shù)。 當(dāng)滿足當(dāng)滿足 條件時，有條件時，有 。5.4 5.4 線性流水線性能分析線性流水線性能分析kTnTP ttitknTk) 1( S4 1 2 3 4 N-1 N S3 1 2 3 4 N-1 N S2 1 2 3 4 N-1 N S1 1 2 3 4 N-1 N 時間 KT

25、(N-1)T NT (K-1)T Tk 流水線產(chǎn)生流水線產(chǎn)生n n個結(jié)果所需要的時間：個結(jié)果所需要的時間： 實際吞吐率實際吞吐率： 最大吞吐率：最大吞吐率： 最大吞吐率與實際吞吐率的關(guān)系：最大吞吐率與實際吞吐率的關(guān)系：（1 1）流水線各段的執(zhí)行時間相等流水線各段的執(zhí)行時間相等(1 )kTknt(1 )nT Pkntm a x1(1 )nnT PL imtknt m a x(1 )nT PT Pkn 實際吞吐率：實際吞吐率： 最大吞吐率：最大吞吐率： （2 2） 流水線各段的執(zhí)行時間不等流水線各段的執(zhí)行時間不等121(1) m ax(,)kikiT Ptntttn12m axm ax(,)1kT

26、 Pttt5.4.2 5.4.2 加速比（即吞吐率之比，）加速比（即吞吐率之比，）koTTS kiiotnT1不使用流水線所用的時間與使用流水線所用的時間之比不使用流水線所用的時間與使用流水線所用的時間之比一般表示：一般表示：s=Ts=T0 0/T/TK K其中其中 實際加速比：實際加速比：最大加速比：最大加速比：(1)1kntknSkntkn m a x(1 )nknSL imkkn kiiotnT1段效率：，各段平均效率：其中 表示第i段設(shè)備量占整條流水線全部設(shè)備量的百分比當(dāng)滿足 條件（即等長、等權(quán)）時，有：5.4.3 5.4.3 效率（設(shè)備利用率效率（設(shè)備利用率）kiiTtnEkiiiE

27、E1)(kttii1和ikSTkTtTknEkEkikikoiki11)(1上式指出，S=Ek，就是說當(dāng)效率達(dá)到100%時，流水方式（一個任務(wù)/t）吞吐率為順序方式（一個任務(wù)/(kt)）的k倍。實際效率：實際效率：最大效率：最大效率：(1)1kntnEkkntkn max11nnELimkn瓶頸問題用兩種方法改進(jìn)后的效率瓶頸問題用兩種方法改進(jìn)后的效率和吞吐率和吞吐率靜態(tài)雙功能流水線的效率與吞吐率 教材P241非線性流水線的吞吐率和效率 教材P291 5.5 5.5 流水線中的相關(guān)流水線中的相關(guān)相關(guān)的定義：相關(guān)的定義： 流水線中的相關(guān)是指相鄰或相近的指令因存在某種關(guān)聯(lián)，流水線中的相關(guān)是指相鄰或相

28、近的指令因存在某種關(guān)聯(lián)，后面的指令不能在原指定的時鐘周期開始執(zhí)行。后面的指令不能在原指定的時鐘周期開始執(zhí)行。一般來說，流水線中的相關(guān)主要分為如下三種類型：一般來說，流水線中的相關(guān)主要分為如下三種類型：1.1. 結(jié)構(gòu)相關(guān)：當(dāng)硬件資源滿足不了指令重疊執(zhí)行的要求，結(jié)構(gòu)相關(guān)：當(dāng)硬件資源滿足不了指令重疊執(zhí)行的要求，而發(fā)生資源沖突時，就發(fā)生了結(jié)構(gòu)相關(guān)。而發(fā)生資源沖突時，就發(fā)生了結(jié)構(gòu)相關(guān)。2.2. 數(shù)據(jù)相關(guān)：當(dāng)一條指令需要用到前面指令的執(zhí)行結(jié)果，數(shù)據(jù)相關(guān)：當(dāng)一條指令需要用到前面指令的執(zhí)行結(jié)果，而這些指令均在流水線中重疊執(zhí)行時，就可能引起數(shù)據(jù)而這些指令均在流水線中重疊執(zhí)行時，就可能引起數(shù)據(jù)相關(guān)。相關(guān)。 3.

29、3. 控制相關(guān)：當(dāng)流水線遇到分支指令和其它能夠改變控制相關(guān)：當(dāng)流水線遇到分支指令和其它能夠改變 PC PC 值的指令時，就會發(fā)生控制相關(guān)。值的指令時，就會發(fā)生控制相關(guān)。 一旦流水線中出現(xiàn)相關(guān)，必然會給指令在流水線中一旦流水線中出現(xiàn)相關(guān)，必然會給指令在流水線中的順利執(zhí)行帶來許多問題，如果不能很好地解決的順利執(zhí)行帶來許多問題，如果不能很好地解決相關(guān)問題，輕則影響流水線的性能，重則導(dǎo)致錯相關(guān)問題，輕則影響流水線的性能，重則導(dǎo)致錯誤的執(zhí)行結(jié)果。消除相關(guān)的基本方法是讓流水線誤的執(zhí)行結(jié)果。消除相關(guān)的基本方法是讓流水線暫停執(zhí)行某些指令，而繼續(xù)執(zhí)行其它一些指令。暫停執(zhí)行某些指令，而繼續(xù)執(zhí)行其它一些指令。 在后

30、面的討論中，我們約定：當(dāng)一條指在后面的討論中，我們約定：當(dāng)一條指令被暫停時，在該暫停指令之后發(fā)射的所有指令令被暫停時，在該暫停指令之后發(fā)射的所有指令都要被暫停，而在該暫停之前發(fā)射的指令則可繼都要被暫停，而在該暫停之前發(fā)射的指令則可繼續(xù)進(jìn)行，在暫停期間，流水線不會取新的指令續(xù)進(jìn)行，在暫停期間，流水線不會取新的指令。 5.5.1 5.5.1 結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān)如果某些指令組合在流水線中重疊執(zhí)行時，產(chǎn)如果某些指令組合在流水線中重疊執(zhí)行時，產(chǎn)生資源沖突，則稱該流水線有結(jié)構(gòu)相關(guān)。為了生資源沖突，則稱該流水線有結(jié)構(gòu)相關(guān)。為了能夠在流水線中順利執(zhí)行指令的所有可能組合，能夠在流水線中順利執(zhí)行指令的所有可能組合，

31、而不發(fā)生結(jié)構(gòu)相關(guān)，通常需要采用流水化功能而不發(fā)生結(jié)構(gòu)相關(guān)，通常需要采用流水化功能單元的方法或資源重復(fù)的方法。單元的方法或資源重復(fù)的方法。 許多流水線機(jī)器都是將數(shù)據(jù)和指令保存在同一存儲許多流水線機(jī)器都是將數(shù)據(jù)和指令保存在同一存儲器中。如果在某個時鐘周期內(nèi)，流水線既要完成器中。如果在某個時鐘周期內(nèi)，流水線既要完成某條指令對數(shù)據(jù)的存儲器訪問操作，又要完成取某條指令對數(shù)據(jù)的存儲器訪問操作，又要完成取指令的操作，那么將會發(fā)生存儲器訪問沖突問題指令的操作，那么將會發(fā)生存儲器訪問沖突問題 產(chǎn)生結(jié)構(gòu)相關(guān)。為了解決這個問題，可以讓流水產(chǎn)生結(jié)構(gòu)相關(guān)。為了解決這個問題，可以讓流水線完成前一條指令對數(shù)據(jù)的存儲器訪問時

32、，暫停線完成前一條指令對數(shù)據(jù)的存儲器訪問時，暫停取后一條指令的操作。該周期稱為流水線的一個取后一條指令的操作。該周期稱為流水線的一個暫停周期。暫停周期一般也稱為流水線氣泡，或暫停周期。暫停周期一般也稱為流水線氣泡，或簡稱為簡稱為“氣泡氣泡”。在流水線中插入暫停周期可以。在流水線中插入暫停周期可以消除這種結(jié)構(gòu)相關(guān)。消除這種結(jié)構(gòu)相關(guān)。 結(jié)構(gòu)相關(guān)舉例訪存沖突結(jié)構(gòu)相關(guān)舉例訪存沖突 為為消除結(jié)構(gòu)相關(guān)插入流水氣泡消除結(jié)構(gòu)相關(guān)插入流水氣泡 時空圖來表示暫停情況時空圖來表示暫停情況分析分析 為消除結(jié)構(gòu)相關(guān)而引入的暫停將影響流水線為消除結(jié)構(gòu)相關(guān)而引入的暫停將影響流水線的性能。為了避免結(jié)構(gòu)相關(guān)，可以考慮采用資的性

33、能。為了避免結(jié)構(gòu)相關(guān)，可以考慮采用資源重復(fù)的方法。比如，在流水線機(jī)器中設(shè)置相源重復(fù)的方法。比如，在流水線機(jī)器中設(shè)置相互獨立的指令存儲器和數(shù)據(jù)存儲器；也可以將互獨立的指令存儲器和數(shù)據(jù)存儲器；也可以將 Cache Cache 分割成指令分割成指令 Cache Cache 和數(shù)據(jù)和數(shù)據(jù) CacheCache。 假設(shè)不考慮流水線其它因素對流水線性能的假設(shè)不考慮流水線其它因素對流水線性能的影響，顯然如果流水線機(jī)器沒有結(jié)構(gòu)相關(guān)，那么影響，顯然如果流水線機(jī)器沒有結(jié)構(gòu)相關(guān)，那么其其 CPI CPI 也較小。然而，為什么有時流水線設(shè)計者也較小。然而，為什么有時流水線設(shè)計者卻允許結(jié)構(gòu)相關(guān)的存在呢？主要有兩個原因：

34、一卻允許結(jié)構(gòu)相關(guān)的存在呢？主要有兩個原因：一是為了減少硬件代價，二是為了減少功能單元的是為了減少硬件代價，二是為了減少功能單元的延遲。如果為了避免結(jié)構(gòu)相關(guān)而將流水線中的所延遲。如果為了避免結(jié)構(gòu)相關(guān)而將流水線中的所有功能單元完全流水化，或者設(shè)置足夠的硬件資有功能單元完全流水化，或者設(shè)置足夠的硬件資源，那么所帶來的硬件代價必定很大。源，那么所帶來的硬件代價必定很大。 5.5.2 5.5.2 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)當(dāng)指令在流水線中重疊執(zhí)行時，流水線有可能改變指令當(dāng)指令在流水線中重疊執(zhí)行時，流水線有可能改變指令讀讀/寫操作數(shù)的順序，使得讀寫操作數(shù)的順序，使得讀/寫操作順序不同于它們非寫操作順序不同于它們非流

35、水實現(xiàn)的順序，這將導(dǎo)致數(shù)據(jù)相關(guān)。流水實現(xiàn)的順序，這將導(dǎo)致數(shù)據(jù)相關(guān)。 ADD R1，R2，R3SUBR4，R5，R1AND R6，R1，R7ORR8，R1，R9XORR10，R1， R11 ADD ADD指令后的所有指令都要用到指令后的所有指令都要用到ADDADD指指令的計算結(jié)果，令的計算結(jié)果，ADD ADD 指令在指令在 WB WB 段才將計段才將計算結(jié)果寫入寄存器算結(jié)果寫入寄存器 R1 R1 中，但是中，但是 SUB SUB 指令指令在其在其 ID ID 段就要從寄存器段就要從寄存器 R1 R1 中讀取該計中讀取該計算結(jié)果，這種情況就叫做數(shù)據(jù)相關(guān)。除非算結(jié)果，這種情況就叫做數(shù)據(jù)相關(guān)。除非有措

36、施防止這一情況出現(xiàn)，否則有措施防止這一情況出現(xiàn)，否則 SUB SUB 指令指令讀到的是錯誤的值。所以，為了保證上述讀到的是錯誤的值。所以，為了保證上述指令序列的正確執(zhí)行，流水線只好暫停指令序列的正確執(zhí)行，流水線只好暫停 ADD ADD 指令之后的所有指令，直到指令之后的所有指令，直到 ADD ADD 指令指令將計算結(jié)果寫入寄存器將計算結(jié)果寫入寄存器 R1 R1 之后，再啟動之后，再啟動 ADD ADD 指令之后的指令繼續(xù)執(zhí)行。指令之后的指令繼續(xù)執(zhí)行。 數(shù)據(jù)相關(guān)舉例數(shù)據(jù)相關(guān)舉例例子分析例子分析 從上圖還可以看到，從上圖還可以看到， AND AND 指令同樣也將受到這種相關(guān)關(guān)指令同樣也將受到這種相

37、關(guān)關(guān)系的影響。系的影響。 ADD ADD 指令只有到第五個時鐘周期末尾才能結(jié)束對指令只有到第五個時鐘周期末尾才能結(jié)束對寄存器寄存器 R1 R1 的寫操作，所以的寫操作，所以 AND AND 指令在第四個時鐘周期從寄指令在第四個時鐘周期從寄存器存器 R1 R1 中讀出的值也是錯誤的。而中讀出的值也是錯誤的。而 XOR XOR 指令則可以正常操指令則可以正常操作，因為它是在第六個時鐘周期讀寄存器作，因為它是在第六個時鐘周期讀寄存器 R1 R1 的內(nèi)容。的內(nèi)容。另外，利用流水線的一種簡單技術(shù)，可以使流水線順利另外，利用流水線的一種簡單技術(shù)，可以使流水線順利執(zhí)行執(zhí)行 OR OR 指令。這種技術(shù)就是：在

38、流水線中，約定在時鐘周指令。這種技術(shù)就是：在流水線中，約定在時鐘周期的后半部分進(jìn)行寄存器文件的讀操作，而在時鐘周期的前期的后半部分進(jìn)行寄存器文件的讀操作，而在時鐘周期的前半部分進(jìn)行寄存器文件的寫操作。在圖中，我們將寄存器文半部分進(jìn)行寄存器文件的寫操作。在圖中，我們將寄存器文件的邊框適當(dāng)?shù)禺嫵商摼€來表示這種技術(shù)。件的邊框適當(dāng)?shù)禺嫵商摼€來表示這種技術(shù)。通過定向技術(shù)減少數(shù)據(jù)相關(guān)帶來的暫停通過定向技術(shù)減少數(shù)據(jù)相關(guān)帶來的暫停數(shù)據(jù)相關(guān)問題可以采用一種稱為定向（也稱為旁數(shù)據(jù)相關(guān)問題可以采用一種稱為定向（也稱為旁路或短路）的簡單技術(shù)來解決路或短路）的簡單技術(shù)來解決 。定向技術(shù)的主要。定向技術(shù)的主要思想是：在某

39、條指令（如圖中的思想是：在某條指令（如圖中的 ADD ADD 指令）產(chǎn)生指令）產(chǎn)生一個計算結(jié)果之前，其它指令（如圖中的一個計算結(jié)果之前，其它指令（如圖中的 SUB SUB 和和 AND AND 指令）并不真正需要該計算結(jié)果，如果能夠指令）并不真正需要該計算結(jié)果，如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方（寄存器文件將該計算結(jié)果從其產(chǎn)生的地方（寄存器文件 EX/MEMEX/MEM）直接送到其它指令需要它的地方（）直接送到其它指令需要它的地方（ALU ALU 的輸入寄存器），那么就可以避免暫停的輸入寄存器），那么就可以避免暫停. . 基于這種考慮，定向技術(shù)的要點可以歸納基于這種考慮，定向技術(shù)的要點可以歸納

40、為：為： 寄存器文件寄存器文件 EX/MEM EX/MEM 中的中的 ALU ALU 的運算結(jié)果總的運算結(jié)果總是回送到是回送到 ALU ALU 的輸入寄存器；的輸入寄存器；當(dāng)定向硬件檢測到前一個當(dāng)定向硬件檢測到前一個 ALU ALU 運算結(jié)果的寫運算結(jié)果的寫入寄存器就是當(dāng)前入寄存器就是當(dāng)前 ALU ALU 操作的源寄存器時，操作的源寄存器時，那么控制邏輯將前一個那么控制邏輯將前一個 ALU ALU 運算結(jié)果定向到運算結(jié)果定向到 ALU ALU 的輸入端，后一個的輸入端，后一個 ALU ALU 操作就不必從源操作就不必從源寄存器中讀取操作數(shù)。寄存器中讀取操作數(shù)。 流水線中的指令所需要的定向結(jié)果可

41、能并流水線中的指令所需要的定向結(jié)果可能并不僅僅是前一條指令的計算結(jié)果，而且還不僅僅是前一條指令的計算結(jié)果，而且還有可能是前面與其不相鄰指令的計算結(jié)果有可能是前面與其不相鄰指令的計算結(jié)果采用定向技術(shù)消除數(shù)據(jù)相關(guān)采用定向技術(shù)消除數(shù)據(jù)相關(guān)定向技術(shù)的推廣定向技術(shù)的推廣上述定向技術(shù)可以推廣到更一般的情況，可以將上述定向技術(shù)可以推廣到更一般的情況，可以將一個結(jié)果直接傳送到所有需要它的功能單元。也一個結(jié)果直接傳送到所有需要它的功能單元。也就是說，一個結(jié)果不僅可以從某一功能單元的輸就是說，一個結(jié)果不僅可以從某一功能單元的輸出定向到其自身的輸入，而且還可以從某一功能出定向到其自身的輸入，而且還可以從某一功能單元

42、的輸出定向到其它功能單元的輸入單元的輸出定向到其它功能單元的輸入 。前面的一些數(shù)據(jù)相關(guān)的實例均是有關(guān)寄存器操作前面的一些數(shù)據(jù)相關(guān)的實例均是有關(guān)寄存器操作數(shù)的，但是數(shù)據(jù)相關(guān)也有可能發(fā)生在一對指令對數(shù)的，但是數(shù)據(jù)相關(guān)也有可能發(fā)生在一對指令對存儲器同一單元進(jìn)行讀寫的時候。不過，本章僅存儲器同一單元進(jìn)行讀寫的時候。不過，本章僅討論有關(guān)寄存器的數(shù)據(jù)相關(guān)。討論有關(guān)寄存器的數(shù)據(jù)相關(guān)。到數(shù)據(jù)存儲器和到數(shù)據(jù)存儲器和ALUALU的定向路徑的定向路徑數(shù)據(jù)相關(guān)分類數(shù)據(jù)相關(guān)分類根據(jù)指令對寄存器的讀寫順序，可以將數(shù)據(jù)相關(guān)分為三根據(jù)指令對寄存器的讀寫順序，可以將數(shù)據(jù)相關(guān)分為三類。習(xí)慣上，這些相關(guān)是根據(jù)流水線所必須保持的訪問

43、類。習(xí)慣上，這些相關(guān)是根據(jù)流水線所必須保持的訪問順序來命名的?？紤]流水線中的兩條指令順序來命名的?？紤]流水線中的兩條指令 i i 和和 j j ，且，且 i i 在在 j j 之前進(jìn)入流水線，由此可能帶來的數(shù)據(jù)相關(guān)有：之前進(jìn)入流水線，由此可能帶來的數(shù)據(jù)相關(guān)有： 寫后讀相關(guān)（寫后讀相關(guān)（Read After Write，RAW）：）：j 的執(zhí)行要的執(zhí)行要用到用到 i 的計算結(jié)果，當(dāng)它們在流水線中重疊執(zhí)行時，的計算結(jié)果，當(dāng)它們在流水線中重疊執(zhí)行時，j 可能在可能在 i 寫入其計算結(jié)果之前就先行對保存該結(jié)果的寄寫入其計算結(jié)果之前就先行對保存該結(jié)果的寄存器進(jìn)行讀操作，從而得到錯誤的值。這是最常見的存器

44、進(jìn)行讀操作，從而得到錯誤的值。這是最常見的一種數(shù)據(jù)相關(guān)，采用定向技術(shù)消除的數(shù)據(jù)相關(guān)就屬于一種數(shù)據(jù)相關(guān)，采用定向技術(shù)消除的數(shù)據(jù)相關(guān)就屬于這種類型。這種類型。 寫后寫相關(guān)（寫后寫相關(guān)（Write After WriteWrite After Write，WAWWAW）：）：j j 和和 i i 的目的寄存器相同，當(dāng)它們在流水線中重疊執(zhí)的目的寄存器相同，當(dāng)它們在流水線中重疊執(zhí)行時，行時，j j 可能在可能在 i i 寫入其計算結(jié)果之前就先行對寫入其計算結(jié)果之前就先行對該結(jié)果寄存器進(jìn)行寫操作，從而導(dǎo)致寫入順序錯該結(jié)果寄存器進(jìn)行寫操作，從而導(dǎo)致寫入順序錯誤，在目的寄存器中留下的是誤，在目的寄存器中留下的

45、是 i i 寫入的值，而不寫入的值，而不是是 j j 寫入的值。寫入的值。如果在流水線中不只一個段可以進(jìn)行寫操作，或如果在流水線中不只一個段可以進(jìn)行寫操作，或者當(dāng)流水線暫停某條指令時，允許該指令之后的者當(dāng)流水線暫停某條指令時，允許該指令之后的指令繼續(xù)前進(jìn)，就可能會產(chǎn)生這種類型的數(shù)據(jù)相指令繼續(xù)前進(jìn)，就可能會產(chǎn)生這種類型的數(shù)據(jù)相關(guān)。關(guān)。 讀后寫相關(guān)（讀后寫相關(guān)（Write After ReadWrite After Read，WARWAR）：）：j j 可可能在能在 i i 讀取某個源寄存器的內(nèi)容之前就先對該寄讀取某個源寄存器的內(nèi)容之前就先對該寄存器進(jìn)行寫操作，導(dǎo)致存器進(jìn)行寫操作，導(dǎo)致 i i 后

46、來讀取到的值是錯誤后來讀取到的值是錯誤的。的。需要暫停的數(shù)據(jù)相關(guān)需要暫停的數(shù)據(jù)相關(guān)前面我們討論了如何利用定向技術(shù)消除由于數(shù)據(jù)相關(guān)帶前面我們討論了如何利用定向技術(shù)消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。以通過定向技術(shù)消除。對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法流水線常常會遇到許多種類型的暫停。比如，采用典型的代碼流水線常常會遇到許多種類型的暫停。比如，采用典型的代碼生成方法對生成方法對A=BC這種常用的表達(dá)式進(jìn)行處理，可以得到如圖這種常用的表達(dá)式進(jìn)行處理，可以得到如圖所示的指令序列。從圖中

47、可以看出，在所示的指令序列。從圖中可以看出，在 ADD 指令的流水過程中指令的流水過程中必須插入一個暫停時鐘周期，以保證變量必須插入一個暫停時鐘周期，以保證變量C的讀入值有效。既然的讀入值有效。既然定向無法消除指令序列中所包含的這種暫停，那么能否讓編譯定向無法消除指令序列中所包含的這種暫停，那么能否讓編譯器在進(jìn)行代碼生成時就消除這些潛在的暫停呢？器在進(jìn)行代碼生成時就消除這些潛在的暫停呢？指令級調(diào)度指令級調(diào)度實際上，編譯器的確可以通過重新組織代碼順序來消除實際上，編譯器的確可以通過重新組織代碼順序來消除這種暫停。通常稱這種重新組織代碼順序消除暫停的技這種暫停。通常稱這種重新組織代碼順序消除暫停的

48、技術(shù)為流水線調(diào)度（術(shù)為流水線調(diào)度（pipeline schedulingpipeline scheduling）或指令調(diào)度）或指令調(diào)度（instruction schedulinginstruction scheduling）。）。 5.5.3 5.5.3 控制相關(guān)控制相關(guān)在流水線上執(zhí)行分支指令時，在流水線上執(zhí)行分支指令時，PC 值有兩種可能值有兩種可能的變化情況。一種是的變化情況。一種是 PC 值發(fā)生改變（為分支轉(zhuǎn)值發(fā)生改變（為分支轉(zhuǎn)移的目標(biāo)地址）；一種是移的目標(biāo)地址）；一種是 PC 值保持正常。如果值保持正常。如果一條分支指令將一條分支指令將PC值改變?yōu)榉种мD(zhuǎn)移的目標(biāo)地值改變?yōu)榉种мD(zhuǎn)移的目

49、標(biāo)地址，那么我們稱分支轉(zhuǎn)移成功；如果分支轉(zhuǎn)移址，那么我們稱分支轉(zhuǎn)移成功；如果分支轉(zhuǎn)移條件不成立，條件不成立，PC 值保持正常，我們稱分支轉(zhuǎn)移值保持正常，我們稱分支轉(zhuǎn)移失敗。失敗。處理分支指令最簡單的方法是：一旦在流水線中處理分支指令最簡單的方法是：一旦在流水線中檢測到某條指令是分支指令，就暫停執(zhí)行該分支檢測到某條指令是分支指令，就暫停執(zhí)行該分支指令之后的所有指令，直到分支指令到達(dá)流水線指令之后的所有指令，直到分支指令到達(dá)流水線的的 MEM 段，確定了新的段，確定了新的 PC 值為止。我們當(dāng)然值為止。我們當(dāng)然不希望流水線還沒有確定某條指令是分支指令之不希望流水線還沒有確定某條指令是分支指令之前就

50、暫停執(zhí)行指令，所以對分支指令而言，當(dāng)流前就暫停執(zhí)行指令，所以對分支指令而言，當(dāng)流水線完成其譯碼操作（水線完成其譯碼操作（ID段）之后才會暫停執(zhí)行段）之后才會暫停執(zhí)行其后繼指令。其后繼指令。根據(jù)上述處理分支指令的方法，可以得到如根據(jù)上述處理分支指令的方法，可以得到如圖所示流水線時空圖圖所示流水線時空圖 。從圖中可以看出，在流水。從圖中可以看出，在流水線中插入了兩個暫停周期，當(dāng)分支指令在線中插入了兩個暫停周期，當(dāng)分支指令在 MEM 段確定新的段確定新的 PC 值后，流水線作廢分支直接后繼值后，流水線作廢分支直接后繼指令的指令的 IF 周期（相當(dāng)于一個暫停周期），按照周期（相當(dāng)于一個暫停周期），按照

51、新的有效新的有效 PC 值取指令。值取指令。減少分支暫停時鐘周期數(shù)減少分支暫停時鐘周期數(shù)減少流水線處理分支指令時的暫停時鐘周期數(shù)有如下減少流水線處理分支指令時的暫停時鐘周期數(shù)有如下兩種途徑：兩種途徑：1. 在流水線中盡早判斷出分支轉(zhuǎn)移是否成功；在流水線中盡早判斷出分支轉(zhuǎn)移是否成功；2. 盡早計算出分支轉(zhuǎn)移成功時的盡早計算出分支轉(zhuǎn)移成功時的 PC 值（即分支的目值（即分支的目標(biāo)地址）。標(biāo)地址）。 為了優(yōu)化處理分支指令，在流水線中應(yīng)該同時為了優(yōu)化處理分支指令，在流水線中應(yīng)該同時采用上述兩條途徑，缺一不可。即使知道分支轉(zhuǎn)移采用上述兩條途徑，缺一不可。即使知道分支轉(zhuǎn)移的目標(biāo)地址，而不知道分支轉(zhuǎn)移是否成

52、功對減少暫的目標(biāo)地址，而不知道分支轉(zhuǎn)移是否成功對減少暫停是徒勞的；知道分支轉(zhuǎn)移是否成功，而不知道分停是徒勞的；知道分支轉(zhuǎn)移是否成功，而不知道分支轉(zhuǎn)移的目標(biāo)地址，同樣對降低分支損失毫無幫助。支轉(zhuǎn)移的目標(biāo)地址，同樣對降低分支損失毫無幫助。下面讓我們看看如何基于這些思想，從硬件上改進(jìn)下面讓我們看看如何基于這些思想，從硬件上改進(jìn)流水線，達(dá)到降低分支損失的目的。流水線，達(dá)到降低分支損失的目的。在流水線中，分支指令通常需要測試分支條件寄在流水線中，分支指令通常需要測試分支條件寄存器的值是否為存器的值是否為0，所以可以把測試分支條件寄，所以可以把測試分支條件寄存器的操作移到存器的操作移到 ID 段完成，從而

53、使得在段完成，從而使得在 ID 周期周期末就完成分支轉(zhuǎn)移成功與否的檢測。末就完成分支轉(zhuǎn)移成功與否的檢測。另外，由于要盡早計算出兩個另外，由于要盡早計算出兩個 PC 值（分支值（分支轉(zhuǎn)移成功和失敗時的轉(zhuǎn)移成功和失敗時的 PC 值），也可以將計算分值），也可以將計算分支目標(biāo)地址的操作移到支目標(biāo)地址的操作移到 ID 段完成。為此，需要段完成。為此，需要在在 ID 段增設(shè)一個加法器（注意，為了避免結(jié)構(gòu)段增設(shè)一個加法器（注意，為了避免結(jié)構(gòu)相關(guān)，不能用相關(guān)，不能用EX段的段的 ALU 功能部件來計算分支功能部件來計算分支轉(zhuǎn)移目標(biāo)地址）。下圖是對流水線進(jìn)行上述改進(jìn)轉(zhuǎn)移目標(biāo)地址）。下圖是對流水線進(jìn)行上述改進(jìn)后

54、的流水線數(shù)據(jù)通路。容易看出，基于上述改進(jìn)后的流水線數(shù)據(jù)通路。容易看出，基于上述改進(jìn)后的流水線數(shù)據(jù)通路，處理分支指令只需要一個后的流水線數(shù)據(jù)通路，處理分支指令只需要一個時鐘周期的暫停。時鐘周期的暫停。減少分支暫停時鐘周期數(shù)減少分支暫停時鐘周期數(shù)降低流水線分支損失的方法有許多種。前面論降低流水線分支損失的方法有許多種。前面論述了改進(jìn)流水線硬件減少流水線暫停周期的方述了改進(jìn)流水線硬件減少流水線暫停周期的方法。這里主要從編譯技術(shù)的角度，論述四種降法。這里主要從編譯技術(shù)的角度，論述四種降低流水線分支損失的簡單方法。首先需要說明低流水線分支損失的簡單方法。首先需要說明的是，這些方法對分支轉(zhuǎn)移成功與否進(jìn)行的

55、預(yù)的是，這些方法對分支轉(zhuǎn)移成功與否進(jìn)行的預(yù)測都是靜態(tài)的，并在整個程序的執(zhí)行過程中保測都是靜態(tài)的，并在整個程序的執(zhí)行過程中保持這種預(yù)測結(jié)論，即：要么總是認(rèn)為分支轉(zhuǎn)移持這種預(yù)測結(jié)論，即：要么總是認(rèn)為分支轉(zhuǎn)移成功，要么總是認(rèn)為分支轉(zhuǎn)移失敗。成功，要么總是認(rèn)為分支轉(zhuǎn)移失敗。1.1. 凍結(jié)（凍結(jié)（freezefreeze）或排空（）或排空（flushflush）流水線的方法）流水線的方法在流水線中，處理分支最簡單的方法是凍結(jié)或在流水線中，處理分支最簡單的方法是凍結(jié)或排空流水線，保持或清除流水線在分支指令之排空流水線，保持或清除流水線在分支指令之后讀入的任何指令，直到知道分支指令的目標(biāo)后讀入的任何指令，直

56、到知道分支指令的目標(biāo)地址以及分支轉(zhuǎn)移是否成功為止。這種方法優(yōu)地址以及分支轉(zhuǎn)移是否成功為止。這種方法優(yōu)點在于其對硬件和軟件的要求都十分簡單，我點在于其對硬件和軟件的要求都十分簡單，我們前面采用的就是這種方法。們前面采用的就是這種方法。2.2. 預(yù)測分支失敗的方法預(yù)測分支失敗的方法 如果流水線采用預(yù)測分支失敗的方法處理分支如果流水線采用預(yù)測分支失敗的方法處理分支指令，那么當(dāng)流水線譯碼到一條分支指令時，流水指令，那么當(dāng)流水線譯碼到一條分支指令時，流水線繼續(xù)取指令，并允許該分支指令后的指令繼續(xù)在線繼續(xù)取指令，并允許該分支指令后的指令繼續(xù)在流水線中流動。當(dāng)流水線確定分支轉(zhuǎn)移成功與否以流水線中流動。當(dāng)流水

57、線確定分支轉(zhuǎn)移成功與否以及分支的目標(biāo)地址之后，如果分支轉(zhuǎn)移成功，流水及分支的目標(biāo)地址之后，如果分支轉(zhuǎn)移成功，流水線必須將在分支指令之后取出的所有指令轉(zhuǎn)化為空線必須將在分支指令之后取出的所有指令轉(zhuǎn)化為空操作，并在分支的目標(biāo)地址處重新取出有效的指令；操作，并在分支的目標(biāo)地址處重新取出有效的指令；如果分支轉(zhuǎn)移失敗，那么可以將分支指令看作是一如果分支轉(zhuǎn)移失敗，那么可以將分支指令看作是一條普通指令，流水線正常流動，無需將在分支指令條普通指令，流水線正常流動，無需將在分支指令之后取出的所有指令轉(zhuǎn)化為空操作。之后取出的所有指令轉(zhuǎn)化為空操作。3.3. 預(yù)測分支成功的方法預(yù)測分支成功的方法另一種降低流水線分支損

58、失的方法便是預(yù)測分另一種降低流水線分支損失的方法便是預(yù)測分支成功，一旦流水線譯碼到一條指令是分支指支成功，一旦流水線譯碼到一條指令是分支指令，且完成了分支目標(biāo)地址的計算，我們就假令，且完成了分支目標(biāo)地址的計算，我們就假設(shè)分支轉(zhuǎn)移成功，并開始在分支目標(biāo)地址處取設(shè)分支轉(zhuǎn)移成功，并開始在分支目標(biāo)地址處取指令執(zhí)行。指令執(zhí)行。 在某些流水線中，特別是那些具有隱含在某些流水線中，特別是那些具有隱含設(shè)置條件碼或分支條件更復(fù)雜指令的流水線機(jī)設(shè)置條件碼或分支條件更復(fù)雜指令的流水線機(jī)器中，在確定分支轉(zhuǎn)移成功與否之前，便可以器中，在確定分支轉(zhuǎn)移成功與否之前，便可以知道分支的目標(biāo)地址，這時采用這種方法便可知道分支的目

59、標(biāo)地址，這時采用這種方法便可以降低這些流水線的分支損失。以降低這些流水線的分支損失。 4.4.延遲分支（延遲分支（delayed branchdelayed branch）方法）方法 為降低流水線分支損失而采用的第四種方法就是延遲分為降低流水線分支損失而采用的第四種方法就是延遲分支方法。其主要思想是從邏輯上支方法。其主要思想是從邏輯上“延長延長”分支指令的執(zhí)行時分支指令的執(zhí)行時間。延遲長度為間。延遲長度為 n n 的分支指令的執(zhí)行順序是：的分支指令的執(zhí)行順序是： 分支指令分支指令 順序后繼指令順序后繼指令1 1順序后繼指令順序后繼指令 n n如果分支成功，分支目標(biāo)處指令如果分支成功，分支目標(biāo)處

60、指令 所有順序后繼指令都處于分支延遲槽（所有順序后繼指令都處于分支延遲槽（branch-branch-delay slotsdelay slots）中，無論分支成功與否，流水線都會執(zhí)行這些）中，無論分支成功與否，流水線都會執(zhí)行這些指令。指令。 基于延遲分支方法，無論分支成功與基于延遲分支方法，無論分支成功與否，其流水線時空圖所描述的流水線的行否，其流水線時空圖所描述的流水線的行為是類似的，流水線中均沒有插入暫停周為是類似的，流水線中均沒有插入暫停周期，從而極大地降低了流水線分支損失。期，從而極大地降低了流水線分支損失。從圖中可以看出，實際上是處于分支延遲從圖中可以看出，實際上是處于分支延遲槽中