第五章-標量處理機與流水線

第五章標量處理機與流水線選擇題25，簡答題10,演算題151選擇題★假設一條指令的執(zhí)行過程可以分為“取指令”、“分析”和“執(zhí)行”三段，每一段的執(zhí)行時間分別為Z、2*和陋，順序執(zhí)行n條指令至少需要花費的時間為：3nAt2nAt6nAtnAt答案：C★★假設一條指令的執(zhí)行過程可以分為“取指令”、“分析”和“執(zhí)行”三段，每一段的執(zhí)行時間均為At，連續(xù)執(zhí)行n條指令所需要花費的最短時間約為（假設僅有“取指令”和“執(zhí)行”可重疊并假設n足夠大）：3nAt2nAt—nAt2nAt答案B假設一條指令的執(zhí)行過程可以分為“取指令”、“分析”和“執(zhí)行”三段，每一段的執(zhí)行時間均為At，連續(xù)執(zhí)行n條指令所需要花費的最短時間約為（假設僅有“取指令”和“分析”可重疊并假設n足夠大）：3nAt2nAt3nAt2nAt答案B★★假設一條指令的執(zhí)行過程可以分為“取指令”、“分析”和“執(zhí)行”三段，每一段的執(zhí)行時間分別為At、2At和3At，連續(xù)執(zhí)行n條指令所需要花費的最短時間約為（假設僅有“取指令”和“執(zhí)行:”可重疊并假設n足夠大）：6nAt5nAt3nAt

nAt答案B“執(zhí)行”三段，每2“執(zhí)行”三段，每2At和3At，連續(xù)'、“分析”和“執(zhí)假設一條指令的執(zhí)行過程可以分為“取指令”、“分析”和一段分別只有一個部件可供使用并且執(zhí)行時間分別為At、執(zhí)行n條指令所需要花費的最短時間約為（假設“取指令行”可重疊并假設n足夠大）：6nAt2nAt3nAtnAt答案C★★看下述程序段：k：R0=R1XR4k+1：R6=R5+1k+2：R2=R0XR3k+3：R3=R4-1k+4：R2=R5K+5： 下列哪個數(shù)據(jù)相關沒有在上述程序段中發(fā)生先寫后讀相關寫-寫相關先讀后寫相關以上都不對答案：D★看下述程序段：k：R5=R2k+1：R0=R1XR4k+2：R2=R5+1k+3：R4=R0XR3k+4：R3=R4-1K+5： k和k+2之間發(fā)生的是什么數(shù)據(jù)相關先寫后讀相關寫-寫相關先讀后寫相關只有I只有I、II只有I、III以上都不對答案：C一條流水線可分為k段，各段的執(zhí)行時間都是也，共向該流水線輸入n個任務，第n個任務結束于：nkAt(k+n)kt(k+n-1)(k+n-1kt答案：D★一條流水線的可分為k段，各段的執(zhí)行時間都是At，共向該流水線輸入n個任務，求該流水線實際吞吐率的為：A.TP=nkAtB.TP=n(k+n-1)AtC.TP=1AtD.TP=n(k+n一1)At答案：D★一條流水線可以由以下時空圖來表示，求該流水線的實際吞吐率(假設n=100)123…n-1n123…n-1n123…n-1n123…n-1n—0 時間4ns1MIPS1.04MIPS

0.9709MIPS0.9615MIPS答案：C★★一條4段的流水線可以由以下時空圖來表示，求該流水線的實際吞吐率(假設n=100)0123456時間0123456時間(ns)1MIPS0.165MIPS0.167MIPS0.328MIPS答案：D★12.一條流水線可以由以下時空圖來表示，求該流水線的加速比2346答案：C★一條4段流水線，每段執(zhí)行時間為1ns,求該流水線執(zhí)行100條指令最大效率為：100%96.2%97.1%388%答案：C★如下圖所示的浮點加法流水部件，計算X+Y=Z(i=1,2,,10)，流水線經過多少時鐘后排空(假設時鐘為At)TOC\o"1-5"\h\z16151413答案：B★某動態(tài)流水線有S1、S2、S3和S4段，其特性由下圖所示的預約表來表示t0t1t2t3t4t5t6S1區(qū)XS2XXS3XXS4X問該流水線的沖突向量是：(111111)(110111)(010101)(101010)答案：D★★某動態(tài)流水線有S1、S2、S3和S4段，其特性由下圖所示的預約表來表示

t0t1t2t3t4t5t6S1區(qū)XS2XXS3XXS4X求該流水線的最小平均啟動周期TOC\o"1-5"\h\z6543.5答案：C★17.下圖所示的時空圖對應的處理機為:標量處理機超標量處理機超流水處理機超標量超流水處理機答案：C★一臺(m,n)度的超標量超流水線處理機的指令并行度為mm(n-1)(m-1)(n-1)mn★★★連續(xù)執(zhí)行100條指令時，一臺2度的超標量處理機的最大效率是多少(假設這里的每條流水線是4段標準流水線的流水線)100%97.1%94.3%92.6%答案：C★★★連續(xù)執(zhí)行100條指令時，一臺5度的超標量超流水線處理機的最大效率是多少(假設這里的每條流水線是基于4段標準流水線的超標量流水線)100%97.09%96.34%96.15%答案：C★在不同結構的處理機上運行的矩陣乘法C=AXB，假設A是mXn階的矩陣，B是nXl階的矩陣，則最少需要進行多少次乘法和多少次加法mn,nlmnl,ml(n-1)mnl,mn(l-1)mnl,mnl答案：B★★試比較在指令并行度較低的情況下，具有相同指令并行度的超標量處理機a和超流水線處理機b的效率a>ba=ba<b不能確定(和指令數(shù)有關)答案：A★★一條4個功能段的加一乘靜態(tài)流水線，四個功能段如下所示，計算28A.xB，i=1最少需要經過多少時間，假設運算的結果必須先寫入到緩沖存儲器才能供輸入端使用。并且只有當一個流水線排空后流水線才可以發(fā)生另一種運算。取指譯碼、取數(shù)運算寫結果TOC\o"1-5"\h\z19232527答案：C★★一條4個功能段的加一乘靜態(tài)流水線，四個功能段如下所示，計算28A.xB,i=1最少需要經過多少時間，假設運算的結果有專門的輸出通路連接到輸入端。并且只有當一個流水線排空后流水線才可以發(fā)生另一種運算。取指譯碼、取數(shù)運算寫結果TOC\o"1-5"\h\z16232527答案：B★一臺標量處理機，具有一條5級指令流水線，每級均耗時1個時鐘周期，執(zhí)行一個具有20條指令的代碼序列?，F(xiàn)將此標量處理機改為超流水線處理機，采用同樣基準的指令流水線，不同的是每隔1/4個時鐘周期發(fā)射1條指令，執(zhí)行相同的代碼序列。問前后兩次執(zhí)行的加速比。TOC\o"1-5"\h\z2.42.462.672.75答案：B2問答題★★簡述流水線技術的特點答：流水線技術具有以下特點：⑴流水過程由多個相聯(lián)系的子過程組成，每個過程稱為流水線的“級”或“段”。⑵流水技術適合于大量重復的時序過程?！铩镎垖懗?種亂序流動方式中的數(shù)據(jù)相關，并舉例說明分別在什么情況下發(fā)生（采用設計程序段的方式來說明）答：⑴寫讀相關：例如程序段R0=R1XR4;R2=R0XR3若第二條指令在第一條指令前執(zhí)行則最終的結果與正確結果不同，此時發(fā)生寫讀相關⑵讀寫相關例如程序段R2=R0XR3;R3=R4-1若第二條指令在第一條指令前執(zhí)行則最終的結果與正確結果不同，此時發(fā)生寫讀數(shù)據(jù)相關⑶寫寫相關例如程序段R2=R0XR3;R3=R4-1;R2=R5若指令三在指令一前發(fā)生則最終的結果與正確結果不同，此時發(fā)生寫寫數(shù)據(jù)相關★★在流水線處理機當中，可能有哪幾種操作數(shù)據(jù)相關？這幾種相關分別發(fā)生在什么情況下？解決操作數(shù)相關的基本方法有哪幾種？答：①寫讀相關（先讀后寫）例如程序段R0=R1XR4;R2=R0XR3若第二條指令在第一條指令前執(zhí)行則最終的結果與正確結果不同，此時發(fā)生寫讀相關寫寫相關例如程序段R2=R0XR3;R3=R4-1;R2=R5若指令三在指令一前發(fā)生則最終的結果與正確結果不同，此時發(fā)生寫寫數(shù)據(jù)相關讀寫相關（先寫后讀）例如程序段R2=R0XR3;R3=R4-1若第二條指令在第一條指令前執(zhí)行則最終的結果與正確結果不同，此時發(fā)生寫讀數(shù)據(jù)相關②解決數(shù)據(jù)相關的方法可以分為2大類：延遲執(zhí)行、建立專用路徑★解決流水線結構相關的方法有哪些？寫出2種答：（1） 流水化功能單元（2） 資源重復降低流水線分支損失的方法有哪些？答：在流水線中盡早判斷出分支轉移是否成功盡早計算出分支轉移成功時的PC值(即分支的目標地址)“凍結”“排空”流水線的方法：?預測分支失敗?預測分支成功?延遲分支★★★試寫出延遲分支的3種調度策略，并對其進行評價答：從前調動分支必須不依賴于被調度阿指令，總是可以有效提高流水線的性能從目標處調度若分支轉移失敗，必須保證被調度的指令對程序的執(zhí)行沒有影響，可能需要復制調度指令。分支轉移成功時，可提高流水線性能。單由于復制指令，可能加大程序空間從失敗處調度若分支轉移成功，必須保證被調度的指令對程序的執(zhí)行無影響。分支轉移失敗時，可提高流水線性能★簡述單流水線標量處理機、超標量處理機、超流水線處理機、超標量超流水線處理機的特點答：具有標量數(shù)據(jù)表示和標量指令系統(tǒng)的處理機稱為標量處理機，通常只有一條流水線，一個時鐘周期內可以完成一條指令。超標量處理機一般具有多于一條的流水線，一臺m度的超標量處理機可同時發(fā)射m條指令，指令的發(fā)射等待時間為1個時鐘，指令的并行度為m。超流水線處理機一般具有一條k段的超流水線，一臺n度的超流水處理機可以同時發(fā)射一條指令，指令的發(fā)射等待時間為1/n個時鐘周期，每個時鐘周期共發(fā)射n條指令。指令的并行度為n。超標量超流水處理機一般具有多余1條的超流水線，一臺m,疽度的超標量超流水處理機可以同時發(fā)射m條指令，指令的發(fā)射等待時間為1/n個時鐘周期，每個時鐘周期共發(fā)射mn條指令，指令的并行度為mn。畫圖說明什么是流水線“瓶頸”簡述解決流水線瓶頸的方法答.□.上圖中的S3段就是流水線瓶頸將流水線的“瓶頸”部分再細分重復設置瓶頸流水段，讓多個瓶頸流水段并行工作★什么是靜態(tài)流水線？什么是動態(tài)流水線答：靜態(tài)流水線：在同一時間內，多功能流水線種的各個功能只能按照一種固定的方式連接，實現(xiàn)一種固定的功能。只有當按照這種連接方式工作的所有任務都流出流水線之后，多功能流水線才能重新盡心連接，以實現(xiàn)其他功能。動態(tài)流水線：在同一時間內，多功能流水線種的割斷可以按照不同的方式連接，同時執(zhí)行多種功能。其中流水線種各個功能部件不能發(fā)生沖突。★★程序中有哪兩類相關，分別可以采取什么方法來解決答：：程序中可能出現(xiàn)下兩類相關數(shù)據(jù)相關數(shù)據(jù)相關指在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址偏移量等是前面指令的執(zhí)行結果，則必須等待前面的指令執(zhí)行完成，并把結果寫道主存或通用寄存器中之后，本條指令才能開始執(zhí)行。可以采取設置專用數(shù)據(jù)通路、延遲執(zhí)行等方法來解決數(shù)據(jù)相關?？刂葡嚓P控制相關指由條件分支指令、轉子程序指令、中斷等引起的相關。可以采取靜態(tài)分支預測技術、動態(tài)分支預測技術、提前形成條件碼等來解決控制相關。3演算題★★2.一條流水線連接圖如下所示，畫出100條指令連續(xù)通過該流水線的時空圖，并計算該流水線的吞吐率和最大吞吐率。（其中At=1ns）解：TP=100/(3*100+6-3)=0.3303MIPS(分母是305，300都不對)TPmax=1/3=0.333333MIPS3.一條流水線連接圖如下所示，畫出100條指令連續(xù)通過該流水線的時空圖，并計算該流水線的加速比。（其中At=1ns）解：解：順序執(zhí)行的時間為T0=6X100=600ns采用流水方式執(zhí)行的時間為T1=3X100+6-1=305ns加速比S=T0/T1=600/305=1.97★★★連續(xù)執(zhí)行100條指令時，一臺2度的超標量超流水線處理機的最大效率是多少(假設這里的每條流水線是基于5段標準流水線的超標量流水線)，畫出時空圖來說明解：效率由以下方法計算100*5空圖來說明解：效率由以下方法計算100*5心*(100+4.5))=95.69%用1條5個功能段的浮點加法器流水線計算F=ZA,。每個功能段的延時均i=1相等，流水線的輸出端與輸入端之間有直接的數(shù)據(jù)通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算工作，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率解：假設每個功能段的延遲時間為^t，則F=ZA=Ka+A）+（A+A）+（A+A）+（A+A）+（A+A）］i 1 1 2 6 324 8 536 9 748 7 95 10i=1上式中加法右下側地座標表示這是第幾個加法時空圖略吞吐率為：TP=9/20At=0.45—At加速比為：Sp=9x5/20=2.25設有一個15000條指令地程序在一臺時鐘頻率為25MHz的線性處理機上執(zhí)行。假設該指令流水線有5段，并且每個時鐘周期發(fā)射一條指令。忽略由于轉移指令和無序執(zhí)行造成的損失。用該流水線執(zhí)行這一程序，并用通過延遲時間與其相等的一個等效非流水線處理機執(zhí)行同一程序，將兩者加以比較，并計算其加速比。該流水線處理機的效率和吞吐率是多少？解：(a) 等效的非流水處理機執(zhí)行一條指令需要的時間是5個時鐘周期。按照加速比定義，應有onk 15000x5 75000。4QQ86

k+(n-1)5+(15000-1)15004 .(b)效率為_0.QQQ7E_n,_15000一k\k+(n-1)]_15004_0.QQQ7(c)吞吐率為15004gkf)_皿、2*"C/)_24-皿150047.設有圖3.5所示的浮點加法流水部件，其中第7.設有圖3.5所示的浮點加法流水部件，其中第2功能的延遲時間是3也,其余功能段都是At試提出改進這條流水線的2種方法，并計算改進后的效率（針對100個任務）。解：改進方案1：將S2細分為3個功能斷Z1，Z2，Z3，分別有At的延遲時間，則現(xiàn)在流水線有6個功能段，效率為_0.9524E_(1+3+￡+1)x100一(6+100-1)x6_0.9524改進方案2：改進方案2：另外補充與S2相同的2個功能段，如下圖所示E_3700+102)_0.95714x(100+6-1)某動態(tài)流水線有S1、S2、S3和S4段，其特性由下圖所示的預約表來表示t0t1t2t3t4t5t6S1XXS2XXS3XXS4XX確定禁止表F和沖突向量C畫出狀態(tài)圖，確定其最小平均等待時間和最大吞吐率解：由預約表可以看出，引起沖突的啟動時間是2,4,5,則沖突向量C=（11010）o此流水線的狀態(tài)圖如下所示要找出最小平均等待時間，首先要從狀態(tài)圖種找出迫切循環(huán)。迫切循環(huán)的定義是，從它們各自的初始狀態(tài)輸出的邊緣都具有最小等待時間。從狀態(tài)圖中可以看出（3）和（1，6）是迫切循環(huán)，（1，6）平均為3.5。所以最小平均等待時間為3此時最大吞吐率為MAL的倒數(shù)為33.3%k:k:k+1:k+2:k+3:k+4:其中，器。下列匯編代碼在一臺3段流水線處理機上執(zhí)行，每一段都有（相關）檢測和分解。這3段是取指令、取操作數(shù)（根據(jù)要求取一個或多個）和執(zhí)行（包括寫回操作）。試說明在代碼執(zhí)行中所有可能的相關情況。INCR0MUL ACC,R0STORE R1,ACCADD ACC,R0STORE M,ACC雙操作數(shù)指令，第1個操作數(shù)是目的寄存器，第2個操作數(shù)是源寄存1234567IFINCMULSTOREADDSTOREOFR0ACC,R0ACCACC,R0ACCEXR0ACCR1ACCM由此可以看出在t3時刻，發(fā)生先寫后讀相關在t4時刻，發(fā)生先寫后讀相關在t6時刻，發(fā)生先寫后讀相關。某動態(tài)流水線有S1、S2、S3、S4和S5段，其特性由下圖所示的預約表來表t0t1t0t1t2S1XS2XS3XS4S5Xt3t4t5t6XXXXX確定禁止表F和沖突向量C畫出狀態(tài)圖，確定其最小平均等待時間和最大吞吐率從簡單循環(huán)中找出迫切循環(huán)使用此流水線時，列出可允許的最小恒定循環(huán)如果使用最小恒定循環(huán)，則吞吐率是多少？解：禁止等待時間為：3,4,5沖突向量為：（11100）簡單循環(huán)如下（1,1,6），（2,6），（6），（1,6）迫切（最小啟動）循環(huán)為（1,1,6）最小平均等待時間為（1+1+6）/3=2.67最小恒定循環(huán)為（6）設該流水線的時鐘周期為，，則最大吞吐率為maxMALxt8t使用最小恒定循環(huán)時，流水線的吞吐率為TP=—6t★★★在不同結構的處理機上運行8X8的矩陣乘法C=AXB，計算所需要的最短時間。只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時間。加法部件和乘法部件的延遲時間都是3個時鐘周期，另外，加法指令和乘法指令還要經過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為0。各操作部件的輸出段有直接數(shù)據(jù)通路連接到有關操作部件的輸入端，在操作部件的輸出端設置有足夠容量的緩沖寄存器。求：處理機那只有一個通用操作部件，采用順序方式執(zhí)行指令的時間單流水線標量處理機，有一條2個功能的靜態(tài)流水線，流水線每個功能段的延遲時間均為1個時鐘周期，加法操作和乘法操作各經過3個功能段解：共需要進行512次乘法和448次加法，需要時間(512+448)*20*(3+1+1)=96000ns先進行所有的乘法，512次乘法，需要512+5—1=516個時鐘周期。再進行所有的乘法，每出一個C矩陣中的結果需要考慮時鐘相關，即8個數(shù)連加需要18個時鐘周期，出64個數(shù)就需要16X64=1152個時鐘周期，則供需要516+1152=1668個時鐘周期，則需要166800ns12.某RISC機有8個通用寄存器，有一條4級流水線取指譯碼、取數(shù)運算寫結果試編寫出8個通用寄存器那所存的數(shù)據(jù)之和的程序，要求此程序的執(zhí)行時間最短，并計算出時間(假設，每級流水線的周期為50ns，加法運算的結果只能送回寄存器，而不能再傳送途中被截取，另外假設運算的結果可以直接送到輸出端)解：程序如下：ADDR1,R2ADDR3,R4ADDR5,R6ADDR7,R8ADDR1,R3ADDR5,R7ADDR1,R5指令的執(zhí)行周期數(shù)為13，共需要13X50=650ns13.一條具有k個流水段的流水線，由于條件轉移指令的影響，再最壞的情況下，每一次條件轉移將造成k-1個時鐘的“斷流”。另外，假設條件轉移指令再一般程序中所占的比例為p，轉移成功的概率為q。對于一個由n條指令組成的程序，總的執(zhí)行時間是多少解：由于條件轉移需要額外增加的時鐘周期數(shù)是pqn(kfAt因此，這n條指令的總執(zhí)行時間是：T =(n+k-1)At+npq(k-1)At14.某RISC機有16個通用寄存器A1?A8,B1?B8,有一條如下所示的加一乘雙功能靜態(tài)流水線，加法時按照1、2、3、5連接，乘法時按照1、2、3、4、5連接。流水線的輸出可直接送到其輸入端或存入緩沖器，不計期間的傳送延遲，操作數(shù)可連續(xù)提供。取指譯碼、取數(shù)運算1運算2寫結果試編寫出求丈A.xB的程序，要求此程序的執(zhí)行時間最短，并計算出時間i=1(假設，每級流水線的周期為50ns)解：程序如下：FORi=1TO8DOMULAi,BiADDA1,A2ADDA3,A4ADDA5,A6ADDA7,A8ADDA1,A3ADDA5,A7ADDA1,A5乘法指令的執(zhí)行周期數(shù)為8+5-1=12，共需要600ns加