《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案.ppt

2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),1,3.4 RISC的基本流水線(P70),下面是RISC的指令流水線簡化結(jié)構(gòu)圖（5段結(jié)構(gòu)），每段1個(gè)時(shí)鐘周期。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),2,(1)流水運(yùn)行方式,RISC流水線5段功能的初步定義（時(shí)鐘周期圖Cycle）,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令K+1,取指 PC+4,譯碼 取數(shù),計(jì)算 判斷,訪存 送PC,寫回,(2)順序運(yùn)行方式,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令K+1,取指,譯碼 取數(shù),計(jì)算 判斷,訪存 送PC,寫回,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),3,RISC流水線5段功能的初步定義,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),4,為了簡單，先考慮順序處理方式下的工作過程（即不考慮并行處理多條指令）： (1) IF 取指周期（后來稱IM） (2) ID 指令譯碼/讀寄存器周期 (3) EX 執(zhí)行/地址計(jì)算周期 做4種操作之一：存儲(chǔ)器地址計(jì)算、寄存器/寄存器ALU運(yùn)算、寄存器/立即數(shù)ALU運(yùn)算、分支地址計(jì)算與條件判斷。 (4) MEM 存儲(chǔ)器訪問/分支完成周期（ALU指令不需要）（后來稱DM） 做2種操作之一：存儲(chǔ)器訪問、根據(jù)分支條件對(duì)PC賦值。 (5) WB 寫回寄存器周期（分支指令不需要） 做2種操作之一：ALU結(jié)果寫寄存器、LOAD結(jié)果寫寄存器。 總周期數(shù) = n CPI（ALU和分支指令的CPI=4，其它指令的CPI=5）,3.4.1 用順序方式實(shí)現(xiàn)RISC詳解,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),5,按流水方式運(yùn)行需要解決的問題： 存儲(chǔ)周期每個(gè)時(shí)鐘周期都至少訪問一次存儲(chǔ)器，所以存儲(chǔ)器件的訪問周期必須縮短為順序方式的1/5（流水線必須配用高速存儲(chǔ)系統(tǒng)）。 沖突前面指令在MEM修改PC與后面指令在IF做PC+4發(fā)生PC沖突； 前面指令在MEM訪存與后面指令在IF取指發(fā)生存儲(chǔ)器沖突； 前面指令在WB寫寄存器與后面指令在ID讀寄存器發(fā)生寄存器沖突。（下頁圖） 對(duì)策用多路器選擇PC+4送PC，還是ALUout送PC；IF改成訪問指令存儲(chǔ)器IM，MEM改成訪問數(shù)據(jù)存儲(chǔ)器DM，以避免存儲(chǔ)器沖突；或者雖共用一個(gè)存儲(chǔ)器，但是分別連到指令Cache、數(shù)據(jù)Cache； 寄存器沖突留待下文解決。 寄存器文件每條指令啟動(dòng)后就被分配一組暫存器，稱為“寄存器文件”，用以保存自己的臨時(shí)數(shù)據(jù)，如NPC、IR等，它們伴隨指令逐段推進(jìn)，直至指令結(jié)束。在沒有操作的段，寄存器文件被直接拷貝到下一段。（P119） 總周期數(shù) = n + m 1 + stall總數(shù)（無相關(guān)、無沖突情況下）,3.5 基本的MIPS流水線（P87）,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),6,(1)3種沖突,流水方式運(yùn)行帶來的結(jié)構(gòu)沖突,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令K+1,譯碼 取數(shù),訪存 送PC,寫回,(2)存儲(chǔ)器哈佛結(jié)構(gòu)、分離Cache結(jié)構(gòu),CPU,指令K+3,指令K,IF,ID,EX,Mem,WB,指令K+2,IF,ID,EX,Mem,WB,指令K+3,取指 PC+4,指令存儲(chǔ)器,數(shù)據(jù)存儲(chǔ)器,CPU,指令Cache,數(shù)據(jù)Cache,內(nèi)存,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),7,3.5.1 MIPS的一種簡單實(shí)現(xiàn),2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),8,3.4.2 相關(guān)與沖突(P72),相關(guān)dependence ：一條指令依賴另一條指令的結(jié)果。 沖突hazard ：由于相關(guān)或其它原因，一條指令暫時(shí)停下來等待另一條指令執(zhí)行，不然就會(huì)產(chǎn)生錯(cuò)誤的結(jié)果（與程序員預(yù)期的不一致）。 相關(guān)的分類 1. 數(shù)據(jù)相關(guān)：前面指令的結(jié)果作為后面指令的操作數(shù)（真數(shù)據(jù)相關(guān)） 2. 名相關(guān)：兩條指令使用了同一個(gè)寄存器或存儲(chǔ)單元，并非要傳送數(shù)據(jù) 3. 控制相關(guān)：分支指令等改變PC值的情況 反相關(guān) 名相關(guān) 輸出相關(guān) 沖突的分類 1. 結(jié)構(gòu)沖突：即資源爭用 寫后讀：RAW 2. 數(shù)據(jù)沖突：由數(shù)據(jù)相關(guān)、或者名相關(guān)造成 寫后寫：WAW 3. 控制沖突：由控制相關(guān)造成 讀后寫：WAR 實(shí)例：P73P83；多種相關(guān)、沖突演示程序Lesson-5.s,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),9,3種相關(guān)與3種沖突的關(guān)系,?,數(shù)據(jù)相關(guān),名相關(guān),控制相關(guān),3種相關(guān),結(jié)構(gòu)沖突,數(shù)據(jù)沖突,控制沖突,3種沖突,原因,結(jié)果,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),10,沖突的通用處理方法暫停,沖突的通用處理方法：為了不出現(xiàn)錯(cuò)誤結(jié)果，相關(guān)檢測(cè)硬件會(huì)自動(dòng)插入所需個(gè)數(shù)的暫停周期stall（又稱為“流水線氣泡”），圖3.21和圖3.22是等效的表示法，后者比較緊湊； MIPS流水線的暫停：在ID段之后分支，在MEM段之前匯合。 如果一條指令在非分支的IF、ID、MEM、WB段暫停，它后面的指令只能順序流動(dòng)；如果一條指令在任一分支內(nèi)暫停，它后面的其它種類指令可以亂序流動(dòng)（繞過它先流向出口）。 MIPS暫停演示程序Lesson-5.s： dmul r1,r2,r3 dmul r4,r5,r1 sub.d f1,f2,f3,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),11,1. 結(jié)構(gòu)沖突特異處理方法（P75）,“設(shè)備重復(fù)”方法，又稱“完全流水化功能單元”方法：即為不同指令的同一操作分別設(shè)置獨(dú)立的設(shè)備。比如 IF 段訪問指令存儲(chǔ)器，MEM 段訪問數(shù)據(jù)存儲(chǔ)器（見課件P108）。 這種方法需要顯著增加成本，對(duì)經(jīng)常發(fā)生的沖突類型值得采用。而不常發(fā)生的結(jié)構(gòu)相關(guān)，因?yàn)閷?dǎo)致的程序平均執(zhí)行時(shí)間增加并不多，可以放任不管，見下頁例子。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),12,例3.5（不用“完全流水化功能單元”的例子，2版教材）,已知DLX處理機(jī)（MIPS的前身）中其它指令的 CPI = 1，浮點(diǎn)乘法指令的 CPI = 7，因?yàn)榉橇魉母↑c(diǎn)乘法部件用時(shí) 7 拍。如果下一條指令也要使用浮點(diǎn)乘法部件，則必須比上一條指令推遲7 拍啟動(dòng)，除非增加一個(gè)浮點(diǎn)乘法部件。在mdljdp2基準(zhǔn)測(cè)試程序中，浮點(diǎn)乘法指令出現(xiàn)的概率為14%，試分析不采用“完全流水化功能單元” 方法帶來的 CPI 增量。 分析： 不采用“完全流水化功能單元” 方法，即系統(tǒng)中只有一個(gè)浮點(diǎn)乘法部件，那么當(dāng)浮點(diǎn)乘法指令的下一條指令不是浮點(diǎn)乘法指令時(shí) CPI 仍為 1（應(yīng)為2，林老師注），當(dāng)下一條指令是浮點(diǎn)乘法指令時(shí) CPI 增大到 7。最壞情況是這14%的浮點(diǎn)乘法指令連續(xù)出現(xiàn)，那么整個(gè)程序的平均 CPI 將增加 14% 6 = 0.84拍。 該教材說當(dāng)浮點(diǎn)乘法指令服從均勻分布時(shí)，采用“完全流水化功能單元” 獲得的好處可能很少，原因是實(shí)際 CPI 的增量比0.84小得多（見下頁例3.5 的進(jìn)一步推導(dǎo)”）。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),13,例3.5 的進(jìn)一步推導(dǎo),記：浮點(diǎn)乘法指令的出現(xiàn)概率，= 14%； 由于浮點(diǎn)乘法指令出現(xiàn)導(dǎo)致的平均 CPI 增量（節(jié)拍數(shù)）；n 指令總數(shù)。 分析：1條單獨(dú)出現(xiàn)的概率為1（1-），對(duì)應(yīng)的= 0；2條連續(xù)出現(xiàn)的概率為2（1-），對(duì)應(yīng)的= 4；k條連續(xù)出現(xiàn)的概率為k（1-），對(duì)應(yīng)的= 4（k-1）；n+1條連續(xù)出現(xiàn)的概率為0。 的期望值：/= 2（1-）41 + 3（1-）42 + + n（1-）4（n-1） = 4（1-）12 + 23 + +（n-1）n = 42（1-n -1）/（1-）-（n-1）n+1 當(dāng)n時(shí)，/ 42 /（1-）0.09拍,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),14,2. 數(shù)據(jù)沖突特異處理方法（P76）,(1) 實(shí)例見圖3.23 (2) 相關(guān)指令彼此間隔大于一定距離就不會(huì)出錯(cuò)（P77第1段，XOR） (3) 把時(shí)鐘分成前、后半段的方法可以解決寄存器相關(guān)（P77第1段，OR） (4) 定向技術(shù)（forwarding）可以達(dá)到提前1.5拍寫、推遲0.5拍讀的效果，消除2拍以內(nèi)的相關(guān)出錯(cuò)（實(shí)際有效范圍因指令而異，見下圖） (5) 通過編譯軟件的指令調(diào)度處理，可以達(dá)到(2)的目的，而不用增加“空操作”指令或者硬件“氣泡”（P79第5行實(shí)例分析）。,前半拍完成寫寄存器,后半拍完成讀寄存器,ALU出口定向路徑,定向路徑ALU入口,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),15,定向路徑（相關(guān)專用通路）,寄存器文件,寄存器文件,寄存器文件,寄存器文件,通過定向路徑復(fù)制寄存器文件,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),16,采用定向技術(shù)后消除停頓的情形,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),17,采用定向技術(shù)后減少停頓的情形,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),18,數(shù)據(jù)沖突的分類（P76）,(1) 寫-讀沖突，當(dāng)后一條指令I(lǐng)D先于前一條指令WB時(shí)發(fā)生，最常見； (2) 寫-寫沖突，當(dāng)后一條指令WB先于前一條指令WB時(shí)發(fā)生，亂序流動(dòng)下會(huì)出現(xiàn)； (3) 讀-寫沖突，當(dāng)后一條指令WB先于前一條指令I(lǐng)D時(shí)發(fā)生。RISC機(jī)器不會(huì)出現(xiàn)，因?yàn)榱魉€在ID之前沒有分支。 數(shù)據(jù)沖突的自動(dòng)檢測(cè)與氣泡的自動(dòng)生成： 通過“流水線互鎖”（pipeline interlock）機(jī)構(gòu)來實(shí)現(xiàn)，閱讀P79第1段， P89第2段，詳見2版P96；可以檢測(cè)到的各種數(shù)據(jù)沖突列表，見2版P96表3.3。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),19,3. 控制沖突特異處理方法（P79）,重要性（P80）：每個(gè)條件分支指令帶來3個(gè)暫停周期，30%時(shí)減速一半。 方法： (1) “凍結(jié)”（freeze）或“排空”（flush）：消極暫停 (2) 提早完成分支操作，把3個(gè)暫停周期縮短為1個(gè)。需要做兩件事： 盡早判斷是否成功（將測(cè)試操作提早到ID段）； 盡早算出目標(biāo)地址（將地址計(jì)算提早到ID段）。 改進(jìn)前 改進(jìn)后,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),20,3. 控制沖突特異處理方法（P79）續(xù),(3) 通過預(yù)測(cè)提前啟動(dòng)分支后面的指令 “預(yù)測(cè)分支失敗”：猜失敗，提前取指令i+1； “預(yù)測(cè)分支成功”：猜成功，需要計(jì)算目標(biāo)地址，而RISC流水線的地址計(jì)算與判跳操作是同時(shí)完成的，故此舉無益； (4) “延遲分支”（delayed branch）：調(diào)若干指令在若干“延遲槽”中執(zhí)行， 調(diào)分支前的指令（最佳方案）； 調(diào)跳轉(zhuǎn)目標(biāo)處指令（猜成功，猜錯(cuò)需作廢）； 調(diào)后續(xù)指令（猜失敗，猜錯(cuò)需作廢）。 (5) “取消”（canceling）或“作廢”（nullifying）分支：對(duì)“分支延遲槽”的處理技術(shù)。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),21,改進(jìn)后的MIPS流水線（P90）,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),22,改進(jìn)流水線上使用定向技術(shù)的延遲時(shí)間,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),23,各種處理控制沖突方法的性能公式（2版P104）,(1) 控制沖突（即分支）導(dǎo)致的最大加速比Smax下降 在定義流水線“效率”指標(biāo)時(shí)推導(dǎo)過一個(gè)公式：Smax=Em，意思是說當(dāng)效率達(dá)到100%時(shí)，流水方式（每個(gè)t完成一個(gè)任務(wù)）吞吐率為順序方式（每m個(gè)t完成一個(gè)任務(wù)）的m倍。此處把m改寫為D。 考慮分支損失的流水線最大加速比公式： Smax=Em / (1 + f P分支)，其中f是分支指令的出現(xiàn)概率，P分支是平均分支損失（暫停周期數(shù)）。 其實(shí)這個(gè)公式可以用來計(jì)算任何一種沖突對(duì)應(yīng)的最大加速比Smax 。 對(duì)MIPS來說，無任何沖突情況下“效率” E=100%。 (2) 采用每種處理方法減少分支損失的效果 假定沒有分支損失情況下，理想CPI = 1。 可以算出存在分支損失情況下，不處理或單一處理方法對(duì)應(yīng)的平均分支損失值、延長的CPI值。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),24,各種沖突處理方法小結(jié)（同學(xué)們自己做）,結(jié)構(gòu)沖突： 數(shù)據(jù)沖突： (1) (2) (3) 控制沖突： (1) (2) (3) 作業(yè)3.11題修改： 開頭添加：在圖3.33所示MIPS流水線上,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),25,實(shí)驗(yàn)2MIPS流水線部件與指令周期,實(shí)驗(yàn)要求： 在人工完成習(xí)題3.11之后，在WinMIPS64模擬器上運(yùn)行對(duì)應(yīng)的程序，分別按(1)(2)(3)小問的條件設(shè)置模擬器的運(yùn)行模式，記錄相應(yīng)的時(shí)鐘周期數(shù)。 實(shí)驗(yàn)報(bào)告： (1) 程序清單； (2) 程序時(shí)間對(duì)比 (3) 人工計(jì)算值與實(shí)測(cè)值的差異原因分析，如果有差異的話； (4) 至少1段自己認(rèn)為有價(jià)值的“時(shí)鐘周期圖”片段抄錄或者打印，加注釋。,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),26,各次作業(yè)應(yīng)交的內(nèi)容,作業(yè)5（第5次課）,3.11(改)，實(shí)驗(yàn)2,