計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)-第四章(流水處理和ILP)

流水處理和

指令級并行流水線基本概念相關(guān)性分析技術(shù)多指令放射技術(shù)流水線基本概念引入流水線工作原理流水線的分類流水線的性能分析非線性流水線的調(diào)度技術(shù)本章內(nèi)容引入本章內(nèi)容>>流水線基本概念標(biāo)量處理機(jī)具有標(biāo)量數(shù)據(jù)表示和標(biāo)量指令系統(tǒng)的處理機(jī)稱為標(biāo)量處理機(jī)。提高指令執(zhí)行速度的主要途徑提高處理機(jī)的工作主頻；接受更好的算法和設(shè)計(jì)更好的功能部件；接受指令級并行（ILP）技術(shù)（本章介紹）。流水線工作原理本章內(nèi)容>>流水線基本概念基本思想表示方法主要特點(diǎn)流水線基本思想本章內(nèi)容>>流水線基本概念>>流水線工作原理基本思想：以指令流水線為例進(jìn)行介紹：取指分析執(zhí)行通過將一個(gè)重復(fù)的過程分解為若干子過程，每個(gè)子過程可以與其它子過程同時(shí)進(jìn)行。△t△t△t5之1流水線基本思想本章內(nèi)容>>流水線基本概念>>流水線工作原理依次執(zhí)行取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1……優(yōu)點(diǎn)：限制簡潔，節(jié)約設(shè)備。缺點(diǎn)：處理器執(zhí)行指令的速度慢功能部件的利用率很低n條指令的執(zhí)行時(shí)間為：5之2n條指令的執(zhí)行時(shí)間為：流水線基本思想本章內(nèi)容>>流水線基本概念>>流水線工作原理一次重疊

取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1取指k+2分析k+2執(zhí)行k+2優(yōu)點(diǎn)：執(zhí)行指令的速度較快功能部件的利用率較高缺點(diǎn)：限制較困難，需增加設(shè)備5之3n條指令的執(zhí)行時(shí)間為：流水線基本思想本章內(nèi)容>>流水線基本概念>>流水線工作原理二次重疊

優(yōu)點(diǎn)：執(zhí)行指令的速度更快功能部件的利用率更高缺點(diǎn)：限制更困難，需增加設(shè)備取指k+2分析k+2執(zhí)行k+2取指k+1分析k+1執(zhí)行k+1取指k分析k執(zhí)行k5之4流水線基本思想本章內(nèi)容>>流水線基本概念>>流水線工作原理流水線利用并行性實(shí)現(xiàn)：空間并行性設(shè)置多個(gè)獨(dú)立的操作部件。時(shí)間并行性分時(shí)運(yùn)用同一個(gè)部件的不同部分。5之5流水線表示方法本章內(nèi)容>>流水線基本概念>>流水線工作原理流水線的表示方法通常有三種：連接圖時(shí)空圖預(yù)約表連接圖本章內(nèi)容>>流水線基本概念>>流水線工作原理>>流水線表示方法分析器分析k+1流水

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

鎖存器輸入輸出t1t2Stage1latch輸入輸出t1t2Stage2latchStage3latcht32之1連接圖功能段流水線的每一個(gè)階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、流水級、流水節(jié)拍等。流水寄存器在每一個(gè)流水段的末尾或開頭必需設(shè)置一個(gè)寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。加入流水寄存器，會增加指令的執(zhí)行時(shí)間。在一般流水線中不畫出流水寄存器。本章內(nèi)容>>流水線基本概念>>流水線工作原理>>流水線表示方法2之2時(shí)空圖1時(shí)間空間0t1t2t3t4t52345123451234512345t6t7t8求階差對階尾數(shù)加規(guī)格化求階差對階尾數(shù)加規(guī)格化△t△t△t△t本章內(nèi)容>>流水線基本概念>>流水線工作原理>>流水線表示方法流水線主要特點(diǎn)本章內(nèi)容>>流水線基本概念>>流水線工作原理只有連續(xù)供應(yīng)同類任務(wù)才能發(fā)揮流水線效率盡量削減因條件分支造成的“斷流”，可通過編譯技術(shù)供應(yīng)連續(xù)的相同類型操作。每個(gè)流水線段都要設(shè)置一個(gè)流水寄存器用于保存本流水線段的執(zhí)行結(jié)果，會使流水線的執(zhí)行時(shí)間加長，是流水線中須要增加的主要硬件。各流水段的時(shí)間應(yīng)盡量相等流水線處理機(jī)的基本時(shí)鐘周期等于時(shí)間最長的流水段的時(shí)間長度。流水線須要有“裝入時(shí)間”和“排空時(shí)間”流水線的分類本章內(nèi)容>>流水線基本概念從不同的角度，依據(jù)不同的觀點(diǎn)，可以將流水線分成多種不同的種類。分類一分類二分類三分類四其它分類一單功能流水線只能完成一種固定功能的流水線。例如：Cray-1計(jì)算機(jī)中有12條；YH-1計(jì)算機(jī)有18條；Pentium有一條5段定點(diǎn)和一條8段浮點(diǎn)流水線；PentiumⅢ有兩條定點(diǎn)和一條浮點(diǎn)指令流水線。多功能流水線流水線的各段通過不同連接實(shí)現(xiàn)不同功能。例如：Texas公司的ASC機(jī)，8段流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加減法、定點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。本章內(nèi)容>>流水線基本概念>>流水線的分類按流水線具有功能的多少來分，可分為：2之1Texas公司ASC機(jī)上的8段多功能流水線2之2分類二本章內(nèi)容>>流水線基本概念>>流水線的分類在多功能流水線中，依據(jù)在同一時(shí)間內(nèi)是否能夠連接成多種方式，同時(shí)執(zhí)行多種功能，可以將多功能流水線分為：靜態(tài)流水線動態(tài)流水線靜態(tài)流水線本章內(nèi)容>>流水線基本概念>>流水線的分類>>分類二同一段時(shí)間內(nèi)，各個(gè)功能段只能依據(jù)一種方式連接，實(shí)現(xiàn)一種固定的功能。1時(shí)間空間023…n123…n123…n123…n123…n123…n1234…123…12……1輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出浮點(diǎn)加法定點(diǎn)乘法動態(tài)流水線在同一段時(shí)間內(nèi)，各段可以依據(jù)不同的方式連接，同時(shí)執(zhí)行多種功能。1時(shí)間空間023…n123…n123…n123…n123…n123…n輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出………………123546123541234123…………浮點(diǎn)加法定點(diǎn)乘法本章內(nèi)容>>流水線基本概念>>流水線的分類>>分類二分類三本章內(nèi)容>>流水線基本概念>>流水線的分類依據(jù)流水線的各個(gè)功能段之間是否有反饋信號，可以將流水線分為：線性流水線是指流水線內(nèi)各功能段串行連接，沒有反饋回路，各個(gè)功能段只經(jīng)過一次。一條線性流水線通常只完成一種固定的功能。例子：指令流水線、浮點(diǎn)加法器流水線等。非線性流水線是指流水線內(nèi)除有串行連接的通路外，還有某種反饋回路，使得一次流水過程中，某些段會多次通過。非線性流水線常常用于遞歸調(diào)用，或構(gòu)成多功能流水線等。3之1非線性流水線S1輸入S2S3輸出前饋回路反饋回路一種簡潔的非線性流水線對應(yīng)的兩種預(yù)約表××S3×S2×S14321S3×××S2×S143215×3之2本章內(nèi)容>>流水線基本概念>>流水線的分類提示線性流水線能夠用連接圖唯一表示，非線性流水線必需用連接圖和預(yù)約表共同表示。一條非線性流水線可以對應(yīng)有很多張預(yù)約表，同樣，一張預(yù)約表事實(shí)上僅表示了一條非線性流水線的一種工作方式線性流水線事實(shí)上也有預(yù)約表，只不過它的預(yù)約表是固定的（一張對角線為×的正方形的表格）3之3本章內(nèi)容>>流水線基本概念>>流水線的分類分類四依據(jù)流水線運(yùn)用的不同級別，可以將流水線分為：部件級流水線處理機(jī)級流水線系統(tǒng)級流水線本章內(nèi)容>>流水線基本概念>>流水線的分類部件級流水線本章內(nèi)容>>流水線基本概念>>流水線的分類>>分類四是指構(gòu)成部件內(nèi)的各子部件之間的流水。例如：浮點(diǎn)加法器流水線。求階差輸入輸出t1對階尾數(shù)加規(guī)格化t2t3t4處理機(jī)級流水線又稱為指令流水線，例如：在接受先行限制器的處理機(jī)中，各功能部件之間的流水線。先行指令

緩沖棧輸入先行控制方式

中的指令流水線先行指令

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

先行操作棧取指譯碼取操作數(shù)指令執(zhí)行部件后行寫數(shù)棧輸出執(zhí)行寫結(jié)果本章內(nèi)容>>流水線基本概念>>流水線的分類>>分類四系統(tǒng)級流水線也稱為宏流水線，是處理機(jī)之間的流水線。例如：每個(gè)處理機(jī)對同一個(gè)數(shù)據(jù)流的不同部分分別進(jìn)行處理。P1輸入任務(wù)1MM…P2任務(wù)2MP3任務(wù)3輸出本章內(nèi)容>>流水線基本概念>>流水線的分類>>分類四其它依據(jù)不同的數(shù)據(jù)表示方式分：標(biāo)量流水線對標(biāo)量數(shù)據(jù)進(jìn)行處理。向量流水線對向量數(shù)據(jù)進(jìn)行處理。依據(jù)流水線中信息流淌依次的限制方式分：依次流水線流水線輸出端的任務(wù)流出依次與輸入端的任務(wù)流入依次完全相同。異步流水線流水線輸出端的任務(wù)流出依次與輸入端的任務(wù)流入依次可以不一樣。本章內(nèi)容>>流水線基本概念>>流水線的分類流水線的性能分析本章內(nèi)容>>流水線基本概念吞吐率加速比效率流水線最佳段數(shù)的選擇性能分析舉例吞吐率定義單位時(shí)間內(nèi)能流出的任務(wù)數(shù)或能流出的結(jié)果數(shù)。公式n：任務(wù)數(shù)；Tm：處理完成n個(gè)任務(wù)所用的時(shí)間。本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之1案例1：志向狀況(1)假設(shè)在流水線各段的執(zhí)行時(shí)間均相等，輸入到流水線中的任務(wù)是連續(xù)的志向狀況下，一條單功能m段線性流水線能夠在m+n-1個(gè)時(shí)鐘周期內(nèi)完成n個(gè)任務(wù)。本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之21時(shí)間空間S123……n-1nS2…Sm123……n-1n…………………123……n-1nmt(n-1)tnt(m-1)tTm案例1：志向狀況(2)本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之3實(shí)際吞吐率最大吞吐率兩者之間的關(guān)系案例2：實(shí)際狀況假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到流水線中的任務(wù)是連續(xù)的志向狀況下。實(shí)際吞吐率最大吞吐率本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之4問題及解決本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之5問題流水線的TP和TPmax主要由流水線中執(zhí)行時(shí)間最長的那個(gè)功能段來確定，這個(gè)功能段就成了整個(gè)流水線的“瓶頸”。解決將流水線中的“瓶頸”再細(xì)分；通過重復(fù)設(shè)置多套瓶頸功能段，讓多個(gè)瓶頸功能段并行工作。舉例-瓶頸本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之6S1t1=tS2t2=3tS3t3=tS4t4=t輸出1時(shí)間空間S1S2S3S4ti(n-1)t2Tm23…n123…n123…n123…n輸入舉例-瓶頸解決本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之7S1輸入輸出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1輸入輸出t1=tS2-3S2-2S2-1S3S4t3=tt4=tt2=3t瓶頸細(xì)分多套瓶頸舉例-多套瓶頸時(shí)空圖本章內(nèi)容>>流水線基本概念>>流水線的性能分析8之81時(shí)間空間23nS1S2-1456…14…n-2n-1n-225…n-136…n123n456…n-2n-1123n456…n-2n-1S2-2S2-3S3S4加速比本章內(nèi)容>>流水線基本概念>>流水線的性能分析定義完成同樣一批任務(wù)，不運(yùn)用流水線所用的時(shí)間與運(yùn)用流水線所用的時(shí)間之比。公式T0：依次執(zhí)行所用的時(shí)間；Tm：運(yùn)用流水線所用的時(shí)間。3之1案例1：志向狀況假設(shè)在流水線各段的執(zhí)行時(shí)間都相等，輸入到流水線中的任務(wù)是連續(xù)的志向狀況下。實(shí)際加速比最大加速比本章內(nèi)容>>流水線基本概念>>流水線的性能分析3之2案例2：實(shí)際狀況假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到流水線中的任務(wù)是連續(xù)的志向狀況下。實(shí)際加速比本章內(nèi)容>>流水線基本概念>>流水線的性能分析3之3效率本章內(nèi)容>>流水線基本概念>>流水線的性能分析定義是指流水線的設(shè)備利用率。在時(shí)空圖上，流水線的效率定義為n個(gè)任務(wù)占用的時(shí)空區(qū)與m個(gè)功能段總的時(shí)空區(qū)之比。公式1時(shí)間空間S1…nS2…Sm1…n………1…n4之1案例1：志向狀況假設(shè)在流水線各段的執(zhí)行時(shí)間都相等，輸入到流水線中的任務(wù)是連續(xù)的志向狀況下。實(shí)際效率最大效率本章內(nèi)容>>流水線基本概念>>流水線的性能分析4之2案例2：實(shí)際狀況(1)假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到流水線中的任務(wù)是連續(xù)的志向狀況下。實(shí)際效率（功能段等權(quán)值）本章內(nèi)容>>流水線基本概念>>流水線的性能分析4之3案例2：實(shí)際狀況(2)實(shí)際效率（功能段權(quán)值不同）其中，i為i段的權(quán)值，i<m，且本章內(nèi)容>>流水線基本概念>>流水線的性能分析4之4流水線最佳段數(shù)的

選擇本章內(nèi)容>>流水線基本概念>>流水線的性能分析問題提出功能段數(shù)量的增加能提高流水線的吞吐率和加速比，但使流水線價(jià)格增加（鎖存器數(shù)量的增加），一條指令執(zhí)行的總時(shí)間增加（鎖存器的總延遲時(shí)間增加）。所以從性價(jià)比角度動身流水線存在著最佳段數(shù)。2之1流水線最佳段數(shù)的選擇問題解決對自變量m求導(dǎo)，求PCR的最大值，得到最佳段數(shù)為：本章內(nèi)容>>流水線基本概念>>流水線的性能分析t：任務(wù)總時(shí)間d：鎖存器時(shí)間m：功能段數(shù)a：全部功能段價(jià)格b：鎖存器價(jià)格2之2性能分析舉例本章內(nèi)容>>流水線基本概念>>流水線的性能分析問：用一條4段浮點(diǎn)加法器流水線求8個(gè)浮點(diǎn)數(shù)的和，要求所用時(shí)間最短，求流水線的吞吐率、加速比和效率。Z＝A＋B＋C＋D＋E＋F＋G＋H答：由于存在著數(shù)據(jù)相關(guān)，假如干脆交與流水線處理，效果與依次執(zhí)行完全一樣，因此先作一個(gè)簡潔變換，然后交與流水線處理。Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]3之1性能分析舉例本章內(nèi)容>>流水線基本概念>>流水線的性能分析3之21時(shí)間空間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+HZ被加數(shù)性能分析舉例流水線的吞吐率為：流水線的加速比為：流水線的效率為：本章內(nèi)容>>流水線基本概念>>流水線的性能分析3之3非線性流水線的

調(diào)度技術(shù)本章內(nèi)容>>流水線基本概念調(diào)度目的非線性流水線的沖突無沖突調(diào)度方法優(yōu)化調(diào)度方法調(diào)度目的本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度目的是要找出一個(gè)最小的循環(huán)周期，依據(jù)這周期向流水線輸入新任務(wù)，流水線的各個(gè)功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。非線性流水線的沖突本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)啟動距離向一條非線性流水線的輸入端依次輸入兩個(gè)任務(wù)之間的時(shí)間間隔稱為啟動距離/等待時(shí)間。沖突幾個(gè)任務(wù)同時(shí)爭用同一個(gè)流水線功能段的狀況稱為非線性流水線的沖突。禁止啟動距離引起非線性流水線沖突的啟動距離稱為禁止啟動距離。5之1舉例-非線性流水線本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)5之2輸出S1S2S3S4輸入×S4××S3××S2×××S17654321時(shí)間流水段舉例-流水線沖突本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)5之3舉例-流水線不沖突本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)5之4不發(fā)生沖突的啟動距離一般是一個(gè)循環(huán)數(shù)列，稱為非線性流水線的啟動循環(huán)，記作（1，7）。舉例-流水線不沖突啟動距離5也可以認(rèn)為是一個(gè)循環(huán)數(shù)列，稱為非線性流水線的恒定循環(huán)，記作（5）。本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)5之5無沖突調(diào)度方法-例子本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)×S4××S3××S2××S17654321時(shí)間流水段12之1S1S2S3S4輸入輸出無沖突調(diào)度方法-步驟本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)由預(yù)約表得到禁止向量由禁止向量得到?jīng)_突向量由沖突向量構(gòu)造調(diào)度流水線的狀態(tài)圖在狀態(tài)圖中找出可用啟動距離，并計(jì)算平均啟動距離找出平均啟動距離最小的啟動循環(huán)或恒定循環(huán)12之2步驟一本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法由預(yù)約表得到禁止向量定義：將一條非線性流水線的全部各功能段禁止啟動距離組合在一起形成的數(shù)列。計(jì)算：將預(yù)約表中的每一行中隨意兩個(gè)“×”之間的距離都計(jì)算出來，去掉重復(fù)的，由這些數(shù)形成禁止向量。例子：上例所示非線性流水線的禁止向量為（2，4，6）。12之3步驟二本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法由禁止向量得到?jīng)_突向量概念：沖突向量用一個(gè)m位的二進(jìn)制數(shù)表示（其中m是禁止向量中的最大值），一般格式為C=（CmCm-1…Ci…C2C1），若i在禁止向量中，則Ci=1，否則Ci=0，其中Cm確定為1。例子：上例所示非線性流水線的沖突向量為C=（101010）。12之4步驟三（1）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法由沖突向量構(gòu)造調(diào)度流水線的狀態(tài)圖將沖突向量C作為初始沖突向量送入一個(gè)m位邏輯右移移位器，移位m次；若移出的是“0”，用移位器中的值與初始沖突向量作“按位或”運(yùn)算，得到一個(gè)新的沖突向量；若移出的是“1”，不作任何處理。將中間形成的每一個(gè)新的沖突向量同樣處理；畫出狀態(tài)圖。 在初始沖突向量和全部的新形成的沖突向量之間用帶箭頭的線連接，表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系。12之5步驟三（2）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法12之6步驟四（1）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法在狀態(tài)圖中找出可用啟動距離，并計(jì)算平均啟動距離在狀態(tài)圖中從初始狀態(tài)動身，能構(gòu)成一種間隔拍數(shù)呈周期性重復(fù)的方案就是可用啟動距離。即：找出全部的簡潔循環(huán)（是指在狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)）。12之7步驟四（2）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法簡單循環(huán)平均啟動距離1，743，755，763，5，755，3，753，54557712之8步驟五（1）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法找出平均啟動距離最小的啟動循環(huán)或恒定循環(huán)啟動循環(huán)（1，7）和（3，5）恒定循環(huán)（5）12之9步驟五（2）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法12之10××S3×S2×S143215×S467××1234567891011121314151617181920…S1X1X2X1X2X3X4X3X4X5X6S2X1X2X1X2X3X4X3X4X5X6S3X1X2X1X2X3X4X3X4X5X6S4X1X2X3X4X5最小啟動循環(huán)（1，7）的流水線工作狀態(tài)啟動周期重復(fù)啟動周期步驟五（3）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法12之11××S3×S2×S143215×S467××1234567891011121314151617181920…S1X1X2X1X3X2X4X3X5X4X6S2X1X2X1X2X3X4X3X4X5S3X1X1X2X2X3X3X4X4X5S4X1X2X3X4X5最小啟動循環(huán)（3，5）的流水線工作狀態(tài)啟動周期重復(fù)啟動周期步驟五（4）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)>>無沖突調(diào)度方法12之12××S3×S2×S143215×S467××1234567891011121314151617181920…S1X1X2X1X3X2X4X3S2X1X1X2X2X3X3X4S3X1X1X2X2X3X3X4X4S4X1X2X3X4最小恒定循環(huán)（5）的流水線工作狀態(tài)啟動周期重復(fù)啟動周期優(yōu)化調(diào)度方法本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)問題當(dāng)接受最小啟動循環(huán)啟動非線性流水線時(shí)，沒有充分發(fā)揮非線性流水線的效率，因?yàn)榱魉€中的很多流水段還有空閑，即使最繁忙的流水段也有空閑。解決接受非線性流水線的優(yōu)化調(diào)度方法（預(yù)留算法），可以使流水線的工作效率最高。7之1理論基礎(chǔ)本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍并于1992年進(jìn)行了證明：最小平均啟動距離的下限是預(yù)約表中隨意一行里“×”的最多個(gè)數(shù)。最小平均啟動距離小于等于狀態(tài)圖中隨意一個(gè)簡潔循環(huán)的平均啟動距離。最小平均啟動距離的上限是沖突向量中1的個(gè)數(shù)再加上1。7之2預(yù)留算法本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)確定流水線的最小啟動距離最小啟動距離等于預(yù)約表中隨意一行中“×”的最大個(gè)數(shù)。確定最小啟動循環(huán)為簡化流水線的限制邏輯，一般接受恒定循環(huán)作為最小啟動循環(huán)。插入延遲進(jìn)行預(yù)留對預(yù)約表中隨意一行中隨意兩個(gè)“×”之間的距離是最小啟動距離整數(shù)倍的通過插入延遲進(jìn)行預(yù)留。7之3舉例-優(yōu)化前（前例）本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)×S4××S3××S2××S17654321時(shí)間流水段S1S2S3S4輸入輸出7之4舉例-優(yōu)化后本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)S1S2S3S4輸入輸出D1時(shí)間12345678功能段S1××S2××S3××S4×延遲D1×7之5舉例-優(yōu)化后從狀態(tài)圖中很簡潔可以看出：流水線的最小啟動循環(huán)是（2）。本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)7之6舉例-優(yōu)化后在非線性流水線中，“×”最多的流水段確定是“瓶頸”流水段。實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使“瓶頸”流水段處于勞碌狀態(tài)，沒有空閑周期。本章內(nèi)容>>流水線基本概念>>非線性流水線的調(diào)度技術(shù)7之7相關(guān)性分析技術(shù)基本概念資源相關(guān)數(shù)據(jù)相關(guān)限制相關(guān)綜合應(yīng)用循環(huán)處理本章內(nèi)容基本概念本章內(nèi)容>>相關(guān)性分析技術(shù)概念相關(guān)（CorrelationorDependency）也稱為沖突（Hazard）是指鄰近指令之間存在著某種關(guān)系，影響指令的重疊執(zhí)行或流水線的正常運(yùn)行。內(nèi)容有三種類型的相關(guān)：資源相關(guān)：爭用部件。數(shù)據(jù)相關(guān)：變更操作數(shù)的讀寫依次，使得依次執(zhí)行與流水執(zhí)行時(shí)結(jié)果不同。限制相關(guān)：分支、轉(zhuǎn)子程序、中斷。2之1示例環(huán)境說明本章內(nèi)容>>相關(guān)性分析技術(shù)在介紹相關(guān)性分析技術(shù)時(shí)，我們以一個(gè)典型的RISC指令流水線（MIPS64指令集）為例進(jìn)行介紹：MIPS基本流水線MIPS擴(kuò)展流水線2之2MIPS基本流水線本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明RISC指令集接受MIPS64（MIPS的64位版本）的整數(shù)子集：ALU指令（5個(gè)時(shí)鐘周期）、load（5個(gè)時(shí)鐘周期）/store（4個(gè)時(shí)鐘周期）指令和分支指令（2個(gè)時(shí)鐘周期）。RISC指令的實(shí)現(xiàn)每一條RISC指令的執(zhí)行至多須要5個(gè)時(shí)鐘周期：取指令周期（IF）、指令譯碼/讀寄存器周期（ID）、執(zhí)行/有效地址周期（EX）、訪問存儲器周期（MEM）和寫回周期（WB）。13之1取指令周期（IF）本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明 IR←Mem[PC] NPC←PC+4說明：依據(jù)PC指示的地址從存儲器中取指令并裝入指令寄存器（IR），同時(shí)PC加4以獲得下一條指令的地址。IR中保存下一個(gè)時(shí)鐘周期須要的指令，NPC中保存下一條指令的PC。13之2圖示IF本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之3指令譯碼/讀寄存器周期（ID）本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明 A←Regs[rs] B←Regs[rt] Imm←IR的馬上數(shù)字段進(jìn)行符號擴(kuò)展 ALUOutput←NPC+(Imm<<2) Cond←(A==0) if(cond)PC←ALUOutput說明：分析指令并訪問寄存器堆以讀寄存器，并結(jié)束分支指令（為簡潔只設(shè)置一條：BEQZ）的操作。13之4圖示ID本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之5執(zhí)行/有效地址周期（EX）訪問存儲器ALUOutput←A+Imm寄存器-寄存器ALUALUOutput←AfuncB寄存器-馬上數(shù)ALUALUOutput←AopImm說明：Load/Store指令在本周期形成有效地址。ALU指令完成相應(yīng)的ALU操作。本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之6圖示EX本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之7訪問存儲器周期（MEM）本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明 LMD←Mem[ALUOutput]or Mem[ALUOutput]←B說明：Load指令從存儲器中讀出數(shù)據(jù)并裝入LMD（裝入存儲器數(shù)據(jù)）寄存器，Store指令將寄存器B中的數(shù)據(jù)寫入存儲器。13之8圖示MEM本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之9寫回周期（WB）Load指令Regs[rt]←LMD寄存器-寄存器ALURegs[rd]←ALUOutput寄存器-馬上數(shù)ALURegs[rt]←ALUOutput說明：將結(jié)果寫入寄存器堆。寄存器的寫入端口在兩個(gè)目標(biāo)中選擇一個(gè)（rtorrd），具體選擇哪一個(gè)要由操作碼確定。本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之10圖示W(wǎng)B本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明13之11時(shí)空圖本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明指令時(shí)鐘123456789iIFIDEXMEMWBi+1IFIDEXMEMWBi+2IFIDEXMEMWBi+3IFIDEXMEMWBi+4IFIDEXMEMWB13之12MIPS基本流水線的數(shù)據(jù)通路13之13IM：指令存儲器DM：數(shù)據(jù)存儲器CC

：時(shí)鐘周期寫操作（前半周期進(jìn)行）讀操作（后半周期進(jìn)行）MIPS基本流水線的實(shí)現(xiàn)9之9MIPS擴(kuò)展流水線本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明3之1在MIPS基本流水線中引入浮點(diǎn)操作功能。主定點(diǎn)操作部件負(fù)責(zé)load/store、定點(diǎn)ALU操作和分支操作（功能同MIPS基本流水線）。浮點(diǎn)/定點(diǎn)乘法部件負(fù)責(zé)浮點(diǎn)/定點(diǎn)乘法，接受流水設(shè)計(jì)。浮點(diǎn)加法部件負(fù)責(zé)處理浮點(diǎn)加、減法及定點(diǎn)數(shù)/浮點(diǎn)數(shù)之間的轉(zhuǎn)換，接受流水設(shè)計(jì)。浮點(diǎn)/定點(diǎn)除法部件負(fù)責(zé)浮點(diǎn)/定點(diǎn)除法，不接受流水設(shè)計(jì)。連接圖本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明3之2一組獨(dú)立的浮點(diǎn)操作流水線時(shí)序藍(lán)色斜體的流水段須要數(shù)據(jù)，紅色的流水段已經(jīng)得到結(jié)果。本章內(nèi)容>>相關(guān)性分析技術(shù)>>示例環(huán)境說明3之3MUL.DIFIDM1M2M3M4M5M6M7MEMWBADD.DIFIDA1A2A3A4MEMWBL.DIFIDEXMEMWBS.DIFIDEXMEMWB資源相關(guān)本章內(nèi)容>>相關(guān)性分析技術(shù)因?yàn)橘Y源沖突而導(dǎo)致流水線斷流。例1:指重疊指令或流水線中的指令同時(shí)要用同一個(gè)功能部件，事實(shí)上是一種沖突。非線性流水線的調(diào)度就是為了盡量避開資源運(yùn)用上的沖突。例2:后面介紹的RISC指令流水線當(dāng)指令和數(shù)據(jù)共享同一個(gè)存儲器時(shí)，也會出現(xiàn)資源沖突（見后圖）。4之1MIPS基本流水線當(dāng)指令和數(shù)據(jù)共享同一個(gè)存儲器時(shí)會出現(xiàn)資源沖突4之2IF段ID段EX段MEM段WB段資源相關(guān)本章內(nèi)容>>相關(guān)性分析技術(shù)緣由分析主要有：部分功能部件沒有充分流水資源沒有充分重復(fù)設(shè)置解決方法可以接受推后處理法來解決：暫停相關(guān)指令的執(zhí)行，直到所需的功能單元能夠運(yùn)用為止。4之3例子本章內(nèi)容>>相關(guān)性分析技術(shù)指令時(shí)鐘123456789loadIFIDEXMEMWBi+1IFIDEXMEMWBi+2IFIDEXMEMWBi+3stallIFIDEXMEMWBi+4IFIDEXMEM4之4時(shí)空圖的另一種畫法數(shù)據(jù)相關(guān)本章內(nèi)容>>相關(guān)性分析技術(shù)數(shù)據(jù)相關(guān)類型數(shù)據(jù)相關(guān)解決動態(tài)調(diào)度技術(shù)數(shù)據(jù)相關(guān)類型本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)“先寫后讀”相關(guān)“先讀后寫”相關(guān)“寫寫”相關(guān)“先寫后讀”相關(guān)（RAW）本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型概念有兩條相鄰指令i和j，i在j之前執(zhí)行，指令i將結(jié)果寫入某個(gè)存儲單元，而指令j從相同存儲單元中讀取該數(shù)據(jù)。假如指令j想在指令i寫之前去讀數(shù)據(jù)，則會發(fā)生“先寫后讀”相關(guān)，也稱為寫讀相關(guān)、數(shù)據(jù)相關(guān)、RAW相關(guān)、WR相關(guān)等。2之1“先寫后讀”相關(guān)（RAW）本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型例子 i：DADDR1,R2,R3;(R2)＋(R3)→(R1) j：DSUBR4,R1,R5;(R1)－(R5)→(R4)2之2IF段ID段EX段MEM段WB段流水寄存器“先讀后寫”相關(guān)（WAR）本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型概念有兩條相鄰指令i和j，i在j之前執(zhí)行，指令i從某個(gè)存儲單元中讀取數(shù)據(jù)，而指令j將結(jié)果寫入相同存儲單元。假如指令j想在指令i讀之前去寫數(shù)據(jù)，則會發(fā)生“先讀后寫”相關(guān)，也稱為讀寫相關(guān)、反相關(guān)、WAR相關(guān)、RW相關(guān)等。2之1“先讀后寫”相關(guān)（WAR）本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型例子 i：DSUB

R4,R1,R5;(R1)－(R5)→(R4) j：DADDR1,R2,R3;(R2)＋(R3)→(R1)2之2“寫寫”相關(guān)

（WAW）本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型概念有兩條相鄰指令i和j，i在j之前執(zhí)行，指令i將結(jié)果寫入某個(gè)存儲單元，而指令j也將結(jié)果寫入相同存儲單元。假如指令j想在指令i寫之前去寫該數(shù)據(jù)，則會發(fā)生“寫寫”相關(guān)，也稱為寫寫相關(guān)、輸出相關(guān)、WAW相關(guān)、WW相關(guān)等。3之1“寫寫”相關(guān)

（WAW）本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型3之2例子 i：DSUB

R1,R4,R5;(R4)－(R5)→(R1) j：DADDR1,R2,R3;(R2)＋(R3)→(R1)“先寫后讀”相關(guān)在流水線依次執(zhí)行和亂序執(zhí)行時(shí)都可能發(fā)生，“先讀后寫”相關(guān)和“寫寫”相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生，而“讀讀”相關(guān)無需處理。提示本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)類型3之3數(shù)據(jù)相關(guān)解決本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)“先讀后寫”相關(guān)“寫寫”相關(guān)設(shè)置專用路徑推后處理“先寫后讀”相關(guān)寄存器換名設(shè)置專用路徑思想將結(jié)果干脆送到須要它的功能部件，即：一個(gè)結(jié)果能夠從一個(gè)部件的輸出干脆送到另一個(gè)部件的輸入。程序段DADD R1,R2,R3DSUB R4,R1,R5AND R6,R1,R7OR R8,R1,R9XOR R10,R1,R11本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)解決3之1“先寫后讀”數(shù)據(jù)相關(guān)3之2通過設(shè)置專用路徑解決“先寫后讀”數(shù)據(jù)相關(guān)3之3推后處理思想對于接受設(shè)置專用路徑無法解決的數(shù)據(jù)相關(guān)只有推后處理相關(guān)指令，直至數(shù)據(jù)就緒。程序段LD R1,0(R2)DSUB R4,R1,R5AND R6,R1,R7OR R8,R1,R9本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)解決3之1通過設(shè)置專用路徑解決數(shù)據(jù)相關(guān)（失?。?之2失敗通過推后處理解決數(shù)據(jù)相關(guān)3之3指令時(shí)鐘123456789LDR1,0(R2)IFIDEXMEMWBDSUBR4,R1,R5IFIDEXMEMWBANDR6,R1,R7IFIDEXMEMWBORR8,R1,R9IFIDEXMEMWB指令時(shí)鐘123456789LDR1,0(R2)IFIDEXMEMWBDSUBR4,R1,R5IFIDstallEXMEMWBANDR6,R1,R7IFstallIDEXMEMWBORR8,R1,R9stallIFIDEXMEMWB推后處理前的數(shù)據(jù)相關(guān)寄存器換名

WAR相關(guān)WAW相關(guān)本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)解決2之1ACACBBB’ijijACACBB’Bijij寄存器換名舉例換名前DIV.D F0,F2,F4ADD.D F6,F0,F8S.D F6,0(R1)SUB.D F8,F10,F14MUL.D F6,F10,F8換名后DIV.D F0,F2,F4ADD.D S,F0,F8S.D S,0(R1)SUB.D T,F10,F14MUL.D F6,F10,T本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>數(shù)據(jù)相關(guān)解決2之2動態(tài)調(diào)度技術(shù)本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)引入思想方法CDC計(jì)分牌法Tomasulo算法引入本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù) DIV.D F0,F2,F4 ADD.D F10,F0,F8 SUB.D F12,F8,F14時(shí)間1234…2627282930DIV.DIFIDDIVMEMWBADD.DIFID暫?！瓡和XMEMWBSUB.DIFID暫停…暫停EXMEMWB2之1問題在MIPS擴(kuò)展流水線中，指令按序放射、按序執(zhí)行和按序完成，RAW相關(guān)使ADD.D及后續(xù)指令在流水線中被暫停，即使后續(xù)指令與DIV.D、ADD.D指令沒有沖突，這限制流水線的性能。解決假如指令按序放射、亂序執(zhí)行和亂序完成，則可以削減暫停所帶來的影響。引入本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)2之2思想本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)記錄和檢測指令相關(guān)，當(dāng)指令的操作數(shù)就緒時(shí)就執(zhí)行該指令（即：指令按序放射、亂序執(zhí)行和亂序完成）以降低RAW相關(guān)的影響，接受寄存器換名技術(shù)來避開WAR、WAW相關(guān)的影響。Tomasulo算法本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)概述實(shí)現(xiàn)舉例概述本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)>>Tomasulo算法Tomasulo算法是由R.M.Tomasulo于1967年首先提出，并最早在大型機(jī)IBM360/91處理機(jī)的浮點(diǎn)處理部件中運(yùn)用。Tomasulo算法也稱為公共數(shù)據(jù)總線（CDB）法、令牌法等，它接受亂序方式來提高流水線的性能，并通過分散限制的方法處理數(shù)據(jù)相關(guān)。基于Tomasulo算法的MIPS浮點(diǎn)部件的基本結(jié)構(gòu)6之1FPaddersAdd1Add2Add3FPmultipliersMult1Mult2FromMemFPRegistersReservationStationsCommonDataBus(CDB)ToMemFPOpQueueLoadBuffersStoreBuffersLoad1Load2Load3Load4Load5Load6保留站Op操作類型。Vj和Vk存放兩個(gè)源操作數(shù)的值。Qj和Qk存放產(chǎn)生相應(yīng)源操作數(shù)的保留站。對每個(gè)源操作數(shù)，V字段或Q字段中只有一個(gè)是有效的。A用于保存load/store操作的存儲器地址信息。最初指令中的馬上數(shù)存放于此，在地址計(jì)算后有效地址也存放于此。Busy指示該保留站及相關(guān)的功能部件是否正在運(yùn)用。本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)>>Tomasulo算法寄存器換名是通過保留站實(shí)現(xiàn)的，保留站的數(shù)據(jù)結(jié)構(gòu)為：6之2存儲設(shè)備讀數(shù)/寫數(shù)緩沖器每個(gè)緩沖器也都是保留站，字段同前。浮點(diǎn)寄存器堆每個(gè)寄存器都需設(shè)置Qi字段，用于保存保留站號。在該保留站中進(jìn)行的操作，其結(jié)果將存入該寄存器。假如Qi為空，則表示當(dāng)前不會有運(yùn)算結(jié)果要存到該寄存器。本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)>>Tomasulo算法6之3指令執(zhí)行過程本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)>>Tomasulo算法放射從浮點(diǎn)操作隊(duì)列中取得一條指令。假如相應(yīng)保留站空閑（即：沒有結(jié)構(gòu)沖突），則可以放射指令和發(fā)送數(shù)據(jù)。寄存器換名工作在本階段進(jìn)行。執(zhí)行對操作數(shù)進(jìn)行相應(yīng)的操作。當(dāng)指令所須要的源操作數(shù)都準(zhǔn)備好，就可以執(zhí)行該運(yùn)算；否則監(jiān)視CDB等待源操作數(shù)。寫回結(jié)果當(dāng)計(jì)算結(jié)果出來之后，送至CDB，進(jìn)而寫回到寄存器中，或被其它保留站讀取。6之4指令格式浮點(diǎn)運(yùn)算指令load和store指令MUL.DF4，F(xiàn)0，F(xiàn)2rsrdrtL.DF2，45（R3）rsrtimmS.DF3，40（R4）rsrtimm本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)>>Tomasulo算法6之5jkjjkAA指令執(zhí)行的具體過程6之6舉例程序 L.D F6,34(R2) L.D F2,45(R3) MUL.D F0,F2,F4 SUB.D F8,F2,F6 DIV.D F10,F0,F6 ADD.D F6,F8,F2假設(shè)各指令在“放射”和“寫回結(jié)果”所花時(shí)鐘周期數(shù)都為1，在“執(zhí)行”階段所花時(shí)鐘周期數(shù)分別為：L.D為2，ADD.D和SUB.D為2，MUL.D為10，DIV.D為40。本章內(nèi)容>>相關(guān)性分析技術(shù)>>數(shù)據(jù)相關(guān)>>動態(tài)調(diào)度技術(shù)>>Tomasulo算法21之1指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1YLoadRegs[R2]34Load2Add1Add2Add3Mult1Mult2寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiLoad1CLOCK：121之2指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)1L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1YLoadRegs[R2]34Load2YLoadRegs[R3]45Add1Add2Add3Mult1Mult2寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiLoad2Load1CLOCK：221之3指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)2L.DF2,45(R3)1MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1YLoad34+Regs[R2]Load2YLoadRegs[R3]45Add1Add2Add3Mult1YMULRegs[F4]Load2Mult2寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Load2Load1CLOCK：321之4指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)2MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2YLoad45+Regs[R3]Add1YSUBMem[34+Regs[R2]]Load2Add2Add3Mult1YMULRegs[F4]Load2Mult2寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Load2Mem[34+Regs[R2]]Add1CLOCK：421之5指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1YSUBMem[34+Regs[R2]]Mem[45+Regs[R3]]Add2Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Mem[34+Regs[R2]]Add1Mult2CLOCK：521之6指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F41SUB.DF8,F6,F21DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1YSUBMem[34+Regs[R2]]Mem[45+Regs[R3]]Add2YADDMem[45+Regs[R3]]Add1Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Add1Mult2CLOCK：621之7指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F42SUB.DF8,F6,F22DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1YSUBMem[34+Regs[R2]]Mem[45+Regs[R3]]Add2YADDMem[45+Regs[R3]]Add1Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Add1Mult2CLOCK：721之8指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F43SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2YADDMem[34+Regs[R2]]-Mem[45+Regs[R3]Mem[45+Regs[R3]]Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：821之9指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F44SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F21站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2YADDMem[34+Regs[R2]]-Mem[45+Regs[R3]Mem[45+Regs[R3]]Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：921之10指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F45SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F22站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2YADDMem[34+Regs[R2]]-Mem[45+Regs[R3]Mem[45+Regs[R3]]Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：1021之11指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F46SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]…Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：1121之12指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F47SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1221之13指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F48SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1321之14指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F49SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1421之15指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F410SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1521之16指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2YDIVMem[45+Regs[R3]*Regs[F4]Mem[34+Regs[R2]]寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMem[45+Regs[R3]*Regs[F4]………Mult2CLOCK：1621之17指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F61ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2YDIVMem[45+Regs[R3]*Regs[F4]Mem[34+Regs[R2]]寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMem[45+Regs[R3]*Regs[F4]………Mult2CLOCK：1721之18……21之19指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F640ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2YDIVMem[45+Regs[R3]*Regs[F4]Mem[34+Regs[R2]]寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30QiMem[45+Regs[R3]*Regs[F4]………Mult2CLOCK：5621之20指令指令狀態(tài)發(fā)射執(zhí)行寫回結(jié)果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2N寄存器狀態(tài)字段F0F2F4F6F8F10F12…F30Qi………Mem[45+Regs[R3]*Regs[F4]/Mem[34+Regs[R2]]CLOCK：5721之21限制相關(guān)本章內(nèi)容>>相關(guān)性分析技術(shù)基本概念條件轉(zhuǎn)移的影響條件轉(zhuǎn)移的處理中斷的處理基本概念本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)因程序的執(zhí)行方向可能被變更而引起的相關(guān)，也稱為全局相關(guān)（而將前面介紹的其他相關(guān)稱為局部相關(guān)）?？赡茏兏绦驁?zhí)行方向的指令主要包括：無條件轉(zhuǎn)移、條件轉(zhuǎn)移、子程序調(diào)用、中斷等。2之1舉例本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)指令時(shí)鐘123456789分支指令I(lǐng)FIDEXMEMWB分支后繼IFIFIDEXMEMWB分支后繼+1IFIDEXMEMWB分支后繼+2IFIDEXMEMWB2之2條件轉(zhuǎn)移的影響本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)對于一條有k個(gè)流水段的流水線，在最壞狀況下每一次條件轉(zhuǎn)移（條件分支）指令將造成k-1個(gè)時(shí)鐘的“停頓”；假設(shè)條件轉(zhuǎn)移指令在一般程序中所占的比例為p，轉(zhuǎn)移成功的概率為q。則n條指令的總執(zhí)行時(shí)間是：3之1有條件轉(zhuǎn)移影響的流水線吞吐率有條件轉(zhuǎn)移影響的最大流水線吞吐率條件轉(zhuǎn)移的影響本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)3之2流水線吞吐率下降的比例例子據(jù)統(tǒng)計(jì)：在一些典型程序中p=20%、q=60%，對于有8個(gè)流水段的流水線，最大吞吐率會下降46%；對于有10個(gè)流水段的流水線，最大吞吐率會下降52%。條件轉(zhuǎn)移指令對流水線的影響很大，必需實(shí)行措施降低影響。條件轉(zhuǎn)移的影響本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)3之3條件轉(zhuǎn)移的處理本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)條件出來前提前形成條件碼預(yù)料條件出來后停頓提前形成條件碼本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)>>條件轉(zhuǎn)移的處理可在運(yùn)算起先或中間產(chǎn)生條件碼在絕大多數(shù)狀況下，只要在運(yùn)算部件的入口處設(shè)置一個(gè)比較器，通過比較兩個(gè)操作數(shù)的符號或者階碼就能夠提前形成結(jié)果的正負(fù)號、是否為0、是否溢出等條件碼。假如在一個(gè)時(shí)鐘周期之內(nèi)產(chǎn)生條件碼，則正好可以供應(yīng)應(yīng)下一條條件轉(zhuǎn)移指令運(yùn)用，這樣流水線就不會“斷流”。3之1提前形成條件碼本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)>>條件轉(zhuǎn)移的處理加快循環(huán)內(nèi)條件碼形成編譯前： LOADR1,NUM ;循環(huán)次數(shù)初值裝入R1LOOP： …… ;循環(huán)體起先 …… DECR1 ;循環(huán)次數(shù)減“1” BNELOOP ;測試循環(huán)是否則結(jié)束 HALT ;程序結(jié)束NUM： n3之2提前形成條件碼本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)>>條件轉(zhuǎn)移的處理加快循環(huán)內(nèi)條件碼形成編譯后： LOADR1,NUM ;循環(huán)次數(shù)裝入R1中LOOP:LDECR1;一條專用的循環(huán)次數(shù)減1指令 …… ;循環(huán)體起先 …… LBNELOOP;一條專用的測試循環(huán)是否結(jié)束的指令 HALT ;程序結(jié)束NUM:n ;循環(huán)次數(shù)【提示】指令LDEC和LBNE運(yùn)用專用的條件碼寄存器。3之3預(yù)測本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)>>條件轉(zhuǎn)移的處理思想預(yù)料的后續(xù)處理分支現(xiàn)場的愛護(hù)及復(fù)原預(yù)防預(yù)料不中時(shí)的加速處理提高預(yù)料命中率靜態(tài)預(yù)料動態(tài)預(yù)料思想本章內(nèi)容>>相關(guān)性分析技術(shù)>>限制相關(guān)>>條件轉(zhuǎn)移的處理>>預(yù)料選取發(fā)生概率較高的分支為預(yù)料方向，運(yùn)行但不寫回結(jié)果。若猜對，接著執(zhí)行；否則,作廢預(yù)料方向的執(zhí)行，返回實(shí)際轉(zhuǎn)移處。時(shí)間ti+1i+2…i+k-3i+k-2輸出輸入i