北郵 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)實(shí)驗(yàn)四-使用MIPS指令實(shí)現(xiàn)冒泡排序
計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書 實(shí)驗(yàn)使用 指令實(shí)現(xiàn)冒泡排序法 實(shí)驗(yàn)?zāi)康?()掌握靜態(tài)調(diào)度方法 ()增強(qiáng)匯編語言編程能力 ()學(xué)會(huì)使用模擬器中的定向功能進(jìn)行優(yōu)化 實(shí)驗(yàn)平臺(tái) 實(shí)驗(yàn)平臺(tái)采用指令級(jí)和流水線操作級(jí)模擬器 實(shí)驗(yàn)內(nèi)容和步驟 ()自行編寫一個(gè)實(shí)現(xiàn)冒泡排序的匯編程序,該程序要求可以實(shí)現(xiàn)對(duì)一維整數(shù)數(shù)組 進(jìn)行冒泡排序 冒泡排序算法的運(yùn)作如下 ①比較相鄰的元素。如果第一個(gè)比第個(gè)大,就交換他們兩個(gè) ②對(duì)每一對(duì)相鄰元素作同樣的工作,從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn) 最后的元素應(yīng)該會(huì)是最大的數(shù) ③針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè) ④持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟,直到?jīng)]有仼何一對(duì)數(shù)字需要比較。 要求數(shù)組長(zhǎng)度不得小于 代碼見附錄。 ()啟動(dòng) ()載入自己編寫的程序,觀察流水線輸出結(jié)果。 程序的目的是對(duì)12,34,17,5,89,15,9,22,16,19,21的進(jìn)行冒泡排序。 程序執(zhí)行統(tǒng)計(jì)情況:共128個(gè)周期,其中RAW沖突占495個(gè)周期,占比40.30% 叫統(tǒng)計(jì) 計(jì) L總 行周期總數(shù):1 TT了58↓ 指爾數(shù) 指令總款的百分認(rèn) 其巾 硬件配置 分支成功 分支指令教的百分比:91.6083粥% 內(nèi)有里:103B 分支指令款的百分比:6. 加法器十?dāng)?shù):1 執(zhí)行間〔月周款 我法器個(gè)類1 執(zhí)行刊問(周魏數(shù)) 1 cad stor指令 軌行封間后數(shù) 指令總款的百分比:24.4898 定向機(jī)制:不采月 工:144 占1。 d/rtor指 俘頓〔周期 n 月期總數(shù)的百比:4.3944% 乎點(diǎn)指僉 10ad亭頓:132 占所有停百外∴.乇6675 占指袋總數(shù)的它公比:0 浮點(diǎn)亭頓: 占所有F停百分七 A售頓:0 上周期包數(shù)的百分比:0% 加法 占浮點(diǎn)拎令勤的分比: 結(jié)構(gòu)停項(xiàng) 上周期忽數(shù)的百分比:0% 占浮點(diǎn)指令勤的分 控制停聽:14 月明蘭教的百六比:11.64459 除法:0 占浮馬指勃的分比 自陷停哂 上周期這數(shù)的百分比:0.08 俘頓周期總數(shù):周期忽數(shù)的百分比:52.0383 指令爾數(shù):1占指令總數(shù)公比:01788 部分流水線周期圖: 前11個(gè)周期 ADIIU Sr9, r0.116 工r DIIV Sr4, r-0,0 工n 5, ELIZ Sr7 PASS TALL 后11個(gè)周期: 4 r20.0(x3 $r26.24(x 工 2727( r2832($x IMIAMD ()使用定向功能再次執(zhí)行代碼,與剛才執(zhí)行結(jié)果進(jìn)行比較,觀察執(zhí)行效率的不同 統(tǒng)計(jì) 叫統(tǒng)計(jì) 分支指 執(zhí)行周期己數(shù):92 指令條數(shù):14 占指令總教的百分比::41973 T限行了漸指 分支戊功:13 占分支指數(shù)百冷比:3.印09% 硬件配置: 與分支指冷教予百恰E, 1608% 內(nèi)存容:4CB 加法器個(gè)數(shù):1 熱行時(shí)間(周期數(shù)〕 指 法器個(gè)款:1 訂時(shí)間周蝴素 指令殺梨:144 占指念總數(shù)的白分比:2.4E 除法器個(gè)勞 行時(shí)間(月期數(shù))10 機(jī)制:朵用 占 oad store指窆數(shù)的百分 信頓(周期熱) FA信中:279 古周期總熱的百分比:E2.1664 點(diǎn)指令: 指令條數(shù):口 占指金總￥百比 1oad寫:EE 占祈有RA俘頓的百外比:3:.5739% 浮點(diǎn)頓:0 斫有EA停頓的百分比 加法:0 占點(diǎn)指令勤百分比:0% WAH信中:0 占周劁總款的白分比:0 乘法:0 浮點(diǎn) 結(jié)構(gòu)停頂: 占周與總勤的面分比:0 蹤法:0 百計(jì)比:0% 控制停頃:14 占局賬總婁百分:15.18U 白陷項(xiàng):1 占周總數(shù)的百分比:0.1061571 自指 停期數(shù):353凸周總的百分比:37.47346% 占指令總數(shù)的百分比:3.170068 程序執(zhí)行統(tǒng)計(jì)情況:共942個(gè)周期,其中RAW沖突占209個(gè)周期,占比22.18% 采用定向技術(shù)之后,和不采用定向技術(shù)相比:執(zhí)行的時(shí)鐘周期總數(shù)減少了286個(gè)。執(zhí)行 效率是定向前的1228/942=1.30(倍) ()采用靜態(tài)調(diào)度方法重排指令序列,減少相關(guān),優(yōu)化程序 優(yōu)化后的代碼見附錄。優(yōu)化部分 LOOP2 LW$r5,0($3) #載入A1[j LW$r6,4($3) #載入A1[j+1] DSUB Sr7, $r5, $r6# Allj]- Al[j+1] BLTZ$r7,PASS#A1[訂<A1[計(jì)1],跳轉(zhuǎn)到PASS SW$r6,0($r3) #A1[j〉A(chǔ)1[j1],交換 SW$r5,4($r3) PASS ADDIU Sr4, Sr4, 1 #j+=1 ADDIU r3, r3, 4 DSUB r8, r2, Sr4 i 主要是DSUB$r7,$r5,$r6#A1[-AL[j+1]和BLTZ$r7,PASS這兩條指令存在 RAW相關(guān),分支指令后面部分的執(zhí)行順序依靠前面的結(jié)果。如果能夠采取前瞻執(zhí)行的方 式,減少?zèng)_突,就能減少周期的延遲,于是對(duì)原代碼進(jìn)行修改,調(diào)整指令的執(zhí)行順序以 及結(jié)構(gòu)。 主要收變?nèi)缦滤? LOOP2 LW$r5,0($r3) #載入A1[ LW$r6,4($r3) #載入A1[j+1 #前瞻執(zhí)行 ADIU$r4,$r4,1#j+=1 DSUB $r7, $r5, r6# Allj]-Al[j+1] DSUB r8, $r2, Sr4 # i-j BLZ$r7, NOSWAP#A1[訂<A1j1],跳轉(zhuǎn)到 NOSWAP SW$r5,4($r3)#A1[j〉A(chǔ)1[j+1],交換 SW$r6,0($r3) NOSWAP AdDIN Sr3, r3, 4 執(zhí)行結(jié)果 口統(tǒng)計(jì) 執(zhí)行期數(shù): 指令條數(shù):14 占指令總數(shù)￥百分比;22.3]889 83217 占分支指會(huì)數(shù)的百分 行時(shí)間(店速 1oad/tre指 執(zhí)行時(shí)問圩款 指會(huì)條數(shù): 占指會(huì)總數(shù)￥百分比:3L.21 定可機(jī)制:不親月 占1 oad/store指令數(shù)的百分比:66% 指令數(shù)拍百分比: 停頓:同 W停頓:165 占片總數(shù)的百分比:17.34 浮點(diǎn)指 指會(huì)條數(shù) 占指令總數(shù)的百分比:0 1oad停頓: 占所有停百分比:4 點(diǎn)停頓:0 白所有RA停啦百分比:0% 占浮點(diǎn)指令教的百 乘法 占浮點(diǎn)指令的百分比:C 結(jié)柯停轉(zhuǎn) 占周蝴總強(qiáng)分比:C 除法 占點(diǎn)指效的百分 片數(shù)的百分比:15.05863% 自停頓:0 占周期總的白分比:[ 自指會(huì) 倬頓局期總數(shù):36古周期總分比 421C5% 指令系數(shù) 占指令總教的百外比;隅 程序執(zhí)行統(tǒng)計(jì)情況:共950個(gè)周期,其中RAW沖突占165個(gè)周期,占比17.36% ()對(duì)優(yōu)化后的程序使用定向功能執(zhí)行,與剛才執(zhí)行結(jié)果進(jìn)行比較,況察執(zhí)行效率的 不同。 執(zhí)行結(jié)果 口統(tǒng)計(jì) 2統(tǒng)計(jì) 指令 丸行周期總封 掛之打數(shù):14 占指窆總數(shù)百分比:24.男6 I行了57指令 其中 支成功:131 占分支指令菱的百分比:91nR 硬仁西 內(nèi)存里:403王 加法器個(gè)數(shù) 熱行時(shí)問(周其教):f loadstore指 乖器個(gè)數(shù): 熱行時(shí)間周款}7 令氛教:1 占指令總歉的百分比:23 法怒個(gè)數(shù):1 鹽行時(shí)間(其)10 甘中 白機(jī)制:采用 1oad:⊥ 10 ad/stor∈指窆數(shù)的百分比:100 占1a/stxe指令款的百分 換(周數(shù) 1占局期總數(shù)的互分比:1.51085 且中 條數(shù):0指念總數(shù)的百分比: 占所有R停頓的百分比: 點(diǎn)停頓 凸所有RAw停頓的百分比 占浮點(diǎn)指剡百分比:U 占局總數(shù)的三分:0 占浮點(diǎn)指令的百分比:「 吉構(gòu)信輛:0 占浮點(diǎn)指拗的百過比 占總數(shù)光:19.6206 白陀停:0 占后相戶教的百升比:0% 白指 停頓周數(shù):1占周隱效的當(dāng)分比:21.1539% 令條數(shù):0 占指令總數(shù)的百分比:0 程序執(zhí)行統(tǒng)計(jì)情況:共728個(gè)周期,其中RAW沖突占11個(gè)周期,占比1.51% 采用定向技術(shù)之后,和不采用定向技術(shù)相比:執(zhí)行的時(shí)鐘周期總數(shù)減少了222個(gè)。執(zhí)行 效率是定向前的950/728=1.31(倍) 附錄 優(yōu)化前代碼: 數(shù)組大小 層循環(huán)計(jì)數(shù) 數(shù)組基址 內(nèi)層循環(huán)計(jì)數(shù) 載入 載入 跳轉(zhuǎn)到 交換 繼續(xù)內(nèi)層循環(huán) 繼續(xù)外層循環(huán) 附錄2 優(yōu)化后代碼 外層循環(huán)計(jì)數(shù) 數(shù)組基址 內(nèi)層循環(huán)計(jì)數(shù) 載入 載入 前瞻執(zhí)行 ,跳轉(zhuǎn)到 交換 繼續(xù)內(nèi)層循環(huán) 繼續(xù)外層循環(huán)