CS61c – Homework 4
EECS - University of California , Berkeley
TA in Charge: Chris
Submitting Your Solution
Submit your solution online by 11:59pm on July 21st . Do this by creating a directory named hw4 that contains a file named hw4.txt. “hw4.txt” is a text file that you create containing your answers to the following questions. From within that directory, type “submit hw4”.
This is not a partnership assignment; hand in your own work.
1. The following code fragment processes two arrays and produces an important value in register $v0. Assume that each array consists of 2500 words indexed 0 through 2499, that the base addresses of the arrays are stored in $a0 and $a1 respectively, and their sizes (2500) are stored in $a2 and $a3, respectively. Add comments to the code and describe in one sentence what this code does. Specifically, what will be returned in $v0?
| 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 |
2. Assume that the code from problem 1 is run on a machine with a 2 GHz clock that requires the following number of cycles for each instruction:
add, addi, sll: 1 Cycle
lw, bne: 2 Cycles
In the worst case, how many seconds will it take to execute this code?
3. Show the single MIPS instruction or minimal sequence of instructions for this C statement:
b = 25 | a;
4. Given your understanding of PC-relative addressing, explain why an assembler might have problems directly implementing the branch instruction in the following code sequence:
here: beq $s0, $s2, there
...
there: add $s0, $s0, $s0
Show how the assembler might rewrite this code sequence to solve these problems.
5. Consider the following fragment of C code:
for (i=0; i<=100; i=i+1) {a[i] = b[i] + c;}
Assume that a and b are arrays of words and the base address of a is in $a0 and the
base address of b is in $a1. Register $t0 is associated with variable i and register $s0
with c. Write the code for MIPS. How many instructions are executed during the running
of this code? How many memory data references will be made during execution?
6. You've seen this problem before. Give it another try now that you're not until any particular time pressure. Try to really understand it and how it works.
Examine the following section of MIPS code and use it to answer the questions that follow. You may assume that the first instruction is at memory address 1000 hex .
| j | magic | |
| tech: | addiu | $t1, $t1, 1 |
| sw | $t1, 0($t0) | |
| magic: | and | $s0, $s0, $s1 |
| la | $t0, magic | |
| lw | $t1, 0($t0) | |
| andi | $t2, $t1, 0x3f | |
| addi | $t3, $0, 0x26 | |
| bne | $t2, $t3, tech |
a) Convert the 4 th instruction, ( magic: and $s0, $s0, $s1 ) into machine code. Express your answer in binary, as clearly as possible.
b) Given that x is in $s0 and y is in $s1: with regard to the contents of $s0 and $s1, what three lines of C have the same result as the above MIPS.
c) Come up with a single MIPS instruction which has the same result as the provided code:
d) Translate the final instruction ( bne $t2, $t3, tech ) into machine code. Express your answer in hexadecimal.