計(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ù)就是縮短解釋指令的時(shí)間，提高處理機(jī)指令的執(zhí)行速度：提高處理機(jī)的工作主頻。5、60年代主要采用這種技術(shù)，每3、4年處理機(jī)的速度要提高一個(gè)數(shù)量級(jí)。采用更好的算法和設(shè)計(jì)更好的功能部件，如采用RISC等。多條指令并行執(zhí)行。指令級(jí)的并行技術(shù)。流水線技術(shù)。處理機(jī)中設(shè)置多個(gè)獨(dú)立的功能部件，如浮點(diǎn)運(yùn)算器，定點(diǎn)運(yùn)算器，訪存部件等

2、。超長(zhǎng)指令技術(shù)。35.1 先行控制技術(shù)先行控制技術(shù)的關(guān)鍵是采用緩沖技術(shù)和預(yù)處理技術(shù)，以及兩者都采用，通過(guò)對(duì)指令流和數(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í)行可以分為多個(gè)階段，具體分法視處理機(jī)而定，一般可以分為三個(gè)階段：取指令是指按照指令計(jì)數(shù)器的內(nèi)容訪問(wèn)主存，取出一條指令送到指令寄存器。分析指令是指對(duì)指令的操作碼進(jìn)行譯碼，按照給定的尋址方式和地址字段內(nèi)容形成操作數(shù)地

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

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

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

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

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

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

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

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

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

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

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

14、DI8，DCDR4，DW2。 DI12，DCDR6，DW2。緩沖深度的設(shè)計(jì)方法（續(xù)）29數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)：在執(zhí)行本條指令的過(guò)程中，如果用到的指令、操作數(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)的存儲(chǔ)單元。設(shè)置專用路徑。不必等到所需要的數(shù)據(jù)寫入到相關(guān)存儲(chǔ)單元，而是經(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條指令還沒(méi)有把執(zhí)行結(jié)果寫到主存之前，取出的第n+1條指令顯然是錯(cuò)誤的。在k個(gè)流水段的流水線處理機(jī)中，第n條指令要修改從第n+1到第n+ k 指令中的任意一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤。數(shù)據(jù)相關(guān)（續(xù)）31在采用先行控制方式的處理機(jī)中，如果執(zhí)行部件正在執(zhí)行第n條指令，與下述情況之一發(fā)生相關(guān)，都可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤。存放在先行操作棧中的指令正在指令分析器中分析的指令已經(jīng)預(yù)取到先行指令緩沖棧中的指令指令執(zhí)行結(jié)果還在后行緩沖棧中的指令更嚴(yán)重的是：有些分支指令，可能已經(jīng)在指令分析器中執(zhí)行完成。 數(shù)據(jù)相關(guān)（續(xù)）32解決指令相關(guān)的根本辦法是： 在程序執(zhí)行過(guò)程中不允許修改指令?，F(xiàn)代程序設(shè)計(jì)方

16、法要求程序具有再入性，可以被遞歸調(diào)用等，也要求不修改指令。在IBM370系列機(jī)中，用“執(zhí)行指令”來(lái)解決：在程序執(zhí)行過(guò)程中既能夠修改指令，程序又具有再入性?！皥?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é)果寫到通用寄存器，而不寫到主存對(duì)于訪問(wèn)主存

17、儲(chǔ)器的請(qǐng)求，寫結(jié)果的優(yōu)先級(jí)高于讀操作數(shù)。數(shù)據(jù)相關(guān)（續(xù)）34有先行操作棧處理機(jī)中，分析指令、已經(jīng)執(zhí)行指令需要進(jìn)入后行寫數(shù)操作棧向主存寫回運(yùn)算結(jié)果的指令之間可能相隔很多條指令。已經(jīng)進(jìn)入先行操作棧的任何一條指令在向主存申請(qǐng)讀數(shù)時(shí)都可能與正在執(zhí)行部件中執(zhí)行的指令、正在后行寫數(shù)棧中等待寫結(jié)果到主存的指令，甚至還在先行操作棧中的指令發(fā)生主存操作數(shù)相關(guān)。解決辦法：對(duì)于剛進(jìn)入先行操作棧中的指令在向主存讀數(shù)之前，首先把訪問(wèn)主存的地址與后行寫數(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í)行合在一個(gè)節(jié)拍。從數(shù)據(jù)從通用寄存器讀出，在運(yùn)算器中完成運(yùn)算，結(jié)果寫回通用寄存器的整個(gè)回路中，只有通用寄存器是時(shí)序邏輯。當(dāng)發(fā)生下述情況時(shí)，不能采用這種方法：當(dāng)寄存器個(gè)數(shù)多時(shí)，讀寫寄存器的時(shí)間長(zhǎng)。當(dāng)功能部件數(shù)量多時(shí)，寄存器的讀寫端口多。當(dāng)功能部件的執(zhí)行時(shí)間比較長(zhǎng)，或要求指令的執(zhí)行時(shí)間

19、短時(shí) 。數(shù)據(jù)相關(guān)（續(xù)）37方法二：建立相關(guān)專用通路(ByPass)由于發(fā)生寄存器數(shù)據(jù)相關(guān)的情況很普遍，一般計(jì)算機(jī)系統(tǒng)都采用專用數(shù)據(jù)通路。把讀通用寄存器、執(zhí)行操作和寫結(jié)果分為3個(gè)周期，或2個(gè)周期。采用專用數(shù)據(jù)通路能夠縮短1至2個(gè)周期。數(shù)據(jù)相關(guān)（續(xù)）38變址相關(guān)：在采用變址尋址方式的處理機(jī)中，由于變址量放在寄存器中，因此，可能發(fā)生與通用寄存器數(shù)據(jù)相關(guān)類似變址相關(guān).4. LOAD相關(guān) LOAD操作的執(zhí)行時(shí)間可能比較長(zhǎng) 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í)行時(shí)間不確定，不能根本解決問(wèn)題。方法二：由硬件自動(dòng)插入空操作，直到LOAD操作完成。在單條流水線處理機(jī)中，也可以停止節(jié)拍發(fā)生器，直到數(shù)據(jù)從存儲(chǔ)器中讀出為止。數(shù)據(jù)相關(guān)（續(xù)）40控制相關(guān)因程序的執(zhí)行方向可能被改變而引起的相關(guān)，也稱為全局相關(guān)。主要包括：無(wú)條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、復(fù)合條件轉(zhuǎn)移、中斷等。1. 無(wú)條件轉(zhuǎn)移在流水線處理機(jī)中，無(wú)條件轉(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在先行指令緩沖棧中，只要作廢先行指令緩沖棧中的部分指令。無(wú)條件轉(zhuǎn)移指令一般對(duì)指令執(zhí)行部件的工作不會(huì)造成影響。為進(jìn)一步減少無(wú)條件轉(zhuǎn)移指令造成的影響，在先行指令緩沖棧的入口處增設(shè)一個(gè)專門處理無(wú)條件轉(zhuǎn)移指令的指令分析器控制相關(guān)(續(xù)) 422.一般條件轉(zhuǎn)移 k： ;置條件碼CC k+1：JMP(CC) L ;如果CC為真轉(zhuǎn)向L L： 當(dāng)條件碼是上一條指令產(chǎn)生時(shí)，相關(guān)最嚴(yán)重控制相關(guān)(續(xù)) 43無(wú)論轉(zhuǎn)移是否成功，條轉(zhuǎn)移指令都在指令分析階段就已經(jīng)執(zhí)行完成。無(wú)論轉(zhuǎn)移不成功或不成功，指令分析器要停頓一段

22、時(shí)間，等待條件碼產(chǎn)生?？刂葡嚓P(guān)(續(xù)) 44如果轉(zhuǎn)移成功：指令L已經(jīng)在先行指令緩沖棧，指令分析器接著“分析L”，如果指令L不在先行指令緩沖棧，指令分析器要等待一個(gè)周期。轉(zhuǎn)移不成功，對(duì)程序執(zhí)行影響不大，當(dāng)轉(zhuǎn)移成功時(shí)，不僅指令執(zhí)行過(guò)程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。在采用流水線方式的處理機(jī)中，要通過(guò)軟件與硬件的多種手段來(lái)近可能地降低轉(zhuǎn)移成功的概率，減少轉(zhuǎn)移成功造成的影響。控制相關(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)移成功造成的影響?？刂葡嚓P(guān)(續(xù)) 46控制相關(guān)(續(xù)) 47轉(zhuǎn)移預(yù)測(cè)技術(shù)轉(zhuǎn)移預(yù)測(cè)技術(shù)包括：靜態(tài)分支預(yù)測(cè)：在程序執(zhí)行過(guò)程中轉(zhuǎn)移預(yù)測(cè)方向不能改變動(dòng)態(tài)分支預(yù)測(cè)： 在程序執(zhí)行過(guò)程中能夠改變轉(zhuǎn)移預(yù)測(cè)方向48靜態(tài)分支預(yù)測(cè)技術(shù)1.軟件“猜測(cè)法”目標(biāo)：通過(guò)編譯器盡量降低轉(zhuǎn)移成功的概率。例如：對(duì)于循環(huán)程序，普通編譯器生成的目標(biāo)代碼，轉(zhuǎn)移成功的概率很高，不成功的只有一次。這種編譯結(jié)果對(duì)流水線極為不利。優(yōu)點(diǎn)：不需要改變先行控制器的硬件結(jié)構(gòu)，只需適當(dāng)修改編譯器就能夠大幅度降低條件轉(zhuǎn)移指令對(duì)先行控制器產(chǎn)生的影響。其最終目標(biāo)是提高處理機(jī)執(zhí)行程序

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

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

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

27、（續(xù)）方法一：在指令系統(tǒng)中專門設(shè)置短循環(huán)程序的開(kāi)門指令和關(guān)門指令，由編譯器在對(duì)源程序進(jìn)行編譯時(shí)發(fā)現(xiàn)短循環(huán)程序，并在其開(kāi)頭加上短循環(huán)開(kāi)門指令，在末尾加上關(guān)門指令。在指令分析器中增加專門的硬件來(lái)處理短循環(huán)開(kāi)關(guān)門指令。設(shè)置專門的短循環(huán)標(biāo)志觸發(fā)器TL。當(dāng)TL=1時(shí)表示先行指令緩沖棧內(nèi)是短循行程序而不被清除56短循環(huán)程序的處理（續(xù)）執(zhí)行過(guò)程：指令分析器分析到開(kāi)門指令表示循環(huán)開(kāi)始，開(kāi)門指令主要為循環(huán)做預(yù)處理：將短循環(huán)程序的循環(huán)次數(shù)送入指令分析器的循環(huán)次數(shù)計(jì)數(shù)器。設(shè)置短循環(huán)程序在先行指令緩沖棧的起始地址，即入口。置位短循環(huán)標(biāo)志觸發(fā)器TL，表示短循環(huán)程序的開(kāi)始。先從指令緩沖棧中取出一條指令進(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時(shí)，每分析一條指令就清除該指令，先行緩沖?；謴?fù)正常功能。若循環(huán)計(jì)數(shù)器值為0，循環(huán)結(jié)束，順序執(zhí)行后續(xù)指令。58短循環(huán)程序的處理（續(xù)）優(yōu)缺點(diǎn)：優(yōu)點(diǎn)是硬件簡(jiǎn)單，開(kāi)關(guān)門指令確定循環(huán)體，指令操作馬即可識(shí)別此兩條指令，不需專門的硬件。缺點(diǎn)是增加了程序員的負(fù)擔(dān)。方法二：在有的

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

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

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

32、預(yù)約表共同表示。65流水線的分類（續(xù)）2.按照流水線的級(jí)別來(lái)分 處理機(jī)級(jí)流水線，又稱為指令流水線。 例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線66流水線的分類（續(xù)）部件級(jí)流水線(操作流水線)如浮點(diǎn)加法器流水線 宏流水線(Macro Pipelining)處理機(jī)之間的流水線稱，每個(gè)處理機(jī)對(duì)同一個(gè)數(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、水線的各段通過(guò)不同連接實(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)流水線與動(dòng)態(tài)流水線靜態(tài)流水線：同一段時(shí)間內(nèi)，多功能流水線各個(gè)功能段只能按照一種方式連接，實(shí)現(xiàn)一種固定的功能。流水線的分類（續(xù)）70動(dòng)態(tài)流水線：在同一段時(shí)間內(nèi)，多功能流水線各段可以按照不同的方式連接，同時(shí)執(zhí)行多種功能。流水線的分類（續(xù)）條件：流水線中各個(gè)功能部件之間不能發(fā)生沖突。 715.流水線的其他分類方法按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序

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

35、務(wù)，共n-1個(gè)任務(wù)。從輸入端：用n個(gè)周期輸入n個(gè)任務(wù)。另外還有k-1個(gè)周期等待流水線排空。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時(shí)，才有TPTPmax。76線性流水線的性能分析（續(xù)）各段時(shí)間不等，完成n個(gè)連續(xù)任務(wù)：吞吐率：最大吞吐率：流水線各段執(zhí)行時(shí)間不相等的解決辦法77線性流水線的性能分析（續(xù)）(1)將“瓶頸”部分再細(xì)分（如果可分的話）78線性流水線的性能分析（續(xù)

36、）79線性流水線的性能分析（續(xù)）2.加速比（Speedup） 計(jì)算加速比的基本公式：各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下,加速比：最大加速比：各段時(shí)間不等，輸入連續(xù)任務(wù)情況下, 實(shí)際加速比為：80線性流水線的性能分析（續(xù)）是否流水線的段數(shù)越多越好？當(dāng)流水線段數(shù)增加時(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ì)算流水線效率的一般公式：各流水段時(shí)間相等，輸入n個(gè)連續(xù)任務(wù)，流水線的效率為：最高效率為：各流水段時(shí)間不等

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

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

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

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

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

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

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

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

45、來(lái)，去掉重復(fù)的，這些數(shù)組成數(shù)列就是該非線性流水線的禁止向量。把一個(gè)啟動(dòng)循環(huán)內(nèi)的所有啟動(dòng)距離相加再除以這個(gè)啟動(dòng)循環(huán)內(nèi)的啟動(dòng)距離個(gè)數(shù)就得到該啟動(dòng)循環(huán)的平均啟動(dòng)距離。1033.無(wú)沖突調(diào)度方法主要目標(biāo)：找出最小平均啟動(dòng)距離的啟動(dòng)循環(huán)。由E.S.Davidson及其學(xué)生于1971年提出禁止向量：預(yù)約表中每一行任意兩個(gè)“”之間距離的集合。上例中為（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)算。得到一個(gè)新的沖突向量。移出為1，不做任何處理。移位器繼續(xù)右移。中間形成的新的沖突向量，也按上述方法處理。在初始向量和新的沖突向量之間用箭頭連接，并標(biāo)注右移次數(shù)。表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系，向量重復(fù)時(shí)合并到一起。105非線性流水線的調(diào)度（續(xù)）當(dāng)初始沖突向量確定后，狀態(tài)圖就是唯一的。不同的預(yù)約表可能產(chǎn)生相同的初始沖突向量，因而不同的預(yù)約表也可能有相同的狀態(tài)圖。從預(yù)約表可以畫出狀態(tài)圖，沖狀態(tài)圖不能獲得預(yù)約表。當(dāng)啟動(dòng)距離大于或等于m+1時(shí)，流水線的任何一個(gè)功能段在任何時(shí)鐘周期都不會(huì)發(fā)生沖突，但流水線的吞吐率、

47、加速比、效率都很差。106例：一條4功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等，它的預(yù)約表如下： (1)寫出流水線的禁止向量和初始沖突向量。 (2)畫出調(diào)度流水線的狀態(tài)圖。 (3)求最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 (4)求平均啟動(dòng)距離最小的恒定循環(huán)。非線性流水線的調(diào)度（續(xù)）107解：(1)禁止向量為：(2，4，6) 初始沖突向量：S = 101010(2)構(gòu)造狀態(tài)圖 S邏輯右移2、4、6位時(shí)，不作任何處理， 邏輯右移1、3、5和大于等于7時(shí)： 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簡(jiǎn)單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過(guò)一次的啟動(dòng)循環(huán)。在一個(gè)狀態(tài)圖中，簡(jiǎn)單循環(huán)的個(gè)數(shù)是有限的。(3)最小的啟動(dòng)循環(huán)為（1，7）和（3，5）, 平均啟動(dòng)距離為 4。(4)啟動(dòng)距離最小的恒定循環(huán)為（5）非線性流水線的調(diào)度（續(xù)）110非線性流水線的調(diào)度（續(xù)）111非線

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

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

51、1,4)、(1,2,3)、?，F(xiàn)取恒定循環(huán)(2)。每一行中與第1個(gè)“”的距離為2的倍數(shù)的位置都要預(yù)留出來(lái)。 S3行的第2個(gè)“”從周期5延遲到周期6。為此， S2行的第2個(gè)“”從周期6延遲到周期7； S1行的第2個(gè)“”從周期7延遲到周期8。實(shí)際上，只要在流水段S4的輸出端到流水段S3的輸入端中間插入一個(gè)非計(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)，沒(méi)有空閑周期。最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率、加速比和效率達(dá)到最優(yōu)。非線性流水線

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

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

54、段S3、S4、S5將逐漸空閑。缺點(diǎn)：吞吐率和效率降低優(yōu)點(diǎn)：流水線的控制邏輯比較簡(jiǎn)單順序流動(dòng)與亂序流動(dòng)（續(xù)）123順序流動(dòng)與亂序流動(dòng)（續(xù)）流水線“斷流”，有些功能段“空閑”1242.亂序(Out of order)流動(dòng)方式：指令流出流水線的順序與流入流水線的順序不同。又稱為錯(cuò)序流動(dòng)方式、無(wú)序流動(dòng)方式、異步流動(dòng)方式等。順序流動(dòng)與亂序流動(dòng)（續(xù)）125亂序流動(dòng)中的數(shù)據(jù)相關(guān)在亂序流動(dòng)方式中，可能發(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)等。有時(shí)把相關(guān)稱為“冒險(xiǎn)”(hazard)、“竟?fàn)帯?(competition)等。在程序執(zhí)行過(guò)程中，只有避免相關(guān)，執(zhí)行結(jié)果才是正確的。亂序流動(dòng)中的數(shù)據(jù)相關(guān)（續(xù)）127亂序流動(dòng)中的數(shù)據(jù)相關(guān)（續(xù)）測(cè)試先寫后讀數(shù)據(jù)

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

57、 D(i) D(j) 129亂序流動(dòng)中的數(shù)據(jù)相關(guān)（續(xù)）在流水線中避免數(shù)據(jù)相關(guān)的方法分為兩類：延遲執(zhí)行。優(yōu)點(diǎn)是流水線的控制簡(jiǎ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可以同時(shí)執(zhí)行。 即專用數(shù)據(jù)通路。(2)寫寫相關(guān)，先后順序無(wú)關(guān)。(3)讀寫相關(guān)，先后順序無(wú)關(guān)。后兩種情況又稱為“變量換名技術(shù)”131數(shù)據(jù)重定向方法（續(xù)）1322.變量換名

58、技術(shù)用來(lái)自動(dòng)消除讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)。規(guī)則：一個(gè)變量只允許定值一次。在三種數(shù)據(jù)相關(guān)中，實(shí)際上只有寫讀數(shù)據(jù)相關(guān)必須依靠硬件、或采用軟硬件結(jié)合的方法來(lái)解決。解決方法：推后處理或?qū)Ｓ脭?shù)據(jù)通路。在上面的數(shù)據(jù)重定向圖中，把B換成了B，并在以后的都引用B讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就不存在了。數(shù)據(jù)重定向方法（續(xù)）133數(shù)據(jù)重定向方法（續(xù)）一個(gè)實(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.一個(gè)簡(jiǎn)單的程序： 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動(dòng)態(tài)調(diào)度算法實(shí)用的動(dòng)態(tài)調(diào)度算法主要有兩種:(1)集中控制：CDC計(jì)分牌(scorebord)算法.最先在CDC 6600大型機(jī)中采用。(2)分散控制：Tomasulo算法, 公共數(shù)據(jù)總線法，令牌法等。最早在大型機(jī)IBM 360/91的浮點(diǎn)處理部件中被采用。以上面的一段程序?yàn)槔f(shuō)明Tomasulo算法k： LOAD F1, Ak+1：