計算機系統結構第四章習題解答

《計算機系統結構第四章習題解答》由會員分享，可在線閱讀，更多相關《計算機系統結構第四章習題解答（20頁珍藏版）》請在裝配圖網上搜索。

1、.1. 假設一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時間分別是t、2t和3t。在下列各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時間表達式。順序執(zhí)行方式。僅“取指令”和“執(zhí)行”重疊。“取指令”、“分析”和“執(zhí)行”重疊。答：順序執(zhí)行方式t2t3t12.1212Tn(t2t3t)6nt僅“取指令”和“執(zhí)行”重疊t2t3t12.1212T6t6t(n-1)(2t3t)(5n1)t“取指令”、“分析”和“執(zhí)行”重疊精品.t2t3t1234.12341234T6t6t(n-1)(3t)(3n3)t2. 一條線性流水線有4個功能段組成，每個功能段的延遲時間都相等，都為t。開始5個

2、任務，每間隔一個t向流水線輸入一個任務，然后停頓2個t，如此重復。求流水線的實際吞吐率、加速比和效率。答：123456789101112131415.1234567891011121314151234567891011121314151234567891011121314151234567891011121314151617181920212223我們可以看出，在（7n+1）t的時間內，可以輸出5n個結果，如果指令的序列足夠長（n），并且指令間不存在相關，那么，吞吐率可以認為滿足：加速比為：精品.從上面的時空圖很容易看出，效率為：3. 用一條5個功能段的浮點加法器流水線計算。每個功能段的延遲時

3、間均相等，流水線的輸出端與輸入端之間有直接數據通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率。答：首先需要考慮的是“10個數的和最少需要做幾次加法？”，我們可以發(fā)現，加法的次數是不能減少的：9次；于是我們要盡可能快的完成任務，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關。由于加法滿足交換律和結合律，我們可以調整運算次序如以下的指令序列，我們把中間結果寄存器稱為R，源操作數寄存器稱為A，最后結果寄存器稱為F，并假設源操作數已經在寄存器中，則指令如下：I1：R1A1+A2I2：R2A3+A4I3：R3A5+A

4、6I4：R4A7+A8I5：R5A9+A10I6：R6R1+R2I7：R7R3+R4I8：R8R5+R6精品.I9：FR7+R8這并不是唯一可能的計算方法。假設功能段的延遲為t。時空圖如下（圖中的數字是指令號）：123456789123456789123456789123456789123456789123456789101112131415161718192021整個計算過程需要21t，所以吞吐率為：加速比為：效率為：4. 一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個功能段的延遲時間均相等。流水線的輸出端與輸入

5、端之間有直接數據通路，而且設置有足夠的緩沖寄存器。用這條流水線計算向量點積，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率。精品.答：我們安排運算次序如下：把中間結果寄存器稱為R，源操作數寄存器稱為A、B，最后結果寄存器稱為F，并假設源操作數已經在寄存器中，則指令如下：I1：R0A0*B0I8：R7R0+R1I2：R1A1*B1I9：R8R2+R3I3：R2A2*B2I10：R9R4+R5I4：R3A3*B3I11：R10R6+R7I5：R4A4*B4I12：R11R8+R9I6：R5A5*B5I13：FR10+R11I7：R6A6*B6假設功能段的延遲為t。時空圖如下（圖中的數字是指

6、令號）：12345678910111213123456712345678910111213891011121312345678910111213123456789101112131415161718192021222324整個計算過程需要24t，所以吞吐率為：精品.加速比為：效率為：5. 一條有三個功能段的流水線如下圖。每個功能段的延遲時間均相等，都為t。其中功能段S2的輸出要返回到它自己的輸入端循環(huán)一次。輸出輸入S3S2S1ttt如果每間隔一個t向流水線的輸入端連續(xù)輸入新任務，問這條流水線會發(fā)生什么情況？求這條流水線能夠正常工作的最大吞吐率、加速比和效率。有什么辦法能夠提高這條流水線的吞吐率

7、，畫出新的流水線。答：如果每間隔一個t向流水線的輸入端連續(xù)輸入新任務，流水線S2功能段存在資源沖突。見下表：時間功能段t1t2t3t4t5S1X1X2X3X4X5S2X1X1,X2X2,X3X3,X4S3X1X2精品.每間隔兩個t向流水線的輸入端連續(xù)輸入新任務（如見下表所示）可獲得最佳性能。時間功能段t1t2t3t4t5t6S1X1X2X3S2X1X1X2X2X3S3X1X2我們可以看出：在（2n+2）t的時間內，可以輸出n個結果，如果指令的序列足夠長（n），并且指令間不存在相關，那么，吞吐率為：加速比為：效率為：如要提高這條流水線的吞吐率，可采用：將功能段S2重復設置一次，見下圖：輸出S3t

8、tt輸入S2S2S1t6. 一條有4個功能段的非線性流水線，每個功能段的延遲時間都相等，都為20ns，它的預約表如下：精品.時間流水段1234567S1××S2××S3×S4×× 寫出流水線的禁止向量和初始沖突向量。 畫出調度流水線的狀態(tài)圖。 求流水線的最小啟動循環(huán)和最小平均啟動距離。 求平均啟動距離最小的恒定循環(huán)。 求流水線的最大吞吐率。 按照最小啟動循環(huán)連續(xù)輸入10個任務，求流水線的實際吞吐率。 畫出該流水線各功能段之間的連接圖。答： 禁止向量F=（6,4,2）；沖突向量C=（101010）。 i=1i7i=3i7i=5

9、i=3i7i=5i=5i7101010111111101111101011C0C1C2C3精品. 簡單循環(huán)平均啟動距離1，7（C0-C1-C0）43，7（C0-C2-C0）55，7（C0-C3-C0）63，5，7（C0-C2-C3-C0）53，5（C0-C2-C3-C2-C3）45，3，7（C0-C3-C2-C0）55，3（C0-C3-C2-C3-C2）45（C0-C3-C3）57（C0-C0）7 流水線的最小啟動循環(huán)為：（1，7）或（3，5）或（5，3），最小平均啟動距離為4。 由上表可知：平均啟動距離最小的恒定循環(huán)為（5）。 采用最小平均啟動距離為4的最小啟動循環(huán)可獲得流水線的最大吞吐率，

10、以（1，7）為例：（其他類似，最大吞吐率皆相同）當任務數為偶數2n時：當任務數為奇數2n+1時：精品. 流水線的最大吞吐率為： 10個任務的實際吞吐率：利用上式可得（偶數個任務）TP10=1/4t=12.5M(任務/s)。 該流水線的連接圖為：S1S2S3S41234567輸入輸出7. 一條由4個功能段組成的非線性流水線的預約表如下，每個功能段的延遲時間都為10ns。時間流水段123456S1××S2××S3×S4××寫出流水線的禁止向量和初始沖突向量。畫出調度流水線的狀態(tài)圖。求流水線的最小啟動循環(huán)和最小平均啟動距離。精品.

11、在流水線中插入一個非計算延遲功能段后，求該流水線的最佳啟動循環(huán)及其最小平均啟動距離。畫出插入一個非計算延遲功能段后的流水線預約表（5行8列）。畫出插入一個非計算延遲功能段后的流水線狀態(tài)變換圖。分別計算在插入一個非計算延遲功能段前、后的最大吞吐率。如果連續(xù)輸入10個任務，分別計算在插入一個非計算延遲功能段前、后的實際吞吐率。答：禁止向量F=（5,2,1）；沖突向量C=（10011）。10011i=3i=4C0i6簡單循環(huán)平均啟動距離334466最小啟動循環(huán)為（3），最小平均啟動距離為3。插入一個非計算延遲功能段后，最小平均啟動距離為2（因為預約表中每行至多2個×），相應地可改進最小啟動

12、循環(huán)為（2）。精品.時間功能段12345678S1XXS2XXS3XS4XXDXX流水線的禁止向量為（1，3，7），流水線的沖突向量為1000101，流水線的狀態(tài)圖如下：100010110101011000111i=4,6i8i=4,6i8i=4,6i8i=2i=2i=5C0C1C2i=5簡單循環(huán)平均啟動距離2，4(C0-C1)32，6(C0-C1)42(C0-C1-C1)24(C0-C0)46(C0-C0)6精品.5(C0-C2-C2)55，4(C0-C2)4.55，6(C0-C2)5.5流水線的最小啟動循環(huán)為（2），最小平均啟動距離為2。插入前：插入后：連續(xù)輸入10個任務，插入前的實際吞吐

13、率為：連續(xù)輸入10個任務，插入后的實際吞吐率為：8. 在流水線處理機中，有獨立的加法操作部件和乘法操作部件各一個，加法操作部件為4段流水線，乘法操作部件6段流水線，都在第一段從通用寄存器讀操作數，在最后一段把運算結果寫到通用寄存器中。每段的時間長度都相等，都是一個時鐘周期。每個時鐘周期發(fā)出一條指令。問可能發(fā)生哪幾種數據相關?寫出發(fā)生相關的指令序列，分析相關發(fā)生的原因，并給出解決相關的具體辦法。精品.答：可能的數據相關性有：“先寫后讀”（RAW）相關Ø Read After 加法寫。原因：還沒有寫好就已經讀取寄存器中的數據了。DADD R1,R2,R3；（R2）（R3）（R1）DSUB

14、 R4,R1,R5；（R1）（R5）（R4）Ø Read After 乘法寫。原因：還沒有寫好已經讀取寄存器中的數據了。DMUL R1,R2,R3；（R2）×（R3）（R1）DSUB R4,R1,R5；（R1）（R5）（R4）本相關在流水線順序執(zhí)行和亂序執(zhí)行時都可能發(fā)生。解決的方法是：利用編譯程序調整指令的次序方法；延遲執(zhí)行是避免數據相關最簡單的方法；建立寄存器之間的專用路徑。 “寫寫”（WAW）相關Write After 乘法寫。原因：后寫的反而早執(zhí)行（乘法所化的時間長，后面一個寫任務反而先完成），使最后寫入的內容不正確。DMUL R1,R2,R3；（R2）×（

15、R3）（R1）DSUB R1,R4,R5；（R4）（R5）（R1）本相關只有在流水線亂序執(zhí)行時才可能發(fā)生。解決的方法是：寄存器換名。 “先讀后寫”（WAR）相關Write After 任何讀。原因：前面的讀操作因為某種原因被推遲，要讀的內容被后面的寫操作修改了。精品.DSUB R4,R1,R5；（R1）（R5）（R4）DADD R1,R2,R3；（R2）（R3）（R1）本相關只有在流水線亂序執(zhí)行時才可能發(fā)生。解決的方法是：寄存器換名。9. 在下列不同結構的處理機上運行8×8的矩陣乘法C=A×B，計算所需要的最短時間。只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數、數據傳

16、送和程序控制等指令的執(zhí)行時間。加法部件和乘法部件的延遲時間都是3個時鐘周期，另外，加法指令和乘法指令還要經過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為“0”。各操作部件的輸出端有直接數據通路連接到有關操作部件的輸入端，在操作部件的輸出端設置有足夠容量的緩沖寄存器。處理機內只有一個通用操作部件，采用順序方式執(zhí)行指令。單流水線標量處理機，有一條兩個功能的靜態(tài)流水線，流水線每個功能段的延遲時間均為一個時鐘周期，加法操作和乘法操作各經過3個功能段。多操作部件處理機，處理機內有獨立的乘法部件和加法部件，兩個操作部件可以并行工作。只有一個指令流水線，操作部件不采用流水線結

17、構。單流水線標量處理機，處理機內有兩條獨立的操作流水線，流水線每個功能段的延遲時間均為一個時鐘周期。超標量處理機，每個時鐘周期同時發(fā)射一條乘法指令和一條加法指令，處理機內有兩條獨立的操作流水線，流水線的每個功能段的延遲時間均為一個時鐘周期。精品.超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件的延遲時間都為6個流水級，每個時鐘周期能夠分時發(fā)射兩條指令，即每個流水級能夠發(fā)射一條指令。超標量超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件延遲時間都為6個流水級，每個流水級能夠同時發(fā)射一條乘法指令和一條加法指令。答：要完成上面的矩陣乘法，需要完成的乘法數目為8

18、5;8×8=512次；需要完成的加法數目為8×8×7=448次；下面分析處理機的結構會給性能帶來什么樣的影響。通用操作部件采用順序方式執(zhí)行順序執(zhí)行時，每個乘法和加法指令都需要5個時鐘周期（取指令、指令分析、指令執(zhí)行）；所以所需要的時間為：單流水線標量處理機，有一條兩個功能的靜態(tài)流水線因為有足夠的緩沖寄存器，所以我們可以首先把所有的乘法計算完，并通過調度使加法流水線不出現停頓，所以所需要的時間為：加法加31234加21234加11234乘法乘3乘2精品.乘1譯碼1234取指1234123456785135145155165175189639649659661=+、2

19、=1+、3=2+、4=3+、5=4+、6=5+、7=6+多操作部件處理機，只有一條指令流水線由于只有一條指令流水線，所以只能一個時鐘周期發(fā)射一條指令；由于操作部件不采用流水線，對于結果C矩陣的第一個元素，首先執(zhí)行2次乘法，然后乘法和加法并行執(zhí)行7次，此時C矩陣的第一個元素出來了，然后加法運算停頓3個時鐘周期，再開始與乘法并行執(zhí)行運算7次，如此下去，直到C的64個元素都出來。故執(zhí)行時間為：單流水線標量處理機，處理機內有兩條獨立的操作流水線由于只有一條指令流水線，所以只能一個時鐘周期發(fā)射一條指令；對于乘法運算不存在數據相關，對于加法運算有數據相關，由于存在足夠的緩沖寄存器，我們可以通過合適的調度消

20、除加法的數據相關。因此，最佳情況下的執(zhí)行時間為：加法加31234567加21234567加11234567乘法乘3精品.乘2乘1譯碼1234567取指1234567123456789101112131415161718192021221=+、2=1+、3=2+、4=3+、5=4+、6=5+、7=6+超標量處理機同一時鐘周期可以有一條乘法指令和一條加法指令同時發(fā)射，對于乘法運算不存在數據相關性，對于加法運算有數據相關性，由于存在足夠的緩沖寄存器，當運算完所有的乘法運算后，還要做一次加法運算。因此執(zhí)行時間為：加法加3123456712345加2123456712345加1123456712345譯碼123456712345取指123456712345乘法乘3乘2乘1譯碼取指12345678910111213141516171819202122精品.1=+、2=1+、3=2+、4=3+、5=4+、6=5+、7=6+超流水線處理機每個時鐘周期發(fā)射兩條指令，加法部件和乘法部件都為6個流水級。事實上相當于將時鐘周期變成了10ns，而加法和乘法流水線變成了6級。因此執(zhí)行時間為：超標量超流水線處理機一個時鐘周期分為兩個流水級，加法部件和乘法部件都為6個流水級，每個流水級能同時發(fā)射一條加法和一條乘法指令。綜合和的分析，我們可以知道，執(zhí)行時間為：如有侵權請聯系告知刪除，感謝你們的配合！精品