Transcript ppt

CS232 Exam 1
Solutions
February 20, 2004
Name:






This exam has 5 pages, including this cover.
There are three questions, worth a total of 100 points.
The last page is a summary of the MIPS instruction set, which
you may remove for your convenience.
No other written references or calculators are allowed.
Write clearly and show your work. State any assumptions you make.
You have 50 minutes. Budget your time, and good luck!
Question
Maximum
1
40
2
45
3
15
Total
100
1
Your Score
Question 1: Understanding MIPS programs (40 points)
func:
L1:
L2:
L3:
li
li
add
lb
beq
bne
add
add
j
jr
$v0,
$t0,
$t1,
$t2,
$t2,
$t2,
$v0,
$t0,
L1
$ra
0
0
$a0, $t0
0($t1)
$zero, L3
$a1, L2
$v0, 1
$t0, 1
Part (a)
Translate the function func above into a high-level language like C or Java. You should include a header that lists the types of any
arguments and return values. Also, your code should be as concise as possible, without any gotos or pointers. We will not deduct
points for syntax errors unless they are significant enough to alter the meaning of your code. (30 points)
int func (char s[], char c)
{
int num = 0;
for(int i=0;s[i] !=0;i++)
{
if(s[i] = = c)
num++;
}
return num;
}
Part (b)
Describe briefly, in English, what this function does. (10 points)
Counts the number of occurrences of the second argument (a character) in the character array (first argument) and returns the
count when it finds a zero in the array.
2
Question 2: Write a recursive function (45 points)
Here is a function is_prime_rec that takes two arguments (i and P, both 32-bit numbers) and returns an
integer; 1 is returned if P is found to be prime, otherwise 0 is returned. This function is used by the function
is_prime.
int
is_prime_rec(int i, int P) {
if (i <= 1)
return 0;
if ((P % i) == 0)
return 1;
return is_prime_rec(i-1, P);
}
int
is_prime(int P) {
return is_prime_rec(P-1, P);
}
Translate is_prime_rec into a MIPS assembly language function. You do not need to translate
is_prime!! Argument registers $a0 and $a1 will correspond to i and P, and the return value should be
placed in $v0 as usual. Use the rem pseudoinstruction for the mod (%) operator .
Your implementation must be recursive. You will not be graded on the efficiency of your code, but you
must follow all MIPS conventions. Comment your code!!!
Is_prime_rec:
subi $sp, $sp, 4
sw $ra, 0($sp)
#allocate stack
bgt $a0, 1 L1
li $v0, 1
j exit
#if (I>1) branch to L1
L1:
rem $to, $ao, $a0 #rem = (P%i)
bne $t0, $zero, L2 #if(rem !=0), branch to L2
li $v0, 0
j exit
L2:
subi $a0, $a0, 1 #i = i-1
jal is_prime_rec
Exit:
lw $ra, 0($sp)
add $sp, $sp, 4
jr $ra
#restore ra
#cleanup stack
#return $v0
3
Question 3: Concepts (15 points)
Write a short answer to the following questions. For full credit, answers should not be longer than two
sentences.
Part a) What is abstraction? How does it relate to instruction set architectures (ISAs)? (5 points)
Abstraction is the concept of hiding complexity, e.g. by separating interface from implementation. ISAs
abstract the specification of what computation should be performed from how it is performed, allowing
binary code compatibility across a family of hardware implementations that implement the same ISA.
Part b) Why can IEEE floating point numbers represent a larger range of numbers than integers with the
same number of bits? (e.g., single precision can represent from 2-126 to 2127 while 32-bit integers can only
do 0 and from 1 to 232-1) It is not enough to simply give the IEEE format; you must explain what drawback
of floating point numbers enables the larger range. (5 points)
Since both representations use only 32 bits, there are as many single precision FP numbers as there are
integers. As the FP number values get farther from zero, it's less likely that they can be specified exactly
using the IEEE notation, which may result in rounding errors.
Part c) What is the 90/10 rule? How does it relate to assembly language programming? (5 points)
90/10 rule specifies that processor spends 90% of the time executing 10% of the code. To best optimize these
10%, implement that code in the assembly language.
4
MIPS instructions
These are some of the most common MIPS instructions and pseudo-instructions, and should be all you
need. However, you are free to use any valid MIPS instructions or pseudo-instruction in your programs.
Category
Arithmetic
Example Instruction
add
sub
addi
mul
div
rem
Meaning
$t0, $t1, $t2
$t0, $t1, $t2
$t0, $t1, 100
$t0, $t1, $t2
$t0, $t1, $t2
$t0, $t1, $t2
$t0 = $t1 + $t2
$t0 = $t1 – $t2
$t0 = $t1 + 100
$t0 = $t1 x $t2
$t0 = $t1 / $t2
$t0 = $t1 mod $t2
move $t0, $t1
li
$t0, 100
$t0 = $t1
$t0 = 100
Data Transfer
lw
sw
$t0, 100($t1)
$t0, 100($t1)
$t0 = Mem[100 + $t1]
Mem[100 + $t1] = $t0
Branch
beq
bne
bge
bgt
ble
blt
$t0, $t1, Label
$t0, $t1, Label
$t0, $t1, Label
$t0, $t1, Label
$t0, $t1, Label
$t0, $t1, Label
if ($t0 = $t1) go to Label
if ($t0 ≠ $t1) go to Label
if ($t0 ≥ $t1) go to Label
if ($t0 > $t1) go to Label
if ($t0 ≤ $t1) go to Label
if ($t0 < $t1) go to Label
Set
slt
slti
$t0, $t1, $t2
$t0, $t1, 100
if ($t1 < $t2) then $t0 = 1 else $t0 = 0
if ($t1 < 100) then $t0 = 1 else $t0 = 0
Jump
j
jr
jal
Label
$ra
Label
go to Label
go to address in $ra
$ra = PC + 4; go to Label
Register Setting
The second source operand of the arithmetic and branch instructions may be a constant.
Register Conventions
The caller is responsible for saving any of the following registers that it needs, before invoking a function.
$t0-$t9
$a0-$a3
$v0-$v1
The callee is responsible for saving and restoring any of the following registers that it uses.
$s0-$s7
$ra
5