計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章基本概念第二章指令系統(tǒng)第三章存儲(chǔ)系統(tǒng)第四章輸入輸出系統(tǒng)第五章標(biāo)量處理機(jī)第六章向量處理機(jī)第七章互連網(wǎng)絡(luò)第八章并行處理機(jī)第九章多處理機(jī)1第五章標(biāo)量處理機(jī)標(biāo)量處理機(jī)--只有標(biāo)量數(shù)據(jù)表示和標(biāo)量指令系統(tǒng)的處理機(jī)提高指令執(zhí)行速度的主要途徑提高處理機(jī)的工作主頻采用更好的算法和設(shè)計(jì)更好的功能部件采用指令級(jí)并行技術(shù)三種指令級(jí)并行處理機(jī)流水線處理機(jī)和超流水線(Super-pipelining)處理機(jī)超標(biāo)量(Superscalar)處理機(jī)超長(zhǎng)指令字(VLIW:VeryLongInstructionWord)處理機(jī)三種基本技術(shù)先行控制技術(shù)流水線技術(shù)相關(guān)性分析技術(shù)動(dòng)態(tài)調(diào)度技術(shù)2本章主要內(nèi)容5.1先行控制技術(shù)5.2流水線技術(shù)5.3相關(guān)性分析技術(shù)5.4動(dòng)態(tài)調(diào)度技術(shù)5.5超標(biāo)量處理機(jī)5.6超流水線處理機(jī)5.7超標(biāo)量超流水線處理機(jī)35.1先行控制技術(shù)先行控制(Lookahead)技術(shù)最早在IBM公司的STRETCH機(jī)器中采用。先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。目前，許多處理機(jī)中都已經(jīng)采用了先行控制技術(shù)。45.1先行控制技術(shù)5.1.1指令的重疊執(zhí)行方式1、順序執(zhí)行方式執(zhí)行n條指令所用的時(shí)間為：如每段時(shí)間都為t，則執(zhí)行n條指令所用的時(shí)間為：T=3nt主要優(yōu)點(diǎn)：控制簡(jiǎn)單，節(jié)省設(shè)備。主要缺點(diǎn)：執(zhí)行指令的速度慢，功能部件的利用率低取指令k分析k執(zhí)行k取指令k+1分析k+1執(zhí)行k+152、一次重疊執(zhí)行方式如果兩個(gè)過程的時(shí)間相等，則執(zhí)行n條指令的時(shí)間為：T=(1+2n)t一種最簡(jiǎn)單的流水線方式主要優(yōu)點(diǎn)：指令的執(zhí)行時(shí)間縮短功能部件的利用率明顯提高主要缺點(diǎn)：需要增加一些硬件控制過程稍復(fù)雜取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1取指k+2分析k+2執(zhí)行k+263、二次重疊執(zhí)行方式如果三過程的時(shí)間相等，執(zhí)行n條指令的時(shí)間為：T=(2+n)t理想情況下同時(shí)有三條指令在執(zhí)行處理機(jī)的結(jié)構(gòu)要作比較大的改變，必須采用先行控制方式取指k+2分析k+2執(zhí)行k+2取指k+1分析k+1執(zhí)行k+1取指k分析k執(zhí)行k71、采用二次重疊執(zhí)行方式，必須解決兩個(gè)問題(1)有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件一個(gè)集中的指令控制器，分解成三個(gè)相對(duì)獨(dú)立的控制器：存儲(chǔ)控制器、指令控制器、運(yùn)算控制器(2)要解決訪問主存儲(chǔ)器的沖突問題取指令、分析指令、執(zhí)行指令都可能要訪問存儲(chǔ)器5.1.2先行控制方式的原理和結(jié)構(gòu)8(1)兩個(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)。(2)采用低位交叉存取方式：這種方法不能根本解決沖突問題。取指令、讀操作數(shù)、寫結(jié)果。(3)采用先行控制技術(shù)。先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。緩沖技術(shù)是在工作速度不固定的兩個(gè)功能部件之間設(shè)置緩沖棧，用以平滑它們的工作。在采用了緩沖技術(shù)和預(yù)處理技術(shù)之后，運(yùn)算器能夠?qū)Ｐ挠跀?shù)據(jù)的運(yùn)算，從而大幅度提高程序的執(zhí)行速度。2、解決訪存沖突的方法95.1.2.1處理機(jī)結(jié)構(gòu)在處理機(jī)內(nèi)部設(shè)置一定容量的指令緩沖棧把指令分析器所需要的指令事先取到指令緩沖棧中，而不必訪問主存儲(chǔ)器使取指令、分析指令和執(zhí)行指令重疊起來執(zhí)行三個(gè)獨(dú)立的控制器存儲(chǔ)控制器指令控制器運(yùn)算控制器四個(gè)緩沖棧先行指令緩沖棧先行讀數(shù)緩沖棧先行操作棧后行寫數(shù)棧10先行控制方式中的一次重疊執(zhí)行指令分析器每次取指令能夠在先行指令緩沖棧中得到，則取指令只需要很短的時(shí)間就能夠完成可以把取指令與分析指令合并到一起構(gòu)成一次重疊執(zhí)行方式11先行指令緩沖棧的組成只要指令緩沖棧沒有充滿，就自動(dòng)發(fā)出取指令的請(qǐng)求。設(shè)置兩個(gè)程序計(jì)數(shù)器：先行程序計(jì)數(shù)器PC1，用來指示取指令，現(xiàn)行程序計(jì)數(shù)器PC，記錄指令分析器正在分析的指令地址12存在的主要問題(1)各類指令“分析”和“執(zhí)行”所需要的時(shí)間相差很大。(2)數(shù)據(jù)相關(guān)和變址相關(guān)。(3)轉(zhuǎn)移或轉(zhuǎn)子程序指令。135.1.2.2先行控制方式的指令執(zhí)行時(shí)序設(shè)置了指令緩沖棧，取指令的時(shí)間就可以忽略不計(jì)。1、分析指令和執(zhí)行指令時(shí)間不相等時(shí)的情況142、采用先行緩沖棧的指令執(zhí)行過程先行讀數(shù)棧，先行操作棧，后行寫數(shù)棧。153、指令執(zhí)行過程的時(shí)空?qǐng)D表示方法理想情況下，指令執(zhí)行部件應(yīng)該一直忙碌連續(xù)執(zhí)行n條指令的時(shí)間為：165.1.2.3先行緩沖棧設(shè)置先行緩沖棧的目的：使指令分析器和指令執(zhí)行部件獨(dú)立工作。171、先行指令緩沖棧位置：主存儲(chǔ)器與指令分析器之間。作用：用它來平滑主存儲(chǔ)器取指令和指令分析器的工作。運(yùn)算、移位、數(shù)據(jù)傳送等指令都處理成RR型指令，送入先行操作棧。RR型指令，不必處理，直接送先行緩沖棧；RS和RX型指令，主存有效地址送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號(hào)替換指令中的主存地址碼部分，形成RR*指令送先行緩沖棧；RI型指令，指令中的立即數(shù)送先行讀數(shù)棧，用該先行讀數(shù)棧的寄存器編號(hào)替換指令中的立即數(shù)部分，形成RR*指令送先行緩沖棧。無條件轉(zhuǎn)移及條件轉(zhuǎn)移指令，一般在指令分析器中直接執(zhí)行。182、先行操作棧位置：指令分析器和運(yùn)算控制器之間。作用：使指令分析器和運(yùn)算器能夠各自獨(dú)立工作。采用先進(jìn)先出方式工作，由指令寄存器堆和控制邏輯組成。193、先行讀數(shù)棧位置：主存儲(chǔ)器與運(yùn)算器之間。作用：平滑運(yùn)算器與主存儲(chǔ)器的工作。每個(gè)緩沖寄存器由地址寄存器、操作數(shù)寄存器和標(biāo)志三部分組成。也可以把地址寄存器和操作數(shù)寄存器合為一個(gè)。當(dāng)收到從指令分析器中送來的有效地址時(shí)，就向主存申請(qǐng)讀操作數(shù)。讀出的操作數(shù)存放在操作數(shù)寄存器中或覆蓋掉地址寄存器中的地址。204、后行寫數(shù)棧每個(gè)后行緩沖寄存器由地址寄存器、數(shù)據(jù)寄存器和標(biāo)志三個(gè)部分組成。指令分析器遇到向主存寫結(jié)果的指令，把形成的有效地址送入后行寫數(shù)棧的地址寄存器中，并用該地址寄存器的編號(hào)替換指令的目的地址部分，形成RR*指令送入先行操作棧。當(dāng)運(yùn)算器執(zhí)行這條RR*型寫數(shù)指令時(shí)，只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可。215、在采用先行控制方式的處理機(jī)中，一個(gè)程序的執(zhí)行情況指令地址指令執(zhí)行情況......k-i-1已經(jīng)執(zhí)行完成的指令k-i......k-1在“后行寫數(shù)?！敝械却呀Y(jié)果寫到主存儲(chǔ)器中的指令k正在“指令執(zhí)行部件”中執(zhí)行的指令k+1......k+j已經(jīng)由“指令分析器”預(yù)處理完成，被存放在“先行操作?！敝械腞R*型指令，指令所需要的操作數(shù)也已經(jīng)讀到“先行讀數(shù)?！敝衚+j+1......k+j+n指令已經(jīng)由“指令分析器”預(yù)處理完成，存放在“先行操作?！敝?，指令所需要的操作數(shù)還沒有讀到“先行讀數(shù)棧”中k+j+n+1正在“指令分析器”中進(jìn)行分析和預(yù)處理的指令k+j+n+2......k+j+n+m已經(jīng)從主存儲(chǔ)器中預(yù)取到“先行指令緩沖?！敝械闹噶頺+j+n+m+1......還沒有進(jìn)入處理機(jī)的指令225.1.2.4緩沖深度的設(shè)計(jì)以采用靜態(tài)分析方法為主，并通過系統(tǒng)模擬來確定緩沖深度。1、先行指令緩沖棧的設(shè)計(jì)考慮兩種極端情況：(1)先行指令緩沖棧已經(jīng)充滿假設(shè)緩沖深度為DI,指令流出的速度最快，例如連續(xù)分析RR型指令，設(shè)這種指令序列的最大長(zhǎng)度為L(zhǎng)1，平均分析一條這種指令的時(shí)間為t1；指令流入的速度最慢，設(shè)平均取一條指令的時(shí)間為t2。從主存儲(chǔ)器中取到先行指令緩沖棧中的指令條數(shù)是L1-DI條。應(yīng)該滿足如下關(guān)系：L1t1=(LI-DI)t2計(jì)算出緩沖深度為：如果這種指令流的連續(xù)長(zhǎng)度超過L1，則先行指令緩沖棧將失去作用。23(2)先行指令緩沖棧原來空并假設(shè)它的緩沖深度為DI輸入端指令流入的速度最快，每次取指令的時(shí)間最短；設(shè)這種指令序列的最大長(zhǎng)度為L(zhǎng)2，平均取一條這種指令的時(shí)間為t2’；輸出端指令流出的速度最慢，指令分析器連續(xù)分析最難分析的指令；設(shè)平均分析一條指令的時(shí)間為t1’。指令分析器分析的指令條數(shù)是L2-DI條。應(yīng)該滿足如下關(guān)系：(L2-DI)t1’=LIt2’計(jì)算出緩沖深度為：如果這種指令流的連續(xù)長(zhǎng)度超過L2，先行指令緩沖棧就失去了緩沖作用。242、設(shè)計(jì)舉例在一般處理機(jī)中連續(xù)執(zhí)行短指令的概率大，另外，還有“吸收型”指令。因此，一般用前一種方法來計(jì)算緩沖深度。例5.1：一個(gè)采用先行控制方式的處理機(jī)，指令分析器分析一條指令用一個(gè)周期，到主存儲(chǔ)器中取一條指令裝入先行指令緩沖棧平均要用4個(gè)周期。如果這種指令的平均長(zhǎng)度L1=9，即90%的指令是執(zhí)行時(shí)間短的指令。計(jì)算先行指令緩沖棧的緩沖深度為：253、先行指令緩沖棧的工作時(shí)間關(guān)系第1個(gè)周期，指令分析器取走指令k+1；向主存請(qǐng)求取指令。第4個(gè)周期末尾，指令k+8取到先行指令緩沖棧中。第8個(gè)周期末尾，指令k+9取到先行指令緩沖棧中。第9個(gè)周期，分析指令k+9，先行指令緩沖棧中沒有任何指令。第10個(gè)周期，指令分析器沒有指令可分析，只好等待。264、其余緩沖棧的設(shè)計(jì)原則各個(gè)緩沖棧的緩沖深度一般有如下關(guān)系：DI≥DC≥DR≥DW其中：DI是先行指令緩沖棧的緩沖深度，DC是先行操作棧的緩沖深度，DR是先行讀數(shù)棧的緩沖深度，DW是后行寫數(shù)棧的緩沖深度。例如：IBM370/165機(jī)，DI=4，DC=3，DR=2，DW=1。我國(guó)研制的兩臺(tái)大型計(jì)算機(jī)，其中一臺(tái)，DI=8，DC=DR=4，DW=2。另外一臺(tái)，DI=12，DC=DR=6，DW=2。275.1.3數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)：在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址量等正好是前面指令的執(zhí)行結(jié)果，則必須等待前面的指令執(zhí)行完成，并把結(jié)果寫到主存或寄存器中之后，本條指令才能開始執(zhí)行。這種相關(guān)稱為數(shù)據(jù)相關(guān)。控制相關(guān)：由條件分支指令、轉(zhuǎn)子程序指令、中斷等引起的相關(guān)。數(shù)據(jù)相關(guān)有四種：指令相關(guān)、主存操作數(shù)相關(guān)、通用寄存器相關(guān)和變址相關(guān)解決數(shù)據(jù)相關(guān)的方法有兩種：推后分析法和設(shè)置專用路徑法。285.1.3.1指令相關(guān)發(fā)生指令相關(guān)的情況：n：STORER1,n+1n+1：……滿足關(guān)系：結(jié)果地址(n)=指令地址(n+1)當(dāng)?shù)趎條指令還沒有把執(zhí)行結(jié)果寫到主存之前，取出的第n+1條指令顯然是錯(cuò)誤的。29造成的后果：在采用k個(gè)流水段的流水線處理機(jī)中，第n條指令要修改從第n+1到第n+k指令中的任意一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤。在采用先行控制方式的處理機(jī)中，如果執(zhí)行部件正在執(zhí)行第n條指令，與下面的任意一條指令發(fā)生相關(guān)，都可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤：已經(jīng)存放在先行操作棧中的指令，正在指令分析器中進(jìn)行預(yù)處理指令，已經(jīng)預(yù)取到先行指令緩沖棧中的指令。更為嚴(yán)重的是：有一些“吸收型”指令，已經(jīng)在指令分析器執(zhí)行完成30解決指令相關(guān)的根本辦法在程序設(shè)計(jì)中不允許修改指令?，F(xiàn)代程序設(shè)計(jì)方法要求程序具有再入性，可以被遞歸調(diào)用等。在IBM370機(jī)中，用“執(zhí)行指令”來解決指令相關(guān)“執(zhí)行指令”本身并不執(zhí)行，它執(zhí)行的是由第二地址((X2)+(B2)+D2)決定的主存單元中的指令。這個(gè)主存單元一般不在指令區(qū)，而是在數(shù)據(jù)區(qū)315.1.3.2主存操作數(shù)相關(guān)發(fā)生主存操作數(shù)相關(guān)的指令序列：指令執(zhí)行結(jié)果寫到主存，所需要的操作數(shù)也來自主存。n：OPA1，A2，A3；A1=(A2)OP(A3)n+1：OPA1，A2，A3；A1=(A2)OP(A3)當(dāng)出現(xiàn)下列兩種情況之一時(shí)，就發(fā)生主存操作數(shù)相關(guān)：A1(n)=A2(n+1)A1(n)=A3(n+1)32解決辦法運(yùn)算結(jié)果寫到通用寄存器，而不寫到主存。對(duì)于訪問主存儲(chǔ)器的請(qǐng)求，寫結(jié)果的優(yōu)先級(jí)高于讀操作數(shù)。335.1.3.3通用寄存器數(shù)據(jù)相關(guān)發(fā)生通用寄存器數(shù)據(jù)相關(guān)：發(fā)生的可能性最大，影響面也最大的一種數(shù)據(jù)相關(guān)。n：OPR1，A2；R1=(R1)OP(A2)n+1：OPR1，R2；R1=(R1)OP(R2)如果發(fā)生：R1(n)=R1(n+1)稱為R1數(shù)據(jù)相關(guān)。如果發(fā)生：R1(n)=R2(n+1)稱為R2數(shù)據(jù)相關(guān)。34解決通用寄存器數(shù)據(jù)相關(guān)的方法方法一：把讀操作數(shù)、寫運(yùn)算結(jié)果與指令執(zhí)行合在一個(gè)節(jié)拍。在數(shù)據(jù)從寄存器讀出，在運(yùn)算器中完成運(yùn)算，結(jié)果寫回寄存器的整個(gè)回路中，只有寄存器是時(shí)序邏輯。寄存器個(gè)數(shù)和操作部件個(gè)數(shù)不多時(shí)，是一種最常用的方法。存在問題：寄存器個(gè)數(shù)比較多時(shí)，讀、寫寄存器的時(shí)間長(zhǎng)。當(dāng)功能部件數(shù)量比較多時(shí)，寄存器堆的讀寫端口很多。必須使用多級(jí)多路選擇器。35方法二：把執(zhí)行與讀操作數(shù)、寫結(jié)果分在不同周期典型的方法是：讀操作數(shù)放在指令分析周期，在執(zhí)行周期之后，有一個(gè)寫回結(jié)果周期。36結(jié)構(gòu)上，必須在運(yùn)算器的入口處增加兩個(gè)鎖存器。第k條指令的執(zhí)行結(jié)果，如果寫回寄存器堆，然后后再讀出來，則第k+1條指令必須推后兩個(gè)周期。37方法三增加相關(guān)專用通路增加相關(guān)專用通路之后，第k+1條指令的執(zhí)行不必推后。實(shí)際上節(jié)省了兩個(gè)時(shí)鐘周期。由于通用寄存器數(shù)據(jù)相關(guān)出現(xiàn)的概率很高，因此增加一條相關(guān)專用通路是合適的。指令的執(zhí)行結(jié)果在寫回到通用寄存器的時(shí)候，同時(shí)也寫入運(yùn)算器入口處的鎖存器中。在數(shù)據(jù)從鎖存器讀出，在運(yùn)算器中完成運(yùn)算，結(jié)果再寫入鎖存器的整個(gè)回路中，只有鎖存器是時(shí)序邏輯。另外，在采用變址方式的處理機(jī)中，由于變址偏移量是放在寄存器中，因此，與通用寄存器的數(shù)據(jù)相關(guān)類似，有可能發(fā)生變址相關(guān)。385.1.3.4變址相關(guān)通用寄存器作變址寄存器使用，在指令分析時(shí)用來計(jì)算有效地址k：OPR1，R2 ;R1=(R1)OP(R2)k+1：OPR1，A2(X2) ;R1=(R1)OP((A2)+(X2))k+2：OPR1，A2(X2) ;R1=(R1)OP((A2)+(X2))如果發(fā)生：R1(k)=X2(k+1)稱為一次變址相關(guān)如果發(fā)生：R1(k)=X2(k+2)稱為二次變址相關(guān)變址相關(guān)專用通路39LOAD相關(guān)在RISC處理機(jī)中，只有LOAD操作能夠訪問存儲(chǔ)器。LOAD操作的執(zhí)行時(shí)間可能比較長(zhǎng)。n：LOADR1，A ；R1=(A)n+1：ADDR2，R1 ；R2=(R1)OP(R2)如果R1(n)=R1(n+1)，則發(fā)生LOAD數(shù)據(jù)相關(guān)。解決方法：方法一：由編譯器在LOAD之后插入不發(fā)生數(shù)據(jù)相關(guān)的指令由于LOAD操作的執(zhí)行時(shí)間不能確定，依靠插入指令不能根本解決問題方法二：由硬件自動(dòng)插入空操作，直到LOAD操作完成在只有一條流水線的處理機(jī)中，可以采用停止節(jié)拍發(fā)生器的方法，直到存儲(chǔ)器的回答信號(hào)到來時(shí)，再啟動(dòng)節(jié)拍發(fā)生器。40各種數(shù)據(jù)相關(guān)的三種主要解決方法1采用硬件或軟件的辦法盡量避免數(shù)據(jù)相關(guān)發(fā)生。例如，為了避免通用寄存器數(shù)據(jù)相關(guān)，只要采用D型觸發(fā)器構(gòu)成通用寄存器堆，并且通用寄存器堆在一個(gè)節(jié)拍中能夠讀出兩個(gè)操作數(shù)并寫回一個(gè)結(jié)果2在確保指令正確執(zhí)行的前提下，推后指令分析3設(shè)置相關(guān)專用通路來解決數(shù)據(jù)相關(guān)415.1.4控制相關(guān)指因?yàn)槌绦虻膱?zhí)行方向可能被改變而引起的相關(guān)可能改變程序執(zhí)行方向的指令通常有

無條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、復(fù)合條件轉(zhuǎn)移、子程序調(diào)用、中斷等數(shù)據(jù)相關(guān)稱為局部相關(guān)，影響到的僅僅是本條指令附近的少數(shù)幾條指令控制相關(guān)稱為全局相關(guān)，影響的范圍要大得多，它可能引起程序執(zhí)行方向的改變425.1.4.1無條件轉(zhuǎn)移無條件轉(zhuǎn)移指令在程序中一般如下：

k：……

k+1：JMPL

…：……

L：……在流水線處理機(jī)中，無條件轉(zhuǎn)移指令不進(jìn)入執(zhí)行流水段，一般在指令譯碼(或稱為指令分析)階段就實(shí)際執(zhí)行完成如果在處理機(jī)中設(shè)置有指令先行緩沖棧，無條件轉(zhuǎn)移指令一般能夠在指令分析階段就執(zhí)行完成，形成轉(zhuǎn)移地址L同時(shí)送入先行程序計(jì)數(shù)器PC1和現(xiàn)行程序計(jì)數(shù)器PC中，指令緩沖棧按照PC1的指示重新開始向存儲(chǔ)控制器申請(qǐng)取指令。43如果轉(zhuǎn)移距離比較遠(yuǎn)指令L不在指令緩沖棧中，則要將指令緩沖棧中的所有指令全部作廢指令分析器要等待一個(gè)“取指令L”周期之后才能開始“分析L”如果轉(zhuǎn)移的距離比較近有可能指令L已經(jīng)被取到了指令緩沖棧中只要作廢指令緩沖棧中的部分指令，即作廢從k+3到L-1之間的所有指令指令分析器在完成“分析k+1”之后，可以接著進(jìn)行“分析L”，即指令分析器仍然可以不停頓地連續(xù)工作在指令緩沖棧的入口處增設(shè)一個(gè)專門處理無條件轉(zhuǎn)移指令的指令分析器44在設(shè)置有先行操作棧的處理機(jī)中，無條件轉(zhuǎn)移指令一般對(duì)指令執(zhí)行部件的工作不會(huì)造成影響。為了進(jìn)一步減少無條件轉(zhuǎn)移指令造成的影響，在先行指令緩沖棧的入口處增設(shè)一個(gè)專門處理無條件轉(zhuǎn)移指令的指令分析器。就不會(huì)再發(fā)生作廢先行緩沖棧中指令的情況。455.1.4.2一般條件轉(zhuǎn)移條件轉(zhuǎn)移指令有兩種:一般條件轉(zhuǎn)移指令的轉(zhuǎn)移條件來自上一條指令，或更前面的指令而復(fù)合型條件轉(zhuǎn)移指令直接根據(jù)本條指令的執(zhí)行結(jié)果決定是否轉(zhuǎn)移k：…… ;置條件碼CC

k+1：JMP(CC)L ;CC為真轉(zhuǎn)向L，否則繼續(xù)執(zhí)行k+2

k+2：……

…：……

L：……46一般條件轉(zhuǎn)移指令，相關(guān)最嚴(yán)重的情況發(fā)生在條件碼是由上一條指令產(chǎn)生的:條件碼要在“執(zhí)行k”的末尾才能形成“分析k+1”在一開始就要根據(jù)這個(gè)條件碼判斷轉(zhuǎn)移條件是否成立指令分析器分析到條件轉(zhuǎn)移指令時(shí)，必須停下來等待所需要的條件碼4748無論轉(zhuǎn)移是否成功，條轉(zhuǎn)移指令都在指令分析階段就已經(jīng)執(zhí)行完成。如果轉(zhuǎn)移不成功：指令分析器要停頓一段時(shí)間，等待條件碼。如果轉(zhuǎn)移成功：指令L已經(jīng)在先行指令緩沖棧，指令分析器接著“分析L”指令L不在先行指令緩沖棧，指令分析器要等待一個(gè)周期。轉(zhuǎn)移不成功，對(duì)程序執(zhí)行影響不大。當(dāng)轉(zhuǎn)移成功時(shí)，不僅指令執(zhí)行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。因此，在采用流水線方式的處理機(jī)中，要通過軟件與硬件的多種手段來近可能地降低轉(zhuǎn)移成功的概率，減少轉(zhuǎn)移成功造成的影響。495.1.4.3復(fù)合條件轉(zhuǎn)移復(fù)合型條件轉(zhuǎn)移指令本身就是一條運(yùn)算指令，并且直接根據(jù)本條指令的運(yùn)算結(jié)果決定是否轉(zhuǎn)移。復(fù)合型條件轉(zhuǎn)移指令的執(zhí)行時(shí)間關(guān)系下：k：OPL;先執(zhí)行OP操作，根據(jù)執(zhí)行結(jié)果產(chǎn)生的條件碼決定是否轉(zhuǎn)向Lk+1：………：……L：……復(fù)合型條件轉(zhuǎn)移指令不能在指令分析器中執(zhí)行完成，它必須象其它運(yùn)算型指令一樣經(jīng)指令執(zhí)行部件執(zhí)行無條件轉(zhuǎn)移指令和一般條件轉(zhuǎn)移指令能夠在指令分析器中執(zhí)行完成，稱為吸收型指令50如果轉(zhuǎn)移不成功：不造成任何影響，復(fù)合型條件轉(zhuǎn)移指令就象一條普通的運(yùn)算型指令一樣。如果轉(zhuǎn)移成功：造成的影響比一般條件轉(zhuǎn)移指令還要大得多，全部作廢或部分作廢先行指令緩沖棧中已經(jīng)預(yù)取的指令，作廢先行操作棧中的指令和先行讀數(shù)棧中的操作數(shù)，作廢當(dāng)前在指令分析器中分析的指令。因此，必須采取策略，減小轉(zhuǎn)移成功造成的影響。515.1.4.4轉(zhuǎn)移預(yù)測(cè)技術(shù)在程序執(zhí)行過程中，轉(zhuǎn)移預(yù)測(cè)的方向不能改變的稱為靜態(tài)分支預(yù)測(cè)。在程序執(zhí)行過程中能夠動(dòng)態(tài)地改變轉(zhuǎn)移預(yù)測(cè)方向的稱為動(dòng)態(tài)分支預(yù)測(cè)。521、軟件“猜測(cè)法”轉(zhuǎn)移不成功時(shí)，條件轉(zhuǎn)移指令對(duì)流水線的影響比較小編譯器在對(duì)源程序進(jìn)行編譯時(shí)，為了達(dá)到比較好的效果，要盡量降低轉(zhuǎn)移成功出現(xiàn)的概率優(yōu)點(diǎn)是不需要改變硬件結(jié)構(gòu)，只要適當(dāng)修改編譯器就能夠大幅度降低條件轉(zhuǎn)移指令的影響主要目的：通過編譯器盡量降低轉(zhuǎn)移成功的概率。例如：對(duì)于普通的循環(huán)程序，一般編譯器生成的目標(biāo)代碼，轉(zhuǎn)移成功的概率很高，不成功的只有一次。這種編譯結(jié)果對(duì)流水線的影響非常大。53542、硬件“猜測(cè)法”基本原理：通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對(duì)流水線造成的影響。實(shí)現(xiàn)方法：在先行指令緩沖棧的人口處設(shè)置一個(gè)簡(jiǎn)單的指令分析器，當(dāng)這個(gè)指令分析器檢測(cè)到轉(zhuǎn)移指令時(shí)，就把轉(zhuǎn)移目標(biāo)地址L送入先行程序計(jì)數(shù)器PC1中，同時(shí)保留當(dāng)前PC1中的內(nèi)容到另一寄存器中。如果轉(zhuǎn)移成功，則猜測(cè)正確。轉(zhuǎn)移指令對(duì)流水線不造成影響。如果轉(zhuǎn)移不成功，用保存下來的地址恢復(fù)PC1和PC中的內(nèi)容，并重新開始取指令。軟件和硬件要共同配合，軟件與硬件都往同一個(gè)方向去猜測(cè)。553、兩個(gè)指令緩沖棧原因：對(duì)于循環(huán)程序，軟件“猜測(cè)法”或硬件“猜測(cè)法”都能獲得很好效果對(duì)于普通條件轉(zhuǎn)移指令(向前轉(zhuǎn)移)；轉(zhuǎn)移成功與不成功的概率很難預(yù)測(cè)。普通條件轉(zhuǎn)移指令；如“IF”語句編譯產(chǎn)生的條件轉(zhuǎn)移指令,轉(zhuǎn)移成功與不成功的概率一般各為50%方法：增加一個(gè)指令目標(biāo)緩沖棧當(dāng)指令分析器分析到條件轉(zhuǎn)移指令時(shí)，按照轉(zhuǎn)移成功的方向預(yù)取指令到這個(gè)指令目標(biāo)緩沖棧中原來的指令緩沖棧仍然按照轉(zhuǎn)移不成功的方向繼續(xù)預(yù)取指令轉(zhuǎn)移不成功，則繼續(xù)分析原來指令緩沖棧中指令轉(zhuǎn)移成功，則分析新增設(shè)的指令目標(biāo)緩沖棧中的指令56IBM370/165機(jī)就采用了兩個(gè)先行指令緩沖棧。先行目標(biāo)緩沖棧AIB的緩沖深度為4。為了簡(jiǎn)化對(duì)兩套先行指令緩沖棧的控制，在轉(zhuǎn)移成功時(shí)，交換先行目標(biāo)緩沖棧AIB和原來的先行指令緩沖棧IB中內(nèi)容，使指令分析器仍然從原來的指令緩沖棧IB中的取指令。575.1.4.5短循環(huán)程序的處理開門、關(guān)門指令硬件識(shí)別585.2流水線處理機(jī)空間并行性設(shè)置多個(gè)獨(dú)立的操作部件多操作部件處理機(jī)超標(biāo)量處理機(jī)時(shí)間并行性采用流水線技術(shù)。不增加或只增加少量硬件就能使運(yùn)算速度提高幾倍流水線處理機(jī)超流水線處理機(jī)595.2.1流水線工作原理5.2.1.1從重疊到流水線流水線的每一個(gè)階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級(jí)、流水節(jié)拍等。在每一個(gè)流水段的末尾或開頭必須設(shè)置一個(gè)寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。會(huì)增加指令的執(zhí)行時(shí)間。為了簡(jiǎn)化，在一般流水線中不畫出流水鎖存器。分析器分析k+1流水

鎖存器執(zhí)行部件執(zhí)行k流水

鎖存器輸入輸出Dt1Dt2602、一種指令流水線一般4至12個(gè)流水段，等于及大于8個(gè)流水段的稱為超流水線處理機(jī)流水線的連接圖表示方法表示流水線的邏輯關(guān)系流水線的時(shí)空?qǐng)D表示方法表示流水線的時(shí)間關(guān)系流水線的預(yù)約表表示方法將在非線性流水線中介紹取指形成操

作數(shù)地址譯碼取操作數(shù)執(zhí)行保存結(jié)果61?IntelP4CPU是否流水線處理機(jī)IntelP4CPU使用幾級(jí)流水線625.2.1.2時(shí)空?qǐng)D一條簡(jiǎn)單流水線的時(shí)空?qǐng)D：分析k分析k+1分析k+2分析k+3執(zhí)行k執(zhí)行k+1執(zhí)行k+2執(zhí)行k+3時(shí)間空間0t1t2t3t4t563一個(gè)浮點(diǎn)加法器流水線的時(shí)空?qǐng)D(由求階差、對(duì)階、尾數(shù)加和規(guī)格化4個(gè)流水段組成)：ED1時(shí)間空間0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：規(guī)格化MA：尾數(shù)加EA：對(duì)階ED：求階差645.2.1.3流水線的特點(diǎn)1、在流水線中處理的必須是連續(xù)任務(wù)只有連續(xù)不斷地提供任務(wù)才能充分發(fā)揮流水線的效率在采用流水線方式工作的處理機(jī)中，特別是當(dāng)流水線的級(jí)數(shù)較多時(shí)，要在軟件和硬件設(shè)計(jì)等多方面盡量為流水線提供連續(xù)的任務(wù)，以提高流水線的效率2、把一個(gè)任務(wù)(一條指令或一個(gè)操作)分解為幾個(gè)有聯(lián)系的子任務(wù)，每個(gè)子任務(wù)由一個(gè)專門的功能部件來實(shí)現(xiàn)流水線實(shí)際上是把一個(gè)大的功能部件分解為多個(gè)獨(dú)立的功能部件，并依靠多個(gè)功能部件并行工作來縮短程序的執(zhí)行時(shí)間653、在流水線的每一個(gè)功能部件的后面要要設(shè)置一個(gè)緩沖寄存器，或稱為鎖存器、閘門寄存器等，用于保存本段的執(zhí)行結(jié)果。這是因?yàn)榱魉€中每一段的延遲時(shí)間一般不可能都相等在段與段之間傳送子任務(wù)時(shí)，必須通過緩沖寄存器。當(dāng)某一個(gè)流水段的執(zhí)行時(shí)間變化范圍比較大時(shí)，要設(shè)置多個(gè)緩沖寄存器664、流水線中各段的時(shí)間應(yīng)盡量相等否則將引起“堵塞”、“斷流”等。執(zhí)行時(shí)間長(zhǎng)的一段將成為整個(gè)流水線的“瓶頸”，這時(shí)，流水線中的各個(gè)功能部件將不能充分發(fā)揮作用。因此，在流水線設(shè)計(jì)中，當(dāng)遇到“瓶頸”時(shí)，必須采取辦法解決一種辦法是把“瓶頸”流水段再細(xì)分，另一種辦法是重復(fù)設(shè)置瓶頸功能段。具體內(nèi)容在性能分析一節(jié)介紹5、流水線需要有“裝入時(shí)間”和“排空時(shí)間”只有流水線完全充滿時(shí)，整個(gè)流水線的效率才能得到充分發(fā)揮在流水線處理機(jī)的設(shè)計(jì)過程中，要充分注意上述問題，以設(shè)計(jì)出高效率的流水線。在流水線處理機(jī)上設(shè)計(jì)程序時(shí)，也必須注意流水線的上述特點(diǎn)，以充分發(fā)揮流水線處理機(jī)的高效率。675.2.2流水線的分類5.2.2.1線性流水線與非線性流水線流水線的各個(gè)流水段之間是否有反饋信號(hào)線性流水線(LinearPipelining)

每個(gè)流水段都流過一次，且僅流過一次非線性流水線(NonlinearPipelining)

在流水線的某些流水段之間有反饋回路或前饋回路線性流水線能夠用流水線連接圖唯一表示

非線性流水線必須用流水線連接圖流水線預(yù)約表等共同表示S1輸入S2S3輸出前饋回路反饋回路一種簡(jiǎn)單的非線性流水線685.2.2.2流水線的級(jí)別處理機(jī)級(jí)流水線,又稱為指令流水線(InstructionPipelining)例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線先行指令

緩沖棧輸入先行控制方式

中的指令流水線先行指令

分析器先行讀數(shù)棧

先行操作棧取指譯碼取操作數(shù)指令執(zhí)行部件后行寫數(shù)棧輸出執(zhí)行寫結(jié)果69部件級(jí)流水線(操作流水線)，如浮點(diǎn)加法器流水線處理機(jī)之間的流水線稱為宏流水線(MacroPipelining)

每個(gè)處理機(jī)對(duì)同一個(gè)數(shù)據(jù)流的不同部分分別進(jìn)行處理求階差輸入輸出Dt1對(duì)階尾數(shù)加規(guī)格化Dt2Dt3Dt4P1輸入任務(wù)1MM…P2任務(wù)2MP3任務(wù)3輸出705.2.2.3單功能流水線與多功能流水線單功能流水線：只能完成一種固定功能的流水線Cray-1計(jì)算機(jī)中有12條；YH-1計(jì)算機(jī)有18條；Pentium有一條5段的定點(diǎn)和一條8段的浮點(diǎn)流水線；PentiumIII有三條指令流水線，其中兩條定點(diǎn)指令流水線，一條浮點(diǎn)指令流水線。多功能流水線：流水線的各段通過不同連接實(shí)現(xiàn)不同功能Texas公司的ASC計(jì)算機(jī)中的8段流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加減法、定點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。71725.2.2.4靜態(tài)流水線與動(dòng)態(tài)流水線靜態(tài)流水線：同一段時(shí)間內(nèi)，多功能流水線中的各個(gè)功能段只能按照一種固定的方式連接，實(shí)現(xiàn)一種固定的功能。只有連續(xù)出現(xiàn)同一種運(yùn)算時(shí)，流水線的效率才能得到充分的發(fā)揮。動(dòng)態(tài)流水線：在同一段時(shí)間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時(shí)執(zhí)行多種功能。731時(shí)間空間023…n123…n123…n123…n123…n123…n1234…123…12……1輸入求階差對(duì)階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出靜態(tài)流水線時(shí)空?qǐng)D浮點(diǎn)加法定點(diǎn)乘法741時(shí)間空間023…n123…n123…n123…n123…n123…n輸入求階差對(duì)階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出動(dòng)態(tài)流水線時(shí)空?qǐng)D………………123546123541234123…………浮點(diǎn)加法定點(diǎn)乘法75流水線的其他分類方法按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序流水線：亂序流水線又稱為無序流水線、錯(cuò)序流水線或異步流水線等S1就緒回答S2就緒回答S3就緒回答輸出就緒回答輸入765.2.3線性流水線的性能分析衡量流水線性能的主要指標(biāo)有：吞吐率、加速比和效率5.2.3.1吞吐率(ThoughPut)求流水線吞吐率的最基本公式：TP=n/Tkn為任務(wù)數(shù),Tk為完成n個(gè)任務(wù)所用時(shí)間各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下完成n個(gè)連續(xù)任務(wù)需要的總時(shí)間為：Tk=(k+n-1)Dtk為流水線的段數(shù)Dt為時(shí)鐘周期771時(shí)間空間S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nkDt(n-1)DtnDt(k-1)DtT78吞吐率：最大吞吐率為：各段執(zhí)行時(shí)間不相等、輸入連續(xù)任務(wù)情況下：吞吐率為：最大吞吐率為：79流水線各段執(zhí)行時(shí)間不相等的解決辦法S1輸入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt輸出1時(shí)間空間S1S2S3S4SDti(n-1)Dt2Tk23…n123…n123…n123…n80一是將“瓶頸”流水段細(xì)分(如果可分的話)：二是將“瓶頸”流水段重復(fù)設(shè)置：p420級(jí)、31級(jí)1，2Pentium系統(tǒng)結(jié)構(gòu)的核心是超標(biāo)量流水線。U,V兩條指令流水線，有各自的ALU、地址生成電路、與數(shù)據(jù)Cache的接口RISC2，4，8，16個(gè)整數(shù)運(yùn)算器2??HyperThreading超線程技術(shù)S1輸入輸出DtS2-1DtS2-2DtS2-3DtS3DtS4DtS2(3Dt)S1輸入輸出Dt1=DtS2-1S2-1S2-1S3S4Dt3=DtDt4=DtDt2=3Dt81流水段重復(fù)設(shè)置的流水線1時(shí)間空間23nS1S2-1456…14…-2-1n-225…n-136…n123n456…-2-1123n456…-2-1S2-2S2-3S3S4825.2.3.2、加速比(Speedup)計(jì)算流水線加速比的基本公式：S=順序執(zhí)行時(shí)間T0/流水線執(zhí)行時(shí)間Tk各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下加速比為：

最大加速比為：

各段執(zhí)行時(shí)間不等，輸入連續(xù)任務(wù)情況下實(shí)際加速比為：83K=6K=10任務(wù)

個(gè)數(shù)加速比10246811248163264128845.2.3.3效率(Efficiency)計(jì)算流水線效率的一般公式：

各流水段執(zhí)行時(shí)間相等，輸入n個(gè)連續(xù)任務(wù)

流水線的效率為：

流水線的最高效率為：85各流水段執(zhí)行時(shí)間不等，輸入n個(gè)連續(xù)任務(wù)流水線的效率為：流水線各段的設(shè)備量或各段的價(jià)格不相等時(shí),流水線的效率為：

即：

其中，ai<k，且86流水線的吞吐率、加速比與效率的關(guān)系因?yàn)橐虼耍篍=TP·Dt，S=k·E875.2.3.4流水線最佳段數(shù)的選擇從上面的分析中可以清楚地看到，增加流水線的段數(shù)，流水線的吞吐率和加速比都能提高用于在每一個(gè)流水段的輸出端都必須設(shè)置一個(gè)鎖存器(或稱緩沖寄存器、閘門寄存器等)當(dāng)流水線的段數(shù)增多時(shí)，鎖存器的總的延遲時(shí)間也將增加，甚至有可能出現(xiàn)鎖存器的總延遲時(shí)間超過流水線本身的延遲時(shí)間。增加鎖存器數(shù)量，必然要增加流水線的價(jià)格要綜合各方面的因素，應(yīng)該根據(jù)最佳性能價(jià)格比的要求來選擇流水線的最佳段數(shù)88

如果流水線段數(shù)過多，時(shí)鐘周期很小，以至于與時(shí)鐘偏移和鎖存器的附加開銷相當(dāng)，會(huì)導(dǎo)致在一個(gè)時(shí)鐘周期內(nèi)沒有足夠時(shí)間用于有效工作，流水線也就失去了作用。

假設(shè)在非流水線的機(jī)器上采用順序執(zhí)行方式完成一個(gè)任務(wù)所需要的時(shí)間為t，那么，在同等速度的有k段流水線的機(jī)器上執(zhí)行一個(gè)任務(wù)需要的時(shí)間為：其中d為鎖存器的延遲時(shí)間。這樣，流水線的最大吞吐率可以表示為：89流水線的總價(jià)格粗略地估計(jì)為：C=a+bk，其中，a為所有流水段本身的總價(jià)格，b為每個(gè)鎖存器的價(jià)格。A.G.Larson把流水線的性能價(jià)格比PCR定義為： (5.41)可以通過對(duì)自變量k求導(dǎo)，得到性能價(jià)格比PCR的極值。由于大于零的極值只有一個(gè)，因此，這個(gè)極值就是最大值。如圖所示，當(dāng)性能價(jià)格比PCR取得最大值時(shí)，它所對(duì)應(yīng)的流水線的段數(shù)就時(shí)最佳段數(shù)k0：

(5.42)式中的t為流水線的總的延遲時(shí)間。

從(5.42)關(guān)系式中可以很清楚地看到，流水線的最佳段數(shù)與流水線的延遲時(shí)間t和流水線本身的價(jià)格a的平方根成正比，而與鎖存器的延遲時(shí)間d和鎖存器的價(jià)格b的平方根成反比。90流水線的最佳段數(shù)

在設(shè)計(jì)一條流水線的時(shí)候，可以根據(jù)(5.42)關(guān)系式，在流水線的總延遲時(shí)間t一定的情況下，可以通過調(diào)整流水線本身的價(jià)格a，鎖存器的延遲時(shí)間d和鎖存器的價(jià)格b來選取最佳的流水線段數(shù)k0。

目前，一般處理機(jī)中的流水線段數(shù)在2段至10段之間，極少有超過15段的流水線。一般把8段或超過8段的流水線稱為超流水線，采用8段以上流水線的處理機(jī)稱為超流水線處理機(jī)。915.2.3.5、流水線性能分析舉例對(duì)于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計(jì)算出流水線的吞吐率、加速比和效率。例5.1：用一條4段浮點(diǎn)加法器流水線求8個(gè)浮點(diǎn)數(shù)的和：

Z=A+B+C+D+E+F+G+H92解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1時(shí)間空間23求階差4567123456712345671234567對(duì)階尾數(shù)加規(guī)格化加數(shù)ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H結(jié)果A+BC+DE+FG+HA+B+C+DE+F+G+H937個(gè)浮點(diǎn)加法共用了15個(gè)時(shí)鐘周期。

流水線的吞吐率為：

流水線的加速比為：

流水線的效率為：945.2.4非線性流水線的調(diào)度技術(shù)非線性流水線調(diào)度的任務(wù)找出一個(gè)最小的循環(huán)周期按照這周期向流水線輸入新任務(wù)流水線的各個(gè)功能段都不會(huì)發(fā)生沖突流水線的吞吐率和效率最高955.2.4.1非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示96流水線連接圖不能唯一表示非線性流水線的工作流程引入流水線預(yù)約表97一張預(yù)約表可能與多個(gè)流水線連接圖相對(duì)應(yīng)與上面的預(yù)約表對(duì)應(yīng)的另一種非線性流水線的連接圖98一個(gè)連接圖對(duì)應(yīng)有多張預(yù)約表與前一個(gè)連接圖對(duì)應(yīng)的另一張預(yù)約表995.2.4.2非線性流水線的沖突流水線的啟動(dòng)距離：向流水線連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔流水線的沖突：幾個(gè)任務(wù)爭(zhēng)用同一個(gè)流水段1001011025.2.4.3無沖突調(diào)度方法相關(guān)理論由E.S.Davidson及其學(xué)生們于1971年提出非線性流水線的禁止向量預(yù)約表中每一行任意兩個(gè)“×”之間的距離都計(jì)算出來，去掉重復(fù)的例如，上圖所示的預(yù)約表的禁止向量為(3，4，6)由禁止向量得到?jīng)_突向量C=(CmCm-1…C2C1)其中：m是禁止向量中的最大值如果i在禁止向量中，則Ci=1，否則Ci=0例如：對(duì)于上面的預(yù)約表，C=(101100)由沖突向量構(gòu)造狀態(tài)圖：把沖突向量送入一個(gè)m位邏輯右移移位器，當(dāng)移位器移出0時(shí)，用移位器中的值與初始沖突向量作“按位或”運(yùn)算，得到一個(gè)新的沖突向量；否則不作任何處理；如此重復(fù)m次對(duì)于中間形成的每一個(gè)新的沖突向量，也要按照這一方法進(jìn)行處理在初始沖突向量和所有的新形成的沖突向量之間用帶箭頭的線連接，當(dāng)新形成的沖突向量出現(xiàn)重復(fù)時(shí)可以合并到一起103例一條有4個(gè)功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等1寫出流水線的禁止向量和初始沖突向量2畫出調(diào)度流水線的狀態(tài)圖3求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離4求平均啟動(dòng)距離最小的恒定循環(huán)104解1.禁止向量為：(2，4，6)初始沖突向量：101010(0)2.初始沖突向量邏輯右移2、4、6位時(shí)，不作任何處理邏輯右移1、3、5和大于等于7時(shí)，要進(jìn)行處理初始沖突向量右移1位之后：010101∨101010=111111(0)--1-->(1)初始沖突向量右移3位之后：000101∨101010=101111(0)--3-->(2)初始沖突向量右移5位之后：000001∨101010=101011(0)--5-->(3)初始沖突向量右移7位或大于7位后：還原到它本身。(0)--7-->(0)中間沖突向量101111右移5位之后：000001∨101010=101011(2)--5-->(3)中間沖突向量101011右移3位之后：000101∨101010=101111(3)--3-->(2)中間沖突向量101011右移5位之后：000001∨101010=101011(3)--5-->(3)105預(yù)約表與狀態(tài)圖是唯一對(duì)應(yīng)，但不同的預(yù)約表也可能有相同的狀態(tài)圖1063.簡(jiǎn)單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動(dòng)循環(huán)簡(jiǎn)單循環(huán)的個(gè)數(shù)一般是有限的由簡(jiǎn)單循環(huán)可以計(jì)算出平均啟動(dòng)距離107最小的啟動(dòng)循環(huán)為(1，7)或(3，5)其平均啟動(dòng)距離為4平均啟動(dòng)距離最小的恒定循環(huán)為(5)。1081091105.2.4.4優(yōu)化調(diào)度方法L.E.Shar于1972年提出了流水線最小平均啟動(dòng)距離的限制范圍1下限是預(yù)約表中任意一行里“×”的最多個(gè)數(shù)2小于或等于狀態(tài)圖中任意一個(gè)簡(jiǎn)單循環(huán)的平均啟動(dòng)距離3最小平均啟動(dòng)距離的上限是沖突向量中1的個(gè)數(shù)再加上11992年，L.E.Shar證明了上述限制范圍最有用的是第1條。預(yù)約表中“×”最多的行一定是瓶頸流水段采用預(yù)留算法來調(diào)度非線性流水線，可以實(shí)現(xiàn)最優(yōu)調(diào)度第1步：確定最小平均啟動(dòng)距離，為預(yù)約表中任意一行中“×”的最多個(gè)數(shù)。第2步：確定最小啟動(dòng)循環(huán)，以恒定循環(huán)作為最小啟動(dòng)循環(huán)。第3步：采用預(yù)留算法，插入非計(jì)算延遲段實(shí)現(xiàn)最小啟動(dòng)循環(huán)111對(duì)于上一節(jié)的例子：S1、S2、S3對(duì)應(yīng)的行有2個(gè)“×”，因此，最小平均啟動(dòng)距離為2。以恒定循環(huán)(2)作為最小啟動(dòng)循環(huán)。檢查每一行中與第1個(gè)“×”的距離為2的倍數(shù)的位置都要預(yù)留出來。S3行的第2個(gè)“×”從周期5延遲到周期6。為此，S2行的第2個(gè)“×”也要向后延遲一個(gè)周期，從周期6延遲到周期7S1行的第2個(gè)“×”也要向后延遲一個(gè)周期，從周期7延遲到周期8。實(shí)際上，只要在S4的輸出端到S3的輸入端中間插入一個(gè)非計(jì)算延遲D1，如下表和下圖所示112113在非線性流水線中，“×”最多的流水段一定是“瓶頸“流水段。實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使“瓶頸”流水段處于忙碌狀態(tài)，沒有空閑的周期最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率、加速比和效率達(dá)到最優(yōu)。1145.2.5局部相關(guān)(動(dòng)態(tài)調(diào)度技術(shù))由硬件動(dòng)態(tài)調(diào)整指令執(zhí)行順序以減少數(shù)據(jù)相關(guān)的影響。能夠處理在編譯階段無法確定的相關(guān)關(guān)系，并簡(jiǎn)化編譯器設(shè)計(jì)；在別的流水線機(jī)器上編譯的代碼也能夠高效運(yùn)行。采用靜態(tài)調(diào)度方法生成的代碼也能在采用動(dòng)態(tài)調(diào)度法的機(jī)器中運(yùn)行。5.2.5.1順序流動(dòng)與亂序流動(dòng)5.2.5.2亂序流動(dòng)方式中的數(shù)據(jù)相關(guān)5.2.5.3數(shù)據(jù)重定向方法5.2.5.4Tomasulo動(dòng)態(tài)調(diào)度算法115順序流動(dòng)方式，流水線的控制邏輯比較簡(jiǎn)單

在程序中有“先寫后讀”數(shù)據(jù)相關(guān)時(shí)，流水線可能會(huì)“斷流”，這將降低流水線的吞吐率和效率亂序流動(dòng)方式中，除了有“先寫后讀”數(shù)據(jù)相關(guān)之外，還可能發(fā)生“先讀后寫”數(shù)據(jù)相關(guān)和“寫-寫”數(shù)據(jù)相關(guān)?！跋葘懞笞x”數(shù)據(jù)相關(guān)又稱為數(shù)據(jù)相關(guān)、寫讀相關(guān)、流相關(guān)、WR相關(guān)、RAW相關(guān)“先讀后寫”相關(guān)又稱為變量名相關(guān)、讀寫相關(guān)、反相關(guān)、RW相關(guān)、WAR相關(guān)“寫-寫”數(shù)據(jù)相關(guān)又稱為輸出相關(guān)、WW相關(guān)、WAW相關(guān)或?qū)懞笤賹懴嚓P(guān)1165.2.5.1順序流動(dòng)與亂序流動(dòng)順序流動(dòng)方式：任務(wù)按順序流入流水線，也按順序流出流水線把如下一段程序輸入到這條流水線中：117其中，指令k與指令k+2之間有數(shù)據(jù)相關(guān)。指令k+2無法繼續(xù)執(zhí)行，要在功能段S2中等待。后續(xù)的指令k+4、k+5、……等也不能進(jìn)入流水線。功能段S3、S4、S5將逐漸空閑。缺點(diǎn)：流水線“斷流”，有些功能段“空閑”，吞吐率和效率降低。優(yōu)點(diǎn)：流水線的控制邏輯比較簡(jiǎn)單。118亂序流動(dòng)方式：指令流出流水線的順序與指令原先的順序不同亂序(Outoforder)流動(dòng)方式，錯(cuò)序流動(dòng)方式、無序流動(dòng)方式、異步流動(dòng)方式等。造成流水線亂序流動(dòng)方式的原因不僅僅是“先寫后讀”數(shù)據(jù)相關(guān)，有些指令執(zhí)行的時(shí)間短或經(jīng)過的流水段比較少，它們要越過執(zhí)行時(shí)間長(zhǎng)或經(jīng)過流水段多的指令向前流動(dòng)把指令k+2保存在功能段S2中，而讓后續(xù)的指令k+3、k+4、k+5進(jìn)入功能段S2執(zhí)行，并超越指令k+2進(jìn)入以后的功能段。從流水線的輸出端看，指令流出流水線的順序與進(jìn)入流水線的順序不一樣1195.2.5.2亂序流動(dòng)方式中的數(shù)據(jù)相關(guān)在亂序流動(dòng)方式中，還有另外兩種不同的相關(guān)。例如，把下面一小段程序中輸入到采用亂序流動(dòng)方式的流水線中，可能發(fā)生三種不同的數(shù)據(jù)相關(guān)。其中，F(xiàn)1、F2和F3是三個(gè)浮點(diǎn)寄存器，A和B是兩個(gè)內(nèi)存單元。(1)在指令k的F1與指令k+1的F1之間的相關(guān)關(guān)系稱為：數(shù)據(jù)相關(guān)、先寫后讀相關(guān)、寫讀相關(guān)、流相關(guān)、WR相關(guān)、RAW相關(guān)或讀后寫相關(guān)等，我們把它稱為寫讀相關(guān)。(2)在指令k+1的F1與指令k+2的左邊那個(gè)F1之間的相關(guān)關(guān)系稱為：變量名相關(guān)、先讀后寫相關(guān)、讀寫相關(guān)、反相關(guān)、RW相關(guān)、WAR相關(guān)或?qū)懞笞x相關(guān)等，我們把它稱為讀寫相關(guān)。(3)在指令k的F1與指令k+2的左邊那個(gè)F1之間的相關(guān)關(guān)系稱為：輸出相關(guān)、寫寫相關(guān)、WW相關(guān)、WAW相關(guān)或?qū)懞笤賹懴嚓P(guān)等，我們把它稱為寫寫相關(guān)。另外還有：在指令k+2的F1與指令k+3的F1之間之間有寫讀相關(guān)，在指令k+1左邊的F2與右邊的F1之間有讀寫相關(guān)。120121有些書中把相關(guān)稱為“冒險(xiǎn)”(hazard)、“竟?fàn)帯?competition)等。

三種數(shù)據(jù)相關(guān)可以用下列關(guān)系式來表示：對(duì)于寫讀相關(guān)D(i)∩S(j)≠對(duì)于讀寫相關(guān)S(i)∩D(j)≠對(duì)于寫寫相關(guān)D(i)∩D(j)≠這只是發(fā)生相關(guān)的必要條件，而不是充分條件；在執(zhí)行程序過程，只有避免數(shù)據(jù)相關(guān)，程序執(zhí)行結(jié)果才是正確的。通過建立專用路徑來避免數(shù)據(jù)相關(guān)的基本原理是數(shù)據(jù)重定向。首先介紹常用的數(shù)據(jù)重定向的一般原理和基本方法在此基礎(chǔ)上，再介紹一種經(jīng)典的避免數(shù)據(jù)相關(guān)的Tomasulo算法。1225.2.5.3數(shù)據(jù)重定向方法1、三種數(shù)據(jù)相關(guān)的重定向方法重定向之前，j只能在i之后執(zhí)行。重定向之后，分為三種情況：(1)對(duì)于寫讀相關(guān)，j與i可以同時(shí)執(zhí)行，就是專用數(shù)據(jù)通路法。(2)對(duì)于寫寫相關(guān)，j與i無先后時(shí)間順序要求。(3)對(duì)于讀寫相關(guān)，j與i無先后時(shí)間順序要求。1231242、讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)的重定向在編譯器中稱為變量換名技術(shù)，只要符合：任何變量只允許定義一次的規(guī)則，讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就自動(dòng)消除了。在三種數(shù)據(jù)相關(guān)中，實(shí)際上只有寫讀數(shù)據(jù)必須依靠硬件來解決：采用推后處理或增加專用數(shù)據(jù)通路。在上面的數(shù)據(jù)重定向圖中，把B換成了B’，讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)就不存在了。125一個(gè)依靠編譯器進(jìn)行數(shù)據(jù)重定向的例子1263、一個(gè)采用數(shù)據(jù)重定向的實(shí)際例子k：LOADF1,Ak+1：FADDF1,F2k+2：FMULF1,F3k+3：STOREF1,B專門設(shè)置A→FADD、FADD→FMUL、FMUL→B三條專用路徑，撤消F1→FADD和F1→FMUL的路徑，A→F1、FADD→F1的傳送路徑。1271285.2.5.4Tomasulo動(dòng)態(tài)調(diào)度算法在機(jī)器中實(shí)際使用的動(dòng)態(tài)調(diào)度算法主要有兩種Tomasulo算法最早在大型機(jī)IBM360/91處理機(jī)的浮點(diǎn)處理部件中被采用

又稱為公共數(shù)據(jù)總線(CDB：CommonDataBus)法，或令牌法等

分散控制的方法CDC計(jì)分牌(scorebord)算法，最先在CDC6600大型機(jī)中采用

集中控制方法。1295.2.5.4Tomasulo動(dòng)態(tài)調(diào)度算法以上面的一小段程序?yàn)槔?/p>

如果在串行執(zhí)行的處理機(jī)中，必須等待上一條指令執(zhí)行完后，下一條指令才能開始執(zhí)行。

由于浮點(diǎn)加法器和浮點(diǎn)乘法器可以同時(shí)工作，如果采用亂序流動(dòng)方式，在上面的這四條指令中可能發(fā)生“先寫后讀”和“寫-寫”兩種數(shù)據(jù)相關(guān)。

指令k的執(zhí)行結(jié)果，把一個(gè)浮點(diǎn)操作數(shù)從主存儲(chǔ)器中讀出，送入浮點(diǎn)先行讀數(shù)站的(FLB1)中，并在執(zhí)行指令k+1時(shí)通過(FLB1)直接送入到浮點(diǎn)加法器的保存站A1，而不是送到浮點(diǎn)通用寄存器F1中，這就相當(dāng)于建立了一條從主存儲(chǔ)器到浮點(diǎn)加法器的專用數(shù)據(jù)路徑。

在執(zhí)行指令k+1時(shí)，把浮點(diǎn)通用寄存器(F2)中的內(nèi)容通過FLR總線送入浮點(diǎn)加法器的保存站A1中，同時(shí)把浮點(diǎn)先行讀數(shù)站(FLB1)中的操作數(shù)通過另一條FLB總線也送入浮點(diǎn)加法器的保存站A1中，并啟動(dòng)浮點(diǎn)加法器開始工作。因?yàn)楦↑c(diǎn)加法器的運(yùn)算結(jié)果要送入F1，因此，要把浮點(diǎn)加法器保存站A1的站號(hào)“10”裝入浮點(diǎn)通用寄存器F1的站號(hào)中；另外，要把F1的“忙位”標(biāo)志置“1”，表示浮點(diǎn)通用寄存器F1中的內(nèi)容目前不能讀出作為源操作數(shù)來使用。130

由于浮點(diǎn)加法器要執(zhí)行兩個(gè)時(shí)鐘周期才能出結(jié)果，當(dāng)執(zhí)行指令k+2時(shí)，雖然可以把浮點(diǎn)通用寄存器(F3)中的內(nèi)容通過FLR總線送入浮點(diǎn)乘/除法器的保存站M1中；但是，執(zhí)行浮點(diǎn)乘法所需要的另一個(gè)操作數(shù)還不能從浮點(diǎn)通用寄存器F1中讀出；這時(shí)，改為把保存在浮點(diǎn)通用寄存器F1中的站號(hào)“10”(浮點(diǎn)加法器保存站A1的站號(hào))讀出來，并通過控制總線送入到浮點(diǎn)乘/除法器的保存站M1中，并把F1內(nèi)的站號(hào)改為浮點(diǎn)乘/除法器保存站M1的站號(hào)“8”，表示F1改從浮點(diǎn)乘/除法器接收運(yùn)算結(jié)果。

在浮點(diǎn)加法執(zhí)行完成之后，把運(yùn)算結(jié)果和保存站A1的站號(hào)“10”都送上公共數(shù)據(jù)總線CDB。通過與所有站號(hào)中保存的內(nèi)容進(jìn)行相等比較，找到浮點(diǎn)乘/除法器的保存站M1；于是，把CDB上的數(shù)據(jù)送入M1，而不是送入浮點(diǎn)通用寄存器F1；這相當(dāng)與建立了一條從浮點(diǎn)加法器到浮點(diǎn)乘/除法器的專用數(shù)據(jù)路徑。

浮點(diǎn)乘/除法器收到CDB上的數(shù)據(jù)之后就可以開始工作。在6個(gè)時(shí)鐘周期之后，浮點(diǎn)乘法的執(zhí)行結(jié)果連同保存站M1的站號(hào)都送上CDB。通過與所有站號(hào)進(jìn)行相等比較，把CDB上的數(shù)據(jù)送入到浮點(diǎn)通用寄存器F1中。

在浮點(diǎn)乘/除法器剛剛開始工作時(shí)，指令k+3開始執(zhí)行。由于浮點(diǎn)乘法的最終運(yùn)算結(jié)果還沒有出來，因此，就把保存站M1的站號(hào)“8”裝入后行寫數(shù)站的站號(hào)中。當(dāng)浮點(diǎn)乘法操作執(zhí)行結(jié)束之后，在把運(yùn)算結(jié)果通過CDB送入浮點(diǎn)通用寄存器F1的同時(shí)，也送入浮點(diǎn)后行寫數(shù)站SDB，由SDB負(fù)責(zé)把這個(gè)結(jié)果寫到主存儲(chǔ)器的B單元中。1311325.2.6全局相關(guān)(相關(guān)性分析技術(shù))5.2.6.1條件分支對(duì)流水線的影響5.2.6.2動(dòng)態(tài)分支預(yù)測(cè)技術(shù)5.2.6.3提前形成條件碼5.2.6.4精確斷點(diǎn)與不精確斷點(diǎn)1335.2.6.1條件分支對(duì)流水線的影響由條件分支或程序中斷引起的相關(guān)被稱為全局相關(guān)。全局相關(guān)對(duì)流水線的吞吐率和效率的影響相對(duì)于數(shù)據(jù)相關(guān)要大得多；處理好條件轉(zhuǎn)移和中斷的關(guān)鍵問題有兩個(gè)：一是要確保流水線能夠正常工作，二是減少因“斷流”引起的吞吐率和效率的下降。1341、條件分支的處理方法在一般程序中，條件轉(zhuǎn)移指令占五分之一左右。條件轉(zhuǎn)移指令對(duì)流水線的影響很大，必須采取措施來減少這種影響?？赡懿扇〉拇胧┯腥缦聨追N：(1)延遲轉(zhuǎn)移技術(shù)和指令取消技術(shù)只能用于單流水線標(biāo)量處理機(jī)中，而且流水線的級(jí)數(shù)不能太多；據(jù)統(tǒng)計(jì)，編譯器調(diào)度一條指令成功的概率在90%以上，而調(diào)度兩條指令成功的概率只有40%左右。當(dāng)沒有合適的指令可調(diào)度時(shí)，編譯器只能插入空操作。SUN公司的SPARC處理機(jī)，SGI公司的一部分MIPS處理機(jī)采用了延遲轉(zhuǎn)移技術(shù)。在HPPA處理機(jī)種采用了指令取消技術(shù)。135(2)靜態(tài)分支預(yù)測(cè)技術(shù)，轉(zhuǎn)移預(yù)測(cè)的方向是確定，或者預(yù)測(cè)轉(zhuǎn)移不成功，或者預(yù)測(cè)轉(zhuǎn)移成功，在程序?qū)嶋H執(zhí)行過程中，轉(zhuǎn)移預(yù)測(cè)的方向不能改變。靜態(tài)轉(zhuǎn)移預(yù)測(cè)可以只用軟件實(shí)現(xiàn)，也可用硬件來實(shí)現(xiàn)，還可以在轉(zhuǎn)移的兩個(gè)方向上都預(yù)取指令。TI公司的SuperSPARC處理機(jī)采用了靜態(tài)轉(zhuǎn)移預(yù)測(cè)技術(shù)，而且設(shè)置有轉(zhuǎn)移目標(biāo)緩沖棧，在兩個(gè)方向上都預(yù)取指令。(3)動(dòng)態(tài)分支預(yù)測(cè)技術(shù)，根據(jù)近期轉(zhuǎn)移是否成功的歷史記錄來預(yù)測(cè)下一次轉(zhuǎn)移的方向。所有的動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)方法都能夠隨程序的執(zhí)行過程動(dòng)態(tài)地改變轉(zhuǎn)移的預(yù)測(cè)方向。1362、條件分支在流水線中的執(zhí)行過程因?yàn)榈趇條指令所需要的條件碼由第i-1條指令給出；在一條由k個(gè)功能段的流水線中，第i-1條指令要等到第i+k-2條指令進(jìn)入流水線時(shí)才能形成條件碼。137如果轉(zhuǎn)移不成功的，則猜測(cè)正確，流水線的吞吐率和效率沒有降低，如果轉(zhuǎn)移成功的，則猜測(cè)錯(cuò)誤，要先作廢流水線中已經(jīng)執(zhí)行的第i+1、i+2、……、i+k-2條指令；然后，再從分支點(diǎn)開始執(zhí)行第P、p+1、……條指令。一條k段流水線有k-2個(gè)功能段是浪費(fèi)的。當(dāng)分支方向猜測(cè)錯(cuò)誤時(shí)，可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤例如，若第i+1條指令是：(R1)+(R2)→R1寄存器R1中內(nèi)容就被破壞，整個(gè)程序執(zhí)行的結(jié)果也將是錯(cuò)誤的。目前的處理機(jī)有兩種做法：一種方法是只進(jìn)行指令譯碼和準(zhǔn)備好運(yùn)算所需要的操作數(shù)，在轉(zhuǎn)移條件沒有形成之前不執(zhí)行運(yùn)算；另一種方法是一直執(zhí)行到運(yùn)算完成，但不送回運(yùn)算結(jié)果1383、條件分支對(duì)流水線性能的影響假設(shè)條件轉(zhuǎn)移指令在一般程序中所占的比例為p，轉(zhuǎn)移成功的概率為qn條指令的總的執(zhí)行時(shí)間是：TK-IF=(n+k-1)t+npq(k-1)t有條件轉(zhuǎn)移影響的流水線吞吐率為：有條件轉(zhuǎn)移影響的流水線最大吞吐率為：TPMAX-IF=流水線吞吐率下降的百分比為：D=1393、條件分支對(duì)流水線性能的影響在典型程序中，轉(zhuǎn)移指令占的比例為p=20%，轉(zhuǎn)移成功的概率為q=60%。對(duì)于一條有8個(gè)功能段的指令流水線，由于條件轉(zhuǎn)移指令的影響，流水線的最大吞吐率要下降：D8==46%如果指令流水線的功能段數(shù)為10，由于條件轉(zhuǎn)移指令的影響，流水線的最大吞吐率將下降到原來的一半以下：

D10==52%條件分支使流水線的吞吐率大約下降50%。1405.2.6.2動(dòng)態(tài)分支預(yù)測(cè)技術(shù)動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)技術(shù)的兩個(gè)問題關(guān)鍵問題：一是記錄轉(zhuǎn)移歷史信息，二個(gè)是根據(jù)所記錄的轉(zhuǎn)移歷史信息預(yù)測(cè)轉(zhuǎn)移的方向。記錄轉(zhuǎn)移歷史信息的方法有三種：第一種是把最近一次或幾次轉(zhuǎn)移是否成功的信息記錄在轉(zhuǎn)移指令中，第二種是用一個(gè)小容量的高速緩沖棧保存條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)地址，第三種是用Cache保存轉(zhuǎn)移目標(biāo)地址之后的n條指令。根據(jù)三種不同的記錄轉(zhuǎn)移歷史信息的方法，有三類動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)技術(shù)。1411、在指令Cache中記錄轉(zhuǎn)移歷史信息在指令Cache中專門設(shè)置一個(gè)字段，稱為“轉(zhuǎn)移歷史表”。在執(zhí)行轉(zhuǎn)移指令時(shí)，把轉(zhuǎn)移成功或不成功的信息記錄在這個(gè)表中。當(dāng)下次再執(zhí)行到這條指令時(shí)，轉(zhuǎn)移預(yù)測(cè)邏輯根據(jù)“轉(zhuǎn)移歷史表”中記錄的信息預(yù)測(cè)轉(zhuǎn)移成功或不成功。每一條指令一位的“轉(zhuǎn)移歷史表”，只記錄最近一次轉(zhuǎn)移是否成功的歷史信息。142在執(zhí)行條件轉(zhuǎn)移指令時(shí)，如果“轉(zhuǎn)移歷史表”中記錄的內(nèi)容是“T”，則轉(zhuǎn)移預(yù)測(cè)邏輯預(yù)測(cè)轉(zhuǎn)移成功，并按照轉(zhuǎn)移成功的方向取指令；如果記錄的是“N”，則按照轉(zhuǎn)移不成功的方向繼續(xù)取下一條指令。用本條轉(zhuǎn)移指令實(shí)際轉(zhuǎn)移是否成功的信息來修改“轉(zhuǎn)移歷史表”。143記錄最近兩次轉(zhuǎn)移是否成功的歷史信息修改“轉(zhuǎn)移歷史表”的規(guī)則是采用了一種向左移位的方法轉(zhuǎn)移預(yù)測(cè)偏向于轉(zhuǎn)移成功的，只有歷史上最近兩次執(zhí)行這條轉(zhuǎn)移指令時(shí)轉(zhuǎn)移都沒有成功，本次才預(yù)測(cè)轉(zhuǎn)移不成功，對(duì)于另外三種情況都預(yù)測(cè)轉(zhuǎn)移成功。144“轉(zhuǎn)移歷史表”的修改規(guī)則和轉(zhuǎn)移預(yù)測(cè)規(guī)則可以有多種多樣，也可以記錄轉(zhuǎn)移預(yù)測(cè)是否成功的信息。預(yù)測(cè)本次轉(zhuǎn)移方向時(shí)，也可以用最近預(yù)測(cè)是否成功的信息作為依據(jù)當(dāng)“轉(zhuǎn)移歷史表”是空白時(shí)，可以有兩種做法：一種是在“轉(zhuǎn)移歷史表”中預(yù)置轉(zhuǎn)移歷史信息。另一種是根據(jù)指令本身的偏移字段的符號(hào)來預(yù)測(cè)轉(zhuǎn)移的方向；如果偏移字段的符號(hào)是負(fù)的，則預(yù)測(cè)轉(zhuǎn)移成功，否則預(yù)測(cè)轉(zhuǎn)移不成功主要優(yōu)點(diǎn)：不必專門設(shè)置轉(zhuǎn)移緩沖棧，所記錄的轉(zhuǎn)移歷史信息比較少。DEC公司的Alpha21064超標(biāo)量超流水線處理機(jī)就采用了這種轉(zhuǎn)移預(yù)測(cè)方法，在它的一級(jí)指令Cache中有一個(gè)專門的“轉(zhuǎn)移歷史表”字段。1452、設(shè)置轉(zhuǎn)移目標(biāo)地址緩沖棧用高速緩沖棧保存最近k條轉(zhuǎn)移指令的“轉(zhuǎn)移歷史表”和轉(zhuǎn)移目標(biāo)地址“轉(zhuǎn)移指令地址”字段采用全相聯(lián)方式訪問。把當(dāng)前指令地址與轉(zhuǎn)移目標(biāo)緩沖棧中的所有轉(zhuǎn)移指令地址進(jìn)行比較；如果發(fā)現(xiàn)有相等的，則根據(jù)同一行中的“轉(zhuǎn)移歷史表”所記錄的歷史信息預(yù)測(cè)本次轉(zhuǎn)移的方向。并根據(jù)某一種規(guī)則修改“轉(zhuǎn)移歷史表”。1463、設(shè)置轉(zhuǎn)移目標(biāo)指令緩沖棧把上面方法中的轉(zhuǎn)移目標(biāo)地址改為存放轉(zhuǎn)移目標(biāo)地址之后的n條指令。預(yù)測(cè)轉(zhuǎn)移方向的規(guī)則和修改“轉(zhuǎn)移歷史表”的規(guī)則與上面的方法相同1475.2.6.3提前形成條件碼必要性：盡早產(chǎn)生條件碼對(duì)減少流水線吞吐率和效率的損失非常有效?？赡苄裕簩?duì)于大多數(shù)情況，可以在運(yùn)算實(shí)際開始之前或者在運(yùn)算中間產(chǎn)生條件碼。例如：乘法和除法，兩個(gè)源操作數(shù)符號(hào)相同結(jié)果為正，相反結(jié)果為負(fù)；有一個(gè)操作數(shù)為“0”，則乘積為“0”；被除數(shù)為“0”，則商為“0”；除數(shù)為“0”，則除法結(jié)果溢出。例如：加法和減法，同號(hào)相加，異號(hào)相減，結(jié)果的符號(hào)與第一操作數(shù)相同；異號(hào)相加，同號(hào)相減，結(jié)果的符號(hào)與絕對(duì)值大的操作數(shù)相同；溢出、是否為“0”可以通過一個(gè)比較器提前產(chǎn)生。在絕大多數(shù)情況下，只要在運(yùn)算部件的入口處設(shè)置一個(gè)比較器，就能夠提前形成結(jié)果的正負(fù)號(hào)、是否為“0”、是否溢出等條件碼。如果能夠在一個(gè)時(shí)鐘之前內(nèi)就產(chǎn)生條件碼，流水線就不會(huì)“斷流”。Amdahl470V/6在運(yùn)算部件的入口處設(shè)置一個(gè)LOCK部件來預(yù)判條件碼。1481495.2.6.4精確斷點(diǎn)與不精確斷點(diǎn)對(duì)于輸入輸出設(shè)備申請(qǐng)的中斷服務(wù)，實(shí)際上不需要有精確斷點(diǎn)。比較簡(jiǎn)單的處理方法是：讓已經(jīng)進(jìn)入流水線的所有指令都執(zhí)行完成，斷點(diǎn)就是最后進(jìn)入流水線的那條指令的地址。

對(duì)于程序性錯(cuò)誤和機(jī)器故障等引起的中斷，它們出現(xiàn)的概率很低，處理原則：不在于縮短時(shí)間，關(guān)鍵是要正確保存現(xiàn)場(chǎng)和正確恢復(fù)斷點(diǎn)。不精確斷點(diǎn)(Impreciseinterrupt)方法，精確斷點(diǎn)(Preciseinterrupt)方法。150采用不精確斷點(diǎn)法，流水線可以不“斷流”；所需要的硬件比較少，控制邏輯相對(duì)比較簡(jiǎn)單；中斷響應(yīng)時(shí)間稍長(zhǎng)，要增加一條流水線的時(shí)間長(zhǎng)度。151采用不精確斷點(diǎn)法可能會(huì)發(fā)生如下兩個(gè)問題：(1)問題是程序執(zhí)行的結(jié)果可能出錯(cuò)；例如，有如下兩條指令：i：FADDR1,R2；(R1)+(R2)→R1i+1：FMULR3,R1；(R3)×(R1)→R3當(dāng)?shù)趇條指令執(zhí)行到S6段時(shí)發(fā)現(xiàn)浮點(diǎn)加法結(jié)果溢出，于是發(fā)出中斷服務(wù)申請(qǐng)。由于采用不精確斷點(diǎn)法，要讓已經(jīng)進(jìn)入流水線的第i+1條指令也執(zhí)行完成；因?yàn)榈趇+1條指令使用了不正確的通用寄存器R1中的內(nèi)容作源操作數(shù)，因此，浮點(diǎn)乘法的執(zhí)行結(jié)果一般也是不正確的152(2)程序的調(diào)試?yán)щy.早期生產(chǎn)的一批大型流水線處理機(jī)中，有許多采用了不精確斷點(diǎn)法；近期生產(chǎn)的流水線處理機(jī)一般都采用精確斷點(diǎn)法。采用精確斷點(diǎn)法，要設(shè)置一定數(shù)量的后援寄存器，把整個(gè)流水線中所有指令的執(zhí)行結(jié)果和現(xiàn)場(chǎng)都保存下來。1535.3超標(biāo)量處理機(jī)與超流水線處理機(jī)超標(biāo)量處理機(jī)：

Intel公司的i860,i960,Pentium處理機(jī)

Motolora公司的MC88110

IBM公司的Power6000

SUN公司的SuperSPARC等。超流水線處理機(jī)：

SGI公司的MIPSR4000,R5000,R10000等。超標(biāo)量超流水線處理機(jī)：

DEC公司的Alpha等。154k段流水

線基準(zhǔn)標(biāo)

量處理機(jī)m度

超標(biāo)量n度超

流水線(m,n)度

超標(biāo)量

超流水機(jī)器類型機(jī)器流水

線周期同時(shí)發(fā)射

指令條數(shù)指令發(fā)射

等待時(shí)間指令級(jí)并

行度ILP1個(gè)時(shí)

鐘周期1條1個(gè)時(shí)

鐘周期11m1m1/n11/nn1/nm1/nm′n超標(biāo)量、超流水、超標(biāo)量超流水處理機(jī)的主要性能1555.3.1超標(biāo)量處理機(jī)一般流水線處理機(jī)：

一條指令流水線，

一個(gè)多功能操作部件，每個(gè)時(shí)鐘周期平均執(zhí)行指令的條數(shù)小于1。多操作部件處理機(jī)：

一條指令流水線，

多個(gè)獨(dú)立的操作部件，操作部件可以采用流水線，也可以不流水。多操作部件處理機(jī)的指令級(jí)并行度小于1。超標(biāo)量處理機(jī)典型結(jié)構(gòu)：

多條指令流水線

先進(jìn)的超標(biāo)量處理機(jī)有：定點(diǎn)處理部件CPU，浮點(diǎn)處理部件FPU,圖形加速部件GPU

大量的通用寄存器，兩個(gè)一級(jí)高速Cache

超標(biāo)量處理機(jī)的指令級(jí)并行度大于11565.3.1.1基本結(jié)構(gòu)Motorola公司的MC88110：

10個(gè)操作部件兩個(gè)寄存器堆

整數(shù)部件通用寄存器堆，32個(gè)32位寄存器；

浮點(diǎn)部件擴(kuò)展寄存器堆，32個(gè)80位寄存器。

每個(gè)寄存器堆有8個(gè)端口，分別與8條內(nèi)部總線相連接，有一個(gè)緩沖深度為4的先行讀數(shù)棧和一個(gè)緩沖深度為3的后行寫數(shù)棧。兩個(gè)獨(dú)立的高速Cache中，各為8KB，采用兩路組相聯(lián)方式。轉(zhuǎn)移目標(biāo)指令Cache，在有兩路分支時(shí)，存放其中一路分支上的指令157整數(shù)

部件整數(shù)

部件位

操作浮點(diǎn)加乘法

部件除法

部件圖形

部件圖形

部件內(nèi)部總線讀數(shù)/存

數(shù)部件通用寄

存器堆擴(kuò)展寄

存器堆目標(biāo)

指令指令分配

轉(zhuǎn)移部件數(shù)據(jù)Cache(8KB)指令Cache(8KB)系統(tǒng)總線32位地址總線64位數(shù)據(jù)總線超標(biāo)量處理機(jī)MC88110的結(jié)構(gòu)1585.3.1.2單發(fā)射與多發(fā)射單發(fā)射處理機(jī)：每個(gè)周期只取一條指令、只譯碼一條指令，只執(zhí)行一條指令，只寫回一個(gè)運(yùn)算結(jié)果取指部件和譯碼部件各設(shè)置一套可以只設(shè)置一個(gè)多功能操作部件，也可以設(shè)置多個(gè)獨(dú)立的操作部件操作部件中可以采用流水線結(jié)構(gòu)，也可以不采用流水線結(jié)構(gòu)設(shè)計(jì)目標(biāo)是每個(gè)時(shí)鐘周期平均執(zhí)行一條指令，ILP的期望值1159IF時(shí)鐘

周期指令I(lǐng)1I2I3IDEXWRIFIDEXWRIFIDEXWR123456單發(fā)射處理機(jī)的指令流水線時(shí)空?qǐng)D160161多發(fā)射處理機(jī)每個(gè)周期同時(shí)取多條指令、同時(shí)譯碼多條指令，同時(shí)執(zhí)行多條指令，同時(shí)寫回多個(gè)運(yùn)算結(jié)果需要多個(gè)取指令部件，多個(gè)指令譯碼部件和多個(gè)寫結(jié)果部件設(shè)置多個(gè)指令執(zhí)行部件，復(fù)雜的指令執(zhí)行部件一般采用流水線結(jié)構(gòu)設(shè)計(jì)目標(biāo)是每個(gè)時(shí)鐘周期平均執(zhí)行多條指令，ILP的期望值大于1162多發(fā)射處理機(jī)的指令流水線時(shí)空?qǐng)DIF時(shí)鐘

周期指令I(lǐng)1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR163164超標(biāo)量處理機(jī)：

一個(gè)時(shí)鐘周期內(nèi)能夠同時(shí)發(fā)射多條指令的處理機(jī)稱為超標(biāo)量處理機(jī)

必須有兩條或兩條以上能夠同時(shí)工作的指令流水線先行指令窗口：

能夠從指令Cache中預(yù)取多條指令

能夠?qū)Υ翱趦?nèi)的指令進(jìn)行數(shù)據(jù)相關(guān)性分析和功能部件沖突的檢測(cè)

窗口的大?。阂话銥?至8條指令

采用目前的指令調(diào)度技術(shù)，每個(gè)周期發(fā)射2至4條指令比較合理165例如：Intel公司的i860、i960、Pentium處理機(jī)，Motolora公司的MC88110處理機(jī)，IBM公司的Power6000處理機(jī)等每個(gè)周期都發(fā)射兩條指令TI公司生產(chǎn)的SuperSPARC處理機(jī)以及Intel的PentiumIII處理機(jī)等每個(gè)周期發(fā)射三條指令操作部件的個(gè)數(shù)多于每個(gè)周期發(fā)射的指令條數(shù)。4個(gè)至16個(gè)操作部件

超標(biāo)量處理機(jī)的指令級(jí)并行度：1＜ILP＜m；m為每個(gè)周期發(fā)射的指令條數(shù)1661675.3.1.3多流水線調(diào)度多條流水線的調(diào)度問題是一個(gè)NP完成問題。順序發(fā)射(in-orderissue)與亂序發(fā)射(out-orderissue)指令的發(fā)射順序是按照程序中的指令排列順序進(jìn)行的稱為順序發(fā)射。順序完成(in-ordercompletion)與亂序完成(out-ordercompletion)指令的完成順序按照程序中的指令排列順序進(jìn)行的稱為順序完成。多流水線的調(diào)度主要有三種方法順序發(fā)射順序完成順序發(fā)射亂序完成亂序發(fā)射亂序完成1681691、順序發(fā)射順序完成6條指令按順序分三個(gè)時(shí)鐘周期發(fā)射。6條指令共用10個(gè)時(shí)鐘周期完成。除了流水線的裝入和排空部分之外，還有8個(gè)空閑的時(shí)鐘周期。1702、順序發(fā)射亂序完成171與順序發(fā)射順序完成調(diào)度方法相比，少了5個(gè)空閑時(shí)鐘周期。6條指令總的執(zhí)行時(shí)間為9個(gè)時(shí)鐘周期與順序發(fā)射順序完成調(diào)度方法相比節(jié)省了一個(gè)時(shí)鐘周期。1723、亂序發(fā)射亂序完成采用亂序發(fā)射的指令調(diào)度方法，必須使用先行指令窗口。在采用亂序發(fā)射時(shí)，指令的完成次序必然也是亂序的。173除了裝入和排空之外，已經(jīng)沒有空閑周期，功能部件得到充分利用。6條指令總的執(zhí)行時(shí)間縮短為8個(gè)周期比順序發(fā)射順序完成方法節(jié)省兩個(gè)周期比順序發(fā)射亂序完成方法相比節(jié)省一個(gè)周期1745.3.1.4資源沖突操作部件采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性很??；如果不采用流水線結(jié)構(gòu)，發(fā)生資源沖突的可能性就大。下面是一個(gè)由4條指令程序的程序：I1：FADDR0,R1；R0←(R0)+(R1)I2：FMULR2,R3；R2←(R2)×(R3)