这是Cousera上计算机组成的课后作业。主要考察MIPS汇编程序设计,要求熟悉MIPS指令系统的常见指令,掌握MARS集成开发环境基本使用方法,完成自编MIPS汇编语言程序的上机调试过程。

作业推荐使用MARS(MIPS Assembler and Runtime Simulator)集成开发环境作为实验平台,MARS是密苏里州立大学为配合《计算机组成与设计》一书,开发的一款专用于教学的MIPS汇编语言模拟器,并提供了丰富的调试功能。

MARS的官网链接如下:
http://courses.missouristate.edu/KenVollmar/Mars/index.htm

对于MIPS入门和MARS的使用可以看这个视频:
https://www.bilibili.com/video/av18785863

想更详细学习汇编可以看这门课:
汇编语言程序设计(2019春)

MIPS指令集在MARS的帮助中有详细的介绍,也可以参考下面这个相对简单的版本:
https://blog.csdn.net/yixilee/article/details/4316617

程序设计过程中需要用到ASCII码表:
https://zh.wikipedia.org/wiki/ASCII

用系统功能调用实现简单输入输出

利用系统功能调用从键盘输入,转换后在屏幕上显示,具体要求如下:
(1) 如果输入的是字母(A~Z,区分大小写)或数字(0~9),则将其转换成对应的英文单词后在屏幕上显示,对应关系见下表

AAlphaNNovember1Firstaalphannovember
BBravoOOscar2Secondbbravoooscar
CChinaPPaper3Thirdcchinappaper
DDeltaQQuebec4Fourthddeltaqquebec
EEchoRResearch5Fiftheechorresearch
FFoxtrotSSierra6Sixthffoxtrotssierra
GGolfTTango7Seventhggolfttango
HHotelUUniform8Eighthhhoteluuniform
IIndiaVVictor9Ninthiindiavvictor
JJulietWWhisky0zerojjulietwwhisky
KKiloXX-ray kkiloxx-ray
LLimaYYankee llimayyankee
MMaryZZulu mmaryzzulu

(2) 若输入的不是字母或数字,则在屏幕上输出字符“*”,
(3) 每输入一个字符,即时转换并在屏幕上显示,
(4) 支持反复输入,直到按“?”键结束程序。

            .data
u_word:	    .asciiz
            "Alpha ","Bravo ","China ","Delta ","Echo ","Foxtrot ",
	    "Golf ","Hotel ","India ","Juliet ","Kilo ","Lima ",
            "Mary ","November ","Oscar ","Paper ","Quebec ","Research ",
            "Sierra ","Tango ","Uniform ","Victor ","Whisky ","X-ray ",
            "Yankee ","Zulu "
uw_offset:  .word
            0,7,14,21,28,34,43,49,56,63,71,
            77,83,89,99,106,113,121,131,
            139,146,155,163,171,178,186
l_word:     .asciiz
            "alpha ","bravo ","china ","delta ","echo ","foxtrot ",
            "golf ","hotel ","india ","juliet ","kilo ","lima ",
            "mary ","november ","oscar ","paper ","quebec ","research ",
            "sierra ","tango ","uniform ","victor ","whisky ","x-ray ",
            "yankee ","zulu "
lw_offset:  .word
            0,7,14,21,28,34,43,49,56,63,71,
            77,83,89,99,106,113,121,131,
            139,146,155,163,171,178,186
number:     .asciiz
            "zero ", "First ", "Second ", "Third ", "Fourth ",
            "Fifth ", "Sixth ", "Seventh ","Eighth ","Ninth "
n_offset:   .word
            0,6,13,21,28,36,43,50,59,67
 
            .text
            .globl main
main:       # wrap
            addi $a0, $0, 0xA
	    addi $v0, $0, 0xB
            syscall

	    li $v0, 12 # read character
            syscall

            # is  '?'
            sub $t1, $v0, 63 # $v0 - 63 == 0
            beqz $t1, exit
            
            # others
            sub $t1, $v0, 48 # $v0 - 48 < 0
            slt $s0, $t1, $0
            bnez $s0, others
 
            # is number?
            sub $t2, $t1, 10 # $v0 - 48 -10 < 0    0~9
            slt $s1, $t2, $0
            bnez $s1, getnum
 
            # is capital?
            sub $t2, $v0, 91 # 64 < $v0 < 91      A~Z
            slt $s3, $t2, $0
            sub $t3, $v0, 64 
            sgt $s4, $t3, $0
            and $s0, $s3, $s4
            bnez $s0, getuword
 
            # is lower case?
            sub $t2, $v0, 123 # 96 < $v0 < 123      a~z
            slt $s3, $t2, $0
            sub $t3, $v0, 96 
            sgt $s4, $t3, $0
            and $s0, $s3, $s4
            bnez $s0, getlword
            
            # others
            j others
 
getnum:     add $t2, $t2, 10
            sll $t2, $t2, 2
            la $s0, n_offset
            add $s0, $s0, $t2
            lw $s1, ($s0)
            la $a0, number
            add $a0, $a0, $s1
            li $v0, 4
            syscall
            j main
 
            # upper case word
getuword:   sub $t3, $t3, 1
            sll $t3, $t3, 2
            la $s0, uw_offset
            add $s0, $s0, $t3
            lw $s1, ($s0)
            la $a0, u_word
            add $a0, $s1, $a0
            li $v0, 4
            syscall
            j main
 
            # lower case word
getlword:   sub $t3, $t3, 1
            sll $t3, $t3, 2
            la $s0, lw_offset
            add $s0, $s0, $t3
            lw $s1, ($s0)
            la $a0, l_word
            add $a0, $s1, $a0
            li $v0, 4
            syscall
            j main
 
others:     and $a0, $0, $0
            add $a0, $a0, 42 # '*'
            li $v0, 11 # print character
            syscall
            j main
            
exit:       li $v0, 10 # exit
            syscall

字符串查找比较

利用系统功能调用从键盘输入一个字符串,然后输入单个字符,查找该字符串中是否有该字符(区分大小写)。具体要求如下:
(1) 如果找到,则在屏幕上显示:

Success! Location: X

其中,X为该字符在字符串中第一次出现的位置

(2) 如果没找到,则在屏幕上显示:

Fail!

(3) 输入一个字符串后,可以反复输入希望查询的字符,直到按“?”键结束程序

(4) 每个输入字符独占一行,输出查找结果独占一行,位置编码从1开始。
提示:为避免歧义,字符串内不包含"?"符号
格式示例如下:

abcdefgh
a
Success! Location: 1
x
Fail!
            .data
msg_s:      .asciiz "\r\nSuccess! Location: "
msg_f:      .asciiz "\r\nFail!\r\n"
s_end:      .asciiz "\r\n"
buf:        .space 100

            .text
            .globl main
main:       la $a0, buf # address of input buffer
            la $a1, 100 # maximum number of characters to read
            li $v0, 8 # read string
            syscall

inputchar:  li $v0, 12 # read character
            syscall
            
            # if '?'
            addi $t7, $0, 63
            sub $t6, $t7, $v0
            beq $t6, $0, exit
            
            li $t0, 0 # t0=0
            la $s1, buf

find_loop:  lb $s0, 0($s1) # move s1 to s0
            sub $t1, $v0, $s0
            beq $t1, $0, success
            addi $t0, $t0, 1  # t0++
            slt $t3, $t0, $a1 # t0>=100 fail
            beq $t3, $0, fail
            addi $s1 $s1, 1
            j find_loop

success:    la $a0, msg_s
            li $v0, 4 # print string
            syscall
            addi $a0, $t0, 1
            li $v0, 1 # print integer
            syscall
            la $a0, s_end
            li $v0, 4
            syscall
            j inputchar

fail:       la $a0, msg_f
            li $v0, 4
            syscall
            j inputchar

exit:       li $v0, 10
            syscall

阅读下面的MIPS汇编程序,回答问题

.data
array:	.word   1,1,1
tmp:	.word   0 : 25
.text
	.globl main
main:
	la       $t0, array
	li       $t1, 25
loop:	lw       $t3, 0($t0)
	lw       $t4, 4($t0)
	lw       $t5, 8($t0)
	add       $t2, $t3, $t4
	add       $t2, $t2, $t5
	sw       $t2, 12($t0)
	addi       $t0, $t0, 4
	addi       $t1, $t1, -1
	bgtz       $t1, loop
	li    $v0, 10           # system call for exit
	syscall

请在你的作业中回答以下七道题:

1.请说明程序实现的功能。(5分)(提示:可以利用“Math”编辑输入数学公式,建议提交之前用Previe查看输入效果)
答:计算了一个数列a_{n} = a_{n-1} + a_{n-2} + a_{n-3},其中a_0 = a_1 = a_2 = 1

2.分析程序的访存行为,仅考虑数据访存。(5分)(提示:访存行为包括程序一共发生了多少次访存操作,每次访存操作的地址之间有什么样的关系等)
答:每次循环执行3条lw,1条sw,循环25次共访存100次。每次循环访问的4个地址均增加4。

3.根据MARS内置的Data Cache Simulation Tool,构建一个容量为8字节的cache,要求块大小为4字节(one word),替换策略为LRU,组策略为直接映射。运行上述MIPS程序,得到cache命中率为多少?(5分)
答:24%

4.结合程序的访存行为,详细分析问题3中cache miss的原因。
答:总共循环25次, round3之后的循环会重复round2/3的操作,总共miss cache = 76, hit = 24.

5.根据MARS内置的Data Cache Simulation Tool,构建一个容量为8字节的cache,要求块大小为4字节(one word),替换策略为LRU,组策略为全相联。运行上述MIPS程序,得到cache命中率为多少?(5分)
答:0%

6.结合程序的访存行为,详细分析问题5中cache miss的原因。(10分)
答:cache size为8 byte 而块大小为4 byte 那么总共就只有2个block。同时替换策略是LRU,组策略为全相联.所以每个block里面也只能放1个word(4 byte)。
假设Cache对于CPU的访存请求分别是0,1,2,3,…同时假设括号内为(_ , _)为cache的两个block

Round 1 (0,1,2,3)
 (0,void) miss -> (0,1) miss -> (2,1) miss -> (2,3) miss 

Round 2 (1,2,3,4)
(1,3) miss -> (1,2) miss -> (3,2) miss -> (3,4) miss

Round 3 (2,3,4,5)
(2,4) miss -> (2,3) miss -> (4,3) miss -> (4,5) miss

之后每次循环都会是miss,所以不会有hit的情况出现

7.(1) 保持其他参数不变,通过增加block数量的方式将cache的容量扩大为16个字节,评测不同组策略下cache命中率的变化,并分析原因?(2) 进一步扩大cache容量,cache命中率会如何变化?(10分)
答:16字节时,不同的组策略下均为72%。16字节时,cache 中能保存4个连续地址,第二次循环开始,每次循环中前三次都可以命中,命中率为3*24/100 = 72%。若继续扩大cache容量,命中率不变。

posted @ 2019-09-06 15:21:53
评论加载中...

发表评论