计算机系统结构实验4 使用MIPS指令实现冒泡排序法

Sekiro

计算机系统结构实验

发布于：2020年4月16日

次浏览

字数：1.9k字

时长：7分钟

本文是关于计算机系统结构实验四，使用MIPS指令实现冒泡排序法。

一、实验目的

掌握静态调度方法
增强汇编语言编程能力
学会使用模拟器中的定向功能进行优化

二、实验原理

通过编写MIPS汇编程序，实现冒泡排序的功能。在模拟器MIPSsim上执行所写的汇编程序，查看结果，判断所写的汇编程序是否正确。然后观察时钟周期图窗口的执行过程和冲突的指令，查看统计窗口的信息，来判断定向前后和优化前后的执行效率高低。

三、实验步骤及结果分析

1、自行编写一个实现冒泡排序的汇编程序，该程序要求可以实现对一维整数数组进行冒泡排序。

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

要求数组长度不得小于10

PS：汇编程序见附录。

2、启动 MIPSsim。

3、载入自己编写的程序，观察流水线输出结果。

载入的代码：

执行结果：

内存中的数组

原数组是{5,4,11,3,7,1,10,6,8,9,2}，排序后是{1,2,3,4,5,6,7,8,9,10,11}，结果符合预期，说明编写的汇编程序正确。
部分时钟周期图

可以看到有非常多的停顿，主要是DSUB命令与BGTZ命令的RAW停顿，还有一些控制停顿。
统计

发现RAW停顿有417个周期，停顿次数非常多，可以进行优化。共执行了1076个周期，RAW停顿占周期总数的百分比为38.75465%，所有的停顿为537个周期，占周期总数的百分比为49.90706%，效率很低。
$$
吞吐率TP_1=\frac{538}{1076\Delta{t}}
$$

$$
加速比S_1=\frac{538\times{5\Delta{t}}}{1076\Delta{t}}={2.5}
$$

4、使用定向功能再次执行代码，与刚才执行结果进行比较，观察执行效率的不同。

内存中的数组

结果正确。
部分时钟周期图

在使用定向技术后，发现停顿明显减少。
统计

发现RAW停顿有175个周期，停顿周期数比没有定向技术时的417个少了很多；

共执行了834个周期，比没有定向技术时的1076个也少了很多；

RAW停顿占周期总数的百分比为20.98321%，较没有定向技术时的38.75465%也减少了很多；

所有的停顿为295个周期，占周期总数的百分比为35.3717%，较没有定向技术时的49.90706%也减少了很多；

$$
吞吐率TP_2=\frac{538}{834\Delta{t}}
$$

$$
加速比S_2=\frac{538\times{5\Delta{t}}}{834\Delta{t}}\approx{3.23}
$$
吞吐率和加速比是没有定向技术时的$\frac{1076}{834}\approx{1.29}$倍。

5、采用静态调度方法重排指令序列，减少相关，优化程序

因为主要是DSUB命令与BGTZ命令的RAW停顿，分支指令的操作数需要用到前面的结果，因此将后面pass中执行的ADDIU $r4, $r4, 1和DSUB $r8, $r2, $r4拿到loop2中执行，从而减少RAW停顿。

PS：静态调度后的汇编程序见附录。

载入代码
内存中的数组

结果正确。
部分时钟周期图

在使用静态调度后，发现停顿少了很多。
统计

发现RAW停顿有142个周期，停顿周期数比没有静态调度时的417个少了很多；

共执行了801个周期，比没有静态调度时的1076个也少了很多；

RAW停顿占周期总数的百分比为17.72784%，较没有静态调度时的38.75465%也减少了很多；

所有的停顿为262个周期，占周期总数的百分比为32.70911%，较没有静态调度时的49.90706%也减少了很多；

$$
吞吐率TP_3=\frac{538}{801\Delta{t}}
$$

$$
加速比S_3=\frac{538\times{5\Delta{t}}}{801\Delta{t}}\approx{3.36}
$$

吞吐率和加速比是没有静态调度时的$\frac{1076}{801}\approx{1.34}$倍。

6、对优化后的程序使用定向功能执行，与刚才执行结果进行比较，观察执行效率的不同。

内存中的数组

结果正确。
部分时钟周期图

在使用静态调度和定向技术后，发现所有的RAW停顿几乎没有了，几乎只剩下了控制停顿。
统计

发现RAW停顿有10个周期，停顿周期数比没有静态调度和定向技术时的417个少了非常多；

共执行了669个周期，比没有静态调度和定向技术时的1076个也少了非常多；

RAW停顿占周期总数的百分比为1.494768%，较没有静态调度和定向技术时的38.75465%也减少了非常多；

所有的停顿为130个周期，占周期总数的百分比为19.43199%，较没有静态调度和定向技术时的49.90706%也减少了很多；

$$
吞吐率TP_4=\frac{538}{669\Delta{t}}
$$

$$
加速比S_4=\frac{538\times{5\Delta{t}}}{669\Delta{t}}\approx{4.02}
$$

吞吐率和加速比是没有静态调度和定向技术时的$\frac{1076}{669}\approx{1.61}$倍。

四、实验遇到的问题

本次实验中遇到了一个问题，如果main到下一个标签（比如loop1）只有一行汇编代码，在载入程序时，loop1的基地址就会和main重合，变为0x00000000，这样就导致loop1被覆盖，使载入的程序与自己编写的汇编程序不符，产生错误或者结果出错。但是如果>=2行汇编代码就不会有问题，我怀疑是MIPSsim程序的bug。

五、附录

1、初始的汇编代码

点击查看代码

.text
main:
ADDIU $r1, $r0, 11		# 数组长度n=11
ADDIU $r2, $r1, -1		# 外循环i=n-1=10

loop1:
ADDIU $r3, $r0, array	# 数组起始地址
ADDIU $r4, $r0, 0		# 内循环j=0

loop2:
LW $r5, 0($r3)			# a[j]
LW $r6, 4($r3)			# a[j+1]
DSUB $r7, $r6, $r5		# a[j+1]-a[j]
BGTZ $r7, pass			# a[j+1]>a[j]，不交换，跳到pass；

SW $r6, 0($r3)			# a[j+1]<a[j]，交换
SW $r5, 4($r3)

pass:
ADDIU $r4, $r4, 1		# j++
ADDIU $r3, $r3, 4		# 取数组的下一个元素
DSUB $r8, $r2, $r4		# i-j
BGTZ $r8, loop2			# i>j，跳转到loop2，继续内循环

ADDIU $r2, $r2, -1		# i--
BGTZ $r2, loop1			# i>0，跳转到loop1，继续外循环

TEQ $r0, $r0

.data
array: .word 5,4,11,3,7,1,10,6,8,9,2

2、经过静态调度后的汇编代码

点击查看代码

.text
main:
ADDIU $r1, $r0, 11		# 数组长度n=11
ADDIU $r2, $r1, -1		# 外循环i=n-1=10

loop1:
ADDIU $r3, $r0, array	# 数组起始地址
ADDIU $r4, $r0, 0		# 内循环j=0

loop2:
LW $r5, 0($r3)			# a[j]
LW $r6, 4($r3)			# a[j+1]
ADDIU $r4, $r4, 1		# j++
DSUB $r7, $r6, $r5		# a[j+1]-a[j]
DSUB $r8, $r2, $r4		# i-j
BGTZ $r7, pass			# a[j+1]>a[j]，不交换，跳到pass；

SW $r6, 0($r3)			# a[j+1]<a[j]，交换
SW $r5, 4($r3)

pass:
ADDIU $r3, $r3, 4		# 取数组的下一个元素
BGTZ $r8, loop2			# i>j，跳转到loop2，继续内循环

ADDIU $r2, $r2, -1		# i--
BGTZ $r2, loop1			# i>0，跳转到loop1，继续外循环

TEQ $r0, $r0

.data
array: .word 5,4,11,3,7,1,10,6,8,9,2