CSE378 Midterm Exam

 

Answer all questions.  Show your work. 

 

1.      Imagine a computer with a 16 bit word. The computer is unique in that all of the customary features of 32 bit words are present, just smaller:  For example, the exponent field for floating point is not 8 bits, it is 6 bits. 

a)     What signed magnitude number is:                        0000 1010  0000 1010

2¹¹ + 2⁹ + 2³ + 2¹ = (2³ + 2¹)(2⁸ + 1) = 10 x 257 = 2570

 

b)     What two-s complement number is:                        1111 0101  1111 0101

The most significant bit is a 1, so the number is negative.

Complement the bits:           0000 1010 0000 1010

Add 1:                                     0000 1010 0000 1011 = -2571

 

c)      What is the 8-bit ASCII representation of:              0100 0001  0100 0010

2⁶ + 2⁰ = 65, which is the ASCII code for A

2⁶ + 2¹ = 66, which is the ASCII code for B

 

d)     What is the floating point number of:                       0100 0001  0100 0010

Sign bit is 0, so the number is positive

      Exponent is 2⁶ in excess-31 notation = 1

      Mantissa is normalized = 1.101000010

            Number is 2¹ x (1 + 1/2 + 1/8 + 1/256) = 3 33/128

 

8 points total:

For each part:

1 point for working.

1 point for a correct answer. For part c, this included any reasonable characters if they were one apart in the ASCII code. So 'B' and 'C' would get credit, as would 'E' and 'F' etc.

 

2.      If the short floating point numbers in the last question followed the IEEE 754 standard, but using its smaller exponent field, show the representation for +/- infinity that they would use?

Positive infinity    0111 1110 0000 0000

Negative infinity   1111 1110 0000 0000

 

2 points total:

1 point for showing that infinity has a positive and negative form.

1 point for the rest of the bit pattern.

 

3.      The instruction

mul      $t0, $t1, $t2

is multiply without overflow.  It is a pseudo instruction. What equivalent code will the assembler probably generate for this instruction?

mult $t1, $t2 OR multu $t1, $t2

mflo $t0

 

2 points total:

1 point for a multiply instruction (not mul).

1 point for moving the result from the lo register.

 

4.      Did the people who invented the MIPS ISA leave out Subtract Immediate to save opcodes or what?  Explain.

Yes, they did. addi with a negative immediate operand does the same task.

 

1 point.

 

5.      Give a 1-bit ALU design for a machine with the following features:

 

a)     Bitwise AND operation, i.e.  AND(a,b)

b)     Bitwise NOT operation, i.e.  NOT(a)

c)      Binary addition using a "ripple adder"

d)     Shift the a operand right by one bit position, i.e. DivBy2(a)

There is no need to handle overflow. The design should use the standard logic gates: and, or and not.  Label all inputs and outputs.

 

16 points total:

4 points for AND

4 points for NOT

4 points for the adder

4 points for the shift

 

6.      In twos complement binary addition what property or properties of the operands will assure that there will be no overflow?

If the operands have opposite signs, overflow cannot occur

 

1 point

 

7.      Write a MIPS assembly language procedure to determine how many bytes two null-terminated strings have in common before they are differ.  Specifically, in $a0 and $a1 are the addresses of two null-terminated strings.  Return in $v0 the number of bytes, starting at the beginning, that match.  Recall that the strings could both be empty, they could completely match and one could be the prefix of the other.

            addi    $t0,   $a0,    0             # Copy address of first string

            addi    $t1,   $a1,    0             # Copy address of second string

            addi    $v0,  $zero, 0             # Initialize matched characters count

 

loop:    lb         $t2,   0($t0)                 # Load character from first string

            beq     $t2,   $zero, exit         # Exit if it is a null character

            lb         $t3,   0($t1)                 # Load character from second string

 

            bne      $t2,   $t3,      exit         # Exit if the characters don’t match

            addi    $v0,  $v0,     1             # Increment matched characters count

            addi    $t0,   $t0,      1             # Increment first string pointer

            addi    $t1,   $t1,      1             # Increment second string pointer

            j           loop                             # Start the loop body again

 

exit:     jr          $ra                              # Exit from the procedure

 

10 points total:

2 for setting up the function (stack manipulation - if you needed to save any registers)

2 for loading the characters from memory with lb

2 for correct termination conditions (empty strings, non-equal characters)

2 for incrementing the pointers, registers

2 for returning the correct value and reseting the stack (again only if you needed to restore registers)

 

8.  The following binary sequence is a load word instruction

	1001 1100 0100 0001 0000 0000 0000 1100

 

 

 

And the following binary sequence is a branch on equal instruction

	0001 0000 0100 0001 0000 0000 0000 1100

 

 

 

After the opcodes, they look identical.  In what way are they not identical?  Explain.

The main difference is in the interpretation of the offset/displacement field. In the load instruction, it is in bytes. In the branch instruction, it is in words.

 

2 points total:

1 for identifying the difference is in the displacement field.

1 for mentioning byte versus word offsets.

 

8.      Write a 5 instruction sequence that takes the word whose address is given in $a0 and changes its "endianness", i.e. switches if from big-endian to little-endian.

This question was dropped from the midterm due to an error in the question.

 

9.  Registers are very useful, but modern computers tend only to have 32 general purpose registers.  Explain why architects do not increase that number.

A smaller number of registers is faster. Increasing the registers beyond 32 slows the CPU down too much.

 

1 point.