本科系統(tǒng)結(jié)構(gòu)課件 chapter5-2

§2流水方式

基本概念流水線處理機的主要性能流水機器的相關(guān)處理和控制機構(gòu)

空間并行性設(shè)置多個獨立的操作部件多操作部件處理機超標(biāo)量處理機時間并行性采用流水線技術(shù)。不增加或只增加少量硬件就能使運算速度提高幾倍流水線處理機超流水線處理機基本概念

流水是重疊的延伸.一次重疊：只是把一條指令的解釋分解為兩個子過程；流水：分解為更多的子過程。時空圖表示。流水線的表示方法連接圖時空圖預(yù)約表取指令指令譯碼取操作數(shù)執(zhí)行入出12345123451234512345取指令指令譯碼取操作數(shù)執(zhí)行空間時間t1t2t3t4t5t6t7t8流水線的時-空圖說明流水線的每一個階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級、流水節(jié)拍等。在每一個流水段的末尾或開頭必須設(shè)置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。會增加指令的執(zhí)行時間。為了簡化，在一般流水線中不畫出流水鎖存器說明流水線經(jīng)過裝入、充滿、排空三個階段流水的最大吞吐率：當(dāng)流水線正常符合流動時的吞吐率。每隔Δt流出一個結(jié)果。流水的最大吞吐率取決于子過程所經(jīng)過的時間Δt一個浮點加法器流水線的時空圖由求階差、對階、尾數(shù)加和規(guī)格化4個流水段組成ED1時間空間0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：規(guī)格化MA：尾數(shù)加EA：對階ED：求階差流水線的特點只有連續(xù)提供同類任務(wù)才能充分發(fā)揮流水線的效率對于指令流水線：要盡量減少因條件分支造成的“斷流”對于操作部件：主要通過編譯技術(shù)，盡量提供連續(xù)的同類操作在流水線的每一個流水線段中都要設(shè)置一個流水鎖存器時間開銷：流水線的執(zhí)行時間加長是流水線中需要增加的主要硬件之一各流水段的時間應(yīng)盡量相等流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度流水線需要有裝入時間、充滿時間和排空時間在理想情況下，當(dāng)流水線充滿后，每隔Δt時間將會有一個結(jié)果流出流水線。流水線的分類從不同角度，有不同的分類依據(jù)向下擴展和向上擴展思路，可分類出在計算機系統(tǒng)不同等級上使用的流水線向下擴展：子過程細(xì)分向上擴展：多個處理機之間進行流水流水線的分類（續(xù)）

按流水處理的級別部件級（操作流水線），如浮點加法器流水線求階差輸入輸出Dt1對階尾數(shù)加規(guī)格化Dt2Dt3Dt4流水線的分類（續(xù)）處理機級，指令流水線(InstructionPipelining)例如：在采用先行控制器的處理機中，各功能部件之間的流水線先行指令

緩沖棧輸入先行控制方式

中的指令流水線先行指令

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

先行操作棧取指譯碼取操作數(shù)指令執(zhí)行部件后行寫數(shù)棧輸出執(zhí)行寫結(jié)果流水線的分類（續(xù)）系統(tǒng)級：宏流水線(MacroPipelining)

每個處理機對同一個數(shù)據(jù)流的不同部分分別進行處理處理機1處理機2處理機n數(shù)據(jù)集處理機間的流水處理流水線的分類（續(xù)）按功能多少單功能：只能完成一種固定功能的流水線Cray-1計算機中有12條；YH-1計算機有18條；Pentium有一條5段的定點和一條8段的浮點流水線；PentiumⅢ有三條指令流水線，其中兩條定點指令流水線，一條浮點指令流水線。多功能：流水線的各段通過不同連接實現(xiàn)不同功能Texas公司的ASC計算機中的8段流水線，能夠?qū)崿F(xiàn)：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運算等。流水線的分類（續(xù)）按多功能的連接方式靜態(tài)：同一段時間內(nèi)，多功能流水線中的各個功能段只能按照一種固定的方式連接，實現(xiàn)一種固定的功能。只有連續(xù)出現(xiàn)同一種運算時，流水線的效率才能得到充分的發(fā)揮。動態(tài)：在同一段時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。1時間空間023…n123…n123…n123…n123…n123…n1234…123…12……1輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出靜態(tài)流水線時空圖浮點加法定點乘法1時間空間023…n123…n123…n123…n123…n123…n輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出動態(tài)流水線時空圖………………123546123541234123…………浮點加法定點乘法流水線的分類（續(xù)）按數(shù)據(jù)表示標(biāo)量流水：沒有向量數(shù)據(jù)，只能用標(biāo)量循環(huán)方式來對向量、數(shù)組進行處理。Amdahl470V/6IBM360/91向量流水：設(shè)置有向量指令和向量運算硬件，能對向量、數(shù)組中的各個元素流水地處理。CRAY-1流水線的分類（續(xù)）按是否有反饋回路線性(LinearPipelining)：每個流水段都流過一次，且僅流過一次非線性(NonlinearPipelining)：在流水線的某些流水段之間有反饋回路或前饋回路1234入出非線性流水線流水線的分類（續(xù)）按照控制方式：同步流水線異步流水線順序流水線與亂序流水線：亂序流水線又稱為無序流水線、錯序流水線或異步流水線等流水線處理機的主要性能

通過時空圖分析

吞吐率（TP,ThoughputRate）

加速比（SpeedRatio）效率（Efficiency）

吞吐率（TP,ThoughputRate）

是流水線單位時間里能流出的任務(wù)數(shù)或結(jié)果數(shù)。

1時間空間S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nmDt(n-1)DtnDt(m-1)DtTS1輸入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt輸出1時間空間S1S2S3S4SDti(n-1)Dt2Tk23…n123…n123…n123…n吞吐率（續(xù)）

解決瓶頸子過程的辦法細(xì)分S1輸入輸出DtS2-1DtS2-2DtS2-3DtS3DtS4DtS2(3Dt)細(xì)分1471014710Ss3bs3as2s1t1t12t17Ts3cs468111235911122359268147103591112268147103591112268147103591112268147103591112268吞吐率（續(xù)）瓶頸段并聯(lián)S1輸入輸出Dt1=DtS2-1S2-1S2-1S3S4Dt3=DtDt4=DtDt2=3Dt1時間空間23nS1S2-1456…14…-2-1n-225…n-136…n123n456…-2-1123n456…-2-1S2-2S2-3S3S4并聯(lián)吞吐率（續(xù)）說明：加速比（SpeedRatio）

指流水線的速度與等效的非流水線的速度之比。加速比（續(xù)）加速比（續(xù)）m=6m=10任務(wù)

個數(shù)加速比10246811248163264128效率（Efficiency）Eta

是指流水線中的設(shè)備實際使用時間占整個運行時間之比，也稱流水線設(shè)備的時間利用率。

效率（續(xù)）效率舉例1：用一條4段浮點加法器流水線求8個浮點數(shù)的和：

Z＝A＋B＋C＋D＋E＋F＋G＋H解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1時間空間23求階差4567123456712345671234567對階尾數(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+HZ7個浮點加法共用了15個時鐘周期。流水線的吞吐率為：流水線的加速比為：流水線的效率為舉例2:（靜態(tài)多功能流水線）設(shè)有兩個向量A和B，各有4個元素，要在如圖所示的靜態(tài)雙功能流水線上，計算向量點積AB，其中1-〉2-〉3-〉5組成加法流水線，1-〉4-〉5組成乘法流水線，又設(shè)每個流水線所經(jīng)過的時間均為Dt，而且流水線的輸出結(jié)果可以直接返回到輸入或存于相應(yīng)的緩沖寄存器中，其延遲時間和功能切換所需的時間都可以忽略不計。12354xyzA*B=a1b1+a2b2+a3b3+a4b4空間時間12345678910111213141516靜態(tài)多功能流水線實際吞吐率TP=7/15Dt加速比Sp=24Dt/(15Dt)=1.6效率η=（3*4Dt+4*3Dt）/（5*15Dt)=0.32=32%A*B=a1b1+a2b2+a3b3+a4b4空間時間12345678910111213141516動態(tài)多功能流水線實際吞吐率TP=7/14Dt加速比Sp=24Dt/(14Dt)=1.714效率η=（3*4Dt+4*3Dt）/（5*14Dt)=0.343=34.3%舉例3：書中P190第6題有一個雙輸入端的加-乘雙功能靜態(tài)流水線，由經(jīng)過時間分別為Dt、2Dt、2Dt、Dt的1、2、3、4四個子過程構(gòu)成，加法時按1-〉2-〉4連接，乘法時按1-〉3-〉4連接。流水線輸出設(shè)有緩沖器，也可將數(shù)據(jù)直接回授到流水線輸入端?，F(xiàn)要執(zhí)行

A*(B+C*(D+E*F))+G*H

的運算，請對運算順序進行交換，畫出能獲得盡可能高的吞吐率的流水時空圖；標(biāo)出流水線入、出端的操作數(shù)變化情況；求出完成全部運算所需時間及此期間整個流水線的效率。如對流水線瓶頸子過程細(xì)分，最少需多少時間完成全部運算？若子過程3已無法再細(xì)分，只能采用并聯(lián)方法改進，問流水線的效率為多少？A*B+A*C*D+A*C*E*F+G*H空間時間123456789101112131415161718192021222324效率η=（6*4Dt+3*4Dt）/（4*24Dt)=3/8時間空間123456789101112131415161718效率η=（6*4Dt+3*4Dt）/（6*18Dt)=1/3空間123456789101112131415161718效率η=（6*4Dt+3*4Dt）/（6*18Dt)=1/3流水機器的相關(guān)處理和控制機構(gòu)流水線只有連續(xù)不斷地流動，不出現(xiàn)斷流，才能獲得高效率。如果處理不當(dāng)，就會使流水效率顯著下降。全局相關(guān)：轉(zhuǎn)移相關(guān)局部相關(guān)流水機器的相關(guān)處理和控制機構(gòu)

局部性相關(guān)的處理

全局性相關(guān)的處理------轉(zhuǎn)移相關(guān)

流水機器的中斷處理

流水線調(diào)度-----非線性流水線

局部性相關(guān)的處理局部性相關(guān)：指令相關(guān)、訪存操作數(shù)相關(guān)、通用寄存器組相關(guān)原因：在機器同時解釋多條指令之間出現(xiàn)了對同一主存單元或寄存器要求“先寫后讀”而產(chǎn)生的。解決：推后后續(xù)指令對相關(guān)單元的讀，直至在先的指令寫入完成設(shè)置相關(guān)直接通路，將運算結(jié)果經(jīng)相關(guān)直接通路直接送入所需部件局部性相關(guān)的處理（續(xù)）任務(wù)在流水線中流動順序的安排和控制順序流動方式（同步流動方式）：任務(wù)流出流水線的順序保持與流入流水線的順序一致控制簡單，但相關(guān)后吞吐率和效率下降異步流動方式入指令地址：順序流動和異步流動指令j的源操作數(shù)地址與指令h的目的操作數(shù)地址相同時，h和j就發(fā)生先寫后讀的操作數(shù)相關(guān)。讀段寫段相關(guān)直接通路12345678nkkjjjm空il空hk空iihh可以不順序流動的順序流動的（推后）判出j、h相關(guān)出讀段寫段相關(guān)直接通路12345678nkkjjjm空il空hk空iihh出舉例：流動順序的控制8段流水線，第2段為讀段，第7段為寫段一串指令流入：h,i,j,k,l,m,n當(dāng)指令j的源操作數(shù)地址與指令h的目的操作數(shù)相同時，發(fā)生先寫后讀的操作數(shù)相關(guān)順序流動時：j讀段是停下來等待，直到h到達寫段并完成后，才流動。推后讀。優(yōu)點：控制比較簡單相關(guān)后流水線的吞吐率和效率下降舉例：流動順序的控制（續(xù)）異步流動：如果讓j之后的指令，如k,l,m,n，只要與j沒有相關(guān)，就越過j繼續(xù)向前流動。會發(fā)生其他相關(guān)寫-寫相關(guān)：對同一單元，要求在先的指令先寫入，在后的指令后寫入的關(guān)聯(lián)。先讀后寫相關(guān)：對同一單元，要求在先的指令先讀出，在后的指令再寫入的關(guān)聯(lián)。全局性相關(guān)的處理指的是已進入流水線的轉(zhuǎn)移指令（尤其是條件轉(zhuǎn)移指令）和其后續(xù)指令之間的相關(guān)。全局性相關(guān)的處理------轉(zhuǎn)移相關(guān)

猜測法

加快和提前形成條件碼加快單條指令內(nèi)部的條件碼的形成在一段程序內(nèi)提前形成條件碼（適合循環(huán)）采用延遲轉(zhuǎn)移------采用軟件進行靜態(tài)指令調(diào)度加快短循環(huán)程序的處理

猜測法i-3i-2i-1ii+1i+2i+3i+4pp+1p+2p+3猜測路徑（轉(zhuǎn)移不成功路徑）轉(zhuǎn)移成功路徑轉(zhuǎn)移不成功分支轉(zhuǎn)移指令猜測法（續(xù)）在典型的標(biāo)量類機器指令程序中，條件轉(zhuǎn)移指令占20%，其中轉(zhuǎn)移成功的概率有約占其中的60%。流水機器的中斷處理中斷的出現(xiàn)概率比條件轉(zhuǎn)移的概率要低。處理中斷的主要問題：斷點現(xiàn)場的保護和恢復(fù)，而不是縮短流水線的斷流時間。不精確斷點：無論指令I(lǐng)在流水線的哪一段發(fā)生中斷，都不再允許尚未進入流水線的后續(xù)指令再進入，但已在流水線的所有指令仍繼續(xù)流動到執(zhí)行完畢，然后才轉(zhuǎn)入中斷處理程序。IBM360/91不利于編程和程序的排錯精確斷點：無論指令I(lǐng)是在流水線中的哪一段響應(yīng)中斷，給中斷現(xiàn)場全都是對應(yīng)I的，I之后流入流水線內(nèi)的指令的原有現(xiàn)場都能保存和恢復(fù)。需設(shè)置很多后援寄存器控制邏輯比較復(fù)雜S1S2S3S4S5S6S7S8不精確斷點精確斷點流水線處理機的中斷處理相關(guān)問題相關(guān)（correlation）：指在一段程序的相近指令之間有某種關(guān)系，這種關(guān)系可能影響指令的重疊執(zhí)行。數(shù)據(jù)相關(guān)：局部相關(guān)控制相關(guān)：全局相關(guān)數(shù)據(jù)相關(guān)在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址偏移量等正好是前面指令的執(zhí)行結(jié)果，則必須等待前面的指令執(zhí)行完成，并把結(jié)果寫到主存或通用寄存器中之后，本條指令才能執(zhí)行。指令相關(guān)主存操作數(shù)相關(guān)通用寄存器相關(guān)變址相關(guān)控制相關(guān)指由條件分支指令、轉(zhuǎn)子程序指令、終斷等引起的相關(guān)。指令相關(guān)第k+1條指令本身的內(nèi)容取決于第k條指令的執(zhí)行結(jié)果。解決：程序中不允許修改指令。主存操作數(shù)相關(guān)當(dāng)指令的執(zhí)行結(jié)果寫到主存儲器，所讀取的操作數(shù)也取自主存儲器時。解決：推后處理法通用寄存器相關(guān)在寄存器-寄存器型和寄存器-存儲器型指令的執(zhí)行過程中有可能發(fā)生通用寄存器數(shù)據(jù)相關(guān)。解決在通用寄存器和運算器之間建立直接數(shù)據(jù)通路推后處理設(shè)置專用數(shù)據(jù)通路變址相關(guān)變址寄存器發(fā)生相關(guān)。解決推后分析設(shè)置專用通路總結(jié)：數(shù)據(jù)相關(guān)的解決方法采用硬件或軟件的辦法盡量避免數(shù)據(jù)相關(guān)發(fā)生是在確保指令正確執(zhí)行的前提下，推后指令分析設(shè)置專用通路轉(zhuǎn)移相關(guān)無條件轉(zhuǎn)移一般條件轉(zhuǎn)移復(fù)合條件轉(zhuǎn)移無條件轉(zhuǎn)移相關(guān)一般能夠在指令分析器中就執(zhí)行完成。對程序執(zhí)行速度的影響很小。分析k執(zhí)行k分析k+1取指令L分析L執(zhí)行L分析L執(zhí)行L分析L+1執(zhí)行L+1指令L不在先行指令緩沖棧中：指令L在先行指令緩沖棧中：一般條件轉(zhuǎn)移對程序執(zhí)行速度造成的影響很大。緩沖深度越深，影響越大。分析k執(zhí)行k分析k+1分析k+2執(zhí)行k+2分析k+1分析L執(zhí)行L分析k+1取指令L分析L執(zhí)行L轉(zhuǎn)移不成功成功，L在指緩棧中成功，L不在指緩棧中產(chǎn)生轉(zhuǎn)移條件CC根據(jù)轉(zhuǎn)移條件CC判斷轉(zhuǎn)移是否成功復(fù)合條件轉(zhuǎn)移本身是一條運算指令，根據(jù)結(jié)果決定后轉(zhuǎn)移。影響比一般條件轉(zhuǎn)移指令要大。分析K執(zhí)行k分析K+1執(zhí)行k+1分析L執(zhí)行L取指令L分析L執(zhí)行L轉(zhuǎn)移不成功成功，L在先行指令緩沖棧中成功，L不在先行指令緩沖棧中轉(zhuǎn)移預(yù)測技術(shù)軟件“猜測法”不改變硬件結(jié)構(gòu)，只修改編譯器。硬件“猜測法”增設(shè)指令分析器兩個先行指令緩沖棧增設(shè)先行目標(biāo)緩沖棧短循環(huán)程序的處理短循環(huán)程序的三個條件循環(huán)體的長度小于等于先行指令緩沖棧的深度循環(huán)次數(shù)的控制采用計數(shù)轉(zhuǎn)移指令控制循環(huán)的條件轉(zhuǎn)移指令一般是向后轉(zhuǎn)移的指令短循環(huán)程序的處理（續(xù)）解決好三個問題指令分析器如何發(fā)現(xiàn)短循環(huán)程序如何控制短循環(huán)程序在先行指令緩沖棧中不被清除如何控制循環(huán)體的執(zhí)行次數(shù)短循環(huán)程序的處理（續(xù)）在指令系統(tǒng)中設(shè)置專門的短循環(huán)程序的開門指令和關(guān)門指令用專門的硬件來識別短循環(huán)程序流水線調(diào)度--非線性流水線

由于非線性流水線有反饋回路，因此會出現(xiàn)幾個任務(wù)爭用同一功能段的沖突現(xiàn)象前饋線、后饋線功能部件沖突（流水線沖突）流水線的調(diào)度S1S2S3S4S5入①②③④⑥⑤⑦⑧⑦⑨出⑧非線性流水線的表示對非線性流水線，采用：二維預(yù)約表（ReservationTable）1971年E.S.Davidson提出。1234567891XX2XXX3X4XX5XX段號k拍號n非線性流水線的沖突向一條非線性流水線的輸入端連續(xù)輸入兩個任務(wù)之間間隔稱為非線性流水線的啟動距離或等待時間。段號

k拍號n1234567891011121314151X1X2X3X1X2X32X1X1X2X2X1X3X3X2X33X1X2X34X1X1X2X2X3X35X1X1X2X2X3X3啟動距離為3的流水線沖突情況舉例1234567891**2***3*4**5**段號k拍號n預(yù)約表延遲禁止表F(ForbiddenList){1,5,6,8},相鄰兩個任務(wù)的間隔拍數(shù)不能為1，5，6，8沖突向量C(CollisionVector)第i位的狀態(tài)用以表示與當(dāng)時相隔i拍給流水線送入后繼任務(wù)是否會發(fā)生功能段的使用沖突。如不發(fā)生，0，否則，1C=(10110001)

初始沖突向量（1）形成預(yù)約表

指令總拍數(shù)為n，流水線有k個段，則形成n×k的預(yù)約表，段的使用情況用“×”表示。

預(yù)約表如下：××5××4×3××××2××1987654382716tS（2）由預(yù)約表形成禁止表F

F={各段中沖突間隔拍數(shù)}本例：F={1，5，6，8}××5××4×3××××2××1987654382716tS××××5×××4×3××××2××1987654382716tS5681（3）由禁止表F形成初始沖突向量C0

C0=（cN…c0），ci=1沖突，=0不沖突。本例：C0=（10110001）。（4）由初始沖突向量C0形成狀態(tài)轉(zhuǎn)換圖

a.C0每過一拍邏輯右移一位，若移出0，則允許后續(xù)指令進入流水線，再與C0按位“或”，形成新的沖突向量Ci；10110001101101111011110110111011初始狀態(tài)3427

2拍后，新指令(×-I2)進入后：×××5××××4××3×××××2×××1987654321tS643I1與I3的F={3,4,6}，I2與I3的F={1,5,6,8},新F={1,3,4,5,6,8}，C2=(10111101)。

注意：Ci為第i拍后流水線的沖突向量，此時流水線中已有兩條指令，Ci用于判斷第三條指令的進入。1011000110110111101111011011101110111111初始狀態(tài)34422777

b.各Ci再每過一拍邏輯右移一位，若移出0，允許后續(xù)指令進入，再與C0按位“或”，形成新的沖突向量Cij；

注意：Cij為第i+j拍后流水線的沖突向量，此時流水線中已有三條指令，Cij用于判斷第四條指令的進入。對C2，再2拍后，新指令(×-I3)進入后：

421×××5×××××4×××3×××××××2××××1987654321tS×××××98I1與I4的F={1,2,4}，I2與I4的F={3,4,6},I3與I4的F={1,5,6,8},新F={1,2,3,4,5,6,8}，C22=(10111111)。643

注意：Cij為第i+j拍后流水線的沖突向量，此時流水線中已有三條指令，Cij用于判斷第四條指令的進入。

c.重復(fù)上一步驟，直到不再生成新的沖突向量為止。1011000110110111101111011011101110111111初始狀態(tài)34342277777（5）找出最加調(diào)度方案

從各個閉合回路中找出平均間隔最小的一個。1011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000100101111（右移2位）101111111011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000100101111（右移2位）101111111011000100010110（右移3位）101101111011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000100101111（右移2位）101111111011000100010110（右移3位）101101111011000100001011（右移4位）10111011調(diào)度方案平均間隔拍數(shù)調(diào)度方案平均間隔拍數(shù)（2，2，7）3.67（3，7）5.00（2，7）4.50（4，3，7）4.67（3，4）3.50（4，7）5.50（4，3）3.50（7）7.00（3，4，7）4.671234567891011121314151X1X2X3X1X22X1X1X2X2X1X3X3X2X33X1X2X34X1X1X2X2X3X35X1X1X2X2X3X3按(3,4)進行調(diào)度111112222213333324444364556666556124355456按(3,4)進行調(diào)度

TP=6/26Sp=(6*10)/26=30/13e=(6*10)/(26*5)=60/130=6/13111112222213333324444364556666556124355456按(4,3)進行調(diào)度

TP=6/27Sp=(6*10)/27=20/9e=(6*10)/(27*5)=12/27舉例：一條有4個流水段的非線性流水線，每個流水段的延遲時間都相等，它的預(yù)約表如下圖：時間流水段1234567S1XXS2XXS3XXS4X（1）寫出流水線的禁止向量和初始沖突向量（2）畫出調(diào)度流水線的狀態(tài)圖（3）求流水線的最小啟動循環(huán)和最小啟動距離（4）求平均啟動距離最小的恒定循環(huán)。解：（1）禁止向量為（2，4，6）沖突向量：用二進制表示，長度是禁止向量的最大距離。沖突向量C=（C1C2C3C4C5C6），由禁止向量，C2=C4=C6=1，其余位為0，沖突向量為

C=（101010）。（2）由沖突向量構(gòu)造一張圖：將C放到一個6位邏輯右移移位器，當(dāng)從移位器移出0，用移位器中的值與初始沖突向量做“按位或”，得到一個新的沖突向量。當(dāng)移位器移出1，不做任何處理。重復(fù)這個步驟。對產(chǎn)生的每一個新的沖突向量做同樣處理。在初始沖突向量和所有形成的沖突向量之間，箭頭連接。1010101111111011111010117*157*3537*當(dāng)右移2、4、6位，時移出位為1，表示用這些啟動距離輸入新任務(wù)要發(fā)生沖突，不做任何處理。當(dāng)右移1、3、5和大于等于7位時，移出位是0，表示用這些啟動距離輸入新任務(wù)不會發(fā)生沖突。7*表示大于等于75（3）從狀態(tài)圖中可以找到許多不發(fā)生流水段沖突的啟動循環(huán)。，只要找到簡單循環(huán)，進而確定平均啟動距離最小的啟動循環(huán)。它們是：（1，7）、（3，5，7）、（5，7）等簡單循環(huán)平均啟動距離（1，7）4（3，5）4（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7最小啟動循環(huán)是具有最小平均最小啟動距離的啟動循環(huán)。最小循環(huán)為（1，7）、（3，5）最小恒定