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. What's the difference between a logical shift right and an arithmetic shift right?
  9. 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; s0 <= 7; s0++) {
  if (s0 > 3 || s0 == 1) {
    s1++;
  }
}

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, 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);
  }
}