【文章內(nèi)容簡(jiǎn)介】 的輸入端連續(xù)地每時(shí)間輸入任務(wù)時(shí)，該流水線會(huì)發(fā)生什么情況？（2） 此流水線的最大吞吐率為多少？如果每輸入一個(gè)任務(wù)，連續(xù)處理10個(gè)任務(wù)時(shí)的實(shí)際吞吐率和效率是多少？（3） 當(dāng)每段時(shí)間不變時(shí)，如何提高該流水線的吞吐率？仍連續(xù)處理10個(gè)任務(wù)時(shí)，其吞吐率提高多少？解：（1）會(huì)發(fā)生流水線阻塞情況。第1個(gè)任務(wù)S1S2S3S3S4第2個(gè)任務(wù)S1S2stallS3S3S4第3個(gè)任務(wù)S1stallS2stallS3S3S4第4個(gè)任務(wù)S1stallS2stallS3S3S4（2）（3）重復(fù)設(shè)置部件吞吐率提高倍數(shù)＝＝ 有一條靜態(tài)多功能流水線由5段組成，加法用5段，乘法用5段，第3段的時(shí)間為2△t，其余各段的時(shí)間均為△t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中?，F(xiàn)要在該流水線上計(jì)算 ，畫(huà)出其時(shí)空?qǐng)D，并計(jì)算其吞吐率、加速比和效率。解：首先，應(yīng)選擇適合于流水線工作的算法。對(duì)于本題，應(yīng)先計(jì)算A1＋BA2＋BA3＋B3和A4＋B4；再計(jì)算(A1＋B1) (A2＋B2)和(A3＋B3) (A4＋B4)；然后求總的結(jié)果。其次，畫(huà)出完成該計(jì)算的時(shí)空?qǐng)D，如圖所示，圖中陰影部分表示該段在工作。由圖可見(jiàn)，它在18個(gè)△t時(shí)間中，給出了7個(gè)結(jié)果。所以吞吐率為： 如果不用流水線，由于一次求積需3△t，一次求和需5△t，則產(chǎn)生上述7個(gè)結(jié)果共需（45+33）△t =29△t。所以加速比為： 該流水線的效率可由陰影區(qū)的面積和5個(gè)段總時(shí)空區(qū)的面積的比值求得： 動(dòng)態(tài)多功能流水線由6個(gè)功能段組成，如下圖：其中，SSSS6組成乘法流水線，SSSS6組成加法流水線，各個(gè)功能段時(shí)間均為50ns，假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端，而且設(shè)置有足夠的緩沖寄存器，若以最快的方式用該流水計(jì)算：（1） 畫(huà)出時(shí)空?qǐng)D；（2） 計(jì)算實(shí)際的吞吐率、加速比和效率。解：機(jī)器一共要做10次乘法，4次加法。 在MIPS流水線上運(yùn)行如下代碼序列：LOOP： LW R1，0（R2） DADDIU R1，R1，1 SW R1， 0（R2） DADDIU R2，R2，4 DSUB R4，R3，R2 BNEZ R4，LOOP 其中：R3的初值是R2+396。假設(shè)：在整個(gè)代碼序列的運(yùn)行過(guò)程中，所有的存儲(chǔ)器訪問(wèn)都是命中的，并且在一個(gè)時(shí)鐘周期中對(duì)同一個(gè)寄存器的讀操作和寫(xiě)操作可以通過(guò)寄存器文件“定向”。問(wèn)：（1） 在沒(méi)有任何其它定向（或旁路）硬件的支持下，請(qǐng)畫(huà)出該指令序列執(zhí)行的流水線時(shí)空?qǐng)D。假設(shè)采用排空流水線的策略處理分支指令，且所有的存儲(chǔ)器訪問(wèn)都命中Cache，那么執(zhí)行上述循環(huán)需要多少個(gè)時(shí)鐘周期？（2） 假設(shè)該流水線有正常的定向路徑，請(qǐng)畫(huà)出該指令序列執(zhí)行的流水線時(shí)空?qǐng)D。假設(shè)采用預(yù)測(cè)分支失敗的策略處理分支指令，且所有的存儲(chǔ)器訪問(wèn)都命中Cache，那么執(zhí)行上述循環(huán)需要多少個(gè)時(shí)鐘周期？（3） 假設(shè)該流水線有正常的定向路徑和一個(gè)單周期延遲分支，請(qǐng)對(duì)該循環(huán)中的指令進(jìn)行調(diào)度，你可以重新組織指令的順序，也可以修改指令的操作數(shù)，但是注意不能增加指令的條數(shù)。請(qǐng)畫(huà)出該指令序列執(zhí)行的流水線時(shí)空?qǐng)D，并計(jì)算執(zhí)行上述循環(huán)所需要的時(shí)鐘周期數(shù)。解：寄存器讀寫(xiě)可以定向，無(wú)其他旁路硬件支持。排空流水線。第i次迭代（i＝0..98）開(kāi)始周期：1＋（i17）總的時(shí)鐘周期數(shù)：（9817）＋18＝1684有正常定向路徑，預(yù)測(cè)分支失敗。第i次迭代（i＝0..98）開(kāi)始周期：1＋（i10）總的時(shí)鐘周期數(shù)：（9810）＋11＝991有正常定向路徑。單周期延遲分支。LOOP: LW R1，0(R2)DADDIU R2，R2，4DADDIU R1，R1，1DSUB R4，R3，R2BNEZ R4，LOOPSW R1，4(R2)第i次迭代（i ＝0..98）開(kāi)始周期：1＋（i 6 ）總的時(shí)鐘周期數(shù)：（986）＋10＝598 假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比如下：條件分支20%（其中的60%是分支成功的）跳轉(zhuǎn)和調(diào)用5%現(xiàn)有一條段數(shù)為4的流水線，無(wú)條件分支在第二個(gè)時(shí)鐘周期結(jié)束時(shí)就被解析出來(lái)，而條件分支要到第三個(gè)時(shí)鐘周期結(jié)束時(shí)才能夠被解析出來(lái)。第一個(gè)流水段是完全獨(dú)立于指令類(lèi)型的，即所有類(lèi)型的指令都必須經(jīng)過(guò)第一個(gè)流水段的處理。請(qǐng)問(wèn)在沒(méi)有任何控制相關(guān)的情況下，該流水線相對(duì)于存在上述控制相關(guān)情況下的加速比是多少？解：沒(méi)有控制相關(guān)時(shí)流水線的平均CPI＝1存在控制相關(guān)時(shí)：由于無(wú)條件分支在第二個(gè)時(shí)鐘周期結(jié)束時(shí)就被解析出來(lái)，而條件分支要到第3個(gè)時(shí)鐘周期結(jié)束時(shí)才能被解析出來(lái)。所以：（1）若使用排空流水線的策略，則對(duì)于條件分支，有兩個(gè)額外的stall，對(duì)無(wú)條件分支，有一個(gè)額外的stall：CPI = 1+20%*2+5%*1 = 加速比S=CPI/1 = （2） 若使用預(yù)測(cè)分支成功策略，則對(duì)于不成功的條件分支，有兩個(gè)額外的stall，對(duì)無(wú)條件分支和成功的條件分支，有一個(gè)額外的stall 1：CPI = 1+20%*(60%*1+40%*2) +5%*1 = 加速比S=CPI/1 = （3）若使用預(yù)測(cè)分支失敗策略，則對(duì)于成功的條件分支，有兩個(gè)額外的stall；對(duì)無(wú)條件分支，有一個(gè)額外的stall；對(duì)不成功的條件分支，其目標(biāo)地址已經(jīng)由PC 值給出，不必等待，所以無(wú)延遲：CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 加速比S=CPI/1 = 在CRAY1機(jī)器上，按照鏈接方式執(zhí)行下述4條向量指令（括號(hào)中給出了相應(yīng)功能部件的執(zhí)行時(shí)間），如果向量寄存器和功能部件之間的數(shù)據(jù)傳送需要1拍，試求此鏈接流水線的通過(guò)時(shí)間是多少拍？如果向量長(zhǎng)度為64，則需多少拍才能得到全部結(jié)果？ V0←存儲(chǔ)器 （從存儲(chǔ)器中取數(shù)：7拍） V2←V0+V1 （向量加：3拍） V3←V2A3 （按（A3）左移：4拍） V5←V3∧V4 （向量邏輯乘：2拍）解：通過(guò)時(shí)間就是每條向量指令的第一個(gè)操作數(shù)執(zhí)行完畢需要的時(shí)間，也就是各功能流水線由空到滿的時(shí)間，具體過(guò)程如下圖所示。要得到全部結(jié)果，在流水線充滿之后，向量中后繼操作數(shù)繼續(xù)以流水方式執(zhí)行，直到整組向量執(zhí)行完畢。 某向量處理機(jī)有16個(gè)向量寄存器，其中V0~V5中分別放有向量A、B、C、D、E、F，向量長(zhǎng)度均為8，向量各元素均為浮點(diǎn)數(shù)；處理部件采用兩條單功能流水線，加法功能部件時(shí)間為2拍，乘法功能部件時(shí)間為3拍。采用類(lèi)似于CARY1的鏈接技術(shù)，先計(jì)算（A+B）*C，在流水線不停流的情況下，接著計(jì)算（D+E）*F。（1） 求此鏈接流水線的通過(guò)時(shí)間？（設(shè)寄存器入、出各需1拍）（2） 假如每拍時(shí)間為50ns，完成這些計(jì)算并把結(jié)果存進(jìn)相應(yīng)寄存器，此處理部件的實(shí)際吞吐率為多少M(fèi)FLOPS？解：（1）我們?cè)谶@里假設(shè)A＋B的中間結(jié)果放在V6中，（A＋B）C地最后結(jié)果放在V7中，D＋E地中間結(jié)果放在V8中，（D＋E）F的最后結(jié)果放在V9中。具體實(shí)現(xiàn)參考下圖：通過(guò)時(shí)間應(yīng)該為前者（（A＋B）C）通過(guò)的時(shí)間：T通過(guò)= (1+2+1)+(1+3+1) =9（拍）（2）在做完（A＋B）C之后，作（C＋D）E就不需要通過(guò)時(shí)間了。V6←A＋B V7←V6C V8←D＋E V9←V8F第4章 指令級(jí)并行 指令級(jí)并行：簡(jiǎn)稱ILP。是指指令之間存在的一種并行性，利用它，計(jì)算機(jī)可以并行執(zhí)行兩條或兩條以上的指令。指令調(diào)度：通過(guò)在編譯時(shí)讓編譯器重新組織指令順序或通過(guò)硬件在執(zhí)行時(shí)調(diào)整指令順序來(lái)消除沖突。指令的動(dòng)態(tài)調(diào)度：是指在保持?jǐn)?shù)據(jù)流和異常行為的情況下，通過(guò)硬件對(duì)指令執(zhí)行順序進(jìn)行重新安排，以提高流水線的利用率且減少停頓現(xiàn)象。是由硬件在程序?qū)嶋H運(yùn)行時(shí)實(shí)施的。指令的靜態(tài)調(diào)度：是指依靠編譯器對(duì)代碼進(jìn)行靜態(tài)調(diào)度，以減少相關(guān)和沖突。它不是在程序執(zhí)行的過(guò)程中、而是在編譯期間進(jìn)行代碼調(diào)度和優(yōu)化的。保留站：在采用Tomasulo算法的MIPS處理器浮點(diǎn)部件中，在運(yùn)算部件的入口設(shè)置的用來(lái)保存一條已經(jīng)流出并等待到本功能部件執(zhí)行的指令（相關(guān)信息）。CDB：公共數(shù)據(jù)總線。動(dòng)態(tài)分支預(yù)測(cè)技術(shù)：是用硬件動(dòng)態(tài)地進(jìn)行分支處理的方法。在程序運(yùn)行時(shí)，根據(jù)分支指令過(guò)去的表現(xiàn)來(lái)預(yù)測(cè)其將來(lái)的行為。如果分支行為發(fā)生了變化，預(yù)測(cè)結(jié)果也跟著改變。BHT：分支歷史表。用來(lái)記錄相關(guān)分支指令最近一次或幾次的執(zhí)行情況是成功還是失敗，并據(jù)此進(jìn)行預(yù)測(cè)。分支目標(biāo)緩沖：是一種動(dòng)態(tài)分支預(yù)測(cè)技術(shù)。將執(zhí)行過(guò)的成功分支指令的地址以及預(yù)測(cè)的分支目標(biāo)地址記錄在一張硬件表中。在每次取指令的同時(shí)，用該指令的地址與表中所有項(xiàng)目的相應(yīng)字段進(jìn)行比較，以便盡早知道分支是否成功，盡早知道分支目標(biāo)地址，達(dá)到減少分支開(kāi)銷(xiāo)的目的。前瞻執(zhí)行：解決控制相關(guān)的方法，它對(duì)分支指令的結(jié)果進(jìn)行猜測(cè)，然后按這個(gè)猜測(cè)結(jié)果繼續(xù)取指、流出和執(zhí)行后續(xù)的指令。只是指令執(zhí)行的結(jié)果不是寫(xiě)回到寄存器或存儲(chǔ)器，而是放到一個(gè)稱為ROB的緩沖器中。等到相應(yīng)的指令得到“確認(rèn)”（即確實(shí)是應(yīng)該執(zhí)行的）后，才將結(jié)果寫(xiě)入寄存器或存儲(chǔ)器。ROB：ReOrder Buffer。前瞻執(zhí)行緩沖器。超標(biāo)量：一種多指令流出技術(shù)。它在每個(gè)時(shí)鐘周期流出的指令條數(shù)不固定，依代碼的具體情況而定，但有個(gè)上限。超流水：在一個(gè)時(shí)鐘周期內(nèi)分時(shí)流出多條指令。超長(zhǎng)指令字：一種多指令流出技術(shù)。VLIW處理機(jī)在每個(gè)時(shí)鐘周期流出的指令條數(shù)是固定的，這些指令構(gòu)成一條長(zhǎng)指令或者一個(gè)指令包，在這個(gè)指令包中，指令之間的并行性是通過(guò)指令顯式地表示出來(lái)的。循環(huán)展開(kāi)：是一種增加指令間并行性最簡(jiǎn)單和最常用的方法。它將循環(huán)展開(kāi)若干遍后，通過(guò)重命名和指令調(diào)度來(lái)開(kāi)發(fā)更多的并行性。 簡(jiǎn)述Tomasulo算法的基本思想。答：核心思想是：① 記錄和檢測(cè)指令相關(guān)，操作數(shù)一旦就緒就立即執(zhí)行，把發(fā)生RAW沖突的可能性減小到最少；② 通過(guò)寄存器換名來(lái)消除WAR沖突和WAW沖突。寄存器換名是通過(guò)保留站來(lái)實(shí)現(xiàn)，它保存等待流出和正在流出指令所需要的操作數(shù)?；舅枷耄褐灰僮鲾?shù)有效，就將其取到保留站，避免指令流出時(shí)才到寄存器中取數(shù)據(jù)，這就使得即將執(zhí)行的指令從相應(yīng)的保留站中取得操作數(shù)，而不是從寄存器中。指令的執(zhí)行結(jié)果也是直接送到等待數(shù)據(jù)的其它保留站中去。因而，對(duì)于連續(xù)的寄存器寫(xiě)，只有最后一個(gè)才真正更新寄存器中的內(nèi)容。一條指令流出時(shí)，存放操作數(shù)的寄存器名被換成為對(duì)應(yīng)于該寄存器保留站的名稱（編號(hào)）。 根據(jù)需要展開(kāi)下面的循環(huán)并進(jìn)行指令調(diào)度，直到?jīng)]有任何延遲。LOOP: F0,0(R1) F0,F0,F2 F4,0(R2) F0,F0,F4 F0,0(R2) DSUBI R1,R1,8 DSUBI R2,R2,8 BNEZ R1,LOOP解：將循環(huán)展開(kāi)兩次，進(jìn)行指令調(diào)度，即可以消除延遲，代碼如下：LOOP： F0，0（R1） F10，8（R1） F0，F(xiàn)0，F(xiàn)2 F10，F(xiàn)10，F(xiàn)2 F4，0（R2） F14，8（R2） F0，F(xiàn)0，F(xiàn)4 F10，F(xiàn)10，F(xiàn)14DSUBI R1，R1，16 0（R2），F(xiàn)0DSUBI R2，R2，16BNEZ R1，LOOP 8（R2），F(xiàn)10 假設(shè)有一條長(zhǎng)流水線，僅僅對(duì)條件轉(zhuǎn)移指令使用分支目標(biāo)緩沖。假設(shè)分支預(yù)測(cè)錯(cuò)誤的開(kāi)銷(xiāo)為4個(gè)時(shí)鐘周期，緩沖不命中的開(kāi)銷(xiāo)為3個(gè)時(shí)鐘周期。假設(shè)：命中率為90%，預(yù)測(cè)精度為90%，分支頻率為15%，沒(méi)有分支的基本CPI為1。（1） 求程序執(zhí)行的CPI。（2） 相對(duì)于采用固定的2個(gè)時(shí)鐘周期延遲的分支處理，哪種方法程序執(zhí)行速度更快？解：（1）程序執(zhí)行的CPI = 沒(méi)有分支的基本CPI（1） + 分支帶來(lái)的額外開(kāi)銷(xiāo)分支帶來(lái)的額外開(kāi)銷(xiāo)是指在分支指令中，緩沖命中但預(yù)測(cè)錯(cuò)誤帶來(lái)的開(kāi)銷(xiāo)與緩沖沒(méi)有命中帶來(lái)的開(kāi)銷(xiāo)之和。分支帶來(lái)的額外開(kāi)銷(xiāo)= 15% * (90%命中10%預(yù)測(cè)錯(cuò)誤4 + 10％沒(méi)命中3)= 所以，程序執(zhí)行的CPI ＝ 1 ＋ = （2）采用固定的2 個(gè)時(shí)鐘周期延遲的分支處理CPI = 1 + 15%2 = 由（1）（2）可知分支目標(biāo)緩沖方法執(zhí)行速度快。 假設(shè)分支目標(biāo)緩沖的命中率為90%，程序中無(wú)條件轉(zhuǎn)移指令的比例為5%，沒(méi)有無(wú)條件轉(zhuǎn)移指令的程序CPI值為1。假設(shè)分支目標(biāo)緩沖中包含分支目標(biāo)指令，允許無(wú)條件轉(zhuǎn)移指令進(jìn)入分支目標(biāo)緩沖，則程序的CPI值為多少？解：設(shè)每條無(wú)條件轉(zhuǎn)移指令的延遲為x，則有：1＋5%x＝ x＝2當(dāng)分支目標(biāo)緩沖命