《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》 課件 第三章 流水線技術(shù)與向量處理技術(shù)

第三章流水線技術(shù)與向量處理技術(shù)

主講教師：單博煒計(jì)算機(jī)系統(tǒng)設(shè)計(jì)的基本任務(wù)之一就是加快指令的解釋過程。除了采用高速部件，努力提高指令內(nèi)部的并行性，從而加快單條指令的解釋過程之外，也可以采用提高指令間的并行性，從而并發(fā)地解釋兩條或兩條以上的指令，以達(dá)到提高計(jì)算機(jī)整體速度的目的。流水線技術(shù)是提高處理機(jī)指令執(zhí)行速度的主要途徑本章在并行性基本概念的基礎(chǔ)上，著重介紹重疊解釋、先行控制、流水線的工作原理與分類、流水線的性能計(jì)算方法和相關(guān)處理等基本原理，以及非線性流水線的調(diào)度方法；討論超標(biāo)量處理機(jī)和把流水線技術(shù)與超標(biāo)量技術(shù)相結(jié)合的超標(biāo)量超流水線處理機(jī)，以及超長指令字等先進(jìn)的指令級(jí)并行技術(shù)。最后闡述向量處理技術(shù)與向量處理機(jī)，絕大多數(shù)向量處理機(jī)都采用流水線結(jié)構(gòu)。

3.1流水線的基本原理重疊解釋方式先行控制流水技術(shù)原理流水線分類流水線例子1．重疊方式原理一條指令的解釋過程可分成取指、分析和執(zhí)行三個(gè)子過程取指子過程是把要處理的指令從存儲(chǔ)器里取到處理機(jī)的指令寄存器；分析子過程則包括對指令的譯碼，形成操作數(shù)真地址并取操作數(shù)，形成下一條指令地址；執(zhí)行子過程是對操作數(shù)進(jìn)行運(yùn)算并將結(jié)果寫到目標(biāo)單元中。指令的解釋方式可以有順序解釋方式和重疊解釋方式兩種順序執(zhí)行的優(yōu)點(diǎn)是控制簡單，但由于順序執(zhí)行的前一步操作未完成，后一步操作就不能開始，故其主要缺點(diǎn)是速度慢，機(jī)器各部件的利用率很低。重疊解釋方式，在解釋第k條指令的操作完成之前，就可開始解釋第k+l條指令。顯然，重疊執(zhí)行方式并不能縮短一條指令的執(zhí)行時(shí)間，但是縮短了多條指令的平均執(zhí)行時(shí)間2．重疊方式結(jié)構(gòu)為了實(shí)現(xiàn)重疊方式，處理機(jī)必須從硬件組成上符合某些原則首先，為了實(shí)現(xiàn)“執(zhí)行k”與“分析k+1”重疊，必須在硬件上保證有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件。它們有各自的控制線路，實(shí)現(xiàn)各自的功能。為此，把處理機(jī)中原來一個(gè)集中的控制器，分解為存儲(chǔ)控制器（存控）、指令控制邏輯和運(yùn)算控制器（運(yùn)部控）三個(gè)部分其次，在一般的機(jī)器上，操作數(shù)和指令是混合存儲(chǔ)于同一主存內(nèi)的，而且主存同時(shí)只能訪問一個(gè)存儲(chǔ)單元。為了解決好可能出現(xiàn)的訪存沖突讓操作數(shù)和指令分別存放于兩個(gè)獨(dú)立編址且可同時(shí)訪問的存儲(chǔ)器中。

仍維持指令和操作數(shù)混存，但采用多體交叉主存結(jié)構(gòu)。增設(shè)指令緩沖寄存器。設(shè)置指令緩沖寄存器就可以在主存空閑時(shí)，預(yù)先把下一條或下幾條指令取來存放在指令緩沖寄存器中。預(yù)取指令的最大數(shù)量取決于指令緩沖寄存器的容量，它按先進(jìn)先出的方式工作，保證指令順序不會(huì)混亂。這樣，“分析k”訪主存取操作數(shù)，“取指k+1”則從指令緩沖器中取第k+l條指令，互不干擾。而且，從指令緩沖器中取指所用時(shí)間很短，完全可以把這個(gè)微操作合并到“分析k+1”內(nèi)，從而由原來的取指、分析、執(zhí)行重疊演變成只需“執(zhí)行k”與“分析k+1”的一次重疊，如圖3.5所示?！耙淮沃丿B”解釋方式的優(yōu)點(diǎn)為節(jié)省硬件，機(jī)器只需要一套指令分析部件和指令執(zhí)行部件，同時(shí)有助于簡化控制。先行控制一次重疊方式中保證“執(zhí)行k”與“分析k+1”重疊。如果所有指令“分析”與“執(zhí)行”的時(shí)間均相等，則一次重疊的流程是非常流暢的，指令的分析和執(zhí)行部件的功能均能充分發(fā)揮，機(jī)器的速度也能顯著提高。但實(shí)際中很難做到各種類型指令的“分析”與“執(zhí)行”時(shí)間始終相等。此時(shí)，一次重疊的流程中可能出現(xiàn)如圖3.6所示的情況。這時(shí)，指令分析部件和執(zhí)行部件就不能連續(xù)、流暢的工作，從而使機(jī)器的整體速度受到影響。先行控制原理減少這種情況下機(jī)器速度損失的基本思想是運(yùn)用緩沖技術(shù)和預(yù)處理技術(shù)。緩沖技術(shù)是在兩個(gè)工作速度不同的功能部件之間設(shè)置緩沖器，用以平滑它們之間工作速度的差異。預(yù)處理技術(shù)則是把進(jìn)入運(yùn)算器的指令都處理成寄存器-寄存器型（R-R型）指令，它與緩沖技術(shù)相結(jié)合，為進(jìn)入運(yùn)算器的指令準(zhǔn)備好所需要的全部操作數(shù)。具體就是在執(zhí)行部件執(zhí)行第k條指令的同時(shí)，指令控制部件能對其后繼的第k+l、k+2、…條指令進(jìn)行預(yù)取和預(yù)處理，為執(zhí)行部件執(zhí)行新的指令做好必要而充分的前期準(zhǔn)備。先行控制結(jié)構(gòu)采用先行控制方式的處理機(jī)結(jié)構(gòu)如圖3.8所示。在指令控制部件中，除了原有指令分析器外，又增加了先行指令棧、先行讀數(shù)棧、先行操作棧和后行寫數(shù)棧。(l)先行指令棧先行指令棧的作用是后繼指令預(yù)取，保證指令分析器在順序取指時(shí)能從先行指令棧內(nèi)取到，它的作用相當(dāng)于一次重疊結(jié)構(gòu)中的指緩寄存器。先行指令棧是主存與指令分析器之間的一個(gè)緩沖部件，用于平滑主存和指令分析器之間的工作。當(dāng)指令分析器分析某條指令用時(shí)較長或主存空閑時(shí)，可就從主存中多取幾條指令存入先行指令棧備取。(2)先行讀數(shù)棧指令分析器完成指令譯碼后，經(jīng)過尋址操作得到操作數(shù)有效地址。如果仍由指令分析器向存控發(fā)取數(shù)請求信號(hào)，則必然等待存控的響應(yīng)，這就妨礙了后繼指令的連續(xù)處理。若將有效地址送先行讀數(shù)棧內(nèi)的先行地址緩沖寄存器，則指令分析器可以繼續(xù)處理后繼指令。先行讀數(shù)棧由一組先行地址緩沖寄存器、先行操作數(shù)緩沖寄存器和相應(yīng)的控制邏輯組成。每當(dāng)?shù)刂肪彌_寄存器接到有效地址后，控制邏輯主動(dòng)向存控發(fā)取數(shù)請求信號(hào)，讀出的數(shù)據(jù)送到先行數(shù)據(jù)緩沖寄存器內(nèi)。先行讀數(shù)棧以先進(jìn)先出的方式工作。運(yùn)算器直接從其讀取數(shù)據(jù)操作，不向主存取數(shù)。因此，先行讀數(shù)棧是主存和運(yùn)算器間的緩沖部件。先行讀數(shù)棧內(nèi)的數(shù)據(jù)對運(yùn)算器內(nèi)正在執(zhí)行的指令而言是屬于后繼指令執(zhí)行所需的數(shù)據(jù)，故稱“先行”。設(shè)置先行讀數(shù)棧后，將運(yùn)算器原來要訪存取操作數(shù)變?yōu)樵L問先行讀數(shù)棧中的寄存器，從而使指令的執(zhí)行速度大大加快。(3)先行操作棧指令分析器與運(yùn)算器之間的緩沖部件是先行操作棧，由一組操作命令緩沖寄有器及相應(yīng)的控制邏輯組成。由指令分析器對指令進(jìn)行預(yù)處理后送入先行操作棧。各種運(yùn)算型指令、移位指令、數(shù)據(jù)傳送指令等都要處理成寄存器-寄存器型（R-R型）指令。例如，對于變址型（R-X型）和存儲(chǔ)器型（R-S型）指令，指令分析器計(jì)算出主存有效地址后送入先行讀數(shù)棧，由先行讀數(shù)棧負(fù)責(zé)到主存讀取操作數(shù)，同時(shí)用先行讀數(shù)棧中存放這個(gè)操作數(shù)的寄存器編號(hào)替換原來指令中的主存地址碼，從而轉(zhuǎn)換成R-R型指令送入先行操作棧。為了與指令系統(tǒng)中原有的R-R型指令相區(qū)別，通常把送入先行操作棧中的指令稱為R-R*型指令。先行操作棧、是指令分析器和運(yùn)算控制器之間的一個(gè)緩沖存儲(chǔ)器，一旦運(yùn)算器空閑，運(yùn)算控制器就從先行操作棧中取出下一條R-R*型指令，運(yùn)算器需要的操作數(shù)則來自先行讀數(shù)棧或通用寄存器中。同樣，先行操作棧內(nèi)命令對于運(yùn)算器內(nèi)正在執(zhí)行的命令而言是“先行”的。(4)后行寫數(shù)棧如果指令分析器遇到向主存寫數(shù)的指令，則把形成的主存有效地址送入后行寫數(shù)棧的后行地址緩沖寄存器中，并把預(yù)處理好的RR*型指令送入先行操作棧，這條R-R*型指令中的目標(biāo)寄存器就是后行寫數(shù)棧的緩沖寄存器編號(hào)。當(dāng)運(yùn)算器執(zhí)行這條RR*型寫數(shù)指令時(shí)，只需將數(shù)據(jù)送人后行寫數(shù)緩沖寄存器即可，不與主存打交道，可繼續(xù)執(zhí)行后繼命令。后行寫數(shù)棧由一組后行地址緩沖寄存器、后行寫數(shù)緩沖寄存器，及相應(yīng)控制邏輯組成。每當(dāng)接到運(yùn)算器送來的要寫入主存的數(shù)據(jù)，由控制邏輯白動(dòng)地向主存發(fā)寫數(shù)請求信號(hào)，由后行寫數(shù)棧負(fù)責(zé)把后行寫數(shù)緩沖寄存器中的數(shù)據(jù)按后行地址緩沖寄存器中的主存地址送人主存。它是運(yùn)算器和主存間的緩沖部件。由于后行寫數(shù)棧中寫回的數(shù)據(jù)，對于運(yùn)算器中正在執(zhí)行的命令而言，是先前命令“滯后”寫回的數(shù)據(jù)，故叫后行寫數(shù)棧。它也是按先進(jìn)先出方式工作的。1．流水處理方式流水線技術(shù)就是將一個(gè)完整的處理過程分解為若干個(gè)子過程，而每個(gè)子過程都可以有效地在其專用功能部件上與其他子過程對不同的對象同時(shí)執(zhí)行。處理機(jī)可以在不同級(jí)別上采用流水線方式工作。在一次重疊方式中，把一條指令解釋過程分解為“分析”與“執(zhí)行”兩個(gè)子過程，分別在獨(dú)立的分析部件和執(zhí)行部件上進(jìn)行。描述流水線的工作過程，常采用時(shí)-空圖的方法。時(shí)-空圖的橫坐標(biāo)表示時(shí)間，縱坐標(biāo)表示流水線的各功能部件，每個(gè)功能部件通常稱為一個(gè)功能段。圖3.10所示的是由這四個(gè)過程段構(gòu)成的流水線連續(xù)對六條指令的流水處理過程和相應(yīng)的時(shí)-空圖?！傲魉痹诟拍钌吓c“重疊”沒有什么差別，可以看成是“重疊”的進(jìn)一步引申：只是“一次重疊”把一條指令的解釋分解為兩個(gè)子過程，而“流水”則是分解成更多個(gè)子過程。前者同時(shí)解釋兩條指令，后者可同時(shí)解釋多條指令。應(yīng)該注意的是，只有當(dāng)流水線正常滿負(fù)荷流動(dòng)時(shí)，才會(huì)每隔Δt流出一個(gè)結(jié)果。流水線從開始啟動(dòng)工作到流出第一個(gè)結(jié)果，需要經(jīng)過一段流水線的建立時(shí)間，在這段時(shí)間里流水線并沒流出任何結(jié)果。在計(jì)算機(jī)實(shí)際的流水線中，各子部件經(jīng)過的時(shí)間會(huì)有差異。為解決各子部件處理速度的差異，一般在子部件之間需設(shè)置高速接口鎖存器。所有鎖存器都受同一時(shí)鐘信號(hào)控制，以實(shí)現(xiàn)各子部件信息流的同步推進(jìn)。時(shí)鐘信號(hào)周期不得低于速度最慢子部件的經(jīng)過時(shí)間與鎖存器的存取時(shí)間之和，還要考慮時(shí)鐘信號(hào)到各鎖存器可能存在的時(shí)延差。因此，子過程的細(xì)分，會(huì)因鎖存器數(shù)增多而增大指令流過流水線的時(shí)間，這在一定程度上會(huì)抵消子過程細(xì)分而使流水線吞吐率得到提高的好處。2．流水線的特點(diǎn)(l)流水線可以劃分為若干個(gè)互有聯(lián)系的子過程（功能段）。每個(gè)功能段有專用功能部件實(shí)現(xiàn)對任務(wù)的某種如工。(2)實(shí)現(xiàn)子過程的功能段所需時(shí)間應(yīng)盡可能相等，避免因時(shí)間不等而產(chǎn)生的處理瓶頸。這在設(shè)計(jì)流水線的控制線路及計(jì)算流水線的性能方面會(huì)帶來方便，簡化設(shè)計(jì)。但在實(shí)際機(jī)器中，各流水段所需的時(shí)間很難保證一致。(3)流水線工作狀態(tài)可分為建立、滿載和排空三個(gè)階段。從第一個(gè)任務(wù)進(jìn)入流水線到流水線所有的部件都處于工作狀態(tài)的這一個(gè)時(shí)期，稱為流水線的建立階段。當(dāng)所有部件都處于工作狀態(tài)時(shí)，稱為流水線的滿載階段。從最后一個(gè)任務(wù)流人流水線到結(jié)果流出，稱為流水線的排空階段。在理想情況下，當(dāng)流水線充滿后，每隔Δt時(shí)間將會(huì)有一個(gè)結(jié)果流出流水線。(4)由于各種原因使指令流不能連續(xù)執(zhí)行時(shí)，會(huì)使流水過程中斷，而重新形成流水過程則需要通過時(shí)間，所以流水過程不應(yīng)?！皵嗔鳌?，否則流水線效率就不會(huì)很高。因此，流水技術(shù)適用于大量重復(fù)的程序過程，只有在輸入端連續(xù)地提供服務(wù)，流水線效率才能夠充分發(fā)揮。流水線的分類從不同的角度，可對流水線進(jìn)行不同的分類。按流水線具有的功能分類流水線可以分為單功能流水線和多功能流水線。單功能流水線(unifunctionpipelining)是指只能完成一種固定功能的流水線。如Pentium有一條五段的定點(diǎn)和一條八段的浮點(diǎn)流水線。在計(jì)算機(jī)中要實(shí)現(xiàn)多個(gè)功能，必須采用多個(gè)單功能流水線。多功能流水線(multifuncitonpipelining)是指同一流水線的各個(gè)段之間可以有多種不同的連接方式，以實(shí)現(xiàn)多種不同的運(yùn)算或功能。例如，美國Texas公司的ASC計(jì)算機(jī)運(yùn)算器的流水線就是多功能的，它有八個(gè)可并行丁作的獨(dú)立功能段，如圖3.11(a)所示，能夠?qū)崿F(xiàn)定點(diǎn)加/減法、定點(diǎn)乘法、浮點(diǎn)加／減法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。

TI-ASC機(jī)器要進(jìn)行浮點(diǎn)加、減法時(shí)，其流水線功能段的連接如圖3.11(b)所示；而要進(jìn)行定點(diǎn)乘法運(yùn)算時(shí)，其流水線功能段的連接如圖3.11(c)所示。按流水線多種功能的連接分類按多功能流水線的各段能否允許同時(shí)用于多種不同功能連接流水，可把流水線分為靜態(tài)流水線和動(dòng)態(tài)流水線。靜態(tài)流水線(staticpipelining)是指在同一時(shí)間內(nèi)，多功能流水線中的各個(gè)功能段只能按一種功能的連接方式丁作。只有當(dāng)按照這種連接流入的所有處理的對象都流出流水線之后，多功能流水線才能重新進(jìn)行連接以實(shí)現(xiàn)其他功能。以TII-ASC機(jī)器的流水線為例，如果按照圖3.12所示的時(shí)-空圖工作，那么就是一種靜態(tài)流水線動(dòng)態(tài)流水線(dynamicpipelining)是指在同一時(shí)間內(nèi)，多功能流水線中的各個(gè)功能段可以實(shí)現(xiàn)多種連接，同時(shí)執(zhí)行多種功能。圖3.13比較圖3.12和圖3.13，得出靜態(tài)流水線與動(dòng)態(tài)流水線的差別在于：對于相同的一串運(yùn)算功能不同的指令而言，動(dòng)態(tài)流水線的吞吐率和設(shè)備利用率比靜態(tài)流水線的高。由于在同一時(shí)間內(nèi)，要通過不同的連接實(shí)現(xiàn)不同的運(yùn)算，因而動(dòng)態(tài)流水線的控制比靜態(tài)流水線要復(fù)雜，這就需增加相應(yīng)硬件，故成本比靜態(tài)流水線的高。從軟、硬件功能分配的觀點(diǎn)上看，靜態(tài)流水線把功能負(fù)擔(dān)較多地加到軟件上，要求程序員編寫出（或是編譯程序生成）的程序應(yīng)盡可能有更多相同運(yùn)算的指令串，以提高其流水的效能，簡化硬件控制，而動(dòng)態(tài)流水線則把功能負(fù)擔(dān)較多地加在硬件控制上，以提高流水的效能。按流水線的級(jí)別分類按流水處理的級(jí)別不同，可以把流水線分為部件級(jí)流水線、處理機(jī)級(jí)流水線和系統(tǒng)級(jí)流水線。部件級(jí)流水線，又稱運(yùn)算操作流水線(arithmeticpipelining)．它是指處理機(jī)功能部件內(nèi)部分段，采用流水操作來實(shí)現(xiàn)功能。例如，對于一些比較復(fù)雜的運(yùn)算操作部件，如浮點(diǎn)加法器、浮點(diǎn)乘法器等，一般要采用多級(jí)流水線來實(shí)現(xiàn)。后行寫數(shù)棧和先行讀數(shù)棧都要實(shí)現(xiàn)訪存操作，也可以采用多級(jí)流水線來實(shí)現(xiàn)。處理機(jī)級(jí)流水線又稱為指令流水線(instructionpipelining)．它是把一條指令的解釋過程分解為多個(gè)子過程，每個(gè)子過程在一個(gè)獨(dú)立的功能部件中完成。組成先行控制器的各個(gè)部件實(shí)際上也構(gòu)成了一條流水線，它把指令過程被分解為五個(gè)子過程，用五個(gè)專用功能段進(jìn)行流水處理，如圖3.14所示。系統(tǒng)級(jí)流水線又稱為宏流水線(macropipelining)，如圖3.15所示。這種流水線由兩個(gè)或兩個(gè)以上的處理機(jī)通過存儲(chǔ)器串行連接起來，每個(gè)處理機(jī)對同一數(shù)據(jù)流的不同部分分別進(jìn)行處理，前一個(gè)處理機(jī)的輸出結(jié)果存人存儲(chǔ)器中，作為后一個(gè)處理機(jī)的輸入，每個(gè)處理機(jī)完成整個(gè)任務(wù)中的一部分。按流水線的連接方式分類按照流水線的各功能段之間是否有反饋回路，可以把流水線分為線性流水線和非線性流水線。線性流水線(linepipelining)是指流水線各段串行連接，數(shù)據(jù)順序流經(jīng)流水線各段一次且僅流過一次。圖3.10所示的指令流水線就屬于線性流水線。非線性流水線(nonlinearpipelining)是指在流水線各段之間除有串行連接之外，還有某種反饋回路，使一個(gè)任務(wù)流經(jīng)流水線時(shí)，需多次經(jīng)過某個(gè)段或越過某些段。非線性流水線常用于遞歸調(diào)用或組成多功能流水線，如圖3.16所示。按數(shù)據(jù)表示分類以機(jī)器所具有的數(shù)據(jù)表示可以把流水線處理機(jī)分為標(biāo)量流水處理機(jī)和向量流水處理機(jī)。標(biāo)量流水處理機(jī)只能對標(biāo)量數(shù)據(jù)進(jìn)行處理，它沒有向量數(shù)據(jù)表示，只能用標(biāo)量循環(huán)方式來對向量、數(shù)組進(jìn)行處理。向量流水處理機(jī)則指的是機(jī)器具有向量數(shù)據(jù)表示，設(shè)置有向量指令和向量運(yùn)算硬件，能對向量、數(shù)組中的各個(gè)元素流水的處理。向量流水處理機(jī)是向量數(shù)據(jù)表示和流水技術(shù)的結(jié)合。流水線性能分析衡量流水線性能的主要指標(biāo)有吞吐率、加速比和效率。本節(jié)以線性流水線為例，分析流水線的主要性能指標(biāo)。該分析方法也適用于非線性流水線。吞吐率吞吐率(TP，ThroughputRate)是指單位時(shí)間內(nèi)流水線能夠處理的任務(wù)數(shù)（或指令數(shù)）或流水線能輸出的結(jié)果的數(shù)量，它是衡量流水線速度的主要性能指標(biāo)。最大吞吐率Tpmax：是指在流水線正常滿負(fù)荷工作時(shí)，單位時(shí)間內(nèi)機(jī)器所能處理的最多指令條數(shù)或機(jī)器能輸出的最多結(jié)果數(shù)。(2)實(shí)際吞吐率TP：流水線的實(shí)際吞吐率TP是指從啟動(dòng)流水線處理機(jī)開始到流水線操作結(jié)束，單位時(shí)間內(nèi)能流出的任務(wù)數(shù)或能流出的結(jié)果數(shù)。實(shí)際吞吐率TP總是小于最大吞吐率TPmax。各段執(zhí)行時(shí)間相等的吞吐率若一條m段線性流水線．各段執(zhí)行時(shí)間相等，均為Δt0，當(dāng)有n個(gè)任務(wù)連續(xù)流人流水線時(shí)，流水線的工作過程可用如圖3.17所示的時(shí)-空圖表示。m段流水線的完成n個(gè)任務(wù)所需時(shí)間T為實(shí)際吞吐率為當(dāng)n趨于無窮大時(shí)，TP達(dá)到最大各段執(zhí)行時(shí)間不等的吞吐率當(dāng)流水線各段執(zhí)行時(shí)間不相等時(shí)，為了使各段之間的時(shí)間匹配，需要在各子過程之間插入鎖存器，這些鎖存器受同一個(gè)時(shí)鐘脈沖的控制，從而達(dá)到同步。若一條m段線性流水線各段執(zhí)行時(shí)間分別為Δt1，Δt2，Δt3，…，Δtm，則時(shí)鐘周期應(yīng)為max{Δt1，Δt2，Δt3，…，Δtm}，流水線的最大吞吐率為TPmax=1/max{Δt1，Δt2，Δt3，…，Δtm}顯然，流水線的最大吞吐率取決于流水線中最慢子過程所需要的時(shí)間。我們把流水線中經(jīng)過時(shí)間最長的子過程稱為“瓶頸”子過程。該流水線完成行個(gè)任務(wù)的實(shí)際吞吐率為式中，tj為瓶頸段的經(jīng)過時(shí)間。[例3.1]一個(gè)四段線性流水線，各段執(zhí)行時(shí)間不等，如圖3.18(a)所示。求流水線最大吞吐率和連續(xù)輸入n個(gè)任務(wù)的實(shí)際吞吐率。解：圖中S1、S3、S4段的處理時(shí)間均為Δt，而S2段的處理時(shí)間需要3Δt，故S2段是該流水線的瓶頸段。根據(jù)流水線的最大吞吐率公式，其最大吞吐率為該流水線滿負(fù)荷工作時(shí)，每隔3Δt才能輸出一個(gè)結(jié)果。其時(shí)-空圖如圖3.18(b)所示。流水線連續(xù)輸入n個(gè)任務(wù)的實(shí)際吞吐率為瓶頸段的存在是引起流水線吞吐率下降的重要原因，必須找出并設(shè)法消除流水線中的瓶頸，才能提高流水線的吞吐率。消除瓶頸段，提高流水線吞吐率的方法(l)瓶頸子過程細(xì)分將圖3.18(a)歷示的瓶頸段S2進(jìn)一步分離為三個(gè)子功能段S21、S22和S23，并且各子功能段的執(zhí)行時(shí)間均為Δt，把原來執(zhí)行時(shí)間不等的四段流水線改造為如圖3.19所示的執(zhí)行時(shí)間相等的六段流水線。瓶頸段分離后流水線的最大吞吐率為由于可間隔一個(gè)Δt輸入一個(gè)任務(wù)，流水線連續(xù)輸入n個(gè)任務(wù)的實(shí)際吞吐率為(2)瓶頸段部件重復(fù)設(shè)置由于結(jié)構(gòu)等方面的原因，并不是所有子過程都可以進(jìn)一步細(xì)分。那么，可以采用重復(fù)設(shè)置瓶頸段部件，讓多個(gè)瓶頸段并行工作來消除瓶頸段原執(zhí)行時(shí)間的“瓶頸”。如對圖3.18(a)所示流水線的瓶頸段S2，可再增設(shè)兩個(gè)相同的段，并分別以S2a、S2b、S2c命名，如圖3.20(a)所示。S1間隔Δt輪流給各瓶頸段提供任務(wù)，使它們?nèi)钥擅扛籀解釋完一條指令，其時(shí)-空圖如圖3.20(b)所示。流水線的最大吞吐率為TPmax=l/Δt，連續(xù)輸入n個(gè)任務(wù)的實(shí)際吞吐率為這種辦法需要解決好在各并行子過程之間的任務(wù)分配和同步控制，與瓶頸子過程細(xì)分方法相比，控制要復(fù)雜些，設(shè)備量要多些。加速比流水線的加速比Sp(speedupratio)是指流水方式與非流水線順序方式工作，完成同樣任務(wù)量時(shí)的工作速度提高的比值。1．各段執(zhí)行時(shí)間相等的加速比

流水線完成這n個(gè)任務(wù)所用的時(shí)間為Tm=(m+n-1)Δt順序執(zhí)行這n個(gè)任務(wù)，則所用的時(shí)間為T0

=n·m·Δt。加速比為當(dāng)

時(shí)，流水線的加速比Sp接近于流水線的段數(shù)m2．各段執(zhí)行時(shí)間不等的加速比

如果流水線各功能段的執(zhí)行時(shí)間不相等，其中“瓶頸”段經(jīng)過的時(shí)間為Δtj，則一條m段線性流水線完成n個(gè)連續(xù)輸入的任務(wù)時(shí)，此流水線的實(shí)際加速比為效率流水線的效率η(efficiency)是指流水線的設(shè)備利用率，即流水線在整個(gè)運(yùn)行時(shí)間里，流水線的設(shè)備實(shí)際使用時(shí)間所占的比率。由于流水線存在有建立時(shí)間和排空時(shí)間，在連續(xù)完成n個(gè)任務(wù)的時(shí)間里，各段并不是滿負(fù)荷T作的，所以流水線的效率一定小于1。1．各段執(zhí)行時(shí)間相等的效率從時(shí)-空圖上看，流水線的效率即為n個(gè)任務(wù)占用的時(shí)空區(qū)與m個(gè)功能段總的時(shí)空區(qū)面積之比。2．各段執(zhí)行時(shí)間不等的效率如果流水線各功能段的執(zhí)行時(shí)間不等，則各段的效率也不等，若其中“瓶頸”段的經(jīng)過時(shí)間為Δtj，則一條m段線性流水線連續(xù)輸入，n個(gè)任務(wù)時(shí)．整個(gè)流水線的效率為流水線的效率仍然是n個(gè)任務(wù)占用的時(shí)空區(qū)和m個(gè)段總的時(shí)空區(qū)面積之比。[例3.2]設(shè)有兩個(gè)向量A、B，各有四個(gè)元素，要在如圖3.21所示的靜態(tài)雙功能流水線上計(jì)算向量點(diǎn)積A·B。在該雙功能流水線中，S1→S2→S3→S5組成加法流水線，S1→S4→S5組成乘法流水線。設(shè)每個(gè)流水段所經(jīng)過的時(shí)間為Δt，而且流水線的輸出結(jié)果可以直接返回到輸入或暫存于相應(yīng)的緩沖寄存器中，其延遲時(shí)間和功能切換時(shí)間忽略不計(jì)。求出流水線完成此運(yùn)算工作期間的實(shí)陳吞吐率TP和效率η。解：首先選擇合理的算法，使完成向量點(diǎn)積A·B運(yùn)算所用的時(shí)間最短，其算法如下。(1)功能部件連接構(gòu)成乘法流水線，連續(xù)計(jì)算a1×b1、a2×b2

、a3×b3、a4×b4，得到四個(gè)乘積項(xiàng)。(2)等執(zhí)行乘法工作的流水線排空后，進(jìn)行功能部件的切換連接，構(gòu)成加法運(yùn)算的流水線，并連續(xù)計(jì)算（a1×b1+a2×b2）、（a3×b3+a4×b4），得到兩個(gè)部分積。(3)產(chǎn)生了上述兩個(gè)結(jié)果后，再計(jì)算（a1×b1+a2×b2）+（a3×b3+a4×b4）最終得到向量點(diǎn)積。此過程總共流入多功能流水線的任務(wù)數(shù)為七個(gè)，完成任務(wù)所需的時(shí)間為15Δt，該流水線的實(shí)際吞吐率為順序完成這七個(gè)任務(wù)需要的時(shí)間為4×3Δt+3×4Δt=24Δt，故流水線的效率為[例3.3]上例圖3.21(a)中所示如果是動(dòng)態(tài)雙功能流水線，其他條件不變。那么，在計(jì)算向量點(diǎn)積期間，流水線的吞吐率TP和效率η又是多少呢？解：動(dòng)態(tài)流水線完成此運(yùn)算的時(shí)-空圖如圖3.22所示由圖3.22中可以看出，進(jìn)人流水線的任務(wù)數(shù)還是七個(gè)，但所需要的時(shí)間比靜態(tài)流水線少Δt，只需要14Δt就可完成。因此，此期間動(dòng)態(tài)流水線的實(shí)際吞吐率為流水線的效率為從以上兩個(gè)例子可以看出，動(dòng)態(tài)流水線與靜態(tài)流水線相比，由于不同功能可以重疊處理，所以具有較高的實(shí)際吞吐率和效率。3.3流水線中的相關(guān)及處理流水線只有在連續(xù)不斷的工作的狀態(tài)下才能發(fā)揮高效率，所以應(yīng)盡量避免其斷流情況的出現(xiàn)。導(dǎo)致流水線斷流的原因可能有編譯形成的目標(biāo)程序不能發(fā)揮流水結(jié)構(gòu)的作用，或者存儲(chǔ)系統(tǒng)不能為連續(xù)流動(dòng)提供所需的指令和操作數(shù)。除此之外，就是由于出現(xiàn)了相關(guān)和中斷。所謂“相關(guān)”，是指由于機(jī)器語言程序的鄰近指令之間出現(xiàn)了某種關(guān)聯(lián)后，為了避免出錯(cuò)而使得它們不能同時(shí)被解釋的現(xiàn)象。流水線的相關(guān)分為局部性相關(guān)和全局性相關(guān)兩類。局部性相關(guān)(localcorrelation)對程序執(zhí)行過程的影響較小，它僅涉及到相關(guān)指令前后的一條或幾條指令的執(zhí)行；全局性相關(guān)(globalcorrelation)是指影響整個(gè)程序執(zhí)行方向的相關(guān)，主要是轉(zhuǎn)移類指令和中斷引起的相關(guān)。局部性相關(guān)及處理局部性相關(guān)包括指令相關(guān)、主存窄間數(shù)相關(guān)和通用寄存器組數(shù)相關(guān)等。如果第k+l條指令是經(jīng)第k條指令的執(zhí)行來形成的，由于在“執(zhí)行k”的末尾才形成第k+1條指令，第k、k+l條指令就不能同時(shí)解釋，此時(shí)稱這兩條指令之間發(fā)生了“指令相關(guān)”。如果第k+l條指令的源操作數(shù)地址i正好是第k條指令存放運(yùn)算結(jié)果的地址，在笫k、k+1條指令的數(shù)據(jù)地址之間有了關(guān)聯(lián)，稱為發(fā)生了“數(shù)相關(guān)”。通用寄存器數(shù)相關(guān)則是相鄰指令之間出現(xiàn)要求對同一通用寄存器先寫后讀的關(guān)聯(lián)。若讀出的內(nèi)容是操作數(shù)，則是通用寄存器數(shù)相關(guān)；若讀出的內(nèi)容是變址值，則是通用寄存器變址值相關(guān)。順序流動(dòng)的相關(guān)順序流動(dòng)方式是指任務(wù)從流水線輸出端流出的順序同它們進(jìn)入流水線輸入端的順序一樣。如圖3.23所示，有一個(gè)八段的流水線，其中第二段為讀段，第七段為寫段。有一串指令h、i、j、k、l、m…依次流入．如果指令j的源操作數(shù)地址與指令h的目的操作數(shù)地址相同，而當(dāng)指令j到達(dá)讀段時(shí)，指令h還沒有到達(dá)寫段完成寫入操作，則指令j讀出的數(shù)據(jù)就是錯(cuò)誤的，指令h和j就發(fā)生了先寫后讀的操作數(shù)相關(guān)。解決順序流動(dòng)的“先寫后讀”(RAW，ReadAfterWrite)相關(guān)的方法是：要求指令j流到讀段時(shí)停止在流水線中流動(dòng)，直到指令h到達(dá)寫段并完成寫入后，j與其后的指令才能繼續(xù)向前流動(dòng)。這是一種推后對相關(guān)單元讀的處理方法，其優(yōu)點(diǎn)是控制實(shí)現(xiàn)比較簡單，缺點(diǎn)是推后期間流水線中出現(xiàn)空段，降低了流水線的吞吐率和效率。相關(guān)專用通路解決“先寫后讀”相關(guān)的另一種方法是建立相關(guān)專用通路，即在流水線的讀段與寫段之間增加一條專用的數(shù)據(jù)通路。推后的方法是以增加時(shí)間為代價(jià)，降低速度來解決相關(guān)問題；相關(guān)專用通路是以增加設(shè)備為代價(jià)，提高成本來解決相關(guān)問題。異步流動(dòng)的相關(guān)異步流動(dòng)方式是指任務(wù)從流水線輸出端流出的順序同它們進(jìn)入流水線輸入端的順序可以不一樣。異步流動(dòng)也稱為亂序(outoforder)流動(dòng)或錯(cuò)序流動(dòng)。在順序流動(dòng)方式中，當(dāng)指令j與它前面的指令h發(fā)生相關(guān)時(shí)，指令j及其之后的指令串都停止流動(dòng)，以期保持指令串流人與流出順序一致。但是，如果指令j以后的指令與進(jìn)入流水線的全部指令之間都沒有相關(guān)問題，那么完全可以僅使相關(guān)的指令j暫停流動(dòng)，而其后的指令依次越過指令j繼續(xù)向前流動(dòng)，這樣就使得指令串流出的次序同它們流入的次序不一樣了。這就是異步流動(dòng)，如圖3.23所示。在異步流動(dòng)時(shí)除了出現(xiàn)“先寫后讀”相關(guān)外，還可能會(huì)發(fā)生在順序流動(dòng)中不會(huì)出現(xiàn)的其他類型的相關(guān)。例如，指令i、k是都有寫操作，而且是寫入同一單元，那該單元的最后內(nèi)容本應(yīng)是指令k的寫入結(jié)果。但是，若采用異步流動(dòng)方式，則可能出現(xiàn)指令k先于指令i到達(dá)寫段，從而使得該單元的最后內(nèi)容錯(cuò)為指令i的寫入結(jié)果。我們稱這種對同一單元要求在先的指令先寫入，在后的指令后寫入的關(guān)聯(lián)為“寫后寫”相關(guān)(WAW，WriteAfterWrite)。另外，如果指令i的讀操作和指令k的寫操作是對應(yīng)于同一單元的，則指令i讀出的本應(yīng)是該單元的原存內(nèi)容。若采用異步流動(dòng)方式，則可能出現(xiàn)指令是的寫操作先于指令i的讀操作被執(zhí)行，那么指令i讀取的數(shù)據(jù)就會(huì)錯(cuò)誤的為指令j寫入的數(shù)據(jù)。我們稱這種對同一單元，要求在先的指令先讀出，在后的指令后寫入的關(guān)聯(lián)為“先讀后寫”相關(guān)(WAR，WriteAfterRead)。顯然，“寫后寫”相關(guān)和“先讀后寫”相關(guān)都只有在異步流動(dòng)時(shí)才有可能發(fā)生，順序流動(dòng)時(shí)是不可能發(fā)生的。異步流動(dòng)方式的優(yōu)點(diǎn)是流水線的吞吐率和和效率都不會(huì)下降，缺點(diǎn)是異步流動(dòng)的控制復(fù)雜，在設(shè)計(jì)采用異步流動(dòng)方式T作時(shí)，控制機(jī)構(gòu)必須解決好超越和新出現(xiàn)的兩種相關(guān)。全局性相關(guān)及處理全局性相關(guān)指的是已進(jìn)入流水線的轉(zhuǎn)移指令（尤其是條件轉(zhuǎn)移指令）和其后面的指令之間的相關(guān)。若指令i是條件轉(zhuǎn)移指令，它有兩個(gè)分支，如圖3.24所示。一個(gè)分支是i+l、i+2、i+3、…，按原來的順序繼續(xù)執(zhí)行下去，稱轉(zhuǎn)移不成功分支；另一個(gè)分支是轉(zhuǎn)向h，然后繼續(xù)執(zhí)行h+1、h+2、…，稱為轉(zhuǎn)移成功分支。流水方式是同時(shí)解釋多條指令的，因此，當(dāng)指令i進(jìn)入流水線時(shí)，后面進(jìn)i+l還是進(jìn)h，只有等條件碼建立才能知道，而這一般要等該條件轉(zhuǎn)移指令快流出流水線時(shí)，如果在此期間讓i之后的指令等著，流水線就會(huì)“斷流”，性能將會(huì)急劇下降。對于一條有k個(gè)流水段的流水線，若流水線的時(shí)鐘周期為Δt，由于條件轉(zhuǎn)移指令的影響，在最壞情況下，每一次條件轉(zhuǎn)移將造成k-l個(gè)時(shí)鐘周期的“斷流”。另外，假設(shè)條件轉(zhuǎn)移指令在一般程序中所占的比例為p，轉(zhuǎn)移成功的概率為q，則對于一個(gè)由n條指令組成的程序，由于條件轉(zhuǎn)移需要額外增加的時(shí)鐘周期數(shù)是npq（k-l）Δt，因此，這n條指令總的執(zhí)行時(shí)間是有條件轉(zhuǎn)移影響的流水線的吞吐率為流水線的最大吞吐率為流水線吞吐率下降的百分比為[例3.4]據(jù)統(tǒng)計(jì)，在一些典型程序中，轉(zhuǎn)移指令所占的比例為20%，轉(zhuǎn)移成功的概率為q=60%。假設(shè)有一條八個(gè)流水段的指令流水線，那么，由于條件轉(zhuǎn)移指令的影響，流水線的最大吞吐率下降多少？解：已知p=0.20，q=0.60，k=8由于條件轉(zhuǎn)移指令在一般程序中所占的比例較大，所以處理好條件轉(zhuǎn)移引起的全局相關(guān)是很重要的。為了在遇到條件轉(zhuǎn)移指令時(shí)，流水線仍能繼續(xù)向前流動(dòng)，不使吞吐率和效率下降，絕大多數(shù)機(jī)器都采用所謂的“猜測法”，即轉(zhuǎn)移預(yù)測技術(shù)——猜選按轉(zhuǎn)移成功和轉(zhuǎn)移不成功分支中的一個(gè)繼續(xù)向前流動(dòng)。1．靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)所謂靜態(tài)轉(zhuǎn)移頂測是指在處理機(jī)的硬件和軟件設(shè)計(jì)完成之后，轉(zhuǎn)移猜測方向就已經(jīng)被確定了——或者是轉(zhuǎn)移不成功方向，或者是轉(zhuǎn)移成功方向。靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)可以有兩種實(shí)現(xiàn)方法。一種是分析程序結(jié)構(gòu)本身的特點(diǎn)或使用該程序以前運(yùn)行時(shí)收集的模擬信息。另一種是按照分支的方向來預(yù)測分支是否轉(zhuǎn)移成功。當(dāng)兩者概率差不多時(shí)，一般選取轉(zhuǎn)移不成功分支，IBM360／91就采用轉(zhuǎn)移不成功分支。2．動(dòng)態(tài)轉(zhuǎn)移預(yù)測技術(shù)動(dòng)態(tài)轉(zhuǎn)移預(yù)測是根據(jù)近期轉(zhuǎn)移是否成功的歷史記錄來預(yù)測下一次轉(zhuǎn)移的方向。動(dòng)態(tài)轉(zhuǎn)移預(yù)測的關(guān)鍵有兩點(diǎn)：一是如何記錄轉(zhuǎn)移歷史信息，二是如何根據(jù)記錄的轉(zhuǎn)移歷史信息預(yù)測轉(zhuǎn)移的方向。3．延遲轉(zhuǎn)移技術(shù)延遲轉(zhuǎn)移技術(shù)是依靠編譯器把轉(zhuǎn)移指令之前的一條或幾條沒有數(shù)據(jù)相關(guān)和控制相關(guān)的指令調(diào)整到轉(zhuǎn)移指令的后面。當(dāng)轉(zhuǎn)移指令進(jìn)入流水線之后，由這些指令填充流水線的各功能段似保證流水線不斷流，且又不會(huì)出現(xiàn)相關(guān)問題，直到轉(zhuǎn)移條件碼建立。延遲轉(zhuǎn)移技術(shù)一般只用于單流水線標(biāo)量處理機(jī)中，而且流水線的段數(shù)不能太多，因?yàn)槎螖?shù)越多，需要調(diào)整到轉(zhuǎn)移指令之后的沒有數(shù)據(jù)相關(guān)和控制相關(guān)的指令條數(shù)也越多。據(jù)統(tǒng)計(jì)，編譯器只調(diào)整一條指令的成功概率在90%以上，調(diào)整兩條指令的成功概率只有40%左右。當(dāng)沒有合適的指令可供調(diào)整時(shí)，編譯器只能在轉(zhuǎn)移指令之后插入空操作指令。SUN公司的SPARC處理機(jī)、HP公司的HPPA處理機(jī)和SG公司的一部分MIPS處理機(jī)都采用了延遲轉(zhuǎn)移技術(shù)。4．加快和提前形成條件碼采取措施盡快、盡早地獲得條件碼以便提前知道程序流向哪個(gè)分支，將有利于流水機(jī)器簡化對條件轉(zhuǎn)移的處理。由前可知，條件轉(zhuǎn)移指令造成流水線性能下降的主要原因是條件碼形成得太晚。很多時(shí)候，條件轉(zhuǎn)移指令的轉(zhuǎn)移條件碼是由上一條運(yùn)算型指令產(chǎn)生的，而有些運(yùn)算型指令在其執(zhí)行完畢之前，就可以形成反映運(yùn)算結(jié)果的部分條件碼，如零標(biāo)志、符號(hào)標(biāo)志等。因此可以在取得操作數(shù)之后、開始運(yùn)算之前提前形成條件碼，或者可采用延遲轉(zhuǎn)移技術(shù)．由編譯器調(diào)整指令序列，提前執(zhí)行產(chǎn)生條件碼的運(yùn)算型指令，盡早產(chǎn)生條件碼。5．加快短循環(huán)程序的處理由于程席中廣泛采用循環(huán)結(jié)構(gòu)，流水機(jī)器多數(shù)采取特殊措施以加快循環(huán)程序的處理，具體有以下兩種措施：由于循環(huán)程序中執(zhí)行循環(huán)分支的概率高，所以對循環(huán)程序出口端的條件轉(zhuǎn)移指令恒猜選循環(huán)分支，將短循環(huán)程序整體一次性放入指令緩沖器，并暫停預(yù)取指令，以減少執(zhí)行循環(huán)程序的訪主存重復(fù)取指次數(shù)。6．改進(jìn)循環(huán)程序的處理方法循環(huán)操作是程序中廣泛使用的一種特殊條件轉(zhuǎn)移。循環(huán)操作是否結(jié)束，取決于循環(huán)操作次數(shù)是否已達(dá)到原來規(guī)定次數(shù)。所謂改進(jìn)循環(huán)程序的處理-就是通過軟件方法用編譯器來支持條件轉(zhuǎn)移指令的執(zhí)行。從前面分析看出，當(dāng)轉(zhuǎn)移不成功時(shí)，條件轉(zhuǎn)移指令對流水線的影響比較小。基于這種原因，編譯器在對源程序進(jìn)行編譯時(shí)，要盡量提高出現(xiàn)轉(zhuǎn)移不成功的概率。圖3.25所示為用編譯器支持條件轉(zhuǎn)移指令執(zhí)行的方法。如圖3.25(a)所示的源程序，如果在一般編譯器中進(jìn)行編譯，編譯結(jié)果生成的目標(biāo)程序，其轉(zhuǎn)移成功的概率很高，而轉(zhuǎn)移不成功只有一次。這種編譯結(jié)果對流水線的影響非常大。

如果在編譯器中進(jìn)行適當(dāng)處理，將源程序編譯成如圖3.20(b)所示的結(jié)果，此時(shí)轉(zhuǎn)移成功與不成功的概率正好反過來。如果要支持復(fù)合型條件轉(zhuǎn)移指令（條件碼形成與轉(zhuǎn)移目標(biāo)地址計(jì)算功能用一條指令實(shí)現(xiàn)），編譯器也可以把源程序編譯成如圖3.25(c)所示的結(jié)果。這種編譯結(jié)果也只有一次轉(zhuǎn)移成功，因而對流水線的影響同圖(b)一樣。非線性流水線的調(diào)度在非線性流水線中，由于存在有反饋回路，當(dāng)一個(gè)任務(wù)在流水線中流過時(shí)，在某個(gè)功能段可能要經(jīng)過多次，如果仍按每一個(gè)時(shí)鐘周期向流水線輸入一個(gè)新任務(wù)，則會(huì)發(fā)生與后續(xù)任務(wù)爭用這個(gè)功能段的情況。這種情況稱為功能部件沖突或流水線沖突，屬于一種資源相關(guān)，它的出現(xiàn)將導(dǎo)致流水線阻塞。非線性流水線的調(diào)度是一個(gè)優(yōu)化調(diào)度問題，可以通過構(gòu)造相應(yīng)的狀態(tài)有向圖來尋找最優(yōu)凋度策略。1．預(yù)約表預(yù)約表用于非線性流水線，是一張二維的表格，其橫坐標(biāo)表示流水線工作的時(shí)鐘周期，縱坐標(biāo)表示流水線的功能段，中間畫“√”表示該功能段在這一時(shí)鐘周期處于工作狀態(tài)，空白的地方表示該功能段在這個(gè)時(shí)鐘周期不工作。2．禁止表根據(jù)預(yù)約表可以得出一個(gè)任務(wù)使用流水線中同一段所需全部的間隔拍數(shù)。例如，1段相隔8拍，2段相隔1、5、6拍，那么兩個(gè)任務(wù)相隔8拍流人流水線必將會(huì)爭用1段，而相隔1、5或6拍流人流水線必將會(huì)爭用2段。將后續(xù)任務(wù)禁止流人流水線的時(shí)間間隔的集合構(gòu)成禁止表F(forbiddenlist)。圖3.26所示預(yù)約表對應(yīng)的禁止表為F={1，5，6，8}．即要想不出現(xiàn)爭用流水線功能段的現(xiàn)象，相鄰兩個(gè)任務(wù)送入流水線的間隔拍數(shù)就不能為1、5、6、8拍，這些間隔拍數(shù)應(yīng)當(dāng)禁止使用。3．沖突向量沖突向量C(collisionvector)是一個(gè)n-1位的位向量。沖突向量(Cn-1…Ci…C2C1)中第i位的狀態(tài)用以表示與當(dāng)時(shí)相隔i拍給流水線送人后續(xù)任務(wù)是否會(huì)發(fā)生功能段的使用沖突。如果不會(huì)發(fā)生沖突，令該位為0；否則，讓該位為1。禁止表F={1，5，6，8），可以形成此時(shí)的沖突向量C0=（10110001），4．流水線狀態(tài)轉(zhuǎn)移圖新的沖突向量應(yīng)當(dāng)是已在流水線中的任務(wù)右移k位后的當(dāng)前沖突向量與剛流入流水線的新任務(wù)的初始沖突向量按位“或”的結(jié)果。窮盡此過程，直進(jìn)行到不再產(chǎn)生不同的沖突向量為止5．列出無沖突調(diào)度方案按流水線狀態(tài)圖中由初始狀態(tài)出發(fā)，凡是間隔拍數(shù)能呈現(xiàn)周期性重復(fù)的環(huán)路，都構(gòu)成一個(gè)無沖突調(diào)度方案。并計(jì)算出每種調(diào)度方案的平均間隔拍數(shù)最佳調(diào)度：平均間隔拍數(shù)最少，如方案(3，4)的平均間隔拍數(shù)為3.5拍，吞吐率最高，是最佳調(diào)度方案。計(jì)算最佳調(diào)度方案的流水線吞吐率和加速比最佳調(diào)度方案的平均間隔拍數(shù)為3.5拍，故流水線的最大吞吐率為

TPmax=1/3.5Δt由此可得流水執(zhí)行所需時(shí)間為23Δt，順序執(zhí)行每個(gè)任務(wù)所需時(shí)間為9Δt，五個(gè)任務(wù)共需9×5=45Δt時(shí)間。實(shí)際吞吐率為加速比為效率為

流水機(jī)器的中斷處理流水機(jī)器中斷處理中的關(guān)鍵問題是解決好斷點(diǎn)現(xiàn)場的保存和恢復(fù)。中斷的出現(xiàn)一般不能預(yù)知，因此，當(dāng)有一個(gè)中斷源的中斷請求被響應(yīng)時(shí)所產(chǎn)生問題是：如何從尚在流水線中未執(zhí)行完的指令中選擇作為送給中斷服務(wù)子程序的斷點(diǎn)現(xiàn)場（準(zhǔn)確的斷點(diǎn)現(xiàn)場是指若在執(zhí)行完第i條指令時(shí)響應(yīng)中斷請求，送給中斷處理程序的就是對應(yīng)于第i條指令的中斷現(xiàn)場，如第i條指令的程序狀態(tài)字等）。對此，有兩種處理方法。不精確斷點(diǎn)(impreciseinterrupt)法不精確斷點(diǎn)法對中斷的處理是：中斷請求發(fā)出時(shí)還沒進(jìn)入流水線的后繼指令不允許再進(jìn)入，而凡是已經(jīng)進(jìn)入流水線的指令序列仍然流動(dòng)直到執(zhí)行完成，然后才轉(zhuǎn)入中斷處理程序。實(shí)際上，提出中斷請求的指令可能并不是最后那條指令，所以稱其為不精確斷點(diǎn)法。這個(gè)方法只確定最后一條指令為斷點(diǎn)指令，縣保存這一條指令的現(xiàn)場，因此，保存現(xiàn)場和恢復(fù)現(xiàn)場的工作量較小。但是，采用這種方法有兩個(gè)問題：一是因?yàn)閿帱c(diǎn)不精確，程序執(zhí)行結(jié)果可能出錯(cuò)；二是由于程序不能準(zhǔn)確中斷在程序員在程序中設(shè)置的斷點(diǎn)處，使程序員無法看到自己設(shè)置的斷點(diǎn)處的現(xiàn)場，因而程序調(diào)試?yán)щy。精確斷點(diǎn)(preciseinterrupt)法

精確斷點(diǎn)法對中斷的處理是：對于在流水線中同時(shí)執(zhí)行的多條指令，由哪一條指令的程序性錯(cuò)誤或故障發(fā)出的中斷申請，斷點(diǎn)就是這條指令的地址。為了實(shí)現(xiàn)精確斷點(diǎn)法，需要把斷點(diǎn)指令之前尚在流水線中已完全執(zhí)行和部分執(zhí)行的指令的執(zhí)行結(jié)果都作為現(xiàn)場保存起來．為此，要設(shè)置一定數(shù)量的后援寄存器，以便能精確恢復(fù)斷點(diǎn)現(xiàn)場。因此，采用精確斷點(diǎn)法需要較高的硬件代價(jià)，控制邏輯也比較復(fù)雜。目前的流水線處理機(jī)一般都采用精確斷點(diǎn)法。先進(jìn)的流水線調(diào)度技術(shù)當(dāng)流水線技術(shù)采用按序(inorder)發(fā)射指令的機(jī)制時(shí)，指令序列在流水線中是順序流動(dòng)的，如果當(dāng)前指令在流水線中被暫停，則后續(xù)指令就無法前進(jìn)。因此，當(dāng)相鄰的兩條指令存在相關(guān)時(shí)，會(huì)引起流水線的斷流。如果有多個(gè)功能部件，它們就會(huì)處于空閑狀態(tài)。這是流水線技術(shù)的一個(gè)限制。如果采用亂序(outoforder)按術(shù)，則遇到類似問題時(shí)，后繼指令若無相關(guān)，就可以繞過當(dāng)前相關(guān)指令，繼續(xù)在流水線中流動(dòng)，這樣可提高流水線的效率。我們將要討論的先進(jìn)的流水線動(dòng)態(tài)調(diào)度技術(shù)正是基于這種思想實(shí)現(xiàn)的。在遇到無法消除的數(shù)據(jù)相關(guān)時(shí)，靜態(tài)調(diào)度(staticscheduling)方法是通過調(diào)度相關(guān)指令以減少暫停的影響，而采用動(dòng)態(tài)調(diào)度(dynamicscheduling)的處理機(jī)則會(huì)盡量避免相關(guān)給流水線帶來的暫停。動(dòng)態(tài)調(diào)度相對于靜態(tài)調(diào)度的優(yōu)點(diǎn)在于：它可以處理一些編譯時(shí)未發(fā)現(xiàn)的相關(guān)，從而簡化了編譯器，另外它還允許在一種流水線上編譯的代碼可以在其他流水線上有效的運(yùn)行，實(shí)現(xiàn)代碼的可移植性。當(dāng)然，這些流水線性能的改善是以顯著增加硬件的復(fù)雜程度為代價(jià)的。集中式動(dòng)態(tài)調(diào)度方法——記分牌這種調(diào)度方法源自CDC6600，主要用一個(gè)稱為狀態(tài)記錄控制器(或記分牌(scoreboard))的調(diào)度部件對流水線中的各個(gè)功能部件的工作狀態(tài)、進(jìn)入流水線中的各條指令的工作狀態(tài)、它們所使用的源寄存器和目的寄存器情況等進(jìn)行集中的統(tǒng)一記錄和調(diào)度。記分牌記錄并管理如下三張表：指令狀態(tài)表。它登記已取指到指令流水線的各條指令的狀態(tài)——是否已完成發(fā)射、是否已取完操作數(shù)、是否已完成執(zhí)行、是否已完成寫回。功能部件狀態(tài)表。每一個(gè)功能部件占有一個(gè)表項(xiàng)，登記是否“忙”、目的寄存器名、源寄存器名等是否就緒。目標(biāo)寄存器表。每一個(gè)寄存器與預(yù)約使用它作為目標(biāo)寄存器的功能部件(ID)相聯(lián)系，一個(gè)寄存器只能作為一個(gè)功能部件而不能同時(shí)作為兩個(gè)功能部件的目標(biāo)寄存器。記分牌隨時(shí)監(jiān)督并不斷修改這些表，規(guī)定了一些定向邏輯。指令調(diào)度上若一條譯后的指令所需的功能部件可用，并且目標(biāo)寄存器也不是其他功能部件已預(yù)約的目標(biāo)寄存器，那么這條指令就可發(fā)射，否則將指令掛起，直到條件滿足再發(fā)射。這樣首先杜絕了“寫后寫”相關(guān)。至于取寄存器操作數(shù)并非該段必須完成的功能，能取則取，不能取可在執(zhí)行段完成取操作，這樣會(huì)使流水線停頓減少。在取寄存器操作數(shù)時(shí)要判測是否有“先寫后讀”相關(guān)。若先前發(fā)射的指令以某寄存器為目標(biāo)寄存器，則只有該指令向目標(biāo)寄存器寫入后（目標(biāo)寄存器表中此項(xiàng)清除），此寄存器才作為其他指令的源寄存器就緒，從而消除“先寫后讀”相關(guān)。在寫回段要判測是否有“先讀后寫”相關(guān)。先前發(fā)射的指令若以本指令預(yù)定的目標(biāo)

寄存器為源寄存器，而還沒有讀取的話，則本指令的寫回操作要推遲．直到“先讀后寫”相關(guān)清除再寫回。因指令是按序發(fā)射，并按發(fā)射順序登記在指令狀態(tài)表中，故指令發(fā)射的先后順序容易斷定。分布式動(dòng)態(tài)調(diào)度方法——Tomasulo算法Tomasulo算法的核心是在記分牌調(diào)度方法中融入寄存器重命名(registerrenaming)技術(shù)，并以此來解決“寫后寫”相關(guān)和“先讀后寫”相關(guān)。寄存器重命名的規(guī)則是：如果遇到“寫后寫”或“先讀后寫”相關(guān)，則對引起相關(guān)的目的寄存器重新命名，即對于引起“寫后寫”或“先讀后寫”相關(guān)的指令，其運(yùn)算結(jié)果不能直接寫到指令指定的引起相關(guān)的目的寄存器中，而是先寫到另外一個(gè)動(dòng)態(tài)分配的備用寄存器中。等到與其相關(guān)的指令完成了訪問并將結(jié)果寫入該寄存器之后，就可以將這些臨時(shí)的備用寄存器中的內(nèi)容恢復(fù)到指令中正式指定的寄存器中去。在Tomasulo算法中，寄存器重命名是通過保留站(reservationstation)來實(shí)現(xiàn)的。保留站緩存了即將要發(fā)射的指令所需要的操作數(shù)。Tomasulo算法的基本思想是盡可能早地取得并緩存一個(gè)操作數(shù)，避免指令直接從寄存器中讀取數(shù)據(jù)的情況。指令執(zhí)行時(shí)從保留站中取得操作數(shù)，并將執(zhí)行結(jié)果直接送到等待數(shù)據(jù)的其他保留站。對于連續(xù)對同一寄存器的寫操作，只有最后一個(gè)才真正更新寄存器中的內(nèi)容。一條指令被發(fā)射時(shí)，存放其操作數(shù)的寄存器被重新命名為對應(yīng)保留站的名字，這就是Tomasulo算法中的寄存器重命名技術(shù)。圖3.30所示是IBM360/91浮點(diǎn)執(zhí)行部件的結(jié)構(gòu)框圖浮點(diǎn)數(shù)緩沖器(FLB)接收和緩沖來自主存的操作數(shù)。要寫入存儲(chǔ)器的信息被送到存數(shù)緩沖器(SDB)中緩沖。浮點(diǎn)執(zhí)行部件中的浮點(diǎn)加法器和浮點(diǎn)乘/除法器都是流水線，且能同時(shí)并行工作。浮點(diǎn)操作棧(FLOS，F(xiàn)loatingPointOperandStack)用于緩沖來自指令部件的浮點(diǎn)操作指令通過給每個(gè)浮點(diǎn)寄存器(FLRi)設(shè)置一個(gè)“忙位”來判斷相關(guān)。。當(dāng)某個(gè)浮點(diǎn)寄存器被使用時(shí)就將其“忙位”置為l，使用完則將其“忙位”置為0。若FLOS送出如下兩條指令：I1ADD F2，F(xiàn)LB1 ；(F2)+(FLB1)→F2I2MUL F2，F(xiàn)LB2 ；(F2)×(FLB2)→F2機(jī)器的處理過程如下(l)當(dāng)FLOS送出I1時(shí)，將控制由FLR取得(F2)，由FLB取得(FLBI)送往加法器保留站，假設(shè)送往Al，同時(shí)將F2的“忙位”置1，以指明該寄存器的內(nèi)容已送往保留站等待運(yùn)算，其內(nèi)容不能再被其他指令作為源操作數(shù)讀出使用。(2)由于F2作為“目的”寄存器準(zhǔn)備接收由加法器送來的運(yùn)算結(jié)果，故需將站號(hào)A1送入F2的“站號(hào)”字段，以控制加法流水線將流出的保留站A1的運(yùn)算結(jié)果經(jīng)CDB總線送回F2。當(dāng)結(jié)果送回后，將F2的“忙位”和“站號(hào)”置成0，即釋放F2并允許其他指令使用。(3)如果在F2的“忙位”為1，而加法結(jié)果尚未流出加法流水線時(shí)，F(xiàn)LOS送出了I2，則在訪問F2取源1操作數(shù)時(shí)，會(huì)因其“忙位”為1而表明出現(xiàn)F2相關(guān)。此時(shí)不能直接將F2的內(nèi)容送往乘法器保留站，而應(yīng)將保存在F2“站號(hào)”字段中的站號(hào)A1送往M1源1的“站號(hào)”字段，并將F2的站號(hào)由A1改為M1以指明將從M1接收運(yùn)算結(jié)果。(4)當(dāng)加法器對A1站的（源1）、（源2）進(jìn)行相加，并將結(jié)果由CDB送出時(shí)，就會(huì)將直接送入“站號(hào)”為A1的M1保留站（源1）中，這相當(dāng)于將此間的相關(guān)專用通路接通，之后要清除M1保留站（源1）的“站號(hào)”(5)此時(shí)乘法器的M1保留站的（源1）、（源2）均已就緒，可將其送人乘法器執(zhí)行乘運(yùn)算，這實(shí)際相當(dāng)于推后相乘的執(zhí)行。而乘積則經(jīng)CDB總線送往“站號(hào)”字段為M1的F2寄存器，同時(shí)將F2的“忙位”和“站號(hào)”置0，釋放F2。：動(dòng)態(tài)轉(zhuǎn)移目標(biāo)緩沖技術(shù)這是一種為減少轉(zhuǎn)移指令引起的流水線停頓，而盡早生成轉(zhuǎn)移目標(biāo)地址的技術(shù)。它將以往成功轉(zhuǎn)移的轉(zhuǎn)移指令地址和其轉(zhuǎn)移目標(biāo)地址放到一個(gè)類似Cache的緩沖區(qū)中保存起來，緩沖區(qū)以轉(zhuǎn)移指令的地址作為標(biāo)志。在每條指令的取指階段，將指令的地址與緩沖區(qū)中保存的所有標(biāo)志做相聯(lián)比較，若有相符的標(biāo)志，則認(rèn)為本指令是轉(zhuǎn)移指令，且轉(zhuǎn)移成功，它的下一條指令地址就是緩沖區(qū)中與相待標(biāo)志對應(yīng)的轉(zhuǎn)移目標(biāo)地址。這個(gè)緩沖區(qū)稱為轉(zhuǎn)移目標(biāo)緩沖區(qū)（BTB，BranchTargetBuffer或BranchTargetCache），轉(zhuǎn)移目標(biāo)緩沖的工作過程為：(l)當(dāng)前指令的地址與BTB中的標(biāo)志作相聯(lián)比較，若有相符者，則認(rèn)為此指令為轉(zhuǎn)移成功指令，且下一條指令的地址在BTB的轉(zhuǎn)移目標(biāo)地址域中。因此在本指令的指令譯碼(ID)階段，開始從預(yù)測的指令地址處取下一條指令，如果預(yù)測正確將不會(huì)有任何延遲。(2)若在BTB中有與當(dāng)前指令地址相符者，但當(dāng)前指令轉(zhuǎn)移不成功，則預(yù)測錯(cuò)誤，此時(shí)將該項(xiàng)從BTB中刪去。這時(shí)會(huì)耗費(fèi)一個(gè)時(shí)鐘周期來取錯(cuò)誤的指令，并在一個(gè)時(shí)鐘周期后重新取正確指令。(3)如果當(dāng)前指令地址在BTB中沒有相符者而指令發(fā)生了轉(zhuǎn)移，則轉(zhuǎn)移目標(biāo)地址將在指令譯碼(ID)階段末知道，此時(shí)應(yīng)將該轉(zhuǎn)移指令的地址和轉(zhuǎn)移目標(biāo)地址加入BTB中。(4)若當(dāng)前指令地址在BTB中無相符者且指令不發(fā)生轉(zhuǎn)移，則按普通指令執(zhí)行。指令級(jí)并行技術(shù)前面介紹的技術(shù)主要是通過減少數(shù)據(jù)相關(guān)和控制相關(guān)，達(dá)到每條指令執(zhí)行的平均周期數(shù)CPI為1的理想情況。為獲得更高的性能，我們希望能夠使CPI進(jìn)一步減小為CPI≤1。在20世紀(jì)80年代興起的RISC結(jié)構(gòu)，其設(shè)計(jì)思想就是要讓單處理機(jī)在每個(gè)時(shí)鐘周期里可解釋多條指令。由此出現(xiàn)了采用提高指令級(jí)并行新技術(shù)的超級(jí)處理機(jī)，具代表性的有超標(biāo)量(superscalar)處理機(jī)、超長指令字(VLIW，VeryLongInstructionWord)處理機(jī)和超流水線(superpipelining)處理機(jī)。超標(biāo)量處理機(jī)標(biāo)量流水處理機(jī)的時(shí)-空圖一般的流水機(jī)器在一個(gè)時(shí)鐘周期內(nèi)只能發(fā)射一條指令，每個(gè)時(shí)鐘周期只能產(chǎn)生一個(gè)結(jié)果，稱為標(biāo)量流水線處理機(jī)。超標(biāo)量處理機(jī)在一個(gè)時(shí)鐘周期內(nèi)能夠同時(shí)發(fā)射多條指令。超標(biāo)量處理機(jī)是利用硬件資源重復(fù)設(shè)置來實(shí)現(xiàn)空間上的并行操作，從而縮短處理時(shí)間以減小CPI。采用多指令流水線的超標(biāo)量處理機(jī)在每個(gè)Δt同時(shí)流出m條指令（稱并行度為m）。圖3.34所示為并行度m=3的超標(biāo)量處理機(jī)的流水時(shí)一空圖，每三條指令為一組，執(zhí)行完12條指令只需7Δt。典型的超標(biāo)量流水線處理機(jī)有IBMRS6000、PowerPC620、DEC21064等，還有如Intel公司的i960CA、Pentium系列處理機(jī)，Motorola公司的MC88110等。1986年的Inteli960CA時(shí)鐘頻率為25MHz，并行度m=3，有七個(gè)功能部件可以并發(fā)使用。1990年的IBMRS6000使用1μm的CMOS工藝，時(shí)鐘頻率為30MHz。處理機(jī)中有轉(zhuǎn)移處理、定點(diǎn)、浮點(diǎn)三種功能部件，它們可并行工作。轉(zhuǎn)移處理部件每Δt可執(zhí)行多達(dá)五條指令，并行度m=4，性能可達(dá)34MIPS和11MFLOPS。1992年的DEC21064使用0.75μm的CMOS，時(shí)鐘頻率為150MHz，并行度m=2，具有10段流水線，最高性能可達(dá)300MIPS和150MFLOPS。1995年的PowerPC620是PowerPC結(jié)構(gòu)的第一個(gè)64位實(shí)現(xiàn)方案，它包括六個(gè)獨(dú)立執(zhí)行單元，允許處理器同時(shí)派遣四條指令到三個(gè)整數(shù)單元和一個(gè)浮點(diǎn)單元，時(shí)鐘頻率為150MHz。1998年的IntelPentiumⅡ處理器，具有11段流水線，能并行執(zhí)行三條Pentium指令，最高時(shí)鐘頻率為450MHz。超長指令字處理機(jī)超長指令字VLIW結(jié)構(gòu)是水平微碼和超標(biāo)量處理兩者相結(jié)合的產(chǎn)物。超長指令字處理機(jī)采用指令靜態(tài)調(diào)度策略，通過優(yōu)化編譯器找出指令間潛在的并行性，將多條指令中若干可并行執(zhí)行的操作安排在一個(gè)超長指令字中的各指令操作字段上，形成一條可達(dá)數(shù)百位的指令，超長指令字由此得名。圖3.35所示為典型的VLIW處理機(jī)結(jié)構(gòu)和指令格式。VLIW結(jié)構(gòu)由編譯器在編譯過程中重新安排指令順序，這使得超長指令字譯碼器邏輯簡單。運(yùn)行時(shí)不再需要用軟件或硬件進(jìn)行操作相關(guān)判定、指令調(diào)度及操作的亂序處理等控制邏輯，從而使碗件結(jié)構(gòu)的復(fù)雜性大為降低，卻能獲得很強(qiáng)的性能。VLIW是一種單指令多操作碼多數(shù)據(jù)(SIMOMD)的系統(tǒng)結(jié)構(gòu)。指令同時(shí)可流出的最大數(shù)目（并行度m）越大，超長指令字的性能優(yōu)勢就越顯著。圖3.36所示為VLIW執(zhí)行時(shí)一空圖，每拍啟動(dòng)一條長指令，執(zhí)行三個(gè)操作，相當(dāng)于三條指令，并行度m=3，經(jīng)過七個(gè)Δt后可得到4×3個(gè)結(jié)果。VLIW技術(shù)的關(guān)鍵是它的編譯技術(shù)。VLIW指令中并行操作的同步在編譯時(shí)完成，這

使它比超標(biāo)量處理器具有更高的處理效率。而VLIW體系結(jié)構(gòu)中對指令并行性和數(shù)據(jù)移

動(dòng)在編譯時(shí)說明，則大大簡化了運(yùn)行時(shí)的資源調(diào)度。但是，VLIW的指令格式是特殊的，因

而其代碼無法與一般的計(jì)算機(jī)兼容。VLIW的指令字很長而操作段格式固定，經(jīng)常使指令

字中的許多字段沒有操作，浪費(fèi)了存儲(chǔ)空間。VLIW機(jī)的編譯程序與系統(tǒng)結(jié)構(gòu)關(guān)系非常密

切，二者必須同時(shí)設(shè)計(jì)，故缺乏對傳統(tǒng)硬件和軟件的兼容?，F(xiàn)代VLIW的研究在進(jìn)一步深入開發(fā)更高效實(shí)用的編譯技術(shù)的同時(shí)，也試圖在體系結(jié)構(gòu)方面有所改進(jìn)，以彌補(bǔ)傳統(tǒng)VLIW存在的不足。超流水線處理機(jī)超流水線是指在每個(gè)節(jié)拍只發(fā)射一條指令，但每個(gè)機(jī)器周期內(nèi)可并發(fā)發(fā)射多條指令并產(chǎn)生多個(gè)結(jié)果的流水線。與超標(biāo)量流水線不同的是，超流水線每一節(jié)拍仍只流出一個(gè)結(jié)果，但一臺(tái)并行度為m的超流水線處理機(jī)的節(jié)拍Δt′只是機(jī)器時(shí)鐘周期Δt的l/m。因此在一個(gè)時(shí)鐘周期內(nèi)，流水線仍可流出多個(gè)結(jié)果。圖3.37所示為并行度m=3的超流水線處理機(jī)工作時(shí)-空圖。與超標(biāo)量流水線處理機(jī)利用資源重復(fù)開發(fā)空間并行性不同，超流水線處理機(jī)則著重開，發(fā)時(shí)間并行性，在流水部件上采用較短的時(shí)鐘周期，通過增加流水級(jí)數(shù)來提高速度。如果一臺(tái)有k段流水線的m并行度超流水線處理機(jī)，執(zhí)行完N條指令的時(shí)間為如果m=3，則所需時(shí)間為加速比為當(dāng)N趨于無窮大時(shí)，加速比Sp趨近于m。典型的超流水線機(jī)器有1991年2月MIPS公司的64位RISC計(jì)算機(jī)MIPSR4000超標(biāo)量超流水線處理機(jī)超標(biāo)量超流水線處理機(jī)是超標(biāo)量流水與超流水技術(shù)的結(jié)合。若一條指令包含取指令、譯碼、執(zhí)行、存結(jié)果四個(gè)子過程，各子過程經(jīng)過時(shí)間均為Δt′，且機(jī)器時(shí)鐘周期Δt=3Δt′，則指令在并行度m=9的超標(biāo)量超流水線處理機(jī)中的操作情況如圖3.38所示。在一個(gè)時(shí)鐘周期內(nèi)機(jī)器指令發(fā)射三次，每次發(fā)射三條指令，每個(gè)功能段延遲時(shí)間都是Δt′，則在流水線滿負(fù)荷工作時(shí)，完成12個(gè)任務(wù)只需要5Δt。美國DEC公司1992年推出的Alpha21064處理器就采用了超標(biāo)量超流水結(jié)構(gòu)。設(shè)流水線的級(jí)數(shù)為k，流水線中每級(jí)的執(zhí)行時(shí)間均為τ，采用超流水線時(shí)處理器的時(shí)鐘頻率為主機(jī)時(shí)鐘頻率的n倍，采用超標(biāo)量時(shí)處理器的發(fā)射度為m。對于不同類型的流水線在執(zhí)行N條指令時(shí)的執(zhí)行時(shí)間有所不同。單發(fā)射標(biāo)量流水線m發(fā)射超標(biāo)量流水線單發(fā)射n倍超流水線

m發(fā)射n倍超標(biāo)量超流水線一般情況下，當(dāng)時(shí)鐘頻率和流水線級(jí)數(shù)相同時(shí)，有m發(fā)射的超標(biāo)量處理機(jī)速度最多為單發(fā)射處理機(jī)速度的m倍。具有n倍時(shí)鐘頻率的超流水線處理機(jī)，它的速度最多可為單頻標(biāo)量流水線的n倍。具有n倍時(shí)鐘頻率和m發(fā)射的超標(biāo)量起流水線處理機(jī)，它的組合加速比可為單頻標(biāo)量流水線的m·n倍。[例3.5]設(shè)有12個(gè)任務(wù)需要進(jìn)入流水線，已知流水線的功能段均為四個(gè)，每個(gè)功能段的處理時(shí)間都是Δt?，F(xiàn)計(jì)算在下列情況中完成12個(gè)任務(wù)分別需要多少時(shí)間？(1)單發(fā)射標(biāo)量流水線。(2)超標(biāo)量流水線，每個(gè)時(shí)鐘周期可以同時(shí)發(fā)射三條指令。(3)超流水線，每個(gè)時(shí)鐘周期可以分時(shí)發(fā)射三次，每次發(fā)射一條指令。(4)超標(biāo)量超流水線，每個(gè)時(shí)鐘周期可以分時(shí)發(fā)射三次，每次發(fā)射三條指令。[例3.6]在下列不同結(jié)構(gòu)的處理機(jī)上運(yùn)行8×8的矩陣乘法C=A×B，計(jì)算所需要的最短時(shí)間（只計(jì)算乘法指令和加法指令的執(zhí)行時(shí)間，不計(jì)算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時(shí)間）。加法部件和乘法部件的延遲時(shí)間都是三個(gè)時(shí)鐘周期，另外，加法指令和乘法指令還要經(jīng)過一個(gè)“取指令”和“指令譯碼”的時(shí)鐘周期，每個(gè)時(shí)鐘周期為20ns，C的初始值為0。各操作部件的輸出端有直接數(shù)據(jù)通路連接到有關(guān)操作部件的輸入端，在操作部件的輸出端設(shè)置有足夠容量的緩沖寄存器。(l)處理機(jī)中只有一個(gè)通用操作部件，采用順序方式執(zhí)行指令。(2)單流水線標(biāo)量處理機(jī)。有一條兩個(gè)功能的靜態(tài)流水線，流水線每個(gè)功能段的延遲時(shí)間均為一個(gè)時(shí)鐘周期，加法操怍和乘法操作各經(jīng)過三個(gè)功能段。(3)多操作部件處理機(jī)。處理機(jī)內(nèi)有獨(dú)立的乘法部件和加法部件，兩個(gè)操作部件可以并行工作。只有一個(gè)指令流水線，操作部件不采用流水線結(jié)構(gòu)。(4)單流水線標(biāo)量處理機(jī)。處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線每個(gè)功能段的延遲時(shí)間均為一個(gè)時(shí)鐘周期。(5)超標(biāo)量處理機(jī)。每個(gè)時(shí)鐘周期同時(shí)發(fā)射一條乘法指令和一條加法指令，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線的每個(gè)功能段的延遲時(shí)間均為一個(gè)時(shí)鐘周期。(6)超流水線處理機(jī)。把一個(gè)時(shí)鐘周期分為兩個(gè)流水節(jié)拍，加法部件和乘法部件的延遲時(shí)間都為六個(gè)流水節(jié)拍，“取指令”和“指令譯碼”仍分別為一個(gè)流水節(jié)拍，每個(gè)時(shí)鐘周期能夠分時(shí)發(fā)射兩條指令，即每個(gè)流水節(jié)拍能夠發(fā)射一條指令。(7)超標(biāo)量超流水線處理機(jī)。把一個(gè)時(shí)鐘周期分為兩個(gè)流水節(jié)拍，加法部件和乘法部件延遲時(shí)間都為六個(gè)流水節(jié)拍，“取指令”和“指令譯碼”仍分別為一個(gè)流水節(jié)拍，每個(gè)流水節(jié)拍能夠同時(shí)發(fā)射一條乘法指令和一條加法指令。解：要完成兩個(gè)8×8矩陣相乘，共要進(jìn)行8×8×8=512次乘法，8×8×7=448次加法(1)順序執(zhí)行時(shí)，每個(gè)乘法和加法指令都需要五個(gè)時(shí)鐘周期。計(jì)算所需要的時(shí)間為T=(512+448)×5×20ns=96000ns(2)單流水線標(biāo)量處理機(jī)，操作部件為靜態(tài)雙功能流水線，結(jié)構(gòu)如圖3.39所示。由于有足夠的緩沖寄存器，所以可以首先把所有的乘法計(jì)算完，流水線排空后再輸入加法任務(wù)，并通過調(diào)度使加法流水線不出現(xiàn)停頓。計(jì)算所需要的最短時(shí)間為T=[(5+512-1)+(3+448-1)])×20ns=19320ns(3)單流水線多操作部件處理機(jī)，結(jié)構(gòu)如圖3.40所示。因?yàn)榧臃偣矆?zhí)行448次，而乘法共執(zhí)行512次，所以加法操作可以在某些時(shí)候與乘法操作并行執(zhí)行。同時(shí)考慮乘法流水線的乘積與加法流水線的加數(shù)之間可能出現(xiàn)的“先寫后讀”數(shù)據(jù)相關(guān)，最后一次加法運(yùn)算結(jié)束與最后一次乘法運(yùn)算結(jié)束的時(shí)間差應(yīng)為一次完整的加法流水操作過程，這里為三個(gè)時(shí)鐘周期。計(jì)算所需要的最短時(shí)間為T=[5+(512-1)×3+3]×20ns=30820ns(4)單流水線標(biāo)量處理機(jī)有兩條獨(dú)立的操作流水線，結(jié)構(gòu)如圖3.41所示。分析方法同(2)，但流水線不需排空。計(jì)算所需要的最短時(shí)間為T=[5+(512-1)+448]×20ns=19280ns(5)超標(biāo)量處理機(jī)，能同時(shí)發(fā)射一條加法和一條乘法指令，有兩條獨(dú)立的操作流水線，結(jié)構(gòu)如圖3.42所示。分析方法同(3)，區(qū)別在于乘與加操作均是流水化的，而且在不同的流水線上并行執(zhí)行。計(jì)算所需要的最短時(shí)間為T=[5+(512-1)+3]×20ns=10380ns(6)超流水線處理機(jī)每個(gè)時(shí)鐘周期分時(shí)發(fā)射兩條指令，加法部件和乘法部件都為六個(gè)流水級(jí)，“取指令”和“指令譯碼”仍分別為一個(gè)流水級(jí)，結(jié)構(gòu)如圖3.43所示。分析方法同(4)，不同之處在于時(shí)鐘周期變成了10ns，且流水線已細(xì)化。計(jì)算所需要的最短時(shí)間為T=[8+(512-1)+448]×10ns=9670ns(7)超標(biāo)量超流水線處理機(jī)一個(gè)時(shí)鐘周期分為兩個(gè)流水節(jié)拍，加法部件和乘法部件均為六個(gè)流水級(jí)，“取指令”和“指令譯碼”仍分別為一個(gè)流水級(jí)，每個(gè)流水節(jié)拍能同時(shí)發(fā)射一條加法和一條乘法指令，結(jié)構(gòu)如圖3.44所示。綜合(5)和(6)的分析可知，計(jì)算所需要的最短時(shí)間為T=[8+(512-1)+6]×10ns=5250ns3.6向量處理技術(shù)從前面的分析中可知，如果輸入流水線的指令既無局部性相關(guān)，也無全局性相關(guān)，則流水線可能裝滿。此時(shí)，可獲得高的吞吐率和效率。在科學(xué)計(jì)算中，往往有大量不相關(guān)的數(shù)據(jù)進(jìn)行同一種運(yùn)算，這正適合于流水線特點(diǎn)，因此就出現(xiàn)了具有向量數(shù)據(jù)表示和相應(yīng)向量指令的向量流水線處理機(jī)。由于這種機(jī)器能較好地發(fā)揮流水線技術(shù)特性，因此，可以達(dá)到較高的速度。一般稱向量流水處理機(jī)為向量機(jī)(vectorprocessor)。向量處理方法這里，用一個(gè)簡單的例子說明向量的處理方式。例如，以下是FORTRAN語言寫的一個(gè)循環(huán)程序：DO10i=1，N10d[i]=a[i]*(b[i]+c[i])對此，可以有下面幾種方法。1．水平（橫向）處理法如果用逐個(gè)求d[i]的方式，則：d[1]=a[1]*(b[1]+c[1])d[2]=a[2]*(b[2]+c[2])…d[i]=a[i]*(b[i]+c[i])…d[N]=a[N]*(b[N]+c[N])這種方法的每次循環(huán)中至少要用兩條指令：k[i]=b[i]+c[i]d[i]=k[i]*a[i]顯然在流水處理中，不僅有操作數(shù)相關(guān)（“先讀后寫”相關(guān)），而且每次循環(huán)中又有功能的切換(+、*、…)，這就使流水線的效率和吞吐率降低。實(shí)際上，可以認(rèn)為A、B、C、D是長度為N的向量。A=（a1，a2，…，aN）B=（b1，b2，…，bN）C=（c1，c2，…，cN）D=（d1，d2，…，dN）因此，上述DO循環(huán)可以寫成如下向量運(yùn)算的形式：D=A*(B+C)基于該向量表示形式，還可以有下面兩種處理方式。2．垂直（縱向）處理法垂直處理方法是對整個(gè)向量按相同的運(yùn)算處理完之后，再去執(zhí)行別的運(yùn)算。對于上式，則有K=B+CD=K*A可以看出，這種處理方式僅用了兩條向量指令，且處理過程中沒有出現(xiàn)轉(zhuǎn)移，每條向量指令內(nèi)無相關(guān)，兩條向量指令問只有一次數(shù)據(jù)相關(guān)，如果仍用靜態(tài)多功能流水線，也只需一次功能切換。由于向量長度N是不受限制的，無論N有多大，相同運(yùn)算都用一條向量指令完成。因此，向量運(yùn)算指令的源向量和目的向量都存放在存儲(chǔ)器內(nèi)，流水線運(yùn)算部件的輸入、輸出端通過緩沖器與主存連接，從而構(gòu)成存儲(chǔ)器一存儲(chǔ)器型的運(yùn)算流水線，其結(jié)構(gòu)如圖3.45所示。3．分組（縱橫）處理法把長度為N的向量分成若干組，每組長度為行，組內(nèi)按縱向方式處理，依次處理各組。若 N=s·n+r其中r為余數(shù)，也作為一組處理，則共有s+1組，其運(yùn)算過程為：第一組

K1~n=B1~n+C1~n

D1~n=K1~n*A1~n第二組

Kn+1~2n=Bn+1~2n+Cn+1~2n

Dn+1~2n=Kn+1~2n*An+1~2n

……第s+1組

Ksn+1~N=Bsn+1~N+Csn+1~N

Dsn+1~N=Ksn+1~N*Asn+1~N每組內(nèi)各用兩條向量指令，僅有一次向量指令的數(shù)據(jù)相關(guān)。如果也用靜態(tài)多功能流水線，則各組需兩次功能切換，所以適合于對向量進(jìn)行流水處理。這種處理方式對向量總長度N沒有限制，但組內(nèi)長度不能超過n。因此，可設(shè)置長度為n的向量寄存器，使每組向量運(yùn)算的源向量和目的向量均在向量寄存器中，運(yùn)算流水線的輸入、輸出端與向量寄存器相連，構(gòu)成所謂寄存器一寄存器型運(yùn)算流水線，如圖3.46所示。向量處理機(jī)向量處理機(jī)的結(jié)構(gòu)因具體機(jī)器而不同，20世紀(jì)70年代中期問世的CRAY-1向量流水處理機(jī)是向量處理機(jī)的典型代表。下面僅以CRAY-I機(jī)中的向量流水處理部分為例，介紹面向寄存器一寄存器型向量流水處理機(jī)的一些結(jié)構(gòu)特點(diǎn)。CRAY-I向量處理機(jī)不能獨(dú)立工作，它需要一臺(tái)前置機(jī)對整個(gè)系統(tǒng)進(jìn)行管理，在此只介紹CRAY-I向量處理機(jī)本身。Cray-1CRAY-1是由中央處理機(jī)、診斷維護(hù)控制處理機(jī)、大容量磁盤存儲(chǔ)子系統(tǒng)、前置處理機(jī)組成的功能分布異構(gòu)型多處理機(jī)系統(tǒng)。CRAY-1向量處理機(jī)不能獨(dú)立T作，它需要一臺(tái)前置機(jī)對整個(gè)系統(tǒng)進(jìn)行管理。圖3.47是CRAY-1向量處理機(jī)中有關(guān)向量流水處理部分的簡圖。每個(gè)Vi塊可存元素個(gè)數(shù)達(dá)64的一個(gè)向量。因此，向量寄存器中同時(shí)可存放八個(gè)向量。對于長度超過64個(gè)元素的長向量可以由軟件加以分段處理，每段64個(gè)元素。為了能充分發(fā)揮向量寄存器組和可并行工作的六個(gè)功能部件的作用以及加快向量處理，CRAY-I設(shè)計(jì)成每個(gè)Vi塊都有單獨(dú)總線可連到六個(gè)功能部件，而每個(gè)功能部件也各自都有把運(yùn)算結(jié)果送回向量寄存器組的輸出總線。這樣，只要不出現(xiàn)Vi沖突和功能部件沖突，各個(gè)Vi之間和各個(gè)功能部件之間都能并行工作，從而大大加快了向量指令的處理，所謂Vi沖突是指并行工作的各向量指令的源向量或結(jié)果向量的Vi有相同的。除了相關(guān)情況之外，就是出現(xiàn)源向量沖突，例如：V4=V1+V2V5=V1^V3所謂功能部件沖突指的是同一個(gè)功能部件被一條以上的并行工作向量指令所使用。例如：