流水線問題系統(tǒng)結(jié)構(gòu)

1、1 5.2 流水線處理機(jī)流水線處理機(jī) 教學(xué)目標(biāo)：掌握流水線的基本原理、特點(diǎn)、分類、教學(xué)目標(biāo)：掌握流水線的基本原理、特點(diǎn)、分類、 性能分析，非線性流水線的調(diào)度問題，及局部相性能分析，非線性流水線的調(diào)度問題，及局部相 關(guān)和全局相關(guān)的處理方法。關(guān)和全局相關(guān)的處理方法。 一、流水線工作原理一、流水線工作原理 流水線方式是把一個(gè)重復(fù)的過程分解為若干個(gè)流水線方式是把一個(gè)重復(fù)的過程分解為若干個(gè) 子過程，每個(gè)子過程可以與其他子過程同時(shí)進(jìn)行。子過程，每個(gè)子過程可以與其他子過程同時(shí)進(jìn)行。 在處理機(jī)的各個(gè)部分幾乎都可以采用流水方式在處理機(jī)的各個(gè)部分幾乎都可以采用流水方式 工作。工作。 指令的執(zhí)行過程可以采用流水線，

2、稱為指令流指令的執(zhí)行過程可以采用流水線，稱為指令流 水線。水線。 2 運(yùn)算器中的操作部件，如浮點(diǎn)加法器等可以采運(yùn)算器中的操作部件，如浮點(diǎn)加法器等可以采 用流水線，稱為操作部件流水線。用流水線，稱為操作部件流水線。 從重疊到流水線從重疊到流水線 一次重疊方式就是一種簡(jiǎn)單的流水線。一次重疊方式就是一種簡(jiǎn)單的流水線。 在計(jì)算機(jī)中，一條指令的執(zhí)行過程分解為在計(jì)算機(jī)中，一條指令的執(zhí)行過程分解為“分分 析析”和和“執(zhí)行執(zhí)行”兩個(gè)子過程，這兩個(gè)子過程分別兩個(gè)子過程，這兩個(gè)子過程分別 在指令分析器和指令執(zhí)行部件中完成，如圖在指令分析器和指令執(zhí)行部件中完成，如圖5.23所所 示。示。 3 4 指令分析器和指令執(zhí)

3、行部件的輸出端各有一個(gè)指令分析器和指令執(zhí)行部件的輸出端各有一個(gè) 鎖存器，可分別保存指令鎖存器，可分別保存指令“分析分析”和指令和指令“執(zhí)行執(zhí)行” 的結(jié)果，因此，指令分析器和指令執(zhí)行部件能成的結(jié)果，因此，指令分析器和指令執(zhí)行部件能成 為兩個(gè)完全獨(dú)立的功能部件，可同時(shí)并行工作。為兩個(gè)完全獨(dú)立的功能部件，可同時(shí)并行工作。 指令分析器指令分析器“分析分析k1”與指令執(zhí)行部件與指令執(zhí)行部件“執(zhí)行執(zhí)行k” 可同時(shí)進(jìn)行?？赏瑫r(shí)進(jìn)行。 如果指令分析器分析一條指令所需要的時(shí)間如果指令分析器分析一條指令所需要的時(shí)間 t1與指令執(zhí)行部件執(zhí)行一條指令所需要的時(shí)間與指令執(zhí)行部件執(zhí)行一條指令所需要的時(shí)間 t2相等，即相等

4、，即t1=t2，都為，都為t。則從指令執(zhí)行。則從指令執(zhí)行 部件的輸出端看，每間隔一個(gè)部件的輸出端看，每間隔一個(gè)t就執(zhí)行完成一條就執(zhí)行完成一條 指令，并輸出一個(gè)運(yùn)算結(jié)果。因此，處理機(jī)指令，并輸出一個(gè)運(yùn)算結(jié)果。因此，處理機(jī) 5 執(zhí)行指令的速度提高了一倍。執(zhí)行指令的速度提高了一倍。 如果把執(zhí)行一條指令的過程分得更細(xì)，如圖如果把執(zhí)行一條指令的過程分得更細(xì)，如圖 5.24所示，分為所示，分為6個(gè)子過程。每一個(gè)部件的輸出端個(gè)子過程。每一個(gè)部件的輸出端 都要有一個(gè)鎖存器。都要有一個(gè)鎖存器。 6 在圖在圖5.24中的每一個(gè)子過程還可以再進(jìn)一步分解成中的每一個(gè)子過程還可以再進(jìn)一步分解成 更小的子過程，即在功能部

5、件的內(nèi)部也采用流水更小的子過程，即在功能部件的內(nèi)部也采用流水 線方式工作。如，一個(gè)浮點(diǎn)加法的執(zhí)行過程可采線方式工作。如，一個(gè)浮點(diǎn)加法的執(zhí)行過程可采 用用4級(jí)流水線，如圖級(jí)流水線，如圖5.25所示。如果各個(gè)部件的執(zhí)所示。如果各個(gè)部件的執(zhí) 行時(shí)間均相等，處理機(jī)執(zhí)行浮點(diǎn)加法的速度能夠行時(shí)間均相等，處理機(jī)執(zhí)行浮點(diǎn)加法的速度能夠 提高提高3倍。倍。 7 時(shí)空?qǐng)D時(shí)空?qǐng)D 描述流水線的工作，最常用的方法是采用描述流水線的工作，最常用的方法是采用 “時(shí)空?qǐng)D時(shí)空?qǐng)D”。 圖圖5.23所示的流水線，采用時(shí)空?qǐng)D表示如圖所示的流水線，采用時(shí)空?qǐng)D表示如圖 5.26所示。所示。 8 在時(shí)空?qǐng)D中，橫坐標(biāo)表示時(shí)間，就是輸入到流水

6、在時(shí)空?qǐng)D中，橫坐標(biāo)表示時(shí)間，就是輸入到流水 線中的各個(gè)任務(wù)在流水線中所經(jīng)過的時(shí)間?？v坐線中的各個(gè)任務(wù)在流水線中所經(jīng)過的時(shí)間。縱坐 標(biāo)表示空間，即流水線的各個(gè)子過程。標(biāo)表示空間，即流水線的各個(gè)子過程。 在時(shí)空?qǐng)D中，流水線的一個(gè)子過程通常稱為在時(shí)空?qǐng)D中，流水線的一個(gè)子過程通常稱為“功功 能段能段”。 圖圖5.27是一個(gè)是一個(gè)4段浮點(diǎn)加法器流水線的時(shí)空?qǐng)D。段浮點(diǎn)加法器流水線的時(shí)空?qǐng)D。 9 流水線的特點(diǎn)流水線的特點(diǎn) 在處理機(jī)中采用流水線方式與采用傳統(tǒng)的串行方在處理機(jī)中采用流水線方式與采用傳統(tǒng)的串行方 式相比，具有如下特點(diǎn)：式相比，具有如下特點(diǎn)： 在流水線中處理的必須是連續(xù)的任務(wù)，只有連在流水線中處理的

7、必須是連續(xù)的任務(wù)，只有連 續(xù)不斷地提供任務(wù)才能充分發(fā)揮流水線的效率。續(xù)不斷地提供任務(wù)才能充分發(fā)揮流水線的效率。 把一個(gè)任務(wù)（一條指令或一個(gè)操作）分解為幾把一個(gè)任務(wù)（一條指令或一個(gè)操作）分解為幾 個(gè)有聯(lián)系的子任務(wù)，每個(gè)子任務(wù)由一個(gè)專門的功個(gè)有聯(lián)系的子任務(wù)，每個(gè)子任務(wù)由一個(gè)專門的功 能部件來實(shí)現(xiàn)。能部件來實(shí)現(xiàn)。 在流水線的每一個(gè)功能部件的后面都要有一個(gè)在流水線的每一個(gè)功能部件的后面都要有一個(gè) 緩沖寄存器，用于保存本段的執(zhí)行結(jié)果。當(dāng)某一緩沖寄存器，用于保存本段的執(zhí)行結(jié)果。當(dāng)某一 個(gè)功能段的執(zhí)行時(shí)間變化范圍比較大時(shí)，要設(shè)置個(gè)功能段的執(zhí)行時(shí)間變化范圍比較大時(shí)，要設(shè)置 多個(gè)緩沖寄存器。多個(gè)緩沖寄存器。 1

8、0 流水線中各段的時(shí)間應(yīng)盡量相等，否則將引起流水線中各段的時(shí)間應(yīng)盡量相等，否則將引起 “堵塞堵塞”、“斷流斷流”等。執(zhí)行時(shí)間長(zhǎng)的一段將成等。執(zhí)行時(shí)間長(zhǎng)的一段將成 為整個(gè)流水線的為整個(gè)流水線的“瓶頸瓶頸”，這時(shí)，流水線中的各，這時(shí)，流水線中的各 個(gè)功能部件將不能充分發(fā)揮作用。因此，在流水個(gè)功能部件將不能充分發(fā)揮作用。因此，在流水 線設(shè)計(jì)中，當(dāng)遇到線設(shè)計(jì)中，當(dāng)遇到“瓶頸瓶頸”時(shí)，必須采取辦法解時(shí)，必須采取辦法解 決。決。 流水線需要有流水線需要有“裝入時(shí)間裝入時(shí)間”和和“排空時(shí)間排空時(shí)間”。 只有流水線完全充滿時(shí)，整個(gè)流水線的效率才能只有流水線完全充滿時(shí)，整個(gè)流水線的效率才能 得到充分發(fā)揮。得到充

9、分發(fā)揮。 二、流水線的分類二、流水線的分類 線性流水線與非線性流水線線性流水線與非線性流水線 按照流水線的各個(gè)功能段之間是否有按照流水線的各個(gè)功能段之間是否有 11 反饋信號(hào)，可以把流水線分為線性流水線和非線反饋信號(hào)，可以把流水線分為線性流水線和非線 性流水線兩類。性流水線兩類。 線性流水線是將流水線的各段逐個(gè)串接起來。輸線性流水線是將流水線的各段逐個(gè)串接起來。輸 入數(shù)據(jù)從流水線的一端進(jìn)入，從另一端輸出。數(shù)入數(shù)據(jù)從流水線的一端進(jìn)入，從另一端輸出。數(shù) 據(jù)在流水線中的各個(gè)功能段流過時(shí)，每一個(gè)功能據(jù)在流水線中的各個(gè)功能段流過時(shí)，每一個(gè)功能 段都流過一次，且僅流過一次。段都流過一次，且僅流過一次。 非

10、線性流水線：在流水線的各個(gè)功能段之間除了非線性流水線：在流水線的各個(gè)功能段之間除了 有串行的連接之外，還有反饋回路。如圖有串行的連接之外，還有反饋回路。如圖5.28所示。所示。 12 表示非線性流水線的工作情況除了要有流水線的表示非線性流水線的工作情況除了要有流水線的 連接圖之外，還需要一張連接圖之外，還需要一張“預(yù)約表預(yù)約表”，兩者共同，兩者共同 來表示流水線的工作情況。如圖來表示流水線的工作情況。如圖5.29所示。所示。 13 圖中用圖中用“”表示這一個(gè)功能段在相應(yīng)的這一段時(shí)表示這一個(gè)功能段在相應(yīng)的這一段時(shí) 間內(nèi)有效，即任務(wù)經(jīng)過了這一個(gè)功能段。間內(nèi)有效，即任務(wù)經(jīng)過了這一個(gè)功能段。 一條非線

11、性流水線可以對(duì)應(yīng)有很多張預(yù)約表，一一條非線性流水線可以對(duì)應(yīng)有很多張預(yù)約表，一 張預(yù)約表實(shí)際上僅表示一條非線性流水線的一種張預(yù)約表實(shí)際上僅表示一條非線性流水線的一種 工作方式。工作方式。 線性流水線實(shí)際上也有預(yù)約表，只不過它的預(yù)約線性流水線實(shí)際上也有預(yù)約表，只不過它的預(yù)約 表是確定的。表是確定的。 首先，預(yù)約表的水平方向與垂直方向的格數(shù)是相首先，預(yù)約表的水平方向與垂直方向的格數(shù)是相 等的，其次，預(yù)約表從左上角到右下角所有格子等的，其次，預(yù)約表從左上角到右下角所有格子 全部有效，即是打全部有效，即是打“”的；預(yù)約表的其余部分一的；預(yù)約表的其余部分一 定是空白的。定是空白的。 因此，在描述線性流水線

12、時(shí)，一般不給出預(yù)約表。因此，在描述線性流水線時(shí)，一般不給出預(yù)約表。 14 流水線的級(jí)別流水線的級(jí)別 按照流水線使用的不同級(jí)別，可把流水線分為功按照流水線使用的不同級(jí)別，可把流水線分為功 能部件級(jí)、處理機(jī)級(jí)和處理機(jī)間級(jí)等多種類型。能部件級(jí)、處理機(jī)級(jí)和處理機(jī)間級(jí)等多種類型。 處理機(jī)級(jí)流水線又稱為指令流水線。它把一條指處理機(jī)級(jí)流水線又稱為指令流水線。它把一條指 令的執(zhí)行過程分解為多個(gè)子過程，每個(gè)子過程在令的執(zhí)行過程分解為多個(gè)子過程，每個(gè)子過程在 一個(gè)獨(dú)立的功能部件中完成。一個(gè)獨(dú)立的功能部件中完成。 前面介紹的一次重疊執(zhí)行方式就是一種簡(jiǎn)單的指前面介紹的一次重疊執(zhí)行方式就是一種簡(jiǎn)單的指 令流水線。令流水

13、線。 在采用先行控制器的處理機(jī)中，組成先行控制器在采用先行控制器的處理機(jī)中，組成先行控制器 的各個(gè)部件實(shí)際上也構(gòu)成了一條流水線。如圖的各個(gè)部件實(shí)際上也構(gòu)成了一條流水線。如圖5.30 所所示。 15 16 在先行控制器中，一條指令的執(zhí)行過程被分解為在先行控制器中，一條指令的執(zhí)行過程被分解為5 個(gè)子過程，每個(gè)子過程在一個(gè)專用的功能部件中個(gè)子過程，每個(gè)子過程在一個(gè)專用的功能部件中 執(zhí)行。執(zhí)行。 由于各種指令在同一個(gè)功能部件中執(zhí)行的時(shí)間往由于各種指令在同一個(gè)功能部件中執(zhí)行的時(shí)間往 往相差很大，因此，在每一個(gè)功能段之間要設(shè)置往相差很大，因此，在每一個(gè)功能段之間要設(shè)置 多個(gè)緩沖寄存器，以平滑流水線中各個(gè)功

14、能部件多個(gè)緩沖寄存器，以平滑流水線中各個(gè)功能部件 的操作。的操作。 每個(gè)部件內(nèi)部還可以采用流水線來實(shí)現(xiàn)。如對(duì)于每個(gè)部件內(nèi)部還可以采用流水線來實(shí)現(xiàn)。如對(duì)于 一些復(fù)雜的運(yùn)算操作部件，象浮點(diǎn)加法器等一般一些復(fù)雜的運(yùn)算操作部件，象浮點(diǎn)加法器等一般 要采用多級(jí)流水線來實(shí)現(xiàn)。后行寫數(shù)棧和先行讀要采用多級(jí)流水線來實(shí)現(xiàn)。后行寫數(shù)棧和先行讀 數(shù)棧也可以采用多級(jí)流水線來實(shí)現(xiàn)。這種流水線數(shù)棧也可以采用多級(jí)流水線來實(shí)現(xiàn)。這種流水線 稱為部件級(jí)流水線，或功能部件級(jí)流水線。稱為部件級(jí)流水線，或功能部件級(jí)流水線。 17 功能部件級(jí)流水線也稱為運(yùn)算操作流水線。功能部件級(jí)流水線也稱為運(yùn)算操作流水線。 把指令執(zhí)行部件中采用了流水

15、線的處理機(jī)稱為流把指令執(zhí)行部件中采用了流水線的處理機(jī)稱為流 水線處理機(jī)或超流水線處理機(jī)，把指令執(zhí)行部件水線處理機(jī)或超流水線處理機(jī)，把指令執(zhí)行部件 中設(shè)置有多個(gè)操作部件的處理機(jī)稱為多操作部件中設(shè)置有多個(gè)操作部件的處理機(jī)稱為多操作部件 處理機(jī)或超標(biāo)量處理機(jī)。處理機(jī)或超標(biāo)量處理機(jī)。 處理機(jī)間流水線又稱為宏流水線，如圖處理機(jī)間流水線又稱為宏流水線，如圖5.31所示。所示。 18 這種流水線由兩個(gè)或兩個(gè)以上處理機(jī)通過存儲(chǔ)器這種流水線由兩個(gè)或兩個(gè)以上處理機(jī)通過存儲(chǔ)器 串行連接起來，每個(gè)處理機(jī)對(duì)同一個(gè)數(shù)據(jù)流的不串行連接起來，每個(gè)處理機(jī)對(duì)同一個(gè)數(shù)據(jù)流的不 同部分分別進(jìn)行處理。前一個(gè)處理機(jī)的輸出結(jié)果同部分分別進(jìn)

16、行處理。前一個(gè)處理機(jī)的輸出結(jié)果 存入存儲(chǔ)器中，作為后一個(gè)處理機(jī)的輸入，每個(gè)存入存儲(chǔ)器中，作為后一個(gè)處理機(jī)的輸入，每個(gè) 處理機(jī)完成整個(gè)任務(wù)的一部分。處理機(jī)完成整個(gè)任務(wù)的一部分。 一臺(tái)大型計(jì)算機(jī)系統(tǒng)通常由多個(gè)同型號(hào)的或不同一臺(tái)大型計(jì)算機(jī)系統(tǒng)通常由多個(gè)同型號(hào)的或不同 型號(hào)的處理機(jī)構(gòu)成，每個(gè)處理機(jī)有不同的分工。型號(hào)的處理機(jī)構(gòu)成，每個(gè)處理機(jī)有不同的分工。 例如，由多個(gè)用高級(jí)語(yǔ)言編寫的程序需要在機(jī)器例如，由多個(gè)用高級(jí)語(yǔ)言編寫的程序需要在機(jī)器 上運(yùn)行，則程序和數(shù)據(jù)的輸入、編譯、連接、執(zhí)上運(yùn)行，則程序和數(shù)據(jù)的輸入、編譯、連接、執(zhí) 行、執(zhí)行結(jié)果輸出等可分別在不同的處理機(jī)上完行、執(zhí)行結(jié)果輸出等可分別在不同的處理機(jī)

17、上完 成，這些處理機(jī)就構(gòu)成了一條宏流水線。成，這些處理機(jī)就構(gòu)成了一條宏流水線。 單功能與多功能流水線單功能與多功能流水線 19 一條流水線只能完成一種固定的功能，這種流水一條流水線只能完成一種固定的功能，這種流水 線稱為單功能流水線。線稱為單功能流水線。 多功能流水線是指流水線的各段可以進(jìn)行不同的多功能流水線是指流水線的各段可以進(jìn)行不同的 連接。在不同時(shí)間內(nèi)，或在同一時(shí)間內(nèi)，通過不連接。在不同時(shí)間內(nèi)，或在同一時(shí)間內(nèi)，通過不 同的連接方式實(shí)現(xiàn)不同的功能。同的連接方式實(shí)現(xiàn)不同的功能。 20 21 靜態(tài)流水線與動(dòng)態(tài)流水線靜態(tài)流水線與動(dòng)態(tài)流水線 在多功能流水線中，按照在同一時(shí)間內(nèi)是否能夠在多功能流水線

18、中，按照在同一時(shí)間內(nèi)是否能夠 連接成多種方式，同時(shí)執(zhí)行多種功能，可以把多連接成多種方式，同時(shí)執(zhí)行多種功能，可以把多 功能流水線分為靜態(tài)流水線和動(dòng)態(tài)流水線兩種。功能流水線分為靜態(tài)流水線和動(dòng)態(tài)流水線兩種。 靜態(tài)流水線是指在同一時(shí)間內(nèi)，多功能流水線中靜態(tài)流水線是指在同一時(shí)間內(nèi)，多功能流水線中 的各個(gè)功能段只能按照一種固定的方式連接，實(shí)的各個(gè)功能段只能按照一種固定的方式連接，實(shí) 現(xiàn)一種固定的功能。只有當(dāng)按照這種連接方式工現(xiàn)一種固定的功能。只有當(dāng)按照這種連接方式工 作的所有任務(wù)都流出流水線之后，多功能流水線作的所有任務(wù)都流出流水線之后，多功能流水線 才能重新進(jìn)行連接，以實(shí)現(xiàn)其它功能。才能重新進(jìn)行連接，以

19、實(shí)現(xiàn)其它功能。 例如，圖例如，圖5.32的多功能流水線，如果按照?qǐng)D的多功能流水線，如果按照?qǐng)D5.33所所 示的時(shí)空?qǐng)D工作，就是一種靜態(tài)流水線。示的時(shí)空?qǐng)D工作，就是一種靜態(tài)流水線。 22 23 動(dòng)態(tài)流水線是指在同一段時(shí)間內(nèi)，多功能流水線動(dòng)態(tài)流水線是指在同一段時(shí)間內(nèi)，多功能流水線 中的各段可以按照不同的方式連接，同時(shí)執(zhí)行多中的各段可以按照不同的方式連接，同時(shí)執(zhí)行多 種功能。種功能。 當(dāng)然，同時(shí)實(shí)現(xiàn)多種連接方式是有條件的，即流當(dāng)然，同時(shí)實(shí)現(xiàn)多種連接方式是有條件的，即流 水線中的各個(gè)功能部件之間不能發(fā)生沖突。如圖水線中的各個(gè)功能部件之間不能發(fā)生沖突。如圖 5.34所示。所示。 在一般情況下，動(dòng)態(tài)流水線

20、的效率和功能部件的在一般情況下，動(dòng)態(tài)流水線的效率和功能部件的 利用率要比靜態(tài)流水線高，但動(dòng)態(tài)流水線的控制利用率要比靜態(tài)流水線高，但動(dòng)態(tài)流水線的控制 比靜態(tài)流水線要復(fù)雜得多，目前，在大多數(shù)處理比靜態(tài)流水線要復(fù)雜得多，目前，在大多數(shù)處理 機(jī)中均采用靜態(tài)流水線。機(jī)中均采用靜態(tài)流水線。 24 25 按照不同的數(shù)據(jù)表示方式，可以把流水線分為標(biāo)按照不同的數(shù)據(jù)表示方式，可以把流水線分為標(biāo) 量流水線和向量流水線。量流水線和向量流水線。 在線性流水線中，根據(jù)對(duì)流水線的控制方式不同，在線性流水線中，根據(jù)對(duì)流水線的控制方式不同， 可以把流水線分為同步流水線和異步流水線兩類?？梢园蚜魉€分為同步流水線和異步流水線兩類

21、。 一般的宏流水線多采用異步流水線方式。如圖一般的宏流水線多采用異步流水線方式。如圖5.35 所示。在異步流水線中，當(dāng)所示。在異步流水線中，當(dāng)Si功能段要向功能段要向Si1功功 能段傳送數(shù)據(jù)時(shí)，首先發(fā)出就緒信號(hào)，能段傳送數(shù)據(jù)時(shí)，首先發(fā)出就緒信號(hào)， Si1功能功能 段收到就緒信號(hào)后，向段收到就緒信號(hào)后，向Si功能段回送一個(gè)回答信號(hào)。功能段回送一個(gè)回答信號(hào)。 26 27 按照流水線輸出端流出的任務(wù)與流水線輸入端流按照流水線輸出端流出的任務(wù)與流水線輸入端流 入的任務(wù)的順序是否相同，可以把流水線分為順入的任務(wù)的順序是否相同，可以把流水線分為順 序流水線與亂序流水線兩種。序流水線與亂序流水線兩種。 在順

22、序流水線中，流水線輸出端的任務(wù)流出順序在順序流水線中，流水線輸出端的任務(wù)流出順序 與輸入端的任務(wù)流入順序完全相同，每個(gè)任務(wù)在與輸入端的任務(wù)流入順序完全相同，每個(gè)任務(wù)在 流水線的各個(gè)功能段中是一個(gè)跟著一個(gè)順序流動(dòng)流水線的各個(gè)功能段中是一個(gè)跟著一個(gè)順序流動(dòng) 的。的。 亂序流水線輸出端流出任務(wù)的順序與輸入端流入亂序流水線輸出端流出任務(wù)的順序與輸入端流入 任務(wù)的順序可以不一樣。每個(gè)任務(wù)在流水線中并任務(wù)的順序可以不一樣。每個(gè)任務(wù)在流水線中并 不是按照輸入的順序一個(gè)跟著一個(gè)流動(dòng)的。不是按照輸入的順序一個(gè)跟著一個(gè)流動(dòng)的。 三、線性流水線的性能分析三、線性流水線的性能分析 28 衡量流水線性能的主要指標(biāo)有吞吐

23、率、加速比和衡量流水線性能的主要指標(biāo)有吞吐率、加速比和 效率。效率。 吞吐率吞吐率 流水線的吞吐率是指在單位時(shí)間內(nèi)流水線所完成流水線的吞吐率是指在單位時(shí)間內(nèi)流水線所完成 的任務(wù)數(shù)量或輸出結(jié)果數(shù)量。的任務(wù)數(shù)量或輸出結(jié)果數(shù)量。 其中，其中，n為任務(wù)數(shù)，為任務(wù)數(shù)，Tk是處理完成是處理完成n個(gè)任務(wù)所用的個(gè)任務(wù)所用的 時(shí)間。時(shí)間。 以下討論滿足某種特殊情況的流水線吞吐率。以下討論滿足某種特殊情況的流水線吞吐率。 流水線各段執(zhí)行時(shí)間相等，輸入到流水線中的任流水線各段執(zhí)行時(shí)間相等，輸入到流水線中的任 務(wù)是連續(xù)的。如圖務(wù)是連續(xù)的。如圖5.36所示。所示。 29 30 一條一條k段線性流水線完成段線性流水線完成

24、n個(gè)連續(xù)任務(wù)需要的總時(shí)個(gè)連續(xù)任務(wù)需要的總時(shí) 間為：間為： 其中，其中，t為時(shí)鐘周期。為時(shí)鐘周期。 實(shí)際吞吐率為：實(shí)際吞吐率為： 最大吞吐率為：最大吞吐率為： 31 最大吞吐率與實(shí)際吞吐率的關(guān)系是：最大吞吐率與實(shí)際吞吐率的關(guān)系是： 當(dāng)流水線中各段的執(zhí)行時(shí)間不完全相等時(shí)，流水當(dāng)流水線中各段的執(zhí)行時(shí)間不完全相等時(shí)，流水 線中就存在有線中就存在有“瓶頸瓶頸”。如圖。如圖5.37所示。所示。 32 33 流水線各段執(zhí)行時(shí)間不相等情況下的實(shí)際吞吐率：流水線各段執(zhí)行時(shí)間不相等情況下的實(shí)際吞吐率： 此時(shí)流水線的最大吞吐率為：此時(shí)流水線的最大吞吐率為： 對(duì)于圖對(duì)于圖5.37所示的例子，流水線的最大吞吐率為：所示

25、的例子，流水線的最大吞吐率為： 34 可以看出，當(dāng)流水線中各個(gè)功能段的執(zhí)行時(shí)間不可以看出，當(dāng)流水線中各個(gè)功能段的執(zhí)行時(shí)間不 完全相等時(shí)，流水線的最大吞吐率與實(shí)際吞吐率完全相等時(shí)，流水線的最大吞吐率與實(shí)際吞吐率 主要是由流水線中執(zhí)行時(shí)間最長(zhǎng)的那個(gè)功能段來主要是由流水線中執(zhí)行時(shí)間最長(zhǎng)的那個(gè)功能段來 決定的，這個(gè)功能段就成了整個(gè)流水線的決定的，這個(gè)功能段就成了整個(gè)流水線的“瓶瓶 頸頸”。 解決流水線解決流水線“瓶頸瓶頸”問題的方法主要有兩種。問題的方法主要有兩種。 是將流水線的是將流水線的“瓶頸瓶頸”部分再細(xì)分。如圖部分再細(xì)分。如圖5.38所所 示。示。 35 通過重復(fù)設(shè)置瓶頸功能段，讓多個(gè)瓶頸功能

26、段通過重復(fù)設(shè)置瓶頸功能段，讓多個(gè)瓶頸功能段 并行工作。但這種方法，其控制邏輯比較復(fù)雜。并行工作。但這種方法，其控制邏輯比較復(fù)雜。 如圖如圖5.39所示。所示。 加速比加速比 完成一批任務(wù)，不使用流水線所用的時(shí)間與使用完成一批任務(wù)，不使用流水線所用的時(shí)間與使用 流水線所用的時(shí)間之比稱為流水線的加速比。流水線所用的時(shí)間之比稱為流水線的加速比。 如果不使用流水線，即順序執(zhí)行所用的時(shí)間為如果不使用流水線，即順序執(zhí)行所用的時(shí)間為T0， 使用流水線的執(zhí)行時(shí)間為使用流水線的執(zhí)行時(shí)間為Tk，則流水線的加速比，則流水線的加速比 為：為： 36 37 各個(gè)功能段執(zhí)行時(shí)間均相等的一條各個(gè)功能段執(zhí)行時(shí)間均相等的一條k

27、段流水線完成段流水線完成 n個(gè)連續(xù)任務(wù)時(shí)的實(shí)際加速比為：個(gè)連續(xù)任務(wù)時(shí)的實(shí)際加速比為： 此時(shí)的最大加速比為：此時(shí)的最大加速比為： 38 可以看出，流水線的最大加速比等于流水線的段可以看出，流水線的最大加速比等于流水線的段 數(shù)。數(shù)。 是否流水線的段數(shù)越多越好呢是否流水線的段數(shù)越多越好呢? 實(shí)際上，當(dāng)流水線的段數(shù)很多時(shí)，為了使流水線實(shí)際上，當(dāng)流水線的段數(shù)很多時(shí)，為了使流水線 能夠充分發(fā)揮效率，要求連續(xù)輸入的任務(wù)數(shù)能夠充分發(fā)揮效率，要求連續(xù)輸入的任務(wù)數(shù)n也就也就 很多。很多。 圖圖5.40給出連續(xù)任務(wù)個(gè)數(shù)給出連續(xù)任務(wù)個(gè)數(shù)n與加速比與加速比S的關(guān)系。的關(guān)系。 當(dāng)任務(wù)個(gè)數(shù)很小時(shí)，加速比可能很差，當(dāng)當(dāng)任務(wù)個(gè)

28、數(shù)很小時(shí)，加速比可能很差，當(dāng)n=1時(shí)，時(shí)， 加速比加速比S的值最小為的值最小為1。當(dāng)流水線的段數(shù)。當(dāng)流水線的段數(shù)K增大時(shí)，增大時(shí)， 可以獲得比較好的加速比。當(dāng)可以獲得比較好的加速比。當(dāng)n=64時(shí)，一條時(shí)，一條4段流段流 水線的加速比為水線的加速比為3.8，一條，一條8段流水線的加速比可以段流水線的加速比可以 達(dá)到達(dá)到7.2。 39 但是，一方面，由于一般程序中存在數(shù)據(jù)相關(guān)、但是，一方面，由于一般程序中存在數(shù)據(jù)相關(guān)、 轉(zhuǎn)移、中斷等情況，連續(xù)輸入的任務(wù)數(shù)轉(zhuǎn)移、中斷等情況，連續(xù)輸入的任務(wù)數(shù)n受到很大受到很大 的限制。另一方面，由于控制的復(fù)雜性、電路實(shí)的限制。另一方面，由于控制的復(fù)雜性、電路實(shí) 現(xiàn)及組

29、裝技術(shù)、實(shí)現(xiàn)成本等方面的限制，流水線現(xiàn)及組裝技術(shù)、實(shí)現(xiàn)成本等方面的限制，流水線 的段數(shù)也不可能很多。的段數(shù)也不可能很多。 40 當(dāng)流水線的各個(gè)功能段的執(zhí)行時(shí)間不相等時(shí)，一當(dāng)流水線的各個(gè)功能段的執(zhí)行時(shí)間不相等時(shí)，一 條條k段線性流水線完成段線性流水線完成n個(gè)連續(xù)任務(wù)的實(shí)際加速比個(gè)連續(xù)任務(wù)的實(shí)際加速比 為：為： 效率效率 流水線的效率是指流水線的設(shè)備利用率。流水線的效率是指流水線的設(shè)備利用率。 在時(shí)空?qǐng)D上，流水線的效率定義為在時(shí)空?qǐng)D上，流水線的效率定義為n個(gè)任務(wù)占用的個(gè)任務(wù)占用的 時(shí)空區(qū)與時(shí)空區(qū)與k個(gè)功能段總的時(shí)空區(qū)之比。個(gè)功能段總的時(shí)空區(qū)之比。 41 其中，其中，T0為為n個(gè)任務(wù)順序執(zhí)行的時(shí)間，

30、個(gè)任務(wù)順序執(zhí)行的時(shí)間，Tk為流水線為流水線 完成完成n個(gè)任務(wù)的時(shí)間，個(gè)任務(wù)的時(shí)間，k為功能段數(shù)。為功能段數(shù)。 如果流水線各段執(zhí)行時(shí)間均相等，輸入如果流水線各段執(zhí)行時(shí)間均相等，輸入n個(gè)任務(wù)是個(gè)任務(wù)是 連續(xù)的，則一條連續(xù)的，則一條k段流水線的效率為：段流水線的效率為： 42 此時(shí)，流水線的最高效率為：此時(shí)，流水線的最高效率為： 如果流水線的各段執(zhí)行時(shí)間不相等，則連續(xù)執(zhí)行如果流水線的各段執(zhí)行時(shí)間不相等，則連續(xù)執(zhí)行n 個(gè)任務(wù)的流水線效率為：個(gè)任務(wù)的流水線效率為： 43 此時(shí)，流水線除了瓶頸功能段之外，其它各個(gè)功此時(shí)，流水線除了瓶頸功能段之外，其它各個(gè)功 能段都有空閑時(shí)間，這些功能段的效率沒有得到能段都

31、有空閑時(shí)間，這些功能段的效率沒有得到 充分發(fā)揮，因此，整個(gè)流水線的效率充分發(fā)揮，因此，整個(gè)流水線的效率E也比較低。也比較低。 在上面給出的所有流水線時(shí)空?qǐng)D中，都默認(rèn)每個(gè)在上面給出的所有流水線時(shí)空?qǐng)D中，都默認(rèn)每個(gè) 功能段的設(shè)備量或設(shè)備的價(jià)格都是相等的。對(duì)于功能段的設(shè)備量或設(shè)備的價(jià)格都是相等的。對(duì)于 可能出現(xiàn)的每一個(gè)功能段的設(shè)備量或功能段的價(jià)可能出現(xiàn)的每一個(gè)功能段的設(shè)備量或功能段的價(jià) 格不等的情況，應(yīng)該根據(jù)各個(gè)功能段所用的設(shè)備格不等的情況，應(yīng)該根據(jù)各個(gè)功能段所用的設(shè)備 量或設(shè)備價(jià)格在流水線總設(shè)備中所占的比例，分量或設(shè)備價(jià)格在流水線總設(shè)備中所占的比例，分 別賦予不同的別賦予不同的“權(quán)權(quán)”值值Pi。此

32、時(shí)流水線的效率為：。此時(shí)流水線的效率為： 44 45 流水線最佳段數(shù)的選擇流水線最佳段數(shù)的選擇 從上面的分析可看出，增加流水線的段數(shù)，流水從上面的分析可看出，增加流水線的段數(shù)，流水 線的吞吐率和加速比都能提高。但由于在每個(gè)功線的吞吐率和加速比都能提高。但由于在每個(gè)功 能段的輸出端都必須設(shè)置一個(gè)鎖存器，因此，當(dāng)能段的輸出端都必須設(shè)置一個(gè)鎖存器，因此，當(dāng) 流水線的段數(shù)增多時(shí)，鎖存器的總延遲時(shí)間也將流水線的段數(shù)增多時(shí)，鎖存器的總延遲時(shí)間也將 增加，另外，增加鎖存器數(shù)量，流水線的價(jià)格也增加，另外，增加鎖存器數(shù)量，流水線的價(jià)格也 增加。所以，在設(shè)計(jì)流水線時(shí)，要綜合各方面的增加。所以，在設(shè)計(jì)流水線時(shí)，要綜

33、合各方面的 因素，根據(jù)最佳性能價(jià)格比的要求來選擇流水線因素，根據(jù)最佳性能價(jià)格比的要求來選擇流水線 的最佳段數(shù)。的最佳段數(shù)。 假設(shè)在非流水線的機(jī)器上采用順序執(zhí)行方式完成假設(shè)在非流水線的機(jī)器上采用順序執(zhí)行方式完成 一個(gè)任務(wù)所需要的時(shí)間為一個(gè)任務(wù)所需要的時(shí)間為t，則在同等速度的有，則在同等速度的有k 段流水線的機(jī)器上執(zhí)行一個(gè)任務(wù)需要的時(shí)間為：段流水線的機(jī)器上執(zhí)行一個(gè)任務(wù)需要的時(shí)間為： 46 tkd，d為鎖存器延遲時(shí)間。為鎖存器延遲時(shí)間。 則流水線的最大吞吐率為：則流水線的最大吞吐率為： 流水線的總價(jià)格為：流水線的總價(jià)格為：Cabk a為所有功能為所有功能 段本身的總價(jià)格，段本身的總價(jià)格，b為每個(gè)鎖存

34、器的價(jià)格為每個(gè)鎖存器的價(jià)格 則性能價(jià)格比則性能價(jià)格比PCR定義為：定義為： 47 可以通過對(duì)自變量可以通過對(duì)自變量k求導(dǎo)，得到性能價(jià)格比求導(dǎo)，得到性能價(jià)格比PCR的的 極值，這個(gè)極值也是最大值，如圖極值，這個(gè)極值也是最大值，如圖5.41所示。所示。 48 當(dāng)性能價(jià)格比當(dāng)性能價(jià)格比PCR取得最大值時(shí)，它所對(duì)應(yīng)的流取得最大值時(shí)，它所對(duì)應(yīng)的流 水線的段數(shù)就是最佳段數(shù)水線的段數(shù)就是最佳段數(shù)k： 一般處理機(jī)中的流水線段數(shù)在一般處理機(jī)中的流水線段數(shù)在2段至段至10段之間，極段之間，極 少有超過少有超過15段的流水線。段的流水線。 流水線性能分析舉例流水線性能分析舉例 例例5.1單功能、線性流水線，輸入任務(wù)

35、是不連續(xù)的單功能、線性流水線，輸入任務(wù)是不連續(xù)的 情況，計(jì)算流水線的吞吐率、加速比和效率。情況，計(jì)算流水線的吞吐率、加速比和效率。 用圖用圖5.25所示的一條所示的一條4段浮點(diǎn)加法器流水線計(jì)算段浮點(diǎn)加法器流水線計(jì)算8 個(gè)浮點(diǎn)數(shù)的和：個(gè)浮點(diǎn)數(shù)的和： 49 ZABCDEFGH 由于存在數(shù)據(jù)相關(guān)，將上式變換為：由于存在數(shù)據(jù)相關(guān)，將上式變換為： Z(AB) (CD) (EF) (GH) 8個(gè)浮點(diǎn)數(shù)求和的流水線時(shí)空?qǐng)D如圖個(gè)浮點(diǎn)數(shù)求和的流水線時(shí)空?qǐng)D如圖5.42所示。所示。 假設(shè)每一個(gè)功能段的延遲時(shí)間均相等，都為假設(shè)每一個(gè)功能段的延遲時(shí)間均相等，都為t。 50 51 例例5.2多功能、線性流水線，輸入任務(wù)是

36、不連續(xù)的多功能、線性流水線，輸入任務(wù)是不連續(xù)的 情況，計(jì)算流水線的吞吐率、加速比和效率。情況，計(jì)算流水線的吞吐率、加速比和效率。 用圖用圖5.32所示的多功能靜態(tài)流水線計(jì)算兩個(gè)向量的所示的多功能靜態(tài)流水線計(jì)算兩個(gè)向量的 點(diǎn)積：點(diǎn)積： ZABCDEFGH 為了盡量減少數(shù)據(jù)相關(guān)性，充分發(fā)揮流水線的作為了盡量減少數(shù)據(jù)相關(guān)性，充分發(fā)揮流水線的作 用，計(jì)算的順序應(yīng)該是先做用，計(jì)算的順序應(yīng)該是先做4個(gè)乘法：個(gè)乘法：AB、CD、 EF和和GH，然后做兩個(gè)加法，然后做兩個(gè)加法ABCD和和EFGH， 最后求總的結(jié)果最后求總的結(jié)果Z。流水線的時(shí)空?qǐng)D如圖。流水線的時(shí)空?qǐng)D如圖5.43所示。所示。 假設(shè)每一個(gè)功能段的延

37、遲時(shí)間都為假設(shè)每一個(gè)功能段的延遲時(shí)間都為t，則流水線，則流水線 的吞吐率的吞吐率TP為：為： 52 如果采用順序執(zhí)行方式，完成一次乘法用如果采用順序執(zhí)行方式，完成一次乘法用4個(gè)個(gè)t， 完成一次加法用完成一次加法用6個(gè)個(gè)t，則完成全部運(yùn)算要用：，則完成全部運(yùn)算要用： T044t36t34t 則流水線的加速比則流水線的加速比S為：為： 整個(gè)流水線共有整個(gè)流水線共有8段，流水線效率段，流水線效率E為：為： 53 54 四、非線性流水線的調(diào)度技術(shù)四、非線性流水線的調(diào)度技術(shù) 在非線性流水線中，由于存在有反饋回路，當(dāng)一在非線性流水線中，由于存在有反饋回路，當(dāng)一 個(gè)任務(wù)在流水線中流過時(shí)，在同一個(gè)功能段中可個(gè)

38、任務(wù)在流水線中流過時(shí)，在同一個(gè)功能段中可 能要經(jīng)過多次。因此，就不能每一個(gè)時(shí)鐘周期向能要經(jīng)過多次。因此，就不能每一個(gè)時(shí)鐘周期向 流水線輸入一個(gè)新任務(wù)，否則會(huì)發(fā)生在同一個(gè)時(shí)流水線輸入一個(gè)新任務(wù)，否則會(huì)發(fā)生在同一個(gè)時(shí) 刻有幾個(gè)任務(wù)爭(zhēng)用同一個(gè)功能段的情況。這種情刻有幾個(gè)任務(wù)爭(zhēng)用同一個(gè)功能段的情況。這種情 況稱為功能部件沖突，或流水線沖突。況稱為功能部件沖突，或流水線沖突。 為避免流水線發(fā)生沖突，一般采用延遲輸入新任為避免流水線發(fā)生沖突，一般采用延遲輸入新任 務(wù)的方法。務(wù)的方法。 在非線性流水線的輸入端，究竟每隔多少個(gè)時(shí)鐘在非線性流水線的輸入端，究竟每隔多少個(gè)時(shí)鐘 周期向流水線輸入一個(gè)新任務(wù)才能使流水

39、線的各周期向流水線輸入一個(gè)新任務(wù)才能使流水線的各 個(gè)功能段都不發(fā)生沖突，這就是非線性流水線的個(gè)功能段都不發(fā)生沖突，這就是非線性流水線的 調(diào)度問題。調(diào)度問題。 55 在許多非線性流水線中，間隔的周期數(shù)往往不是在許多非線性流水線中，間隔的周期數(shù)往往不是 一個(gè)常數(shù)，而是一串周期變化的數(shù)字。一個(gè)常數(shù)，而是一串周期變化的數(shù)字。 因此，非線性流水線調(diào)度的任務(wù)是要找出一個(gè)最因此，非線性流水線調(diào)度的任務(wù)是要找出一個(gè)最 小的循環(huán)周期，按照這個(gè)周期向流水線輸入新任小的循環(huán)周期，按照這個(gè)周期向流水線輸入新任 務(wù)，流水線的各個(gè)功能段都不會(huì)發(fā)生沖突，而且務(wù)，流水線的各個(gè)功能段都不會(huì)發(fā)生沖突，而且 流水線的吞吐率和效率最

40、高。流水線的吞吐率和效率最高。 下面，先介紹非線性流水線的表示方法，然后分下面，先介紹非線性流水線的表示方法，然后分 析非線性流水線中的沖突情況，并介紹無沖突調(diào)析非線性流水線中的沖突情況，并介紹無沖突調(diào) 度方法，最后介紹非線性流水線的優(yōu)化調(diào)度方法。度方法，最后介紹非線性流水線的優(yōu)化調(diào)度方法。 非線性流水線的表示非線性流水線的表示 一條非線性流水線一般需要一個(gè)各功能段之間的一條非線性流水線一般需要一個(gè)各功能段之間的 連接圖和一張預(yù)約表共同來表示，如圖連接圖和一張預(yù)約表共同來表示，如圖5.44(a)和和 5.44(b)所示。所示。 56 57 預(yù)約表的橫坐標(biāo)表示流水線工作的時(shí)鐘周期，縱預(yù)約表的橫坐

41、標(biāo)表示流水線工作的時(shí)鐘周期，縱 坐標(biāo)表示流水線的功能段，中間有坐標(biāo)表示流水線的功能段，中間有“”的表示該的表示該 功能段在這一個(gè)時(shí)鐘周期處于工作狀態(tài)，即在這功能段在這一個(gè)時(shí)鐘周期處于工作狀態(tài)，即在這 個(gè)時(shí)鐘周期有任務(wù)通過這個(gè)功能段，空白的地方個(gè)時(shí)鐘周期有任務(wù)通過這個(gè)功能段，空白的地方 表示該功能段在這個(gè)時(shí)鐘周期不工作。表示該功能段在這個(gè)時(shí)鐘周期不工作。 一行中可以由多個(gè)一行中可以由多個(gè)“”，其含義是一個(gè)任務(wù)在不，其含義是一個(gè)任務(wù)在不 同時(shí)鐘周期重復(fù)使用了同一個(gè)功能段，一列中有同時(shí)鐘周期重復(fù)使用了同一個(gè)功能段，一列中有 多個(gè)多個(gè)“”是指在同一個(gè)時(shí)鐘周期同時(shí)使用了多個(gè)是指在同一個(gè)時(shí)鐘周期同時(shí)使用了

42、多個(gè) 功能段。功能段。 預(yù)約表的行數(shù)就是非線性流水線的段數(shù)，預(yù)約表預(yù)約表的行數(shù)就是非線性流水線的段數(shù)，預(yù)約表 的列數(shù)是指一個(gè)任務(wù)從進(jìn)入流水線到從流水線中的列數(shù)是指一個(gè)任務(wù)從進(jìn)入流水線到從流水線中 輸出所經(jīng)過的時(shí)鐘周期數(shù)。輸出所經(jīng)過的時(shí)鐘周期數(shù)。 有時(shí)把預(yù)約表的列數(shù)稱為流水線的功能求值時(shí)間有時(shí)把預(yù)約表的列數(shù)稱為流水線的功能求值時(shí)間 或流水線的裝入時(shí)間等?；蛄魉€的裝入時(shí)間等。 58 一張非線性流水線的預(yù)約表可能與多個(gè)非線性流一張非線性流水線的預(yù)約表可能與多個(gè)非線性流 水線連接圖相對(duì)應(yīng)，如圖水線連接圖相對(duì)應(yīng)，如圖5.45就是圖就是圖5.44(b)所示所示 預(yù)約表的另一種連接圖。預(yù)約表的另一種連接圖

43、。 59 產(chǎn)生這種情況的原因是：在預(yù)約表的同一列中可產(chǎn)生這種情況的原因是：在預(yù)約表的同一列中可 能有多個(gè)能有多個(gè)“”，即在這個(gè)時(shí)鐘周期有多個(gè)功能段，即在這個(gè)時(shí)鐘周期有多個(gè)功能段 有輸出，從而造成下一個(gè)功能段的輸入可能有多有輸出，從而造成下一個(gè)功能段的輸入可能有多 種來源，從而對(duì)應(yīng)有多個(gè)流水線的連接圖。種來源，從而對(duì)應(yīng)有多個(gè)流水線的連接圖。 同樣，一個(gè)非線性流水線的連接圖也可能對(duì)應(yīng)有同樣，一個(gè)非線性流水線的連接圖也可能對(duì)應(yīng)有 多張預(yù)約表。如圖多張預(yù)約表。如圖5.46就是圖就是圖5.44(a)所示流水線所示流水線 連接圖的另一張預(yù)約表。連接圖的另一張預(yù)約表。 60 61 造成這種情況的原因是：在非

44、線性流水線的有些造成這種情況的原因是：在非線性流水線的有些 功能段可能有多個(gè)輸出端，也有些功能段可能有功能段可能有多個(gè)輸出端，也有些功能段可能有 多個(gè)輸入端，這些輸出端與輸入端之間連接的先多個(gè)輸入端，這些輸出端與輸入端之間連接的先 后次序就形成了多張預(yù)約表。后次序就形成了多張預(yù)約表。 非線性流水線的沖突非線性流水線的沖突 向一條非線性流水線的輸入端連續(xù)輸入兩個(gè)任務(wù)向一條非線性流水線的輸入端連續(xù)輸入兩個(gè)任務(wù) 之間的時(shí)間間隔稱為非線性流水線的啟動(dòng)距離或之間的時(shí)間間隔稱為非線性流水線的啟動(dòng)距離或 等待時(shí)間。等待時(shí)間。 啟動(dòng)距離通常用時(shí)鐘周期數(shù)來表示，它是一個(gè)正啟動(dòng)距離通常用時(shí)鐘周期數(shù)來表示，它是一個(gè)

45、正 整數(shù)。整數(shù)。 62 當(dāng)以某一個(gè)啟動(dòng)距離向一條非線性流水線連續(xù)輸當(dāng)以某一個(gè)啟動(dòng)距離向一條非線性流水線連續(xù)輸 入任務(wù)時(shí)，可能在某一個(gè)功能段或某幾個(gè)功能段入任務(wù)時(shí)，可能在某一個(gè)功能段或某幾個(gè)功能段 中發(fā)生有幾個(gè)任務(wù)同時(shí)爭(zhēng)用同一個(gè)功能段的情況，中發(fā)生有幾個(gè)任務(wù)同時(shí)爭(zhēng)用同一個(gè)功能段的情況， 這種情況就是非線性流水線中的沖突。這種情況就是非線性流水線中的沖突。 如圖如圖5.44所示的非線性流水線，當(dāng)啟動(dòng)距離為所示的非線性流水線，當(dāng)啟動(dòng)距離為3時(shí)，時(shí)， 有關(guān)功能段的沖突情況如圖有關(guān)功能段的沖突情況如圖5.47所示。所示。 63 64 同樣，圖同樣，圖5.44所示的非線性流水線，當(dāng)啟動(dòng)距離為所示的非線性流

46、水線，當(dāng)啟動(dòng)距離為 2時(shí)，沖突情況如圖時(shí)，沖突情況如圖5.48所示。所示。 65 引起非線性流水線功能段沖突的啟動(dòng)距離稱為禁引起非線性流水線功能段沖突的啟動(dòng)距離稱為禁 止啟動(dòng)距離。如圖止啟動(dòng)距離。如圖5.44所示的非線性流水線，啟動(dòng)所示的非線性流水線，啟動(dòng) 距離距離2和啟動(dòng)距離和啟動(dòng)距離3都是禁止啟動(dòng)距離。都是禁止啟動(dòng)距離。 有些啟動(dòng)距離在非線性流水線的所有功能段，在有些啟動(dòng)距離在非線性流水線的所有功能段，在 任何時(shí)間都不會(huì)發(fā)生沖突。如圖任何時(shí)間都不會(huì)發(fā)生沖突。如圖5.44的非線性流水的非線性流水 線，當(dāng)啟動(dòng)距離為線，當(dāng)啟動(dòng)距離為5時(shí)的預(yù)約表如圖時(shí)的預(yù)約表如圖5.49所示。所示。 66 67

47、在非線性流水線中，不發(fā)生沖突的啟動(dòng)距離不一在非線性流水線中，不發(fā)生沖突的啟動(dòng)距離不一 定是一個(gè)常數(shù)，在一般情況下是一個(gè)循環(huán)數(shù)列。定是一個(gè)常數(shù)，在一般情況下是一個(gè)循環(huán)數(shù)列。 例如，圖例如，圖5.44所示的非線性流水線當(dāng)啟動(dòng)距離為所示的非線性流水線當(dāng)啟動(dòng)距離為1、 7、1、7、交替循環(huán)時(shí)，任何一個(gè)功能段在任何交替循環(huán)時(shí)，任何一個(gè)功能段在任何 一個(gè)時(shí)鐘周期也都不發(fā)生沖突，如圖一個(gè)時(shí)鐘周期也都不發(fā)生沖突，如圖5.50所示。所示。 68 69 這種使非線性流水線的任何一個(gè)功能段在任何一這種使非線性流水線的任何一個(gè)功能段在任何一 個(gè)時(shí)鐘周期都不發(fā)生沖突的循環(huán)數(shù)列稱為非線性個(gè)時(shí)鐘周期都不發(fā)生沖突的循環(huán)數(shù)列稱

48、為非線性 流水線的啟動(dòng)循環(huán)。流水線的啟動(dòng)循環(huán)。 圖圖5.50中的啟動(dòng)循環(huán)記作（中的啟動(dòng)循環(huán)記作（1，7）。圖）。圖5.49中的中的 不發(fā)生沖突的啟動(dòng)距離也可以認(rèn)為是一個(gè)循環(huán)數(shù)不發(fā)生沖突的啟動(dòng)距離也可以認(rèn)為是一個(gè)循環(huán)數(shù) 列，可以記作（列，可以記作（5）。這種只有一個(gè)啟動(dòng)距離的啟）。這種只有一個(gè)啟動(dòng)距離的啟 動(dòng)循環(huán)又稱為恒定循環(huán)。動(dòng)循環(huán)又稱為恒定循環(huán)。 要正確調(diào)度一條非線性流水線，首先要找出流水要正確調(diào)度一條非線性流水線，首先要找出流水 線的所有禁止啟動(dòng)距離。線的所有禁止啟動(dòng)距離。 把一條非線性流水線的所有禁止啟動(dòng)距離組合在把一條非線性流水線的所有禁止啟動(dòng)距離組合在 一起就形成一個(gè)數(shù)列，通常把這個(gè)

49、數(shù)列稱為非線一起就形成一個(gè)數(shù)列，通常把這個(gè)數(shù)列稱為非線 性流水線的禁止向量。性流水線的禁止向量。 70 由預(yù)約表得到禁止向量的方法很簡(jiǎn)單，只要把預(yù)由預(yù)約表得到禁止向量的方法很簡(jiǎn)單，只要把預(yù) 約表的每一行中任意兩個(gè)約表的每一行中任意兩個(gè)“”之間的距離都計(jì)算之間的距離都計(jì)算 出來，去掉重復(fù)的，由這種數(shù)組成的一個(gè)數(shù)列就出來，去掉重復(fù)的，由這種數(shù)組成的一個(gè)數(shù)列就 是這條非線性流水線的禁止向量。是這條非線性流水線的禁止向量。 例圖例圖5.44所示的非線性流水線的禁止向量為（所示的非線性流水線的禁止向量為（3， 4，6）。）。 把一個(gè)啟動(dòng)循環(huán)內(nèi)的所有啟動(dòng)距離相加再除以這把一個(gè)啟動(dòng)循環(huán)內(nèi)的所有啟動(dòng)距離相加再

50、除以這 個(gè)啟動(dòng)循環(huán)內(nèi)的啟動(dòng)距離個(gè)數(shù)就得到這個(gè)啟動(dòng)循個(gè)啟動(dòng)循環(huán)內(nèi)的啟動(dòng)距離個(gè)數(shù)就得到這個(gè)啟動(dòng)循 環(huán)的平均啟動(dòng)距離。環(huán)的平均啟動(dòng)距離。 例如，啟動(dòng)循環(huán)（例如，啟動(dòng)循環(huán)（1，7）的平均啟動(dòng)距離是）的平均啟動(dòng)距離是4，而，而 恒定循環(huán)（恒定循環(huán)（5）的平均啟動(dòng)距離就是它本身的啟動(dòng)）的平均啟動(dòng)距離就是它本身的啟動(dòng) 距離距離5。 無沖突的調(diào)度方法無沖突的調(diào)度方法 71 非線性流水線無沖突調(diào)度的主要目標(biāo)是要找出具非線性流水線無沖突調(diào)度的主要目標(biāo)是要找出具 有最小平均啟動(dòng)距離的啟動(dòng)循環(huán)，按照這樣的啟有最小平均啟動(dòng)距離的啟動(dòng)循環(huán)，按照這樣的啟 動(dòng)循環(huán)向非線性流水線的輸入端輸入任務(wù)，流水動(dòng)循環(huán)向非線性流水線的輸入

51、端輸入任務(wù)，流水 線的工作速度最快，而且所有功能段在任何時(shí)間線的工作速度最快，而且所有功能段在任何時(shí)間 都沒有沖突。都沒有沖突。 根據(jù)一張預(yù)約表的禁止向量可以很容易得到?jīng)_突根據(jù)一張預(yù)約表的禁止向量可以很容易得到?jīng)_突 向量。向量。 沖突向量用一個(gè)沖突向量用一個(gè)m位的二進(jìn)制數(shù)表示，其中位的二進(jìn)制數(shù)表示，其中m是禁是禁 止向量中的最大值。對(duì)于一張止向量中的最大值。對(duì)于一張k列的預(yù)約表，有列的預(yù)約表，有 mk1。一般的沖突向量用。一般的沖突向量用C(CmCm1C2 C1)來表示。如果在在禁止向量中，則來表示。如果在在禁止向量中，則Ci 1，否，否 則則Ci 0。其中。其中, Cm一定為一定為1，因?yàn)椋?/p>

52、因?yàn)閙必定在禁止必定在禁止 向量中。向量中。 72 例如，對(duì)于圖例如，對(duì)于圖5.44(b)所示預(yù)約表，沖突向量所示預(yù)約表，沖突向量C (101100)。 由沖突向量可以構(gòu)造一張狀態(tài)圖。由沖突向量可以構(gòu)造一張狀態(tài)圖。 把沖突向量把沖突向量C作為初始沖突向量送入一個(gè)作為初始沖突向量送入一個(gè)m位邏輯位邏輯 右移移位器，當(dāng)從移位器移出的位為右移移位器，當(dāng)從移位器移出的位為0時(shí)，用移位時(shí)，用移位 器中的值與初始沖突向量作器中的值與初始沖突向量作“按位或按位或”運(yùn)算，得運(yùn)算，得 到一個(gè)新的沖突向量；若移位器移出的位為到一個(gè)新的沖突向量；若移位器移出的位為1，不，不 做任何處理；移位器繼續(xù)右移，如此重復(fù)做任

53、何處理；移位器繼續(xù)右移，如此重復(fù)m次。次。 在初始沖突向量和所有新形成的沖突向量之間用在初始沖突向量和所有新形成的沖突向量之間用 帶箭頭的線連接，表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系。帶箭頭的線連接，表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系。 線邊注上數(shù)字線邊注上數(shù)字n，表示初始沖突向量經(jīng)過，表示初始沖突向量經(jīng)過n次右移次右移 產(chǎn)生新沖突向量。產(chǎn)生新沖突向量。 73 對(duì)于中間形成的每一個(gè)新的沖突向量，也按這一對(duì)于中間形成的每一個(gè)新的沖突向量，也按這一 方法進(jìn)行處理。方法進(jìn)行處理。 當(dāng)形成的新沖突向量出現(xiàn)重復(fù)時(shí)，可合并到一起。當(dāng)形成的新沖突向量出現(xiàn)重復(fù)時(shí)，可合并到一起。 由圖由圖5.44所示非線性流水線構(gòu)成的狀態(tài)圖如圖

54、所示非線性流水線構(gòu)成的狀態(tài)圖如圖5.51 所示。所示。 74 75 當(dāng)初始沖突向量確定之后，狀態(tài)圖就是唯一的，當(dāng)初始沖突向量確定之后，狀態(tài)圖就是唯一的， 因此，與一張預(yù)約表相對(duì)應(yīng)，只有唯一的一個(gè)狀因此，與一張預(yù)約表相對(duì)應(yīng)，只有唯一的一個(gè)狀 態(tài)圖。但是，由于不同的預(yù)約表可能產(chǎn)生相同的態(tài)圖。但是，由于不同的預(yù)約表可能產(chǎn)生相同的 初始沖突向量，因此，不同的預(yù)約表也可能有相初始沖突向量，因此，不同的預(yù)約表也可能有相 同的狀態(tài)圖。所以，從預(yù)約表可以畫出狀態(tài)圖，同的狀態(tài)圖。所以，從預(yù)約表可以畫出狀態(tài)圖， 但從狀態(tài)圖不能得到預(yù)約表。但從狀態(tài)圖不能得到預(yù)約表。 在狀態(tài)圖中可以找到無窮多個(gè)不發(fā)生功能段沖突在狀態(tài)

55、圖中可以找到無窮多個(gè)不發(fā)生功能段沖突 的啟動(dòng)循環(huán)。因?yàn)榉蔷€性流水線調(diào)度的主要目標(biāo)的啟動(dòng)循環(huán)。因?yàn)榉蔷€性流水線調(diào)度的主要目標(biāo) 是要找出平均啟動(dòng)距離最小的啟動(dòng)循環(huán)，因此，是要找出平均啟動(dòng)距離最小的啟動(dòng)循環(huán)，因此， 在這些無窮多個(gè)啟動(dòng)循環(huán)中，一般只要找出簡(jiǎn)單在這些無窮多個(gè)啟動(dòng)循環(huán)中，一般只要找出簡(jiǎn)單 循環(huán)即可。循環(huán)即可。 所謂簡(jiǎn)單循環(huán)是指狀態(tài)圖中各種沖突向量只經(jīng)過所謂簡(jiǎn)單循環(huán)是指狀態(tài)圖中各種沖突向量只經(jīng)過 一次的啟動(dòng)循環(huán)。一次的啟動(dòng)循環(huán)。 76 狀態(tài)圖狀態(tài)圖5.51中的所有簡(jiǎn)單循環(huán)如表中的所有簡(jiǎn)單循環(huán)如表5.1所示，表中所示，表中 還給出了簡(jiǎn)單循環(huán)的平均啟動(dòng)距離還給出了簡(jiǎn)單循環(huán)的平均啟動(dòng)距離。 77

56、 從表中可以找到平均啟動(dòng)距離最小的啟動(dòng)循環(huán)，從表中可以找到平均啟動(dòng)距離最小的啟動(dòng)循環(huán)， 這樣的啟動(dòng)循環(huán)被稱為最小啟動(dòng)循環(huán)。這樣的啟動(dòng)循環(huán)被稱為最小啟動(dòng)循環(huán)。 上例中，最小啟動(dòng)循環(huán)為（上例中，最小啟動(dòng)循環(huán)為（1，1，7），平均啟動(dòng)），平均啟動(dòng) 距離為：距離為：（1 1 7）/33。 圖圖5.44所示非線性流水線按照最小啟動(dòng)循環(huán)（所示非線性流水線按照最小啟動(dòng)循環(huán)（1， 1，7）工作時(shí)，流水線預(yù)約表如圖）工作時(shí)，流水線預(yù)約表如圖5.52所示。所示。 78 79 優(yōu)化調(diào)度方法優(yōu)化調(diào)度方法 按照前面介紹的調(diào)度方法得到的最小啟動(dòng)循環(huán)，按照前面介紹的調(diào)度方法得到的最小啟動(dòng)循環(huán)， 有時(shí)并不能使非線性流水線充分

57、發(fā)揮效率。有時(shí)并不能使非線性流水線充分發(fā)揮效率。 下面將介紹非線性流水線的優(yōu)化調(diào)度方法，按照下面將介紹非線性流水線的優(yōu)化調(diào)度方法，按照 這種方法調(diào)度非線性流水線，流水線的工作效率這種方法調(diào)度非線性流水線，流水線的工作效率 最高，即流水線的吞吐率、加速比和效率最好。最高，即流水線的吞吐率、加速比和效率最好。 預(yù)約表中預(yù)約表中“”最多的一行所對(duì)應(yīng)的功能段一定是最多的一行所對(duì)應(yīng)的功能段一定是 整個(gè)流水線的瓶頸功能段。要使整個(gè)流水線充分整個(gè)流水線的瓶頸功能段。要使整個(gè)流水線充分 發(fā)揮效率，瓶頸功能段必須不間斷工作，不能有發(fā)揮效率，瓶頸功能段必須不間斷工作，不能有 空閑?？臻e。 80 因此，非線性流水線

58、調(diào)度的關(guān)鍵是充分使用瓶頸因此，非線性流水線調(diào)度的關(guān)鍵是充分使用瓶頸 功能段，只要讓瓶頸功能段不空閑，則非線性流功能段，只要讓瓶頸功能段不空閑，則非線性流 水線的吞吐率、加速比和效率必然是最好的。按水線的吞吐率、加速比和效率必然是最好的。按 照這種方法調(diào)度流水線，流水線的平均啟動(dòng)距離照這種方法調(diào)度流水線，流水線的平均啟動(dòng)距離 也一定是最小的。也一定是最小的。 采用預(yù)留算法來調(diào)度非線性流水線，可以達(dá)到最采用預(yù)留算法來調(diào)度非線性流水線，可以達(dá)到最 優(yōu)調(diào)度。具體方法如下：優(yōu)調(diào)度。具體方法如下： 確定流水線的最小平均啟動(dòng)距離。確定流水線的最小平均啟動(dòng)距離。 最小平均啟動(dòng)距離等于預(yù)約表中任意一行中最小平均

59、啟動(dòng)距離等于預(yù)約表中任意一行中“” 的最多個(gè)數(shù)。的最多個(gè)數(shù)。 確定最小啟動(dòng)循環(huán)。確定最小啟動(dòng)循環(huán)。 81 相對(duì)于同一個(gè)最小平均啟動(dòng)距離可能有多個(gè)最小相對(duì)于同一個(gè)最小平均啟動(dòng)距離可能有多個(gè)最小 啟動(dòng)循環(huán)，其中有一個(gè)恒定循環(huán)。為了簡(jiǎn)化控制啟動(dòng)循環(huán)，其中有一個(gè)恒定循環(huán)。為了簡(jiǎn)化控制 邏輯，一般選擇恒定循環(huán)作為最小啟動(dòng)循環(huán)。邏輯，一般選擇恒定循環(huán)作為最小啟動(dòng)循環(huán)。 結(jié)合流水線預(yù)約表和連接圖，采用預(yù)留算法，結(jié)合流水線預(yù)約表和連接圖，采用預(yù)留算法， 通過插入非計(jì)算延遲功能段實(shí)現(xiàn)最小啟動(dòng)循環(huán)。通過插入非計(jì)算延遲功能段實(shí)現(xiàn)最小啟動(dòng)循環(huán)。 以下，結(jié)合圖以下，結(jié)合圖5.44的例子，具體說明調(diào)度方法。的例子，具體說

60、明調(diào)度方法。 用預(yù)留算法調(diào)度的預(yù)約表、連接圖如圖用預(yù)留算法調(diào)度的預(yù)約表、連接圖如圖5.53所示。所示。 與圖與圖5.53相對(duì)應(yīng)的流水線狀態(tài)圖如圖相對(duì)應(yīng)的流水線狀態(tài)圖如圖5.54所示。所示。 按照最小啟動(dòng)循環(huán)（按照最小啟動(dòng)循環(huán)（3）工作的流水線預(yù)約表如圖）工作的流水線預(yù)約表如圖 5.55所示。每間隔所示。每間隔3個(gè)時(shí)鐘周期，可以向流水線個(gè)時(shí)鐘周期，可以向流水線 82 輸入一個(gè)新任務(wù)。此時(shí)，流水線的任何一個(gè)功能輸入一個(gè)新任務(wù)。此時(shí)，流水線的任何一個(gè)功能 段在任何一個(gè)時(shí)鐘周期都不發(fā)生沖突。另外，從段在任何一個(gè)時(shí)鐘周期都不發(fā)生沖突。另外，從 時(shí)鐘周期時(shí)鐘周期7開始，瓶頸功能段開始，瓶頸功能段S1就一直