計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第五章標(biāo)量處理機(jī)課件

1、第五章 標(biāo)量處理機(jī)7/29/2022本章主要內(nèi)容5.1 先行控制技術(shù)5.2 流水線技術(shù)5.3 相關(guān)性分析技術(shù)5.4 超標(biāo)量處理機(jī)5.5 超流水線處理機(jī)5.6 超標(biāo)量超流水線處理機(jī)2標(biāo)量處理機(jī)只有標(biāo)量數(shù)據(jù)表示和標(biāo)量指令系統(tǒng)的處理機(jī)稱為標(biāo)量處理機(jī)，是最常用最普通的處理機(jī)。設(shè)計(jì)處理機(jī)的主要任務(wù)就是縮短解釋指令的時間，提高處理機(jī)指令的執(zhí)行速度：提高處理機(jī)的工作主頻。5、60年代主要采用這種技術(shù)，每3、4年處理機(jī)的速度要提高一個數(shù)量級。采用更好的算法和設(shè)計(jì)更好的功能部件，如采用RISC等。多條指令并行執(zhí)行。指令級的并行技術(shù)。流水線技術(shù)。處理機(jī)中設(shè)置多個獨(dú)立的功能部件，如浮點(diǎn)運(yùn)算器，定點(diǎn)運(yùn)算器，訪存部件等

2、。超長指令技術(shù)。35.1 先行控制技術(shù)先行控制技術(shù)的關(guān)鍵是采用緩沖技術(shù)和預(yù)處理技術(shù)，以及兩者都采用，通過對指令流和數(shù)據(jù)流的預(yù)處理和緩沖，能夠盡量使指令分析器和指令執(zhí)行部件獨(dú)立工作并始終處于忙碌狀態(tài)。5.1.1 指令的重疊執(zhí)行方式5.1.2 先行控制方式的原理5.1.3 處理機(jī)結(jié)構(gòu)5.1.4 指令執(zhí)行序列5.1.5 先行緩沖棧5.1.6 緩沖深度的設(shè)計(jì)方法4指令的重疊執(zhí)行方式一條指令的執(zhí)行可以分為多個階段，具體分法視處理機(jī)而定，一般可以分為三個階段：取指令是指按照指令計(jì)數(shù)器的內(nèi)容訪問主存，取出一條指令送到指令寄存器。分析指令是指對指令的操作碼進(jìn)行譯碼，按照給定的尋址方式和地址字段內(nèi)容形成操作數(shù)地

3、址，并用這個地址讀出操作數(shù)，操作數(shù)可以在主存也可以在寄存器。執(zhí)行指令是根據(jù)操作碼的要求，完成指令規(guī)定的功能，把結(jié)果寫到主存或者寄存器。指令分析或者指令執(zhí)行階段還得修改指令計(jì)數(shù)器的更新，為下一條指令作準(zhǔn)備。5指令的重疊執(zhí)行方式1.順序執(zhí)行方式執(zhí)行n條指令所用的時間為：如果每段時間都為t，則執(zhí)行n條指令所用的時間為：T3 n t主要優(yōu)點(diǎn)：控制簡單，節(jié)省設(shè)備。主要缺點(diǎn)：速度慢，功能部件的利用率低。62.一次重疊執(zhí)行方式如果兩個過程的時間相等，則執(zhí)行n條指令的時間為：T(1+2n)t主要優(yōu)點(diǎn)： 指令的執(zhí)行時間縮短， 功能部件的利用率明顯提高。主要缺點(diǎn)： 需要增加一些硬件， 控制過程稍復(fù)雜。指令的重疊執(zhí)

4、行方式(續(xù)) 73.二次重疊執(zhí)行方式如果三個過程的時間相等，執(zhí)行n條指令的時間為：T(2n）t在理想情況下，處理機(jī)中同時有三條指令在執(zhí)行。處理機(jī)的結(jié)構(gòu)要作比較大的改變，需要采用先行控制技術(shù)。 指令的重疊執(zhí)行方式(續(xù)) 8先行控制方式的原理1.采用二次重疊執(zhí)行方式必須解決兩個問題：(1)有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件 把一個集中的指令控制器，分解成三個獨(dú)立的控制器： 存儲控制器、指令控制器、運(yùn)算控制器。(2)要解決訪問主存儲器的沖突問題 取指令、分析指令、執(zhí)行指令都可能要訪問存儲器。92.解決訪存沖突的方法：(1)采用低位交叉存取方式：這種方法不能根本解決沖突問題。取指令、讀操作

5、數(shù)、寫結(jié)果。(2)主存分為兩個獨(dú)立的存儲器：獨(dú)立的指令存儲器和數(shù)據(jù)存儲器。如果再規(guī)定，執(zhí)行指令所需要的操作數(shù)和執(zhí)行結(jié)果只寫到通用寄存器，則取指令、分析指令和執(zhí)行指令就可以同時進(jìn)行。在許多高性能處理機(jī)中，有獨(dú)立的指令Cache和數(shù)據(jù)Cache。這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)。先行控制方式的原理（續(xù)）10(3)采用先行控制技術(shù)采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。緩沖技術(shù)通常用在工作速度不固定的兩個功能部件之間。設(shè)置緩沖棧的目的是用來以平滑功能部件之間的工作速度。在采用了緩沖技術(shù)和預(yù)處理技術(shù)之后，運(yùn)算器能夠?qū)Ｐ挠跀?shù)據(jù)的運(yùn)算，從而大幅度提高程序的執(zhí)行速度。先行控制方式的原理（續(xù)）11處理機(jī)結(jié)構(gòu)1.三

6、個獨(dú)立的控制器：存儲控制器、指令控制器、運(yùn)算控制器。2.四個緩沖棧：先行指令緩沖棧、先行讀數(shù)緩沖棧、先行操作棧、后行寫數(shù)棧。3.處理機(jī)組成124.先行指令緩沖棧的組成作用：只要指令緩沖棧沒有充滿，就自動發(fā)出取指令的請求。指令分析器每分析完一條指令，自動向指令緩沖棧發(fā)出取下一條指令的請求，指令取出后就把先行指令緩沖棧中的指令作廢。分析指令速度和從主存取指令的速度是隨機(jī)的，指令緩沖棧的指令數(shù)目是動態(tài)的。設(shè)置兩個程序計(jì)數(shù)器：先行程序計(jì)數(shù)器PC1，用來指示取指令，現(xiàn)行程序計(jì)數(shù)器PC，記錄指令分析器正在分析的指令地址。處理機(jī)結(jié)構(gòu)（續(xù)）13處理機(jī)結(jié)構(gòu)（續(xù)）先行緩沖站的組成指令緩沖存儲器堆，采用先進(jìn)先出的方

7、式，保證指令的執(zhí)行順序不致混亂。14處理機(jī)結(jié)構(gòu)（續(xù)）先行控制方式中的一次重疊執(zhí)行重疊部分，無論誰先結(jié)束，都不能提前執(zhí)行下一條指令，需要等待。無論任何時刻，在指令分析部件和指令執(zhí)行部件內(nèi)都只有相鄰的兩條指令重疊執(zhí)行，處理機(jī)只需要設(shè)置一套指令分析部件，指令控制器；一套指令執(zhí)行部件，運(yùn)算控制器和運(yùn)算器。控制方式簡單。所需要時間為T=（1+n）t15處理機(jī)結(jié)構(gòu)（續(xù)）5.存在的主要問題：計(jì)算機(jī)指令系統(tǒng)復(fù)雜，各類指令“分析”和“執(zhí)行”的時間相差很大，分析指令和執(zhí)行指令常常相互等待，造成部件的浪費(fèi)。分析k+1操作所需要的操作數(shù)正好是執(zhí)行k的結(jié)果，不能重疊執(zhí)行，發(fā)生數(shù)據(jù)相關(guān)，還有控制相關(guān)，變址相關(guān)。轉(zhuǎn)移或轉(zhuǎn)子

8、程序指令時，程序的執(zhí)行過程不是順序的，先行指令緩沖棧中預(yù)取指令和分析的下一條指令都可能要作廢。16指令執(zhí)行時序設(shè)置了指令緩沖棧，取指令的時間就可以忽略不計(jì)。一條指令的執(zhí)行可分為2個過程。1.分析指令和執(zhí)行指令時間不相等時的情況。17指令執(zhí)行時序2.采用先行緩沖棧的指令執(zhí)行過程先行讀數(shù)棧,先行操作棧,后行寫數(shù)棧。理想情況下，指令執(zhí)行部件應(yīng)該一直忙碌。連續(xù)執(zhí)行n條指令的時間為：18先行緩沖棧設(shè)置先行緩沖棧的目的：使指令分析器和指令執(zhí)行部件能夠獨(dú)立工作。1.先行指令緩沖棧：處于主存儲器與指令分析器之間。用它來平滑主存儲器取指令和指令分析器使用指令之間的速度差異。RR型指令，不必處理，直接送先行緩沖棧

9、。RS型指令，主存有效地址送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的主存地址碼部分，形成RR*指令送先行緩沖棧。19RI型指令，指令中的立即數(shù)送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號替換指令中的立即數(shù)部分，形成RR*指令送先行緩沖棧。轉(zhuǎn)移指令，一般在指令分析器中直接執(zhí)行。2.先行操作棧處于指令分析器和運(yùn)算控制器之間。使指令分析器和運(yùn)算器能夠各自獨(dú)立工作。采用先進(jìn)先出方式工作，由指令寄存器堆和控制邏輯組成。先行緩沖棧（續(xù)）203.先行讀數(shù)棧處于主存儲器與運(yùn)算器之間。平滑運(yùn)算器與主存儲器的工作。每個緩沖寄存器由地址寄存器、操作數(shù)寄存器和標(biāo)志三部分組成。也可以把地址寄存器和操作數(shù)寄存器合為

10、一個。當(dāng)收到從指令分析器中送來的有效地址時，就向主存申請讀操作數(shù)。讀出的操作數(shù)存放在操作數(shù)寄存器中或覆蓋掉地址寄存器中的地址。先行緩沖棧（續(xù)）214.后行寫數(shù)棧每個后行緩沖寄存器由地址寄存器、數(shù)據(jù)寄存器和標(biāo)志三部分組成。指令分析器遇到向主存寫結(jié)果的指令時，把形成的有效地址送入后行寫數(shù)棧的地址寄存器中，并用該地址寄存器的編號替換指令的目的地址部分，形成RR*指令送入先行操作棧。當(dāng)運(yùn)算器執(zhí)行這條RR*型寫數(shù)指令時，只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可。先行緩沖棧（續(xù)）22先行緩沖棧（續(xù)）5.采用先行控制方式時一個程序的執(zhí)行情況：23緩沖深度的設(shè)計(jì)方法以靜態(tài)分析為主，通過模擬來確定緩

11、沖深度。1.先行指令緩沖棧的設(shè)計(jì)考慮兩種極端情況：假設(shè)緩沖深度為DI(1)先行指令緩沖棧已經(jīng)充滿指令流出的速度最快，例如連續(xù)分析RR型指令，設(shè)這種指令序列的最大長度為L1，平均分析一條這種指令的時間為t1。指令流入的速度最慢，設(shè)平均取一條指令的時間為t2。從主存儲器中取到先行指令緩沖棧中的指令條數(shù)是L1DI條。24應(yīng)該滿足如下關(guān)系：L1 t1(LIDI) t2計(jì)算出緩沖深度為：如果這種指令流的連續(xù)長度超過L1，則先行指令緩沖棧被取空，指令分析器沒有指令可分析，被迫處于等待狀態(tài)。緩沖棧失去作用。(2)先行指令緩沖棧原來為空輸入端指令流入的速度最快，每次取指令的時間最短；設(shè)這種指令序列的最大長度為

12、 L2，平均取一條這種指令的時間為 t2；緩沖深度的設(shè)計(jì)方法（續(xù)）25輸出端指令流出的速度最慢，指令分析器連續(xù)分析最難分析的指令；設(shè)平均分析一條指令的時間為 t1。分析的指令條數(shù)是L2DI條。應(yīng)該滿足如下關(guān)系：(L2DI) t1LI t2計(jì)算出緩沖深度為：如果這種指令流的連續(xù)長度超過L2，先行指令緩沖棧被完全充滿，失去緩沖作用。緩沖深度的設(shè)計(jì)方法（續(xù)）262.設(shè)計(jì)舉例在一般處理機(jī)中連續(xù)執(zhí)行短指令的概率大。例：一個采用先行控制方式的處理機(jī)，指令分析器分析一條指令用一個周期，到主存儲器中取一條指令裝入先行指令緩沖棧平均用4個周期，如果這種指令的平均長度為9，即90的指令是執(zhí)行時間短的指令。解：計(jì)算

13、先行指令緩沖棧的緩沖深度為：緩沖深度的設(shè)計(jì)方法（續(xù)）273.先行指令緩沖棧的工作時間關(guān)系第1個周期，取走指令k+1，請求取指令。第4個周期末尾，指令k+8取到先行指令緩沖棧。第8個周期末尾，指令k+9取到先行指令緩沖棧。第9個周期，分析指令k+9，先行指令緩沖棧空。第10個周期，指令分析器等待。緩沖深度的設(shè)計(jì)方法（續(xù)）284.其余緩沖棧的設(shè)計(jì)原則一般有關(guān)系：DIDCDRDW 其中：DI是先行指令緩沖棧的緩沖深度， DC是先行操作棧的緩沖深度， DR是先行讀數(shù)棧的緩沖深度， DW是后行寫數(shù)棧的緩沖深度。例如：IBM370/165機(jī)： DI4，DC3，DR2，DW1。 我國研制的兩臺大型計(jì)算機(jī)：

14、DI8，DCDR4，DW2。 DI12，DCDR6，DW2。緩沖深度的設(shè)計(jì)方法（續(xù)）29數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)：在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址量等是前面指令的執(zhí)行結(jié)果，這種相關(guān)稱為數(shù)據(jù)相關(guān)?？刂葡嚓P(guān)：由條件分支指令、轉(zhuǎn)子程序指令、中斷等引起的相關(guān)。解決數(shù)據(jù)相關(guān)的方法有兩種：推后分析法，遇到相關(guān)數(shù)據(jù)，推后本條指令的分析，直至所需要的數(shù)據(jù)寫入到相關(guān)的存儲單元。設(shè)置專用路徑。不必等到所需要的數(shù)據(jù)寫入到相關(guān)存儲單元，而是經(jīng)專門設(shè)置的數(shù)據(jù)通路讀取所需要的數(shù)據(jù)。301.指令相關(guān)發(fā)生指令相關(guān)的情況： n： STORE R1, n+1 n+1： 滿足關(guān)系： 結(jié)果地址(n)指令地址(n+1)當(dāng)?shù)?/p>

15、n條指令還沒有把執(zhí)行結(jié)果寫到主存之前，取出的第n+1條指令顯然是錯誤的。在k個流水段的流水線處理機(jī)中，第n條指令要修改從第n+1到第n+ k 指令中的任意一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤。數(shù)據(jù)相關(guān)（續(xù)）31在采用先行控制方式的處理機(jī)中，如果執(zhí)行部件正在執(zhí)行第n條指令，與下述情況之一發(fā)生相關(guān)，都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤。存放在先行操作棧中的指令正在指令分析器中分析的指令已經(jīng)預(yù)取到先行指令緩沖棧中的指令指令執(zhí)行結(jié)果還在后行緩沖棧中的指令更嚴(yán)重的是：有些分支指令，可能已經(jīng)在指令分析器中執(zhí)行完成。 數(shù)據(jù)相關(guān)（續(xù)）32解決指令相關(guān)的根本辦法是： 在程序執(zhí)行過程中不允許修改指令?，F(xiàn)代程序設(shè)計(jì)方

16、法要求程序具有再入性，可以被遞歸調(diào)用等，也要求不修改指令。在IBM370系列機(jī)中，用“執(zhí)行指令”來解決：在程序執(zhí)行過程中既能夠修改指令，程序又具有再入性?！皥?zhí)行指令”執(zhí)行由第二地址(X2)+(B2)+D2)決定的主存數(shù)據(jù)區(qū)中的指令。數(shù)據(jù)相關(guān)（續(xù)）332.主存操作數(shù)相關(guān)發(fā)生主存操作數(shù)相關(guān)的指令序列： n：OP A1，A2，A3 ；A1(A2) OP (A3) n+1：OP A4，A1，A5 ；A4(A1) OP (A5)出現(xiàn)下列情況之一，A1、A2、A3是主存地址，就發(fā)生主存操作數(shù)相關(guān)： A1（n） A2（n1） A1（n） A3（n1）解決辦法：運(yùn)算結(jié)果寫到通用寄存器，而不寫到主存對于訪問主存

17、儲器的請求，寫結(jié)果的優(yōu)先級高于讀操作數(shù)。數(shù)據(jù)相關(guān)（續(xù)）34有先行操作棧處理機(jī)中，分析指令、已經(jīng)執(zhí)行指令需要進(jìn)入后行寫數(shù)操作棧向主存寫回運(yùn)算結(jié)果的指令之間可能相隔很多條指令。已經(jīng)進(jìn)入先行操作棧的任何一條指令在向主存申請讀數(shù)時都可能與正在執(zhí)行部件中執(zhí)行的指令、正在后行寫數(shù)棧中等待寫結(jié)果到主存的指令，甚至還在先行操作棧中的指令發(fā)生主存操作數(shù)相關(guān)。解決辦法：對于剛進(jìn)入先行操作棧中的指令在向主存讀數(shù)之前，首先把訪問主存的地址與后行寫數(shù)棧中的所有主存地址比較，如果發(fā)現(xiàn)有相等的，則先行棧的讀數(shù)操作緩行，等到相關(guān)寫操作數(shù)指令完成，并把結(jié)果寫到主存之后再讀數(shù)。數(shù)據(jù)相關(guān)（續(xù)）35數(shù)據(jù)相關(guān)（續(xù)）3. 通用寄存器數(shù)據(jù)

18、相關(guān)發(fā)生寄存器數(shù)據(jù)相關(guān)的可能性很大，影響面也很大 n：OP R1，A2 ；R1(R1) OP (A2) n+1：OP R1，R2 ；R1(R1) OP (R2)發(fā)生R1(n)R1(n1)稱為R1數(shù)據(jù)相關(guān)。發(fā)生R1(n)R2(n1)稱為R2數(shù)據(jù)相關(guān)。36解決通用寄存器數(shù)據(jù)相關(guān)的方法：方法一：把讀操作數(shù)、寫運(yùn)算結(jié)果與指令執(zhí)行合在一個節(jié)拍。從數(shù)據(jù)從通用寄存器讀出，在運(yùn)算器中完成運(yùn)算，結(jié)果寫回通用寄存器的整個回路中，只有通用寄存器是時序邏輯。當(dāng)發(fā)生下述情況時，不能采用這種方法：當(dāng)寄存器個數(shù)多時，讀寫寄存器的時間長。當(dāng)功能部件數(shù)量多時，寄存器的讀寫端口多。當(dāng)功能部件的執(zhí)行時間比較長，或要求指令的執(zhí)行時間

19、短時 。數(shù)據(jù)相關(guān)（續(xù)）37方法二：建立相關(guān)專用通路(ByPass)由于發(fā)生寄存器數(shù)據(jù)相關(guān)的情況很普遍，一般計(jì)算機(jī)系統(tǒng)都采用專用數(shù)據(jù)通路。把讀通用寄存器、執(zhí)行操作和寫結(jié)果分為3個周期，或2個周期。采用專用數(shù)據(jù)通路能夠縮短1至2個周期。數(shù)據(jù)相關(guān)（續(xù)）38變址相關(guān)：在采用變址尋址方式的處理機(jī)中，由于變址量放在寄存器中，因此，可能發(fā)生與通用寄存器數(shù)據(jù)相關(guān)類似變址相關(guān).4. LOAD相關(guān) LOAD操作的執(zhí)行時間可能比較長 n： LOAD R1， A ；R1(A) n+1： ADD R1， R2 ；R1(R1) OP (R2) 如果 R1(n)R2(n1)，或 R1(n)R1(n1)， 則發(fā)生LOAD數(shù)據(jù)

20、相關(guān)。數(shù)據(jù)相關(guān)（續(xù)）39解決方法：方法一：由編譯器在LOAD之后插入不發(fā)生數(shù)據(jù)相關(guān)的指令，由于LOAD的執(zhí)行時間不確定，不能根本解決問題。方法二：由硬件自動插入空操作，直到LOAD操作完成。在單條流水線處理機(jī)中，也可以停止節(jié)拍發(fā)生器，直到數(shù)據(jù)從存儲器中讀出為止。數(shù)據(jù)相關(guān)（續(xù)）40控制相關(guān)因程序的執(zhí)行方向可能被改變而引起的相關(guān)，也稱為全局相關(guān)。主要包括：無條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、復(fù)合條件轉(zhuǎn)移、中斷等。1. 無條件轉(zhuǎn)移在流水線處理機(jī)中，無條件轉(zhuǎn)移指令不進(jìn)入執(zhí)行流水段，一般在指令譯碼階段就實(shí)際執(zhí)行完成。如果在處理機(jī)中設(shè)置有指令先行緩沖棧，則要全部或部分作廢先行指令緩沖棧中的指令。41如果轉(zhuǎn)移目標(biāo)指令

21、L不在先行指令緩沖棧中，則要將先行指令緩沖棧中的所有指令全部作廢，并等待取出轉(zhuǎn)移目標(biāo)指令L。如果轉(zhuǎn)移目標(biāo)指令L在先行指令緩沖棧中，只要作廢先行指令緩沖棧中的部分指令。無條件轉(zhuǎn)移指令一般對指令執(zhí)行部件的工作不會造成影響。為進(jìn)一步減少無條件轉(zhuǎn)移指令造成的影響，在先行指令緩沖棧的入口處增設(shè)一個專門處理無條件轉(zhuǎn)移指令的指令分析器控制相關(guān)(續(xù)) 422.一般條件轉(zhuǎn)移 k： ;置條件碼CC k+1：JMP(CC) L ;如果CC為真轉(zhuǎn)向L L： 當(dāng)條件碼是上一條指令產(chǎn)生時，相關(guān)最嚴(yán)重控制相關(guān)(續(xù)) 43無論轉(zhuǎn)移是否成功，條轉(zhuǎn)移指令都在指令分析階段就已經(jīng)執(zhí)行完成。無論轉(zhuǎn)移不成功或不成功，指令分析器要停頓一段

22、時間，等待條件碼產(chǎn)生。控制相關(guān)(續(xù)) 44如果轉(zhuǎn)移成功：指令L已經(jīng)在先行指令緩沖棧，指令分析器接著“分析L”，如果指令L不在先行指令緩沖棧，指令分析器要等待一個周期。轉(zhuǎn)移不成功，對程序執(zhí)行影響不大，當(dāng)轉(zhuǎn)移成功時，不僅指令執(zhí)行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。在采用流水線方式的處理機(jī)中，要通過軟件與硬件的多種手段來近可能地降低轉(zhuǎn)移成功的概率，減少轉(zhuǎn)移成功造成的影響?？刂葡嚓P(guān)(續(xù)) 453.復(fù)合條件轉(zhuǎn)移 k：OP L ;產(chǎn)生條件碼，并決定是否轉(zhuǎn)向L L：如果轉(zhuǎn)移不成功：不造成任何影響，就象普通的運(yùn)算型指令一樣如果轉(zhuǎn)移成功：造成的影響比一般條件轉(zhuǎn)移指令還要大得多。全部或部分作廢

23、先行指令緩沖棧、先行操作棧、先行讀數(shù)棧和指令分析器中的指令。必須采取策略，減小轉(zhuǎn)移成功造成的影響。控制相關(guān)(續(xù)) 46控制相關(guān)(續(xù)) 47轉(zhuǎn)移預(yù)測技術(shù)轉(zhuǎn)移預(yù)測技術(shù)包括：靜態(tài)分支預(yù)測：在程序執(zhí)行過程中轉(zhuǎn)移預(yù)測方向不能改變動態(tài)分支預(yù)測： 在程序執(zhí)行過程中能夠改變轉(zhuǎn)移預(yù)測方向48靜態(tài)分支預(yù)測技術(shù)1.軟件“猜測法”目標(biāo)：通過編譯器盡量降低轉(zhuǎn)移成功的概率。例如：對于循環(huán)程序，普通編譯器生成的目標(biāo)代碼，轉(zhuǎn)移成功的概率很高，不成功的只有一次。這種編譯結(jié)果對流水線極為不利。優(yōu)點(diǎn)：不需要改變先行控制器的硬件結(jié)構(gòu)，只需適當(dāng)修改編譯器就能夠大幅度降低條件轉(zhuǎn)移指令對先行控制器產(chǎn)生的影響。其最終目標(biāo)是提高處理機(jī)執(zhí)行程序

24、的速度。49靜態(tài)分支預(yù)測技術(shù)（續(xù)）軟件“猜測法”：通過編譯器降低轉(zhuǎn)移成功的概率502.硬件“猜測法”方法：通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對流水線的影響在先行指令緩沖棧的入口處設(shè)置一個簡單的指令分析器，當(dāng)檢測到轉(zhuǎn)移指令時，就把轉(zhuǎn)移目標(biāo)地址L送入先行程序計(jì)數(shù)器PC1中，同時保留當(dāng)前PC1中的內(nèi)容到另一寄存器中。轉(zhuǎn)移成功，猜測正確。對轉(zhuǎn)移指令對流水線不造成影響。轉(zhuǎn)移不成功，用保存下來的地址恢復(fù)PC1和PC。軟硬件共同配合，都往同一個方向去猜測。靜態(tài)分支預(yù)測技術(shù)（續(xù)）513.兩個先行指令緩沖棧向前條件轉(zhuǎn)移，轉(zhuǎn)移成功與不成功各50%在先行指令緩沖棧中增加一個先行目標(biāo)緩沖棧按照轉(zhuǎn)移成功的方向預(yù)取指令到先行

25、目標(biāo)緩沖棧中。先行指令緩沖棧仍然按照轉(zhuǎn)移不成功的方向繼續(xù)預(yù)取指令。如果轉(zhuǎn)移不成功，則繼續(xù)分析原來先行指令緩沖棧中指令。如果轉(zhuǎn)移成功，則分析新增設(shè)的先行目標(biāo)緩沖棧中的指令。靜態(tài)分支預(yù)測技術(shù)（續(xù)）52靜態(tài)分支預(yù)測技術(shù)（續(xù)）AIB，新增先行指令緩沖棧，IB原先行指令緩沖棧。TR1，TR2，保存PC1和PC中的內(nèi)容，轉(zhuǎn)移不成功，恢復(fù)PC1和PC。53短循環(huán)程序的處理在循環(huán)程序中存在大量的短循環(huán)程序，對于短循環(huán)程序，一般先行指令緩沖棧的效率很低，一種極端的情況是：當(dāng)循環(huán)體只有一條指令，先行緩沖棧失效。指令分析器分析完該指令后就清除指令緩沖棧，重新到主存取指令。短循環(huán)程序的特點(diǎn)：循環(huán)體的長度小于等于先行指

26、令緩沖棧的深度。使得在循環(huán)程序執(zhí)行過程中，整個循環(huán)體能夠始終存放在先行指令緩沖棧不被清除。循環(huán)程序可以多次重復(fù)使用減少訪問主存的次數(shù)。循環(huán)次數(shù)的控制采用計(jì)數(shù)轉(zhuǎn)移指令實(shí)現(xiàn)。因?yàn)橛?jì)數(shù)轉(zhuǎn)移指令可以在指令分析器中直接執(zhí)行，指令分析器分析到這種特殊條件轉(zhuǎn)移指令時不必等到指令執(zhí)行部件形成條件碼，而在指令分析器中就可以判斷循環(huán)出口條件是否滿足?？刂蒲h(huán)的條件轉(zhuǎn)移指令一般是向后轉(zhuǎn)移的指令。54短循環(huán)程序的處理（續(xù)）要在先行控制器中對短循環(huán)程序作特殊處理，必須解決好三個問題：指令分析器如何發(fā)現(xiàn)短循環(huán)程序。如何控制短循環(huán)程序在先行緩沖棧不被清除。如何控制循環(huán)體的執(zhí)行次數(shù)，即處理好循環(huán)體的出口。55短循環(huán)程序的處理

27、（續(xù)）方法一：在指令系統(tǒng)中專門設(shè)置短循環(huán)程序的開門指令和關(guān)門指令，由編譯器在對源程序進(jìn)行編譯時發(fā)現(xiàn)短循環(huán)程序，并在其開頭加上短循環(huán)開門指令，在末尾加上關(guān)門指令。在指令分析器中增加專門的硬件來處理短循環(huán)開關(guān)門指令。設(shè)置專門的短循環(huán)標(biāo)志觸發(fā)器TL。當(dāng)TL=1時表示先行指令緩沖棧內(nèi)是短循行程序而不被清除56短循環(huán)程序的處理（續(xù)）執(zhí)行過程：指令分析器分析到開門指令表示循環(huán)開始，開門指令主要為循環(huán)做預(yù)處理：將短循環(huán)程序的循環(huán)次數(shù)送入指令分析器的循環(huán)次數(shù)計(jì)數(shù)器。設(shè)置短循環(huán)程序在先行指令緩沖棧的起始地址，即入口。置位短循環(huán)標(biāo)志觸發(fā)器TL，表示短循環(huán)程序的開始。先從指令緩沖棧中取出一條指令進(jìn)行分析，如果TL=

28、1，每從指令緩沖棧取一條指令，都不清除該指令。執(zhí)行到關(guān)門指令，循環(huán)體結(jié)束，指令緩沖棧放置了全部該段循環(huán)體的指令。每次循環(huán)都執(zhí)行關(guān)門指令，關(guān)門指令控制循環(huán)體的次數(shù)。57短循環(huán)程序的處理（續(xù)）關(guān)門指令的工作：把循環(huán)計(jì)數(shù)器減1。若循環(huán)計(jì)數(shù)器值大于等于1，現(xiàn)行程序計(jì)數(shù)器指向短循環(huán)程序的入口，準(zhǔn)備下一次循環(huán)。若等于1， 還要把Tl清零。當(dāng)Tl=0時，每分析一條指令就清除該指令，先行緩沖棧恢復(fù)正常功能。若循環(huán)計(jì)數(shù)器值為0，循環(huán)結(jié)束，順序執(zhí)行后續(xù)指令。58短循環(huán)程序的處理（續(xù)）優(yōu)缺點(diǎn)：優(yōu)點(diǎn)是硬件簡單，開關(guān)門指令確定循環(huán)體，指令操作馬即可識別此兩條指令，不需專門的硬件。缺點(diǎn)是增加了程序員的負(fù)擔(dān)。方法二：在有的

29、機(jī)器中為使短循環(huán)程序處理對程序員透明，不采用專門的開關(guān)門指令。而是采用專門的硬件來識別短循環(huán)程序。IBM360/370在指令分析器中有一個向后檢測8條指令的功能，如果條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)地址和轉(zhuǎn)移指令本身地址相差小于0，大于-8，即認(rèn)為遇到短循環(huán)程序。處理方法和開關(guān)方法相同。許多高性能處理機(jī)采用專門的一級指令Cache，把指令Cache和數(shù)據(jù)Cache分開，其中指令可以較長時間保存，有效提高循環(huán)程序的執(zhí)行速度。595.2 流水線處理機(jī)技術(shù)空間并行性：設(shè)置多個獨(dú)立的操作部件時間并行性：分時使用同一個部件的不同部分 5.2.1 流水線工作原理 5.2.2 流水線的分類 5.2.3 線性流水線的性

30、能分析 5.2.4 非線性流水線的調(diào)度60流水線工作原理1.流水寄存器流水線的每一個階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級、流水節(jié)拍等。在每一個流水段的末尾或開頭必須設(shè)置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。加入流水寄存器，會增加指令的執(zhí)行時間。在一般流水線時空圖中不畫出流水寄存器。612.一種指令流水線一般4至12個流水段，8個流水段的稱為超流水線處理機(jī)3.流水線時空圖流水線工作原理（續(xù)）62流水線工作原理（續(xù)）一個浮點(diǎn)加法器流水線的時空圖634.流水線的主要特點(diǎn)只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效率盡量減少因條件分支造成的“斷流”通過編

31、譯技術(shù)提供連續(xù)的相同類型操作每個流水線段都要設(shè)置一個流水寄存器時間開銷：流水線的執(zhí)行時間加長是流水線中需要增加的主要硬件各流水段的時間應(yīng)盡量相等流水線處理機(jī)的基本時鐘周期等于時間最長的流水段的時間長度。流水線需要有“裝入時間”和“排空時間” 流水線工作原理（續(xù)）64流水線的分類1.線性流水線與非線性流水線流水線的各個流水段之間是否有反饋信號線性流水線（Linear Pipelining）：每一個流水段都流過一次，而且僅流過一次非線性流水線（Nonlinear Pipelining）：某些流水段之間有反饋回路或前饋回路。線性流水線能夠用流水線連接圖唯一表示。非線性流水線必須用流水線連接圖和流水線

32、預(yù)約表共同表示。65流水線的分類（續(xù)）2.按照流水線的級別來分 處理機(jī)級流水線，又稱為指令流水線。 例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線66流水線的分類（續(xù)）部件級流水線(操作流水線)如浮點(diǎn)加法器流水線 宏流水線(Macro Pipelining)處理機(jī)之間的流水線稱，每個處理機(jī)對同一個數(shù)據(jù)流的不同部分分別進(jìn)行處理。67流水線的分類（續(xù)）3. 單功能流水線與多功能流水線單功能流水線：只能完成一種固定功能的流水線。Cray-1計(jì)算機(jī)種有12條，YH-1計(jì)算機(jī)有18條Pentium有一條5段定點(diǎn)和一條8段浮點(diǎn)流水線。Pentium有兩條定點(diǎn)和一條浮點(diǎn)指令流水線。多功能流水線：流

33、水線的各段通過不同連接實(shí)現(xiàn)不同功能Texas公司的ASC機(jī)，8段流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加減法、定點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。68流水線的分類（續(xù)）694.靜態(tài)流水線與動態(tài)流水線靜態(tài)流水線：同一段時間內(nèi)，多功能流水線各個功能段只能按照一種方式連接，實(shí)現(xiàn)一種固定的功能。流水線的分類（續(xù)）70動態(tài)流水線：在同一段時間內(nèi)，多功能流水線各段可以按照不同的方式連接，同時執(zhí)行多種功能。流水線的分類（續(xù)）條件：流水線中各個功能部件之間不能發(fā)生沖突。 715.流水線的其他分類方法按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序

34、流水線，按照流水線輸出端流出的任務(wù)和流水線輸入端流入的任務(wù)順序是否相同劃分。亂序流水線又稱為無序流水線、錯序流水線或異步流水線等。流水線的分類（續(xù)）72線性流水線的性能分析主要指標(biāo)：吞吐率、加速比和效率1.吞吐率（Though Put），單位時間內(nèi)流水線所完成的任務(wù)數(shù)量或輸出結(jié)果數(shù)量。流水線吞吐率的最基本公式： 其中：n為任務(wù)數(shù)， k為完成n個任務(wù)所用的時間。各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下，完成n個任務(wù)需要的總時間為： Tk(kn1)t 其中：k 為流水線的段數(shù)，t為時鐘周期。73線性流水線的性能分析（續(xù)）依據(jù)：從輸出端：用k個時鐘周期輸出第一個任務(wù)，其余n-1個周期，每個周期輸出一個任

35、務(wù)，共n-1個任務(wù)。從輸入端：用n個周期輸入n個任務(wù)。另外還有k-1個周期等待流水線排空。74線性流水線的性能分析（續(xù)）Tk= kt + (n-1)t = (k+n-1)t吞吐率為：最大吞吐率為：75線性流水線的性能分析（續(xù)）最大吞吐率和實(shí)際吞吐率的關(guān)系：流水線的實(shí)際吞吐率要小于最大吞吐率。實(shí)際吞吐率和t，流水線短數(shù)k，輸入到流水線的任務(wù)數(shù)n相關(guān)。 只有nk時，才有TPTPmax。76線性流水線的性能分析（續(xù)）各段時間不等，完成n個連續(xù)任務(wù)：吞吐率：最大吞吐率：流水線各段執(zhí)行時間不相等的解決辦法77線性流水線的性能分析（續(xù)）(1)將“瓶頸”部分再細(xì)分（如果可分的話）78線性流水線的性能分析（續(xù)

36、）79線性流水線的性能分析（續(xù)）2.加速比（Speedup） 計(jì)算加速比的基本公式：各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下,加速比：最大加速比：各段時間不等，輸入連續(xù)任務(wù)情況下, 實(shí)際加速比為：80線性流水線的性能分析（續(xù)）是否流水線的段數(shù)越多越好？當(dāng)流水線段數(shù)增加時，需要連續(xù)輸入的任務(wù)數(shù)也必須增加。由于程序中存在數(shù)據(jù)相關(guān)、轉(zhuǎn)移、中斷等情況。任務(wù)數(shù)n受到很大限制。控制的復(fù)雜性，電路的實(shí)現(xiàn)及組裝技術(shù)，實(shí)現(xiàn)的成本等的限制，流水線不可能很多。813.效率（Efficiency）流水線的設(shè)備利用率。計(jì)算流水線效率的一般公式：各流水段時間相等，輸入n個連續(xù)任務(wù)，流水線的效率為：最高效率為：各流水段時間不等

37、，輸入n個連續(xù)任務(wù)，流水線效率為： 線性流水線的性能分析（續(xù)）82各段設(shè)備量或價格不等時，流水線的效率為： 即： 其中，aik，且k。流水線的吞吐率、加速比與效率的關(guān)系：因?yàn)椋阂虼耍篍TP t，Sk E線性流水線的性能分析（續(xù)）834.流水線最佳段數(shù)的選擇采用順序執(zhí)行方式完成一個任務(wù)的時間為t在同等速度的 k 段流水線上執(zhí)行一個任務(wù)的時間為：tkd (d為流水鎖存器的延遲時間)流水線的最大吞吐率為：P=1(tkd)流水線的總價格估計(jì)為：Cab k， 其中：a為功能段身的總價格， b為每個鎖存器的價格 A.G.Larson把流水線的性能價格比PCR定義為：線性流水線的性能分析（續(xù)）84線性流水線

38、的性能分析（續(xù)）求PCR的最大值為：855. 流水線性能分析舉例對于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計(jì)算出流水線的吞吐率、加速比和效率。對于輸入不連續(xù)任務(wù)，或多功能流水線，通常采用基本公式計(jì)算。例：用一條4段浮點(diǎn)加法器流水線求8個浮點(diǎn)數(shù)的和：ZABCDEFGH線性流水線的性能分析（續(xù)）86解： Z(AB)(CD)(EF)(GH)線性流水線的性能分析（續(xù)）87解：線性流水線的性能分析（續(xù)）88線性流水線的性能分析（續(xù)）例，多功能、線形流水線，輸入任務(wù)是不連續(xù)的情況，計(jì)算流水線的吞吐率、加速比和效率。利用Ti-ASC多功能靜態(tài)流水線計(jì)算兩個向量的點(diǎn)積：Z=AB+CD+

39、EF+GH。解，為減少數(shù)據(jù)相關(guān)性充分發(fā)揮流水線的作用，因該先做4個乘法，AB，CD，EF，GH。然后坐兩個加法AB+CD和EF+GH。最后求總的結(jié)果Z。89線性流水線的性能分析（續(xù)）流水線的時空圖：7654321765765765765432143217654321AB+CDEF+GHAB EFCD GHABCDEFGH數(shù)據(jù)1數(shù)據(jù)2輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出ABCDEFGHAB+CDEF+GH時間空間90線性流水線的性能分析（續(xù)）20個周期完成7個運(yùn)算。每個功能能段的延遲時間都為t，則Tk=20 t，n=7。則有流水線吞吐率TP為：如果采用順序執(zhí)行方式，完成一次乘法要用4個t ，

40、完成一次加法要用6個t ，完成全部運(yùn)算要用： t tt。流水線的加速比為：整個流水線共有段，流水線的效率為：91線性流水線的性能分析（續(xù)）整個流水線效率很低：多功能流水線在做某一運(yùn)算時，總有一些功能段是閑置的。靜態(tài)流水線必須等前一種運(yùn)算運(yùn)算全部排除流水線之后才能重新進(jìn)行連接。計(jì)算本身存在數(shù)據(jù)相關(guān)，發(fā)生數(shù)據(jù)相關(guān)時必須等待前一個運(yùn)算結(jié)果產(chǎn)生之后，下一個運(yùn)算才能開始。流水線有裝入和排空部分，當(dāng)輸入到流水線中的任務(wù)不多時，裝入與排空部分所占的比例比較大。92非線性流水線的調(diào)度非線性流水線中存在反饋回路，當(dāng)一個任務(wù)在流水線中流過時，在同一功能段中可能要多次經(jīng)過。不能在一個時鐘周期內(nèi)向流水線輸入一個任務(wù)，

41、否則會發(fā)生在同一個時刻有幾個任務(wù)爭用同一個功能段的情況。稱為功能部件沖突或者流水線沖突。為避免沖突，采用延遲輸入新任務(wù)的方法。間隔幾個周期再輸入新任務(wù)。間隔的周期數(shù)不是一個常數(shù)。而是一串周期變化的數(shù)字。93非線性流水線的調(diào)度（續(xù)）非線性流水線調(diào)度的任務(wù)是要找出一個最小的循環(huán)周期，按照這周期向流水線輸入新任務(wù)，流水線的各個功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。1.非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預(yù)約表94非線性流水線的調(diào)度（續(xù)）例如：非線形流水線的連接圖和預(yù)約表95非線性流水線的調(diào)度（續(xù)）四個功能段

42、組成非線性流水線。與線性流水線相同地方：從第一個功能段S1到最后一個功能段S4的單方向傳輸線。不同的地方：有兩條反饋線和一條前饋線。輸出端經(jīng)常不在最后一個功能段，可能從中間的任意一個功能段輸出。96非線性流水線的調(diào)度（續(xù)）預(yù)約表：預(yù)約表的橫坐標(biāo)表示流水線工作的時鐘周期，縱坐標(biāo)表示流水線的功能段。中間的X表示該功能段在該時鐘周期處于工作狀態(tài)。即有任務(wù)在該時鐘段通過該功能段。空白表示該時鐘周期該功能段不工作。一行可以有多個X，表示一個任務(wù)在不同時鐘周期重復(fù)使用同一個功能段。一列可以有多個X，指同一個時鐘周期多個功能段被使用。預(yù)約表的行數(shù)是非線性流水線的段數(shù)。列數(shù)是指一個任務(wù)從進(jìn)入流水線到從流水線輸

43、出經(jīng)過的時鐘周期數(shù)。又稱為功能求值時間或裝入時間。97非線性流水線的調(diào)度（續(xù)）一張預(yù)約表可能與多個流水線連接圖相對應(yīng)原因：在預(yù)約表的同一列中可能有多個X，即該時鐘周期有多個功能段輸出，下一功能段的輸入有多個來源，從而應(yīng)對有多個連接圖。98非線性流水線的調(diào)度（續(xù)）一個流水線連接圖對應(yīng)與多張預(yù)約表原因：非線性流水線的有些功能段可能有多個輸出端，也有些功能段有多個輸入端，輸出端和輸入端之間連接的先后次序形成多張預(yù)約表。99非線性流水線的調(diào)度（續(xù)）2.非線性流水線的沖突啟動距離：連續(xù)輸入兩個任務(wù)之間的時間間隔，又稱等待時間。流水線沖突：以某啟動距離連續(xù)向一條非線性流水線輸入任務(wù)，可能會存在幾個任務(wù)爭用

44、同一個流水段。100非線性流水線的調(diào)度（續(xù)）7/29/2022101非線性流水線的調(diào)度（續(xù)）引起非線性流水線功能段沖突的啟動距離稱為禁止啟動距離。有些啟動距離在非線性流水線的所有功能段，在任何時間都不會發(fā)生沖突，如前表的（5），（1，7）。不發(fā)生沖突的啟動距離不一定僅僅是一個常數(shù)，在一般情況下是一個循環(huán)數(shù)列。稱為非線性流水線的啟動循環(huán)。只有一個啟動距離的啟動循環(huán)又稱為恒定循環(huán)。102非線性流水線的調(diào)度（續(xù)）要正確的調(diào)度一條非線性流水線，首先需要找到流水線的所有禁止啟動距離。把所有禁止啟動距離組合在一起形成數(shù)列，稱為非線性流水線的禁止向量。計(jì)算禁止向量：把預(yù)約表中每一行中任意兩個X之間的距離算出

45、來，去掉重復(fù)的，這些數(shù)組成數(shù)列就是該非線性流水線的禁止向量。把一個啟動循環(huán)內(nèi)的所有啟動距離相加再除以這個啟動循環(huán)內(nèi)的啟動距離個數(shù)就得到該啟動循環(huán)的平均啟動距離。1033.無沖突調(diào)度方法主要目標(biāo)：找出最小平均啟動距離的啟動循環(huán)。由E.S.Davidson及其學(xué)生于1971年提出禁止向量：預(yù)約表中每一行任意兩個“”之間距離的集合。上例中為（3，4，6）沖突向量：用C（CmCm-1C2C1）表示，m位的二進(jìn)制數(shù)。 其中：m是禁止向量中的最大值。 如果i在禁止向量中，則Ci1，否則Ci0。上例中C(101100)非線性流水線的調(diào)度（續(xù)）104非線性流水線的調(diào)度（續(xù)）由沖突向量可以構(gòu)造狀態(tài)圖。將沖突向量

46、C作為初始沖突向量送入m位的右移邏輯移位器。移出為0，移位器內(nèi)的值和初始沖突向量做按位或運(yùn)算。得到一個新的沖突向量。移出為1，不做任何處理。移位器繼續(xù)右移。中間形成的新的沖突向量，也按上述方法處理。在初始向量和新的沖突向量之間用箭頭連接，并標(biāo)注右移次數(shù)。表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系，向量重復(fù)時合并到一起。105非線性流水線的調(diào)度（續(xù)）當(dāng)初始沖突向量確定后，狀態(tài)圖就是唯一的。不同的預(yù)約表可能產(chǎn)生相同的初始沖突向量，因而不同的預(yù)約表也可能有相同的狀態(tài)圖。從預(yù)約表可以畫出狀態(tài)圖，沖狀態(tài)圖不能獲得預(yù)約表。當(dāng)啟動距離大于或等于m+1時，流水線的任何一個功能段在任何時鐘周期都不會發(fā)生沖突，但流水線的吞吐率、

47、加速比、效率都很差。106例：一條4功能段的非線性流水線，每個功能段的延遲時間都相等，它的預(yù)約表如下： (1)寫出流水線的禁止向量和初始沖突向量。 (2)畫出調(diào)度流水線的狀態(tài)圖。 (3)求最小啟動循環(huán)和最小平均啟動距離。 (4)求平均啟動距離最小的恒定循環(huán)。非線性流水線的調(diào)度（續(xù)）107解：(1)禁止向量為：(2，4，6) 初始沖突向量：S = 101010(2)構(gòu)造狀態(tài)圖 S邏輯右移2、4、6位時，不作任何處理， 邏輯右移1、3、5和大于等于7時： S右移1位之后：010101101010111111， S右移3位之后：000101101010101111， S右移5位之后：00000110

48、1010101011， S右移7位或大于7位后：按位或就還原到它本身。非線性流水線的調(diào)度（續(xù)）108非線性流水線的調(diào)度（續(xù)）新沖突向量再處理：101111右移5位之后：000001101010101011，101011右移3位之后：000101101010101111，101011右移5位之后：000001101010101011。109簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。在一個狀態(tài)圖中，簡單循環(huán)的個數(shù)是有限的。(3)最小的啟動循環(huán)為（1，7）和（3，5）, 平均啟動距離為 4。(4)啟動距離最小的恒定循環(huán)為（5）非線性流水線的調(diào)度（續(xù)）110非線性流水線的調(diào)度（續(xù)）111非線

49、性流水線的調(diào)度（續(xù)）1124.優(yōu)化調(diào)度方法采用最小啟動循環(huán)啟動非線性流水線時，許多功能段還有空閑，即預(yù)約表中還有空白格子。最小啟動循環(huán)實(shí)際上不能使非線性流水線充分發(fā)揮效率。L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍：最小平均啟動距離的下限是預(yù)約表中任意一行里“”的最多個數(shù)。即同一任務(wù)通過流水線中任意一個功能段的次數(shù)。最小平均啟動距離小于等于狀態(tài)圖中任意一個簡單循環(huán)的平均啟動距離。最小平均啟動距離的上限是沖突向量中1的個數(shù)再加上1。1992年，L.E.Shar又證明了上述限制范圍。最有用的是第1條。預(yù)約表中“”最多的行一定是瓶頸流水段。要使整個流水線最大發(fā)揮作用，必須使瓶頸

50、功能段不間斷工作。不得空閑。非線性流水線的調(diào)度（續(xù)）113非線性流水線的調(diào)度（續(xù)）采用預(yù)留算法來調(diào)度非線性流水線，可以達(dá)到最優(yōu)調(diào)度。確定流水線的最小平均距離，最小平均距離等于預(yù)約表中任意一行中X的最大個數(shù)。或者同一個任務(wù)流過任意功能段的最多次數(shù)。確定最小啟動循環(huán)，相對于同一個最小平均啟動距離可能有多個最小啟動循環(huán)。其中有一個且只有一個啟動距離都相等的恒定循環(huán)。選用該恒定循環(huán)為最小啟動循環(huán)。結(jié)合流水線預(yù)約表和連接圖，采用預(yù)留算法，通過插入非計(jì)算延遲功能段實(shí)現(xiàn)最小啟動循環(huán)。114對于前例的預(yù)約表，在同一行中“”最多的為2個，因此，最小平均距離可以達(dá)到2。最小啟動循環(huán)可以是(2)、(1,3)、(1,

51、1,4)、(1,2,3)、。現(xiàn)取恒定循環(huán)(2)。每一行中與第1個“”的距離為2的倍數(shù)的位置都要預(yù)留出來。 S3行的第2個“”從周期5延遲到周期6。為此， S2行的第2個“”從周期6延遲到周期7； S1行的第2個“”從周期7延遲到周期8。實(shí)際上，只要在流水段S4的輸出端到流水段S3的輸入端中間插入一個非計(jì)算延遲D1。非線性流水線的調(diào)度（續(xù)）115非線性流水線的調(diào)度（續(xù)）116非線性流水線的調(diào)度（續(xù)）117在非線性流水線中，“”最多的流水段一定是“瓶頸“流水段。實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使“瓶頸”流水段處于忙碌狀態(tài)，沒有空閑周期。最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率、加速比和效率達(dá)到最優(yōu)。非線性流水線

52、的調(diào)度（續(xù)）118局部相關(guān)在流水線處理機(jī)中由于處理的指令條數(shù)很多，發(fā)生相關(guān)的可能性及其造成的影響將更嚴(yán)重。按照對程序執(zhí)行過程可能造成的影響劃分：可以把相關(guān)分為局部相關(guān)和全局相關(guān)兩類。如圖，程序中一條分支指令把程序劃分為三個部分，每部分內(nèi)部不再有分支操作，這種部分稱為基本塊。 B0B1B2119局部相關(guān)（續(xù)）同一個基本塊內(nèi)部的相關(guān)稱為局部相關(guān)（lacal correlation）在基本塊之間的相關(guān)成為全局相關(guān)（）。引起全局相關(guān)的除了分支操作還有中斷。局部相關(guān)對程序執(zhí)行影響較小，僅限于相關(guān)指令臨近的幾條指令。全局相關(guān)影響很大，影響到整個程序的執(zhí)行方向。120局部相關(guān)（續(xù)）促使流水線充分發(fā)揮作用，需

53、要軟硬件結(jié)合。軟件編譯的目標(biāo)代碼要適合流水線結(jié)構(gòu)，盡量把相關(guān)數(shù)據(jù)和相關(guān)控制的指令安排得遠(yuǎn)一些。把相同操作盡量安排在一起。在硬件方面解決好存儲系統(tǒng)的頻帶問題，能夠?yàn)榱魉€提高足夠的指令和數(shù)據(jù)。解決好流水線的局部相關(guān)和全局相關(guān)。局部相關(guān)包括：先寫后讀數(shù)據(jù)相關(guān)，先讀后寫數(shù)據(jù)相關(guān)，寫寫相關(guān)三種。121順序流動與亂序流動1.順序流動方式：任務(wù)按順序流入流水線,也按順序流出流水線把如下一段程序輸入到這條流水線中： k： R0（R1） k+1： k+2： R2（R0）（R3） k+3： k+4： k+5： 122指令k+2無法繼續(xù)執(zhí)行，要在功能段S2中等待。后續(xù)的指令k+4、k+5、等也不能進(jìn)入流水線。功能

54、段S3、S4、S5將逐漸空閑。缺點(diǎn)：吞吐率和效率降低優(yōu)點(diǎn)：流水線的控制邏輯比較簡單順序流動與亂序流動（續(xù)）123順序流動與亂序流動（續(xù)）流水線“斷流”，有些功能段“空閑”1242.亂序(Out of order)流動方式：指令流出流水線的順序與流入流水線的順序不同。又稱為錯序流動方式、無序流動方式、異步流動方式等。順序流動與亂序流動（續(xù)）125亂序流動中的數(shù)據(jù)相關(guān)在亂序流動方式中，可能發(fā)生三種數(shù)據(jù)相關(guān) 寫寫相關(guān) k：LOAD F1, A ;F1（A） 寫讀相關(guān) k+1：FADD F2, F1 ;F2（F2）+（F1） k+2：FMUL F1, F3 ;F1（F1）（F3） k+3：STORE

55、F1, B ;B（F1） 讀寫相關(guān)(1)寫讀相關(guān)：指令k與指令k+1之間關(guān)于F1的相關(guān)，又稱為數(shù)據(jù)相關(guān)、先寫后讀相關(guān)、流相關(guān)、WR相關(guān)、RAW相關(guān)等。126(2)讀寫相關(guān)：指令k+1與指令k+2之間關(guān)于F1的相關(guān)，變量名相關(guān)、先讀后寫相關(guān)、反相關(guān)、RW相關(guān)、WAR相關(guān)等。(3)寫寫相關(guān)：指令k與指令k+2左邊的F1之間的相關(guān)關(guān)系稱為：輸出相關(guān)、寫寫相關(guān)、WW相關(guān)、WAW相關(guān)或?qū)懞笤賹懴嚓P(guān)等。有時把相關(guān)稱為“冒險”(hazard)、“竟?fàn)帯?(competition)等。在程序執(zhí)行過程中，只有避免相關(guān)，執(zhí)行結(jié)果才是正確的。亂序流動中的數(shù)據(jù)相關(guān)（續(xù)）127亂序流動中的數(shù)據(jù)相關(guān)（續(xù)）測試先寫后讀數(shù)據(jù)

56、相關(guān)的方法：在流水線的讀書操作功能段設(shè)置一個相聯(lián)比較器，在指令讀操作數(shù)之前，把源操作數(shù)地址和已經(jīng)在流水線中的從讀數(shù)功能段到寫結(jié)果功能段之間的所有指令的目標(biāo)地址進(jìn)行比較，發(fā)現(xiàn)地址相等，則表明發(fā)生了先寫后讀相關(guān)。測試先讀后寫，寫寫相關(guān)的方法：在流水線的寫功能段設(shè)置相聯(lián)比較器，把自己的目標(biāo)操作數(shù)地址分別與已經(jīng)進(jìn)入流水線的指令序號比自己小的源操作數(shù)地址和目標(biāo)操作數(shù)地址進(jìn)行比較。發(fā)現(xiàn)源操作數(shù)地址相等，發(fā)生先讀后寫相關(guān)，發(fā)現(xiàn)目標(biāo)操作數(shù)地址相等，發(fā)生了寫寫相關(guān)。128亂序流動中的數(shù)據(jù)相關(guān)（續(xù)）三種數(shù)據(jù)相關(guān)可以用下列關(guān)系式來表示：對于寫讀相關(guān) D(i) S(j) 對于讀寫相關(guān) S(i) D(j) 對于寫寫相關(guān)

57、 D(i) D(j) 129亂序流動中的數(shù)據(jù)相關(guān)（續(xù)）在流水線中避免數(shù)據(jù)相關(guān)的方法分為兩類：延遲執(zhí)行。優(yōu)點(diǎn)是流水線的控制簡單，缺點(diǎn)是流水線的吞吐率和效率很低。建立專用路徑。分散控制的公共數(shù)據(jù)總線法。集中控制的CDC記分牌法。流水線的吞吐率和效率有比較大的提高。在流水線中建立專用數(shù)據(jù)路徑是高性能處理機(jī)的通用方式。130數(shù)據(jù)重定向方法1.三種數(shù)據(jù)相關(guān)的重定向重定向之前，j只能在i之后執(zhí)行。重定向之后，可以做到：(1)寫讀相關(guān)，j與i可以同時執(zhí)行。 即專用數(shù)據(jù)通路。(2)寫寫相關(guān)，先后順序無關(guān)。(3)讀寫相關(guān)，先后順序無關(guān)。后兩種情況又稱為“變量換名技術(shù)”131數(shù)據(jù)重定向方法（續(xù)）1322.變量換名

58、技術(shù)用來自動消除讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)。規(guī)則：一個變量只允許定值一次。在三種數(shù)據(jù)相關(guān)中，實(shí)際上只有寫讀數(shù)據(jù)相關(guān)必須依靠硬件、或采用軟硬件結(jié)合的方法來解決。解決方法：推后處理或?qū)Ｓ脭?shù)據(jù)通路。在上面的數(shù)據(jù)重定向圖中，把B換成了B，并在以后的都引用B讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就不存在了。數(shù)據(jù)重定向方法（續(xù)）133數(shù)據(jù)重定向方法（續(xù)）一個實(shí)際例子：Loop: LD F0, 0(R1) ADD F0, F2 SD 0(R1), F0 LD F0, -8(R1) ADD F0, F2 SD -8(R1), F0 LD F0, -16(R1) ADD F0, F2 SD -16(R1), F0 LD F

59、0, -24(R1) ADD F0, F2 SD -24(R1), F0 SUBI R1, R1, #32 BNEZ R1, LoopLoop: LD F0, 0(R1) LD F4, -8(R1) LD F6, -16(R1) LD F8, -24(R1) ADD F0，F(xiàn)2 ADD F4，F(xiàn)2 ADD F6，F(xiàn)2 ADD F8，F(xiàn)2 SD 0(R1), F0 SD -8(R1), F4 SUBI R1, R1, #32 SD -16(R1), F6 BNEZ R1, Loop SD -24(R1), F8134數(shù)據(jù)重定向方法（續(xù)）3.一個簡單的程序： k： LOAD F1, A k+1：

60、FADD F1, F2 k+2： FMUL F1, F3 k+3： STORE F1, B135專門設(shè)置：AFADD、FMULB、FADDFMUL三條專用路徑。撤消：F1FADD、F1FMUL、FADDF1 、AF1的路徑。數(shù)據(jù)重定向方法（續(xù)）136Tomasulo動態(tài)調(diào)度算法實(shí)用的動態(tài)調(diào)度算法主要有兩種:(1)集中控制：CDC計(jì)分牌(scorebord)算法.最先在CDC 6600大型機(jī)中采用。(2)分散控制：Tomasulo算法, 公共數(shù)據(jù)總線法，令牌法等。最早在大型機(jī)IBM 360/91的浮點(diǎn)處理部件中被采用。以上面的一段程序?yàn)槔f明Tomasulo算法k： LOAD F1, Ak+1：