北邮 计算机系统结构实验四-使用MIPS指令实现冒泡排序

北邮 计算机系统结构实验四-使用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 优化后代码 外层循环计数 数组基址 内层循环计数 载入 载入 前瞻执行 ,跳转到 交换 继续内层循环 继续外层循环