第4章-流水技術與向量處理

2023/9/21第4章流水技術與向量處理

4.1標量流水工作原理4.2標量流水中的障礙及控制4.3流水線的調度技術4.4先進的流水技術4.5Pentium微處理器中的流水技術4.6向量流水技術2023/9/22本章學習要求掌握標量流水的性能分析及障礙的處理方法掌握非線性流水調度技術掌握向量流水機的結構特征、向量指令并行性分析了解標量流水、超標量流水、超流水及超長指令字計算機的基本工作原理2023/9/23提高指令執(zhí)行速度的主要途徑：

(1)提高處理機的工作主頻

(2)采用更好的算法和設計更好的功能部件

(3)采用指令級并行技術三種指令級并行處理機：

(1)流水線處理機和超流水線(Super-pipelining)處理機

(2)超標量(Superscalar)處理機

(3)超長指令字(VLIW:VeryLongInstructionWord)處理機2023/9/24……4.1標量流水工作原理什么是流水線？考慮設計一個洗衣機的工作流程，假定它有三道工序：洗滌、清洗、甩干。每個環(huán)節(jié)為5分鐘。需要完成的任務為3批，則考慮下述工作方式的工作效率：第一種：串行工作方式，即按照如下方式工作：第1批洗滌第1批清洗第1批甩干第2批洗滌第2批清洗第2批甩干第3批洗滌第3批清洗第3批甩干3批衣服的整個工作時間為3*3*5=45分鐘2023/9/25第二種：重疊工作方式，設計三個部件，可以同時工作，每個部件只做一樣工作，操作方式如下圖：第1批洗滌第1批清洗第1批甩干第2批洗滌第2批清洗第2批甩干第3批洗滌第3批清洗第3批甩干TΔtΔtΔtΔtΔt3批衣服的工作時間為5*5=25分鐘，節(jié)省20分鐘。2023/9/26引出下述關于洗衣機工作的有關性能特點：吞吐率：單位時間內完成的任務數TP=n/T

加速比：串行方式與流水線方式的時間比：上述為45/25=1.8

效率：即洗衣機的利用率，上述洗衣機的效率是9/15=3/5=60%將一條指令的執(zhí)行分為幾個階段，讓幾條指令按重疊或流水方式工作，以提高程序的執(zhí)行速度。這就引出了計算機中的流水線技術。2023/9/27指令的重疊解釋與先行控制計算機系統(tǒng)中廣泛存在著重疊工作方式指令的解釋方式一般只有三種：順序、重疊和流水重疊和流水給指令的執(zhí)行帶來了高的吞吐率和加速比，同時也給系統(tǒng)增加了障礙2023/9/28指令的解釋過程ALULOAD/STOREIF取指取指ID譯碼、讀寄存器堆譯碼、讀寄存器堆EX執(zhí)行計算訪存有效地址MEM---訪存（讀或寫）WB結果寫回寄存器堆將讀出的數據寫入寄存器堆2023/9/29一、指令的重疊解釋方式1、順序執(zhí)行方式一條指令的執(zhí)行過程：取指令->分析->執(zhí)行執(zhí)行n條指令所用的時間為：

如每段時間都為t，則執(zhí)行n條指令所用的時間為：T=3nt主要優(yōu)點：控制簡單，節(jié)省設備。主要缺點：執(zhí)行指令的速度慢，功能部件的利用率很低。取指令k分析k執(zhí)行k取指令k+1分析k+1執(zhí)行k+12023/9/210

2、重疊執(zhí)行方式(最簡單的流水線方式)

如果每個過程的時間相等，則執(zhí)行n條指令的時間為：T=(1+2n)t

主要優(yōu)點：

指令的執(zhí)行時間縮短

功能部件的利用率明顯提高主要缺點：

需要增加一個IBR取指分析執(zhí)行取指分析執(zhí)行取指分析執(zhí)行2023/9/2113、更高重疊度的重疊解釋方式把取第k+1條指令提前到分析第k條指令同時執(zhí)行如果三個過程的時間相等，執(zhí)行n條指令的時間為：T=(2+n)t理想情況下同時有三條指令在執(zhí)行處理機的結構要作比較大的改變，必須采用先行控制方式取指k+2分析k+2執(zhí)行k+2取指k+1分析k+1執(zhí)行k+1取指k分析k執(zhí)行k2023/9/2121．訪存沖突分析與取指均要訪問主存解決：

1）采用兩個獨立編制的存貯器數據/指令

但增加了復雜性

2）采用多體交叉存貯器

3）指令緩沖寄存器2．功能部件的沖突

解決：設置獨立的分析部件和執(zhí)行部件重疊方式對計算機組成的要求2023/9/2133．同步分析與執(zhí)行所需的時間不同，要求的是一次重疊一次重疊：任何時間都是“分析K+1”與“執(zhí)行K”的重疊=>相鄰兩條指令的重疊分析K執(zhí)行K分析K+1執(zhí)行K+1T=(n+1)t2023/9/2144．轉移

無條件轉移/條件轉移

當轉移成功時，重疊預取無效，變?yōu)轫樞驁?zhí)行應盡可能不使用或少使用條件轉移指令5．相關

鄰近指令之間出現某種關聯，為避免出錯而不能同時執(zhí)行的現象。局部性相關、全局性相關2023/9/2152023/9/216先行控制技術基本思想：使分析和執(zhí)行部件分別連續(xù)不斷地運行，使部件空閑狀態(tài)減至最低。(a)重疊方式分析k+1分析k執(zhí)行k執(zhí)行k+1分析k+2執(zhí)行k+2分析部件空閑執(zhí)行部件空閑分析k+1分析k執(zhí)行k分析k+2(b)先行控制執(zhí)行k+1執(zhí)行k+22023/9/217關鍵：緩沖技術＋預處理技術緩沖技術：在工作速度不固定的兩個功能部件之間設置緩沖棧，用以平滑它們的工作預處理技術：把進入運算器的指令都預處理成R-R型指令，與緩沖技術相結合，為進入運算器的指令準備好所需的全部操作數先行控制方式使運算器可專注于運算，從而可大幅度提高程序的執(zhí)行速度硬件要求：增設指令緩沖棧，消除取指過程；增設數據緩沖棧，保證不同指令的讀、寫操作并行；增設先行操作棧，保證執(zhí)行部件能連續(xù)執(zhí)行。2023/9/218工作原理主存存控指令分析器

先行指令棧先行讀數棧后行寫數棧執(zhí)行部件先行操作棧數據緩沖棧

棧的深度要求：D指緩≥D操作≥D讀?！軩寫棧2023/9/219二、標量流水工作原理基本思想：流水是重疊的進一步延伸，使指令解釋過程進一步細化，提高各部件的利用率，以提高指令執(zhí)行速度。流水線的表示方法：連接圖、時空圖、預約表2023/9/2201、簡單流水線的連接圖表示流水線的每一個階段稱為流水段、流水線階段、流水功能段、功能段、流水級、流水節(jié)拍等。一個流水階段與另一個流水階段相連形成流水線。有些復雜指令，在執(zhí)行階段也采用流水線方式工作，稱為操作流水線。取指訪存執(zhí)行譯碼寫回IFIDEXMEMWBS1S2S3S4S5輸入輸出2023/9/221

一種指令流水線一般4至12個流水段，等于及大于8個流水段的稱為超流水線處理機2、流水線的時空圖采用“時空圖”表示流水線的工作過程。一條簡單流水線的時空圖：取指形成操

作數地址譯碼取操作數執(zhí)行保存結果2023/9/222一個浮點加法器流水線的時空圖(由求階差、對階、尾數加和規(guī)格化4個流水段組成)：ED1時間空間0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：規(guī)格化MA：尾數加EA：對階ED：求階差EDEAMANLmt2023/9/2233、流水線的預約表

時間流水段1234567S1XXXS2XXS3XXS4X2023/9/224三、流水線工作方式取指訪存執(zhí)行譯碼寫回IFIDEXMEMWBS1S2S3S4S5輸入輸出指令的流水處理

流水線的基本結構中主要包括三大部分：鎖存器、時鐘、功能段。流水線中每個段都是由一些執(zhí)行算術和邏輯功能的組合邏輯線路組成的，它們可以互相獨立地對流過的信息進行某種操作，相鄰兩站由高速鎖存器（latch）隔開，信息在各段間的流動靠同時送到各站的時鐘信號來控制。1、流水線的結構2023/9/225S1S2Sm輸入

輸出流水線的基本結構.….…..時鐘2023/9/226121321nn-1...43215432...543......54.........5nn-1......n-1.........nn-1n1234△t0△t0

△t0△t0T0=m△t0n△t0T(m-1)△t0(n-1)△t0填入正常排空流水時空圖空間時間建立時間、正常流動時間、排空時間。2、流水線工作的三個時間2023/9/2273、流水線的分級、分類分級：（處理的級別分類）部件級(操作流水線)：將復雜的算邏運算組成流水工作方式；指令級：把一條指令解釋過程分成多個子過程；處理機級：每個處理機完成某一專門任務，各個處理機所得到的結果需存放在與下一個處理機所共享的存儲器中2023/9/228其他分類：功能：單功能流水線（如CRAY-1）、多功能流水線（如TI-ASC）工作方式：靜態(tài)流水線、動態(tài)流水線連接方式：線性、非線性處理數據：標量流水、向量流水1234出入非線性流水線2023/9/2291)ASC算術運算流水線（多功能）輸入減階對階移位相加規(guī)格化相乘累加輸出123456784、流水線舉例輸入減階對階移位相加規(guī)格化輸出123458加輸入相乘累加輸出1678乘2023/9/230...1234......n-1n...1234......n-1n...1234......n-1n...1234......n-1n12345867...1234...n-1n...1234......n-1n時間空間(段號)加法一二三四二三一二一一乘法......靜態(tài)多功能流水線時-空圖靜態(tài)流水線：只有當進入的是一串相同運算的指令時，流水的效能才得以發(fā)揮，才能使各個功能段并行地對多條指令的數據進行流水處理。2023/9/231區(qū)別：如果從軟硬功能分配的觀點上來看，靜態(tài)流水線其實是把功能負擔較多地加到軟件上，以簡化硬件；動態(tài)流水線則是把功能負擔較多地加在硬件上，以提高流水的效能。...12345......n-1n...12345......n-1n...12345......n-1n...12345......n-1n12345867...12345......n-1n...12345......n-1n時間加法乘法一二三四五六一二三四五六七一二三四五一二三四動態(tài)多功能流水線時-空圖m2023/9/232四、標量流水線性能分析衡量流水線處理機的性能主要是吞吐率、加速比和效率。

1．吞吐率：單位時間內能處理的指令條數或能輸出的數據量。吞吐率越高，計算機系統(tǒng)的處理能力就越強。就流水線而言，吞吐率就是單位時間內能流出的任務數或能流出的結果數。最大吞吐率：流水線達到穩(wěn)定狀態(tài)后可獲得的吞吐率。（1）Tpmax=1/

t（2）TPmax=1/max{

t1，

t2，

t3，

t4}“瓶頸”子過程：1234

t

t3

t

t2023/9/233子過程3為瓶頸段的時空圖最大吞吐率TPmax=1/3

tmTS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412341234輸出2023/9/2341312323342143a3b3c333瓶頸段細分重復設置瓶頸流水段解決瓶頸有兩種方法A：B：2023/9/235T重復設置瓶頸流水段后的工作時空圖mS1S2S3aS3cS3bS4123546789101112123546789101112147102581136912123546789101112t1t12t172023/9/236實際吞吐率（1）完成n條指令的解釋共需時間

可以看出不僅實際的吞吐率總是小于最大的吞吐率，而且只有當n>>m時，實際的吞吐率才能接近于理想的最大吞吐率。(2)各功能段時間不相等2023/9/2372.效率：設備的利用率，直接反映了處理機結構有效程度。流水線有建立時間、排空時間，不總是滿負載工作。各段時間相等：各段時間不等：2023/9/238各段時間相等:各段時間不等:加速比：M段流水線的速度與等效的非流水線的速度之比。2023/9/239K=6K=10任務

個數加速比10246811248163264128因為因此：E=TP·Δt，S=k·E流水線的吞吐率、加速比與效率的關系2023/9/240例1.

有一四段線性流水線,每功能段延時時間分別是：△t1=△t3=△t4=△t,△t2=3△t?，F在這個流水線上分別執(zhí)行4個任務和40個任務。求實際吞吐率、效率和加速比。解法一：時空圖分析法時間12343111223234123123123444443△t3△t空間152023/9/241Tp=4/(15△t)E=24△t

/(4*15△t)=40%Sp=4*6△t

/15△t=1.6完成4個任務時：完成40個任務時，如何畫時空圖呢？？方法二，公式分析法。當流水線中各功能段的執(zhí)行時間不相等時，有2023/9/2422023/9/243例2、以浮點加法運算為例（四段）各段時間相等，求Z=A+B+C+D+E+F+G+H的TP、E、Sp。時間空間Z=A+B+C+D+E+F+G+H1234567TP=7/15△tE=7*4/(15*4)=7/15Sp=4*7/15=28/15=1.871111222233334444555566667777152023/9/244例3.ASC計算機功能算術運算流水線各段時間相等，6次浮點加、5次定點乘的吞吐率、效率和加速比。1,2,3,4,5,8組成加法流水1,6,7,8組成乘法流水12345678對階減階輸出相加規(guī)格化相乘累加輸入ASC計算機的流水線2023/9/245分析：T加=6+(6-1)*1=11T乘=4+(5-1)*1=8TP=11/(11+8)△t=11/19△tE=(6*6+5*4)△t/(19*8△t)=11.54%Sp=56△t/19△t=2.9412345612345612345612345612345867123456123456時間浮加定點乘一二三四五一二三四五一二三四五一二三四五2023/9/2464.2標量流水中的障礙及控制保持流水線性能條件：不能停頓或斷流。影響流水線性能因素：相關和功能切換。相關類型：全局相關：轉移指令引起的相關結果：流水線斷流，流水線中后續(xù)指令全部作廢。局部相關：資源或結構相關；指令相關；數據相關。結果：流水線停頓，流水線中后續(xù)指令有效。2023/9/247一、資源相關資源相關：功能部件、主存資源當有多條指令進入流水線后在同一機器周期內爭用同一功能部件所引起的相關（沖突）當有多條指令進入流水線后在同一機器周期內同時訪問主存資源2023/9/248例1：兩條指令同時要用一個加法器ALULOAD/STOREIF取指取指ID譯碼、讀寄存器堆譯碼、讀寄存器堆EX執(zhí)行計算訪存有效地址MEM-訪存（讀或寫）WB結果寫回寄存器堆將讀出的數據寫入寄存器堆指令流水段不同類型指令中各流水段進行的操作2023/9/249兩條指令同時訪存造成資源相關MEMEXIDIF指令i+4WBMEMEXIDIF指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321

時鐘指令沖突取指譯碼執(zhí)行訪存寫回例2：2023/9/250EXIDIF指令i+4MEMEXIDIF停頓指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321

時鐘指令9WBMEM使i+3指令停頓一拍進入流水線，以解決訪存相關；或重復設置一個存儲器；采用先行控制技術解決方法：2023/9/251二、指令相關后續(xù)指令的內容取決于當前指令執(zhí)行的結果，即指令允許修改引起的相關解決相關：不準修改指令、變指令相關為數據相關EXR1D2B2X2IBM370中的“執(zhí)行”指令2023/9/252三、數據相關由于流水線中的各條指令間的重疊解釋，使得原來對操作數的訪問順序發(fā)生了變化，從而導致了數據之間的相關。這種相關有三類：先寫后讀（改用相關）

、先讀后寫（用改相關）、寫寫相關（改改相關）。設有i和j兩條指令，i指令在前，j指令在后，則三種不同類型的數據相關的含義為：2023/9/253RAW讀寫(先寫后讀)---指令j試圖在指令i寫入寄存器前就讀出該寄存器內容，這樣，指令j就會錯誤地讀出該寄存器舊的內容。

i:R1+R2->R3

j:R3*R4->R5WAR寫讀(先讀后寫)---指令j試圖在指令i讀出寄存器之前就寫入該寄存器，這樣，指令i就錯誤地讀得該寄存器新的內容。

i:R3*R4->R5j:R1+R2->R3WAW寫寫(先寫后寫)---指令j試圖在指令i寫寄存器之前就寫入該寄存器，這樣，兩次寫的先后次序被顛倒，就會錯誤地使由指令i寫入的值成為該寄存器內容。

i:R1*R2->R3

j:R4+R5->R32023/9/254解決數據相關的辦法用軟件和硬件技術：時間推后法旁路技術或相關專用通路技術例：

n:loadAIFIDEXWRn+1:loadBIFIDEXWRn+2:addA,B

IF

ID

氣泡EXWRn+3:storeCIFID氣泡EXWRn+4:jumpKIFIDEXWRn+5:loadE停頓停頓停頓。。

n+6………停頓。。

K:IFIDEX例中有資源相關、有控制轉移相關，這將影響流水線的性能。2023/9/255IF

ID

EX

MEM

WB

IF

ID

EX

WB

IF

ID

EX

WB

IF

ID

EX

WB

IF

ID

EX

WB

ADDR1,R2,R3SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11定向傳遞R1值數據相關和定向傳遞指令寫R1完成MEM

MEM

MEM

MEM

2023/9/256ALU運算結果寫RF

RF讀RFALU操作數寄存器專用通路（旁路）旁路RFALUBufferMultMult2023/9/257四、全局性相關由轉移指令（條件/無條件）引起的相關轉移指令在程序中所占比例約為20-25%，不可忽視解決這種相關的方法：猜測法、加快和提前形成條件碼、加快短循環(huán)程序的處理、采用延遲轉移技術2023/9/2581、猜測法：選取發(fā)生概率較高的分支為猜測方向，若猜對，繼續(xù)執(zhí)行；否則,作廢猜測方向的執(zhí)行，返回實際轉移處。（1）如何提高猜測命中率靜態(tài)猜測法：猜測不成功方向。由程序員和編譯程序把發(fā)生概率高的分支安排在猜測方向。動態(tài)猜測法：根據轉移歷史猜測。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功2023/9/259轉移目標緩沖器(BTB)

利用BTB(BranchTargetBuffer)硬件，動態(tài)地預測轉移方向轉移指令地址轉移目標地址狀態(tài)欲取指令的PC查找預測PC值=按正常順序執(zhí)行NY2023/9/260轉移預測原理：用2位二進制數記錄實際轉移狀態(tài)(歷史位)，高位為1時預測轉移發(fā)生，高位為0時預測轉移不發(fā)生。注意：初始狀態(tài)、狀態(tài)修改、猜測方向表示預測發(fā)生11預測發(fā)生10預測不發(fā)生01預測不發(fā)生00轉移1不轉移0不轉移0不轉移0轉移1轉移1轉移1不轉移02023/9/261（2）猜測的后續(xù)處理分支現場的保護及恢復：

猜測執(zhí)行只完成譯碼、取操作數或執(zhí)行但不寫結果；采用后援寄存器保存可能被破壞的狀態(tài)。預防猜不中時的加速處理：

預取猜測方向的另一方向的前幾條指令，放到緩沖器中，加速猜不中時回頭速度。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功2023/9/2622、加快和提前形成條件碼單條指令的條件碼并不一定要等執(zhí)行完成得到運算結果后才能形成循環(huán)程序判斷的提前形成3、優(yōu)化延遲轉移技術

a.將轉移指令前的那條指令調度到延遲槽中；

b.將轉移目標處的那條指令調度到延遲槽中；

c.將轉移不發(fā)生時該執(zhí)行的那條指令調度到延遲槽中。4、加快短循環(huán)處理2023/9/263五、流水線中的中斷處理流水機器處理中斷的關鍵不在于如何縮短斷流時間，而是如何處理好斷點現場及中斷后的恢復問題不精確斷點法：不論第i條指令在流水線的哪一段發(fā)出中斷申請，都不再允許那時還未進入流水線的后續(xù)指令再進入。斷點就是最后進入流水線的那條指令2023/9/264S1S8S7S6S5S4S3S2輸入輸出i+5ii-1i+1i+2i+3i+4i-2PC：不精確斷點申請中斷精確斷點特點：硬件開銷小，控制簡單，適用于常規(guī)的I/O操作。2023/9/265

精確斷點法：不論第i條指令是在流水線中哪一段發(fā)出的中斷申請，給中斷處理程序的現場全都是對應第i條的。適用于程序性錯誤和機器故障等產生的中斷精確斷點法中對原有現場的恢復，要增加后援寄存器，以保留各功能段狀態(tài)i:FADDR1,R2;(R1)+(R2)→R1i+1:FMULR3,R1;(R3)*(R1)→R3S6：加法結果溢出精確斷點法有利于程序調試2023/9/266例4

在一條單流水線處理機上執(zhí)行下面的程序。每條指令都要經過“取指”,“譯碼”,“執(zhí)行”和“寫結果”4個流水段。每個流水段的延遲時間都是5ns。在“執(zhí)行”流水段,LS部件完成LOAD或STORE操作,其它操作都在ALU部件中完成,兩個操作部件的輸出端有直接數據通路與任一操作部件的輸入端相連,ALU部件產生的條件碼也能夠直接送入控制器。2023/9/2671:SUBR0,R0;R0←02:LOADR1,#8;向量長度83:LOOP:LOADR2,A;R2←A向量的一個元素

4:MULR2,R1;R2←(R2)*(R1)5:ADDR0,R2;R0←(R0)+(R2)6:DJNER1,LOOP;R1←(R1)-1若(R1)≠0則轉

7:STORER0,S;保存結果(1)采用靜態(tài)分支預測技術,每次都預測轉移不成功。畫出指令流水線的時空圖。計算流水線的吞吐率和加速比。并分別計算出譯碼部件和ALU部件的使用效率。(2)采用靜態(tài)分支預測技術,每次都預測轉移成功。計算指令流水線的吞吐率和加速比。并分別計算出譯碼部件和ALU部件的使用效率。2023/9/26852112112322333454445556666取指寫回ALULS譯碼3333444455556666333344445555666633334444555566667777............重復8次m(1)解:每次預測轉移不成功,流水線時空圖如下:2023/9/269112112322333454445556666取指寫回ALULS譯碼333344445555666633334444555566667777......重復8次m(2)解:每次預測轉移成功,流水線時空圖如下:2023/9/2704.3流水線的調度技術靜態(tài)調度：借助軟件對指令執(zhí)行順序進行調度，以減少由于流水線中存在相關沖突而引起流水線的停頓時間。動態(tài)調度：通過硬件重新安排指令的執(zhí)行順序以減少流水的停頓。有集中式和分布式兩種。2023/9/271一、靜態(tài)調度技術靜態(tài)調度：借助軟件對指令執(zhí)行順序進行調度，以減少由于流水線中存在相關沖突而引起流水線的停頓時間。非線性流水線中存在著前（反）饋回路，必然會引起功能段的沖突而發(fā)生流水線停頓。調度方法會減少停頓時間。調度方案是基于二維預約表和狀態(tài)圖來進行分析2023/9/272非線性流水線的連接圖

時間流水段1234567S1XXXS2XXS3XXS4X非線性流水線的預約表S1S2S3S4輸出輸入反饋線2023/9/273某流水線結構如下：非線性流水線調度舉例

S1S2S3S4S5入①②③④⑥⑤⑦⑧⑦⑨出⑧

流水線調度方案如下：2023/9/274（1）形成預約表指令總拍數為n，流水線有k個段，則形成n×k的預約表，段的使用情況用“×”表示。預約表如下：××5××4×3××××2××198765438271tS2023/9/275（2）由預約表形成禁止表FF={各段中沖突間隔拍數}

---功能段1的禁止間隔拍數為8；

---功能段2的禁止間隔拍數為5和6；

---功能段3的無禁止間隔拍數；

---功能段4的禁止間隔拍數為1；

---功能段5的禁止間隔拍數為1。F={1，5，6，8}（3）由禁止表F形成初始沖突向量C0C0=（10110001），ci=1沖突，0不沖突。2023/9/276（4）由初始沖突向量C0形成狀態(tài)轉換圖a.

取C0分別間隔2、3、4、7拍，且將C0分別邏輯右移2、3、4、7位，高位補0后再與C0按位“或”，形成新的沖突向量C1、C2和C3；10110001101101111011110110111011初始狀態(tài)3427C0C1C2C32023/9/277b.再分別取C1間隔2、7拍；取C2間隔4、7拍；取C3間隔3、7拍。方法同上，直至全部完成。

注意：向量Ci右移后，總是與原始向量C0作邏輯加。1011000110110111101111011011101110111111初始狀態(tài)34422777C0C1C2C3C4772023/9/278（5）根據狀態(tài)圖寫出調度方案

每一個閉合回路就是一個調度方案（策略）1011000110110111101111011011101110111111初始狀態(tài)34422777C0C1C2C3C47732023/9/279本例中調度方案如下：調度策略平均間隔拍數調度策略平均間隔拍數(2,7)4.50(4,3)3.50(2,2,7)3.67(4,3,7)4.67(3,4)3.50(4,7)5.00(3,7)5.00(7)7.00(3,4,7)4.67

平均延時最小的調度方案為最佳調度方案，本例為（3，4）和（4，3）。

對非C0開始的調度方案由流水線控制器完成控制的過渡。2023/9/280調度方案的驗證原理：二維預約表方法：給定任務數，使用每一種可能的調度方案進行調度驗證：調度過程中有無功能段的沖突？2023/9/281123456789101112131415S1√√√√√S2√√√√√√√√√S3√√√S4√√√√√√S5√√√√√√例如，按(3,4)調度方案，連續(xù)輸入3個任務的調度過程如下：2023/9/282按（4，3）調度方案連續(xù)輸入6個任務的時空圖S1S2S3S4S5mt2023/9/283性能分析設共輸入8個任務，按最佳調度方案（平均時延最小3.5拍）（3，4）進行調度，計算流水調度的最大和實際吞吐率2023/9/284例5設有一4段流水線處理機如下圖所示。此流水線的總值時間為6個時鐘周期,所有相繼段必須在每個時鐘周期之后才能使用。(1)列出這一流水線的4行6列的預約表;(2)列出禁止表和畫出狀態(tài)圖;(3)求出平均延遲最小的調度方案和最大吞吐率。S1S2S3S4輸出輸入2023/9/285功能段123456S1√√S2√√S3√S4√解法一：4行6列的預約表(一)禁止表的原始沖突向量為：F={4}，C=(1000)2023/9/28610001100111011111010100110111101111212333223解法一的狀態(tài)轉移圖平均延遲最小的調度方案是：(1,2,3,2)。最小平均延遲是：2▲t。最大吞吐率是：TPmax=1/2▲t。2023/9/287功能段123456S1√√S2√√√S3√√S4√解法二：4行6列的預約表(二)禁止表的原始沖突向量為：F={2,4}，C=(1010)2023/9/28810101111101113355解法二的狀態(tài)轉移圖平均延遲最小的調度方案是：(3)。最小平均延遲是：3▲t。最大吞吐率是：TPmax=1/3▲t。2023/9/289二、動態(tài)調度技術動態(tài)調度：通過硬件重新安排指令的執(zhí)行順序以減少流水的停頓。有集中式和分布式優(yōu)點：（1）能處理某些在編譯時無法知道的相關情況（2）能簡化編譯程序設計（3）使代碼有可移植性缺點：相應的硬件較為復雜。2023/9/2901、集中式動態(tài)調度靜態(tài)調度中的指令是按序(In-order)執(zhí)行，如果一條指令在流水線中發(fā)生停頓，后續(xù)指令就不再前進了動態(tài)調度可使指令按無序(Out-order)方式工作集中式動態(tài)調度：依靠硬件在程序運行過程中對可能出現的相關情況加以檢測，從而保證流水線中的各個功能部件能最大限度地重疊工作2023/9/291EX

MEMWB

集中式動態(tài)調度IFID整數部分浮點加浮點乘浮點除RF記錄控制器指令控制/狀態(tài)控制/狀態(tài)狀態(tài)記錄控制器（記分牌）記錄與控制在流水線的EX段開始。2023/9/292檢測功能：功能部件（資源）沖突；源、目的REG引起的RAW、WAR、WAW相關。控制功能：有沖突或相關的指令推后進入流水線的執(zhí)行部件，否則正常指令進入流水線的執(zhí)行部件；記錄功能部件、REG、指令的狀態(tài)；根據記錄的狀態(tài)，控制后續(xù)指令的進入。2023/9/2932、分布式動態(tài)調度

此方法是由Tomasulo于1967年提出來的，已在IBM360/91機中采用。IBM360/91的浮點運算器主要部件：（1）

運算部件：一個加法部件和一個乘除部件。（2）保存站：加法部件中有A1~A3三個保存站，乘除部件有M1和M2兩個保存站，用來保存當前參加運算的數據。2023/9/294（3）

指令操作緩沖棧：存放經分析后由指令部件送來的指令，譯碼后，產生相應的控制信號送到各個部件。（4）浮點操作數寄存器（FLB）：存放由主存預取來的操作數。（5）浮點寄存器（FLR）：存放操作數的寄存器。（6）

存儲數據緩沖站（SDB）：存放將寫入存儲器的結果數據，也有站號。（7）

公共數據總線（CDB）：以上各部件間的連接總線。2023/9/295浮點操作數緩沖器(FLB)控浮點操作棧(FLOS)忙制位站號源1控制站號源2站號源1站號源2控制控制號站存數緩沖器(SDB)加法器乘/除法器譯碼器站號浮點寄存器(FLR)M1M2A1A2A3101010111100FLB總線FLR總線10001001CDB公共數據總線指令處理部件存儲器總線654321站號：

01100001F76543F21F0保存站IBM360/91的浮點運算部件結構框圖2023/9/296S1：(FLB1)→F0S2：(F0)*(FLB2)→F0S3：(F0)→AS4：(FLB3)→F0S5：(F0)+(FLB4)→F0;F0站號置為0001;F0置忙位為1，M1源1為0001，源2為0010，F0站號為1000;C1站號置1000;F0站號置為0011;F0置忙位為1，A1源1為0011，源2為0100，F0站號為1010調度方法特點：通過FLR的“忙”位，檢測RAW相關；通過修改站號（重命名），消除WAR、WAW相關；通過設置保存站，減少資源相關沖突；借助CDB作相關專用通路。2023/9/2974.4先進的流水技術流水中指令級并行性的進一步開發(fā)粗粒度并行性：在多處理機上分別運行多個進程，由多臺處理機合作完成一個程序；細粒度并行性：指在一個進程中進行操作一級或指令一級的并行處理。RISC機進一步開發(fā)細粒度并行性2023/9/298一、超標量流水處理技術每個時鐘周期平均執(zhí)行指令的條數大于或等于2超標量處理機典型結構：

多條指令流水線、多個功能部件先進的超標量處理機有：定點處理部件CPU，浮點處理部件FPU,圖形加速部件GPU，大量的通用寄存器，兩個一級高速Cache超標量處理機的指令級并行度ILP大于12023/9/299超標量流水線處理機的一般結構IFIDFA1FA2FA3MD1MD2MD3ALLS浮點加法部件乘除法部件定點ALU部件取數存數部件WRIFIDWR2023/9/2100整數

部件整數

部件位

操作浮點加乘法

部件除法

部件圖形

部件圖形

部件內部總線讀數存

數部件通用寄

存器堆擴展寄

存器堆目標

指令指令分配

轉移部件數據Cache(8KB)指令Cache(8KB)系統(tǒng)總線32位地址總線32位數據總線超標量處理機MC88110的結構2023/9/2101IFIDFA1FA2FA3MD1MD2MD3ALLS浮點加法部件乘除法部件定點ALU部件取數存數部件WRIFIDWRIFID先行指

令窗口注：先行指令窗口除了能夠做數據相關性分析和功能部件沖突的檢測之外，還至少有一套取指令部件和一套指令譯碼部件2023/9/2102IF時鐘

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR超標量流水處理機的時空圖2023/9/2103超標量流水線的調度按序發(fā)射：當指令按策劃功能序的次序發(fā)射時，稱之為按序發(fā)射（in-orderissue）無序發(fā)射：為改善流水線性能，可以將有相關的指令推后發(fā)射，而將后面的無相關性的指令提前發(fā)射，即不按程序原有次序發(fā)射指令，稱之為無序發(fā)射（out-of-order）按序完成：完成順序與發(fā)射順序一致無序完成：完成順序與發(fā)射順序不一致2023/9/2104按序發(fā)射按序完成—靜態(tài)調度策略；（Pentium)按序發(fā)射無序完成—動態(tài)調度策略；（PentiumII/III）無序發(fā)射無序完成—動態(tài)調度策略。無論那種調度策略，都要保證程序運行的最終結果是正確的，發(fā)射策略由譯碼控制器完成，完成策略由執(zhí)行控制器完成。常用的調度方法2023/9/2105IF1ID1L/SWR1IF2ID2部件FA1WR2FA3FA2順序(RAW)順序(WAW)順序順序(RAW)MD1MD2MD3WR1IF2ID2FA1FA2FA3ID1IF1WR2ID1ALIF1WR1ID2MD1MD2MD3I1WR2IF2I2I3I4I5I6指令時鐘周期12345678910流水線2流水線1I1：LOADR1，A；主存單元A→R1I2：FADDR2，R1

；(R1)+(R2)→R2I3：FMULR3，R4

；(R3)×(R4)→R3I4：FADDR4，R5

；(R4)+(R5)→R4I5：DECR6

；(R6)-1→R6I6：FMULR6，R7

；(R6)×(R7)→R6按序發(fā)射按序完成之調度過程2023/9/2106IF1ID1L/SWR1IF2ID2部件FA1WR2FA3FA2(RAW)(RAW)MD1MD2MD3WR1IF2ID2FA1FA2FA3ID1IF1WR2ID1ALIF1WR1ID2MD1MD2MD3I1WR2IF2I2I3I4I5I6指令時鐘周期123456789流水線2流水線1I1：LOADR1，A；主存單元A→R1I2：FADDR2，R1

；(R1)+(R2)→R2I3：FMULR3，R4

；(R3)×(R4)→R3I4：FADDR4，R5

；(R4)+(R5)→R4I5：DECR6

；(R6)-1→R6I6：FMULR6，R7

；(R6)×(R7)→R6按序發(fā)射無序完成之調度過程2023/9/2107IF1ID1L/SWR1IF2ID2FA1WR2FA3FA2MD1MD2MD3WR1IF1ID1FA2FA3FA1ID3IF3WR2ID2ALIF2WR1ID2MD2MD3MD1I1WR2IF2I3I4I2I5I6指令時鐘周期12345678流水線2流水線1I1：LOADR1，A；主存單元A→R1I2：FADDR2，R1

；(R1)+(R2)→R2I3：FMULR3，R4

；(R3)×(R4)→R3I4：FADDR4，R5

；(R4)+(R5)→R4I5：DECR6

；(R6)-1→R6I6：FMULR6，R7

；(R6)×(R7)→R6無序發(fā)射無序完成之調度過程先行控制2023/9/2108超標量流水線的資源沖突在先進的超標量流水機中，有多個操作（執(zhí)行）部件，如：ALU、FADD、FMUL、GPU、LSU等操作部件必須采用流水結構，可減少資源沖突2023/9/2109I1：FADDR0，R1；(R0)+(R1)→R0

I2：FMULR2，R3；(R2)×(R3)→R2I3：FADDR4，R5；(R4)+(R5)→R4I4：FMULR6，R7；(R6)×(R7)→R6IF1IF2ID1ID2FADDIF1ID1IF2ID2WR1FMULWR2FADDFMULWR1WR2I1I2I3I41234567891011雙流水線超標量處理機（操作部件非流水結構）2023/9/2110I1：FADDR0，R1；(R0)+(R1)→R0

I2：FMULR2，R3；(R2)×(R3)→R2I3：FADDR4，R5；(R4)+(R5)→R4I4：FMULR6，R7；(R6)×(R7)→R6IF1IF2ID1ID2FA1IF1ID1IF2ID2WR1FM1WR2WR1I1I2I3I412345678t雙流水線超標量處理機（操作部件流水結構）FA2FA3FM2FM3FM4FA1FA2FA3FM1WR2FM2FM3FM42023/9/2111二、超流水線處理機兩種定義：

一個周期內能夠分時發(fā)射多條指令的處理機稱為超流水線處理機。

指令流水線有8個或更多功能段的流水線處理機稱為超流水線處理機。提高處理機性能的不同方法：

超標量處理機是通過增加硬件資源為代價來換取處理機性能的。超流水線處理機則通過各硬件部件充分重疊工作來提高處理機性能。兩種不同并行性：

超標量處理機采用的是空間并行性

超流水線處理機采用的是時間并行性2023/9/2112指令執(zhí)行時序每隔1/n個時鐘周期發(fā)射一條指令，流水線周期為1/n個時鐘周期在超標量處理機中，流水線的有些功能段還可以進一步細分，例如：ID功能段可以再細分為譯碼、讀第一操作數和讀第二操作數三個流水段。也有些功能段不能再細分，如WR功能段一般不再細分。因此有超流水線的另外一種定義：有8個或8個以上流水段的處理機稱為超流水線處理機2023/9/2113IF時鐘

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR每個時鐘周期分時發(fā)送3條指令的超流水線2023/9/2114MIPSR4000處理機的流水線操作指令CacheIF：取第一條指令 IS：取第二條指令

RF：讀寄存器堆，指令譯碼

EX：執(zhí)行指令 DF：取第一個數據

DS：取第二個數據 TC：數據標志校驗；WB：寫回結果指令

譯碼讀寄

存器堆ALU數據Cache標志檢驗寄存器堆IFISRFEXDFDSWBTC2023/9/2115IF流水線周期當前CPU周期ISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWB主時

鐘

周期MIPSR4000正常指令流水線工作時序2023/9/2116三、超標量超流水線處理機把超標量與超流水線技術結合在一起，就成為超標量超流水線處理機

指令執(zhí)行時序

超標量超流水線處理機在一個時鐘周期內分時發(fā)射指令n次，每次同時發(fā)射指令m條，每個時鐘周期總共發(fā)射指令m×n條。2023/9/2117IF時鐘周期指令I1I2I3IDEXWR12345I4I5I6I7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRI10I11I12每時鐘周期發(fā)射3次,每次3條指令2023/9/2118不同結構計算機的性能分析標量處理機的并行度(1,1)超標量處理機的并行度(m,1)超流水處理機的并行度(1,n)超標量超流水處理機的并行度(m,n)2023/9/2119標量流水處理機上執(zhí)行N條指令的時間：超標量流水處理機上執(zhí)行N條指令的時間：2023/9/2120超流水處理機上執(zhí)行N條指令的時間：超標量超流水處理機上執(zhí)行N條指令的時間：2023/9/2121四、超長指令字(VLIW)計算機VLIW是以一條長指令實現多個操作的并行執(zhí)行，減少存儲器訪問。主要特點：（1）單一的控制流。只有一個控制器，每個周期啟動一條指令。（2）超長指令字被分成多個控制字段，每個字段直接獨立地控制每個功能部件。（3）在編譯階段完成超長指令中多個可并行執(zhí)行操作的調度。2023/9/2122

超長指令字計算機舉例如完成以下運算：C=A+B、K=I+J、

L=M-K、Q=C×K需以下13條指令完成：（需花14個T

）LOADA、LOADB、C=A+B、STOREC、LOADI、LOADJ、K=I+J、STOREK、LOADM、L=M-K、STOREL、Q=C×K、STOREQ2023/9/2123主存RF(寄存器堆)LD/ST2FADDFMULLD/ST1LD/ST1LD/ST2FADDFMUL存/取1存/取2浮點加浮點乘操作并行度≤4LOADALOADBLOADILOADJC=A+BLOADMSTORECK=I+JSTOREKL=M-KQ=C×KSTORELSTOREQ用VLIW則只需6個T2023/9/2124例6

在下列不同結構的處理機上運行8×8的矩陣乘法C=A×B，計算所需要的最短時間。只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數、數據傳送和程序控制等指令的執(zhí)行時間。加法部件和乘法部件的延遲時間都是3個時鐘周期，另外，加法指令和乘法指令還要經過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為“0”。各操作部件的輸出端有直接數據通路連接到有關操作部件的輸入端，在操作部件的輸出端設置有足夠容量的緩沖寄存器。2023/9/2125（1）處理機內只有一個通用操作部件，采用順序方式執(zhí)行指令。解：需要完成的乘法次數為8×8×8=512次需要完成的加法次數為8×8×7=448次執(zhí)行完成總時間為：2023/9/2126（2）單流水線標量處理機，有一條兩個功能的靜態(tài)流水線，流水線每個功能段的延遲時間均為一個時鐘周期，加法操作和乘法操作各經過3個功能段。解：IFIDAD1AD2AD3MU1MU3MU22023/9/2127（3）單流水線標量處理機，處理機內有兩條獨立的操作流水線，流水線每個功能段的延遲時間均為一個時鐘周期。解：IFIDAD1AD2AD3MU1MU3MU22023/9/2128（4）超標量處理機，每個時鐘周期同時發(fā)送一條乘法指令和一條加法指令，處理要內有兩條獨立的操作流水線，流水線的每個功能段的延遲時間均為一個時鐘周期。（不考慮數據之間的相關性，下同。）解：2023/9/2129（5）超流水處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件的延遲時間都為6個流水級，每個時鐘周期能夠分時發(fā)射兩條指令，即每個流水級能夠發(fā)射一條指令。IFIDAD1AD2AD3MU1MU3MU2解：123456789102023/9/2130（6）超標量超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件延遲時間都為6個流水級，每個流水級能夠同時發(fā)射一條乘法指令和一條加法指令。解：2023/9/21314.6向量流水技術向量流水的基本原理CRAY-1型向量處理機增強向量處理性能的方法2023/9/21324.6.1向量流水的基本原理提高流水性能方法：增加流水線段數，以減少Δt；每個時鐘同時啟動多條指令；減少相關，減少功能變換次數，增加處理指令條數。向量操作特點1.向量元素間操作相互獨立，且為相同操作。2.相當于標量循環(huán)，對指令帶寬的訪問要求不高。3.可采用多體交叉存儲器，減少訪存延遲。向量操作很適合于流水處理或并行處理。2023/9/2133例如：Y=a*X+YX、Y為向量，長度為64；a為標量LDF0，aADDIR4,RX,#512；由X向量的末址地裝入R4LOOP:LDF2,0(RX)；取向量元素X(i)MULDF2,F0,F2；X向量與標量乘

LDF4,0(RY)；取向量元素Y(i)ADDDF4,F2,F4SD0(RY),F4；存結果向量

ADDIRX,RX,#8ADDIRY,RY,#8；地址增量

SUBR20,R4,RX；R4-RX→R20JNZR20,LOOP；判是否為02023/9/2134如果用向量處理機來完成同樣的操作LDF0，aLDVV1,RX；裝入向量XMULVV2,F0,V1；X向量與標量乘

LDVV3,RY；取向量元素YADDVV4,V2,V3SDVRY,V4；存結果向量特點：1、執(zhí)行指令6條（標量執(zhí)行8*64+2=514條）。降低了存儲器對取指帶寬的要求。2、標量運算過程中存在的數據相關性，在向量運算過程中已基本消除（共2次）。2023/9/2135一、向理處理的方式有三種處理方式：

1．橫向處理方式，又稱為水平處理方式，橫向加工方式等。向量計算是按行的方式從左至右橫向地進行。

2．縱向處理方式，又稱為垂直處理方式，縱向加工方式等。向量計算是按列的方式自上而下縱向地進行。

3．縱橫處理方式，又稱為分組處理方式，縱橫向加工方式等。橫向處理和縱向處理相結合的方式。2023/9/2136向量處理方式以一個簡單的C語言編寫的程序為例，說明向量的三種處理方式的工作原理。

for(i=1；i<=n；i++)

y[i]=a[i]×(b[i]+c[i]);2023/9/21371、橫向處理方式

逐個分量進行處理：設k中間變量

第1個分量：k＝B[1]＋C[1],Y[1]＝A[1]×k;

第2個分量：k＝B[2]＋C[2],Y[2]＝A[2]×k;

……

第n個分量：k＝B[N]＋C[N],Y[N]＝A[N]×k.存在兩個問題：

在計算向量的每個分量時，都發(fā)生先寫后讀的數據相關。流水線性能降低

如果采用多功能流水線，必須頻繁進行流水線切換橫向處理方式對向量處理機不適合

即使在標量處理機中，也經常通過編譯器進行指令流調度。2023/9/21382、縱向處理也稱為垂直處理方式，縱向加工方式等

T[1]=B[1]+C[1]

T[2]=B[2]+C[2]

……

T[n]=B[n]+C[n]

Y[1]=A[1]×T[1]

Y[2]=A[2]×T[2]

……

Y[N]=A[N]×T[N]采用向量指令只需要2條：

ADDVT,B,C

MULVY,A,T這種處理方式適用于向量處理機，數據相關不影響流水線連續(xù)工作。不同的運算操作只需要切換1次。2023/9/21393、縱橫向處理方式

將長度為n的向量分成若干組，每組長度為N，組內按縱向方式處理，依次處理各組，組間是橫向處理方式。用于寄存器-寄存器結構的向量處理機中

向量寄存器的長度是有限的，例如，每個向量寄存器有64個寄存器。向量長度N=64時，需要分組處理。分組方法：n＝Ｋ·N＋ｒ，其中：ｒ為余數，共分Ｋ＋１組。

組內采用縱向處理方式，組間采用橫向處理方式。因此，也稱為分組處理方式。2023/9/2140二、向量處理機的分類向量處理機的基本思想是把兩個向量的對應分量進行運算，產生一個結果向量。最關鍵問題是存儲器系統(tǒng)能夠滿足運算部件帶寬的要求。主要采用兩種方法：

1.存儲器－存儲器結構

多個獨立的存儲器模塊并行工作

處理機結構簡單，對存儲系統(tǒng)的訪問速度要求很高

2.寄存器－寄存器結構

運算通過向量寄存器進行

需要大量高速寄存器，對存儲系統(tǒng)訪問速度的要求降低2023/9/21411、存儲器－存儲器結構下圖說明一個具有8個存儲體的向量處理機：

MMMMMMMM流水結構加法器ABC=A+B三條互相獨立的數據通路，可并行工作，同一個存儲模塊同時只能為一個通路服務2023/9/2142

參加運算的向量數據在存儲器中，運算的結果也送到存儲器中，其結構與數據流的示意圖如下圖所示。如果以向量加法為例子C=A+B存儲器ABC流水線運算部件(