計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第四章習(xí)題解答

.1. 假設(shè)一條指令的執(zhí)行過(guò)程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時(shí)間分別是t、2t和3t。在下列各種情況下，分別寫(xiě)出連續(xù)執(zhí)行n條指令所需要的時(shí)間表達(dá)式。順序執(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個(gè)功能段組成，每個(gè)功能段的延遲時(shí)間都相等，都為t。開(kāi)始5個(gè)任務(wù)，每間隔一個(gè)t向流水線輸入一個(gè)任務(wù)，然后停頓2個(gè)t，如此重復(fù)。求流水線的實(shí)際吞吐率、加速比和效率。答：123456789101112131415.1234567891011121314151234567891011121314151234567891011121314151234567891011121314151617181920212223我們可以看出，在（7n+1）t的時(shí)間內(nèi)，可以輸出5n個(gè)結(jié)果，如果指令的序列足夠長(zhǎng)（n），并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿(mǎn)足：加速比為：精品.從上面的時(shí)空?qǐng)D很容易看出，效率為：3. 用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算。每個(gè)功能段的延遲時(shí)間均相等，流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時(shí)間完成計(jì)算，畫(huà)出流水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。答：首先需要考慮的是“10個(gè)數(shù)的和最少需要做幾次加法？”，我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：9次；于是我們要盡可能快的完成任務(wù)，就只有考慮如何讓流水線盡可能充滿(mǎn)，這需要消除前后指令之間的相關(guān)。由于加法滿(mǎn)足交換律和結(jié)合律，我們可以調(diào)整運(yùn)算次序如以下的指令序列，我們把中間結(jié)果寄存器稱(chēng)為R，源操作數(shù)寄存器稱(chēng)為A，最后結(jié)果寄存器稱(chēng)為F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下：I1：R1A1+A2I2：R2A3+A4I3：R3A5+A6I4：R4A7+A8I5：R5A9+A10I6：R6R1+R2I7：R7R3+R4I8：R8R5+R6精品.I9：FR7+R8這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為t。時(shí)空?qǐng)D如下（圖中的數(shù)字是指令號(hào)）：123456789123456789123456789123456789123456789123456789101112131415161718192021整個(gè)計(jì)算過(guò)程需要21t，所以吞吐率為：加速比為：效率為：4. 一條線性靜態(tài)多功能流水線由6個(gè)功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個(gè)功能段的延遲時(shí)間均相等。流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。用這條流水線計(jì)算向量點(diǎn)積，畫(huà)出流水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。精品.答：我們安排運(yùn)算次序如下：把中間結(jié)果寄存器稱(chēng)為R，源操作數(shù)寄存器稱(chēng)為A、B，最后結(jié)果寄存器稱(chēng)為F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下：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假設(shè)功能段的延遲為t。時(shí)空?qǐng)D如下（圖中的數(shù)字是指令號(hào)）：12345678910111213123456712345678910111213891011121312345678910111213123456789101112131415161718192021222324整個(gè)計(jì)算過(guò)程需要24t，所以吞吐率為：精品.加速比為：效率為：5. 一條有三個(gè)功能段的流水線如下圖。每個(gè)功能段的延遲時(shí)間均相等，都為t。其中功能段S2的輸出要返回到它自己的輸入端循環(huán)一次。輸出輸入S3S2S1ttt如果每間隔一個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)，問(wèn)這條流水線會(huì)發(fā)生什么情況？求這條流水線能夠正常工作的最大吞吐率、加速比和效率。有什么辦法能夠提高這條流水線的吞吐率，畫(huà)出新的流水線。答：如果每間隔一個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)，流水線S2功能段存在資源沖突。見(jiàn)下表：時(shí)間功能段t1t2t3t4t5S1X1X2X3X4X5S2X1X1,X2X2,X3X3,X4S3X1X2精品.每間隔兩個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)（如見(jiàn)下表所示）可獲得最佳性能。時(shí)間功能段t1t2t3t4t5t6S1X1X2X3S2X1X1X2X2X3S3X1X2我們可以看出：在（2n+2）t的時(shí)間內(nèi)，可以輸出n個(gè)結(jié)果，如果指令的序列足夠長(zhǎng)（n），并且指令間不存在相關(guān)，那么，吞吐率為：加速比為：效率為：如要提高這條流水線的吞吐率，可采用：將功能段S2重復(fù)設(shè)置一次，見(jiàn)下圖：輸出S3ttt輸入S2S2S1t6. 一條有4個(gè)功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等，都為20ns，它的預(yù)約表如下：精品.時(shí)間流水段1234567S1××S2××S3×S4×× 寫(xiě)出流水線的禁止向量和初始沖突向量。 畫(huà)出調(diào)度流水線的狀態(tài)圖。 求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 求平均啟動(dòng)距離最小的恒定循環(huán)。 求流水線的最大吞吐率。 按照最小啟動(dòng)循環(huán)連續(xù)輸入10個(gè)任務(wù)，求流水線的實(shí)際吞吐率。 畫(huà)出該流水線各功能段之間的連接圖。答： 禁止向量F=（6,4,2）；沖突向量C=（101010）。 i=1i7i=3i7i=5i=3i7i=5i=5i7101010111111101111101011C0C1C2C3精品. 簡(jiǎn)單循環(huán)平均啟動(dòng)距離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 流水線的最小啟動(dòng)循環(huán)為：（1，7）或（3，5）或（5，3），最小平均啟動(dòng)距離為4。 由上表可知：平均啟動(dòng)距離最小的恒定循環(huán)為（5）。 采用最小平均啟動(dòng)距離為4的最小啟動(dòng)循環(huán)可獲得流水線的最大吞吐率，以（1，7）為例：（其他類(lèi)似，最大吞吐率皆相同）當(dāng)任務(wù)數(shù)為偶數(shù)2n時(shí)：當(dāng)任務(wù)數(shù)為奇數(shù)2n+1時(shí)：精品. 流水線的最大吞吐率為： 10個(gè)任務(wù)的實(shí)際吞吐率：利用上式可得（偶數(shù)個(gè)任務(wù)）TP10=1/4t=12.5M(任務(wù)/s)。 該流水線的連接圖為：S1S2S3S41234567輸入輸出7. 一條由4個(gè)功能段組成的非線性流水線的預(yù)約表如下，每個(gè)功能段的延遲時(shí)間都為10ns。時(shí)間流水段123456S1××S2××S3×S4××寫(xiě)出流水線的禁止向量和初始沖突向量。畫(huà)出調(diào)度流水線的狀態(tài)圖。求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。精品.在流水線中插入一個(gè)非計(jì)算延遲功能段后，求該流水線的最佳啟動(dòng)循環(huán)及其最小平均啟動(dòng)距離。畫(huà)出插入一個(gè)非計(jì)算延遲功能段后的流水線預(yù)約表（5行8列）。畫(huà)出插入一個(gè)非計(jì)算延遲功能段后的流水線狀態(tài)變換圖。分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的最大吞吐率。如果連續(xù)輸入10個(gè)任務(wù)，分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的實(shí)際吞吐率。答：禁止向量F=（5,2,1）；沖突向量C=（10011）。10011i=3i=4C0i6簡(jiǎn)單循環(huán)平均啟動(dòng)距離334466最小啟動(dòng)循環(huán)為（3），最小平均啟動(dòng)距離為3。插入一個(gè)非計(jì)算延遲功能段后，最小平均啟動(dòng)距離為2（因?yàn)轭A(yù)約表中每行至多2個(gè)×），相應(yīng)地可改進(jìn)最小啟動(dòng)循環(huán)為（2）。精品.時(shí)間功能段12345678S1XXS2XXS3XS4XXDXX流水線的禁止向量為（1，3，7），流水線的沖突向量為1000101，流水線的狀態(tài)圖如下：100010110101011000111i=4,6i8i=4,6i8i=4,6i8i=2i=2i=5C0C1C2i=5簡(jiǎn)單循環(huán)平均啟動(dòng)距離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流水線的最小啟動(dòng)循環(huán)為（2），最小平均啟動(dòng)距離為2。插入前：插入后：連續(xù)輸入10個(gè)任務(wù)，插入前的實(shí)際吞吐率為：連續(xù)輸入10個(gè)任務(wù)，插入后的實(shí)際吞吐率為：8. 在流水線處理機(jī)中，有獨(dú)立的加法操作部件和乘法操作部件各一個(gè)，加法操作部件為4段流水線，乘法操作部件6段流水線，都在第一段從通用寄存器讀操作數(shù)，在最后一段把運(yùn)算結(jié)果寫(xiě)到通用寄存器中。每段的時(shí)間長(zhǎng)度都相等，都是一個(gè)時(shí)鐘周期。每個(gè)時(shí)鐘周期發(fā)出一條指令。問(wèn)可能發(fā)生哪幾種數(shù)據(jù)相關(guān)?寫(xiě)出發(fā)生相關(guān)的指令序列，分析相關(guān)發(fā)生的原因，并給出解決相關(guān)的具體辦法。精品.答：可能的數(shù)據(jù)相關(guān)性有：“先寫(xiě)后讀”（RAW）相關(guān)Ø Read After 加法寫(xiě)。原因：還沒(méi)有寫(xiě)好就已經(jīng)讀取寄存器中的數(shù)據(jù)了。DADD R1,R2,R3；（R2）（R3）（R1）DSUB R4,R1,R5；（R1）（R5）（R4）Ø Read After 乘法寫(xiě)。原因：還沒(méi)有寫(xiě)好已經(jīng)讀取寄存器中的數(shù)據(jù)了。DMUL R1,R2,R3；（R2）×（R3）（R1）DSUB R4,R1,R5；（R1）（R5）（R4）本相關(guān)在流水線順序執(zhí)行和亂序執(zhí)行時(shí)都可能發(fā)生。解決的方法是：利用編譯程序調(diào)整指令的次序方法；延遲執(zhí)行是避免數(shù)據(jù)相關(guān)最簡(jiǎn)單的方法；建立寄存器之間的專(zhuān)用路徑。 “寫(xiě)寫(xiě)”（WAW）相關(guān)Write After 乘法寫(xiě)。原因：后寫(xiě)的反而早執(zhí)行（乘法所化的時(shí)間長(zhǎng)，后面一個(gè)寫(xiě)任務(wù)反而先完成），使最后寫(xiě)入的內(nèi)容不正確。DMUL R1,R2,R3；（R2）×（R3）（R1）DSUB R1,R4,R5；（R4）（R5）（R1）本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。 “先讀后寫(xiě)”（WAR）相關(guān)Write After 任何讀。原因：前面的讀操作因?yàn)槟撤N原因被推遲，要讀的內(nèi)容被后面的寫(xiě)操作修改了。精品.DSUB R4,R1,R5；（R1）（R5）（R4）DADD R1,R2,R3；（R2）（R3）（R1）本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。9. 在下列不同結(jié)構(gòu)的處理機(jī)上運(yùn)行8×8的矩陣乘法C=A×B，計(jì)算所需要的最短時(shí)間。只計(jì)算乘法指令和加法指令的執(zhí)行時(shí)間，不計(jì)算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時(shí)間。加法部件和乘法部件的延遲時(shí)間都是3個(gè)時(shí)鐘周期，另外，加法指令和乘法指令還要經(jīng)過(guò)一個(gè)“取指令”和“指令譯碼”的時(shí)鐘周期，每個(gè)時(shí)鐘周期為20ns，C的初始值為“0”。各操作部件的輸出端有直接數(shù)據(jù)通路連接到有關(guān)操作部件的輸入端，在操作部件的輸出端設(shè)置有足夠容量的緩沖寄存器。處理機(jī)內(nèi)只有一個(gè)通用操作部件，采用順序方式執(zhí)行指令。單流水線標(biāo)量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線，流水線每個(gè)功能段的延遲時(shí)間均為一個(gè)時(shí)鐘周期，加法操作和乘法操作各經(jīng)過(guò)3個(gè)功能段。多操作部件處理機(jī)，處理機(jī)內(nèi)有獨(dú)立的乘法部件和加法部件，兩個(gè)操作部件可以并行工作。只有一個(gè)指令流水線，操作部件不采用流水線結(jié)構(gòu)。單流水線標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線每個(gè)功能段的延遲時(shí)間均為一個(gè)時(shí)鐘周期。超標(biāo)量處理機(jī)，每個(gè)時(shí)鐘周期同時(shí)發(fā)射一條乘法指令和一條加法指令，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線的每個(gè)功能段的延遲時(shí)間均為一個(gè)時(shí)鐘周期。精品.超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法部件的延遲時(shí)間都為6個(gè)流水級(jí)，每個(gè)時(shí)鐘周期能夠分時(shí)發(fā)射兩條指令，即每個(gè)流水級(jí)能夠發(fā)射一條指令。超標(biāo)量超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法部件延遲時(shí)間都為6個(gè)流水級(jí)，每個(gè)流水級(jí)能夠同時(shí)發(fā)射一條乘法指令和一條加法指令。答：要完成上面的矩陣乘法，需要完成的乘法數(shù)目為8×8×8=512次；需要完成的加法數(shù)目為8×8×7=448次；下面分析處理機(jī)的結(jié)構(gòu)會(huì)給性能帶來(lái)什么樣的影響。通用操作部件采用順序方式執(zhí)行順序執(zhí)行時(shí)，每個(gè)乘法和加法指令都需要5個(gè)時(shí)鐘周期（取指令、指令分析、指令執(zhí)行）；所以所需要的時(shí)間為：?jiǎn)瘟魉€標(biāo)量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線因?yàn)橛凶銐虻木彌_寄存器，所以我們可以首先把所有的乘法計(jì)算完，并通過(guò)調(diào)度使加法流水線不出現(xiàn)停頓，所以所需要的時(shí)間為：加法加31234加21234加11234乘法乘3乘2精品.乘1譯碼1234取指1234123456785135145155165175189639649659661=+、2=1+、3=2+、4=3+、5=4+、6=5+、7=6+多操作部件處理機(jī)，只有一條指令流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；由于操作部件不采用流水線，對(duì)于結(jié)果C矩陣的第一個(gè)元素，首先執(zhí)行2次乘法，然后乘法和加法并行執(zhí)行7次，此時(shí)C矩陣的第一個(gè)元素出來(lái)了，然后加法運(yùn)算停頓3個(gè)時(shí)鐘周期，再開(kāi)始與乘法并行執(zhí)行運(yùn)算7次，如此下去，直到C的64個(gè)元素都出來(lái)。故執(zhí)行時(shí)間為：?jiǎn)瘟魉€標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；對(duì)于乘法運(yùn)算不存在數(shù)據(jù)相關(guān)，對(duì)于加法運(yùn)算有數(shù)據(jù)相關(guān)，由于存在足夠的緩沖寄存器，我們可以通過(guò)合適的調(diào)度消除加法的數(shù)據(jù)相關(guān)。因此，最佳情況下的執(zhí)行時(shí)間為：加法加31234567加21234567加11234567乘法乘3精品.乘2乘1譯碼1234567取指1234567123456789101112131415161718192021221=+、2=1+、3=2+、4=3+、5=4+、6=5+、7=6+超標(biāo)量處理機(jī)同一時(shí)鐘周期可以有一條乘法指令和一條加法指令同時(shí)發(fā)射，對(duì)于乘法運(yùn)算不存在數(shù)據(jù)相關(guān)性，對(duì)于加法運(yùn)算有數(shù)據(jù)相關(guān)性，由于存在足夠的緩沖寄存器，當(dāng)運(yùn)算完所有的乘法運(yùn)算后，還要做一次加法運(yùn)算。因此執(zhí)行時(shí)間為：加法加3123456712345加2123456712345加1123456712345譯碼123456712345取指123456712345乘法乘3乘2乘1譯碼取指12345678910111213141516171819202122精品.1=+、2=1+、3=2+、4=3+、5=4+、6=5+、7=6+超流水線處理機(jī)每個(gè)時(shí)鐘周期發(fā)射兩條指令，加法部件和乘法部件都為6個(gè)流水級(jí)。事實(shí)上相當(dāng)于將時(shí)鐘周期變成了10ns，而加法和乘法流水線變成了6級(jí)。因此執(zhí)行時(shí)間為：超標(biāo)量超流水線處理機(jī)一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法部件都為6個(gè)流水級(jí)，每個(gè)流水級(jí)能同時(shí)發(fā)射一條加法和一條乘法指令。綜合和的分析，我們可以知道，執(zhí)行時(shí)間為：如有侵權(quán)請(qǐng)聯(lián)系告知?jiǎng)h除，感謝你們的配合！精品