計(jì)算機(jī)體系結(jié)構(gòu)第二章練習(xí)題參考解答(共4頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第 二 章 2.13 在一臺(tái)單流水線多操作部件的處理機(jī)上執(zhí)行下面的程序，每條指令的取指令、指令譯碼需要一個(gè)時(shí)鐘周期，MOVE、ADD和MUL操作分別需要2個(gè)、3個(gè)和4個(gè)時(shí)鐘周期，每個(gè)操作都在第一個(gè)時(shí)鐘周期從通用寄存器中讀操作數(shù)，在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫(xiě)到通用寄存器中。k： MOVE R1，R0 ；R1 (R0)k+1： MUL R0，R2，R1 ；R0 (R2)×(R1)k+2： ADD R0，R2，R3 ；R0 (R2)+(R3)(1)就程序本身而言，可能有哪幾種數(shù)據(jù)相關(guān)?(2)在程序?qū)嶋H執(zhí)行過(guò)程中，哪幾種數(shù)據(jù)相關(guān)會(huì)引起流水線停頓?(3)畫(huà)出指令執(zhí)行

2、過(guò)程的流水線時(shí)空?qǐng)D，并計(jì)算完成這3條指令共需要多少個(gè)時(shí)鐘周期？解：（1）就程序本身而言，可能有三種數(shù)據(jù)相關(guān)。若3條指令順序流動(dòng)，則k指令對(duì)R1寄存器的寫(xiě)與k+1指令對(duì)R1寄存器的讀形成的“先寫(xiě)后讀”相關(guān)。若3條指令異步流動(dòng)，則k指令對(duì)R0寄存器的讀與k+1指令對(duì)R0寄存器的寫(xiě)形成的“先讀后寫(xiě)”相關(guān)，k+2指令對(duì)R0寄存器的寫(xiě)與k+1指令對(duì)R0寄存器的寫(xiě)形成的“寫(xiě)寫(xiě)”相關(guān)。（2）在程序?qū)嶋H執(zhí)行過(guò)程中，二種數(shù)據(jù)相關(guān)會(huì)引起流水線停頓。一是“先寫(xiě)后讀”相關(guān)，k指令對(duì)R1的寫(xiě)在程序執(zhí)行開(kāi)始后的第四個(gè)時(shí)鐘；k+1指令對(duì)R1的讀對(duì)指令本身是第三個(gè)時(shí)鐘，但k+1指令比k指令晚一個(gè)時(shí)鐘進(jìn)入流水線，則在程序執(zhí)行開(kāi)

3、始后的第四個(gè)時(shí)鐘要讀R1。不能在同一時(shí)鐘周期內(nèi)讀寫(xiě)同一寄存器，因此k+1指令應(yīng)推遲一個(gè)時(shí)鐘進(jìn)入流水線，產(chǎn)生了流水線停頓。二是“寫(xiě)寫(xiě)”相關(guān)，k+1指令對(duì)R0的寫(xiě)對(duì)指令本身是第六個(gè)時(shí)鐘，而要求該指令進(jìn)入流水線應(yīng)在程序執(zhí)行開(kāi)始后的第三個(gè)時(shí)鐘，所以對(duì)R0的寫(xiě)是在程序執(zhí)行開(kāi)始后的第八個(gè)時(shí)鐘。k+2指令對(duì)R0的寫(xiě)對(duì)指令本身是第五個(gè)時(shí)鐘，而k+2指令比k+1指令晚一個(gè)時(shí)鐘進(jìn)入流水線，則在程序執(zhí)行開(kāi)始后的第四個(gè)時(shí)鐘，所以對(duì)R0的寫(xiě)是在程序執(zhí)行開(kāi)始后的第八個(gè)時(shí)鐘。不能在同一時(shí)鐘周期內(nèi)寫(xiě)寫(xiě)同一寄存器，因此k+2指令應(yīng)推遲一個(gè)時(shí)鐘進(jìn)入流水線，產(chǎn)生了流水線停頓。另外，可分析“先讀后寫(xiě)”相關(guān)不會(huì)產(chǎn)生流水線的停頓。 （3

4、）由題意可認(rèn)位該指令流水線由六個(gè)功能段取指、譯碼、取數(shù)、運(yùn)一、運(yùn)二和存數(shù)等組成，則程序指令執(zhí)行過(guò)程的流水線時(shí)空?qǐng)D如下圖所示。若3條指令順序流動(dòng)，共需要9個(gè)時(shí)鐘周期。 空間存數(shù) K存數(shù) K+1存數(shù) K+2存數(shù) 運(yùn)二 K+1運(yùn)二 運(yùn)一 K+1運(yùn)一 K+2運(yùn)一 取數(shù) K取數(shù) K+1取數(shù) K+2取數(shù) 譯碼 K譯碼 K+1譯碼 K+2譯碼 取指 K取指 K+1取指 K+2取指 時(shí)間 0 1 2 3 4 5 6 7 8 92.23 有一條5個(gè)功能段的線性動(dòng)態(tài)多功能流水線如圖所示，其中1235功能段組成加法流水線，145功能段組成乘法流水線，設(shè)每個(gè)功能段的延遲時(shí)間均相等為t。用這條流水線計(jì)算F=，畫(huà)出流水線

5、時(shí)空?qǐng)D，并計(jì)算流水線的實(shí)際吞吐率、加速比和效率。S1S2S3S5S4XYZ解：由于該流水線為動(dòng)態(tài)雙功能流水線，計(jì)算要求先加后乘，因此應(yīng)先設(shè)置加法功能，連續(xù)計(jì)算出（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四個(gè)加法后；再設(shè)置乘法功能，而且按(a1+b1)×(a2+b2)×(a3+b3)×(a4+b4)順序做3個(gè)乘法。因此可畫(huà)出該流水線的時(shí)空?qǐng)D如圖所示，圖中A=a1+b1，B=a2+b2，C=a3+b3，D=a4+b4?？臻gS5S4S3S2S11234三一二一二一二1234ABCDA·B C·D(A·B)×(C

6、·D) t7t13a1b1a2b2a3b3a4b4ABCDA·BC·D時(shí)間12341234三三由時(shí)空?qǐng)D可以看出，在總共12個(gè)t的時(shí)間內(nèi)輸出7個(gè)結(jié)果，所以有：TP = n/Tn = 7/12t而當(dāng)用串行方法完成操作時(shí)，需要四次加法和三次乘法，完成一次加法需要4t，完成一次乘法需要3t，完成該運(yùn)算總共需要時(shí)間為：T0 = 4×4t+3×3t = 25t所以 S = T0/Tn = 2.08E = 有效時(shí)空區(qū)面積/全部時(shí)空區(qū)面積 = (4×4t+3×3t)/(5×12t) = 0.422.24 有一條3個(gè)功能段的流水線如

7、下圖所示，每個(gè)功能段的延遲時(shí)間均為t，但是，功能段S2的輸出要返回到它自己的輸入端循環(huán)執(zhí)行一次。S1S2S3 輸入 輸出 t t t（1）如果每隔一個(gè)t向流水線連續(xù)輸入任務(wù)，這條流水線會(huì)發(fā)生什么問(wèn)題？（2）求這條流水線能夠正常工作的實(shí)際吞吐率、加速比和效率。 （3）可用什么辦法來(lái)提高流水線的吞吐率，畫(huà)出改進(jìn)后的流水線結(jié)構(gòu)。解：（1）每個(gè)任務(wù)在段S2要反饋循環(huán)一次，執(zhí)行時(shí)間為2t，其它各段的執(zhí)行時(shí)間為t，因此應(yīng)按瓶頸段的執(zhí)行時(shí)間2t流入任務(wù)，才不會(huì)發(fā)生沖突現(xiàn)象，否則會(huì)發(fā)生流水線的阻塞。 （2）若連續(xù)輸入n個(gè)任務(wù)，則流水線的實(shí)際吞吐率、加速比和效率分別為： TP = n/（4t +2（n1）t）=

8、 n/2（n + 1）t 1/2tS = 4nt/（4t +2（n1）t）= 2n/（n + 1）2 E = 4nt/3（4t +2（n1）t）= 2n/3（n + 1）2/3（3）為提高流水線的吞吐率，可重復(fù)設(shè)置段S2，并使兩個(gè)段S2串連在一起，從而消除瓶頸段S2，而且各段執(zhí)行時(shí)間相等為t，流水線的段數(shù)為4。流水線的結(jié)構(gòu)如下圖所示。S3S2S2S1 輸入 輸出 t t t t2.25 在一個(gè)5段的流水線處理機(jī)上需經(jīng)9t才能完成一個(gè)任務(wù)，其預(yù)約表為： 時(shí)間 1 2 3 4 5 6 7 8 9流水段S1 × ×S2 × × ×S3 ×S

9、4 × ×S5 × ×延遲D2 × （1）寫(xiě)出流水線的初始沖突向量。（2）畫(huà)出流水線任務(wù)調(diào)度的狀態(tài)有向圖。（3）求出流水線的最優(yōu)調(diào)度策略及最小平均延遲時(shí)間和流水線的最大吞吐率。（4）按最優(yōu)調(diào)度策略連續(xù)輸入8個(gè)任務(wù)時(shí)，流水線的實(shí)際吞吐率是多少? 解：（1）根據(jù)初始沖突向量的構(gòu)成方法，對(duì)預(yù)約表各行中打“×”的拍數(shù)求出差值，除去重復(fù)的后匯集在一起，即得到延遲禁止表為F =1，5，6，8。由F可得到初始沖突向量為： C =（） （2）根據(jù)后繼沖突向量的遞推規(guī)則Cj = SHR（k）（Ci）C0則可得出所有的后繼狀態(tài)，具體有： C0C0四個(gè)后繼

10、狀態(tài)：C1 =SHR（2）（C0）C0 = 7 C2 =SHR（3）（C0）C0 = C3 =SHR（4）（C0）C0 = 3 2C4 =SHR（7）（C0）C0 = =C0 7 4 7 C1 C2C1二個(gè)后繼狀態(tài)：C5 =SHR（2）（C1）C0 = C6 =SHR（7）（C1）C0 = =C0 7C2二個(gè)后繼狀態(tài)：C7 =SHR（4）（C2）C0 = =C3 3 4 7 2 C3 C5C8 =SHR（7）（C2）C0 = =C0C3二個(gè)后繼狀態(tài)：C9 =SHR（3）（C3）C0 = =C2C10=SHR（7）（C3）C0 = =C0C5一個(gè)后繼狀態(tài)：C11=SHR（7）（C5）C0 = =

11、C0 由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時(shí)間間隔可得到狀態(tài)有向圖如上圖所示。 （3）由狀態(tài)轉(zhuǎn)移有向圖可得到無(wú)沖突的任務(wù)調(diào)度策略及其平均延遲時(shí)間，如下表所示。調(diào)度策略 平均延遲時(shí)間 特別地，從C0出發(fā)的3，（4，3）也是一個(gè)（2，2，7） （2+2+7）t/3 = 3.67t 任務(wù)調(diào)度策略，除第一條有向弧外，第二、三條 （2，7） （2+7）t/2 = 4.5t 有向組成一個(gè)環(huán)路，該調(diào)度策略為（4，3）。從表 （3，4，7） （3+4+7）t/3 = 4.67t 中可以得到平均延遲時(shí)間最小的調(diào)度策略為（4， （3，7） （3+7）t/2 = 5t 3），該調(diào)度策略則為最優(yōu)調(diào)度策略，相應(yīng)的最?。?，3，7） （4+3+7）t/3 = 4.67t 平均延遲時(shí)間為3.5t，所以流水線的最大吞吐（