# Computer Organization: Problem Set 1

## Due Monday, November 18 (at the start of class)

#### Instructions

• Work entirely on your own.
• Your solution should be typed and printed with plenty of spacing within and between problems in black ink on otherwise blank paper that is stapled (assuming it is more than one page which it should be).
• For problems that ask you to write MIPS assembly language, only use those instructions which we have discussed in class. (If you are not sure whether you should use a particular instruction, just ask the instructor.)

#### The Problems Themselves

1. Consider the following MIPS procedure:

``````  mult_fun:
li \$t0, 43
multu \$a0, \$t0
mflo \$v0
jr \$ra``````
1. Is it a leaf or it is it recursive? Explain.

2. Assuming that `mult_fun` is called with `\$a0` containing a positive integer, what does it return? What assumptions about `\$a0` must hold for `mult_fun` to work correctly?

3. Rewrite the procedure as equivalent MIPS code (i.e., that returns equivalent values in `\$v0`) without using any explicit multiplication operations (i.e., without `multu`, `mflo`, etc.).

4. Which version (the original or your rewrite) is more efficient? Explain.

2. Consider the following C version of division. Assume `dividend` and `divisor` are nonnegative integers that have been specified in advance.

`````` int quotient = 0;
int remainder = dividend;
while (remainder >= divisor) {
quotient++;
remainder -= divisor;
}``````
1. In general, which would be more efficient: a MIPS translation of that code or the MIPS `div` instruction? Explain.

2. What happens in the C version if `divisor` is 0?

3. Consider the hardware division algorithms that we have discussed in class (and read about in section 3.4 of the course text; see for example diagrams 3.8, 3.9 and 3.11). What happens in hardware if the divisor is 0?

4. What do the previous two questions say about how division by 0 should be handled on a computer?

3. In the circuit diagrams that we studied for multiplication and division, we needed one special piece of hardware: a double-wide register. (That is it needs one register that is twice the width of the normal, word-sized registers in whatever architecture we are using.) This problem explores how we can simulate such a register in software. For example, if `\$t0` and `\$t1` were only 8-bits each and contained these values:

``````    \$t1       \$t0
10010100  11001011``````

the result of shifting the combined pair left one bit would be:

`` 00101001  10010110``
1. Write a minimal sequence of MIPS instructions that shifts left a single bit the pair of registers `\$t1`, `\$t0` where `\$t1` contains the most significant bits and `\$t0` the least significant bits.

2. Write a minimal sequence of MIPS instructions that shifts the pair of registers one bit to the right, logically.

3. Write a minimal sequence of MIPS instructions that shifts the pair of registers one bit to the right, arithmetically.

4. Consider the following C leaf procedure and a simple translation into MIPS:

``````  int foo(int n) {                        foo:   ori  \$v0, \$zero, 0
int s = 0;                                 ori  \$t0, \$zero, 0
int i;                              Loop:  slt  \$t1, \$t0, \$a0
for (i = 0; i < n; i++) {                  beq  \$t1, \$zero, Exit
s += i;                                add  \$v0, \$v0, \$t0
return s;                                  j    Loop
}                                       Exit:  jr   \$ra``````
1. If `foo` is called when `\$a0` contains the value 50, how many instructions are executed in the above MIPS code?
2. Write an “optimized” version of the MIPS assembly for `foo` in which only one jump or branch is executed each time through the loop.
3. If your optimized version of `foo` is called when `\$a0` contains the value 50, how many instructions are executed?
5. Consider the following MIPS procedure:

``````  mys:    addi \$sp, \$sp, -4
sw   \$ra, 0(\$sp)
beq  \$a0, \$zero, L_0
jal  mys
sll  \$t0, \$v0, 2
j    L_1
L_1:     lw   \$ra, 0(\$sp)
jr   \$ra``````
1. If the following fragment is executed, what value will result in register `\$s2`?

``````  ori \$a0, \$zero, 2
jal mys
ori \$s2, \$v0, 0``````
2. Translate the `mys` procedure into equivalent (but not necessarily line-by-line literal) C code.

3. In a clear and concise sentence, state what `mys` computes.

6. Consider the following C function:

``````  void wow(char s[]) {
int n = strlen(s);
int i;
for (i = 0; i < n; i++) {
s[i] = s[i] & 0xDF;
}
}``````
1. Translate `wow` to MIPS assembly language, assuming that `strlen` exists as function defined elsewhere that returns the length of a string and so that `wow` is not a leaf procedure. Indicate via comments which C variables correspond to which MIPS registers.

2. In a clear and concise sentence explain what the `wow` function accomplishes and of what feature of ASCII it takes advantage.

7. The MIPS instruction set (like any instruction set) is a compromise.

1. Consider the idea of adding a new instruction to MIPS called `bezi`. Syntactically, it would be used like

`` bezi \$s1, Label``

It is like `beq` except it compares the contents of the memory address associated with `\$s1` to `0`. It is essentially saying:

`` if Mem[Rs] == 0 then pc += offset``

where `offset` is the how far away (in memory addresses) `Label` is from the current instruction. Why might it be useful to have this instruction? What would have to change in the MIPS single-cycle datapath to implement it?

2. Identify one core MIPS instruction (an instruction that we studied in class, not a pseudoinstruction, and not multiplication nor division) that could be achieved via a few simple other MIPS instructions. Argue why you think MIPS’ designers chose to include it.

8. The load address pseudoinstruction, denoted by `la`, and used as:

``    la   \$s0, HERE``

takes the memory address that the assembler computes for symbolic address `HERE` and stores it in register `\$s0`. The assembler translates this to one or (usually) two instructions that use `ori` and (usually) `lui` to place the address in the register. This is a powerful feature of the assembler since otherwise it would be difficult to know the precise address where a symbolically-abstracted piece of data would be stored. Given that, consider the following MIPS assembly:

``````  cool:   li   \$v0, 0
lw   \$t0, 0(\$a0)
Weird:  beq  \$t0, \$zero, Exit
lw   \$t1, 4(\$a0)
la   \$t1, Weird
lw   \$t2, 4(\$t1)
sw   \$t2, 4(\$t1)
j    Weird
Exit:   jr   \$ra``````

Assume that the code represents a leaf procedure that takes one argument, `\$a0`, which represents the address of an array of integers.

1. If the array consists of the following elements:

``    5, 3, 7, -3, 9, 4, 1``

what does the procedure return in `\$v0`?

2. In a concise sentence or two, what does the `cool` procedure compute?

3. What important principle does this code illustrate? Explain.