第5章標(biāo)量處理機(jī)(5.1,5.2,5.3)-性能與非線性調(diào)度

第5章流水線技術(shù)5.1 流水線的基本概念5.2 流水線的性能指標(biāo)5.3非線性流水線的調(diào)度5.4 相關(guān)性分析技術(shù)5.5 超標(biāo)量處理機(jī)、超流水處理機(jī)、超標(biāo)量超流水處理機(jī)工業(yè)生產(chǎn)流水線下面通過(guò)一個(gè)例子來(lái)說(shuō)明流水線的好處:兩種方案兩種方案的工作過(guò)程對(duì)比流水線生產(chǎn)過(guò)程的抽象描述這種流水工作方式的主要特點(diǎn)5.1.1什么是流水線5.1流水線的基本概念5.1流水線的基本概念流水線技術(shù)把一個(gè)重復(fù)的過(guò)程分解為若干個(gè)子過(guò)程，每個(gè)子過(guò)程由專門(mén)的功能部件來(lái)實(shí)現(xiàn)。把多個(gè)處理過(guò)程在時(shí)間上錯(cuò)開(kāi)，依次通過(guò)各功能段，這樣，每個(gè)子過(guò)程就可以與其它的子過(guò)程并行進(jìn)行。流水線中的每個(gè)子過(guò)程及其功能部件稱為流水線的級(jí)或段，段與段相互連接形成流水線。流水線的段數(shù)稱為流水線的深度。5.1流水線的基本概念指令流水線把指令的解釋過(guò)程分解為分析和執(zhí)行兩個(gè)子過(guò)程，并讓這兩個(gè)子過(guò)程分別用獨(dú)立的分析部件和執(zhí)行部件來(lái)實(shí)現(xiàn)。

理想情況：速度提高一倍4段指令流水線5.1流水線的基本概念浮點(diǎn)加法流水線把流水線技術(shù)應(yīng)用于運(yùn)算的執(zhí)行過(guò)程，就形成了運(yùn)算操作流水線，也稱為部件級(jí)流水線。把浮點(diǎn)加法的全過(guò)程分解為求階差、對(duì)階、尾數(shù)相加、規(guī)格化四個(gè)子過(guò)程。理想情況：速度提高3倍時(shí)－空?qǐng)D時(shí)－空?qǐng)D從時(shí)間和空間兩個(gè)方面描述了流水線的工作過(guò)程。時(shí)－空?qǐng)D中，橫坐標(biāo)代表時(shí)間，縱坐標(biāo)代表流水線的各個(gè)段。浮點(diǎn)加法流水線的時(shí)空?qǐng)D時(shí)－空?qǐng)D時(shí)－空?qǐng)D從時(shí)間和空間兩個(gè)方面描述了流水線的工作過(guò)程。時(shí)－空?qǐng)D中，橫坐標(biāo)代表時(shí)間，縱坐標(biāo)代表流水線的各個(gè)段。浮點(diǎn)加法流水線的時(shí)空?qǐng)D

流水線需要有通過(guò)時(shí)間和排空時(shí)間。通過(guò)時(shí)間：第一個(gè)任務(wù)從進(jìn)入流水線到流出結(jié)果所需的時(shí)間。排空時(shí)間：最后一個(gè)任務(wù)從進(jìn)入流水線到流出結(jié)果所需的時(shí)間。流水技術(shù)的特點(diǎn)流水線把一個(gè)處理過(guò)程分解為若干個(gè)子過(guò)程（段），每個(gè)子過(guò)程由一個(gè)專門(mén)的功能部件來(lái)實(shí)現(xiàn)。流水線中各段的時(shí)間應(yīng)盡可能相等，否則將引起流水線堵塞、斷流。時(shí)間最長(zhǎng)的段將成為流水線的瓶頸。流水技術(shù)的特點(diǎn)流水線每一個(gè)段的后面都要有一個(gè)緩沖寄存器（鎖存器），稱為流水寄存器。作用：在相鄰的兩段之間傳送數(shù)據(jù)，以保證提供后面要用到的信息，并把各段的處理工作相互隔離。流水技術(shù)適合于大量重復(fù)的時(shí)序過(guò)程，只有在輸入端不斷地提供任務(wù)，才能充分發(fā)揮流水線的效率。流水技術(shù)的特點(diǎn)按照流水技術(shù)用于計(jì)算機(jī)系統(tǒng)的等級(jí)不同可以分為部件級(jí)、處理機(jī)級(jí)及處理機(jī)間流水線部件級(jí)流水線（運(yùn)算操作流水線）：把處理機(jī)中的部件分段，再把這些分段相互連接起來(lái)，使得各種類(lèi)型的運(yùn)算操作能夠按流水方式進(jìn)行。從不同的角度和觀點(diǎn)，把流水線分成多種不同的種類(lèi)。5.1.2流水線的分類(lèi)處理機(jī)級(jí)流水線（指令流水線）：把指令的執(zhí)行過(guò)程按照流水方式處理。把一條指令的執(zhí)行過(guò)程分解為若干個(gè)子過(guò)程，每個(gè)子過(guò)程在獨(dú)立的功能部件中執(zhí)行。5.1.2流水線的分類(lèi)系統(tǒng)級(jí)流水線（宏流水線）：把多臺(tái)處理機(jī)串行連接起來(lái)，對(duì)同一數(shù)據(jù)流進(jìn)行處理，每個(gè)處理機(jī)完成整個(gè)任務(wù)中的一部分。

動(dòng)畫(huà)解析5.1.2流水線的分類(lèi)按照流水線所完成的功能可分為單功能流水線與多功能流水線單功能流水線：只能完成一種固定功能的流水線。多功能流水線：流水線的各段可以進(jìn)行不同的連接，以實(shí)現(xiàn)不同的功能。例：ASC的多功能流水線5.1.2流水線的分類(lèi)按照同一時(shí)間內(nèi)各段之間的連接方式對(duì)多功能流水線可作進(jìn)一步的劃分，分別為靜態(tài)流水線與動(dòng)態(tài)流水線靜態(tài)流水線：在同一時(shí)間內(nèi)，多功能流水線中的各段只能按同一種功能的連接方式工作。對(duì)于靜態(tài)流水線來(lái)說(shuō)，只有當(dāng)輸入的是一串相同的運(yùn)算任務(wù)時(shí)，流水的效率才能得到充分的發(fā)揮。例如：ASC的8段流水線5.1.2流水線的分類(lèi)動(dòng)態(tài)流水線：在同一時(shí)間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時(shí)執(zhí)行多種功能。動(dòng)畫(huà)優(yōu)點(diǎn)：靈活，能夠提高流水線各段的使用率，從而提高處理速度。缺點(diǎn)：控制復(fù)雜。靜、動(dòng)態(tài)流水線時(shí)空?qǐng)D的對(duì)比5.1.2流水線的分類(lèi)按照流水線中是否有反饋回路可以分為線性流水線與非線性流水線線性流水線：流水線的各段串行連接，沒(méi)有反饋回路。數(shù)據(jù)通過(guò)流水線中的各段時(shí)，每一個(gè)段最多只流過(guò)一次。非線性流水線：流水線中除了有串行的連接外，還有反饋回路。（舉例）

5.1.2流水線的分類(lèi)非線性流水線的調(diào)度問(wèn)題確定什么時(shí)候向流水線引進(jìn)新的任務(wù)，才能使該任務(wù)不會(huì)與先前進(jìn)入流水線的任務(wù)發(fā)生沖突——爭(zhēng)用流水段。

5.1.2流水線的分類(lèi)根據(jù)任務(wù)流入和流出的順序是否相同可以分為順序流水線與亂序流水線順序流水線：流水線輸出端任務(wù)流出的順序與輸入端任務(wù)流入的順序完全相同。每一個(gè)任務(wù)在流水線的各段中是一個(gè)跟著一個(gè)順序流動(dòng)的。亂序流水線：流水線輸出端任務(wù)流出的順序與輸入端任務(wù)流入的順序可以不同，允許后進(jìn)入流水線的任務(wù)先完成（從輸出端流出）。也稱為無(wú)序流水線、錯(cuò)序流水線、異步流水線5.1.2流水線的分類(lèi)標(biāo)量處理機(jī)與向量流水處理機(jī)把指令執(zhí)行部件中采用了流水線的處理機(jī)稱為流水線處理機(jī)。標(biāo)量處理機(jī)：處理機(jī)不具有向量數(shù)據(jù)表示和向量指令，僅對(duì)標(biāo)量數(shù)據(jù)進(jìn)行流水處理。向量流水處理機(jī)：具有向量數(shù)據(jù)表示和向量指令的處理機(jī)。是向量數(shù)據(jù)表示和流水技術(shù)的結(jié)合。5.1.2流水線的分類(lèi)5.2流水線的性能指標(biāo)吞吐率：在單位時(shí)間內(nèi)流水線所完成的任務(wù)數(shù)量或輸出結(jié)果的數(shù)量n：任務(wù)數(shù)Tk：處理完成n個(gè)任務(wù)所用的時(shí)間5.2.1吞吐率各段時(shí)間均相等的流水線各段時(shí)間均相等的流水線時(shí)空?qǐng)D5.2.1吞吐率流水線完成n個(gè)連續(xù)任務(wù)所需要的總時(shí)間為：（假設(shè)一條k段線性流水線）

Tk＝kΔt＋(n－1)Δt＝(k＋n－1)Δt

流水線的實(shí)際吞吐率最大吞吐率5.2.1吞吐率最大吞吐率與實(shí)際吞吐率的關(guān)系流水線的實(shí)際吞吐率小于最大吞吐率，它除了與每個(gè)段的時(shí)間有關(guān)外，還與流水線的段數(shù)k以及輸入到流水線中的任務(wù)數(shù)n等有關(guān)。只有當(dāng)n>>k時(shí)，才有TP≈TPmax。5.2.1吞吐率各段時(shí)間不完全相等的流水線各段時(shí)間不等的流水線及其時(shí)空?qǐng)D舉例1（時(shí)空?qǐng)D）一條4段的流水線S1，S3，S4各段的時(shí)間：ΔtS2的時(shí)間：3Δt（瓶頸段）流水線中這種時(shí)間最長(zhǎng)的段稱為流水線的瓶頸段。

5.2.1吞吐率舉例2：一條5段的流水線S1，S2，S3，S5各段的時(shí)間：ΔtS4的時(shí)間：3Δt（瓶頸段）各段時(shí)間不等的流水線的實(shí)際吞吐率為：（Δti為第i段的時(shí)間，共有k個(gè)段）流水線的最大吞吐率為：

5.2.1吞吐率對(duì)前面舉例2中的5段流水線最大吞吐率為：

5.2.1吞吐率細(xì)分瓶頸段舉例例如：對(duì)前面的5段流水線把瓶頸段S4細(xì)分為3個(gè)子流水線段：S4-1，S4-2，S4-3改進(jìn)后的流水線的吞吐率：解決流水線瓶頸問(wèn)題的常用方法重復(fù)設(shè)置瓶頸段舉例：時(shí)-空?qǐng)D缺點(diǎn)：控制邏輯比較復(fù)雜，所需的硬件增加了。例如：對(duì)前面的5段流水線重復(fù)設(shè)置瓶頸段S4：S4a，S4b，S4c解決流水線瓶頸問(wèn)題的常用方法加速比：完成同樣一批任務(wù)，不使用流水線所用的時(shí)間與使用流水線所用的時(shí)間之比。假設(shè)：不使用流水線（即順序執(zhí)行）所用的時(shí)間為T(mén)s，使用流水線后所用的時(shí)間為T(mén)k，則該流水線的加速比為：5.2.2流水線的加速比流水線各段時(shí)間相等（都是△t）一條k段流水線完成n個(gè)連續(xù)任務(wù)所需要的時(shí)間為：

Tk=(k＋n－1)Δt順序執(zhí)行n個(gè)任務(wù)所需要的時(shí)間：

Ts=nk△t

（解釋）流水線的實(shí)際加速比為：5.2.2流水線的加速比最大加速比當(dāng)n>>k時(shí)，S

≈

k

思考：流水線的段數(shù)愈多愈好？

5.2.2流水線的加速比流水線最佳段數(shù)的選擇

流水線的最佳段數(shù)與流水線的延遲時(shí)間t與流水線本身的價(jià)格a的乘積平方根成正比，而與鎖存器的延遲時(shí)間d及價(jià)格b的乘積的平方根成反比。即在設(shè)計(jì)一條流水線時(shí)，可以根據(jù)該公式，在流水線的延遲時(shí)間t一定的情況下，通過(guò)調(diào)整流水線本身的價(jià)格a、鎖存器的延遲時(shí)間d和瑣存器的價(jià)格b來(lái)選擇最佳流水線段數(shù)k0.流水線的各段時(shí)間不完全相等時(shí)一條k段流水線完成n個(gè)連續(xù)任務(wù)的實(shí)際加速比為：5.2.2流水線的加速比

流水線的效率：流水線中的設(shè)備實(shí)際使用時(shí)間與整個(gè)運(yùn)行時(shí)間的比值，即流水線設(shè)備的利用率。

由于流水線有通過(guò)時(shí)間和排空時(shí)間，所以在連續(xù)完成n個(gè)任務(wù)的時(shí)間內(nèi)，各段并不是滿負(fù)荷地工作。各段時(shí)間相等各段的效率ei相同(解釋)5.2.3流水線的效率整條流水線的效率為：

可以寫(xiě)成：

最高效率為：

當(dāng)n>>k時(shí)，E≈1。5.2.2流水線的加速比當(dāng)流水線各段時(shí)間相等時(shí)，流水線的效率與吞吐率成正比。

E=TP·△t

流水線的效率是流水線的實(shí)際加速比S與它的最大加速比k的比值。當(dāng)E=1時(shí)，S=k，實(shí)際加速比達(dá)到最大。5.2.2流水線的加速比從時(shí)空?qǐng)D上看，效率就是n個(gè)任務(wù)占用的時(shí)空面積和k個(gè)段總的時(shí)空面積之比。當(dāng)各段時(shí)間不相等時(shí)：5.2.2流水線的加速比P197例5.1：用一條4段浮點(diǎn)加法器流水線求8個(gè)浮點(diǎn)數(shù)的和：

Z＝A＋B＋C＋D＋E＋F＋G＋H1時(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+HZ解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]流水線的吞吐率為：流水線的加速比為：流水線的效率為：7個(gè)浮點(diǎn)加法共用了15個(gè)時(shí)鐘周期：

例3.1

設(shè)在下圖所示的靜態(tài)流水線上計(jì)算：

流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中，試計(jì)算其吞吐率、加速比和效率。(每段的時(shí)間都為△t)5.2.4流水線性能分析舉例解：（1）選擇適合于流水線工作的算法先計(jì)算A1+B1、A2+B2、A3+B3和A4+B4；再計(jì)算(A1+B1)×(A2+B2)和(A3+B3)×(A4+B4)；然后求總的乘積結(jié)果。（2）畫(huà)出時(shí)空?qǐng)D5.2.4流水線性能分析舉例在18個(gè)△t時(shí)間中，給出了7個(gè)結(jié)果。吞吐率為：

不用流水線，由于一次求和需6△t，一次求積需4△t，則產(chǎn)生上述7個(gè)結(jié)果共需（4×6+3×4）△t=36△t

加速比為：（3）計(jì)算性能5.2.4流水線性能分析舉例

流水線的效率可以看出，在求解此問(wèn)題時(shí)，該流水線的效率不高。

(原因)5.2.4流水線性能分析舉例主要原因多功能流水線在做某一種運(yùn)算時(shí)，總有一些段是空閑的；靜態(tài)流水線在進(jìn)行功能切換時(shí)，要等前一種運(yùn)算全部流出流水線后才能進(jìn)行后面的運(yùn)算；運(yùn)算之間存在關(guān)聯(lián)，后面有些運(yùn)算要用到前面運(yùn)算的結(jié)果；流水線的工作過(guò)程有建立與排空部分。5.2.4流水線性能分析舉例運(yùn)算之間存在關(guān)聯(lián)，后面有些運(yùn)算要用到前面運(yùn)算的結(jié)果；（數(shù)據(jù)相關(guān)）流水線的工作過(guò)程有建立與排空部分。流水線的效率

下面我們?cè)倏匆粋€(gè)例子：

例在靜態(tài)流水線上計(jì)算:

求：吞吐率，加速比，效率。解：(1)確定適合于流水處理的計(jì)算過(guò)程

(2)畫(huà)時(shí)空?qǐng)D

(3)計(jì)算性能吞吐率TP＝7／(20△t)

加速比S＝(34△t)／(20△t)＝1.7

效率E＝(4×4＋3×6)／(8×20)＝0.215.2.4流水線性能分析舉例可以看出，在求解此問(wèn)題時(shí)，該流水線的效率不高。動(dòng)態(tài)流水線的時(shí)－空?qǐng)D舉例Ⅰ舉例Ⅱ:這樣行不行？正確答案5.2.4流水線性能分析舉例

例5.2有一條動(dòng)態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第4段的時(shí)間為2△t，其余各段時(shí)間均為△t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中。若在該流水線上計(jì)算:

試計(jì)算其吞吐率、加速比和效率。5.2.4流水線性能分析舉例解:(1)選擇適合于流水線工作的算法應(yīng)先計(jì)算A1×B1、A2×B2、A3×B3和A4×B4；再計(jì)算(A1×B1)＋(A2×B2)

(A3×B3)＋(A4×B4)；然后求總的累加結(jié)果。(2)畫(huà)出時(shí)空?qǐng)D(3)計(jì)算性能5.2.4流水線性能分析舉例瓶頸問(wèn)題理想情況下，流水線在工作時(shí)，其中的任務(wù)是同步地每一個(gè)時(shí)鐘周期往前流動(dòng)一段。當(dāng)流水線各段不均勻時(shí)，機(jī)器的時(shí)鐘周期取決于瓶頸段的延遲時(shí)間。在設(shè)計(jì)流水線時(shí)，要盡可能使各段時(shí)間相等。流水線的額外開(kāi)銷(xiāo)流水寄存器延遲時(shí)鐘偏移開(kāi)銷(xiāo)5.2.5流水線設(shè)計(jì)中的若干問(wèn)題流水寄存器需要建立時(shí)間和傳輸延遲建立時(shí)間：在觸發(fā)寫(xiě)操作的時(shí)鐘信號(hào)到達(dá)之前，寄存器輸入必須保持穩(wěn)定的時(shí)間。傳輸延遲：時(shí)鐘信號(hào)到達(dá)后到寄存器輸出可用的時(shí)間。時(shí)鐘偏移開(kāi)銷(xiāo)流水線中，時(shí)鐘到達(dá)各流水寄存器的最大差值時(shí)間。（時(shí)鐘到達(dá)各流水寄存器的時(shí)間不是完全相同）5.2.5流水線設(shè)計(jì)中的若干問(wèn)題幾個(gè)問(wèn)題流水線并不能減少（而且一般是增加）單條指令的執(zhí)行時(shí)間，但卻能提高吞吐率。增加流水線的深度（段數(shù)）可以提高流水線的性能。流水線的深度受限于流水線的額外開(kāi)銷(xiāo)。當(dāng)時(shí)鐘周期小到與額外開(kāi)銷(xiāo)相同時(shí)，流水已沒(méi)意義。因?yàn)檫@時(shí)在每一個(gè)時(shí)鐘周期中已沒(méi)有時(shí)間來(lái)做有用的工作。沖突問(wèn)題：流水線設(shè)計(jì)中要解決的重要問(wèn)題之一。5.2.5流水線設(shè)計(jì)中的若干問(wèn)題在非線性流水線中，存在反饋回路，當(dāng)一個(gè)任務(wù)在流水線中流過(guò)時(shí)，可能要多次經(jīng)過(guò)某些段。流水線調(diào)度要解決的問(wèn)題：

應(yīng)按什么樣的時(shí)間間隔向流水線輸入新任務(wù)，才能既不發(fā)生功能段使用沖突，又能使流水線有較高的吞吐率和效率？5.3非線性流水線的調(diào)度如果在第n個(gè)時(shí)鐘周期使用第k段，則在第k行和第n列的交叉處的格子里有一個(gè)×。如果在第k行和第n列的交叉處的格子里有一個(gè)×

，則表示在第n個(gè)時(shí)鐘周期要使用第k段。

非線形流水線的連接圖和預(yù)約表

一張預(yù)約表可能與多個(gè)流水線連接圖相對(duì)應(yīng)

一個(gè)流水線連接圖對(duì)應(yīng)與多張預(yù)約表向一條非線性流水線的輸入端連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔稱為非線性流水線的啟動(dòng)距離。會(huì)引起非線性流水線功能段使用沖突的啟動(dòng)距離則稱為禁用啟動(dòng)距離。啟動(dòng)距離和禁用啟動(dòng)距離一般都用時(shí)鐘周期數(shù)來(lái)表示，是一個(gè)正整數(shù)。5.3.1單功能非線性流水線的最優(yōu)調(diào)度啟動(dòng)距離：連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔流水線沖突：幾個(gè)任務(wù)爭(zhēng)用同一個(gè)流水段計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第五章標(biāo)量處理機(jī)68返回例：一個(gè)4功能段非線性流水線預(yù)約表

如何找出該預(yù)約表對(duì)應(yīng)的啟動(dòng)循環(huán)，該循環(huán)有最小平均啟動(dòng)距離？使非線性流水線在任何一個(gè)時(shí)鐘周期都不發(fā)生沖突的循環(huán)數(shù)列稱為非線性流水線的啟動(dòng)循環(huán)。由E.S.Davidson于1971年提出。根據(jù)預(yù)約表得到所有的禁止啟動(dòng)距離——禁止向量。

F={6，4，2}根據(jù)禁止向量得到?jīng)_突向量。

C=（101010）開(kāi)始畫(huà)出狀態(tài)圖

時(shí)間流水123456789101112S1X1X2X3X1X2X3S2X1X2X1X3X2X3S3X1X1X2X3X2X3S4X1X2X3X3與X2以間隔1拍進(jìn)入流水線與X1產(chǎn)生了爭(zhēng)用流水段X2與X1以間隔3拍的間隔進(jìn)入流水線為例說(shuō)明X2與X1以間隔3拍的間隔進(jìn)入流水線為例說(shuō)明

時(shí)間流水1234567891011121314S1X1X2X1X3X2X3S2X1X2X1X3X2X3S3X1X1X2X2X3X3S4X1X2X3X3與X2以間隔3拍進(jìn)入流水線與X1產(chǎn)生了爭(zhēng)用流水段根據(jù)狀態(tài)圖找出簡(jiǎn)單循環(huán)。簡(jiǎn)單循環(huán)平均啟動(dòng)距離（1，7）4（3，5）4（3，7）5（5，7）6（3，5，7）5（5，3，7）5（5）5（7）7最小啟動(dòng)循環(huán)是具有最小平均最小啟動(dòng)距離的啟動(dòng)循環(huán)。（1，7）（3，5）根據(jù)預(yù)約表寫(xiě)出禁止向量F禁止向量F：一個(gè)由禁用啟動(dòng)距離構(gòu)成的集合。

具體方法對(duì)于預(yù)約表的每一行的任何一對(duì)×，用它們所在的列號(hào)相減（大的減小的），列出各種可能的差值，然后刪除相同的，剩下的就是禁止向量的元素。在上例中：第一行的差值有：6；第二行的差值有：4；第三行的差值：2；第四行只有一個(gè)×

，沒(méi)有差值；其禁止向量是：F={6，4，2}5.3.1單功能非線性流水線的最優(yōu)調(diào)度根據(jù)禁止表F寫(xiě)出初始沖突向量C0（進(jìn)行從一個(gè)集合到一個(gè)二進(jìn)制位串的變換）沖突向量C：一個(gè)N位的二進(jìn)制位串。設(shè)C0=（cNcN-1…ci…c2c1），則：ci=0

：允許間隔i個(gè)時(shí)鐘周期后送入后續(xù)任務(wù)ci=1：不允許間隔i個(gè)時(shí)鐘周期后送入后續(xù)任務(wù)對(duì)于上面的例子

F={6，4，2}

C0=（101010）5.3.1單功能非線性流水線的最優(yōu)調(diào)度F={6，4，2}是相鄰兩個(gè)任務(wù)進(jìn)入流水線時(shí)會(huì)產(chǎn)生爭(zhēng)用同一段段的節(jié)拍間隔數(shù)的綜合。由F可以得出C0根據(jù)初始沖突向量C0畫(huà)出狀態(tài)轉(zhuǎn)換圖當(dāng)?shù)谝粋€(gè)任務(wù)流入流水線后，初始沖突向量C0決定了下一個(gè)任務(wù)需間隔多少個(gè)時(shí)鐘周期才可以流入。由C0=（101010）決定了第二個(gè)任務(wù)只能以1拍、3拍或者5拍的間隔進(jìn)入流水線才不會(huì)產(chǎn)生功能段的沖突。在第二個(gè)任務(wù)流入后，新的沖突向量是怎樣的呢？

這與前一個(gè)任務(wù)在流水線中已經(jīng)進(jìn)行了幾拍有關(guān)。當(dāng)?shù)诙€(gè)任務(wù)流入流水線以后，應(yīng)當(dāng)產(chǎn)生新的沖突向量，以便決定第三個(gè)任務(wù)可以間隔多少拍流入流水線，才不會(huì)與已經(jīng)進(jìn)入流水線的第一個(gè)和第二個(gè)任務(wù)爭(zhēng)用流水段。以第二個(gè)任務(wù)間隔3拍的間隔進(jìn)入流水線為例說(shuō)明。此時(shí)第二個(gè)任務(wù)間隔3拍進(jìn)入流水線時(shí)，第一個(gè)任務(wù)已經(jīng)在流水線里流動(dòng)了3拍。此時(shí)要是再有任務(wù)進(jìn)入流水線，則新的禁止進(jìn)入的間隔拍數(shù)應(yīng)該在原來(lái)的基礎(chǔ)上減去3拍。（原來(lái)禁止拍數(shù)為6拍、4拍、2拍，當(dāng)前則成為3拍和1拍）。即X3以3拍或者1拍進(jìn)入流水線，必與X1產(chǎn)生爭(zhēng)用功能段的情況。以第二個(gè)任務(wù)間隔3拍的間隔進(jìn)入流水線為例說(shuō)明。此時(shí)第二個(gè)任務(wù)間隔3拍進(jìn)入流水線時(shí)，第一個(gè)任務(wù)已經(jīng)在流水線里流動(dòng)了3拍。此時(shí)要是再有任務(wù)進(jìn)入流水線，則新的禁止進(jìn)入的間隔拍數(shù)應(yīng)該在原來(lái)的基礎(chǔ)上減去3拍。（原來(lái)禁止拍數(shù)為6拍、4拍、2拍，當(dāng)前則成為3拍和1拍）。即X3以3拍或者1拍進(jìn)入流水線，必與X1產(chǎn)生爭(zhēng)用功能段的情況。

時(shí)間流水1234567891011121314S1X1X2X1X3X2X3S2X1X2X1X3X2X3S3X1X1X2X2X3X3S4X1X2X3X3以間隔3拍進(jìn)入流水線與X1產(chǎn)生了爭(zhēng)用流水段以第二個(gè)任務(wù)間隔3拍的間隔進(jìn)入流水線為例說(shuō)明。此時(shí)第二個(gè)任務(wù)間隔3拍進(jìn)入流水線時(shí)，第一個(gè)任務(wù)已經(jīng)在流水線里流動(dòng)了3拍。此時(shí)要是再有任務(wù)進(jìn)入流水線，則新的禁止進(jìn)入的間隔拍數(shù)應(yīng)該在原來(lái)的基礎(chǔ)上減去3拍。（原來(lái)禁止拍數(shù)為6拍、4拍、2拍，當(dāng)前則成為3拍和1拍）。即X3以3拍或者1拍進(jìn)入流水線，必與X1產(chǎn)生爭(zhēng)用功能段的情況。

時(shí)間流水123456789101112S1X1X2X3X1X2X3S2X1X2X1X3X2X3S3X1X1X2X3X2X3S4X1X2X3X3以間隔1拍進(jìn)入流水線與X1產(chǎn)生了爭(zhēng)用流水段以第二個(gè)任務(wù)間隔3拍的間隔進(jìn)入流水線為例說(shuō)明。此時(shí)第二個(gè)任務(wù)間隔3拍進(jìn)入流水線時(shí)，第一個(gè)任務(wù)已經(jīng)在流水線里流動(dòng)了3拍。此時(shí)要是再有任務(wù)進(jìn)入流水線，則新的禁止進(jìn)入的間隔拍數(shù)應(yīng)該在原來(lái)的基礎(chǔ)上減去3拍。（原來(lái)禁止拍數(shù)為6拍、4拍、2拍，當(dāng)前則成為3拍和1拍）。即X3以3拍或者1拍進(jìn)入流水線，必與X1產(chǎn)生爭(zhēng)用功能段的情況。則X3只能以2拍、4拍、5拍、6拍進(jìn)入流水線才不會(huì)與X1爭(zhēng)用流水段。對(duì)沖突向量來(lái)說(shuō)，就是邏輯右移j位（左邊補(bǔ)0），即得到（000101）。這樣就形成了第三個(gè)任務(wù)相對(duì)于第一個(gè)任務(wù)的當(dāng)前沖突向量。X3與X1的當(dāng)前沖突向量為（000101）。但X3要是要與X2不爭(zhēng)用流水段，還要符合X2的初始沖突向量C0=（101010）。所以新的沖突向量是X1當(dāng)前的沖突向量與X2的初始沖突向量進(jìn)行按位“或”，從而得到（101111）。也就是說(shuō)X3只能以間隔5拍進(jìn)入流水線，才不會(huì)與X1和X2爭(zhēng)用流水段。概括下來(lái)，就是：SHR(j)（C0）∨C0

其中:SHR(j)表示邏輯右移j位推廣到更一般的情況假設(shè):Ck：當(dāng)前的沖突向量

j:允許的時(shí)間間隔則新的沖突向量為：

SHR(j)（Ck）∨C0對(duì)于所有允許的時(shí)間間隔都按上述步驟求出其新的沖突向量，并且把新的沖突向量作為當(dāng)前沖突向量，反復(fù)使用上述步驟，直到不再產(chǎn)生新的沖突向量為止。從初始沖突向量C0出發(fā)，反復(fù)應(yīng)用上述步驟，可以求得所有的沖突向量以及產(chǎn)生這些向量所對(duì)應(yīng)的時(shí)間間隔。由此可以畫(huà)出用沖突向量表示的流水線狀態(tài)轉(zhuǎn)移圖。有向?。罕硎緺顟B(tài)轉(zhuǎn)移的方向弧上的數(shù)字：表示引入后續(xù)任務(wù)（從而產(chǎn)生新的沖突向量）所用的時(shí)間間隔（時(shí)鐘周期數(shù)）根據(jù)沖突向量C0畫(huà)出狀態(tài)轉(zhuǎn)換圖（1）C0=（101010）引入后續(xù)任務(wù)可用的時(shí)間間隔為：1、3、5個(gè)時(shí)鐘周期如果采用1，則新的沖突向量為：

（010101）∨（101010）=（111111）如果采用3，則新的沖突向量為：

（000101）∨（101010）=（101111）如果采用5，則新的沖突向量為：

（000001）∨（101010）=（101011）

5.3.1單功能非線性流水線的最優(yōu)調(diào)度（2）對(duì)于新向量（101011），其可用的時(shí)間間隔為3個(gè)和5個(gè)時(shí)鐘周期。用類(lèi)似上面的方法，可以求出其后續(xù)的沖突向量分別為

（101111）和（101011）。（3）對(duì)于其他新向量，也照此處理。（4）在此基礎(chǔ)上，畫(huà)出狀態(tài)轉(zhuǎn)移示意圖。根據(jù)狀態(tài)轉(zhuǎn)換圖寫(xiě)出最優(yōu)調(diào)度方案根據(jù)流水線狀態(tài)圖，由初始狀態(tài)出發(fā)，任何一個(gè)閉合回路即為一種調(diào)度方案。列出所有可能的調(diào)度方案，計(jì)算出每種方案的平均時(shí)間間隔，從中找出其最小者即為最優(yōu)調(diào)度方案。上例中，各種調(diào)度方案及其平均間隔時(shí)間。5.3.1單功能非線性流水線的最優(yōu)調(diào)度各種調(diào)度策略及平均延遲拍數(shù)

簡(jiǎn)單循環(huán)平均啟動(dòng)距離（1，7）4（3，5）4（5，7）6（3，5，7）5（5，3，7）5（5）5（7）7最小啟動(dòng)循環(huán)是具有最小平均最小啟動(dòng)距離的啟動(dòng)循環(huán)。（1，7）（3，5）5.3.1單功能非線性流水線的最優(yōu)調(diào)度最小循環(huán)為（1，7）、（3，5）最小恒定循環(huán)為（5）

時(shí)間流水12345678910111213141516S1X1X2X1X3X2X4X3…S2X1X2X1X2X3X4X3…S3X1X1X2X2X3X3X4…S4X1X2X3X4…最小啟動(dòng)循環(huán)為（3，5）的流水線工作狀態(tài)

時(shí)間流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4最小啟動(dòng)循環(huán)為（1，7）的流水線工作狀態(tài)方案（1，7）和（3，5）是一種不等時(shí)間間隔的調(diào)度方案，與等間隔的調(diào)度方案相比，在控制上要復(fù)雜得多。為了簡(jiǎn)