计算机组成习题答案(清华大学出版社) 下载本文

31 j

i 0

(31–j)位 31 0 (32–(j–i) )位

(j–i)位 (i+1)位 0 000 (j–i)位

参考答案:

可以先左移9位,然后右移15位,即:

sll $s2, $s0, 9 srl $s2, $s2, 15

思考:(1) 第二条用算术右移指令sra 行不行?

不行,因为不能保证高位补0!

(2) 若第一条指令中的$s2改成其他寄存器R,则会带来什么问题? 所用寄存器R的值被破坏!

9. 以下程序段是某个过程对应的指令序列。入口参数int a和int b分别置于$a0和$a1中,返回参数是该

过程的结果,置于$v0中。要求为以下MIPS指令序列加注释,并简单说明该过程的功能。

add $t0, $zero, $zero loop: beq $a1, $zero, finish add $t0, $t0, $a0 sub $a1, $a1, 1 j loop

finish: addi $t0, $t0, 100 add $v0, $t0, $zero

参考答案:

1:将t0寄存器置零

2:如果a1的值等于零则程序转移到finish处 3:将t0和a0的内容相加,结果存放于t0 4:将a1的值减1

5:无条件转移到loop处

6:将t0的内容加上100,结果存放于t0 7:将t0的值存放在v0

该程序的功能是计算“100+a×b” 10. 下列指令序列用来对两个数组进行处理,并产生结果存放在$v0中。假定每个数组有2500 个字,

其数组下标为0到2499。两个数组的基地址分别存放在$a0和$a1中,数组长度分别存放在$a2和$a3中。要求为以下MIPS指令序列加注释,并简单说明该过程的功能。假定该指令序列运行在一个时钟频率为2GHz的处理器上,add、addi和sll指令的CPI为1;lw和bne指令的CPI为2,则最坏情况下运行所需时间是多少秒?

sll $a2, $a2, 2 sll $a3, $a3, 2

add $v0, $zero, $zero

add $t0, $zero, $zero

outer: add $t4, $a0, $t0 lw $t4, 0($t4) add $t1, $zero, $zero inner: add $t3, $a1, $t1 lw $t3, 0($t3) bne $t3, $t4, skip

addi $v0, $v0, 1

skip: addi $t1, $t1, 4

bne $t1, $a3, inner addi $t0, $t0, 4 bne $t0, $a2, outer

参考答案:

1:将a2的内容左移2位,即乘4 2:将a3的内容左移2位,即乘4 3:将v0置零 4:将t0置零

5:将第一个数组的首地址存放在t4 6:取第一个数组的第一个元素存放在t4 7:将t1置零

8:将第二个数组的首地址存放在t3 9:取第二个数组的第一个元素存放在t3 10:如果t3和t4不相等,则跳转到skip 11:将v0的值加1,结果存于v0 12:将t1的值加4,结果存于t1

13:如果t1不等于a3,即还未取完数组中所有元素,则转移到inner 14:将t0的值加4

15:如果t0不等于a2,即还未取完数组中所有元素,则转移到outer 该程序的功能是统计两个数组中相同元素的个数。 程序最坏的情况是:两个数组所有元素都相等,这样每次循环都不会执行skip。因此,指令总条数为:5+2500×(3+2500×6+2)=37512505,

其中:add,addi和sll的指令条数为:4+2500×(2+2500×3+1)=18757504 lw和bne的指令条数为: 1+2500×(1+2500×3+1)=18755001 所以:程序执行的时间为:(2GHzclock的clock time=1/2G=0.5ns) (18757504×1+18755001×2) ×0.5ns = 28133753ns≈0.028s 11. 用一条MIPS指令或最短的指令序列实现以下C语言语句:b=25|a。假定编译器将a和b分别分配到

$t0和$t1中。如果把25换成65536,即b=65536|a,则用MIPS指令或指令序列如何实现? 参考答案:

只要用一条指令ori $t1, $t0, 25就可实现。

如果把25换成65536,则不能用一条指令ori $t1, $t0, 65536来实现,因为65536(1 0000 0000 0000 0000B)不能用16位立即数表示。可用以下两条指令实现。

lui $t1, 1

or $t1, $t0, $t1

12. 以下程序段是某个过程对应的MIPS指令序列,其功能为复制一个存储块数据到另一个存储块中,存

储块中每个数据的类型为float,源数据块和目的数据块的首地址分别存放在$a0和$a1中,复制的数据个数存放在$v0中,作为返回参数返回给调用过程。在复制过程中遇到0则停止,最后一个0也需要复制,但不被计数。已知程序段中有多个Bug,请找出它们并修改。

addi $v0, $zero, 0

loop: lw $v1, 0($a0) sw$v1, 0($a1) addi $a0, $a0, 4 addi $a1, $a1, 4 beq$v1, $zero,loop 参考答案:

修改后的代码如下: addi $v0, $zero, 0 loop: lw $v1, 0($a0) sw $v1, 0($a1) beq $v1, $zero, exit addi $a0, $a0, 4 addi $a1, $a1, 4 addi $v0, $v0, 1 j loop exit: 13. 说明beq指令的含义,并解释为什么汇编程序在对下列汇编源程序中的beq指令进行汇编时会遇到问

题,应该如何修改该程序段?

here: beq$s0, $s2, there ……

there: addi $s1, $s0, 4 参考答案:

beq是一个I-型指令,可以跳转到当前指令前,也可以跳转到当前指令后。其转移目的地址的计算公式为:PC+4+offset×4,offset是16位带符号整数,用补码表示。因此,分支指令beq的相对转移范围如下。

其正跳范围为:0000 0000 0000 0000(4)~ 0111 1111 1111 1111(217=4+(215–1)×4) 负跳范围为:1000 0000 0000 0000(4–217=4+(–215)×4)~ 1111 1111 1111 1111(0=4+(–1)×4) 超过以上范围的跳转就不能用上述指令序列实现。 因此,上述指令序列应该改成以下指令序列: here: bne $s0, $s2, skip j there skip: …… ……

there: add $s0, $s0, $s0 14. 以下C语言程序段中有两个函数sum_array和compare,假定sum_array函数第一个被调用,全局变

量sum分配在寄存器$s0中。要求写出每个函数对应的MIPS汇编表示,并画出每个函数调用前、后

栈中的状态、帧指针和栈指针的位置。

1 int sum=0;

2 int sum_array(int array[], int num) 3 { 4 int i; 5 for (i = 0; i

9 int compare (int a, int b) 10 { 11 if ( a>b) 12 return 1; 13 else 14 return 0; 15 }

参考答案(图略):

程序由两个过程组成,全局静态变量sum分配给$s0。 为了尽量减少指令条数,并减少访问内存次数。在每个过程的过程体中总是先使用临时寄存器$t0~$t9,临时寄存器不够或者某个值在调用过程返回后还需要用,就使用保存寄存器$s0~$s7。

MIPS指令系统中没有寄存器传送指令,为了提高汇编表示的可读性,引入一条伪指令move来表示寄存器传送,汇编器将其转换为具有相同功能的机器指令。伪指令“move $t0, $s0”对应的机器指令为“add $t0,$zero,$s0”。

(1)过程set_array:该过程和教材中例5.10中的不同,在例5.10中array数组是过程sum_array的局部变量,应该在过程栈帧中给数组分配空间,但该题中的数组array是在其他过程中定义的,仅将其数组首地址作为参数传递给过程sum_array(假定在在$a0中),因此,无需在其栈帧中给数组分配空间。此外,还有一个入口参数为num(假定在$a1中),有一个返回参数sum,被调用过程为compare。因此,其栈帧中除了保留所用的保存寄存器外,还必须保留返回地址,以免在调用过程compare时被覆盖。是否保存$fp要看具体情况,如果确保后面都不用到$fp,则可以不保存,但为了保证$fp的值不被后面的过程覆盖,通常情况下,应该保存$fp的值。

栈帧中要保存的信息只有返回地址$ra和帧指针$fp,其栈帧空间为4×2=8B。 汇编表示如下:

move $s0, $zero # sum=0

set-array:addi $sp, $sp, –8 # generate stack frame sw $ra, 4($sp) # save $ra on stack sw $fp, 0($sp) # save $fp on stack addi $fp, $sp, 4 # set $fp move $t2, $a0 # base address of array

move $t0, $a1 # $t0=num move $t3, $zero # i=0

loop: slt $t1, $t3, $t0 # if i=num, $t1= 0 beq $t1, $zero, exit1 # if $t1= 0, jump to exit1 move $a0, $t0 # $a0=num move $a1, $t3 # $a1=i