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