Exam 3 (Final) Review

Broadly, the exam may contain the following types of questions:

As for the content of the questions, this is derived from the following sources:

Overall, the final exam is comprehensive. It is intended to be of moderate difficulty, and it is expected to require the full time block to complete. I also tend to use questions similar to those which tended to score poorly in the past, in order to ensure that previously shaky material has since been learned.

Note that answers to these questions will not be provided online, though the questions may be discussed with us. This is because the questions overlap significantly with some of the labs, and so providing these answers inadvertantly provides answers to some of the labs.

Material Since Last Exam

  1. Consider the truth table augmented with don't cares, shown below:
    A B C D U
    00001
    0001X
    00100
    00111
    0100X
    01011
    01100
    0111X
    10001
    10010
    1010X
    10110
    11001
    11010
    1110X
    11110

    Using the above truth table, write out the following:

    1. The unoptimized sum-of-products equation, skipping over don't cares
    2. A Karnaugh map, along with boxes which exploit don't cares where appropriate
    3. An optimized sum-of-products equation, derived from the Karnaugh map created in the previous step

  2. Design a two-bit arithmetic logic unit (ALU) that has the following operations:

    Specifically, your ALU will have the following inputs:

    Input Name Input Description
    A0 Bit 0 of the first operand
    A1 Bit 1 of the first operand
    B0 Bit 0 of the second operand
    B1 Bit 1 of the second operand
    S0 Select bit 0, used for specifying the operation to perform (see table below)
    S1 Select bit 1, used for specifying the operation to perform (see table below)

    As for which operation should be performed, this is based on the values of inputs S0 and S1. The table below described the values that correspond to the different operations:

    Value for S0 Value for S1 Operation
    0 0 Addition
    0 1 AND
    1 0 OR
    1 1 XOR

    For this task, you may use the following provided components, in unlimited supply:

  3. Design a finite state machine (FSM) which will set a particular output U to 1 each time 1001 is encountered in a stream of inputs. Inputs are specified one at a time, and are represented by the variable I. To illustrate, consider the following example, which shows different values of U and I over time, where each cell is separated by a clock tick:

    I 1 1 0 0 1 0 0 1 1
    U 0 0 0 0 0 1 0 0 1

    For this task, you should be able to:

    1. Draw the FSM
    2. Define how many latches/flip-flops are necessary to implement your design
    3. Draw a truth table corresponding to this FSM, taking into account the inputs, outputs, current state, and next state.
  4. Given a 32-bit hexadecimal value, write how it is represented in memory on a big-endian system.
  5. Given a 32-bit hexadecimal value, write how it is represented in memory on a little-endian system.
  6. What are two problems with floating point, as represented according to the IEEE-754 standard?
  7. A floating point number consists of three parts, according to the IEEE-754 standard. Which parts are these, and how do they combine to form the overall floating-point value?

Material From Exam 1 Which is Likely to Return

  1. What is the most positive number representable in 8 bits, in an unsigned setting?
  2. What is the most positive number representable in 8 bits, in a two's complement setting?
  3. What is the most negative number representable in 8 bits, in a two's complement setting?
  4. What is the difference between the add and addu instructions, in terms of how they are implemented in the processor itself?

  5. Consider the instruction below:

    addiu $t0, $t0, -1

    The instruction above correctly decrements the value stored in register $t0, despite the fact that the instruction's full name has “unsigned” in the name. Why does this work correctly? That is, why does a negative immediate operand make sense in what appears to be an unsigned setting?

  6. Write some C code to extract bits 3 through 7 of an input char (one byte) in an unsigned setting. The result should be returned in a char (one byte).
  7. Write some C code to extract bits 3 through 7 of an input char (one byte) in a signed setting. The result should be returned in a char (one byte).
  8. Write some C code to return non-zero if bit 12 of a given input int is a 0, else return 0.
  9. What's the difference between a logical shift right and an arithmetic shift right?
  10. Be able to translate C code using conditionals, non-trivial branches, and loops into MIPS assembly. The following is one such example: 
    int s0;
int s1 = 0;
for (s0 = 0; 7 >= s0; s0++) {
  if (s0 > 3 || s0 == 1) {
    s1++;
  }
}
  11. In C, what does it mean if a given behavior is undefined? What is one example of such a behavior?
  12. Why is it that the li psuedoinstruction cannot always be implemented as a single hardware instruction?

Material From Exam 2 Which is Likely to Return

  1. Spot the bug in a snippet of MIPS assembly code, and describe a potential solution to the problem
  2. Be able to translate C code which uses pointer arithmetic into MIPS assembly. One such example is below: 
    int s0 = 0;
for (s1 = s2; s1 < s2 + s3; s1++) {
  s0 = s0 + *s1;
  *s1 = s0 + s3;
}

  3. Be able to translate C code with function calls into MIPS assembly, using the MIPS calling convention. For full credit, the MIPS assembly should be minimal, meaning:

    Additionally, your MIPS code should not involve optimizations of the C code. This means that function definitions cannot be inlined, parameter ordering swapped, loops unrolled, loop guards repositioned, tail recursion optimizations introduced, etc.

    An example of one possible problem is below: 

    unsigned int foo(unsigned int x, unsigned int y) {
  return x - y;
}
unsigned int bar(unsigned int x, unsigned int y) {
  unsigned int a = foo(x, y);
  unsigned int b = foo(y, x);
  unsigned int c = foo(x - y, x + y);
  return (a - b) * c;
}

    An example of a similar problem is shown below: 

    unsigned int baz(unsigned int x) {
  if (x == 0 || x == 1) {
    return x;
  } else {
    return baz(x - 1) + baz(x - 2);
  }
}

  4. Consider the C code below:

    // s0 already holds a value of type int*
// s1 already holds a value of type unsigned int
unsigned int s2 = s0[s1];
unsigned int s3 = s0[s1 - 1];
unsigned int s4 = s0[s1 + 1];

    Assume that variables s0 through s4 represent MIPS registers $s0 through $s4. Additionally, register $t0 can be used in the MIPS code. With these assumptions, it's possible to implement the above code using only five instructions. Write the code snippet necessary to achieve this.

  5. When do we have to use the la psuedoinstruction? (Hint: the correct answer is not “whenever memory is accessed”, as not all memory accesses need la.)

  6. Consider the MIPS code below:

    foo:
  addiu $sp, $sp, -8
  sw $ra, 0($sp)
  sw $a0, 4($sp)
  jal bar
  lw $a0, 4($sp)
  jal baz
  lw $ra, 0($sp)
  lw $a0, 4($sp)
  addiu $sp, $sp, 8
  jr $ra

    Assume that bar and baz both take a single parameter in $a0, which should be the same value as when foo was first called. Additionally, bar and baz both manipulate some global variables, so they do necessary work even though their return values aren't used. With all of this in mind, there is an instruction in foo which could be removed. Which instruction is it, and why can it be removed? (Hint: it has to do with the MIPS calling convention.)