流水線課后習(xí)題

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

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

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

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

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

6、，則該流水線的最大吞吐率TPMAX為(8) 使用最小恒定循環(huán)時，設(shè)該流水線的時鐘周期為，該流水線的吞吐率為6 下列匯編代碼在一臺3段流水線處理機上執(zhí)行，每一段都有冒險(相關(guān))檢測和分解。這三段是取指令、取操作數(shù)（根據(jù)要求取一個或者多個）和執(zhí)行（包括寫回操作）。試說明在代碼執(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題我們首先給上面的指令序列編號如下：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來分別代表流水線的取指令、取操作數(shù)和執(zhí)行三段。下面的圖表顯示了執(zhí)行的序列：圖中的箭頭方向是同一條指令在流水線中的流動方向，從圖中我們可以看出：在t3時刻：O(I1) I(I2)= R0 ，會發(fā)生RAW相關(guān)；在t4時刻：O(I2) I(I3)= Acc ，會發(fā)生RAW相關(guān)；在t6時刻：O(I4) I(I5)= Acc ，會發(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ān)的發(fā)生。7 設(shè)有4段流水線處理機如下，此流水線的總求值時間為6個時鐘周期，所有相繼段必須在每個時鐘周期之后才能使用。(1) 列出這一流水線的4行六列預(yù)約表。(2) 列出任務(wù)啟動之間的禁止等待時間集。(3) 畫出表示所有可能的等待時間循環(huán)的狀態(tài)圖。(4) 根據(jù)狀態(tài)圖列出所有的迫切（最小啟動）循環(huán)。(5) 最小平均等待時間值是多少？ 第7題可能會有多種方案。答案一：(1) 預(yù)約表如下所示：123456S1XXS2XXS3

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

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

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

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

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

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

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

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

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

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

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

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

21、 ;R1向量長度83： LOOP：LOADR2, A(R1) ;R2A向量的一個元素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ù)測技術(shù)，每次都預(yù)測轉(zhuǎn)移不成功。畫出指令流水線的時空圖（中間部分可以省略，圖中可用指令序號表示），計算流水線的吞吐率和加速比，并分別計算譯碼部件和ALU部件的使用效率。(2)采用靜態(tài)分支預(yù)測技術(shù)，每次都預(yù)測轉(zhuǎn)移成功。計算指令流水線的吞吐率和加速比，并分別計算譯碼部件和ALU部件的使用效

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