Tomasulo算法實(shí)驗(yàn)報(bào)告材料

1、高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Tomasulo算法實(shí)驗(yàn)報(bào)告Tomasulo算法實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模?）加深對(duì)指令集并行性及開發(fā)的理解。（2）加深對(duì)Tomasulo算法的理解。.（3）掌握Tomulo算法在指令流出、執(zhí)行、寫結(jié)果各階段對(duì)浮點(diǎn)操作指令以及l(fā)oad和store指令進(jìn)行什么處理。（4）掌握采用了 Tomasulo算法的浮點(diǎn)處理部件的結(jié)構(gòu)。（5）掌握保留站的結(jié)構(gòu)。（6）給定被執(zhí)行代碼片段，對(duì)于具體某個(gè)時(shí)鐘周期，能夠?qū)懗霰Ａ粽?、指令?態(tài)表以及浮點(diǎn)寄存器狀態(tài)表內(nèi)容的變化情況。二、實(shí)驗(yàn)平臺(tái)采用Tomasulo算法模擬器。Tomasulo算法基本思想：記錄和檢測(cè)指令相關(guān)，操作數(shù)一旦就緒就立即執(zhí)行，把發(fā)生RA

2、W沖突的可能性減少到最??；通過寄存器換名來消除 WAR沖突 和WAW沖突。三、實(shí)驗(yàn)內(nèi)容和步驟實(shí)驗(yàn)一(1) 學(xué)會(huì)使用Tomasulo算法。假設(shè)浮點(diǎn)功能部件的延遲時(shí)間為加減法2個(gè)周 期，乘法10個(gè)時(shí)鐘周期，除法40個(gè)時(shí)鐘周期，load部件2個(gè)時(shí)鐘周期。 對(duì)于下面的代碼段，給出當(dāng)指令 MUL.D寫結(jié)果時(shí)，保留站、load緩沖 器以及寄存器狀態(tài)表中的內(nèi)容。L.DF6, 24(R2)L.DF2, 12(R3)MUL.DF0, F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2 按步進(jìn)方式執(zhí)行上述代碼，利用模擬器的“小三角按鈕”的對(duì)比顯示功能， 觀察每一個(gè)時(shí)鐘周期前

3、后各信息表中內(nèi)容的變化情況。(2) 對(duì)與上面相同的延遲時(shí)間和代碼段。 給出在第3個(gè)時(shí)鐘周期時(shí)，保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi) 容。 步進(jìn)5個(gè)時(shí)鐘周期，給出這時(shí)保留站、load緩沖器以及寄存器狀態(tài)表中的 內(nèi)容。 再步進(jìn)10個(gè)時(shí)鐘周期，給出這時(shí)保留站、load緩沖器以及寄存器狀態(tài)表 中的內(nèi)容。實(shí)驗(yàn)二假設(shè)浮點(diǎn)功能部件的延遲時(shí)間為加減法 3個(gè)時(shí)鐘周期，乘法8個(gè)時(shí)鐘周期， 除法40個(gè)時(shí)鐘周期。對(duì)于下面的代碼重復(fù)實(shí)驗(yàn)一中步驟(2)的內(nèi)容。編寫代碼如下:L.DF6, 28(R2)ADD.DF2,F4,F8MUL.DF0, F2,F4SUB.DF8,F6,F2DIV.DF12,F0,F6ADD.

4、DF10,F8,F2四、實(shí)驗(yàn)結(jié)果及分析說明：RX表示寄存器X的內(nèi)容，My表示存儲(chǔ)器存儲(chǔ)單元y的內(nèi)容:實(shí)驗(yàn)一RER2J+24 E.R3 + 12 M3=ri-M2MI5=M2*EF4 M6=m5/hll實(shí)驗(yàn)二Ml=MRR2+28 M2=KLF4+HF9 M3-F11-MZM4=M3+M2wiB=ryi5/Mi實(shí)驗(yàn)一結(jié)果浮點(diǎn)功能部件的延遲時(shí)間為加減法 2個(gè)周期，乘法10個(gè)時(shí)鐘周期，除法40個(gè)時(shí)鐘周期，load部件2個(gè)時(shí)鐘周期，根據(jù)實(shí)驗(yàn)結(jié)果可知程序全部執(zhí)行完需要57個(gè)時(shí)鐘周期指令流出執(zhí)行寫結(jié)果L. HFS j 24123AL.r垃MJ25MULT DF0 j 72 « F43&&q

5、uot;*15ISSUE,5F5 ； F& , FE4汁DIV. DF10 FO/ F&517*565TABU DF& j ?3> FE59"l0111）當(dāng)指令MUL.D寫結(jié)果時(shí)，保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi)容。根據(jù)實(shí)驗(yàn)結(jié)果得出MUL.D寫結(jié)果時(shí)是第16個(gè)周期，此時(shí)各部件的狀態(tài)如下所示： 其指令執(zhí)行狀態(tài)如下:指令旄出執(zhí)行寫結(jié)果L. DF5 >膽)14L DF2 > 12 CHS)25MULT.® TO > F2- F43516SUB D 陽-F24SDTV D F10 > PD , F6呂HDD D F&

6、amp; , FS , F2&91011 其保留站內(nèi)容如下:T ime名稱Elisy0PVj弧QjQkAidlNoAdd2NoAdd3NoMultiWoHui 12TesDIV.DM5Ml分析：此時(shí)SUB.D、ADD.D和MULtl已經(jīng)執(zhí)行完畢，所以Busy狀態(tài)為“no ”,而DIV.D還未執(zhí)行完，所以保留站 Mult2仍處于忙碌狀態(tài)。 load緩沖器內(nèi)容：Bus 5地址值L-oaidlHoNoHo分析：此時(shí)Loda緩沖器處于閑置狀態(tài)，因?yàn)橹挥星皟蓷l指令需要計(jì)算地址, 而前兩條指令在第5個(gè)周期時(shí)已經(jīng)執(zhí)行完，所以指導(dǎo)程序運(yùn)行完的所有周期中該 部件都是處于閑置狀態(tài)的。 寄存器內(nèi)容：字段oF

7、F67aF10F12目1MultiLoad2Xdd2AddlMnlt2直M5M2n4M32）第3個(gè)時(shí)鐘周期時(shí)，保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi)容 指令狀態(tài)指令硫出執(zhí)行寫結(jié)果j 口re / 輕隹2)L七先L, DFE IE to)2MULT D F0 陀珂SUE L FB n FEBIV. L no f FO f F5AJD.D F& j FS j FZ 保留站內(nèi)容Time名稱BusyOpVjVkAdilHeAddZBoAdd3ultl論MULT.DRF4ult2Ho分析：第3個(gè)時(shí)鐘周期時(shí)MULT.D指令流出，所以保留站的 Multi處于忙碌狀態(tài) load緩沖器內(nèi)容:名稱Bu

8、sy地址值LoadlYoER2+24MRR2+24IjoadSY注EK3+12Loads恥分析：第3個(gè)時(shí)鐘周期時(shí)前兩條去操作數(shù)的指令還為執(zhí)行完，所以load緩沖器的前兩個(gè)緩沖器處于忙狀態(tài)。 寄存器字段FOF2F4F6F6F1CF1ZQiMialtlLc aLo ad.1mr.3）步進(jìn)5個(gè)時(shí)鐘周期，給出這時(shí)保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi) 容。步進(jìn)5個(gè)時(shí)鐘周期后，是程序執(zhí)行的第 8個(gè)周期，此時(shí)各部件的狀態(tài)如下: 指令狀態(tài)（此時(shí)SUB.D指令恰好執(zhí)行完成）I姐令痂出執(zhí)行i寫結(jié)臬FE - 24CR2)14ldF2 - 12 (R3)234EMULT, DFO > F2 F43sub

9、. dFZ40hiv DF1Q j FP j F65ADD DF6 j FS FZ6 保留站內(nèi)容Time名禰Bus/ OpVjYXQQkAddl|NoAddZ丫黠O.DM3H2Wo7WiiltlYeSIflULT. DM2rmUult2DIY.DMlMulti分析：第8個(gè)周期時(shí)L.D和SUB.D三條指令執(zhí)行完畢，其余三條未完成,所以保留站中仍有其他三條的信息 load緩沖器內(nèi)容:名稱Busy地址值Laa.d.1NqNcLoad3Ho 寄存器內(nèi)容FOF2F4F6F8fioF12MultiLo ad2脫32MilIflultS值 -JMl4）再步進(jìn)10個(gè)時(shí)鐘周期，這時(shí)處于執(zhí)行周期的第18個(gè)周期，這

10、時(shí)保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi)容: 指令狀態(tài)指令硫出執(zhí)存寫結(jié)果L. JE& j 24 CRZJ1L.EP2 j 12 CR3)234MULT D70 j F£ > F4361516SUEDj fe陀16T8 DIV. Drio ra j fg5ADD.Jr& j re » fe&曠1口IL分析：第18個(gè)周期時(shí)只剩下DIV.D指令未執(zhí)行完，并且此時(shí)正處于執(zhí)行的等待階段。 保留站Tim電名稱Busy°PVkAddlNoAdd2恥，仙KoMultiNo38Mill 12162EIV.DMSMl分析：此時(shí)其余指令全部執(zhí)行完畢，

11、只有DIV.D還未執(zhí)行完，所以只有保留站Mult2仍處于忙碌狀態(tài)。 Load緩沖器名稱Busy地址值Lo &dlNoLoadZWoLa aJ3No 寄存器FQF4F6flUF12QiMultiLoAidlMult2值MStJIZM4M3IrhL_實(shí)驗(yàn)二結(jié)果浮點(diǎn)功能部件的延遲時(shí)間為加減法 3個(gè)周期，乘法8個(gè)時(shí)鐘周期，除法40 個(gè)時(shí)鐘周期，load部件2個(gè)時(shí)鐘周期。根據(jù)實(shí)驗(yàn)結(jié)果可知該程序需要 56個(gè)周期 執(zhí)行完成。（分析與實(shí)驗(yàn)一類似，不再贅述）扌旨令流出執(zhí)行寫結(jié)果L. DF6 , SB Gi2)123斗妞D，DF2 > F4 ji F3£6MULT. Lro f鹽* f斗3

12、r-孕15JSUB. Dpg j re >410DI叭Dns j fo j re51&"55&ADD. Drioj F8 j FE&1113nK（1 ）第3個(gè)時(shí)鐘周期時(shí)，保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi)容 指令狀態(tài)1揩令猛出執(zhí)齊寫結(jié)果L. BF& , 23 噸123ADD. UF2 f FS FS2HULT. DFO >F43SUE 0FS FG F2DI¥ BFIE FO > FSADLI. DF10 f F3 , F2 保留站Tin名稱BusyOpVIQjQk2AddlYe:ADD, 5RF4RF6砒NoAd

13、d3ffoMultiYesMULT DRF4Adil血Lt2Ho load緩沖器內(nèi)容:名稱BTisy地址值Lo a.dlYesRR2+2BMRLR2+£6Load2血La.d3No 寄存器內(nèi)容宇段FOF2F4FSF8F10FL2QirLitiAddl|Loa.dl值【G(2)步進(jìn)5個(gè)時(shí)鐘周期，給出這時(shí)保留站、load緩沖器以及寄存器狀態(tài)表中的內(nèi)容 指令狀態(tài):指第疣出執(zhí)行寫結(jié)果L. DF&j ®2)12飛4aED. D F2j F4j FS26IIULT D FOj F2j F43SUB. D F8j F6j F24hiv D F12 FD , TB5AID,D Fl

14、Of ra J TZ6 保留站內(nèi)容:Time名輸Vj矗QjAddlADD.DM2Add21Ad(£SUB.DMlK2Add3HoheMultiMULT.TiF4lesDIDMlMulti Load部件內(nèi)容:名稱Btisst地址值Lo*dlNoLoad2 寄存器部件內(nèi)容:字段FO?2F1F5FBF1Q?12QiMultiAddlLcadlU32AddlMult2值HZMl(3)再步進(jìn)10個(gè)時(shí)鐘周期，給出這時(shí)保留站、load緩沖器以及寄存器狀態(tài)表 中的內(nèi)容。 指令狀態(tài):指歹探岀執(zhí)LDFE i 2E®2)1234ADD.D72 > F4 j FB23%BMVLT.BTO &

15、gt; F2 j F43T*1415SUB DIB J F6J F24ra10MV.D712j FO, F651曠ADD.DPIOj F0 > F26iri314 保留站內(nèi)容:Time名稱BusyOpVjVkQjQkMoNo砂NcMultiNoMui 1214SDIV. IM5Ml Load部件內(nèi)容:名暢Busy地址值Lo a.dlNcLo a.32KcIloHe 寄存器部件內(nèi)容:字段10F2T413F10rizQiMultiAddlAdd2UilMult 2值MSM2MlM3M4五、實(shí)驗(yàn)總結(jié)1. 對(duì)并行性的理解流水線使指令重疊并行執(zhí)行，可以達(dá)到提高性能的目的，如果指令間沒有相關(guān)性，可以

16、并行執(zhí)行，例如程序中前兩個(gè)指令的流出和執(zhí)行階段，第二周期時(shí)第二條LOAD.D的流出和第一條LOAD.D的執(zhí)行同時(shí)進(jìn)行，從而提高了指令執(zhí)行 的效率。但是由于程序之間的相互依賴性，使得流水線中指令流的下一條指令不 能在指定的時(shí)鐘周期執(zhí)行，這就是流水線沖突。因此為了更好的使程序的運(yùn)行按 時(shí)完成，我們必須采取相應(yīng)的措施解決流水線相關(guān)引起的問題，而Tomasulo算法就是解決該問題的方法之一。2、對(duì)Tomasulo 算法的理解Tomasulo算法的核心思想是：記錄和檢測(cè)指令相關(guān)，操作數(shù)一旦就緒 就立即執(zhí)行，把發(fā)生RAW沖突的可能性減少到最小；通過寄存器換名來消除 WAR沖突和WAW沖突。使用Tomasu

17、lo算法的流水線需3段：（1）流出：從指令隊(duì)列的頭部取一條指令。 如果該指令的操作所要求的保留站有空閑的，就把該指令送到該保留站（設(shè)為 r ）。 如果其操作數(shù)在寄存器中已經(jīng)就緒，就將這些操作數(shù)送入保留站 如果其操作數(shù)還沒有就緒，就把將產(chǎn)生該操作數(shù)的保留站的標(biāo)識(shí)送入保留站 ro 一旦被記錄的保留站完成計(jì)算，它將直接把數(shù)據(jù)送給保留站 r。完成對(duì)目標(biāo)寄存 器的預(yù)約工作，如果沒有空閑的保留站，指令就不能流出。（2）執(zhí)行 當(dāng)兩個(gè)操作數(shù)都就緒后，本保留站就用相應(yīng)的功能部件開始執(zhí)行指令規(guī)定的操 作。 load和store指令的執(zhí)行需要兩個(gè)步驟：計(jì)算有效地址（要等到基地址寄存器就緒）；把有效地址放入load或store緩沖器。（3）寫結(jié)果功能部件計(jì)算完畢后，就將計(jì)算結(jié)果放到CDB上，所有等待該計(jì)算結(jié)果的寄存器和保留（包括store緩沖器）都同時(shí)從CDB上獲得所需要的數(shù)據(jù)。3、Tomasulo算法的浮點(diǎn)處理部件的結(jié)構(gòu)Tomasulo算法的浮點(diǎn)處理部件包括：保留站（浮點(diǎn)加法器有3個(gè)保留站：ADD1，ADD2，ADD3 ;浮點(diǎn)乘法器有兩個(gè)保留站： MULTI，MULT2 ）、公共數(shù)據(jù)總線CDB、load緩沖器和store緩沖器、浮點(diǎn)寄存器FP、指令隊(duì)列、運(yùn) 算部件（浮點(diǎn)加法器和浮點(diǎn)乘法器）4、保留站的結(jié)構(gòu)每個(gè)保留站有以下6個(gè)字段： Op :要對(duì)源操作數(shù)進(jìn)行的