流水線課后習(xí)題

1、第5章 課后習(xí)題1填空題(1) 衡量流水線性能的主要指標(biāo)有 、 和 。(2) 指令亂序流動(dòng)可能造成 、 、 三種數(shù)據(jù)相關(guān)。(3) 解決數(shù)據(jù)相關(guān)主要有 法和 法。(4) 超標(biāo)量處理機(jī)開(kāi)發(fā)的是 并行性，而超流水線處理機(jī)開(kāi)發(fā)的是 并行性。 (1). 吞吐率、加速比、效率(2). 先寫(xiě)后讀、先讀后寫(xiě)、寫(xiě)寫(xiě)(3). 推后分析、設(shè)置專(zhuān)用路徑 (4). 空間、時(shí)間 2假設(shè)一條指令的執(zhí)行過(guò)程分為取指令、分析和執(zhí)行三段，每一段的時(shí)間分別為t、2t和3t。在下列各種情況下，分別寫(xiě)出連續(xù)執(zhí)行n條指令所需要的時(shí)間表達(dá)式。(1) 順序執(zhí)行方式。(2) 僅取指令和執(zhí)行重疊。(3) 取指令、分析和執(zhí)行重疊。第2題(1) 順

2、序執(zhí)行時(shí)每條指令用時(shí)=t+2t+3t=6t，因此n條指令所需要的時(shí)間=6n*t(2) 第一條指令完成需要時(shí)間=t+2t+3t=6t，根據(jù)題義，下一條指令的取指令與上一條指令執(zhí)行的最后一個(gè)t重疊。因此，自從第一條指令完成后，每隔4t完成一條指令。所以余下的n-1條指令用時(shí)(n-1)*4t. 所以，n條指令所需要的時(shí)間=6t+(n-1)*4t=2(2n+1)t。(3) 第一條指令完成需要時(shí)間=t+2t+3t=6t，由于一條指令的取指令和分析階段和下一條指令的執(zhí)行階段重疊，因此，此后每3t 完成一條指令，余下的n-1條指令用時(shí)(n-1)*3t.因此n條指令所需要的時(shí)間=6t+(n-1)*3t=3(n

3、+1)t3用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算F。每個(gè)功能段的延遲時(shí)間均相等，流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時(shí)間完成計(jì)算，畫(huà)出流水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。第3題假設(shè)每個(gè)功能段的延遲時(shí)間為t。F =(A1+1A2)+6(A3+2A4)+8(A5+3A6)+9(A7+4A8)+7(A9+5A10)由上面的時(shí)空?qǐng)D可以看出，在20t時(shí)間內(nèi)共完成9個(gè)加法操作。因此：吞吐率為：TP= 9/20=0.45 加速比為：Sp= 9*5/20=2.5效率為： E= 45/(20*5)=45%4 設(shè)有一個(gè)15000條指令的程序在一臺(tái)時(shí)

4、鐘速率為25MHz的線性流水線處理機(jī)上執(zhí)行。假設(shè)該指令流水線有5段，并且每個(gè)時(shí)鐘周期發(fā)射一條指令。忽略由于轉(zhuǎn)移指令和無(wú)序執(zhí)行造成的損失。 (1) 用該流水線執(zhí)行這一程序，并用流過(guò)延遲與其相等的一個(gè)等效非流水線處理機(jī)執(zhí)行同一程序，將兩者加以比較，并計(jì)算其加速比。(2) 該流水線處理機(jī)的效率是多少？(3) 計(jì)算該流水線的吞吐率。第4題(1) 等效的非流水處理機(jī)執(zhí)行一條指令需要的時(shí)間是5個(gè)時(shí)鐘周期。依照加速比定義，(2) 效率E為(3) 吞吐率TP為5 設(shè)有5段流水線處理機(jī)的預(yù)約表如下：(1) 列出禁止等待時(shí)間和沖突向量集。(2) 畫(huà)出狀態(tài)轉(zhuǎn)換圖，說(shuō)明不引起流水線沖突的所有可能的啟動(dòng)序列（循環(huán)）。(

5、3) 根據(jù)狀態(tài)圖列出所有簡(jiǎn)單循環(huán)。(4) 從簡(jiǎn)單循環(huán)中找出迫切循環(huán)。(5) 此流水線的最小平均等待時(shí)間(MAL)是多少？(6) 使用此流水線時(shí)，列出可允許的最小恒定循環(huán)。(7) 該流水線的最大吞吐率是多少？(8) 如果使用最小恒定循環(huán)，則吞吐率是多少？123456S1XXS2XXS3XS4XS5XX第5題(1) 禁止等待時(shí)間是：3，4，5。沖突向量為(11100)。(2) 狀態(tài)轉(zhuǎn)換圖如下所示：(3) 簡(jiǎn)單循環(huán)如下：(1，1，6)，(2，6)，(6)，(1，6)(4) 迫切(最小啟動(dòng))循環(huán)為(1，1，6)(5) 最小平均等待時(shí)間MAL為(6) 最小恒定循環(huán)為(6)。(7) 設(shè)該流水線的時(shí)鐘周期為

6、，則該流水線的最大吞吐率TPMAX為(8) 使用最小恒定循環(huán)時(shí)，設(shè)該流水線的時(shí)鐘周期為，該流水線的吞吐率為6 下列匯編代碼在一臺(tái)3段流水線處理機(jī)上執(zhí)行，每一段都有冒險(xiǎn)(相關(guān))檢測(cè)和分解。這三段是取指令、取操作數(shù)（根據(jù)要求取一個(gè)或者多個(gè)）和執(zhí)行（包括寫(xiě)回操作）。試說(shuō)明在代碼執(zhí)行中所有可能的相關(guān)情況。Inc R0/R0(R0)+1/Mul ACC,R0/ACC(ACC)(R0)/Store R1,ACC/R1(ACC)/Add ACC,R0/ACC(ACC)+(R0)/Store M,ACC /M(ACC)/第6題我們首先給上面的指令序列編號(hào)如下：I1： IncR0 /R0(R0)+1/I2： M

7、ulACC,R0 /ACC(ACC)(R0)/I3： StoreR1,ACC /R1(ACC)/I4： Add ACC,R0 /ACC(ACC)+(R0)/I5： StoreM,ACC/M(ACC)/我們使用IF、OF和EX來(lái)分別代表流水線的取指令、取操作數(shù)和執(zhí)行三段。下面的圖表顯示了執(zhí)行的序列：圖中的箭頭方向是同一條指令在流水線中的流動(dòng)方向，從圖中我們可以看出：在t3時(shí)刻：O(I1) I(I2)= R0 ，會(huì)發(fā)生RAW相關(guān)；在t4時(shí)刻：O(I2) I(I3)= Acc ，會(huì)發(fā)生RAW相關(guān)；在t6時(shí)刻：O(I4) I(I5)= Acc ，會(huì)發(fā)生RAW相關(guān)。其中我們用O(I1)表示指令I(lǐng)1的輸出

8、寄存器(如R0表示寄存器，而Acc表示表示累加器)，I(I2)表示指令I(lǐng)2的輸入寄存器。下面的調(diào)度方法能夠避免相關(guān)的發(fā)生：其中，Stall表示流水線停頓，通過(guò)這種方法，可以避免相關(guān)的發(fā)生。7 設(shè)有4段流水線處理機(jī)如下，此流水線的總求值時(shí)間為6個(gè)時(shí)鐘周期，所有相繼段必須在每個(gè)時(shí)鐘周期之后才能使用。(1) 列出這一流水線的4行六列預(yù)約表。(2) 列出任務(wù)啟動(dòng)之間的禁止等待時(shí)間集。(3) 畫(huà)出表示所有可能的等待時(shí)間循環(huán)的狀態(tài)圖。(4) 根據(jù)狀態(tài)圖列出所有的迫切（最小啟動(dòng)）循環(huán)。(5) 最小平均等待時(shí)間值是多少？ 第7題可能會(huì)有多種方案。答案一：(1) 預(yù)約表如下所示：123456S1XXS2XXS3

9、XS4X(2) 禁止等待時(shí)間為：4，沖突向量為：(1000)。(3) 狀態(tài)轉(zhuǎn)移圖如下：(4) 簡(jiǎn)單循環(huán)如下所示：(1，5)，(1，1，5)，(1，1，1，5)，(1，2，5)，(1，2，3，5)，(1，2，3，2，5)，(1，2，3，2，1，5)，(2，5)，(2，1，5)(2，1，2，5)，(2，1，2，3，5)，(2，3，5)，(3，5)，(3)，(3，2，5)，(3，2，1，5)，(3，2，1，2，5)，(5)，(3，2，1，5)(5) 最小啟動(dòng)循環(huán)如下：(1，1，1，5)和(1，2，3，2)(6) 平均最小等待時(shí)間為：(7) 最大的吞吐量為：答案二：(1) 預(yù)約表如下所示：123456

10、S1XXS2XXXS3XXS4X(2) 禁止等待時(shí)間為：2和4，沖突向量為：(1010)。(3) 狀態(tài)轉(zhuǎn)移圖如下：(4) 簡(jiǎn)單循環(huán)如下所示： (3)，(5)，(1，5)和(3，5) (5) 最小啟動(dòng)循環(huán)如下：(1，5)和(3) (6) 最小平均等待時(shí)間為： (7) 最大吞吐量為：8 三條功能流水線f1，f2和f3可用下面的預(yù)約表來(lái)描述： 用這三條流水線還可形成一個(gè)組合流水線網(wǎng)絡(luò)如下： 通過(guò)此組合流水線的每個(gè)任務(wù)按以下的次序使用流水線：第一是f1，其次是f2和f3，再是f1，然后得到輸出。雙多路轉(zhuǎn)換器從（A,B）或（X,Y）中選擇一對(duì)輸入，并把他們輸入給f1。組合流水線的使用也是用組合的預(yù)約表來(lái)

11、描述的。(1) 為此組合流水線填充下列預(yù)約表： 123456789101112S1XS2XS3XT1T2T3XU1XU2U3(2) 寫(xiě)出禁止啟動(dòng)循環(huán)和初始沖突向量。(3) 畫(huà)出能清楚表示所有等待時(shí)間循環(huán)的狀態(tài)圖。(4) 列出所有簡(jiǎn)單循環(huán)和迫切（最小啟動(dòng)）循環(huán)。(5) 計(jì)算此組合流水線的MAL和最大吞吐率。第8題(1) 預(yù)約表如下：123456789101112S1XXS2XXS3XXXXT1XXT2XT3XU1XXU2XU3X(2) 禁止等待時(shí)間為：8，1，7，9，3，2；初始沖突向量為：(111000111)(3) 狀態(tài)轉(zhuǎn)換圖如下：(4) 簡(jiǎn)單循環(huán)為：(5)，(6)，(10)，(4，6)，(

12、4，10)，(5，6)，(5，10)；其中最小啟動(dòng)循環(huán)為：(5)和(4，6)；(5) 最小平均啟動(dòng)距離為：(6) 最大吞吐量為；9 假設(shè)一個(gè)四段流水線（其時(shí)鐘周期=20ns）的預(yù)約表如下：123456S1XXS2XXS3XS4XX(1) 哪些是禁止等待時(shí)間和初始沖突向量？(2) 畫(huà)出調(diào)度該流水線的狀態(tài)變換圖。(3) 確定與最佳迫切循環(huán)相關(guān)聯(lián)的MAL。(4) 確定與MAL和給定的相對(duì)應(yīng)的流水線吞吐率。(5) 確定該流水線的MAL下限。從上面的狀態(tài)圖你得到最佳等待時(shí)間了嗎？如果允許你在上面的流水線中插入一個(gè)非計(jì)算延遲段，使最短迫切循環(huán)中的等待時(shí)間為1，其目的是要產(chǎn)生一張新的預(yù)約表，以獲得下限最佳等

13、待時(shí)間。(6) 畫(huà)出5行7列修改后的預(yù)約表。 (7) 為得到最佳循環(huán)畫(huà)出新的狀態(tài)變換圖。(8) 根據(jù)狀態(tài)圖列出所有的簡(jiǎn)單循環(huán)和迫切循環(huán)。(9) 證明新的MAL等于下限。(10) 這條流水線的最佳吞吐率是多少？與上面的吞吐率相比，改善的百分比是多少？第9題(1) 禁止等待時(shí)間為：1，2，5；初始沖突向量為：（10011）；(2) 狀態(tài)轉(zhuǎn)移圖如下：(3) 最小平均等待時(shí)間為： (4) 最大吞吐量為：(million operation per second)(5) 最小的平均等待時(shí)間為2，因此，這種調(diào)度方法不是最優(yōu)的。(6) 插入非計(jì)算性延遲后，預(yù)約表如下所示：1234567S1XXS2XXS3X

14、S4XXDX(7) 狀態(tài)轉(zhuǎn)換圖變成如下所示：(8) 簡(jiǎn)單循環(huán)如下：（4），（5），（7），（3，1），（3，4），（3，5，4），（3，5，7），（1，7）（5，4），（5，7），（3，7），（1，3，4），（1，3，5，4），（1，3，5，7）（1，3，7），（1，4，3），（1，4，4），（1，4，7），（5，3，4），（5，3，7）（5，3，1，7）其中最小啟動(dòng)循環(huán)為（1，3）(9) 此時(shí)的最小啟動(dòng)距離為：(10) 此時(shí)的最大吞吐率為：10 假設(shè)分支概率（相對(duì)于所有的指令）為：條件分支20%，跳轉(zhuǎn)和過(guò)程調(diào)用：5%， 其中，條件成功分支有60%可能執(zhí)行。在一個(gè)4段的流水線中，如果分支指令在

15、第2個(gè)時(shí)鐘周期末決定是否是條件失敗分支，在第3個(gè)時(shí)鐘周期末決定是否是條件成功分支。假定第1個(gè)時(shí)鐘周期的操作和條件分支無(wú)關(guān)，并且忽略其他流水停頓，那么，如果沒(méi)有控制相關(guān)的話，處理器能快多少？第10題我們使用加速比來(lái)衡量控制相關(guān)引起的流水線的效率下降。考慮如下的公式：這個(gè)公式中假設(shè)輸入的任務(wù)數(shù)目足夠多，并且我們假設(shè)所有的流水線停頓都由控制相關(guān)引起（因?yàn)槲覀冎魂P(guān)心控制相關(guān)），而式中的流水線平均停頓數(shù)定義為平均每條指令執(zhí)行過(guò)程流水線停頓的時(shí)鐘周期數(shù)，該公式可以看成是流水線加速比公式的極限情況。理想狀態(tài)下，如果沒(méi)有控制相關(guān)，也就沒(méi)有流水線停頓，于是，有為了得到因?yàn)榭刂葡嚓P(guān)引起的流水線平均停頓數(shù)，我們需要

16、三方面的信息：(1) 我們需要知道程序中的控制流指令類(lèi)型。本題中有三種：條件分支發(fā)生，條件分支不發(fā)生，跳轉(zhuǎn)和子程序調(diào)用。(2) 我們需要知道每一種控制流指令引起的流水線平均停頓數(shù)。我們假設(shè)流水線的四段分別為IF、ID、EX和WB（分別代表取指令、指令分析、指令執(zhí)行和寫(xiě)回）。首先我們考慮跳轉(zhuǎn)和調(diào)用的情形。如下面的表所示：指令123456跳轉(zhuǎn)或調(diào)用IF IDEXWBi+1IFIFIDEX i+2stallIFID i+3stallIF由于流水線的第一級(jí)總是可以提前進(jìn)行（即不管下一條指令的內(nèi)容），所以在第2個(gè)時(shí)鐘周期（相對(duì)于跳轉(zhuǎn)或調(diào)用指令），下一條指令依然進(jìn)入IF段（因?yàn)榇藭r(shí)i+1指令的地址是這時(shí)知

17、道的唯一一個(gè)可以用來(lái)更新PC的地址），在第2個(gè)時(shí)鐘周期末，跳轉(zhuǎn)和調(diào)用的目的地址已經(jīng)確定，所以流水線在第三個(gè)時(shí)鐘周期再次執(zhí)行IF以取回正確的指令，這樣引起了一個(gè)時(shí)鐘周期的停頓。條件分支發(fā)生的情形如下表：指令123456發(fā)生的條件分支IFIDEXWBi+1IFstallIFIDi+2stallstallIFi+3stallstall因?yàn)闂l件分支的目的地址在第3個(gè)時(shí)鐘周期末才能決定，所以出現(xiàn)了2個(gè)時(shí)鐘周期的停頓。條件分支不發(fā)生的情形如下表：指令123456不發(fā)生的條件分支IFIDEXWBi+1IFstallIDEXi+2stallIFIDi+3stallIF注意到第2個(gè)時(shí)鐘周期取到的是下一條順序指令

18、，也就是不發(fā)生的分支的目標(biāo)地址，而且由于條件分支的目的地址在第3個(gè)時(shí)鐘周期末確定，所以會(huì)產(chǎn)生一個(gè)時(shí)鐘周期的流水線停頓。(3) 各種控制流指令發(fā)生的概率。題目已經(jīng)給出了數(shù)據(jù)，所以，實(shí)際的平均停頓數(shù)為：由此，實(shí)際的流水線加速比為： 比較理想情況和實(shí)際情況，我們可以得到如果沒(méi)有控制相關(guān)的情形下，在現(xiàn)有的系統(tǒng)基礎(chǔ)上得到的加速比為： 11 設(shè)有兩個(gè)4段流水線加法器和若干個(gè)非計(jì)算延遲單元，每個(gè)延遲單元有一個(gè)單位的時(shí)間延遲。(1) 用已有的加法器和延遲單元構(gòu)成一個(gè)組合流水線部件，試對(duì)以下表達(dá)式求值： ，對(duì)于所有的 。組合流水線接收相繼輸入a(i)，對(duì)于 。(2) 設(shè)有第三個(gè)4段流水線加法器，用這第三個(gè)加法器

19、來(lái)擴(kuò)大題(a)中的設(shè)計(jì)，使之能計(jì)算以下的遞歸表達(dá)式：，對(duì)于所有的 。注意，其中b(i)是由題(a)中的組合流水線產(chǎn)生的。第11題 (1) 組合流水線: (2) 第三個(gè)加法器的連接: 12 比較度為（m，n）的超流水線超標(biāo)量處理機(jī)與度為（1，1）的基準(zhǔn)表量處理機(jī)的性能。在下述限制情況下，試分析下面公式的加速比表達(dá)式： （1）在1m4和1n6的范圍內(nèi)，對(duì)加速比S(m,n)最大化后的最佳流水線段數(shù)是多少？（2）阻礙超標(biāo)量度m增長(zhǎng)的實(shí)際限制是什么？（3）阻礙超流水度n增長(zhǎng)的實(shí)際限制是什么？第12題 (1) 對(duì)于給定的m和n的范圍，我們有不等式：我們對(duì)超流水超標(biāo)量機(jī)的加速比公式進(jìn)行改寫(xiě)如下：根據(jù)上面的公

20、式，可以知道當(dāng)mnk取最小值時(shí)，S(m,n)有最大值，因此，為了使加速比最大，流水線的段數(shù)應(yīng)該是1。(2) 指令級(jí)的并行度限制了超標(biāo)量度的增長(zhǎng)。(3) 時(shí)鐘多相的技術(shù)（各部件間的同步存在困難）限制了超流水度的增長(zhǎng)。13 在一臺(tái)單流水線處理機(jī)上執(zhí)行下面的程序。每條指令都要經(jīng)過(guò)取指令、譯碼、執(zhí)行和寫(xiě)結(jié)果4個(gè)流水段，每個(gè)流水段的延遲時(shí)間都是5ns。在執(zhí)行流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，兩個(gè)操作部件的輸出端有直接數(shù)據(jù)通路與任意一個(gè)操作部件的輸入端相連接，ALU部件產(chǎn)生的條件碼也能夠直接送入控制器。1： SUB R0, R0 ;R002： LOADR1, #8

21、 ;R1向量長(zhǎng)度83： LOOP：LOADR2, A(R1) ;R2A向量的一個(gè)元素4： MUL R2, R1 ;R2(R2)(R1)5： ADD R0, R2 ;R0(R0)(R2)6： DNE R1, LOOP;R1(R1)1,若(R1)0轉(zhuǎn)向LOOP7： STORE R0, S ;保存結(jié)果(1)采用靜態(tài)分支預(yù)測(cè)技術(shù)，每次都預(yù)測(cè)轉(zhuǎn)移不成功。畫(huà)出指令流水線的時(shí)空?qǐng)D（中間部分可以省略，圖中可用指令序號(hào)表示），計(jì)算流水線的吞吐率和加速比，并分別計(jì)算譯碼部件和ALU部件的使用效率。(2)采用靜態(tài)分支預(yù)測(cè)技術(shù)，每次都預(yù)測(cè)轉(zhuǎn)移成功。計(jì)算指令流水線的吞吐率和加速比，并分別計(jì)算譯碼部件和ALU部件的使用效

22、率。(3)為了采用指令取消技術(shù)，請(qǐng)改寫(xiě)上面的程序，并計(jì)算程序的執(zhí)行時(shí)間。第13題(1)采用靜態(tài)分支預(yù)測(cè)技術(shù)，每次都預(yù)測(cè)轉(zhuǎn)移不成功。(2)采用靜態(tài)分支預(yù)測(cè)技術(shù)，每次都預(yù)測(cè)轉(zhuǎn)移成功。(3)采用指令取消技術(shù)。SUBR0, R0;R00LOAD R1, #8;R1向量長(zhǎng)度8LOAD R2, A(R1) ;R2A向量的一個(gè)元素MULR2, R1;R2(R2)(R1)LOOP：ADDR0, R2;R0(R0)(R2)DNER1, LOOP;R1(R1)1,若(R1)0轉(zhuǎn)向LOOPLOAD R2, A(R1) ;R2A向量的一個(gè)元素MULR2, R1;R2(R2)(R1)STORER0, S ;保存結(jié)果程序的執(zhí)行時(shí)間為：5ns40200ns14 在一臺(tái)每個(gè)時(shí)鐘周期發(fā)射兩條指令的超標(biāo)量處理機(jī)上運(yùn)行下面一段程序。所有指令都要經(jīng)過(guò)取指令、譯碼、執(zhí)行和寫(xiě)結(jié)果4個(gè)階段，其中，取指令、譯碼和寫(xiě)結(jié)果三個(gè)階段各為一個(gè)流水段，其延遲時(shí)間都為10ns。在執(zhí)行階段，LOAD操作和AND操作各延遲10ns，ADD操作