计算机组成原理mips汇编大作业报告（冒泡排序、选择排序）_mips模型机实验原理

1. 请结合冯诺依曼思想，对本次实践所使用的模型机进行描述，并对比《单周期MIPS (硬布线)》中使用的模型机的相同和不同之处。
   问题一：结合冯诺依曼思想，对本次实践所用的模型机进行描述
   冯诺依曼思想：计算机处理的数据和指令一律用二进制数表示，顺序执行程序，计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分构成。
   在本次实验所使用的模型机中，除了最开始输入存储器的指令为16进制之外，在该模型机内部接收或者传输的指令都为2进制。
   在该模型机中，需要把要执行的指令和处理的数据首先存入存储器中，程序执行时，将自动地并按顺序从存储器中取出指令一条一条地执行。
   本模型机的运算器为：
   运算器由算数逻辑单元ALU、状态寄存器、通用寄存器等组成
   算数逻辑单元ALU如图1-1，打开后如图1-2
   
   
   状态寄存器如图1-3
   

通用寄存器如图1-4

本模型机的控制器如图1-5，打开后如图1-6，分析如下：1.控制器的输入信号为：指令字，Func字段，时钟信号，复位信号2.控制器的输出信号为：多路选择器选择信号，内存访问控制信号，寄存器写使能信号，运算器控制信号，指令译码信号


本模型机的存储器如图1-7

问题二：两模型机的相同之处与不同之处
相同之处：两模型机都符合冯诺依曼思想：对于单周期来说也包含存储器，运算器，控制器。且整个数据和指令在内部也以二进制的方式传输。符合顺序执行，需要把要执行的指令和处理的数据首先存入存储器中，程序执行时，将自动地并按顺序从存储器中取出指令一条一条地执行。
不同之处：

1. 定义不同：单时钟周期硬布线是一个时钟周期执行一条指令，多时钟周期硬布线是一条指令多个时钟周期。
   2.在单周期中含有数据存储器和指令存储器，指令和数据分开存放。但在多周期硬布线中存储器未分开使用，由IorD来控制是数据还是指令。IorD为0，则选择上面的指令，IorD为1则选择下面的数据。如图2-1
   
   3.在单周期硬布线中没有PCWrite,即不能对PC进行写操作，但在多周期硬布线中含有PCwrite，在多周期硬布线中要进行跳转去更改PC的值，一条指令占用不止一个时钟周期，有多个时钟周期，要执行PC+4->PC操作。如图2-2、2-3
   
   
   4.在单周期硬布线中只含有一个AluSrcB,但在多周期硬布线中同时含有AluSrcB和AluSrcA。如图2-4
   
   5.单周期硬布线无微程序控制器，为组合逻辑控制器，而多周期硬布线具有多周期微程序控制器，打开控制存储器如图2-5：
   
   以013201和030010为例分析：
   013201H=0000 0001 0011 0010 0000 0001
   第3~0位：0001表示下一微地址指令地址为1
   第4位：0，判断逻辑，将下址字段送入Uar。如图2-6
   
   第6~5位: 00 ALU_Control为00，则ALU_OP=5。如图2-7
   
   第14~7位：011 0010 0，则MemRead=1,PcWrite=1,IRWrite=1。如图2-8
   
   第16~15位：01，ALUSrcB=01,则将00000004传入ALUB端，即进行PC+4，如图2-9、2-10
   
   
   第19~17：000

030010H=0000 0011 0000 0000 0010 0000
第3~0位：0000表示下一微地址指令地址为0，但是第四位为1，所以没有选中
第4位：1，判断逻辑，将微程序入口送入Uar。如图2-11

第6~5位：00 ALU_Control=00,则ALU_OP=5。如图2-12

第14~7：都为0
第16~15：10，ALUSrcB=10,则将扩展过的32位立即数传入B端。如图2-13

第19~17:001，ALUSrcA=1,则将R1的值传入A端。如图2-14

2. 结合自己所学知识，请对所给的冒泡法排序程序进行分析。
冒泡排序的原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。
以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。
有n个数据，则需比较n-1轮。
冒泡排序的伪代码如图3-1：

C代码如图3-2：

此段代码分析如下：

.text
#################################################################################
#本程序实现0x80开始的8个字单元的降序排序,此程序可在mars mips仿真器中运行,字地址0x80
#运行时请将Mars Setting中的Memory Configuration设置为Compact，data at address 0
#
#################################################################################
 .text
sort_init:
 addi $s0,$0,-1          给$s0赋值为-1，将-1+$0的值传到$s0号寄存器中 
 addi $s1,$0,0           $S1就是相当于C语言的int i，即给i赋初值为0
 sw $s0,128($s1)         写入到实际地址$s1 0x80单元   128*4/4=128=0x80
 addi $s0,$s0,1          给$s0赋值为0，将1+$s0=1+(-1)=0的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+4)/4=129=0x81单元  
 addi $s0,$s0,1          给$s0赋值为1，将1+$s0=1+0=1的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+8)/4=130=0x82单元
 addi $s0,$s0,1          给$s0赋值为2，将1+$s0=1+1=2的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+12)/4=131=0x83单元
 addi $s0,$s0,1          给$s0赋值为3，将1+$s0=1+2=3的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+16)/4=132=0x84单元
 addi $s0,$s0,1          给$s0赋值为4，将1+$s0=1+3=4的值传到$s0号寄存器中
addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+20)/4=133=0x85单元
 addi $s0,$s0,1          给$s0赋值为5，将1+$s0=1+4=5的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+24)/4=134=0x86单元
 addi $s0,$s0,1          给$s0赋值为6，将1+$s0=1+5=6的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+28)/4=135=0x87单元
 
 add $s0,$zero,$zero      $s0=0，即int i=0
 addi $s1,$zero,28   #排序区间  $s1=28,即int j=7;
sort_loop:
 lw $s3,128($s0)          把0x80里的值赋给$s3,即temp1=A[i],后面循环后为0x81\0x82...          
 lw $s4,128($s1)          把0x87里的值赋给$s4,即temp2=A[j],后面循环时即为0x86\0x85...
 slt $t0,$s3,$s4          若$s3<$s4,则$t0=1,反之为0
 beq $t0,$0,sort_next   #降序排序     为真则跳过直接执行下一循环，为假则交换
 sw $s3, 128($s1)         把s3寄存器的值传给0x87单元,即A[j]=temp1 后面循环时依次递减
 sw $s4, 128($s0)         把s4寄存器的值传给0x80,即A[i]=temp2,后面循环时为0x81\0x82...
sort_next:
 addi $s1, $s1, -4        将$s1-4的值存入s1寄存器中,即j=j-1/2/3/.....
 bne $s0, $s1, sort_loop  继续内层循环
 
 
 addi $s0,$s0,4           将$s0+4的值存入$0号寄存器，即i=i+1
 addi $s1,$zero,28        将28传入$s1中，即恢复int j=7，表示由于i引起变化新一轮内循环重新开始
 bne $s0, $s1, sort_loop  $s0不等于$s1时。跳转到上面执行循环，相等时表示排序已结束，退出
 addi   $v0,$zero,10         # system call for exit
 syscall                  # we are out of here.   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

代码运行结果分析示意图如图3-3：

3. 请用另一种排序法将“2”中数据按照由大到小排序。若需要添加指令，请对控制器做修改。
此题选用选择排序的方法：
选择排序：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
选择排序伪代码如图4-1：

C语言代码如图4-2：

汇编代码如下：

.text
sort_init:
 addi $s0,$0,-1          给$s0赋值为-1，将-1+$0的值传到$s0号寄存器中 
 addi $s1,$0,0           $S1就是相当于C语言的int i，即给i赋初值为0
 sw $s0,128($s1)         写入到实际地址$s1 0x80单元   128*4/4=128=0x80
 addi $s0,$s0,1          给$s0赋值为0，将1+$s0=1+(-1)=0的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+4)/4=129=0x81单元  
 addi $s0,$s0,1          给$s0赋值为1，将1+$s0=1+0=1的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+8)/4=130=0x82单元
 addi $s0,$s0,1          给$s0赋值为2，将1+$s0=1+1=2的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+12)/4=131=0x83单元
 addi $s0,$s0,1          给$s0赋值为3，将1+$s0=1+2=3的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+16)/4=132=0x84单元
 addi $s0,$s0,1          给$s0赋值为4，将1+$s0=1+3=4的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+20)/4=133=0x85单元
 addi $s0,$s0,1          给$s0赋值为5，将1+$s0=1+4=5的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+24)/4=134=0x86单元
 addi $s0,$s0,1          给$s0赋值为6，将1+$s0=1+5=6的值传到$s0号寄存器中
 addi $s1,$s1,4          将$s1+4的值传入到$s1号寄存器中，即c代码中的i=i+1
 sw $s0,128($s1)         写入实际地址 (128*4+28)/4=135=0x87单元
 
 add $s0,$zero,$zero        $s0=0，即int i=0
 addi $s1,$zero,32   #排序区间  $s1=32,即n=8;
 addi $s2,$s0,4             $s2=$s0+4，即 int j=i+1
 add $t1,$s0,$0             $t1=$s0+$0，即int m=i
sort_loop:
 lw $s3,128($s2)            从存储器中取出数存到寄存器$s3中
 lw $s4,128($t1)            从存储器中取出数存到寄存器$s4中
 slt $t0,$s3,$s4            若$s3<$s4,则$t0=1,反之为0
 bne $t0,$0,sort_next   #降序排序     相等则继续执行，不等则跳过交换步骤直接进入下一循环
 sw $s3, 128($t1)           将寄存器$3的数存到对应的地址单元即存储器内
 sw $s4, 128($s2)           将寄存器$4的数存到对应的地址单元即存储器内
sort_next:
 addi $s2, $s2, 4           将$s2+4的值存入s2寄存器中,即j=j+1/2/3/.....
 bne $s2, $s1, sort_loop  继续内层循环
 addi $s0,$s0,4             将$s0+4的值存入$s0号寄存器，即i=i+1
 addi $s2,$s0,4             将$s0+4的值存入$s2,即i=j+1
 add $t1,$s0,$0             将$s0+$0的值存入$t1，表示下一次外循环导致m的值重新等于i
 addi $s1,$zero,32          将32传入$s1中，即恢复int n=8，
 add $s6,$s1,-4             表示外循环i<n-1,此条指令算出n-1
 bne $s0, $s6, sort_loop     $s0不等于$s6时。跳转到上面执行循环，相等时表示排序已结束，退出
 addi   $v0,$zero,10         # system call for exit
 syscall                  # we are out of here.  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

汇编代码对应的16进制指令如下：

2010ffff 20110000 ae300200 22100001 22310004 ae300200 22100001 22310004
ae300200 22100001 22310004 ae300200 22100001 22310004 ae300200 22100001
22310004 ae300200 22100001 22310004 ae300200 22100001 22310004 ae300200
8020 20110020 22120004 02004820 8e530200 8d340200 274402a 15000002 ad330200 ae540200 22520004 1651fff8 22100004 22120004 02004820 20110020 2236fffc 1616fff2 2002000a c

1
2
3
4
5

程序的运行结果如图


以上为此次实验全部内容，欢迎讨论！