Computer Organization: Problem Set 1

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


Instructions


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
          }                                          addi $t0, $t0, 1
          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?
    4. What does your solution illustrate about the concept of “optimization”?
  5. Consider the following MIPS procedure:

      mys:    addi $sp, $sp, -4
              sw   $ra, 0($sp)
              beq  $a0, $zero, L_0
              addi $a0, $a0, -1
              jal  mys
              sll  $t0, $v0, 2
              add  $v0, $t0, $v0
              j    L_1
     L_0:     addi $v0, $zero, 1
     L_1:     lw   $ra, 0($sp)
              addi $sp, $sp, 4
              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)
              add  $v0, $v0, $t1
              la   $t1, Weird
              lw   $t2, 4($t1)
              addi $t2, $t2, 4
              sw   $t2, 4($t1)
              addi $t0, $t0, -1
              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.