典型習(xí)題和題例分析與解答

1、5.3典型習(xí)題和題例分析與解答題5. 1假設(shè)指令的解釋分取指、分析和執(zhí)行3步，每步的時(shí)間相應(yīng)地為t取指、11分析、11執(zhí)行，(1)分別計(jì)算下列幾種情況下，執(zhí)行完100條指令所需時(shí)間的一般關(guān)系式；i. 順序方式；ii. 僅“執(zhí)行x”與“取指x乘重疊，iii. 僅“執(zhí)行x”、“分析r+:"，“取指。+:"重疊.(2) 分別在t取指=t分析=2, t執(zhí)行=1及t取指=t執(zhí)行=5, t分析二2兩種情況下，計(jì)算出上述各結(jié)果。分析可先按指令問(wèn)所要求的時(shí)間關(guān)系畫(huà)出指令間的時(shí)間重疊關(guān)系圖，由 圖就可以列出各種情況下，計(jì)算 100條指令所需時(shí)間的一般關(guān)系式。再將給出的 時(shí)間值代入，實(shí)際完成1

2、00條指令所需的時(shí)間就可以求得。順序方式工作的時(shí)間關(guān)系如圖5. 1所示。r取指kj分析k 1執(zhí)行k111取指k+1 ；分析k+1 :執(zhí)行k+1 |VI11取指k+2:分析k+2 1fl執(zhí)行k+2圖5.1 順序方式工作的時(shí)間關(guān)系圖僅“執(zhí)行k ”與“取指k+1 ”、重疊方式工作的時(shí)間關(guān)系如圖 5. 2所示.取指k分析k !執(zhí)行k取指k+1 :分析k+1 1執(zhí)行k+1取指k+2 :分析k+2 ；執(zhí)行k+2口I圖5. 2 僅“執(zhí)行k ”，與“取指k+1 ”重疊方式工作的時(shí)間關(guān)系圖取指k分析k !執(zhí)行k取指k+1 ;分析k+1 I執(zhí)行k+1取指k+2 :分析k+2 :執(zhí)行k+2IIV圖5. 3僅“執(zhí)行k

3、 ”、“分析k+1 ”、“取指k+2 ”重疊方式工作的時(shí)間關(guān)系圖解答(1)計(jì)算執(zhí)行完100條指令所需要的時(shí)間：(i)順序方式工作時(shí)為100 (t取指t分析t執(zhí)行)(ii) 僅“執(zhí)行k ”，與“取指k+1 ”重疊方式工作時(shí)為t取指100t分析99 max t取指，t執(zhí)行t執(zhí)行(iii) 僅“執(zhí)行k ”、“分析k+1“取指k+2 ”重疊方式工作時(shí)為t取指maxt分析，t取指98 max t取指，t分析，t執(zhí)行maxt執(zhí)行，t分析t執(zhí)行(2) 當(dāng)t取指=t分析=2、t執(zhí)行=l時(shí)，代入上面的各式，可求得100條指 令執(zhí)行所需要的時(shí)間是：順序方式工作時(shí)為500。僅“執(zhí)行k ”，與“取指k+1 ”重疊方式

4、工作時(shí)為401。僅“執(zhí)行k ”、“分析k+1“取指k+2 ”重疊方式工作時(shí)為203。輸入101112131415D 圖5. 4題5. 2的流水時(shí)空?qǐng)D所以，按周期性工作時(shí)的流水線平均吞吐宰為：5At時(shí)間(t)當(dāng)t取指=t執(zhí)行=5, t分析=2,代入上面的各式，可求得100條指令執(zhí)行所需要的時(shí)間是：順序方式工作時(shí)為1200。僅“執(zhí)行k ”，與“取指k+1 ”重疊方式工作時(shí)為705。僅“執(zhí)行k ”、“分析k+1 ; 取指k+2 ”重疊方式工作時(shí)為510。題5. 2流水線由4個(gè)功能部件組成，每個(gè)功能部件的延遲時(shí)間為 t。當(dāng)輸 入10個(gè)數(shù)據(jù)后，間歇5At,又輸入10個(gè)數(shù)據(jù)，如此周期性地工作，求此時(shí)流水

5、線的吞吐率，并畫(huà)出其時(shí)空?qǐng)D。分析所謂卒&入10個(gè)數(shù)據(jù)后.間歇5At ,又輸入10個(gè)數(shù)據(jù)的含義應(yīng)當(dāng)是 以輸入時(shí)間為基準(zhǔn)，即從第10個(gè)數(shù)據(jù)輸入時(shí)算起.隔5At后又開(kāi)始輸入新的一 輪數(shù)據(jù)。解答按題意可得4個(gè)功能部件流水時(shí)的時(shí)空關(guān)系.如圖 5. 4所示.部件10101010TJ05p 14 t 7 t題5. 3有一個(gè)浮點(diǎn)乘流水線如圖 5. 5(a)所示，其乘積可直接返回輸入端 或暫存于相應(yīng)緩沖寄存器中，畫(huà)出實(shí)現(xiàn) A*B*C*D的時(shí)空?qǐng)D以及精入端的變化，并 求出該流水線的吞吐率和效率；當(dāng)流水線改為圖 5. 5(b)形式實(shí)現(xiàn)同一計(jì)算時(shí)，求 該流水線的效率及吞吐率。分析為了減少運(yùn)算過(guò)程中的操作數(shù)相關(guān)

6、，A*B*C*D應(yīng)改為采用(A*B) *(C*D)的算法步驟進(jìn)行運(yùn)算。解答按圖5. 5(a)組織.實(shí)現(xiàn)A*B*C, D的時(shí)空關(guān)系如圖5. 6所示。吞吐率效率流水按圖5.5吞吐率效率題5. 4Tp冷3 5 t _53 13 t 13(b)組織時(shí)，實(shí)現(xiàn)A*B*C*D的時(shí)空關(guān)系如圖5.7所示。Tp 11 t3 5 t 勺311t 11一個(gè)4段的雙輸入端規(guī)格化浮點(diǎn)加法流水線，每段經(jīng)過(guò)時(shí)間10ns,輸出可直接返回輸入或?qū)⒔Y(jié)果暫存于相應(yīng)緩沖器中，問(wèn)最少需經(jīng)多少時(shí)間能求出10A ,并畫(huà)出時(shí)空?qǐng)D。i=110分析為了避免流水線的先寫(xiě)后讀相關(guān)，使流水線性能盡可能高，需將 Ai=1調(diào)整成(A1 + A2) + (A

7、3 十A4 ) 十(tjA9+ AI0) + (A5+A6) + (A7 + A8)的算法步驟來(lái)進(jìn)行。解答按( A+A2)+ ( A3 十 A4)十(與人+人0) + ( A+A) + ( A7+A8)流水的時(shí)空?qǐng)D如圖5. 8所示.10由圖5. 8之時(shí)空?qǐng)D可知，求A所需要的最少時(shí)間為170ns 題5.5為提高流水線的效率可用哪兩種主要途徑來(lái)克服速度瓶頸？現(xiàn)有 3段流水線各段經(jīng)過(guò)的時(shí)間依次為At、3At> t o(1)分別計(jì)算在連續(xù)輸入3條指令時(shí)和30條指令時(shí)的吞吐率和效率。(2)按兩種逾徑之一改進(jìn)，畫(huà)出你的流水線結(jié)構(gòu)示意圖.同時(shí)計(jì)算連續(xù)輸入3條指令和30條指令時(shí)的吞吐率和效率。(3) 通

8、過(guò)對(duì)(1)、(2)兩小題的計(jì)算比較可得出什么結(jié)論？分析根據(jù)題意可以看出，原3段的流水線工作起來(lái)仍可看成是一條線性 流水線只是其中經(jīng)過(guò)時(shí)間為34t的段是瓶頸段，所以可以按T np mti (n 1) tjn?Tp -mti(n 1) tji 1335 t 2 3 t 11 tmn? ti i 1mm ti (n 1) tj i 13 5 t 衛(wèi)3 11 t 11而連續(xù)流入30條指令時(shí)，只需將上式之n改為30,其它參數(shù)不變，得Tp30tii 1(30 1) tj30155 t 29 3 t 46ttii 1mm ti (n 1) tji 1來(lái)求得Tp和.其中，n為連續(xù)輸入的指令數(shù)，m為3個(gè)段，ti

9、=4t, t? = 3 t, At3 =At, tj為瓶頸段經(jīng)過(guò)時(shí)間，本題的 tj為34t。在改進(jìn)流水性能時(shí)，無(wú)論是將瓶頸段 2段細(xì)分成3個(gè)時(shí)間分別為t的子段， 還是用3個(gè)瓶頸段2段并聯(lián)，計(jì)算吞吐率、效率時(shí)，只需將公式中的m由3改成5,tj改成,即可。解答提高流水線效率，消除速度瓶頸主要有將瓶頸段再細(xì)分以及重復(fù)設(shè) 置多個(gè)頸段并聯(lián)工作，給其輪流分配任務(wù)的兩種途徑。(1) 在3段流水線，各段經(jīng)過(guò)時(shí)間依次為 5 3At> At的情況下，連續(xù)流入3 條指令時(shí)，將 n=3,3, t1=4t, t2 =3At , t3 = At, tj=34t 代入，可得吞吐 率Tp ,和效率為30 5 t 253

10、 92 t 46(2)若采取將2段細(xì)分成3個(gè)子段，每個(gè)子段均為7 ,構(gòu)成的流水線結(jié)構(gòu)如圖5. 92所示。連續(xù)流入3條指令時(shí)，將n = 3,5, it = tj = t代入，得Tp-ti(31) ti3?i 1ti1517 t連續(xù)流入30條指令時(shí),n=30代入，其它參數(shù)不變，有Tp飛一ti i 1303015(30 1) ti5t 29t 17 t30 5 t5 34 t1517若采取將3個(gè)2段并聯(lián)構(gòu)成的流水線，具構(gòu)成如圖 5. 10所示。連續(xù)流入3條指令及流入30條指令時(shí)的吞吐率Tp,和效率所計(jì)算的結(jié)果分 別與子過(guò)程細(xì)分的相同。(3)將(1)題的計(jì)算結(jié)果進(jìn)行比較可以看出，只有當(dāng)連續(xù)流入流水線的

11、聯(lián) 指令越多時(shí)，流水線的實(shí)際吞吐率和效率才會(huì)提高。將(1)、(2)題的計(jì)算結(jié)果進(jìn)行比較，同樣可以看出，無(wú)論采用瓶頸子過(guò)程再 細(xì)分，還是將多個(gè)瓶頸子過(guò)程并聯(lián)來(lái)消除流水線瓶頸，都只有在連續(xù)流入流水線 的指令數(shù)越多時(shí)才能使實(shí)際吞吐率和效率得到顯著的提高。若連續(xù)流入流水線的指令數(shù)太少，消除流水線瓶頸雖可以提高流水線的實(shí)際吞吐率Tp,而效率 卻可 能下降。題5.6 有一個(gè)雙輸入端的加一乘雙功能靜態(tài)流水線， 由經(jīng)過(guò)時(shí)間為At、2At、 2At> At的1、2、3、4四個(gè)子過(guò)程構(gòu)成.加按124連接，乘按134連接, 流水線，S出設(shè)有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入.現(xiàn)要執(zhí)行A* (B+C*(D+E*

12、H) +G*H的運(yùn)算，請(qǐng)調(diào)整計(jì)算順序，畫(huà)出能獲得吞吐率盡量高的流水時(shí)空?qǐng)D，標(biāo)出流水線 入，出端數(shù)據(jù)的變化情況，求出完成全部運(yùn)算的時(shí)間及此期間流水線的效率.如對(duì)流水線瓶頸子過(guò)程再細(xì)分，最少只需多少時(shí)間可完成全部運(yùn)算？若子過(guò)程3不能再細(xì)分，只能用并聯(lián)方法改進(jìn)，問(wèn)流水線的效率為多少 ？分析因?yàn)槭羌右怀穗p功能靜態(tài)流水線，為了能有高的吞吐率，應(yīng)減少流水線的功能切換次數(shù)。因此，宜將算法調(diào)整成先一連串的乘，然后再切換成一連用的加.這樣，將計(jì)算式展開(kāi)成：A*B+A*C*D+A*C*E*F+G*H對(duì)于該表達(dá)式的計(jì)算，自然應(yīng)先進(jìn)行乘法流水.為了減少因先寫(xiě)后讀相關(guān)而 等待的時(shí)間，應(yīng)盡量安排對(duì)計(jì)算式子項(xiàng)數(shù)量多的乘法先

13、進(jìn)行操作.止匕外，由于流 水線中瓶頸子過(guò)程為2 At,所以，流水輸入端最快也只能每隔24t輸入一組數(shù)據(jù)。解答根據(jù)題意，對(duì)算法經(jīng)調(diào)整后，能使流水吞吐宰盡量高的流水時(shí)空?qǐng)D如圖5.11所示。圖中已標(biāo)出了流水線入、出端的數(shù)據(jù)變化情況.根據(jù)圖5. 11的流水時(shí)空?qǐng)D，可以看出，完成全部運(yùn)算的時(shí)間為24t。在此期間的流水線效率 ( ai?bi a2?b2)a3?b3)a4?b，)a5?b5)a6?d) a7?W a8?bs)如果現(xiàn)在將瓶頸子過(guò)程2和3均細(xì)分成兩個(gè)子過(guò)程.則時(shí)空?qǐng)D如圖 5. 12所 示。圖5. 12子過(guò)程細(xì)分后的沈水線時(shí)空?qǐng)D由田5. 12可見(jiàn)，完成全部運(yùn)算最少需要18At的時(shí)間即可?，F(xiàn)在若干過(guò)

14、程3不能再細(xì)分了，只能用2個(gè)子過(guò)程3通過(guò)并聯(lián)來(lái)改進(jìn)，則其 時(shí)空?qǐng)D如圖5. 13所示。完成全部運(yùn)算時(shí)的流水線效率24t 12t16 18 t 3題5.7現(xiàn)在長(zhǎng)度為8的向量A和B,請(qǐng)分別畫(huà)出在下列4種結(jié)構(gòu)的處理器上 求點(diǎn)積A?B的時(shí)空?qǐng)D，并求完成全部結(jié)果的最少時(shí)鐘拍數(shù)。設(shè)處理器中每個(gè)部件 的輸出均可直接送到任何部件的輸入端或存入緩沖器，其間的傳送延時(shí)不計(jì)，指 令和源操作數(shù)均能連續(xù)提供。(1)處理器有一個(gè)乘法部件和一個(gè)加法部件，不能同時(shí)工作，部件內(nèi)也只能順序方式工作，完成一次加法或乘法均只需 5拍；(2)與(1)基本相同，只是乘法部件和加法部件可并行；(3)處理器有一個(gè)乘、加功能靜態(tài)流水線，乘、加均

15、由5個(gè)部件流水段構(gòu)成，各段經(jīng)過(guò)時(shí)間要1拍；(4)處理器有乘、加兩條流水線，可同時(shí)工作，各由5段構(gòu)成，每段經(jīng)過(guò)時(shí)間為1拍。分析長(zhǎng)度為8的向量A和B的點(diǎn)積為8A? B a?。qDa2b2a3b3a4b4a5b5a6b6a7b7a8b8i 1共需做8次乘法和7次加法。解答(1)乘法部件和加法部件不能同時(shí)工作，部件內(nèi)也只能順序方式工作 時(shí)的時(shí)空?qǐng)D如圖5.14所示。由圖5.14向量點(diǎn)積A?B運(yùn)算的時(shí)空?qǐng)D可知，完成全部運(yùn)算最少為8 5 7 5 75(拍)(2)乘法部件和加法部件可以并行的時(shí)空關(guān)系所示。解題算法步驟為( a1?b1 a2?b2)a3?b3)a4?b,)as?b5)a6?b6)a?8)a8?b

16、8)向量點(diǎn)積運(yùn)算全部完成需45拍。(3) 處理器有乘、加雙功能靜態(tài)流水線，完成點(diǎn)積運(yùn)算的流水時(shí)空關(guān)系 解題算法步驟為a1?b1a2?b2)(a3?b3a4?b4)(a5?b5a6?b6)(a7?b7a8?b8)完成向量點(diǎn)積運(yùn)算需要30 拍。(4) 乘、加兩條流水線可同時(shí)工作，完成點(diǎn)積運(yùn)算的流水時(shí)空田如圖5.17 所示。在此流水線上，所用的解題算法步驟為a1?b1a2?b2)(a7?b7)(a5 ?b5a6?b6)(a3?b3a4 ?b4)a8?b8)全部完成向量點(diǎn)積運(yùn)算共需26 拍。題5 8 試總結(jié)IBM360 91 解決流水控制的一般方法、途徑和特點(diǎn)。I 解答 采用流水控制的方法是總線式分布

17、處理。解決流水控制的途徑如下：(1) 在各個(gè)寄存器中設(shè)置忙位標(biāo)志來(lái)判斷是否相關(guān)。當(dāng)寄存器正在使用時(shí)，置該寄存器的忙位標(biāo)志為“1”當(dāng)寄存器被釋放時(shí)，其忙位標(biāo)志清成“0”。因此，訪問(wèn)寄存器時(shí)，先看忙位標(biāo)志，如為“1”，表示相關(guān)。(2) 設(shè)置多條流水線，讓它們并行地工作，同時(shí)在分布于各流水線的入、出端上分別設(shè)置若干個(gè)保存站來(lái)緩沖存放信息。(3) 通過(guò)分布設(shè)置的站號(hào)來(lái)控制相關(guān)專用通路的連接。(4) 相關(guān)專用通路采用總線方式，相關(guān)后通過(guò)更改站號(hào)來(lái)實(shí)現(xiàn)不同相關(guān)專用通路的連接(5) 設(shè)置多條流水線，讓其并行工作，流水線輸入端設(shè)置多組保存站，這樣，就可以實(shí)現(xiàn)沈水線的異步流動(dòng)。解決流水控制的特點(diǎn)：(1) 不必對(duì)進(jìn)入流水線各條指令的源操作數(shù)地址和目的操作數(shù)地址做兩兩配對(duì)的比較，就可判知是否發(fā)生了相關(guān)。所以，相關(guān)判斷的控制大大簡(jiǎn)化。(2) 對(duì)于異步流動(dòng)的先寫(xiě)后讀、先讀后寫(xiě)及寫(xiě)一寫(xiě)三類相關(guān)都能很方便且不加區(qū)分地予以解決(3) 相關(guān)專用通路采用總線方式，使該通路可以為各種相關(guān)所共用，大大簡(jiǎn)化了硬件(4) 多條流水線采取異步并行，且多條相關(guān)的指令可以一直鏈接下去，使系統(tǒng)有高的性能題 5.9 在一個(gè) 5 段的流水線處理機(jī)上需經(jīng)9 拍才能完成一個(gè)任務(wù)，其預(yù)約表如表 5 1 所示分別寫(xiě)出延遲禁止表F、沖突向量c；畫(huà)出流水線狀態(tài)轉(zhuǎn)移圖，求出最小平均延遲及流水線的最大吞吐率及其調(diào)度方案按此流水調(diào)